{"algorithm":"stable-topological-sort","about":["The stable topological sort works like Kahn's algorithm, but the ready vertices wait in a priority queue instead of a plain queue. Whenever more than one is ready, it takes the smallest by the compare function you pass, such as cmp.Compare for alphabetical labels.","As long as compare only returns zero for equal labels, the order depends on the labels alone, not on the order the graph was built. Two programs that add the same edges in a different order get the same result, which keeps generated files and test output from changing between runs. The priority queue adds a log factor, for O((V+E) log V). Like gograph.TopologySort, it returns ErrDAGHasCycle when the graph has a cycle.","Use it when the order is shown to people or written to a file, such as the steps of a build plan, and every run has to give the same result."],"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","B3","C3","D3","E3","G3","B4","C4","D4","G4","B5","C5","D5","G5","B6","B7","C6","C7","D6","D7","E7","E8"]},"answer":"In this order, every edge points forward, and vertices that are ready together go in alphabetical order: B2, C2, D2, G2, B3, C3, D3, E3, G3, B4, and so on to E8.","legend":{"vertex":[{"id":"idle","label":"Has incoming edges left","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Ready","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":"Ready, alphabetical","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 ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.","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, the ready vertex that comes first alphabetically, 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, the ready vertex that comes first alphabetically, 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, the ready vertex that comes first alphabetically, 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, the ready vertex that comes first alphabetically, 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 ready list.","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":"B3"},{"key":"C3"},{"key":"D3"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take B3, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"B3","state":"current"},{"panel":"ready","list":[{"key":"C3"},{"key":"D3"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"}]},{"v":"G2","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":"2"}},{"e":["B3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"2"}},{"panel":"ready","list":[{"key":"C3"},{"key":"D3"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take C3, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"C3","state":"current"},{"panel":"ready","list":[{"key":"D3"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"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":"2"}},{"e":["C3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"1"}},{"panel":"ready","list":[{"key":"D3"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take D3, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"D3","state":"current"},{"panel":"ready","list":[{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"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 ready list. D5 still has 2 incoming edges.","ops":[{"e":["D3","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"2"}},{"e":["D3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"0"}},{"v":"E3","state":"waiting"},{"panel":"ready","list":[{"key":"E3"},{"key":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take E3, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"E3","state":"current"},{"panel":"ready","list":[{"key":"G3"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"}]},{"v":"D3","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":"G3"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take G3, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"G3","state":"current"},{"panel":"ready","list":[{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"}]},{"v":"E3","state":"done"}]},{"say":"Remove the 3 edges out of G3. B4, C4 and D4 have no incoming edges left, so they join the ready list.","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":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take B4, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"B4","state":"current"},{"panel":"ready","list":[{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"}]},{"v":"G3","state":"done"}]},{"say":"Remove the edge from B4 to B5. B5 still has 1 incoming edge.","ops":[{"e":["B4","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"1"}},{"panel":"ready","list":[{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take C4, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"C4","state":"current"},{"panel":"ready","list":[{"key":"D4"},{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"}]},{"v":"B4","state":"done"}]},{"say":"Remove the edge from C4 to C5. C5 still has 1 incoming edge.","ops":[{"e":["C4","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"1"}},{"panel":"ready","list":[{"key":"D4"},{"key":"G4"},{"key":"G5"}]}]},{"say":"Take D4, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"D4","state":"current"},{"panel":"ready","list":[{"key":"G4"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"}]},{"v":"C4","state":"done"}]},{"say":"Remove the edge from D4 to D5. D5 still has 1 incoming edge.","ops":[{"e":["D4","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"1"}},{"panel":"ready","list":[{"key":"G4"},{"key":"G5"}]}]},{"say":"Take G4, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"G4","state":"current"},{"panel":"ready","list":[{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"}]},{"v":"D4","state":"done"}]},{"say":"Remove the 3 edges out of G4. B5, C5 and D5 have no incoming edges left, so they join the ready list.","ops":[{"e":["G4","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"0"}},{"e":["G4","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"0"}},{"e":["G4","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"0"}},{"v":"B5","state":"waiting"},{"v":"C5","state":"waiting"},{"v":"D5","state":"waiting"},{"panel":"ready","list":[{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"}]}]},{"say":"Take B5, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"B5","state":"current"},{"panel":"ready","list":[{"key":"C5"},{"key":"D5"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"}]},{"v":"G4","state":"done"}]},{"say":"Remove the 2 edges out of B5. B6 and B7 still have incoming edges.","ops":[{"e":["B5","B6"],"state":"removed"},{"panel":"indegree","set":{"B6":"1"}},{"e":["B5","B7"],"state":"removed"},{"panel":"indegree","set":{"B7":"1"}},{"panel":"ready","list":[{"key":"C5"},{"key":"D5"},{"key":"G5"}]}]},{"say":"Take C5, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"C5","state":"current"},{"panel":"ready","list":[{"key":"D5"},{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"}]},{"v":"B5","state":"done"}]},{"say":"Remove the 2 edges out of C5. C6 and C7 still have incoming edges.","ops":[{"e":["C5","C6"],"state":"removed"},{"panel":"indegree","set":{"C6":"1"}},{"e":["C5","C7"],"state":"removed"},{"panel":"indegree","set":{"C7":"1"}},{"panel":"ready","list":[{"key":"D5"},{"key":"G5"}]}]},{"say":"Take D5, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"D5","state":"current"},{"panel":"ready","list":[{"key":"G5"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"}]},{"v":"C5","state":"done"}]},{"say":"Remove the 2 edges out of D5. D6 and D7 still have incoming edges.","ops":[{"e":["D5","D6"],"state":"removed"},{"panel":"indegree","set":{"D6":"1"}},{"e":["D5","D7"],"state":"removed"},{"panel":"indegree","set":{"D7":"1"}},{"panel":"ready","list":[{"key":"G5"}]}]},{"say":"Take G5, the only ready vertex, and add it to the order.","ops":[{"v":"G5","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"}]},{"v":"D5","state":"done"}]},{"say":"Remove the 3 edges out of G5. B6, C6 and D6 have no incoming edges left, so they join the ready list.","ops":[{"e":["G5","B6"],"state":"removed"},{"panel":"indegree","set":{"B6":"0"}},{"e":["G5","C6"],"state":"removed"},{"panel":"indegree","set":{"C6":"0"}},{"e":["G5","D6"],"state":"removed"},{"panel":"indegree","set":{"D6":"0"}},{"v":"B6","state":"waiting"},{"v":"C6","state":"waiting"},{"v":"D6","state":"waiting"},{"panel":"ready","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"}]}]},{"say":"Take B6, the ready vertex that comes first alphabetically, 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":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"}]},{"v":"G5","state":"done"}]},{"say":"Remove the edge from B6 to B7. B7 has no incoming edges left, so it joins the ready list.","ops":[{"e":["B6","B7"],"state":"removed"},{"panel":"indegree","set":{"B7":"0"}},{"v":"B7","state":"waiting"},{"panel":"ready","list":[{"key":"B7"},{"key":"C6"},{"key":"D6"}]}]},{"say":"Take B7, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"B7","state":"current"},{"panel":"ready","list":[{"key":"C6"},{"key":"D6"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"}]},{"v":"B6","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":"C6"},{"key":"D6"}]}]},{"say":"Take C6, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"C6","state":"current"},{"panel":"ready","list":[{"key":"D6"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"},{"key":"C6"}]},{"v":"B7","state":"done"}]},{"say":"Remove the edge from C6 to C7. C7 has no incoming edges left, so it joins the ready list.","ops":[{"e":["C6","C7"],"state":"removed"},{"panel":"indegree","set":{"C7":"0"}},{"v":"C7","state":"waiting"},{"panel":"ready","list":[{"key":"C7"},{"key":"D6"}]}]},{"say":"Take C7, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"C7","state":"current"},{"panel":"ready","list":[{"key":"D6"}]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"},{"key":"C6"},{"key":"C7"}]},{"v":"C6","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":"D6"}]}]},{"say":"Take D6, the only ready vertex, and add it to the order.","ops":[{"v":"D6","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"B2"},{"key":"C2"},{"key":"D2"},{"key":"G2"},{"key":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"},{"key":"C6"},{"key":"C7"},{"key":"D6"}]},{"v":"C7","state":"done"}]},{"say":"Remove the edge from D6 to D7. D7 has no incoming edges left, so it joins the ready list.","ops":[{"e":["D6","D7"],"state":"removed"},{"panel":"indegree","set":{"D7":"0"}},{"v":"D7","state":"waiting"},{"panel":"ready","list":[{"key":"D7"}]}]},{"say":"Take D7, the only ready vertex, 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":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"},{"key":"C6"},{"key":"C7"},{"key":"D6"},{"key":"D7"}]},{"v":"D6","state":"done"}]},{"say":"Remove the edge from D7 to E7. E7 has no incoming edges left, so it joins the ready list.","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 ready vertex, 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":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"},{"key":"C6"},{"key":"C7"},{"key":"D6"},{"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 ready list.","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 ready vertex, 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":"B3"},{"key":"C3"},{"key":"D3"},{"key":"E3"},{"key":"G3"},{"key":"B4"},{"key":"C4"},{"key":"D4"},{"key":"G4"},{"key":"B5"},{"key":"C5"},{"key":"D5"},{"key":"G5"},{"key":"B6"},{"key":"B7"},{"key":"C6"},{"key":"C7"},{"key":"D6"},{"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 := gograph.StableTopologySort(g, cmp.Compare)\nif err != nil {\n\treturn err // gograph.ErrDAGHasCycle\n}\nfor _, v := range order {\n\tfmt.Println(v.Label())\n}"}
