{"algorithm":"dfs","about":["Depth-first search goes from the vertex it is at to a neighbor it hasn't seen, and from there to the next, as deep as it can. The vertices it has gone through form the search path. When the vertex at the end of the path has no neighbor left to try, the search finishes it and backs up one vertex. Each vertex gets a discovery time when the search enters it and a finish time when it leaves, and the times of a vertex nest inside the times of the vertex it was reached from, like parentheses.","traverse.DFSEvents reports each step as an event and sorts every edge it meets into four kinds. A tree edge leads to a new vertex. A back edge leads to a vertex still on the search path, so it closes a loop. A forward edge leads to a finished vertex discovered after the one the search is at, a descendant reached another way. A cross edge leads to a finished vertex discovered before it, in another branch. An undirected graph has only tree and back edges, and the edge back to the vertex a vertex was reached from is the tree edge itself, not a back edge.","The search costs O(V+E). Use it to find everything a vertex can reach, to explore a maze one branch at a time, or for the back edges, which are how connectivity.FindCycle and the topological sorts by finish time work. The path it follows is rarely the shortest one. For the fewest edges, use Breadth-first."],"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":"Follow the imports from main one chain at a time, and sort each import into the four kinds: which ones lead back into the chain being followed, and so form a loop?","params":{"start":"main"},"result":{"kind":"order","vertices":["main","cli","config","utils","logging","db","cache","models","api","handlers","auth","session","users","billing","invoices","email","templates","middleware"]},"answer":"From main, depth-first visits 18 vertices: main, cli, config, utils, logging, db, cache, models, api, handlers, and so on to middleware. It met 17 tree edges, 5 back edges, 3 forward edges and 5 cross edges.","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":"Tree edge, to a new vertex","color":"#009E73","shape":"thick"},{"id":"back","label":"Back edge, to the search path","color":"#D55E00","shape":"dashed"},{"id":"forward","label":"Forward edge, to a finished descendant","color":"#56B4E9","shape":"dotted"},{"id":"cross","label":"Cross edge, to another branch","color":"#E69F00","shape":"line"}],"panels":[{"id":"times","title":"Discovered / finished","kind":"table"},{"id":"path","title":"Search path, start first","kind":"list"},{"id":"order","title":"Discovery order","kind":"list"}]},"steps":[{"say":"Start at main. Discover it at time 1, and it begins the search path.","ops":[{"v":"main","state":"current"},{"panel":"times","set":{"main":"1"}},{"panel":"path","list":[{"key":"main"}]},{"panel":"order","list":[{"key":"main"}]}]},{"say":"main to cli leads to a new vertex, so it is a tree edge. Discover cli at time 2, and it joins the search path.","ops":[{"e":["main","cli"],"state":"tree"},{"v":"cli","state":"current"},{"panel":"times","set":{"cli":"2"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"}]}]},{"say":"cli to config leads to a new vertex, so it is a tree edge. Discover config at time 3, and it joins the search path.","ops":[{"e":["cli","config"],"state":"tree"},{"v":"config","state":"current"},{"panel":"times","set":{"config":"3"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"}]}]},{"say":"config to utils leads to a new vertex, so it is a tree edge. Discover utils at time 4, and it joins the search path.","ops":[{"e":["config","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"times","set":{"utils":"4"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"}]}]},{"say":"utils to logging leads to a new vertex, so it is a tree edge. Discover logging at time 5, and it joins the search path.","ops":[{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"times","set":{"logging":"5"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"}]},{"panel":"order","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, so it is a back edge. The path from utils to logging and this edge make a loop.","ops":[{"e":["logging","utils"],"state":"back"}]},{"say":"logging has no neighbor left to try. Finish it at time 6 and back up to utils.","ops":[{"v":"logging","state":"done"},{"panel":"times","set":{"logging":"5/6"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"}]}]},{"say":"utils has no neighbor left to try. Finish it at time 7 and back up to config.","ops":[{"v":"utils","state":"done"},{"panel":"times","set":{"utils":"4/7"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"config"}]}]},{"say":"config has no neighbor left to try. Finish it at time 8 and back up to cli.","ops":[{"v":"config","state":"done"},{"panel":"times","set":{"config":"3/8"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"}]}]},{"say":"cli to db leads to a new vertex, so it is a tree edge. Discover db at time 9, and it joins the search path.","ops":[{"e":["cli","db"],"state":"tree"},{"v":"db","state":"current"},{"panel":"times","set":{"db":"9"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"db"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"}]}]},{"say":"db to cache leads to a new vertex, so it is a tree edge. Discover cache at time 10, and it joins the search path.","ops":[{"e":["db","cache"],"state":"tree"},{"v":"cache","state":"current"},{"panel":"times","set":{"cache":"10"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"db"},{"key":"cache"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"}]}]},{"say":"cache to models leads to a new vertex, so it is a tree edge. Discover models at time 11, and it joins the search path.","ops":[{"e":["cache","models"],"state":"tree"},{"v":"models","state":"current"},{"panel":"times","set":{"models":"11"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"db"},{"key":"cache"},{"key":"models"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"}]}]},{"say":"models to db leads to db, which is still on the search path, so it is a back edge. The path from db to models and this edge make a loop.","ops":[{"e":["models","db"],"state":"back"}]},{"say":"models has no neighbor left to try. Finish it at time 12 and back up to cache.","ops":[{"v":"models","state":"done"},{"panel":"times","set":{"models":"11/12"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"db"},{"key":"cache"}]}]},{"say":"cache has no neighbor left to try. Finish it at time 13 and back up to db.","ops":[{"v":"cache","state":"done"},{"panel":"times","set":{"cache":"10/13"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"},{"key":"db"}]}]},{"say":"db has no neighbor left to try. Finish it at time 14 and back up to cli.","ops":[{"v":"db","state":"done"},{"panel":"times","set":{"db":"9/14"}},{"panel":"path","list":[{"key":"main"},{"key":"cli"}]}]},{"say":"cli has no neighbor left to try. Finish it at time 15 and back up to main.","ops":[{"v":"cli","state":"done"},{"panel":"times","set":{"cli":"2/15"}},{"panel":"path","list":[{"key":"main"}]}]},{"say":"main to api leads to a new vertex, so it is a tree edge. Discover api at time 16, and it joins the search path.","ops":[{"e":["main","api"],"state":"tree"},{"v":"api","state":"current"},{"panel":"times","set":{"api":"16"}},{"panel":"path","list":[{"key":"main"},{"key":"api"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"}]}]},{"say":"api to handlers leads to a new vertex, so it is a tree edge. Discover handlers at time 17, and it joins the search path.","ops":[{"e":["api","handlers"],"state":"tree"},{"v":"handlers","state":"current"},{"panel":"times","set":{"handlers":"17"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"}]}]},{"say":"handlers to auth leads to a new vertex, so it is a tree edge. Discover auth at time 18, and it joins the search path.","ops":[{"e":["handlers","auth"],"state":"tree"},{"v":"auth","state":"current"},{"panel":"times","set":{"auth":"18"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"}]}]},{"say":"auth to session leads to a new vertex, so it is a tree edge. Discover session at time 19, and it joins the search path.","ops":[{"e":["auth","session"],"state":"tree"},{"v":"session","state":"current"},{"panel":"times","set":{"session":"19"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"}]}]},{"say":"session to users leads to a new vertex, so it is a tree edge. Discover users at time 20, and it joins the search path.","ops":[{"e":["session","users"],"state":"tree"},{"v":"users","state":"current"},{"panel":"times","set":{"users":"20"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"}]}]},{"say":"users to auth leads to auth, which is still on the search path, so it is a back edge. The path from auth to users and this edge make a loop.","ops":[{"e":["users","auth"],"state":"back"}]},{"say":"users to billing leads to a new vertex, so it is a tree edge. Discover billing at time 21, and it joins the search path.","ops":[{"e":["users","billing"],"state":"tree"},{"v":"billing","state":"current"},{"panel":"times","set":{"billing":"21"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"}]}]},{"say":"billing to invoices leads to a new vertex, so it is a tree edge. Discover invoices at time 22, and it joins the search path.","ops":[{"e":["billing","invoices"],"state":"tree"},{"v":"invoices","state":"current"},{"panel":"times","set":{"invoices":"22"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"}]}]},{"say":"invoices to users leads to users, which is still on the search path, so it is a back edge. The path from users to invoices and this edge make a loop.","ops":[{"e":["invoices","users"],"state":"back"}]},{"say":"invoices to models leads to models, which is finished and was discovered before invoices, at time 11, in another branch. So the edge is a cross edge.","ops":[{"e":["invoices","models"],"state":"cross"}]},{"say":"invoices to email leads to a new vertex, so it is a tree edge. Discover email at time 23, and it joins the search path.","ops":[{"e":["invoices","email"],"state":"tree"},{"v":"email","state":"current"},{"panel":"times","set":{"email":"23"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"},{"key":"email"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"},{"key":"email"}]}]},{"say":"email to templates leads to a new vertex, so it is a tree edge. Discover templates at time 24, and it joins the search path.","ops":[{"e":["email","templates"],"state":"tree"},{"v":"templates","state":"current"},{"panel":"times","set":{"templates":"24"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"},{"key":"email"},{"key":"templates"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"},{"key":"email"},{"key":"templates"}]}]},{"say":"templates to email leads to email, which is still on the search path, so it is a back edge. The path from email to templates and this edge make a loop.","ops":[{"e":["templates","email"],"state":"back"}]},{"say":"templates has no neighbor left to try. Finish it at time 25 and back up to email.","ops":[{"v":"templates","state":"done"},{"panel":"times","set":{"templates":"24/25"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"},{"key":"email"}]}]},{"say":"email has no neighbor left to try. Finish it at time 26 and back up to invoices.","ops":[{"v":"email","state":"done"},{"panel":"times","set":{"email":"23/26"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"}]}]},{"say":"invoices has no neighbor left to try. Finish it at time 27 and back up to billing.","ops":[{"v":"invoices","state":"done"},{"panel":"times","set":{"invoices":"22/27"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"}]}]},{"say":"billing has no neighbor left to try. Finish it at time 28 and back up to users.","ops":[{"v":"billing","state":"done"},{"panel":"times","set":{"billing":"21/28"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"}]}]},{"say":"users to models leads to models, which is finished and was discovered before users, at time 11, in another branch. So the edge is a cross edge.","ops":[{"e":["users","models"],"state":"cross"}]},{"say":"users has no neighbor left to try. Finish it at time 29 and back up to session.","ops":[{"v":"users","state":"done"},{"panel":"times","set":{"users":"20/29"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"}]}]},{"say":"session has no neighbor left to try. Finish it at time 30 and back up to auth.","ops":[{"v":"session","state":"done"},{"panel":"times","set":{"session":"19/30"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"},{"key":"auth"}]}]},{"say":"auth has no neighbor left to try. Finish it at time 31 and back up to handlers.","ops":[{"v":"auth","state":"done"},{"panel":"times","set":{"auth":"18/31"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"handlers"}]}]},{"say":"handlers to users leads to users, which is finished and was discovered after handlers, at time 20. So users is a descendant of handlers, reached another way first, and the edge is a forward edge.","ops":[{"e":["handlers","users"],"state":"forward"}]},{"say":"handlers to billing leads to billing, which is finished and was discovered after handlers, at time 21. So billing is a descendant of handlers, reached another way first, and the edge is a forward edge.","ops":[{"e":["handlers","billing"],"state":"forward"}]},{"say":"handlers has no neighbor left to try. Finish it at time 32 and back up to api.","ops":[{"v":"handlers","state":"done"},{"panel":"times","set":{"handlers":"17/32"}},{"panel":"path","list":[{"key":"main"},{"key":"api"}]}]},{"say":"api to middleware leads to a new vertex, so it is a tree edge. Discover middleware at time 33, and it joins the search path.","ops":[{"e":["api","middleware"],"state":"tree"},{"v":"middleware","state":"current"},{"panel":"times","set":{"middleware":"33"}},{"panel":"path","list":[{"key":"main"},{"key":"api"},{"key":"middleware"}]},{"panel":"order","list":[{"key":"main"},{"key":"cli"},{"key":"config"},{"key":"utils"},{"key":"logging"},{"key":"db"},{"key":"cache"},{"key":"models"},{"key":"api"},{"key":"handlers"},{"key":"auth"},{"key":"session"},{"key":"users"},{"key":"billing"},{"key":"invoices"},{"key":"email"},{"key":"templates"},{"key":"middleware"}]}]},{"say":"middleware to auth leads to auth, which is finished and was discovered before middleware, at time 18, in another branch. So the edge is a cross edge.","ops":[{"e":["middleware","auth"],"state":"cross"}]},{"say":"middleware to logging leads to logging, which is finished and was discovered before middleware, at time 5, in another branch. So the edge is a cross edge.","ops":[{"e":["middleware","logging"],"state":"cross"}]},{"say":"middleware has no neighbor left to try. Finish it at time 34 and back up to api.","ops":[{"v":"middleware","state":"done"},{"panel":"times","set":{"middleware":"33/34"}},{"panel":"path","list":[{"key":"main"},{"key":"api"}]}]},{"say":"api to config leads to config, which is finished and was discovered before api, at time 3, in another branch. So the edge is a cross edge.","ops":[{"e":["api","config"],"state":"cross"}]},{"say":"api has no neighbor left to try. Finish it at time 35 and back up to main.","ops":[{"v":"api","state":"done"},{"panel":"times","set":{"api":"16/35"}},{"panel":"path","list":[{"key":"main"}]}]},{"say":"main to config leads to config, which is finished and was discovered after main, at time 3. So config is a descendant of main, reached another way first, and the edge is a forward edge.","ops":[{"e":["main","config"],"state":"forward"}]},{"say":"main has no neighbor left to try. Finish it at time 36, which ends the search.","ops":[{"v":"main","state":"done"},{"panel":"times","set":{"main":"1/36"}},{"panel":"path","list":[]}]},{"say":"Done. Depth-first discovered 18 vertices from main. It met 17 tree edges, 5 back edges, 3 forward edges and 5 cross edges."}],"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":"for ev := range traverse.DFSEvents(g, \"main\") {\n\tif ev.Edge != nil {\n\t\tfmt.Println(ev.Kind, ev.Edge.Source().Label(), ev.Edge.Destination().Label())\n\t}\n}"}
