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.
Import cycles
Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.
A directed graph with 18 vertices and 30 edges.
Which imports form the loop that stops the build?
FindCycle returns a cycle of 2 vertices: utils → logging → utils. 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 main, the first vertex in the graph's order. It begins the search path.
- Follow main to cli, a new vertex. cli joins the search path.
- Follow cli to config, a new vertex. config joins the search path.
- Follow config to utils, a new vertex. utils joins the search path.
- Follow utils to logging, a new vertex. logging joins the search path.
1 more steps lead to the last one:
- Done. FindCycle returns the 2 vertices of the cycle in order, starting where the back edge leads.
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.