/*
* 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;
}