PGX 20.1.1
Documentation

Filtered Fast Path Finding

Category path finding

Algorithm ID pgx_builtin_o9_limited_path_finding_undirected_filtered

Time Complexity O(E) with E = number of edges

Space Requirement O(V) with V = number of vertices

Javadoc


description: Computes the shortest path between the source and destination vertex. The algorithm only considers paths up to a length of k.

Signature

Input Argument Type Comment
G graph
src node the source vertex.
dst node the destination vertex.
k int the dimension of the distances property; i.e. number of high-degree vertices.
maxHops int the maximum number of edges to follow when trying to find a path.
superNodes nodeSet the high-degree vertices.
superNodeMapping map the high-degree vertices.
distances vertexProp[k]> index containing distances to high-degree vertices.
filter edgeFilter filter to be evaluated on the edges when searching for a path.
Output Argument Type Comment
path nodeSeq will contain the vertices on the found path or will be empty if there is none.
pathEdges edgeSeq will contain the vertices on the found path or will be empty if there is none.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVect;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Length;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.filter.EdgeFilter;

import static oracle.pgx.algorithm.ControlFlow.exit;
import static oracle.pgx.algorithm.PgxVertex.NONE;

@GraphAlgorithm
public class HopDistPathFindingUndirectedFiltered {
  public int fastPathFinding(PgxGraph g, PgxVertex src, PgxVertex dst, int k, int maxHopsArg, VertexSet superNodes,
      PgxMap<Integer, PgxVertex> superNodeMapping, VertexProperty<@Length("k") PgxVect<Integer>> distances,
      EdgeFilter filter, @Out VertexSequence path) {
    int maxHops = maxHopsArg;

    // 1. trivial cases
    if (src == dst) {
      path.push(src);
      return 0;
    } else if (maxHops == 0) {
      return -1;
    }
    src.getNeighbors().forSequential(n -> {
      PgxEdge e = n.edge();
      if (n == dst && filter.evaluate(e)) {
        path.push(src);
        path.push(dst);
        exit(1);
      }
    });
    if (maxHops == 1) {
      return -1;
    }

    // 2. check whether src and dst are connected via super-nodes
    int superNodeIndex = -1;
    {
      @Length("k")
      PgxVect<Integer> srcVec = distances.get(src);
      @Length("k")
      PgxVect<Integer> dstVec = distances.get(dst);
      int current = 0;
      int minHops = maxHops + 1;

      while (current < k) {
        int hops = srcVec.get(current) + dstVec.get(current);
        if (hops < minHops) {
          minHops = hops;
          superNodeIndex = current;
        }
        current++;
      }

      if (superNodeIndex != -1) {
        maxHops = minHops; // can reduce the maxHops since no shortest path can be longer than this one
      }
    }

    // 3. find path from src to dst ignoring super-nodes
    int hops = bidirectionalHopDist(g, src, dst, maxHops, superNodes, filter, path);
    if (hops != -1) {
      // found a path without super-nodes
      return hops;
    }

    if (superNodeIndex == -1) {
      // no path with and without super-nodes; i.e. there is no path at all
      return -1;
    }

    // 4. compute path using superNode computed in 1.
    hops = computePathIncludingSuperNode(g, src, dst, superNodeIndex, k, superNodeMapping, distances, filter, path);
    if (hops != -1) {
      // found path using super-nodes
      return hops;
    }

    // 5. there is no path using super-nodes that satisfy the filter - fall back to normal hop-dist
    hops = hopDist(g, src, dst, maxHopsArg, filter, path);
    if (hops != -1) {
      // found a path
      path.pushFront(dst);
      return hops + 1;
    }

    return -1;
  }

