/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
procedure enumerate_simple_paths(graph G, node src, node dst, int k,
nodeSet verticesOnPath, edgeSet edgesOnPath, map<node, int> f_dist; sequence<int> pathLengths, nodeSeq pathVertices, edgeSeq pathEdges) {
// we generate all the paths by doing a pseudo-DFS using a stack
// (we don't include paths with loops)
nodeSeq stack;
sequence<int> hopCountStack;
stack.push(src);
hopCountStack.push(0);
map<node, node> parentNodes;
parentNodes[src] = NIL;
map<node, edge> parentEdges;
parentEdges[src] = NIL;
if (k > 0) {
while (stack.size() > 0) {
node cur = stack.pop();
int hop = hopCountStack.pop();
if (cur == dst) {
// write down the path (in reverse order)
int length = 1;
node pathVertex = cur;
pathVertices.push(pathVertex);
edge pathEdge = parentEdges[pathVertex];
pathVertex = parentNodes[pathVertex];
int l = hop;
while (l > 0) {
pathVertices.push(pathVertex);
pathEdges.push(pathEdge);
length++;
// prepare next iteration
pathEdge = parentEdges[pathVertex];
pathVertex = parentNodes[pathVertex];
l--;
}
pathLengths.push(length);
}
if (hop < k) {
// we can do more hops
int newHop = hop + 1;
for (m : cur.inOutNbrs) {
edge e = m.edge();
// to avoid loops we force increasing distance from the source
if (verticesOnPath.has(m) && edgesOnPath.has(e) && f_dist[m] <= k && f_dist[cur] < f_dist[m]) {
parentNodes[m] = cur;
parentEdges[m] = e;
stack.push(m);
hopCountStack.push(newHop);
}
}
}
}
}
}