Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you. Yes, Graphviz contains a filter called tred that does the transitive reduction. Now off to understand the math behind it. –  Kip May 18 '10 at 22:08

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.