{"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":"delivery-area","name":"Delivery area","description":"Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Depot","x":128,"y":320},{"id":"Bakery","x":352,"y":128},{"id":"Market","x":352,"y":512},{"id":"School","x":608,"y":128},{"id":"Park","x":608,"y":352},{"id":"Clinic","x":608,"y":544},{"id":"Library","x":832,"y":224},{"id":"Station","x":864,"y":480}],"edges":[{"from":"Depot","to":"Bakery","weight":4},{"from":"Depot","to":"Market","weight":2},{"from":"Market","to":"Bakery","weight":1},{"from":"Bakery","to":"School","weight":5},{"from":"Bakery","to":"Park","weight":7},{"from":"Market","to":"Park","weight":8},{"from":"Market","to":"Clinic","weight":10},{"from":"School","to":"Library","weight":3},{"from":"Park","to":"Library","weight":2},{"from":"Park","to":"Station","weight":6},{"from":"Clinic","to":"Station","weight":2},{"from":"Library","to":"Station","weight":5}],"details":{"vertices":8,"edges":12,"directed":true,"weighted":true,"acyclic":true,"weightMin":1,"weightMax":10,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.5,"max":3},"outDegree":{"min":0,"avg":1.5,"max":3},"selfLoops":0,"components":1}},"problem":"Can a van that keeps to the one-way streets ever get back to a corner it has already left?","params":{},"result":{"kind":"yes-no","value":false},"answer":"No, the graph has no cycle. Following the edges never leads back to where it started, so the vertices can be put in an order where every edge points forward.","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"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Followed","color":"#009E73","shape":"thick"},{"id":"loop","label":"On the cycle","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"path","title":"Search path, start first","kind":"list"}]},"steps":[{"say":"HasCycle 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. An edge to a vertex still on the path closes a cycle, and the search stops there."},{"say":"Start at Depot, the first vertex. It goes on the search path.","ops":[{"v":"Depot","state":"current"},{"panel":"path","list":[{"key":"Depot"}]}]},{"say":"Follow Depot to Bakery, which goes on the search path.","ops":[{"e":["Depot","Bakery"],"state":"tree"},{"v":"Bakery","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"}]}]},{"say":"Follow Bakery to School, which goes on the search path.","ops":[{"e":["Bakery","School"],"state":"tree"},{"v":"School","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"},{"key":"School"}]}]},{"say":"Follow School to Library, which goes on the search path.","ops":[{"e":["School","Library"],"state":"tree"},{"v":"Library","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"},{"key":"School"},{"key":"Library"}]}]},{"say":"Follow Library to Station, which goes on the search path.","ops":[{"e":["Library","Station"],"state":"tree"},{"v":"Station","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"},{"key":"School"},{"key":"Library"},{"key":"Station"}]}]},{"say":"Station has no edges left to follow, so it is finished and leaves the path. Back to Library.","ops":[{"v":"Station","state":"done"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"},{"key":"School"},{"key":"Library"}]}]},{"say":"Library has no edges left to follow, so it is finished and leaves the path. Back to School.","ops":[{"v":"Library","state":"done"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"},{"key":"School"}]}]},{"say":"School has no edges left to follow, so it is finished and leaves the path. Back to Bakery.","ops":[{"v":"School","state":"done"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"}]}]},{"say":"Follow Bakery to Park, which goes on the search path.","ops":[{"e":["Bakery","Park"],"state":"tree"},{"v":"Park","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"},{"key":"Park"}]}]},{"say":"The edges from Park to Library and Station lead to finished vertices, which can't lead back to the path. Park has no edges left to follow, so it is finished and leaves the path. Back to Bakery.","ops":[{"v":"Park","state":"done"},{"panel":"path","list":[{"key":"Depot"},{"key":"Bakery"}]}]},{"say":"Bakery has no edges left to follow, so it is finished and leaves the path. Back to Depot.","ops":[{"v":"Bakery","state":"done"},{"panel":"path","list":[{"key":"Depot"}]}]},{"say":"Follow Depot to Market, which goes on the search path.","ops":[{"e":["Depot","Market"],"state":"tree"},{"v":"Market","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Market"}]}]},{"say":"The edges from Market to Bakery and Park lead to finished vertices, which can't lead back to the path. Follow Market to Clinic, which goes on the search path.","ops":[{"e":["Market","Clinic"],"state":"tree"},{"v":"Clinic","state":"current"},{"panel":"path","list":[{"key":"Depot"},{"key":"Market"},{"key":"Clinic"}]}]},{"say":"The edge from Clinic to Station leads to a finished vertex, which can't lead back to the path. Clinic has no edges left to follow, so it is finished and leaves the path. Back to Market.","ops":[{"v":"Clinic","state":"done"},{"panel":"path","list":[{"key":"Depot"},{"key":"Market"}]}]},{"say":"Market has no edges left to follow, so it is finished and leaves the path. Back to Depot.","ops":[{"v":"Market","state":"done"},{"panel":"path","list":[{"key":"Depot"}]}]},{"say":"Depot has no edges left to follow, so it is finished and leaves the path.","ops":[{"v":"Depot","state":"done"},{"panel":"path","list":[]}]},{"say":"Done. Every vertex is finished, and no edge led back to a vertex on the search path, so HasCycle returns false."}],"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"}