{"algorithm":"topological-sort","about":["A topological sort puts the vertices of a directed graph without cycles in an order where every edge points forward: for an edge from A to B, A comes before B. gograph uses Kahn's algorithm. It counts the incoming edges of each vertex and queues the vertices that have none. Each time it takes a vertex from the queue, it removes that vertex's outgoing edges, and a vertex left with no incoming edges joins the back of the queue.","If the queue empties before every vertex is placed, the rest are on a cycle or after one, and gograph.TopologySort returns ErrDAGHasCycle instead of an order. It costs O(V+E). The order depends only on the order the vertices and edges were added, so a graph built the same way gives the same order every time.","Use it to schedule work with dependencies, such as build steps, course plans or database migrations. To break ties between ready vertices by a fixed rule instead of by the order the graph was built, use the stable topological sort."],"template":{"id":"spreadsheet","name":"Spreadsheet formulas","description":"A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"B2","x":41,"y":195},{"id":"C2","x":41,"y":561},{"id":"D2","x":41,"y":884},{"id":"G2","x":41,"y":714},{"id":"G3","x":41,"y":408},{"id":"G4","x":194,"y":195},{"id":"G5","x":347,"y":302},{"id":"B3","x":194,"y":348},{"id":"C3","x":194,"y":654},{"id":"D3","x":194,"y":960},{"id":"B4","x":194,"y":42},{"id":"C4","x":194,"y":501},{"id":"D4","x":194,"y":807},{"id":"B5","x":347,"y":149},{"id":"C5","x":347,"y":455},{"id":"D5","x":347,"y":608},{"id":"B6","x":500,"y":218},{"id":"C6","x":500,"y":371},{"id":"D6","x":500,"y":524},{"id":"B7","x":653,"y":242},{"id":"C7","x":653,"y":395},{"id":"D7","x":653,"y":548},{"id":"E3","x":347,"y":761},{"id":"E7","x":806,"y":418},{"id":"E8","x":959,"y":487}],"edges":[{"from":"B2","to":"B3"},{"from":"G2","to":"B3"},{"from":"C2","to":"C3"},{"from":"G2","to":"C3"},{"from":"D2","to":"D3"},{"from":"G2","to":"D3"},{"from":"B2","to":"B4"},{"from":"G3","to":"B4"},{"from":"C2","to":"C4"},{"from":"G3","to":"C4"},{"from":"D2","to":"D4"},{"from":"G3","to":"D4"},{"from":"B3","to":"B5"},{"from":"B4","to":"B5"},{"from":"G4","to":"B5"},{"from":"C3","to":"C5"},{"from":"C4","to":"C5"},{"from":"G4","to":"C5"},{"from":"D3","to":"D5"},{"from":"D4","to":"D5"},{"from":"G4","to":"D5"},{"from":"B5","to":"B6"},{"from":"G5","to":"B6"},{"from":"C5","to":"C6"},{"from":"G5","to":"C6"},{"from":"D5","to":"D6"},{"from":"G5","to":"D6"},{"from":"B5","to":"B7"},{"from":"B6","to":"B7"},{"from":"C5","to":"C7"},{"from":"C6","to":"C7"},{"from":"D5","to":"D7"},{"from":"D6","to":"D7"},{"from":"B3","to":"E3"},{"from":"C3","to":"E3"},{"from":"D3","to":"E3"},{"from":"B7","to":"E7"},{"from":"C7","to":"E7"},{"from":"D7","to":"E7"},{"from":"E7","to":"E8"},{"from":"E3","to":"E8"}],"durations":{"B2":1,"B3":2,"B4":2,"B5":1,"B6":3,"B7":1,"C2":1,"C3":2,"C4":2,"C5":1,"C6":3,"C7":1,"D2":1,"D3":2,"D4":2,"D5":1,"D6":3,"D7":1,"E3":4,"E7":4,"E8":1,"G2":1,"G3":1,"G4":1,"G5":1},"durationUnit":"milliseconds","details":{"vertices":25,"edges":41,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.06833333333333333,"inDegree":{"min":0,"avg":1.64,"max":3},"outDegree":{"min":0,"avg":1.64,"max":3},"selfLoops":0,"components":1}},"problem":"In what order should the sheet recompute its cells, so that every formula reads cells that are already up to date?","params":{},"result":{"kind":"order","vertices":["B2","C2","D2","G2","G3","G4","G5","B3","C3","D3","B4","C4","D4","E3","B5","C5","D5","B6","C6","D6","B7","C7","D7","E7","E8"]},"answer":"In this order, every edge points forward: B2, C2, D2, G2, G3, G4, G5, B3, C3, D3, and so on to E8.","legend":{"vertex":[{"id":"idle","label":"Has incoming edges left","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In the queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being placed","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Placed","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"removed","label":"Removed, its start is placed","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"ready","title":"Queue, front first","kind":"list"},{"id":"indegree","title":"In-degree left","kind":"table"},{"id":"order","title":"Topological order","kind":"list"}]},"steps":[{"say":"Count the incoming edges of each vertex, its in-degree. B2, C2, D2, G2, G3, G4 and G5 have none, so they start the queue in the order they were added to the graph.","ops":[{"panel":"indegree","set":{"B2":"0"}},{"panel":"indegree","set":{"C2":"0"}},{"panel":"indegree","set":{"D2":"0"}},{"panel":"indegree","set":{"G2":"0"}},{"panel":"indegree","set":{"G3":"0"}},{"panel":"indegree","set":{"G4":"0"}},{"panel":"indegree","set":{"G5":"0"}},{"panel":"indegree","set":{"B3":"2"}},{"panel":"indegree","set":{"C3":"2"}},{"panel":"indegree","set":{"D3":"2"}},{"panel":"indegree","set":{"B4":"2"}},{"panel":"indegree","set":{"C4":"2"}},{"panel":"indegree","set":{"D4":"2"}},{"panel":"indegree","set":{"B5":"3"}},{"panel":"indegree","set":{"C5":"3"}},{"panel":"indegree","set":{"D5":"3"}},{"panel":"indegree","set":{"B6":"2"}},{"panel":"indegree","set":{"C6":"2"}},{"panel":"indegree","set":{"D6":"2"}},{"panel":"indegree","set":{"B7":"2"}},{"panel":"indegree","set":{"C7":"2"}},{"panel":"indegree","set":{"D7":"2"}},{"panel":"indegree","set":{"E3":"3"}},{"panel":"indegree","set":{"E7":"3"}},{"panel":"indegree","set":{"E8":"2"}},{"v":"B2","state":"waiting"},{"v":"C2","state":"waiting"},{"v":"D2","state":"waiting"},{"v":"G2","state":"waiting"},{"v":"G3","state":"waiting"},{"v":"G4","state":"waiting"},{"v":"G5","state":"waiting"},{"panel":"ready","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take B2 from the front of the queue and add it to the order.","ops":[{"v":"B2","state":"current"},{"panel":"ready","list":[{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"}]}]},{"say":"Remove the 2 edges out of B2. B3 and B4 still have incoming edges.","ops":[{"e":["B2","B3"],"state":"removed"},{"panel":"indegree","set":{"B3":"1"}},{"e":["B2","B4"],"state":"removed"},{"panel":"indegree","set":{"B4":"1"}},{"panel":"ready","list":[{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take C2 from the front of the queue and add it to the order.","ops":[{"v":"C2","state":"current"},{"panel":"ready","list":[{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"}]},{"v":"B2","state":"done"}]},{"say":"Remove the 2 edges out of C2. C3 and C4 still have incoming edges.","ops":[{"e":["C2","C3"],"state":"removed"},{"panel":"indegree","set":{"C3":"1"}},{"e":["C2","C4"],"state":"removed"},{"panel":"indegree","set":{"C4":"1"}},{"panel":"ready","list":[{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take D2 from the front of the queue and add it to the order.","ops":[{"v":"D2","state":"current"},{"panel":"ready","list":[{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"}]},{"v":"C2","state":"done"}]},{"say":"Remove the 2 edges out of D2. D3 and D4 still have incoming edges.","ops":[{"e":["D2","D3"],"state":"removed"},{"panel":"indegree","set":{"D3":"1"}},{"e":["D2","D4"],"state":"removed"},{"panel":"indegree","set":{"D4":"1"}},{"panel":"ready","list":[{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take G2 from the front of the queue and add it to the order.","ops":[{"v":"G2","state":"current"},{"panel":"ready","list":[{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"}]},{"v":"D2","state":"done"}]},{"say":"Remove the 3 edges out of G2. B3, C3 and D3 have no incoming edges left, so they join the back of the queue in that order.","ops":[{"e":["G2","B3"],"state":"removed"},{"panel":"indegree","set":{"B3":"0"}},{"e":["G2","C3"],"state":"removed"},{"panel":"indegree","set":{"C3":"0"}},{"e":["G2","D3"],"state":"removed"},{"panel":"indegree","set":{"D3":"0"}},{"v":"B3","state":"waiting"},{"v":"C3","state":"waiting"},{"v":"D3","state":"waiting"},{"panel":"ready","list":[{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"}]}]},{"say":"Take G3 from the front of the queue and add it to the order.","ops":[{"v":"G3","state":"current"},{"panel":"ready","list":[{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"}]},{"v":"G2","state":"done"}]},{"say":"Remove the 3 edges out of G3. B4, C4 and D4 have no incoming edges left, so they join the back of the queue in that order.","ops":[{"e":["G3","B4"],"state":"removed"},{"panel":"indegree","set":{"B4":"0"}},{"e":["G3","C4"],"state":"removed"},{"panel":"indegree","set":{"C4":"0"}},{"e":["G3","D4"],"state":"removed"},{"panel":"indegree","set":{"D4":"0"}},{"v":"B4","state":"waiting"},{"v":"C4","state":"waiting"},{"v":"D4","state":"waiting"},{"panel":"ready","list":[{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]}]},{"say":"Take G4 from the front of the queue and add it to the order.","ops":[{"v":"G4","state":"current"},{"panel":"ready","list":[{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"}]},{"v":"G3","state":"done"}]},{"say":"Remove the 3 edges out of G4. B5, C5 and D5 still have incoming edges.","ops":[{"e":["G4","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"2"}},{"e":["G4","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"2"}},{"e":["G4","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"2"}},{"panel":"ready","list":[{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]}]},{"say":"Take G5 from the front of the queue and add it to the order.","ops":[{"v":"G5","state":"current"},{"panel":"ready","list":[{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"v":"G4","state":"done"}]},{"say":"Remove the 3 edges out of G5. B6, C6 and D6 still have incoming edges.","ops":[{"e":["G5","B6"],"state":"removed"},{"panel":"indegree","set":{"B6":"1"}},{"e":["G5","C6"],"state":"removed"},{"panel":"indegree","set":{"C6":"1"}},{"e":["G5","D6"],"state":"removed"},{"panel":"indegree","set":{"D6":"1"}},{"panel":"ready","list":[{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]}]},{"say":"Take B3 from the front of the queue and add it to the order.","ops":[{"v":"B3","state":"current"},{"panel":"ready","list":[{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"}]},{"v":"G5","state":"done"}]},{"say":"Remove the 2 edges out of B3. B5 and E3 still have incoming edges.","ops":[{"e":["B3","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"1"}},{"e":["B3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"2"}},{"panel":"ready","list":[{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]}]},{"say":"Take C3 from the front of the queue and add it to the order.","ops":[{"v":"C3","state":"current"},{"panel":"ready","list":[{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"}]},{"v":"B3","state":"done"}]},{"say":"Remove the 2 edges out of C3. C5 and E3 still have incoming edges.","ops":[{"e":["C3","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"1"}},{"e":["C3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"1"}},{"panel":"ready","list":[{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]}]},{"say":"Take D3 from the front of the queue and add it to the order.","ops":[{"v":"D3","state":"current"},{"panel":"ready","list":[{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"}]},{"v":"C3","state":"done"}]},{"say":"Remove the 2 edges out of D3. E3 has no incoming edges left, so it joins the back of the queue. D5 still has 1 incoming edge.","ops":[{"e":["D3","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"1"}},{"e":["D3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"0"}},{"v":"E3","state":"waiting"},{"panel":"ready","list":[{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"}]}]},{"say":"Take B4 from the front of the queue and add it to the order.","ops":[{"v":"B4","state":"current"},{"panel":"ready","list":[{"key":"C4"},{"key":"D4"},{"key":"E3"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"}]},{"v":"D3","state":"done"}]},{"say":"Remove the edge from B4 to B5. B5 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["B4","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"0"}},{"v":"B5","state":"waiting"},{"panel":"ready","list":[{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"}]}]},{"say":"Take C4 from the front of the queue and add it to the order.","ops":[{"v":"C4","state":"current"},{"panel":"ready","list":[{"key":"D4"},{"key":"E3"},{"key":"B5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"}]},{"v":"B4","state":"done"}]},{"say":"Remove the edge from C4 to C5. C5 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["C4","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"0"}},{"v":"C5","state":"waiting"},{"panel":"ready","list":[{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"}]}]},{"say":"Take D4 from the front of the queue and add it to the order.","ops":[{"v":"D4","state":"current"},{"panel":"ready","list":[{"key":"E3"},{"key":"B5"},{"key":"C5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"v":"C4","state":"done"}]},{"say":"Remove the edge from D4 to D5. D5 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["D4","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"0"}},{"v":"D5","state":"waiting"},{"panel":"ready","list":[{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"}]}]},{"say":"Take E3 from the front of the queue and add it to the order.","ops":[{"v":"E3","state":"current"},{"panel":"ready","list":[{"key":"B5"},{"key":"C5"},{"key":"D5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"}]},{"v":"D4","state":"done"}]},{"say":"Remove the edge from E3 to E8. E8 still has 1 incoming edge.","ops":[{"e":["E3","E8"],"state":"removed"},{"panel":"indegree","set":{"E8":"1"}},{"panel":"ready","list":[{"key":"B5"},{"key":"C5"},{"key":"D5"}]}]},{"say":"Take B5 from the front of the queue and add it to the order.","ops":[{"v":"B5","state":"current"},{"panel":"ready","list":[{"key":"C5"},{"key":"D5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"}]},{"v":"E3","state":"done"}]},{"say":"Remove the 2 edges out of B5. B6 has no incoming edges left, so it joins the back of the queue. B7 still has 1 incoming edge.","ops":[{"e":["B5","B6"],"state":"removed"},{"panel":"indegree","set":{"B6":"0"}},{"e":["B5","B7"],"state":"removed"},{"panel":"indegree","set":{"B7":"1"}},{"v":"B6","state":"waiting"},{"panel":"ready","list":[{"key":"C5"},{"key":"D5"},{"key":"B6"}]}]},{"say":"Take C5 from the front of the queue and add it to the order.","ops":[{"v":"C5","state":"current"},{"panel":"ready","list":[{"key":"D5"},{"key":"B6"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"}]},{"v":"B5","state":"done"}]},{"say":"Remove the 2 edges out of C5. C6 has no incoming edges left, so it joins the back of the queue. C7 still has 1 incoming edge.","ops":[{"e":["C5","C6"],"state":"removed"},{"panel":"indegree","set":{"C6":"0"}},{"e":["C5","C7"],"state":"removed"},{"panel":"indegree","set":{"C7":"1"}},{"v":"C6","state":"waiting"},{"panel":"ready","list":[{"key":"D5"},{"key":"B6"},{"key":"C6"}]}]},{"say":"Take D5 from the front of the queue and add it to the order.","ops":[{"v":"D5","state":"current"},{"panel":"ready","list":[{"key":"B6"},{"key":"C6"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"}]},{"v":"C5","state":"done"}]},{"say":"Remove the 2 edges out of D5. D6 has no incoming edges left, so it joins the back of the queue. D7 still has 1 incoming edge.","ops":[{"e":["D5","D6"],"state":"removed"},{"panel":"indegree","set":{"D6":"0"}},{"e":["D5","D7"],"state":"removed"},{"panel":"indegree","set":{"D7":"1"}},{"v":"D6","state":"waiting"},{"panel":"ready","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"}]}]},{"say":"Take B6 from the front of the queue and add it to the order.","ops":[{"v":"B6","state":"current"},{"panel":"ready","list":[{"key":"C6"},{"key":"D6"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"}]},{"v":"D5","state":"done"}]},{"say":"Remove the edge from B6 to B7. B7 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["B6","B7"],"state":"removed"},{"panel":"indegree","set":{"B7":"0"}},{"v":"B7","state":"waiting"},{"panel":"ready","list":[{"key":"C6"},{"key":"D6"},{"key":"B7"}]}]},{"say":"Take C6 from the front of the queue and add it to the order.","ops":[{"v":"C6","state":"current"},{"panel":"ready","list":[{"key":"D6"},{"key":"B7"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"}]},{"v":"B6","state":"done"}]},{"say":"Remove the edge from C6 to C7. C7 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["C6","C7"],"state":"removed"},{"panel":"indegree","set":{"C7":"0"}},{"v":"C7","state":"waiting"},{"panel":"ready","list":[{"key":"D6"},{"key":"B7"},{"key":"C7"}]}]},{"say":"Take D6 from the front of the queue and add it to the order.","ops":[{"v":"D6","state":"current"},{"panel":"ready","list":[{"key":"B7"},{"key":"C7"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"},{"key":"D6"}]},{"v":"C6","state":"done"}]},{"say":"Remove the edge from D6 to D7. D7 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["D6","D7"],"state":"removed"},{"panel":"indegree","set":{"D7":"0"}},{"v":"D7","state":"waiting"},{"panel":"ready","list":[{"key":"B7"},{"key":"C7"},{"key":"D7"}]}]},{"say":"Take B7 from the front of the queue and add it to the order.","ops":[{"v":"B7","state":"current"},{"panel":"ready","list":[{"key":"C7"},{"key":"D7"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"}]},{"v":"D6","state":"done"}]},{"say":"Remove the edge from B7 to E7. E7 still has 2 incoming edges.","ops":[{"e":["B7","E7"],"state":"removed"},{"panel":"indegree","set":{"E7":"2"}},{"panel":"ready","list":[{"key":"C7"},{"key":"D7"}]}]},{"say":"Take C7 from the front of the queue and add it to the order.","ops":[{"v":"C7","state":"current"},{"panel":"ready","list":[{"key":"D7"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"}]},{"v":"B7","state":"done"}]},{"say":"Remove the edge from C7 to E7. E7 still has 1 incoming edge.","ops":[{"e":["C7","E7"],"state":"removed"},{"panel":"indegree","set":{"E7":"1"}},{"panel":"ready","list":[{"key":"D7"}]}]},{"say":"Take D7, the only vertex in the queue, and add it to the order.","ops":[{"v":"D7","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"}]},{"v":"C7","state":"done"}]},{"say":"Remove the edge from D7 to E7. E7 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["D7","E7"],"state":"removed"},{"panel":"indegree","set":{"E7":"0"}},{"v":"E7","state":"waiting"},{"panel":"ready","list":[{"key":"E7"}]}]},{"say":"Take E7, the only vertex in the queue, and add it to the order.","ops":[{"v":"E7","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E7"}]},{"v":"D7","state":"done"}]},{"say":"Remove the edge from E7 to E8. E8 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["E7","E8"],"state":"removed"},{"panel":"indegree","set":{"E8":"0"}},{"v":"E8","state":"waiting"},{"panel":"ready","list":[{"key":"E8"}]}]},{"say":"Take E8, the only vertex in the queue, and add it to the order. It has no outgoing edges.","ops":[{"v":"E8","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"G3"},{"key":"G4"},{"key":"G5"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"E3"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E7"},{"key":"E8"}]},{"v":"E7","state":"done"}]},{"say":"Done. All 25 vertices are in the order, and every edge points from an earlier vertex to a later one.","ops":[{"v":"E8","state":"done"}]}],"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":"order, err := traverse.Topological(g)\nif err != nil {\n\treturn err // gograph.ErrDAGHasCycle\n}\nfor v := range order {\n\tfmt.Println(v.Label())\n}"}
