static void all_shortest_path_with_given_source_and_dest_impl()

in flex/engines/graph_db/runtime/common/operators/retrieve/path_expand.cc [618:783]

• 163 lines of code
• 39 McCabe index (conditional complexity)

static void all_shortest_path_with_given_source_and_dest_impl(
    const GraphReadInterface& graph, const ShortestPathParams& params,
    vid_t src, vid_t dst, std::vector<std::vector<vid_t>>& paths) {
  GraphReadInterface::vertex_array_t<int8_t> dist_from_src(
      graph.GetVertexSet(params.labels[0].src_label), -1);
  GraphReadInterface::vertex_array_t<int8_t> dist_from_dst(
      graph.GetVertexSet(params.labels[0].dst_label), -1);
  dist_from_src[src] = 0;
  dist_from_dst[dst] = 0;
  std::queue<vid_t> q1, q2, tmp;
  q1.push(src);
  q2.push(dst);
  std::vector<vid_t> vec;
  int8_t src_dep = 0, dst_dep = 0;

  while (true) {
    if (src_dep >= params.hop_upper || dst_dep >= params.hop_upper ||
        !vec.empty()) {
      break;
    }
    if (q1.size() <= q2.size()) {
      if (q1.empty()) {
        break;
      }
      while (!q1.empty()) {
        vid_t v = q1.front();
        q1.pop();
        auto oe_iter = graph.GetOutEdgeIterator(params.labels[0].src_label, v,
                                                params.labels[0].dst_label,
                                                params.labels[0].edge_label);
        while (oe_iter.IsValid()) {
          vid_t nbr = oe_iter.GetNeighbor();
          if (dist_from_src[nbr] == -1) {
            dist_from_src[nbr] = src_dep + 1;
            tmp.push(nbr);
            if (dist_from_dst[nbr] != -1) {
              vec.push_back(nbr);
            }
          }
          oe_iter.Next();
        }
        auto ie_iter = graph.GetInEdgeIterator(params.labels[0].dst_label, v,
                                               params.labels[0].src_label,
                                               params.labels[0].edge_label);
        while (ie_iter.IsValid()) {
          vid_t nbr = ie_iter.GetNeighbor();
          if (dist_from_src[nbr] == -1) {
            dist_from_src[nbr] = src_dep + 1;
            tmp.push(nbr);
            if (dist_from_dst[nbr] != -1) {
              vec.push_back(nbr);
            }
          }
          ie_iter.Next();
        }
      }
      std::swap(q1, tmp);
      ++src_dep;
    } else {
      if (q2.empty()) {
        break;
      }
      while (!q2.empty()) {
        vid_t v = q2.front();
        q2.pop();
        auto oe_iter = graph.GetOutEdgeIterator(params.labels[0].dst_label, v,
                                                params.labels[0].src_label,
                                                params.labels[0].edge_label);
        while (oe_iter.IsValid()) {
          vid_t nbr = oe_iter.GetNeighbor();
          if (dist_from_dst[nbr] == -1) {
            dist_from_dst[nbr] = dst_dep + 1;
            tmp.push(nbr);
            if (dist_from_src[nbr] != -1) {
              vec.push_back(nbr);
            }
          }
          oe_iter.Next();
        }
        auto ie_iter = graph.GetInEdgeIterator(params.labels[0].src_label, v,
                                               params.labels[0].dst_label,
                                               params.labels[0].edge_label);
        while (ie_iter.IsValid()) {
          vid_t nbr = ie_iter.GetNeighbor();
          if (dist_from_dst[nbr] == -1) {
            dist_from_dst[nbr] = dst_dep + 1;
            tmp.push(nbr);
            if (dist_from_src[nbr] != -1) {
              vec.push_back(nbr);
            }
          }
          ie_iter.Next();
        }
      }
      std::swap(q2, tmp);
      ++dst_dep;
    }
  }

  while (!q1.empty()) {
    q1.pop();
  }
  if (vec.empty()) {
    return;
  }
  if (src_dep + dst_dep >= params.hop_upper) {
    return;
  }
  GraphReadInterface::vertex_array_t<bool> visited(
      graph.GetVertexSet(params.labels[0].src_label), false);
  for (auto v : vec) {
    q1.push(v);
    visited[v] = true;
  }
  while (!q1.empty()) {
    auto v = q1.front();
    q1.pop();
    auto oe_iter = graph.GetOutEdgeIterator(params.labels[0].src_label, v,
                                            params.labels[0].dst_label,
                                            params.labels[0].edge_label);
    while (oe_iter.IsValid()) {
      vid_t nbr = oe_iter.GetNeighbor();
      if (visited[nbr]) {
        oe_iter.Next();
        continue;
      }
      if (dist_from_src[nbr] != -1 &&
          dist_from_src[nbr] + 1 == dist_from_src[v]) {
        q1.push(nbr);
        visited[nbr] = true;
      }
      if (dist_from_dst[nbr] != -1 &&
          dist_from_dst[nbr] + 1 == dist_from_dst[v]) {
        q1.push(nbr);
        visited[nbr] = true;
        dist_from_src[nbr] = dist_from_src[v] + 1;
      }
      oe_iter.Next();
    }

    auto ie_iter = graph.GetInEdgeIterator(params.labels[0].dst_label, v,
                                           params.labels[0].src_label,
                                           params.labels[0].edge_label);
    while (ie_iter.IsValid()) {
      vid_t nbr = ie_iter.GetNeighbor();
      if (visited[nbr]) {
        ie_iter.Next();
        continue;
      }
      if (dist_from_src[nbr] != -1 &&
          dist_from_src[nbr] + 1 == dist_from_src[v]) {
        q1.push(nbr);
        visited[nbr] = true;
      }
      if (dist_from_dst[nbr] != -1 &&
          dist_from_dst[nbr] + 1 == dist_from_dst[v]) {
        q1.push(nbr);
        visited[nbr] = true;
        dist_from_src[nbr] = dist_from_src[v] + 1;
      }
      ie_iter.Next();
    }
  }
  std::vector<vid_t> cur_path;
  dfs(graph, src, dst, visited, dist_from_src, params, paths, cur_path);
}