PGX 21.1.1 has customizable versions of the BFS and DFS traversal algorithms, allowing the use these on tailored use cases.
This filtered version of the BFS algorithm allows to use a filter and a navigator expression to be evaluated over the vertices during the traversal and discriminate them according to the desired criteria. It will return the distance to the source vertex and the corresponding parent vertex for all the filtered vertices.
Input Argument | Type | Comment |
---|---|---|
G | graph | |
root | node | the source vertex from the graph for the path. |
init_with_inf | bool | boolean flag to set the initial distance values of the vertices. If set to true, it will initialize the distances as INF, and -1 otherwise. |
filter | vertexFilter | (deprecated) filter expression to be evaluated on the vertices during the graph traversal. The filter expression has no effect; use the navigator instead to filter out vertices. |
navigator | vertexFilter | navigator expression to be evaluated on the vertices during the graph traversal. |
max_depth | int | maximum depth limit for the BFS traversal. |
Output Argument | Type | Comment |
---|---|---|
dist | vertexProp |
vertex property holding the hop distance for each reachable vertex in the graph. |
parent | vertexProp |
vertex property holding the parent vertex of the each reachable vertex in the path. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ package oracle.pgx.algorithms; import oracle.pgx.algorithm.PgxGraph; import oracle.pgx.algorithm.PgxVertex; import oracle.pgx.algorithm.VertexProperty; import oracle.pgx.algorithm.annotations.GraphAlgorithm; import oracle.pgx.algorithm.annotations.Out; import oracle.pgx.algorithm.filter.VertexFilter; import static oracle.pgx.algorithm.Traversal.currentLevel; import static oracle.pgx.algorithm.Traversal.inBFS; import static java.lang.Integer.MAX_VALUE; @GraphAlgorithm public class FilteredBfs { public void filteredBfs(PgxGraph g, PgxVertex root, boolean initWithInf, VertexFilter filter, VertexFilter navigator, int maxDepth, @Out VertexProperty<Integer> dist, @Out VertexProperty<PgxVertex> parent) { if (g.getNumVertices() == 0) { return; } dist.setAll(initWithInf ? MAX_VALUE : -1); parent.setAll(PgxVertex.NONE); dist.set(root, 0); inBFS(g, root).navigator(n -> navigator.evaluate(n) && currentLevel() < maxDepth) .filter(n -> navigator.evaluate(n) || filter.evaluate(n)).forward(n -> { dist.set(n, currentLevel()); parent.set(n, n.parentVertex()); }); } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ procedure filtered_bfs(graph G, node root, bool init_with_inf, nodeFilter filter, nodeFilter navigator, int max_depth; vertexProp<int> dist, vertexProp<node> parent) { if (G.numNodes() == 0) { return; } G.dist = init_with_inf ? +INF : -1; G.parent = NIL; root.dist = 0; inBFS (n: G.nodes from root) (navigator.evaluate(n) || filter.evaluate(n)) [navigator.evaluate(n) && currentBFSLevel() < max_depth] { n.dist = currentBFSLevel(); n.parent = n.BFSParentNode(); } }
This filtered version of the DFS algorithm allows to use a filter and a navigator expression to be evaluated over the vertices during the traversal and discriminate them according to the desired criteria. It will return the distance to the source vertex and the corresponding parent vertex for all the filtered vertices.
Input Argument | Type | Comment |
---|---|---|
G | graph | |
root | node | the source vertex from the graph for the path. |
init_with_inf | bool | boolean flag to set the initial distance values of the vertices. If set to true, it will initialize the distances as INF, and -1 otherwise. |
filter | vertexFilter | (deprecated) filter expression to be evaluated on the vertices during the graph traversal. The filter expression has no effect; use the navigator instead to filter out vertices. |
navigator | vertexFilter | navigator expression to be evaluated on the vertices during the graph traversal. |
max_depth | int | maximum depth limit for the BFS traversal. |
Output Argument | Type | Comment |
---|---|---|
dist | vertexProp |
vertex property holding the hop distance for each reachable vertex in the graph. |
parent | vertexProp |
vertex property holding the parent vertex of the each reachable vertex in the path. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ package oracle.pgx.algorithms; import oracle.pgx.algorithm.PgxGraph; import oracle.pgx.algorithm.PgxVertex; import oracle.pgx.algorithm.Scalar; import oracle.pgx.algorithm.VertexProperty; import oracle.pgx.algorithm.annotations.GraphAlgorithm; import oracle.pgx.algorithm.annotations.Out; import oracle.pgx.algorithm.filter.VertexFilter; import static oracle.pgx.algorithm.Traversal.inDFS; import static java.lang.Integer.MAX_VALUE; @GraphAlgorithm public class FilteredDfs { public void filteredDfs(PgxGraph g, PgxVertex root, boolean initWithInf, VertexFilter filter, VertexFilter navigator, int maxDepth, @Out VertexProperty<Integer> dist, @Out VertexProperty<PgxVertex> parent) { if (g.getNumVertices() == 0) { return; } VertexProperty<Boolean> visited = VertexProperty.create(false); dist.setAll(initWithInf ? MAX_VALUE : -1); parent.setAll(PgxVertex.NONE); dist.set(root, 0); Scalar<Integer> depth = Scalar.create(0); inDFS(g, root).navigator(n -> navigator.evaluate(n) && depth.get() <= maxDepth) .filter(n -> navigator.evaluate(n) || filter.evaluate(n)).forward(n -> { if (n != root) { n.getInNeighbors().forSequential(m -> { if (visited.get(m) && dist.get(m) < maxDepth && dist.get(m) >= depth.get() - 1) { parent.set(n, m); } }); } if (parent.get(n) != PgxVertex.NONE) { PgxVertex p = parent.get(n); dist.set(n, dist.get(p) + 1); } depth.increment(); visited.set(n, true); }).backward(n -> depth.decrement()); } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ procedure filtered_dfs(graph G, node root, bool init_with_inf, nodeFilter filter, nodeFilter navigator, int max_depth; vertexProp<int> dist, vertexProp<node> parent) { if (G.numNodes() == 0) { return; } vertexProp<bool> visited; G.dist = init_with_inf ? +INF : -1; G.parent = NIL; G.visited = false; root.dist = 0; int depth = 0; inDFS (n: G.nodes from root) (navigator.evaluate(n) || filter.evaluate(n)) [navigator.evaluate(n) && depth <= max_depth] { if (n != root) { for (m: n.inNbrs) (m.visited && m.dist < max_depth && m.dist >= depth - 1) { n.parent = m; } } if (n.parent != NIL) { node p = n.parent; n.dist = p.dist + 1; } depth++; n.visited = true; } inPost { depth--; } }