1

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.

Jack Kass
  • 55
  • 9
  • If you are using Maven as a build system see here: [is-there-a-simple-way-to-remove-unused-dependencies-from-a-maven-pom-xml][1] [1]: http://stackoverflow.com/questions/1517611/is-there-a-simple-way-to-remove-unused-dependencies-from-a-maven-pom-xml – Simone Rondelli Apr 23 '14 at 13:19
  • Using an adjacency matrix, you can find all paths from one node/dependency to another. Just an assumption: if there is more than one path, all but the longest one are 'useless'. – stuXnet Apr 23 '14 at 13:22
  • @Simone Rondelli, i'm not using Maven. – Jack Kass Apr 23 '14 at 13:25
  • But is it really useless? A can't do without B because of two different reasons: first, because A needs D (A --> D), second, because A needs B, which needs C, which needs D (A --> B --> C --> D) When you remove the information about the dependency of A on D, your dependencies would be incorrect if A doesn't need B any more. – stuXnet Apr 23 '14 at 13:26
  • I think what he means is that `A --> D` is redundant because `A --> B --> C --> D` already says it... but what I don't understand is how is this question related to Java. – Erik Kaplun Apr 23 '14 at 13:38
  • @stuXnet, Sorry i edited my question: A --> B means in fact that B runs after A is finished – Jack Kass Apr 23 '14 at 13:39
  • @Erik Allik, yes, you are right. I've got to develop that using java – Jack Kass Apr 23 '14 at 13:42
  • Being forced to develop something in Java is a sad thing to start with so I'm totally sympathetic with you on that one ;) but I still don't see how this *question* is related to Java. – Erik Kaplun Apr 23 '14 at 13:45
  • @user3556895 try to look at your example from the other end: task D needs two tasks finished before being able to run: task A and task C. If you are generating this shortened list of dependencies and removing 'useless' dependencies, you would lose the information that D has to run after A. If now task B would be changed and looses it's dependency on A, D would possibly fail. – stuXnet Apr 23 '14 at 13:47
  • @stuXnet, you are right. In the case of B is not dependant on A, the dependency A --> D is no more useless/redundant. That's the point of my question, how can i be able to analyse all those dependencies and find if there are any "useless" dependencies ? – Jack Kass Apr 23 '14 at 14:00
  • @Erik Allik, I edited the title :) – Jack Kass Apr 23 '14 at 14:04
  • @user3556895 I still can't see the point in removing this information, but I hope my answer is helpful anyway :) If can't write this as Java code, just say so, I could do so later. – stuXnet Apr 23 '14 at 14:09
  • @user3556895: I meant the java tag, but anyway; not important. – Erik Kaplun Apr 23 '14 at 14:10
  • @stuXnet, yes that would very helpful if you have some time, thank you very much :) – Jack Kass Apr 23 '14 at 14:20

2 Answers2

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.

stuXnet
  • 4,309
  • 3
  • 22
  • 31
0

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.

Jack Kass
  • 55
  • 9