How to process dependencies between tasks considering multiple constraints?

Question

I'm working on a Java program that take an input file containing a bunch of depencencies between tasks like this :

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

"C --> D" means that task D can only start after C is finished but doesn't necessarily mean that D comes right after C. Tasks can also run in parallel if they are independent from each others (A & E for instance).

The program should process all those depencencies and generate an output dependency list considering the following constraints :

• Find all the sources (A & E in this case) and order the dependencies begining from the sources :

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

• Remove all the useless dependencies (in this case : A --> D)

• At the end, add a "Start" task as a root for all the dependecies by adding dependencies between "Start" and the sources. The generated output list should look like this :

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

Then i've got to display a rooted tree graph from the dependency list above using a specialised library like "Jung".

Any ideas on how to process all those contraints ?

Thank you in advance for your help.

Answer 1

Finding the sources is trivial; just ask each vertex whether it has any incoming edges.

For the rest, basically you want to extract a spanning tree from the graph; there are several algorithms out there for doing this.

Answer 2

Most of it will be logic, so if a letter like A doesnt appear in the second row then it is one of the starting letters then find the staring letter (in this case A) from the first row and the letter it goes to in the second row and so on until you get to a letter like D which doesnt appear in the first row and you will have one of the chains. Then repeat this for all the starting letters as stated above.