How to detect useless dependencies?

Question

Assuming that i've got a bunch of dependencies between some tasks :

 A --> B 
 A --> D 
 B --> C  
 C --> D 
 E --> F  
 F --> G

Such that A --> B means that B can only run after A is finished.

How can i be able to detect and remove useless dependencies ?

In this case, it's "A --> D" cause D depends on C which depends on B and B depends on A.

Answer 1

i managed to find an easier solution to implement than the one proposed by stuXnet.

Using Jung library, i check whether there are more than one path available between each pair of a given dependency. If it's the case, then this dependency is certainly needless, so i just have to remove correspondent edge.

Answer 2

Translating this into an adjacency matrix, you would get the following:

  A B C D E F G
A 0 1 0 1 0 0 0
B 0 0 1 0 0 0 0
C 0 0 0 1 0 0 0
D 0 0 0 0 0 0 0
E 0 0 0 0 0 1 0
F 0 0 0 0 0 0 1
G 0 0 0 0 0 0 0

Multiplying this matrix with itself will result in a new matrix, telling you how many different ways there are from each node to each, using two steps. Multiplying it again, you will see the result for three steps, and so on.

Generally speaking, A times k will result in a matrix telling you the amount of different paths from one node to another, taking k steps.

Using this information, you can try to spot dependencies between nodes/tasks described by multiple paths. Between A and D, you will see a path with A^1 (A --> D) and in A^3 (A --> B --> C --> D).

Once these multiple paths from node X to node Y are spotted, you can remove the direct dependency in your original adjacency matrix.