/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
procedure undirected_all_on_path(graph G, node src, node dst, int k;
    nodeSet verticesOnPath, edgeSet edgesOnPath, map<node, int> f_dist) : bool {

  // the threshold at which we switch to using parallel iterations
  int parallel_threshold = 1000;

  nodeSet f_frontier; // at any given iteration, the set of left nodes
  f_frontier.add(src);
  nodeSet f_reachables = f_frontier; // the vertices that have been reached from the left

  nodeSet r_frontier; // at any given iteration, the set of right nodes
  r_frontier.add(dst);
  nodeSet r_reachables = r_frontier; // the vertices that have been reached from the right

  // f_dist stores the distance of the vertices reached from the left to src
  f_dist[src] = 0;
  map<node, int> r_dist; // r_dist stores the distance of the vertices reached from the right to dst
  r_dist[dst] = 0;

  // we start by doing k hops in a bidirectional manner so that we can visit all the vertices and edges
  // that are potentially on a path. Thanks to this marking we hopefully can avoid to follow unecessary edges
  // in the loops after that complete the full k-hops from both sides
  long next_f_reachable_size = (src.outDegree() + src.inDegree());
  long next_r_reachable_size = (dst.outDegree() + dst.inDegree());
  int hop = 0;
  int left_hop = 0;
  int right_hop = 0;
  while ((hop < k) && (f_frontier.size() != 0) && (r_frontier.size() != 0) ) {

    if (next_f_reachable_size <= next_r_reachable_size) {
      left_hop++;

      // scanning neighbors of left frontier is cheaper
      next_f_reachable_size = 0;
      nodeSet next_f_frontier;

      //if (f_frontier.size() < parallel_threshold) {
        for (n : f_frontier.items) {
          for (m : n.inOutNbrs) {
            // if m is in the right set, we have a path, we can record it for later
            bool r_reachable = r_reachables.has(m);
            if (r_reachable) {
              // the edge is on a contributing path
              edge e = m.edge();
              edgesOnPath.add(e);

              // the vertex is on a contributing path
              verticesOnPath.add(m);
            }
            bool f_reachable = f_reachables.has(m);
            if (f_reachable == false) {
              next_f_frontier.add(m);
              f_reachables.add(m);
              f_dist[m] = left_hop;
              next_f_reachable_size += (m.outDegree() + m.inDegree());
            }
          }
        }
      //} else {
      //  nodeSet f_reachables_add;
      //  foreach (n : f_frontier.items) {
      //    for (m : n.inOutNbrs) {
            // if m is in the right set, we have a path, we can record it for later
      //      bool r_reachable = r_reachables.has(m);
      //      if (r_reachable) {
              // the edge is on a contributing path
      //        edge e = m.edge();
      //        edgesOnPath.add(e);

              // the vertex is on a contributing path
      //        verticesOnPath.add(m);
      //      }
      //      bool f_reachable = f_reachables.has(m);
      //      if (f_reachable == false) {
      //        next_f_frontier.add(m);
      //        f_reachables_add.add(m);
      //        f_dist[m] = left_hop;
      //        next_f_reachable_size += (m.outDegree() + m.inDegree());
      //      }
      //    }
      //  }
      //  f_reachables.addAll(f_reachables_add);
      //}

      // swap frontiers
      f_frontier = next_f_frontier;
    } else {
      right_hop++;

      // scanning neighbors of right frontier is cheaper
      next_r_reachable_size = 0;
      nodeSet next_r_frontier;

      //if (r_frontier.size() < parallel_threshold) {
        for (n : r_frontier.items) {
          for (m : n.inOutNbrs) {
            // if m is in the left set, we have a path, we can record it for later
            bool f_reachable = f_reachables.has(m);
            if (f_reachable) {
              // the edge is on a contributing path
              edge e = m.edge();
              edgesOnPath.add(e);

              // the vertex is on a contributing path
              verticesOnPath.add(m);
            }
            bool r_reachable = r_reachables.has(m);
            if (r_reachable == false) {
              next_r_frontier.add(m);
              r_reachables.add(m);
              r_dist[m] = right_hop;
              next_r_reachable_size += (m.outDegree() + m.inDegree());
            }
          }
        }
      //} else {
      //  nodeSet r_reachables_add;
      //  foreach (n : r_frontier.items) {
      //    for (m : n.inOutNbrs) {
            // if m is in the left set, we have a path, we can record it for later
      //      bool f_reachable = f_reachables.has(m);
      //      if (f_reachable) {
              // the edge is on a contributing path
      //        edge e = m.edge();
      //        edgesOnPath.add(e);

              // the vertex is on a contributing path
      //        verticesOnPath.add(m);
      //      }
      //      bool r_reachable = r_reachables.has(m);
      //      if (r_reachable == false) {
      //        next_r_frontier.add(m);
      //        r_reachables_add.add(m);
      //        r_dist[m] = right_hop;
      //        next_r_reachable_size += (m.outDegree() + m.inDegree());
      //      }
      //    }
      //  }
      //  r_reachables.addAll(r_reachables_add);
      //}

      // swap frontiers
      r_frontier = next_r_frontier;
    }

    hop++;
  }

  // from that point on , we are extending from the left and the rights up to k hops
  // as we have already done k hops total from left and right, any vertex that contributes
  // to a path of length <= k should already be in the set of vertices discovered in the other direction
  // therefore we can include in the frontiers only the vertices in the other set of reached vertices

  // finish the left hops until we have reached k of them
  while ((left_hop < k) && (f_frontier.size() != 0)) {
    left_hop++;

    nodeSet next_f_frontier;


    //if (f_frontier.size() < parallel_threshold) {
      for (n : f_frontier.items) {
        for (m : n.inOutNbrs) {
          // if m is in the right set, at a distance less than k - left_hops, we have a path, we can record it for later
          bool r_reachable = r_reachables.has(m);
          if (r_reachable && r_dist[m] <= (k - left_hop)) {
            // the edge is on a contributing path
            edge e = m.edge();
            edgesOnPath.add(e);

            // the vertex is on a contributing path
            verticesOnPath.add(m);

            bool f_reachable = f_reachables.has(m);
            if (f_reachable == false) {
              next_f_frontier.add(m);
              f_reachables.add(m);
              f_dist[m] = left_hop;
            }
          }
        }
      }
    //} else {
    //  nodeSet f_reachables_add;
    //  foreach (n : f_frontier.items) {
    //    for (m : n.inOutNbrs) {
          // if m is in the right set, at a distance less than k - left_hops, we have a path, we can record it for later
    //      bool r_reachable = r_reachables.has(m);
    //      if (r_reachable && r_dist[m] <= (k - left_hop)) {
            // the edge is on a contributing path
    //        edge e = m.edge();
    //        edgesOnPath.add(e);

            // the vertex is on a contributing path
    //        verticesOnPath.add(m);

    //        bool f_reachable = f_reachables.has(m);
    //        if (f_reachable == false) {
    //          next_f_frontier.add(m);
    //          f_reachables_add.add(m);
    //          f_dist[m] = left_hop;
    //        }
    //      }
    //    }
    //  }
    //  f_reachables.addAll(f_reachables_add);
    //}

    // swap frontiers
    f_frontier = next_f_frontier;

    hop++;
  }

  // finish the right hops until we have reached k of them
  while ((right_hop < k) && (r_frontier.size() != 0) ) {
    right_hop++;

    nodeSet next_r_frontier;

    //if (r_frontier.size() < parallel_threshold) {
      for (n : r_frontier.items) {
        for (m : n.inOutNbrs) {
          // if m is in the left set, at a distance less than k - left_hops, we have a path, we can record it for later
          bool f_reachable = f_reachables.has(m);
          if (f_reachable && f_dist[m] <= (k - right_hop)) {
            // the edge is on a contributing path
            edge e = m.edge();
            edgesOnPath.add(e);

            // the vertex is on a contributing path
            verticesOnPath.add(m);

            bool r_reachable = r_reachables.has(m);
            if (r_reachable == false) {
              next_r_frontier.add(m);
              r_reachables.add(m);
              r_dist[m] = right_hop;
            }
          }
        }
      }
    //} else {
    //  nodeSet r_reachables_add;
    //  foreach (n : r_frontier.items) {
    //    for (m : n.inOutNbrs) {
          // if m is in the left set, at a distance less than k - left_hops, we have a path, we can record it for later
    //      bool f_reachable = f_reachables.has(m);
    //      if (f_reachable && f_dist[m] <= (k - right_hop)) {
            // the edge is on a contributing path
    //        edge e = m.edge();
    //        edgesOnPath.add(e);

            // the vertex is on a contributing path
    //        verticesOnPath.add(m);

    //        bool r_reachable = r_reachables.has(m);
    //        if (r_reachable == false) {
    //         next_r_frontier.add(m);
    //          r_reachables_add.add(m);
    //          r_dist[m] = right_hop;
    //        }
    //      }
    //    }
    //  }
    //  r_reachables.addAll(r_reachables_add);
    //}

    // swap frontiers
    r_frontier = next_r_frontier;

    hop++;
  }

  // we have discovered all the vertices on a contributing path
  return verticesOnPath.size() > 0;
}