{"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":"spreadsheet","name":"Spreadsheet formulas","description":"A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"B2","x":41,"y":195},{"id":"C2","x":41,"y":561},{"id":"D2","x":41,"y":884},{"id":"G2","x":41,"y":714},{"id":"G3","x":41,"y":408},{"id":"G4","x":194,"y":195},{"id":"G5","x":347,"y":302},{"id":"B3","x":194,"y":348},{"id":"C3","x":194,"y":654},{"id":"D3","x":194,"y":960},{"id":"B4","x":194,"y":42},{"id":"C4","x":194,"y":501},{"id":"D4","x":194,"y":807},{"id":"B5","x":347,"y":149},{"id":"C5","x":347,"y":455},{"id":"D5","x":347,"y":608},{"id":"B6","x":500,"y":218},{"id":"C6","x":500,"y":371},{"id":"D6","x":500,"y":524},{"id":"B7","x":653,"y":242},{"id":"C7","x":653,"y":395},{"id":"D7","x":653,"y":548},{"id":"E3","x":347,"y":761},{"id":"E7","x":806,"y":418},{"id":"E8","x":959,"y":487}],"edges":[{"from":"B2","to":"B3"},{"from":"G2","to":"B3"},{"from":"C2","to":"C3"},{"from":"G2","to":"C3"},{"from":"D2","to":"D3"},{"from":"G2","to":"D3"},{"from":"B2","to":"B4"},{"from":"G3","to":"B4"},{"from":"C2","to":"C4"},{"from":"G3","to":"C4"},{"from":"D2","to":"D4"},{"from":"G3","to":"D4"},{"from":"B3","to":"B5"},{"from":"B4","to":"B5"},{"from":"G4","to":"B5"},{"from":"C3","to":"C5"},{"from":"C4","to":"C5"},{"from":"G4","to":"C5"},{"from":"D3","to":"D5"},{"from":"D4","to":"D5"},{"from":"G4","to":"D5"},{"from":"B5","to":"B6"},{"from":"G5","to":"B6"},{"from":"C5","to":"C6"},{"from":"G5","to":"C6"},{"from":"D5","to":"D6"},{"from":"G5","to":"D6"},{"from":"B5","to":"B7"},{"from":"B6","to":"B7"},{"from":"C5","to":"C7"},{"from":"C6","to":"C7"},{"from":"D5","to":"D7"},{"from":"D6","to":"D7"},{"from":"B3","to":"E3"},{"from":"C3","to":"E3"},{"from":"D3","to":"E3"},{"from":"B7","to":"E7"},{"from":"C7","to":"E7"},{"from":"D7","to":"E7"},{"from":"E7","to":"E8"},{"from":"E3","to":"E8"}],"durations":{"B2":1,"B3":2,"B4":2,"B5":1,"B6":3,"B7":1,"C2":1,"C3":2,"C4":2,"C5":1,"C6":3,"C7":1,"D2":1,"D3":2,"D4":2,"D5":1,"D6":3,"D7":1,"E3":4,"E7":4,"E8":1,"G2":1,"G3":1,"G4":1,"G5":1},"durationUnit":"milliseconds","details":{"vertices":25,"edges":41,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.06833333333333333,"inDegree":{"min":0,"avg":1.64,"max":3},"outDegree":{"min":0,"avg":1.64,"max":3},"selfLoops":0,"components":1}},"problem":"Which references can a diagram of the sheet leave out, because a longer chain of formulas already connects the same cells?","params":{},"result":{"kind":"edges","edges":[["B2","B3"],["B2","B4"],["B3","B5"],["B3","E3"],["B4","B5"],["B5","B6"],["B6","B7"],["B7","E7"],["C2","C3"],["C2","C4"],["C3","C5"],["C3","E3"],["C4","C5"],["C5","C6"],["C6","C7"],["C7","E7"],["D2","D3"],["D2","D4"],["D3","D5"],["D3","E3"],["D4","D5"],["D5","D6"],["D6","D7"],["D7","E7"],["E3","E8"],["E7","E8"],["G2","B3"],["G2","C3"],["G2","D3"],["G3","B4"],["G3","C4"],["G3","D4"],["G4","B5"],["G4","C5"],["G4","D5"],["G5","B6"],["G5","C6"],["G5","D6"]]},"answer":"The reduction keeps 38 of the 41 edges. It drops B5 to B7, C5 to C7 and D5 to D7.","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 B2, to B3 and B4. Neither target reaches the other, so keep both.","ops":[{"v":"B2","state":"current"},{"e":["B2","B3"],"state":"kept"},{"e":["B2","B4"],"state":"kept"}]},{"say":"Check the 2 edges out of C2, to C3 and C4. Neither target reaches the other, so keep both.","ops":[{"v":"C2","state":"current"},{"v":"B2","state":"done"},{"e":["C2","C3"],"state":"kept"},{"e":["C2","C4"],"state":"kept"}]},{"say":"Check the 2 edges out of D2, to D3 and D4. Neither target reaches the other, so keep both.","ops":[{"v":"D2","state":"current"},{"v":"C2","state":"done"},{"e":["D2","D3"],"state":"kept"},{"e":["D2","D4"],"state":"kept"}]},{"say":"Check the 3 edges out of G2, to B3, C3 and D3. No target reaches another, so keep all 3.","ops":[{"v":"G2","state":"current"},{"v":"D2","state":"done"},{"e":["G2","B3"],"state":"kept"},{"e":["G2","C3"],"state":"kept"},{"e":["G2","D3"],"state":"kept"}]},{"say":"Check the 3 edges out of G3, to B4, C4 and D4. No target reaches another, so keep all 3.","ops":[{"v":"G3","state":"current"},{"v":"G2","state":"done"},{"e":["G3","B4"],"state":"kept"},{"e":["G3","C4"],"state":"kept"},{"e":["G3","D4"],"state":"kept"}]},{"say":"Check the 3 edges out of G4, to B5, C5 and D5. No target reaches another, so keep all 3.","ops":[{"v":"G4","state":"current"},{"v":"G3","state":"done"},{"e":["G4","B5"],"state":"kept"},{"e":["G4","C5"],"state":"kept"},{"e":["G4","D5"],"state":"kept"}]},{"say":"Check the 3 edges out of G5, to B6, C6 and D6. No target reaches another, so keep all 3.","ops":[{"v":"G5","state":"current"},{"v":"G4","state":"done"},{"e":["G5","B6"],"state":"kept"},{"e":["G5","C6"],"state":"kept"},{"e":["G5","D6"],"state":"kept"}]},{"say":"Check the 2 edges out of B3, to B5 and E3. Neither target reaches the other, so keep both.","ops":[{"v":"B3","state":"current"},{"v":"G5","state":"done"},{"e":["B3","B5"],"state":"kept"},{"e":["B3","E3"],"state":"kept"}]},{"say":"Check the 2 edges out of C3, to C5 and E3. Neither target reaches the other, so keep both.","ops":[{"v":"C3","state":"current"},{"v":"B3","state":"done"},{"e":["C3","C5"],"state":"kept"},{"e":["C3","E3"],"state":"kept"}]},{"say":"Check the 2 edges out of D3, to D5 and E3. Neither target reaches the other, so keep both.","ops":[{"v":"D3","state":"current"},{"v":"C3","state":"done"},{"e":["D3","D5"],"state":"kept"},{"e":["D3","E3"],"state":"kept"}]},{"say":"Keep the only edge out of B4, to B5. No other path leaves B4.","ops":[{"v":"B4","state":"current"},{"v":"D3","state":"done"},{"e":["B4","B5"],"state":"kept"}]},{"say":"Keep the only edge out of C4, to C5. No other path leaves C4.","ops":[{"v":"C4","state":"current"},{"v":"B4","state":"done"},{"e":["C4","C5"],"state":"kept"}]},{"say":"Keep the only edge out of D4, to D5. No other path leaves D4.","ops":[{"v":"D4","state":"current"},{"v":"C4","state":"done"},{"e":["D4","D5"],"state":"kept"}]},{"say":"Check the 2 edges out of B5, to B6 and B7.","ops":[{"v":"B5","state":"current"},{"v":"D4","state":"done"}]},{"say":"B5 to B7 is implied by the longer path B5, B6, B7. Drop it.","ops":[{"e":["B5","B7"],"state":"implied"},{"panel":"dropped","list":[{"key":"B5 to B7","note":"via B6"}]},{"v":"B6","state":"path"},{"v":"B7","state":"path"}]},{"say":"Keep the remaining edge out of B5, to B6.","ops":[{"v":"B6","state":"idle"},{"v":"B7","state":"idle"},{"e":["B5","B6"],"state":"kept"}]},{"say":"Check the 2 edges out of C5, to C6 and C7.","ops":[{"v":"C5","state":"current"},{"v":"B5","state":"done"}]},{"say":"C5 to C7 is implied by the longer path C5, C6, C7. Drop it.","ops":[{"e":["C5","C7"],"state":"implied"},{"panel":"dropped","list":[{"key":"B5 to B7","note":"via B6"},{"key":"C5 to C7","note":"via C6"}]},{"v":"C6","state":"path"},{"v":"C7","state":"path"}]},{"say":"Keep the remaining edge out of C5, to C6.","ops":[{"v":"C6","state":"idle"},{"v":"C7","state":"idle"},{"e":["C5","C6"],"state":"kept"}]},{"say":"Check the 2 edges out of D5, to D6 and D7.","ops":[{"v":"D5","state":"current"},{"v":"C5","state":"done"}]},{"say":"D5 to D7 is implied by the longer path D5, D6, D7. Drop it.","ops":[{"e":["D5","D7"],"state":"implied"},{"panel":"dropped","list":[{"key":"B5 to B7","note":"via B6"},{"key":"C5 to C7","note":"via C6"},{"key":"D5 to D7","note":"via D6"}]},{"v":"D6","state":"path"},{"v":"D7","state":"path"}]},{"say":"Keep the remaining edge out of D5, to D6.","ops":[{"v":"D6","state":"idle"},{"v":"D7","state":"idle"},{"e":["D5","D6"],"state":"kept"}]},{"say":"Keep the only edge out of B6, to B7. No other path leaves B6.","ops":[{"v":"B6","state":"current"},{"v":"D5","state":"done"},{"e":["B6","B7"],"state":"kept"}]},{"say":"Keep the only edge out of C6, to C7. No other path leaves C6.","ops":[{"v":"C6","state":"current"},{"v":"B6","state":"done"},{"e":["C6","C7"],"state":"kept"}]},{"say":"Keep the only edge out of D6, to D7. No other path leaves D6.","ops":[{"v":"D6","state":"current"},{"v":"C6","state":"done"},{"e":["D6","D7"],"state":"kept"}]},{"say":"Keep the only edge out of B7, to E7. No other path leaves B7.","ops":[{"v":"B7","state":"current"},{"v":"D6","state":"done"},{"e":["B7","E7"],"state":"kept"}]},{"say":"Keep the only edge out of C7, to E7. No other path leaves C7.","ops":[{"v":"C7","state":"current"},{"v":"B7","state":"done"},{"e":["C7","E7"],"state":"kept"}]},{"say":"Keep the only edge out of D7, to E7. No other path leaves D7.","ops":[{"v":"D7","state":"current"},{"v":"C7","state":"done"},{"e":["D7","E7"],"state":"kept"}]},{"say":"Keep the only edge out of E3, to E8. No other path leaves E3.","ops":[{"v":"E3","state":"current"},{"v":"D7","state":"done"},{"e":["E3","E8"],"state":"kept"}]},{"say":"Keep the only edge out of E7, to E8. No other path leaves E7.","ops":[{"v":"E7","state":"current"},{"v":"E3","state":"done"},{"e":["E7","E8"],"state":"kept"}]},{"say":"Done. E8 has no outgoing edges. The reduction keeps 38 of the 41 edges and drops 3 implied edges. Every vertex still reaches the same vertices.","ops":[{"v":"E8","state":"done"},{"v":"E7","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}"}