  int computePathIncludingSuperNode(PgxGraph g, PgxVertex src, PgxVertex dst, int superNodeIndex, int k,
      PgxMap<Integer, PgxVertex> superNodeMapping, VertexProperty<@Length("k") PgxVect<Integer>> distances,
      EdgeFilter filter, @Out VertexSequence path) {
    PgxVertex superNode = superNodeMapping.get(superNodeIndex);
    int forwardHops = getDistanceToSuperNode(g, src, superNodeIndex, k, distances);
    int reverseHops = getDistanceToSuperNode(g, dst, superNodeIndex, k, distances);

    VertexSequence forwardPath = VertexSequence.create();
    hopDist(g, src, superNode, forwardHops, filter, forwardPath);
    hopDist(g, dst, superNode, reverseHops, filter, path);

    if (path.size() == 0 || forwardPath.size() == 0) {
      // either src or dst does not have a valid path to the super-node
      path.clear();
      return -1;
    }

    path.pushFront(superNode);
    forwardPath.forSequential(path::pushFront);
    return path.size() - 1;
  }

  int getDistanceToSuperNode(PgxGraph g, PgxVertex n, int superNodeIndex, int k,
      VertexProperty<@Length("k") PgxVect<Integer>> distances) {
    @Length("k")
    PgxVect<Integer> entry = distances.get(n);
    int result = entry.get(superNodeIndex);
    return result;
  }

  int buildPathBidirectional(PgxGraph g, PgxVertex src, PgxVertex dst, PgxVertex middle,
      PgxMap<PgxVertex, PgxVertex> parentForward, PgxMap<PgxVertex, PgxVertex> parentReverse,
      @Out VertexSequence path) {
    VertexSequence forwardPath = VertexSequence.create();
    buildPath(g, middle, src, parentForward, forwardPath);
    buildPath(g, middle, dst, parentReverse, path);

    path.pushFront(middle);
    forwardPath.forSequential(path::pushFront);
    return path.size() - 1;
  }

  int buildPath(PgxGraph g, PgxVertex start, PgxVertex end, PgxMap<PgxVertex, PgxVertex> parents,
      @Out VertexSequence path) {
    PgxVertex current = start;
    while (current != end) {
      current = parents.get(current);
      path.pushBack(current);
    }
    return path.size() - 1;
  }

  int bidirectionalHopDist(PgxGraph g, PgxVertex src, PgxVertex dst, int maxHops, VertexSet superNodes,
      EdgeFilter filter, @Out VertexSequence path) {
    VertexSequence frontierForward = VertexSequence.create();
    VertexSequence frontierReverse = VertexSequence.create();
    frontierForward.pushBack(src);
    frontierReverse.pushBack(dst);

    PgxMap<PgxVertex, PgxVertex> parentForward = PgxMap.create();
    PgxMap<PgxVertex, PgxVertex> parentReverse = PgxMap.create();
    parentForward.set(src, src);
    parentReverse.set(dst, dst);

    int current = 0;

    while (current < maxHops && frontierForward.size() > 0 && frontierReverse.size() > 0) {
      int c = frontierForward.size();
      while (c > 0) {
        c--;

        PgxVertex n = frontierForward.popFront();

        n.getNeighbors().filter(v -> parentForward.get(v) == NONE && !superNodes.contains(v)).forSequential(v -> {
          PgxEdge e = v.edge();
          if (filter.evaluate(e)) {
            parentForward.set(v, n);
            if (parentReverse.get(v) != NONE) {
              exit(buildPathBidirectional(g, src, dst, v, parentForward, parentReverse, path));
            } else {
              frontierForward.pushBack(v);
            }
          }
        });
      }

      current++;
      if (current == maxHops) {
        return -1;
      }
      c = frontierReverse.size();
      while (c > 0) {
        c--;

        PgxVertex n = frontierReverse.popFront();

        n.getNeighbors().filter(v -> parentReverse.get(v) == NONE && !superNodes.contains(v)).forSequential(v -> {
          PgxEdge e = v.edge();
          if (filter.evaluate(e)) {
            parentReverse.set(v, n);
            if (parentForward.get(v) != NONE) {
              exit(buildPathBidirectional(g, src, dst, v, parentForward, parentReverse, path));
            } else {
              frontierReverse.pushBack(v);
            }
          }
        });
      }
      current++;
    }
    return -1;
  }

