I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a quick algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph. For example:A -> B -> CA -> Cin words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).Its been a while since I studied algorithms, and I'm not sure where to start.By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.thanks in advance!
Reducing redundant edges from a dependency graph
ds.algorithms;graph algorithms;transitive reduction
The Transitive Reduction of a Directed GraphA. V. Aho, M. R. Garey, and J. D. UllmanAccording to wikipedia, this algorithm is used by tred which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph. This question is duplicate of this stackoverflow question.code here graphviz/tools/src/tred.c does use DFS. ;-)