{"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":"build-pipeline","name":"Build pipeline","description":"The jobs of a CI pipeline for a web service, and how many minutes each one takes. Each edge points from a job to a job that waits for it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"Checkout","x":100,"y":440},{"id":"Install","x":300,"y":440},{"id":"Lint","x":500,"y":280},{"id":"Compile","x":500,"y":560},{"id":"Unit tests","x":700,"y":440},{"id":"Docker image","x":700,"y":760},{"id":"Deploy","x":900,"y":440}],"edges":[{"from":"Checkout","to":"Install"},{"from":"Checkout","to":"Docker image"},{"from":"Install","to":"Lint"},{"from":"Install","to":"Compile"},{"from":"Lint","to":"Deploy"},{"from":"Compile","to":"Unit tests"},{"from":"Compile","to":"Docker image"},{"from":"Unit tests","to":"Deploy"},{"from":"Docker image","to":"Deploy"}],"durations":{"Checkout":1,"Compile":3,"Deploy":2,"Docker image":5,"Install":3,"Lint":6,"Unit tests":6},"durationUnit":"minutes","details":{"vertices":7,"edges":9,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.2857142857142858,"max":3},"outDegree":{"min":0,"avg":1.2857142857142858,"max":2},"selfLoops":0,"components":1}},"problem":"In what order can the jobs run, so that each job starts only after the jobs it waits for?","params":{},"result":{"kind":"order","vertices":["Checkout","Install","Compile","Docker image","Lint","Unit tests","Deploy"]},"answer":"In this order, every edge points forward, and vertices that are ready together go in alphabetical order: Checkout, Install, Compile, Docker image, Lint, Unit tests and Deploy.","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. Only Checkout has none, so it starts the ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.","ops":[{"panel":"indegree","set":{"Checkout":"0"}},{"panel":"indegree","set":{"Install":"1"}},{"panel":"indegree","set":{"Lint":"1"}},{"panel":"indegree","set":{"Compile":"1"}},{"panel":"indegree","set":{"Unit tests":"1"}},{"panel":"indegree","set":{"Docker image":"2"}},{"panel":"indegree","set":{"Deploy":"3"}},{"v":"Checkout","state":"waiting"},{"panel":"ready","list":[{"key":"Checkout"}]}]},{"say":"Take Checkout, the only ready vertex, and add it to the order.","ops":[{"v":"Checkout","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"}]}]},{"say":"Remove the 2 edges out of Checkout. Install has no incoming edges left, so it joins the ready list. Docker image still has 1 incoming edge.","ops":[{"e":["Checkout","Install"],"state":"removed"},{"panel":"indegree","set":{"Install":"0"}},{"e":["Checkout","Docker image"],"state":"removed"},{"panel":"indegree","set":{"Docker image":"1"}},{"v":"Install","state":"waiting"},{"panel":"ready","list":[{"key":"Install"}]}]},{"say":"Take Install, the only ready vertex, and add it to the order.","ops":[{"v":"Install","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"}]},{"v":"Checkout","state":"done"}]},{"say":"Remove the 2 edges out of Install. Lint and Compile have no incoming edges left, so they join the ready list.","ops":[{"e":["Install","Lint"],"state":"removed"},{"panel":"indegree","set":{"Lint":"0"}},{"e":["Install","Compile"],"state":"removed"},{"panel":"indegree","set":{"Compile":"0"}},{"v":"Lint","state":"waiting"},{"v":"Compile","state":"waiting"},{"panel":"ready","list":[{"key":"Compile"},{"key":"Lint"}]}]},{"say":"Take Compile, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Compile","state":"current"},{"panel":"ready","list":[{"key":"Lint"}]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"}]},{"v":"Install","state":"done"}]},{"say":"Remove the 2 edges out of Compile. Unit tests and Docker image have no incoming edges left, so they join the ready list.","ops":[{"e":["Compile","Unit tests"],"state":"removed"},{"panel":"indegree","set":{"Unit tests":"0"}},{"e":["Compile","Docker image"],"state":"removed"},{"panel":"indegree","set":{"Docker image":"0"}},{"v":"Unit tests","state":"waiting"},{"v":"Docker image","state":"waiting"},{"panel":"ready","list":[{"key":"Docker image"},{"key":"Lint"},{"key":"Unit tests"}]}]},{"say":"Take Docker image, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Docker image","state":"current"},{"panel":"ready","list":[{"key":"Lint"},{"key":"Unit tests"}]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"},{"key":"Docker image"}]},{"v":"Compile","state":"done"}]},{"say":"Remove the edge from Docker image to Deploy. Deploy still has 2 incoming edges.","ops":[{"e":["Docker image","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"2"}},{"panel":"ready","list":[{"key":"Lint"},{"key":"Unit tests"}]}]},{"say":"Take Lint, the ready vertex that comes first alphabetically, and add it to the order.","ops":[{"v":"Lint","state":"current"},{"panel":"ready","list":[{"key":"Unit tests"}]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"},{"key":"Docker image"},{"key":"Lint"}]},{"v":"Docker image","state":"done"}]},{"say":"Remove the edge from Lint to Deploy. Deploy still has 1 incoming edge.","ops":[{"e":["Lint","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"1"}},{"panel":"ready","list":[{"key":"Unit tests"}]}]},{"say":"Take Unit tests, the only ready vertex, and add it to the order.","ops":[{"v":"Unit tests","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"},{"key":"Docker image"},{"key":"Lint"},{"key":"Unit tests"}]},{"v":"Lint","state":"done"}]},{"say":"Remove the edge from Unit tests to Deploy. Deploy has no incoming edges left, so it joins the ready list.","ops":[{"e":["Unit tests","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"0"}},{"v":"Deploy","state":"waiting"},{"panel":"ready","list":[{"key":"Deploy"}]}]},{"say":"Take Deploy, the only ready vertex, and add it to the order. It has no outgoing edges.","ops":[{"v":"Deploy","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Compile"},{"key":"Docker image"},{"key":"Lint"},{"key":"Unit tests"},{"key":"Deploy"}]},{"v":"Unit tests","state":"done"}]},{"say":"Done. All 7 vertices are in the order, and every edge points from an earlier vertex to a later one.","ops":[{"v":"Deploy","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}"}