  int hopDist(PgxGraph g, PgxVertex src, PgxVertex dst, int maxHops, EdgeFilter filter, @Out VertexSequence path) {

    VertexSequence frontierForward = VertexSequence.create();
    frontierForward.pushBack(src);

    PgxMap<PgxVertex, PgxVertex> parentForward = PgxMap.create();
    parentForward.set(src, src);

    int current = 0;

    while (current < maxHops && frontierForward.size() > 0) {
      current++;

      int c = frontierForward.size();
      while (c > 0) {
        c--;

        PgxVertex n = frontierForward.popFront();

        n.getNeighbors().filter(v -> parentForward.get(v) == NONE).forSequential(v -> {
          PgxEdge e = v.edge();
          if (filter.evaluate(e)) {
            parentForward.set(v, n);
            if (v == dst) {
              exit(buildPath(g, v, src, parentForward, path));
            } else {
              frontierForward.pushBack(v);
            }
          }
        });
      }
    }
    return -1;
  }
}

/*
// use graph instead of dGraph until GM-16698 is fixed
proc fastPathFinding(graph g, node src, node dst, int k, int maxHopsArg, nodeSet superNodes, map<int, node>
superNodeMapping,
    nodeProp<vect<int>[k]> distances, edgeFilter filter; nodeSeq path) : int {

  int maxHops = maxHopsArg;

  // 1. trivial cases
  if (src == dst) {
    path.push(src);
    return 0;
  } else if (maxHops == 0) {
    return -1;
  }
  for (n: src.inOutNbrs) {
    edge e = n.edge();
    if (n == dst && filter.evaluate(e)) {
      path.push(src);
      path.push(dst);
      return 1;
    }
  }
  if (maxHops == 1) {
    return -1;
  }

  // 2. check whether src and dst are connected via super-nodes
  int superNodeIndex = -1;
  {
    iVect[k] srcVec = src.distances;
    iVect[k] dstVec = dst.distances;
    int current = 0;
    int minHops = maxHops + 1;

    while (current < k) {
      int hops = srcVec[current] + dstVec[current];
      if (hops < minHops) {
        minHops = hops;
        superNodeIndex = current;
      }
      current++;
    }

    if (superNodeIndex != -1) {
      maxHops = minHops; // can reduce the maxHops since no shortest path can be longer than this one
    }
  }

  // 3. find path from src to dst ignoring super-nodes
  int hops = bidirectionalHopDist(g, src, dst, maxHops, superNodes, filter, path);
  if (hops != -1) {
    // found a path without super-nodes
    return hops;
  }

  if (superNodeIndex == -1) {
    // no path with and without super-nodes; i.e. there is no path at all
    return -1;
  }

  // 4. compute path using superNode computed in 1.
  hops = computePathIncludingSuperNode(g, src, dst, superNodeIndex, k, superNodeMapping, distances, filter, path);
  if (hops != -1) {
     // found path using super-nodes
    return hops;
  }

  // 5. there is no path using super-nodes that satisfy the filter - fall back to normal hop-dist
  hops = hopDist(g, src, dst, maxHopsArg, filter, path);
  if (hops != -1) {
    // found a path
    path.pushFront(dst);
    return hops + 1;
  } else {
    return -1;
  }
}

local computePathIncludingSuperNode(graph g, node src, node dst, int superNodeIndex, int k, map<int, node>
superNodeMapping, nodeProp<vect<int>[k]> distances, edgeFilter filter; nodeSeq path) : int {
  node superNode = superNodeMapping[superNodeIndex];
  int forwardHops = getDistanceToSuperNode(g, src, superNodeIndex, k, distances);
  int reverseHops = getDistanceToSuperNode(g, dst, superNodeIndex, k, distances);

  nodeSeq forwardPath;
  hopDist(g, src, superNode, forwardHops, filter, forwardPath);
  hopDist(g, dst, superNode, reverseHops, filter, path);

  if (path.size() == 0 || forwardPath.size() == 0) {
    // either src or dst does not have a valid path to the super-node
    path.clear();
    return -1;
  }

  path.pushFront(superNode);
  for (n: forwardPath.items) {
    path.pushFront(n);
  }
  return path.size() - 1;
}

local getDistanceToSuperNode(graph g, node n, int superNodeIndex, int k, nodeProp<vect<int>[k]> distances) : int {
  iVect[k] entry = n.distances;
  int result = entry[superNodeIndex];
  return result;
}

local buildPathBidirectional(graph g, node src, node dst, node middle, map<node, node> parentForward, map<node, node>
 parentReverse; nodeSeq path) : int {
  nodeSeq forwardPath;
  buildPath(g, middle, src, parentForward, forwardPath);
  buildPath(g, middle, dst, parentReverse, path);

  path.pushFront(middle);
  for (n: forwardPath.items) {
    path.pushFront(n);
  }
  return path.size() - 1;
}

local buildPath(graph g, node start, node end, map<node, node> parents; nodeSeq path) : int {
  node current = start;
  while (current != end) {
    current = parents[current];
    path.pushBack(current);
  }
  return path.size() - 1;
}

local bidirectionalHopDist(graph g, node src, node dst, int maxHops, nodeSet superNodes, edgeFilter filter; nodeSeq
path) : int {
  nodeSeq frontier_forward;
  nodeSeq frontier_reverse;
  frontier_forward.pushBack(src);
  frontier_reverse.pushBack(dst);

  map<node, node> parentForward;
  map<node, node> parentReverse;
  parentForward[src] = src;
  parentReverse[dst] = dst;

  int current = 0;

  while (current < maxHops && frontier_forward.size() > 0 && frontier_reverse.size() > 0) {
    int c = frontier_forward.size();
    while (c > 0) {
      c--;

      node n = frontier_forward.popFront();

      for(v: n.inOutNbrs) (parentForward[v] == NIL && superNodes.has(v) == false) {
        edge e = v.edge();
        if (filter.evaluate(e)) {
          parentForward[v] = n;
          if (parentReverse[v] != NIL) {
            return buildPathBidirectional(g, src, dst, v, parentForward, parentReverse, path);
          } else {
            frontier_forward.pushBack(v);
          }
        }
      }
    }

    current++;
    if (current == maxHops) {
      return -1;
    }
    c = frontier_reverse.size();
    while (c > 0) {
      c--;

      node n = frontier_reverse.popFront();

      for(v: n.inOutNbrs) (parentReverse[v] == NIL && superNodes.has(v) == false) {
        edge e = v.edge();
        if (filter.evaluate(e)) {
          parentReverse[v] = n;
          if (parentForward[v] != NIL) {
            return buildPathBidirectional(g, src, dst, v, parentForward, parentReverse, path);
          } else {
            frontier_reverse.pushBack(v);
          }
        }
      }
    }
    current++;
  }
  return -1;
}

local hopDist(graph g, node src, node dst, int maxHops, edgeFilter filter; nodeSeq path) : int {

  nodeSeq frontier_forward;
  frontier_forward.pushBack(src);

  map<node, node> parentForward;
  parentForward[src] = src;

  int current = 0;

  while (current < maxHops && frontier_forward.size() > 0) {
    current++;

    int c = frontier_forward.size();
    while (c > 0) {
      c--;

      node n = frontier_forward.popFront();

      for(v: n.inOutNbrs) (parentForward[v] == NIL) {
        edge e = v.edge();
        if (filter.evaluate(e)) {
          parentForward[v] = n;
          if (v == dst) {
            return buildPath(g, v, src, parentForward, path);
          } else {
            frontier_forward.pushBack(v);
          }
        }
      }
    }
  }
  return -1;
}
*/
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
proc fastPathFinding(graph g, node src, node dst, int k, int maxHopsArg, nodeSet superNodes, map<int, node> superNodeMapping,
    vertexProp<vect<int>[k]> distances, edgeFilter filter; nodeSeq path, edgeSeq pathEdges) : int {

  int maxHops = maxHopsArg;

  // 1. trivial cases
  if (src == dst) {
    path.push(src);
    return 0;
  } else if (maxHops == 0) {
    return -1;
  }

  for (n: src.inOutNbrs) {
    edge e = n.edge();
    if (n == dst && filter.evaluate(e)) {
      path.push(src);
      path.push(dst);
      pathEdges.push(e);
      return 1;
    }
  }
  if (maxHops == 1) {
    return -1;
  }

  // 2. check whether src and dst are connected via super-nodes
  int superNodeIndex = -1;
  {
    iVect[k] srcVec = src.distances;
    iVect[k] dstVec = dst.distances;
    int current = 0;
    int minHops = maxHops + 1;

    while (current < k) {
      int srcHops = srcVec[current];
      int dstHops = dstVec[current];
      if (srcHops < INF && dstHops < INF) {
        int hops = srcHops + dstHops;
        if (hops < minHops) {
          minHops = hops;
          superNodeIndex = current;
        }
      }
      current++;
    }

    if (superNodeIndex != -1) {
      maxHops = minHops; // can reduce the maxHops since no shortest path can be longer than this one
    }
  }

  // 3. find path from src to dst ignoring super-nodes
  int hops = bidirectionalHopDist(g, src, dst, maxHops, superNodes, filter, path, pathEdges);
  if (hops != -1) {
    // found a path without super-nodes
    return hops;
  }

  if (superNodeIndex == -1) {
    // no path with and without super-nodes; i.e. there is no path at all
    return -1;
  }

  // 4. compute path using superNode computed in 1.
  hops = computePathIncludingSuperNode(g, src, dst, superNodeIndex, k, superNodeMapping, distances, filter, path, pathEdges);
  if (hops != -1) {
     // found path using super-nodes
    return hops;
  }

  // 5. there is no path using super-nodes that satisfy the filter - fall back to normal hop-dist
  hops = hopDist(g, src, dst, maxHopsArg, filter, path, pathEdges);
  if (hops != -1) {
    // found a path
    path.pushFront(dst);
    return hops + 1;
  }

  return -1;
}

