{"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":"service-calls","name":"Microservice calls","description":"Nine services of an online shop. Each edge is a call from one service to another, and some services call each other back.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"Gateway","x":96,"y":384},{"id":"Auth","x":320,"y":128},{"id":"Users","x":608,"y":128},{"id":"Orders","x":384,"y":384},{"id":"Payments","x":640,"y":320},{"id":"Shipping","x":640,"y":544},{"id":"Inventory","x":448,"y":640},{"id":"Search","x":192,"y":640},{"id":"Notify","x":896,"y":320}],"edges":[{"from":"Gateway","to":"Auth"},{"from":"Gateway","to":"Orders"},{"from":"Gateway","to":"Search"},{"from":"Auth","to":"Users"},{"from":"Users","to":"Auth"},{"from":"Users","to":"Notify"},{"from":"Orders","to":"Users"},{"from":"Orders","to":"Inventory"},{"from":"Orders","to":"Payments"},{"from":"Payments","to":"Shipping"},{"from":"Payments","to":"Notify"},{"from":"Shipping","to":"Orders"},{"from":"Shipping","to":"Notify"},{"from":"Inventory","to":"Search"},{"from":"Search","to":"Inventory"}],"details":{"vertices":9,"edges":15,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.20833333333333334,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":0,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Which services call each other in a loop, where one slow reply can hold up every service on it?","params":{},"result":{"kind":"cycle","vertices":["Auth","Users"]},"answer":"FindCycle returns a cycle of 2 vertices: Auth → Users → Auth. 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 Gateway, the first vertex in the graph's order. It begins the search path.","ops":[{"v":"Gateway","state":"current"},{"panel":"path","list":[{"key":"Gateway"}]}]},{"say":"Follow Gateway to Auth, a new vertex. Auth joins the search path.","ops":[{"e":["Gateway","Auth"],"state":"tree"},{"v":"Auth","state":"current"},{"panel":"path","list":[{"key":"Gateway"},{"key":"Auth"}]}]},{"say":"Follow Auth to Users, a new vertex. Users joins the search path.","ops":[{"e":["Auth","Users"],"state":"tree"},{"v":"Users","state":"current"},{"panel":"path","list":[{"key":"Gateway"},{"key":"Auth"},{"key":"Users"}]}]},{"say":"Users to Auth leads to Auth, which is still on the search path. The path from Auth to Users and this edge close a cycle: Auth → Users → Auth. FindCycle stops here.","ops":[{"v":"Auth","state":"loop"},{"e":["Auth","Users"],"state":"loop"},{"v":"Users","state":"loop"},{"e":["Users","Auth"],"state":"loop"},{"panel":"cycle","list":[{"key":"Auth"},{"key":"Users"}]}]},{"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())"}
