1
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you. Yes, Graphviz contains a filter called tred that does the transitive reduction. Now off to understand the math behind it. $\endgroup$
    – Kip
    May 18, 2010 at 22:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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