static bool single_source_single_dest_shortest_path_impl()

in flex/engines/graph_db/runtime/common/operators/retrieve/path_expand.cc [406:539]

• 132 lines of code
• 33 McCabe index (conditional complexity)

static bool single_source_single_dest_shortest_path_impl(
    const GraphReadInterface& graph, const ShortestPathParams& params,
    vid_t src, vid_t dst, std::vector<vid_t>& path) {
  std::queue<vid_t> q1;
  std::queue<vid_t> q2;
  std::queue<vid_t> tmp;

  label_t v_label = params.labels[0].src_label;
  label_t e_label = params.labels[0].edge_label;
  auto vertices = graph.GetVertexSet(v_label);
  GraphReadInterface::vertex_array_t<int> pre(vertices, -1);
  GraphReadInterface::vertex_array_t<int> dis(vertices, 0);
  q1.push(src);
  dis[src] = 1;
  q2.push(dst);
  dis[dst] = -1;

  while (true) {
    if (q1.size() <= q2.size()) {
      if (q1.empty()) {
        break;
      }
      while (!q1.empty()) {
        int x = q1.front();
        if (dis[x] >= params.hop_upper + 1) {
          return false;
        }
        q1.pop();
        auto oe_iter = graph.GetOutEdgeIterator(v_label, x, v_label, e_label);
        while (oe_iter.IsValid()) {
          int y = oe_iter.GetNeighbor();
          if (dis[y] == 0) {
            dis[y] = dis[x] + 1;
            tmp.push(y);
            pre[y] = x;
          } else if (dis[y] < 0) {
            while (x != -1) {
              path.emplace_back(x);
              x = pre[x];
            }
            std::reverse(path.begin(), path.end());
            while (y != -1) {
              path.emplace_back(y);
              y = pre[y];
            }
            int len = path.size() - 1;
            return len >= params.hop_lower && len < params.hop_upper;
          }
          oe_iter.Next();
        }
        auto ie_iter = graph.GetInEdgeIterator(v_label, x, v_label, e_label);
        while (ie_iter.IsValid()) {
          int y = ie_iter.GetNeighbor();
          if (dis[y] == 0) {
            dis[y] = dis[x] + 1;
            tmp.push(y);
            pre[y] = x;
          } else if (dis[y] < 0) {
            while (x != -1) {
              path.emplace_back(x);
              x = pre[x];
            }
            std::reverse(path.begin(), path.end());
            while (y != -1) {
              path.emplace_back(y);
              y = pre[y];
            }
            int len = path.size() - 1;
            return len >= params.hop_lower && len < params.hop_upper;
          }
          ie_iter.Next();
        }
      }
      std::swap(q1, tmp);
    } else {
      if (q2.empty()) {
        break;
      }
      while (!q2.empty()) {
        int x = q2.front();
        if (dis[x] <= -params.hop_upper - 1) {
          return false;
        }
        q2.pop();
        auto oe_iter = graph.GetOutEdgeIterator(v_label, x, v_label, e_label);
        while (oe_iter.IsValid()) {
          int y = oe_iter.GetNeighbor();
          if (dis[y] == 0) {
            dis[y] = dis[x] - 1;
            tmp.push(y);
            pre[y] = x;
          } else if (dis[y] > 0) {
            while (y != -1) {
              path.emplace_back(y);
              y = pre[y];
            }
            std::reverse(path.begin(), path.end());
            while (x != -1) {
              path.emplace_back(x);
              x = pre[x];
            }
            int len = path.size() - 1;
            return len >= params.hop_lower && len < params.hop_upper;
          }
          oe_iter.Next();
        }
        auto ie_iter = graph.GetInEdgeIterator(v_label, x, v_label, e_label);
        while (ie_iter.IsValid()) {
          int y = ie_iter.GetNeighbor();
          if (dis[y] == 0) {
            dis[y] = dis[x] - 1;
            tmp.push(y);
            pre[y] = x;
          } else if (dis[y] > 0) {
            while (y != -1) {
              path.emplace_back(y);
              y = pre[y];
            }
            std::reverse(path.begin(), path.end());
            while (x != -1) {
              path.emplace_back(x);
              x = pre[x];
            }
            int len = path.size() - 1;
            return len >= params.hop_lower && len < params.hop_upper;
          }
          ie_iter.Next();
        }
      }
      std::swap(q2, tmp);
    }
  }
  return false;
}