Cycle Detection Algorithms
PGX 21.1.1 has two algorithms for finding cycles. A robust version, hence more expensive, that will perform several DFS traversals using different vertices as starting points for the search. And a light-weight version that will perform just one single DFS traversal using the given vertex as starting point for the task.
Find Cycle
Category
structure evaluation
Algorithm ID
pgx_builtin_s14a_find_cycle
Time Complexity
O(V * (V + E)) with V = number of vertices, E = number of edges
Space Requirement
O(5 * V + E) with V = number of vertices, E = number of edges
Javadoc
This algorithm tries to find a cycle in a directed graph using DFS traversals and will return the first cycle found, if there is one. In such case, the vertices and edges involved in the cycle will be returned in the order of visit. The algorithm is expensive because it will perform DFS traversals using different vertices as starting points until it explores the whole graph (worst-case scenario), or until it finds a cycle.
Signature
Input Argument |
Type |
Comment |
G |
graph |
|
Output Argument |
Type |
Comment |
cycle_nodes |
nodeSeq |
vertex sequence holding the vertices in the cycle. |
cycle_edges |
edgeSeq |
edge sequence holding the edges in the cycle. |
Return Value |
Type |
Comment |
|
bool |
true if there is a cycle in the graph, false otherwise. |
Code
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
package oracle.pgx.algorithms;
import oracle.pgx.algorithm.EdgeSequence;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import static oracle.pgx.algorithm.Traversal.inDFS;
@GraphAlgorithm
public class FindCycle {
public boolean findCycle(PgxGraph g, @Out VertexSequence cycleNodes, @Out EdgeSequence cycleEdges) {
VertexProperty<Boolean> visited = VertexProperty.create();
VertexProperty<Boolean> inPath = VertexProperty.create();
VertexProperty<PgxVertex> source = VertexProperty.create();
VertexProperty<Long> deg = VertexProperty.create();
visited.setAll(false);
inPath.setAll(false);
deg.setAll(PgxVertex::getOutDegree);
Scalar<Boolean> foundCycle = Scalar.create(false);
Scalar<PgxVertex> pivotNode = Scalar.create();
g.getVertices().filter(s -> !visited.get(s) && !foundCycle.get()).forSequential(s ->
inDFS(g, s)
.navigator(v -> !foundCycle.get())
.filter(v -> deg.get(v) > 0)
.forward(v -> {
//Adding potential vertices in the cycle path
inPath.set(v, true);
v.getNeighbors().forEach(w -> {
source.set(w, v);
if (inPath.get(w)) {
foundCycle.set(true);
pivotNode.set(w);
}
});
})
.backwardFilter(v -> !foundCycle.get())
.backward(v -> {
//Updating paths leading to dead-ends
v.getInNeighbors().filter(inPath).forEach(w -> {
if (deg.get(w) > 0) {
deg.set(w, deg.get(w) - 1);
}
});
pivotNode.set(source.get(v));
//Removing from the potential cycle path
//a vertex that leads to a dead-end
PgxVertex vertex = pivotNode.get();
if (deg.get(vertex) == 0) {
inPath.set(vertex, false);
visited.set(vertex, true);
}
})
);
if (foundCycle.get()) {
//Adding the vertices (in REVERSE order) in the cycle
PgxVertex firstInCycle = pivotNode.get();
cycleNodes.pushFront(firstInCycle);
PgxVertex t = source.get(firstInCycle);
pivotNode.set(t);
Scalar<PgxEdge> e = Scalar.create();
while (pivotNode.get() != firstInCycle) {
cycleNodes.pushFront(pivotNode.get());
PgxVertex pivotNodeGet = pivotNode.get();
pivotNodeGet.getNeighbors().filter(inPath).forSequential(v ->
e.set(v.edge())
);
cycleEdges.pushFront(e.get());
PgxVertex vertex = pivotNode.get();
PgxVertex sourceVertex = source.get(vertex);
pivotNode.set(sourceVertex);
}
cycleNodes.pushFront(pivotNode.get());
PgxVertex pivotNodeGet = pivotNode.get();
pivotNodeGet.getNeighbors().filter(inPath).forSequential(v ->
e.set(v.edge())
);
cycleEdges.pushFront(e.get());
}
return foundCycle.get();
}
}
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
procedure find_cycle(graph G; nodeSeq cycle_nodes, edgeSeq cycle_edges) : bool {
vertexProp<bool> visited;
vertexProp<bool> in_path;
vertexProp<node> source;
vertexProp<int> deg;
G.visited = false;
G.in_path = false;
G.deg = _.degree();
bool found_cycle = false;
node pivot_node = G.pickRandom();
for (s: G.nodes) (!s.visited && !found_cycle) {
inDFS (v: G.nodes from s) (v.deg > 0) [!found_cycle] {
//Adding potential vertices in the cycle path
v.in_path = true;
foreach (w: v.nbrs) {
w.source = v;
if (w.in_path ) {
found_cycle = true;
pivot_node = w;
}
}
}
inPost (!found_cycle) {
//Updating paths leading to dead-ends
foreach (w: v.inNbrs) {
if (w.deg > 0) {
w.deg = w.deg - 1;
}
}
pivot_node = v.source;
//Removing from the potential cycle path
//a vertex that leads to a dead-end
if (pivot_node != NIL && pivot_node.deg == 0 && pivot_node.in_path) {
pivot_node.in_path = false;
pivot_node.visited = true;
}
}
}
if (found_cycle) {
//Adding the vertices (in REVERSE order) in the cycle
node first_in_cycle = pivot_node;
cycle_nodes.pushFront(pivot_node);
pivot_node = pivot_node.source;
while (pivot_node != first_in_cycle) {
cycle_nodes.pushFront(pivot_node);
for (v: pivot_node.nbrs) (v.in_path) {
edge e = v.edge();
cycle_edges.pushFront(e);
}
pivot_node = pivot_node.source;
}
cycle_nodes.pushFront(pivot_node);
for (v: pivot_node.nbrs) (v.in_path) {
edge e = v.edge();
cycle_edges.pushFront(e);
}
}
return found_cycle;
}
Find Cycle from Node
This implementation tries to find a cycle in a directed graph using the given vertex as starting point for the DFS traversal and will return the first cycle found, if there is one. In such case, the vertices and edges involved in the cycle will be returned in the order of visit. Restricting the DFS traversal to a single starting point means that some parts of the graph may not get explored.
Signature
Input Argument |
Type |
Comment |
G |
graph |
|
s |
node |
source vertex for the search. |
Output Argument |
Type |
Comment |
cycle_nodes |
nodeSeq |
vertex sequence holding the vertices in the cycle. |
cycle_edges |
edgeSeq |
edge sequence holding the edges in the cycle. |
Return Value |
Type |
Comment |
|
bool |
true if there is a cycle in the graph, false otherwise. |
Code
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
package oracle.pgx.algorithms;
import oracle.pgx.algorithm.EdgeSequence;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSequence;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import static oracle.pgx.algorithm.Traversal.inDFS;
@GraphAlgorithm
public class FindCycleFromNode {
public boolean findCycle(PgxGraph g, PgxVertex s, @Out VertexSequence cycleNodes, @Out EdgeSequence cycleEdges) {
VertexProperty<PgxVertex> source = VertexProperty.create();
VertexProperty<Long> deg = VertexProperty.create();
VertexProperty<Boolean> inPath = VertexProperty.create();
deg.setAll(PgxVertex::getOutDegree);
inPath.setAll(false);
Scalar<Boolean> foundCycle = Scalar.create(false);
Scalar<PgxVertex> pivotNode = Scalar.create();
inDFS(g, s).navigator(v -> !foundCycle.get()).filter(v -> v.getDegree() > 0).forward(v -> {
inPath.set(v, true);
v.getNeighbors().forEach(w -> {
source.set(w, v);
if (inPath.get(w)) {
foundCycle.set(true);
pivotNode.set(w);
}
});
}).backwardFilter(v -> !foundCycle.get()).backward(v -> {
v.getInNeighbors().forEach(w -> {
if (deg.get(w) > 0) {
deg.set(w, deg.get(w) - 1);
}
});
pivotNode.set(source.get(v));
if (deg.get(pivotNode.get()) == 0) {
inPath.set(pivotNode.get(), false);
}
});
if (foundCycle.get()) {
PgxVertex firstInCycle = pivotNode.get();
cycleNodes.pushFront(pivotNode.get());
pivotNode.set(source.get(pivotNode.get()));
Scalar<PgxEdge> e = Scalar.create();
while (pivotNode.get() != firstInCycle) {
cycleNodes.pushFront(pivotNode.get());
pivotNode.get().getOutNeighbors().filter(inPath).forSequential(v -> e.set(v.edge()));
cycleEdges.pushFront(e.get());
pivotNode.set(source.get(pivotNode.get()));
}
cycleNodes.pushFront(pivotNode.get());
pivotNode.get().getOutNeighbors().filter(inPath).forSequential(v -> e.set(v.edge()));
cycleEdges.pushFront(e.get());
}
return foundCycle.get();
}
}
/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
procedure find_cycle(graph G, node s; nodeSeq cycle_nodes, edgeSeq cycle_edges) : bool {
vertexProp<node> source;
vertexProp<int> deg;
vertexProp<bool> in_path;
G.deg = _.degree();
G.in_path = false;
bool found_cycle = false;
node pivot_node = G.pickRandom();
inDFS (v: G.nodes from s) (v.deg > 0) [!found_cycle] {
v.in_path = true;
foreach (w: v.nbrs) {
w.source = v;
if (w.in_path) {
found_cycle = true;
pivot_node = w;
}
}
}
inPost (!found_cycle) {
foreach (w: v.inNbrs) {
if (w.deg > 0) {
w.deg = w.deg - 1;
}
}
pivot_node = v.source;
if (pivot_node != NIL && pivot_node.deg == 0) {
pivot_node.in_path = false;
}
}
if (found_cycle) {
node first_in_cycle = pivot_node;
cycle_nodes.pushFront(pivot_node);
pivot_node = pivot_node.source;
while (pivot_node != first_in_cycle) {
cycle_nodes.pushFront(pivot_node);
for (v: pivot_node.nbrs) (v.in_path) {
edge e = v.edge();
cycle_edges.pushFront(e);
}
pivot_node = pivot_node.source;
}
cycle_nodes.pushFront(pivot_node);
for (v: pivot_node.nbrs) (v.in_path) {
edge e = v.edge();
cycle_edges.pushFront(e);
}
}
return found_cycle;
}