local computePathIncludingSuperNode(graph g, node src, node dst, int superNodeIndex, int k, map<int, node> superNodeMapping, vertexProp<vect<int>[k]> distances, edgeFilter filter; nodeSeq path, edgeSeq pathEdges) : int {
  node superNode = superNodeMapping[superNodeIndex];
  int forwardHops = getDistanceToSuperNode(g, src, superNodeIndex, k, distances);
  int reverseHops = getDistanceToSuperNode(g, dst, superNodeIndex, k, distances);

  nodeSeq forwardPath;
  edgeSeq forwardPathEdges;
  hopDist(g, src, superNode, forwardHops, filter, forwardPath, forwardPathEdges);
  hopDist(g, dst, superNode, reverseHops, filter, path, pathEdges);

  if (path.size() == 0 || forwardPath.size() == 0) {
    // either src or dst does not have a valid path to the super-node
    path.clear();
    pathEdges.clear();
    return -1;
  }

  path.pushFront(superNode);
  for (n: forwardPath.items) {
    path.pushFront(n);
  }
  for (e: forwardPathEdges.items) {
    pathEdges.pushFront(e);
  }
  return pathEdges.size();
}

local getDistanceToSuperNode(graph g, node n, int superNodeIndex, int k, vertexProp<vect<int>[k]> distances) : int {
  iVect[k] entry = n.distances;
  int result = entry[superNodeIndex];
  return result;
}

