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

  1. 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.
  2. Start at main, the first vertex in the graph's order. It begins the search path.
  3. Follow main to cli, a new vertex. cli joins the search path.
  4. Follow cli to config, a new vertex. config joins the search path.
  5. Follow config to utils, a new vertex. utils joins the search path.
  6. Follow utils to logging, a new vertex. logging joins the search path.

1 more steps lead to the last one:

  1. 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

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.

All algorithms