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