{"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":"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":["Programming 1","Discrete math","Calculus 1","Programming 2","Calculus 2","Linear algebra","Computer systems","Data structures","Probability","Operating systems","Databases","Algorithms","Compilers","Machine learning"]},"answer":"In this order, every edge points forward: Programming 1, Discrete math, Calculus 1, Programming 2, Calculus 2, Linear algebra, Computer systems, Data structures, Probability, Operating systems, and so on to Machine learning.","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. Programming 1, Discrete math and Calculus 1 have none, so they start the queue in the order they were added to the graph.","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":"Programming 1","state":"waiting"},{"v":"Discrete math","state":"waiting"},{"v":"Calculus 1","state":"waiting"},{"panel":"ready","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"}]}]},{"say":"Take Programming 1 from the front of the queue and add it to the order.","ops":[{"v":"Programming 1","state":"current"},{"panel":"ready","list":[{"key":"Discrete math"},{"key":"Calculus 1"}]},{"panel":"order","list":[{"key":"Programming 1"}]}]},{"say":"Remove the edge from Programming 1 to Programming 2. Programming 2 has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["Programming 1","Programming 2"],"state":"removed"},{"panel":"indegree","set":{"Programming 2":"0"}},{"v":"Programming 2","state":"waiting"},{"panel":"ready","list":[{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"}]}]},{"say":"Take Discrete math from the front of the queue and add it to the order.","ops":[{"v":"Discrete math","state":"current"},{"panel":"ready","list":[{"key":"Calculus 1"},{"key":"Programming 2"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"}]},{"v":"Programming 1","state":"done"}]},{"say":"Remove the 3 edges out of Discrete math. Data structures, Probability 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":"1"}},{"e":["Discrete math","Algorithms"],"state":"removed"},{"panel":"indegree","set":{"Algorithms":"1"}},{"panel":"ready","list":[{"key":"Calculus 1"},{"key":"Programming 2"}]}]},{"say":"Take Calculus 1 from the front of the queue and add it to the order.","ops":[{"v":"Calculus 1","state":"current"},{"panel":"ready","list":[{"key":"Programming 2"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"}]},{"v":"Discrete math","state":"done"}]},{"say":"Remove the 2 edges out of Calculus 1. Calculus 2 and Linear algebra have no incoming edges left, so they join the back of the queue in that order.","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":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"}]}]},{"say":"Take Programming 2 from the front of the queue and add it to the order.","ops":[{"v":"Programming 2","state":"current"},{"panel":"ready","list":[{"key":"Calculus 2"},{"key":"Linear algebra"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"}]},{"v":"Calculus 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 back of the queue in that order.","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":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"}]}]},{"say":"Take Calculus 2 from the front of the queue and add it to the order.","ops":[{"v":"Calculus 2","state":"current"},{"panel":"ready","list":[{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"}]},{"v":"Programming 2","state":"done"}]},{"say":"Remove the edge from Calculus 2 to Probability. Probability has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["Calculus 2","Probability"],"state":"removed"},{"panel":"indegree","set":{"Probability":"0"}},{"v":"Probability","state":"waiting"},{"panel":"ready","list":[{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"}]}]},{"say":"Take Linear algebra from the front of the queue and add it to the order.","ops":[{"v":"Linear algebra","state":"current"},{"panel":"ready","list":[{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"}]},{"v":"Calculus 2","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":"Computer systems"},{"key":"Data structures"},{"key":"Probability"}]}]},{"say":"Take Computer systems from the front of the queue and add it to the order.","ops":[{"v":"Computer systems","state":"current"},{"panel":"ready","list":[{"key":"Data structures"},{"key":"Probability"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"}]},{"v":"Linear algebra","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"},{"key":"Probability"}]}]},{"say":"Take Data structures from the front of the queue and add it to the order.","ops":[{"v":"Data structures","state":"current"},{"panel":"ready","list":[{"key":"Probability"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"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 back of the queue in that order.","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":"Probability"},{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]}]},{"say":"Take Probability from the front of the queue and add it to the order.","ops":[{"v":"Probability","state":"current"},{"panel":"ready","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"}]},{"v":"Data structures","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":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]}]},{"say":"Take Operating systems from the front of the queue and add it to the order. It has no outgoing edges.","ops":[{"v":"Operating systems","state":"current"},{"panel":"ready","list":[{"key":"Databases"},{"key":"Algorithms"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"},{"key":"Operating systems"}]},{"v":"Probability","state":"done"}]},{"say":"Take Databases from the front of the queue and add it to the order. It has no outgoing edges.","ops":[{"v":"Databases","state":"current"},{"panel":"ready","list":[{"key":"Algorithms"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"},{"key":"Operating systems"},{"key":"Databases"}]},{"v":"Operating systems","state":"done"}]},{"say":"Take Algorithms, the only vertex in the queue, and add it to the order.","ops":[{"v":"Algorithms","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"},{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]},{"v":"Databases","state":"done"}]},{"say":"Remove the 2 edges out of Algorithms. Compilers and Machine learning have no incoming edges left, so they join the back of the queue in that order.","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":"Machine learning"}]}]},{"say":"Take Compilers from the front of the queue and add it to the order. It has no outgoing edges.","ops":[{"v":"Compilers","state":"current"},{"panel":"ready","list":[{"key":"Machine learning"}]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"},{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"},{"key":"Compilers"}]},{"v":"Algorithms","state":"done"}]},{"say":"Take Machine learning, the only vertex in the queue, and add it to the order. It has no outgoing edges.","ops":[{"v":"Machine learning","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"},{"key":"Programming 2"},{"key":"Calculus 2"},{"key":"Linear algebra"},{"key":"Computer systems"},{"key":"Data structures"},{"key":"Probability"},{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Machine learning"}]},{"v":"Compilers","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":"Machine learning","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}"}
