{"algorithm":"has-cycle","about":["A cycle is a way to follow the edges from a vertex and come back to it. A directed graph with a cycle has no topological order, so a build tool checks for one before it orders anything: packages that import each other in a loop can't be built one after the other.","On a directed graph, gograph searches depth-first and keeps the vertices on the current search path. An edge to a vertex that is still on the path leads back to where the path passed before, so it closes a cycle. An edge to a vertex the search has already finished can't, since nothing after that vertex leads back to the path.","On an undirected graph, gograph searches breadth-first and remembers the vertex it reached each vertex from. Each edge is stored in both directions, so the edge back to that vertex is the same edge and doesn't count. Any other edge to a vertex already reached gives a second way between two vertices, which is a cycle.","The search stops at the first cycle, and costs O(V+E) at most. A graph created with gograph.Acyclic refuses every edge that would close a cycle, so HasCycle returns false for it without a search. HasCycle only says yes or no. To list the vertices of every cycle, use the strongly connected components."],"template":{"id":"maze","name":"Maze","description":"A maze of 30 cells in five rows, A to E, and six columns, 1 to 6, so C4 is row C, column 4. Each edge is an open passage between two cells. The way from A1 to E6 winds through most of the maze, and two short loops give a few cells a second route.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"A1","x":100,"y":180},{"id":"A2","x":260,"y":180},{"id":"A3","x":420,"y":180},{"id":"A4","x":580,"y":180},{"id":"A5","x":740,"y":180},{"id":"A6","x":900,"y":180},{"id":"B1","x":100,"y":340},{"id":"B2","x":260,"y":340},{"id":"B3","x":420,"y":340},{"id":"B4","x":580,"y":340},{"id":"B5","x":740,"y":340},{"id":"B6","x":900,"y":340},{"id":"C1","x":100,"y":500},{"id":"C2","x":260,"y":500},{"id":"C3","x":420,"y":500},{"id":"C4","x":580,"y":500},{"id":"C5","x":740,"y":500},{"id":"C6","x":900,"y":500},{"id":"D1","x":100,"y":660},{"id":"D2","x":260,"y":660},{"id":"D3","x":420,"y":660},{"id":"D4","x":580,"y":660},{"id":"D5","x":740,"y":660},{"id":"D6","x":900,"y":660},{"id":"E1","x":100,"y":820},{"id":"E2","x":260,"y":820},{"id":"E3","x":420,"y":820},{"id":"E4","x":580,"y":820},{"id":"E5","x":740,"y":820},{"id":"E6","x":900,"y":820}],"edges":[{"from":"A1","to":"A2"},{"from":"A2","to":"A3"},{"from":"A3","to":"B3"},{"from":"A4","to":"A5"},{"from":"A4","to":"B4"},{"from":"A5","to":"A6"},{"from":"A6","to":"B6"},{"from":"B1","to":"B2"},{"from":"B1","to":"C1"},{"from":"B2","to":"B3"},{"from":"B4","to":"C4"},{"from":"B5","to":"B6"},{"from":"B5","to":"C5"},{"from":"B6","to":"C6"},{"from":"C1","to":"C2"},{"from":"C2","to":"D2"},{"from":"C3","to":"C4"},{"from":"C3","to":"D3"},{"from":"C4","to":"D4"},{"from":"C5","to":"C6"},{"from":"C5","to":"D5"},{"from":"D1","to":"E1"},{"from":"D2","to":"E2"},{"from":"D3","to":"E3"},{"from":"D4","to":"E4"},{"from":"D5","to":"D6"},{"from":"D6","to":"E6"},{"from":"E1","to":"E2"},{"from":"E2","to":"E3"},{"from":"E3","to":"E4"},{"from":"E5","to":"E6"}],"details":{"vertices":30,"edges":31,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.07126436781609195,"degree":{"min":1,"avg":2.066666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Is there a loop in the maze, a way to walk around and come back to a cell without going back along a passage?","params":{},"result":{"kind":"yes-no","value":true},"answer":"Yes, the graph has a cycle: there are two different ways between some pair of vertices.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being checked","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Checked","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Reached a new vertex","color":"#009E73","shape":"thick"},{"id":"loop","label":"On the cycle","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"queue","title":"Queue","kind":"list"}]},"steps":[{"say":"HasCycle searches breadth-first from each vertex no earlier search has reached, in the graph's vertex order, and remembers the vertex it reached each one from. Each edge is stored in both directions, so the edge back to that vertex is the same edge and is skipped. Any other edge to a vertex already reached closes a cycle."},{"say":"Start at A1, the first vertex. Put it in the queue.","ops":[{"v":"A1","state":"waiting"},{"panel":"queue","list":[{"key":"A1"}]}]},{"say":"Take A1 from the front of the queue. A2 is new, so it joins the back of the queue.","ops":[{"v":"A1","state":"current"},{"v":"A2","state":"waiting"},{"e":["A1","A2"],"state":"tree"},{"panel":"queue","list":[{"key":"A2"}]}]},{"say":"Take A2 from the front of the queue. The edge back to A1, which the search reached it from, is the same edge, so it is skipped. A3 is new, so it joins the back of the queue.","ops":[{"v":"A2","state":"current"},{"v":"A1","state":"done"},{"v":"A3","state":"waiting"},{"e":["A2","A3"],"state":"tree"},{"panel":"queue","list":[{"key":"A3"}]}]},{"say":"Take A3 from the front of the queue. The edge back to A2 is skipped. B3 is new, so it joins the back of the queue.","ops":[{"v":"A3","state":"current"},{"v":"A2","state":"done"},{"v":"B3","state":"waiting"},{"e":["A3","B3"],"state":"tree"},{"panel":"queue","list":[{"key":"B3"}]}]},{"say":"Take B3 from the front of the queue. The edge back to A3 is skipped. B2 is new, so it joins the back of the queue.","ops":[{"v":"B3","state":"current"},{"v":"A3","state":"done"},{"v":"B2","state":"waiting"},{"e":["B3","B2"],"state":"tree"},{"panel":"queue","list":[{"key":"B2"}]}]},{"say":"Take B2 from the front of the queue. The edge back to B3 is skipped. B1 is new, so it joins the back of the queue.","ops":[{"v":"B2","state":"current"},{"v":"B3","state":"done"},{"v":"B1","state":"waiting"},{"e":["B2","B1"],"state":"tree"},{"panel":"queue","list":[{"key":"B1"}]}]},{"say":"Take B1 from the front of the queue. The edge back to B2 is skipped. C1 is new, so it joins the back of the queue.","ops":[{"v":"B1","state":"current"},{"v":"B2","state":"done"},{"v":"C1","state":"waiting"},{"e":["B1","C1"],"state":"tree"},{"panel":"queue","list":[{"key":"C1"}]}]},{"say":"Take C1 from the front of the queue. The edge back to B1 is skipped. C2 is new, so it joins the back of the queue.","ops":[{"v":"C1","state":"current"},{"v":"B1","state":"done"},{"v":"C2","state":"waiting"},{"e":["C1","C2"],"state":"tree"},{"panel":"queue","list":[{"key":"C2"}]}]},{"say":"Take C2 from the front of the queue. The edge back to C1 is skipped. D2 is new, so it joins the back of the queue.","ops":[{"v":"C2","state":"current"},{"v":"C1","state":"done"},{"v":"D2","state":"waiting"},{"e":["C2","D2"],"state":"tree"},{"panel":"queue","list":[{"key":"D2"}]}]},{"say":"Take D2 from the front of the queue. The edge back to C2 is skipped. E2 is new, so it joins the back of the queue.","ops":[{"v":"D2","state":"current"},{"v":"C2","state":"done"},{"v":"E2","state":"waiting"},{"e":["D2","E2"],"state":"tree"},{"panel":"queue","list":[{"key":"E2"}]}]},{"say":"Take E2 from the front of the queue. The edge back to D2 is skipped. E1 and E3 are new, so they join the back of the queue.","ops":[{"v":"E2","state":"current"},{"v":"D2","state":"done"},{"v":"E1","state":"waiting"},{"e":["E2","E1"],"state":"tree"},{"v":"E3","state":"waiting"},{"e":["E2","E3"],"state":"tree"},{"panel":"queue","list":[{"key":"E1"},{"key":"E3"}]}]},{"say":"Take E1 from the front of the queue. The edge back to E2 is skipped. D1 is new, so it joins the back of the queue.","ops":[{"v":"E1","state":"current"},{"v":"E2","state":"done"},{"v":"D1","state":"waiting"},{"e":["E1","D1"],"state":"tree"},{"panel":"queue","list":[{"key":"E3"},{"key":"D1"}]}]},{"say":"Take E3 from the front of the queue. The edge back to E2 is skipped. D3 and E4 are new, so they join the back of the queue.","ops":[{"v":"E3","state":"current"},{"v":"E1","state":"done"},{"v":"D3","state":"waiting"},{"e":["E3","D3"],"state":"tree"},{"v":"E4","state":"waiting"},{"e":["E3","E4"],"state":"tree"},{"panel":"queue","list":[{"key":"D1"},{"key":"D3"},{"key":"E4"}]}]},{"say":"Take D1 from the front of the queue. The edge back to E1 is skipped.","ops":[{"v":"D1","state":"current"},{"v":"E3","state":"done"},{"panel":"queue","list":[{"key":"D3"},{"key":"E4"}]}]},{"say":"Take D3 from the front of the queue. The edge back to E3 is skipped. C3 is new, so it joins the back of the queue.","ops":[{"v":"D3","state":"current"},{"v":"D1","state":"done"},{"v":"C3","state":"waiting"},{"e":["D3","C3"],"state":"tree"},{"panel":"queue","list":[{"key":"E4"},{"key":"C3"}]}]},{"say":"Take E4 from the front of the queue. The edge back to E3 is skipped. D4 is new, so it joins the back of the queue.","ops":[{"v":"E4","state":"current"},{"v":"D3","state":"done"},{"v":"D4","state":"waiting"},{"e":["E4","D4"],"state":"tree"},{"panel":"queue","list":[{"key":"C3"},{"key":"D4"}]}]},{"say":"Take C3 from the front of the queue. The edge back to D3 is skipped. C4 is new, so it joins the back of the queue.","ops":[{"v":"C3","state":"current"},{"v":"E4","state":"done"},{"v":"C4","state":"waiting"},{"e":["C3","C4"],"state":"tree"},{"panel":"queue","list":[{"key":"D4"},{"key":"C4"}]}]},{"say":"Take D4 from the front of the queue.","ops":[{"v":"D4","state":"current"},{"v":"C3","state":"done"},{"panel":"queue","list":[{"key":"C4"}]}]},{"say":"D4 also has an edge to C4, which the search already reached another way. The two ways back to where they meet and this edge make a cycle: D4 → E4 → E3 → D3 → C3 → C4 → D4. HasCycle returns true.","ops":[{"e":["D4","E4"],"state":"loop"},{"e":["E4","E3"],"state":"loop"},{"e":["E3","D3"],"state":"loop"},{"e":["D3","C3"],"state":"loop"},{"e":["C3","C4"],"state":"loop"},{"e":["C4","D4"],"state":"loop"}]}],"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":"fmt.Println(gograph.HasCycle(g)) // true when g has a cycle"}