Remove unnecessary dependencies in a task graph? - MathOverflow

Remove unnecessary dependencies in a task graph?

2010-05-18T21:12:02Z

I'm modeling a game tech/build tree as a directed acyclic graph with a .dot file for visualization use in Graphviz.

Some of the dependencies discovered are redundant in the sense that while they are dependencies, they are satisfied via a longer yet required path.

a -> b 
b -> c
a -> c // Unnecessary because we have to do b first.

And a longer example

a -> b
b -> c
c -> d
a -> d // Unnecessary between we have to do both b and c first.

Is there an algorithm to testing a graph for these unnecessary paths so that I could trim them from the .dot file? Perhaps this is more appropriately a programming question, but I'm guessing some use of graph theory applies here.

Answer by mathy for Remove unnecessary dependencies in a task graph?

2010-05-18T21:35:45Z

AFAICT, what you want is called a transitive reduction of the graph. La Wik claims that Graphviz can do the job somehow; consult its documentation.

Answer by Lucas K. for Remove unnecessary dependencies in a task graph?

2010-05-18T22:26:40Z

For each vertex x, make a set that contain each vertex y that can reach x. This sets also includes x.

If you have two edges b -> a and c -> a, then if the set associated with b is a subset of the set associated with c, then the edge b -> a can be removed.

Example:

a -> b
b -> c
a -> c

The set are:
a: { a }
b: { a, b } // Can be reached from a and b
c: { a, b, c}

If you look at the edges:
b -> c
a -> c

Then you see that the set of a is a subset of b. So, the edge a -> c can be removed.

Lucas