{"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":"import-cycles","name":"Import cycles","description":"Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"main","x":500,"y":80},{"id":"cli","x":180,"y":240},{"id":"api","x":560,"y":200},{"id":"config","x":860,"y":320},{"id":"handlers","x":420,"y":340},{"id":"middleware","x":680,"y":370},{"id":"auth","x":720,"y":470},{"id":"session","x":700,"y":640},{"id":"users","x":480,"y":540},{"id":"billing","x":280,"y":470},{"id":"invoices","x":300,"y":650},{"id":"models","x":480,"y":790},{"id":"db","x":180,"y":800},{"id":"cache","x":320,"y":900},{"id":"email","x":700,"y":800},{"id":"templates","x":880,"y":860},{"id":"utils","x":900,"y":480},{"id":"logging","x":900,"y":660}],"edges":[{"from":"main","to":"cli"},{"from":"main","to":"api"},{"from":"main","to":"config"},{"from":"cli","to":"config"},{"from":"cli","to":"db"},{"from":"api","to":"handlers"},{"from":"api","to":"middleware"},{"from":"api","to":"config"},{"from":"handlers","to":"auth"},{"from":"handlers","to":"users"},{"from":"handlers","to":"billing"},{"from":"middleware","to":"auth"},{"from":"middleware","to":"logging"},{"from":"auth","to":"session"},{"from":"session","to":"users"},{"from":"users","to":"auth"},{"from":"users","to":"billing"},{"from":"users","to":"models"},{"from":"billing","to":"invoices"},{"from":"invoices","to":"users"},{"from":"invoices","to":"models"},{"from":"invoices","to":"email"},{"from":"models","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"models"},{"from":"email","to":"templates"},{"from":"templates","to":"email"},{"from":"config","to":"utils"},{"from":"utils","to":"logging"},{"from":"logging","to":"utils"}],"details":{"vertices":18,"edges":30,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.09803921568627451,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":1,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Which imports form the loop that stops the build?","params":{},"result":{"kind":"cycle","vertices":["utils","logging"]},"answer":"FindCycle returns a cycle of 2 vertices: utils → logging → utils. 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 main, the first vertex in the graph's order. It begins the search path.","ops":[{"v":"main","state":"current"},{"panel":"path","list":[{"key":"main"}]}]},{"say":"Follow main to cli, a new vertex. cli joins the search path.","ops":[{"e":["main","cli"],"state":"tree"},{"v":"cli","state":"current"},{"panel":"path","list":[{"key":"main"},{"key":"cli"}]}]},{"say":"Follow cli to config, a new vertex. config joins the search path.","ops":[{"e":["cli","config"],"state":"tree"},{"v":"config","state":"current"},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"}]}]},{"say":"Follow config to utils, a new vertex. utils joins the search path.","ops":[{"e":["config","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"}]}]},{"say":"Follow utils to logging, a new vertex. logging joins the search path.","ops":[{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"}]}]},{"say":"logging to utils leads to utils, which is still on the search path. The path from utils to logging and this edge close a cycle: utils → logging → utils. FindCycle stops here.","ops":[{"v":"utils","state":"loop"},{"e":["utils","logging"],"state":"loop"},{"v":"logging","state":"loop"},{"e":["logging","utils"],"state":"loop"},{"panel":"cycle","list":[{"key":"utils"},{"key":"logging"}]}]},{"say":"Done. FindCycle returns the 2 vertices of the cycle in order, starting where the back edge leads."}],"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())"}
