8

My problem is very simple but I don't really know its name and therefore, it's hard to find a solution by myself : How to simplify a dependency graph like (where -> means depends):

A -> B -> C & A -> C

to 

A -> B -> C
superM
  • 8,605
  • 8
  • 42
  • 51
Maxime
  • 1,776
  • 1
  • 16
  • 29
  • Those are different graphs. A depends on C and B "A->B->C" isn't a "simplification" – Peter Ritchie May 16 '12 at 13:08
  • The first graph is : D(A) = {B, C}, D(B) = {C}, D(C) = {}, so in this case, the graph D(A) = {B}, D(B) = {C}, D(C) = {} is equivalent because C must be done before B anyway. – Maxime May 16 '12 at 13:14
  • 1
    @Peter the dependencies are transitive, I think, which is why for the questioners purposes they are the same. – Paul Phillips May 16 '12 at 13:17

1 Answers1

8

You are looking for transitive reduction.

For a discussion of algorithms, see Transitive Closure and Reduction.

NPE
  • 486,780
  • 108
  • 951
  • 1,012