{"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":"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":"Which prerequisites can the course list leave out, because they already come through another course?","params":{},"result":{"kind":"edges","edges":[["Algorithms","Compilers"],["Algorithms","Machine learning"],["Calculus 1","Calculus 2"],["Calculus 1","Linear algebra"],["Calculus 2","Probability"],["Computer systems","Compilers"],["Computer systems","Operating systems"],["Data structures","Algorithms"],["Data structures","Databases"],["Data structures","Operating systems"],["Discrete math","Data structures"],["Discrete math","Probability"],["Linear algebra","Machine learning"],["Probability","Machine learning"],["Programming 1","Programming 2"],["Programming 2","Computer systems"],["Programming 2","Data structures"]]},"answer":"The reduction keeps 17 of the 18 edges. It drops Discrete math to Algorithms.","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":"Keep the only edge out of Programming 1, to Programming 2. No other path leaves Programming 1.","ops":[{"v":"Programming 1","state":"current"},{"e":["Programming 1","Programming 2"],"state":"kept"}]},{"say":"Check the 3 edges out of Discrete math, to Data structures, Probability and Algorithms.","ops":[{"v":"Discrete math","state":"current"},{"v":"Programming 1","state":"done"}]},{"say":"Discrete math to Algorithms is implied by the longer path Discrete math, Data structures, Algorithms. Drop it.","ops":[{"e":["Discrete math","Algorithms"],"state":"implied"},{"panel":"dropped","list":[{"key":"Discrete math to Algorithms","note":"via Data structures"}]},{"v":"Data structures","state":"path"},{"v":"Algorithms","state":"path"}]},{"say":"Keep the 2 remaining edges out of Discrete math, to Data structures and Probability.","ops":[{"v":"Data structures","state":"idle"},{"v":"Algorithms","state":"idle"},{"e":["Discrete math","Data structures"],"state":"kept"},{"e":["Discrete math","Probability"],"state":"kept"}]},{"say":"Check the 2 edges out of Calculus 1, to Calculus 2 and Linear algebra. Neither target reaches the other, so keep both.","ops":[{"v":"Calculus 1","state":"current"},{"v":"Discrete math","state":"done"},{"e":["Calculus 1","Calculus 2"],"state":"kept"},{"e":["Calculus 1","Linear algebra"],"state":"kept"}]},{"say":"Check the 2 edges out of Programming 2, to Computer systems and Data structures. Neither target reaches the other, so keep both.","ops":[{"v":"Programming 2","state":"current"},{"v":"Calculus 1","state":"done"},{"e":["Programming 2","Computer systems"],"state":"kept"},{"e":["Programming 2","Data structures"],"state":"kept"}]},{"say":"Keep the only edge out of Calculus 2, to Probability. No other path leaves Calculus 2.","ops":[{"v":"Calculus 2","state":"current"},{"v":"Programming 2","state":"done"},{"e":["Calculus 2","Probability"],"state":"kept"}]},{"say":"Keep the only edge out of Linear algebra, to Machine learning. No other path leaves Linear algebra.","ops":[{"v":"Linear algebra","state":"current"},{"v":"Calculus 2","state":"done"},{"e":["Linear algebra","Machine learning"],"state":"kept"}]},{"say":"Check the 2 edges out of Computer systems, to Operating systems and Compilers. Neither target reaches the other, so keep both.","ops":[{"v":"Computer systems","state":"current"},{"v":"Linear algebra","state":"done"},{"e":["Computer systems","Operating systems"],"state":"kept"},{"e":["Computer systems","Compilers"],"state":"kept"}]},{"say":"Check the 3 edges out of Data structures, to Operating systems, Databases and Algorithms. No target reaches another, so keep all 3.","ops":[{"v":"Data structures","state":"current"},{"v":"Computer systems","state":"done"},{"e":["Data structures","Operating systems"],"state":"kept"},{"e":["Data structures","Databases"],"state":"kept"},{"e":["Data structures","Algorithms"],"state":"kept"}]},{"say":"Keep the only edge out of Probability, to Machine learning. No other path leaves Probability.","ops":[{"v":"Probability","state":"current"},{"v":"Data structures","state":"done"},{"e":["Probability","Machine learning"],"state":"kept"}]},{"say":"Check the 2 edges out of Algorithms, to Compilers and Machine learning. Neither target reaches the other, so keep both.","ops":[{"v":"Algorithms","state":"current"},{"v":"Probability","state":"done"},{"e":["Algorithms","Compilers"],"state":"kept"},{"e":["Algorithms","Machine learning"],"state":"kept"}]},{"say":"Done. The 4 vertices with no outgoing edges have nothing to check. The reduction keeps 17 of the 18 edges and drops 1 implied edge. Every vertex still reaches the same vertices.","ops":[{"v":"Operating systems","state":"done"},{"v":"Databases","state":"done"},{"v":"Compilers","state":"done"},{"v":"Machine learning","state":"done"},{"v":"Algorithms","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}"}
