cycleVertex property
T?
cycleVertex
inherited
Returns the first vertex detected that is part of a cycle.
Returns null
if the graph is acyclic.
Implementation
T? get cycleVertex {
// Start vertex of the cycle.
T? start;
final temp = HashSet<T>();
final perm = HashSet<T>();
// Marks [this] graph as acyclic.
var isCyclic = false;
// Recursive function
void visit(T vertex) {
// Graph is not a Directed Acyclic Graph (DAG).
// Terminate iteration.
if (isCyclic) return;
// _Vertex has permanent mark.
// => This vertex and its neighbouring
// vertices have already been visited.
if (perm.contains(vertex)) return;
// A cycle has been detected. Mark graph as acyclic.
if (temp.contains(vertex)) {
start = vertex;
isCyclic = true;
return;
}
// Temporary mark. Marks current vertex as visited.
temp.add(vertex);
for (final connectedVertex in edges(vertex)) {
visit(connectedVertex);
}
// Permanent mark, indicating that there is no path from
// neighbouring vertices back to the current vertex.
perm.add(vertex);
}
// Main loop
for (final vertex in sortedVertices) {
if (isCyclic) break;
visit(vertex);
}
return start;
}