Find a cycle
Returns the vertices of one cycle in order: the first one a depth-first search closes with an edge back to its search path.
Time complexity O(V+E), gograph function connectivity.FindCycle.
How it works
Cycle detection says whether a graph has a cycle. FindCycle also says where: it returns the vertices of one cycle in order, so a build tool can tell which packages import each other in a loop instead of only that some do.
It runs traverse.DFSEventsAll, a depth-first search from each vertex no earlier search reached, and keeps the search path. An edge to a vertex that is still on the path is a back edge: the path runs from that vertex down to the one the search is at, and the edge leads back up, so together they are a cycle. FindCycle returns that part of the path at the first back edge. An edge to a finished vertex can't close a cycle, since nothing that vertex leads to reaches back to the path.
On an undirected graph, the edge back to the vertex a vertex was reached from is the same edge seen from the other end, so it doesn't count, and every other cycle has at least three vertices. A self-loop is a cycle of one vertex.
The search stops at the first back edge and costs O(V+E) at most. The cycle it returns is the first one it closes, not the shortest one. A graph created with gograph.Acyclic returns false without a search. To list every vertex that is on some cycle, use the strongly connected components.
Pipeline with a loop
The build pipeline after a change that makes Install wait for Unit tests, to reuse the packages the tests download. Each edge points from a job to a job that waits for it, and that one new edge makes three jobs wait on each other.
A directed graph with 7 vertices and 10 edges.
Since Install waits for Unit tests, the pipeline won't start. Which jobs wait on each other in a loop?
FindCycle returns a cycle of 3 vertices: Install → Compile → Unit tests → Install. It is the first cycle the search closes, and the graph can have others.
Step by step
- FindCycle searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and keeps the vertices on the current search path. The first edge to a vertex still on the path closes a cycle.
- Start at Checkout, the first vertex in the graph's order. It begins the search path.
- Follow Checkout to Install, a new vertex. Install joins the search path.
- Follow Install to Lint, a new vertex. Lint joins the search path.
- Follow Lint to Deploy, a new vertex. Deploy joins the search path.
- Deploy has no edges left to follow. It is finished and leaves the search path.
5 more steps lead to the last one:
- Done. FindCycle returns the 3 vertices of the cycle in order, starting where the back edge leads. The search stopped at the first cycle it closed, and a shorter one can exist.
Use it in Go
cycle, ok := connectivity.FindCycle(g)
if !ok {
return // no cycle
}
for _, v := range cycle {
fmt.Print(v.Label(), "->")
}
fmt.Println(cycle[0].Label())
Example graphs
- Pipeline with a loop, 7 vertices and 10 edges
- Microservice calls, 9 vertices and 15 edges
- Import cycles, 18 vertices and 30 edges
- Maze, 30 vertices and 31 edges
More in Connectivity
- Tarjan: Finds the strongly connected components of a directed graph, the groups of vertices that can all reach each other, with one depth-first search.
- Kosaraju: Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.
- Gabow: Finds the strongly connected components of a directed graph with one depth-first search and two stacks, without the lowlink values of Tarjan's algorithm.
- Condensation: Replaces each strongly connected component with one vertex. What is left is a DAG, so it can be sorted and scheduled.
- Connected components: Splits a graph into its connected pieces, the groups of vertices joined to each other by some path, with one search per piece.
- Cycle detection: Says whether a graph has a cycle, a way to follow its edges from a vertex back to the same vertex, and stops at the first one it finds.
- Bridges and articulation points: Finds the edges and the vertices whose loss splits an undirected graph into more pieces, its single points of failure, from one depth-first search.