{"algorithm":"find-cycle","about":["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."],"template":{"id":"pipeline-loop","name":"Pipeline with a loop","description":"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.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"Checkout","x":100,"y":440},{"id":"Install","x":300,"y":440},{"id":"Lint","x":500,"y":280},{"id":"Compile","x":500,"y":560},{"id":"Unit tests","x":700,"y":440},{"id":"Docker image","x":700,"y":760},{"id":"Deploy","x":900,"y":440}],"edges":[{"from":"Checkout","to":"Install"},{"from":"Checkout","to":"Docker image"},{"from":"Install","to":"Lint"},{"from":"Install","to":"Compile"},{"from":"Lint","to":"Deploy"},{"from":"Compile","to":"Unit tests"},{"from":"Compile","to":"Docker image"},{"from":"Unit tests","to":"Deploy"},{"from":"Docker image","to":"Deploy"},{"from":"Unit tests","to":"Install"}],"details":{"vertices":7,"edges":10,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.23809523809523808,"inDegree":{"min":0,"avg":1.4285714285714286,"max":3},"outDegree":{"min":0,"avg":1.4285714285714286,"max":2},"selfLoops":0,"components":1}},"problem":"Since Install waits for Unit tests, the pipeline won't start. Which jobs wait on each other in a loop?","params":{},"result":{"kind":"cycle","vertices":["Install","Compile","Unit tests"]},"answer":"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.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"current","label":"On the search path","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Finished","color":"#009E73","shape":"filled"},{"id":"loop","label":"On the cycle","color":"#D55E00","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Followed to a new vertex","color":"#009E73","shape":"thick"},{"id":"finished","label":"To a finished vertex, can't close a cycle","color":"#CC79A7","shape":"dotted"},{"id":"loop","label":"On the cycle","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"path","title":"Search path, start first","kind":"list"},{"id":"cycle","title":"Cycle","kind":"list"}]},"steps":[{"say":"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."},{"say":"Start at Checkout, the first vertex in the graph's order. It begins the search path.","ops":[{"v":"Checkout","state":"current"},{"panel":"path","list":[{"key":"Checkout"}]}]},{"say":"Follow Checkout to Install, a new vertex. Install joins the search path.","ops":[{"e":["Checkout","Install"],"state":"tree"},{"v":"Install","state":"current"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"}]}]},{"say":"Follow Install to Lint, a new vertex. Lint joins the search path.","ops":[{"e":["Install","Lint"],"state":"tree"},{"v":"Lint","state":"current"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"}]}]},{"say":"Follow Lint to Deploy, a new vertex. Deploy joins the search path.","ops":[{"e":["Lint","Deploy"],"state":"tree"},{"v":"Deploy","state":"current"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"},{"key":"Deploy"}]}]},{"say":"Deploy has no edges left to follow. It is finished and leaves the search path.","ops":[{"v":"Deploy","state":"done"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"}]}]},{"say":"Lint has no edges left to follow. It is finished and leaves the search path.","ops":[{"v":"Lint","state":"done"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"}]}]},{"say":"Follow Install to Compile, a new vertex. Compile joins the search path.","ops":[{"e":["Install","Compile"],"state":"tree"},{"v":"Compile","state":"current"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"}]}]},{"say":"Follow Compile to Unit tests, a new vertex. Unit tests joins the search path.","ops":[{"e":["Compile","Unit tests"],"state":"tree"},{"v":"Unit tests","state":"current"},{"panel":"path","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"},{"key":"Unit tests"}]}]},{"say":"Unit tests to Deploy leads to Deploy, which is finished. Nothing Deploy leads to reaches back to the search path, so this edge can't close a cycle.","ops":[{"e":["Unit tests","Deploy"],"state":"finished"}]},{"say":"Unit tests to Install leads to Install, which is still on the search path. The path from Install to Unit tests and this edge close a cycle: Install → Compile → Unit tests → Install. FindCycle stops here.","ops":[{"v":"Install","state":"loop"},{"e":["Install","Compile"],"state":"loop"},{"v":"Compile","state":"loop"},{"e":["Compile","Unit tests"],"state":"loop"},{"v":"Unit tests","state":"loop"},{"e":["Unit tests","Install"],"state":"loop"},{"panel":"cycle","list":[{"key":"Install"},{"key":"Compile"},{"key":"Unit tests"}]}]},{"say":"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."}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"cycle, ok := connectivity.FindCycle(g)\nif !ok {\n\treturn // no cycle\n}\nfor _, v := range cycle {\n\tfmt.Print(v.Label(), \"->\")\n}\nfmt.Println(cycle[0].Label())"}