local buildPathBidirectional(graph g, node src, node dst, node middle, map<node, node> parentForward, map<node, edge> parentEdgesForward,
    map<node, node> parentReverse, map<node, edge> parentEdgesReverse; nodeSeq path, edgeSeq pathEdges) : int {

  nodeSeq forwardPath;
  edgeSeq forwardPathEdges;
  buildPath(g, middle, src, parentForward, parentEdgesForward, forwardPath, forwardPathEdges);
  buildPath(g, middle, dst, parentReverse, parentEdgesReverse, path, pathEdges);

  path.pushFront(middle);
  for (n: forwardPath.items) {
    path.pushFront(n);
  }
  for (e: forwardPathEdges.items) {
    pathEdges.pushFront(e);
  }
  return pathEdges.size();
}

// TODO fix call sites of buildPath
local buildPath(graph g, node start, node end, map<node, node> parents, map<node, edge> parentEdges; nodeSeq path, edgeSeq pathEdges) : int {
  node current = start;
  while (current != end) {
    if (parentEdges.hasKey(current)) {
      edge currentEdge = parentEdges[current];
      pathEdges.pushBack(currentEdge);
    }
    current = parents[current];
    path.pushBack(current);
  }
  return pathEdges.size();
}

local bidirectionalHopDist(graph g, node src, node dst, int maxHops, nodeSet superNodes, edgeFilter filter; nodeSeq path, edgeSeq pathEdges) : int {
  nodeSeq frontier_forward;
  nodeSeq frontier_reverse;
  frontier_forward.pushBack(src);
  frontier_reverse.pushBack(dst);

  map<node, node> parentForward;
  map<node, node> parentReverse;
  map<node, edge> parentEdgesForward;
  map<node, edge> parentEdgesReverse;
  parentForward[src] = src;
  parentReverse[dst] = dst;

  int current = 0;

  while (current < maxHops && frontier_forward.size() > 0 && frontier_reverse.size() > 0) {
    int c = frontier_forward.size();
    while (c > 0) {
      c--;

      node n = frontier_forward.popFront();

      for(v: n.inOutNbrs) (parentForward[v] == NIL && superNodes.has(v) == false) {
        edge e = v.edge();
        if (filter.evaluate(e)) {
          parentForward[v] = n;
          parentEdgesForward[v] = e;
          if (parentReverse[v] != NIL) {
            return buildPathBidirectional(g, src, dst, v, parentForward, parentEdgesForward, parentReverse, parentEdgesReverse, path, pathEdges);
          } else {
            frontier_forward.pushBack(v);
          }
        }
      }
    }

    current++;
    if (current == maxHops) {
      return -1;
    }
    c = frontier_reverse.size();
    while (c > 0) {
      c--;

      node n = frontier_reverse.popFront();

      for(v: n.inOutNbrs) (parentReverse[v] == NIL && superNodes.has(v) == false) {
        edge e = v.edge();
        if (filter.evaluate(e)) {
          parentReverse[v] = n;
          parentEdgesReverse[v] = e;
          if (parentForward[v] != NIL) {
            return buildPathBidirectional(g, src, dst, v, parentForward, parentEdgesForward, parentReverse, parentEdgesReverse, path, pathEdges);
          } else {
            frontier_reverse.pushBack(v);
          }
        }
      }
    }
    current++;
  }
  return -1;
}

local hopDist(graph g, node src, node dst, int maxHops, edgeFilter filter; nodeSeq path, edgeSeq pathEdges) : int {

  nodeSeq frontier_forward;
  frontier_forward.pushBack(src);

  map<node, node> parentForward;
  map<node, edge> parentEdgesForward;
  parentForward[src] = src;

  int current = 0;

  while (current < maxHops && frontier_forward.size() > 0) {
    current++;

    int c = frontier_forward.size();
    while (c > 0) {
      c--;

      node n = frontier_forward.popFront();

      for(v: n.inOutNbrs) (parentForward[v] == NIL) {
        edge e = v.edge();
        if (filter.evaluate(e)) {
          parentForward[v] = n;
          parentEdgesForward[v] = e;
          if (v == dst) {
            return buildPath(g, v, src, parentForward, parentEdgesForward, path, pathEdges);
          } else {
            frontier_forward.pushBack(v);
          }
        }
      }
    }
  }
  return -1;
}