{"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":"course-prereqs","name":"Course prerequisites","description":"Fourteen courses of a computer science degree, each one semester long. Each edge points from a course to a course that requires it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"Programming 1","x":100,"y":200},{"id":"Discrete math","x":100,"y":500},{"id":"Calculus 1","x":100,"y":800},{"id":"Programming 2","x":300,"y":200},{"id":"Calculus 2","x":300,"y":720},{"id":"Linear algebra","x":300,"y":880},{"id":"Computer systems","x":500,"y":120},{"id":"Data structures","x":500,"y":360},{"id":"Probability","x":500,"y":700},{"id":"Operating systems","x":700,"y":260},{"id":"Databases","x":700,"y":420},{"id":"Algorithms","x":700,"y":580},{"id":"Compilers","x":900,"y":240},{"id":"Machine learning","x":900,"y":600}],"edges":[{"from":"Programming 1","to":"Programming 2"},{"from":"Discrete math","to":"Data structures"},{"from":"Discrete math","to":"Probability"},{"from":"Discrete math","to":"Algorithms"},{"from":"Calculus 1","to":"Calculus 2"},{"from":"Calculus 1","to":"Linear algebra"},{"from":"Programming 2","to":"Computer systems"},{"from":"Programming 2","to":"Data structures"},{"from":"Calculus 2","to":"Probability"},{"from":"Linear algebra","to":"Machine learning"},{"from":"Computer systems","to":"Operating systems"},{"from":"Computer systems","to":"Compilers"},{"from":"Data structures","to":"Operating systems"},{"from":"Data structures","to":"Databases"},{"from":"Data structures","to":"Algorithms"},{"from":"Probability","to":"Machine learning"},{"from":"Algorithms","to":"Compilers"},{"from":"Algorithms","to":"Machine learning"}],"durations":{"Algorithms":1,"Calculus 1":1,"Calculus 2":1,"Compilers":1,"Computer systems":1,"Data structures":1,"Databases":1,"Discrete math":1,"Linear algebra":1,"Machine learning":1,"Operating systems":1,"Probability":1,"Programming 1":1,"Programming 2":1},"durationUnit":"semesters","details":{"vertices":14,"edges":18,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.0989010989010989,"inDegree":{"min":0,"avg":1.2857142857142858,"max":3},"outDegree":{"min":0,"avg":1.2857142857142858,"max":3},"selfLoops":0,"components":1}},"problem":"In what order can a student take the courses, so that every course comes after the courses it requires?","params":{},"result":{"kind":"order","vertices":["Calculus 1","Calculus 2","Discrete math","Linear algebra","Probability","Programming 1","Programming 2","Computer systems","Data structures","Algorithms","Compilers","Databases","Machine learning","Operating systems"]},"answer":"In this order, every edge points forward, and vertices that are ready together go in alphabetical order: Calculus 1, Calculus 2, Discrete math, Linear algebra, Probability, Programming 1, Programming 2, Computer systems, Data structures, Algorithms, and so on to Operating systems.","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. Calculus 1, Discrete math and Programming 1 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":{"Programming 1":"0"}},{"panel":"indegree","set":{"Discrete math":"0"}},{"panel":"indegree","set":{"Calculus 1":"0"}},{"panel":"indegree","set":{"Programming 2":"1"}},{"panel":"indegree","set":{"Calculus 2":"1"}},{"panel":"indegree","set":{"Linear algebra":"1"}},{"panel":"indegree","set":{"Computer systems":"1"}},{"panel":"indegree","set":{"Data structures":"2"}},{"panel":"indegree","set":{"Probability":"2"}},{"panel":"indegree","set":{"Operating systems":"2"}},{"panel":"indegree","set":{"Databases":"1"}},{"panel":"indegree","set":{"Algorithms":"2"}},{"panel":"indegree","set":{"Compilers":"2"}},{"panel":"indegree","set":{"Machine learning":"3"}},{"v":"Calculus 1","state":"waiting"},{"v":"Discrete math","state":"waiting"},{"v":"Programming 1","state":"waiting"},{"panel":"ready","list":[{"key":"Calculus 1"},{"key":"Discrete math"},{"key":"Programming 1"}]}]},{"say":"Take Calculus 1, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Calculus 1","state":"current"},{"panel":"ready","list":[{"key":"Discrete math"},{"key":"Programming 1"}]},{"panel":"order","list":[{"key":"Calculus 1"}]}]},{"say":"Remove the 2 edges out of Calculus 1. Calculus 2 and Linear algebra have no incoming edges left, so they join the ready list.","ops":[{"e":["Calculus 1","Calculus 2"],"state":"removed"},{"panel":"indegree","set":{"Calculus 2":"0"}},{"e":["Calculus 1","Linear algebra"],"state":"removed"},{"panel":"indegree","set":{"Linear algebra":"0"}},{"v":"Calculus 2","state":"waiting"},{"v":"Linear algebra","state":"waiting"},{"panel":"ready","list":[{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Programming 1"}]}]},{"say":"Take Calculus 2, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Calculus 2","state":"current"},{"panel":"ready","list":[{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Programming 1"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"}]},{"v":"Calculus 1","state":"done"}]},{"say":"Remove the edge from Calculus 2 to Probability. Probability still has 1 incoming edge.","ops":[{"e":["Calculus 2","Probability"],"state":"removed"},{"panel":"indegree","set":{"Probability":"1"}},{"panel":"ready","list":[{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Programming 1"}]}]},{"say":"Take Discrete math, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Discrete math","state":"current"},{"panel":"ready","list":[{"key":"Linear algebra"},{"key":"Programming 1"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"}]},{"v":"Calculus 2","state":"done"}]},{"say":"Remove the 3 edges out of Discrete math. Probability has no incoming edges left, so it joins the ready list. Data structures and Algorithms still have incoming edges.","ops":[{"e":["Discrete math","Data structures"],"state":"removed"},{"panel":"indegree","set":{"Data structures":"1"}},{"e":["Discrete math","Probability"],"state":"removed"},{"panel":"indegree","set":{"Probability":"0"}},{"e":["Discrete math","Algorithms"],"state":"removed"},{"panel":"indegree","set":{"Algorithms":"1"}},{"v":"Probability","state":"waiting"},{"panel":"ready","list":[{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"}]}]},{"say":"Take Linear algebra, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Linear algebra","state":"current"},{"panel":"ready","list":[{"key":"Probability"},{"key":"Programming 1"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"}]},{"v":"Discrete math","state":"done"}]},{"say":"Remove the edge from Linear algebra to Machine learning. Machine learning still has 2 incoming edges.","ops":[{"e":["Linear algebra","Machine learning"],"state":"removed"},{"panel":"indegree","set":{"Machine learning":"2"}},{"panel":"ready","list":[{"key":"Probability"},{"key":"Programming 1"}]}]},{"say":"Take Probability, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Probability","state":"current"},{"panel":"ready","list":[{"key":"Programming 1"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"}]},{"v":"Linear algebra","state":"done"}]},{"say":"Remove the edge from Probability to Machine learning. Machine learning still has 1 incoming edge.","ops":[{"e":["Probability","Machine learning"],"state":"removed"},{"panel":"indegree","set":{"Machine learning":"1"}},{"panel":"ready","list":[{"key":"Programming 1"}]}]},{"say":"Take Programming 1, the only ready vertex, and add it to the order.","ops":[{"v":"Programming 1","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"}]},{"v":"Probability","state":"done"}]},{"say":"Remove the edge from Programming 1 to Programming 2. Programming 2 has no incoming edges left, so it joins the ready list.","ops":[{"e":["Programming 1","Programming 2"],"state":"removed"},{"panel":"indegree","set":{"Programming 2":"0"}},{"v":"Programming 2","state":"waiting"},{"panel":"ready","list":[{"key":"Programming 2"}]}]},{"say":"Take Programming 2, the only ready vertex, and add it to the order.","ops":[{"v":"Programming 2","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"}]},{"v":"Programming 1","state":"done"}]},{"say":"Remove the 2 edges out of Programming 2. Computer systems and Data structures have no incoming edges left, so they join the ready list.","ops":[{"e":["Programming 2","Computer systems"],"state":"removed"},{"panel":"indegree","set":{"Computer systems":"0"}},{"e":["Programming 2","Data structures"],"state":"removed"},{"panel":"indegree","set":{"Data structures":"0"}},{"v":"Computer systems","state":"waiting"},{"v":"Data structures","state":"waiting"},{"panel":"ready","list":[{"key":"Computer systems"},{"key":"Data structures"}]}]},{"say":"Take Computer systems, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Computer systems","state":"current"},{"panel":"ready","list":[{"key":"Data structures"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"}]},{"v":"Programming 2","state":"done"}]},{"say":"Remove the 2 edges out of Computer systems. Operating systems and Compilers still have incoming edges.","ops":[{"e":["Computer systems","Operating systems"],"state":"removed"},{"panel":"indegree","set":{"Operating systems":"1"}},{"e":["Computer systems","Compilers"],"state":"removed"},{"panel":"indegree","set":{"Compilers":"1"}},{"panel":"ready","list":[{"key":"Data structures"}]}]},{"say":"Take Data structures, the only ready vertex, and add it to the order.","ops":[{"v":"Data structures","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"},{"key":"Data structures"}]},{"v":"Computer systems","state":"done"}]},{"say":"Remove the 3 edges out of Data structures. Operating systems, Databases and Algorithms have no incoming edges left, so they join the ready list.","ops":[{"e":["Data structures","Operating systems"],"state":"removed"},{"panel":"indegree","set":{"Operating systems":"0"}},{"e":["Data structures","Databases"],"state":"removed"},{"panel":"indegree","set":{"Databases":"0"}},{"e":["Data structures","Algorithms"],"state":"removed"},{"panel":"indegree","set":{"Algorithms":"0"}},{"v":"Operating systems","state":"waiting"},{"v":"Databases","state":"waiting"},{"v":"Algorithms","state":"waiting"},{"panel":"ready","list":[{"key":"Algorithms"},{"key":"Databases"},{"key":"Operating systems"}]}]},{"say":"Take Algorithms, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Algorithms","state":"current"},{"panel":"ready","list":[{"key":"Databases"},{"key":"Operating systems"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Algorithms"}]},{"v":"Data structures","state":"done"}]},{"say":"Remove the 2 edges out of Algorithms. Compilers and Machine learning have no incoming edges left, so they join the ready list.","ops":[{"e":["Algorithms","Compilers"],"state":"removed"},{"panel":"indegree","set":{"Compilers":"0"}},{"e":["Algorithms","Machine learning"],"state":"removed"},{"panel":"indegree","set":{"Machine learning":"0"}},{"v":"Compilers","state":"waiting"},{"v":"Machine learning","state":"waiting"},{"panel":"ready","list":[{"key":"Compilers"},{"key":"Databases"},{"key":"Machine learning"},{"key":"Operating systems"}]}]},{"say":"Take Compilers, the ready vertex that comes first alphabetically, and add it to the order. It has no outgoing edges.","ops":[{"v":"Compilers","state":"current"},{"panel":"ready","list":[{"key":"Databases"},{"key":"Machine learning"},{"key":"Operating systems"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Algorithms"},{"key":"Compilers"}]},{"v":"Algorithms","state":"done"}]},{"say":"Take Databases, the ready vertex that comes first alphabetically, and add it to the order. It has no outgoing edges.","ops":[{"v":"Databases","state":"current"},{"panel":"ready","list":[{"key":"Machine learning"},{"key":"Operating systems"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Databases"}]},{"v":"Compilers","state":"done"}]},{"say":"Take Machine learning, the ready vertex that comes first alphabetically, and add it to the order. It has no outgoing edges.","ops":[{"v":"Machine learning","state":"current"},{"panel":"ready","list":[{"key":"Operating systems"}]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Databases"},{"key":"Machine learning"}]},{"v":"Databases","state":"done"}]},{"say":"Take Operating systems, the only ready vertex, and add it to the order. It has no outgoing edges.","ops":[{"v":"Operating systems","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Calculus 1"},{"key":"Calculus 2"},{"key":"Discrete math"},{"key":"Linear algebra"},{"key":"Probability"},{"key":"Programming 1"},{"key":"Programming 2"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Databases"},{"key":"Machine learning"},{"key":"Operating systems"}]},{"v":"Machine learning","state":"done"}]},{"say":"Done. All 14 vertices are in the order, and every edge points from an earlier vertex to a later one.","ops":[{"v":"Operating systems","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}"}
