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.
A -> B -> C
A -> C
in 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!