{"algorithm":"transitive-reduction","about":["The transitive reduction keeps the fewest edges that still let every vertex reach the same vertices. An edge from A to C goes when there is already a longer path from A to C, such as A to B to C, since the path says the same thing. In a graph without cycles, only one graph fits that description.","path.TransitiveReduction takes each vertex's direct neighbors and drops any neighbor that another of those neighbors can already reach. The edges to the neighbors that are left are the ones the graph needs. It caches the vertices each neighbor reaches, so the work is O(V(V+E)) at most.","It returns a new graph with the weights of the edges it keeps, and leaves the input as it was. It returns an error for an undirected graph or one with a cycle. Use it to draw a dependency graph without the clutter of implied edges, or to see which requirements are direct."],"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":"Which waits between jobs can the pipeline drop, because a longer chain of jobs already forces the same order?","params":{},"result":{"kind":"edges","edges":[["Checkout","Install"],["Compile","Docker image"],["Compile","Unit tests"],["Docker image","Deploy"],["Install","Compile"],["Install","Lint"],["Lint","Deploy"],["Unit tests","Deploy"]]},"answer":"The reduction keeps 8 of the 9 edges. It drops Checkout to Docker image.","legend":{"vertex":[{"id":"idle","label":"Not checked yet","color":"#64748B","shape":"hollow"},{"id":"current","label":"Being checked","color":"#56B4E9","shape":"ring"},{"id":"path","label":"On the longer path","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"Checked","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Not checked yet","color":"#475569","shape":"line"},{"id":"kept","label":"Kept","color":"#009E73","shape":"thick"},{"id":"implied","label":"Implied by a longer path, dropped","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"dropped","title":"Dropped edges","kind":"list"}]},"steps":[{"say":"Check the edges out of each vertex in turn. An edge is implied when a longer path already leads from its start to its end, so the reduction drops it."},{"say":"Check the 2 edges out of Checkout, to Install and Docker image.","ops":[{"v":"Checkout","state":"current"}]},{"say":"Checkout to Docker image is implied by the longer path Checkout, Install, Compile, Docker image. Drop it.","ops":[{"e":["Checkout","Docker image"],"state":"implied"},{"panel":"dropped","list":[{"key":"Checkout to Docker image","note":"via Install and Compile"}]},{"v":"Install","state":"path"},{"v":"Compile","state":"path"},{"v":"Docker image","state":"path"}]},{"say":"Keep the remaining edge out of Checkout, to Install.","ops":[{"v":"Install","state":"idle"},{"v":"Compile","state":"idle"},{"v":"Docker image","state":"idle"},{"e":["Checkout","Install"],"state":"kept"}]},{"say":"Check the 2 edges out of Install, to Lint and Compile. Neither target reaches the other, so keep both.","ops":[{"v":"Install","state":"current"},{"v":"Checkout","state":"done"},{"e":["Install","Lint"],"state":"kept"},{"e":["Install","Compile"],"state":"kept"}]},{"say":"Keep the only edge out of Lint, to Deploy. No other path leaves Lint.","ops":[{"v":"Lint","state":"current"},{"v":"Install","state":"done"},{"e":["Lint","Deploy"],"state":"kept"}]},{"say":"Check the 2 edges out of Compile, to Unit tests and Docker image. Neither target reaches the other, so keep both.","ops":[{"v":"Compile","state":"current"},{"v":"Lint","state":"done"},{"e":["Compile","Unit tests"],"state":"kept"},{"e":["Compile","Docker image"],"state":"kept"}]},{"say":"Keep the only edge out of Unit tests, to Deploy. No other path leaves Unit tests.","ops":[{"v":"Unit tests","state":"current"},{"v":"Compile","state":"done"},{"e":["Unit tests","Deploy"],"state":"kept"}]},{"say":"Keep the only edge out of Docker image, to Deploy. No other path leaves Docker image.","ops":[{"v":"Docker image","state":"current"},{"v":"Unit tests","state":"done"},{"e":["Docker image","Deploy"],"state":"kept"}]},{"say":"Done. Deploy has no outgoing edges. The reduction keeps 8 of the 9 edges and drops 1 implied edge. Every vertex still reaches the same vertices.","ops":[{"v":"Deploy","state":"done"},{"v":"Docker image","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":"reduced, err := path.TransitiveReduction(g)\nif err != nil {\n\treturn err\n}\nfor _, e := range reduced.AllEdges() {\n\tfmt.Println(e.Source().Label(), \"->\", e.Destination().Label())\n}"}
