# Tree type algorithm to show project dependencies

We have an application that allows project managers to list any other project that they are
dependent on.  Each time they enter a new dependency a new record is created in our database.

Below is a table that shows how these records are stored:

Predecessor (delivering) Project      Successor (Dependent) Project
--------------------------------            --------------------------------
Project 47                                    Project 69
Project 47                     Project 78
Project 47                                    Project 355
Project 47                     Project 408

Project 355                                   Project 229
Project 355               Project 78
Project 355               Project 408

Project 408               Project 355

In the table above, Project 47 has 4 dependent projects, project 355 has 3 dependent projects and project 408 has 1 depedent project.

What I want to do is create an algorithm that takes a predecessor project, traverses through a table (like the one above) a makes a makes a tree type view of all the Successor projects..

For example, if I choose to start at Project 47, I would find all of project 47's Successors, which are 69,78,355,408, and then the successors of those projects, etc.  In the end, I would have a created a tree like the one pictures in this link:http://www.alexalapatt.com/myspace/Drawing1.jpg

I've been trying to do this in arrays but it is getting ugly.  Does anyone know an algorithm that I can use to store this data in this fashion?  I would do this by hand, but there are thousands of records like this to go through!

Thanks!!

Alex
###### Who is Participating?

Graphics ExpertCommented:
Hi,

Seems not to be a tree.
Trees have n nodes and n-1 edges.
Actual projects have tasks that are dependent on more than just one predecessor and each task can be predecessor of more than one dependent task. The same applies to interdependent projects. So, there are n nodes and much more than n-1 edges. That are general directed graphs. Can be a tree, of course, but this would be a special case.

General graphs are defined by an adjacent matrix (of dependencies) or by adjacent lists. That approach allow multi-dependency to be represented. If the dependencies have the same value, on put 0 or 1 in each matrix cell.

Example:
Suppose a n by n matrix with columns 1, 2,...,n  and rows 1,2,...,n.
It is an array P[n][n].
If n=5 and row 3 is 1,0,0,1,1 then project 3 is sucessor of projects 1, 4 and 5.
If column 2 is 0,0,1,0,1 then projects 2 is predecessor of projects 3 and 5.

Disadvantage of matrix is the large space it wastes. If you have 1000 projects, will spend 1 million cells to store data. And, worst, only half of the matrix is actually needed, because the non-redundant data is a triangular matrix (a right triangle with sides = n  and the hypotenuse is the diagonal of such matrix). As you are storing just 0 or 1, you need 1MB by chosing the cell to be a char (or byte) or bool. Not so much.

To use less memory, you can chose the adjacent list, a little bit more difficult to maintain.
Example of adjacent list (for n=5) is:
1: 2,4,0
2: 3,4,5,0
3: 0
4: 3,5,0
5: 3,4,0
That means: Project 1 is predecessor of projects 2 and 4; Project 2 is predecessor of projects 3, 4 and 5. The zero is the list row terminator.
To query which projects Project 2 depends on, we must search for 2 in each row.
Actually the above data is stored this way:
Dependents = {2,4,0,3,4,5,0,0,3,5,0,3,4,0}
Predecessors = {1, 4, 9, 10, 12}
It spends 14 + 5 = 19 cells. A matriz would spend 25 cells to store the same information. Is that economy a real economy? Must examine your case to decide.

By using adjacent list, we have the below algorithm:
print "Project 2 depends on"
for i=1,n
j=Predecessors[i]
stop=false
while Dependents[j] not = 0 and not stop
if P[j]=2 print "Project ", i
stop=true
end if
j=j+1
end while
end for

The above will print the list of direct predecessors of project 2. By using it recursively for each found predecessor, we have the complete dependency tree.

If I am understanding correctly the question, this solves the core algorithm. The graphical output is another question...

Hope it helps,
Jose
0

Author Commented:
That table didn't post nicely so I'm reposting it.

Predecessor (delivering) Project      Successor (Dependent) Project
--------------------------------            --------------------------------
Project 47                                    Project 69
Project 47                                    Project 78
Project 47                                    Project 355
Project 47                                    Project 408

Project 355                                  Project 229
Project 355                                  Project 78
Project 355                                  Project 408

Project 408                                  Project 355
0

Commented:
Data structure which matches this task is tree (not surprisingly). Tree structure can be defined in C++ as pointer to root and node class:
class Node
{
...
Node* childs;   // array of child nodes

// data (in your case - project name or key)
};

However, the most simple way to build the tree is writing directly to tree control. I don't know what language do you use, but I hope you have tree control in it.
0

Author Commented:
I thought a tree can only have two nodes?  I have an algorithm book at home, I'm going to check it out.
0

Commented:
Binary tree node has maximum two childs. Generally, number of tree childs is not restricted.
0

Commented:
Right, but to simplify this task we can allow the same project to appear number of times in the tree. For example, if dependency is:
A -> B
A -> C
B -> D
C -> D

This is graph, but A depedency tree can be shown as:
A
|--B
|   |--D
|
|--C
|--D
0

Commented:
The code written in C#

private const String cChildColumn = "Successor (Dependent) Project";

Connection cnn = new Connection();
int looptrack=0;
Int64 trackCNT=0;

private void frmTree_Load(object sender, System.EventArgs e)
{

//Connecting to DB
try
{
cnn.ConnectionTimeout = 25;
cnn.Open(Connectionstring, null,null,0);
}
catch
{
MessageBox.Show("Connection Failed!", this.Text, MessageBoxButtons.OK, MessageBoxIcon.Warning);
Application.Exit();
}

tvMain.Nodes.Clear(); //tvMain is the main tree view control on the form

trackCNT=0;
looptrack=0;

TreeNode rootNode = new TreeNode();
rootNode.Text ="ROOT";
rootNode.Tag=      "ROOT";

//Making the Full Tree
MakeTree ("1",rootNode);

//Now adding the Tree to TreeView Control

}

private void MakeTree(string parentnodetext,TreeNode parentNode)
{
looptrack++;
Recordset rs = new Recordset();
rs.Open   ( "SELECT childs from your table WHERE parent =" + parentnodetext + "'" ,cnn,

while(!rs.EOF )
{
trackCNT++;
label1.Text =trackCNT.ToString();
label1.Refresh();

TreeNode aNode = new TreeNode();
aNode.Tag = rs.Fields[cChildColumn].Value.ToString();
aNode.Text = rs.Fields[cChildColumn].Value.ToString();

MakeTree (rs.Fields[cChildColumn].Value.ToString(),aNode);

rs.MoveNext();
}
rs.Close();

}

good luck,

0

Author Commented:
Thanks, I'm going to give this a try today.  Unfortunatly, I most likely have to write this in VBA.  The algorithm books I read this weekend didn't cover VBA which really stinks!
0

Author Commented:
Thanks for the responses.  I used some of the ideas here, I really like the algorithm from JoseParrot.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.