Tree type algorithm to show project dependencies

Posted on 2006-06-02
Last Modified: 2013-12-03
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:

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!


Question by:Virge57

    Author Comment

    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
    LVL 48

    Assisted Solution

    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.

    Author Comment

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

    Expert Comment

    Binary tree node has maximum two childs. Generally, number of tree childs is not restricted.
    LVL 18

    Accepted Solution


    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.

    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
      while Dependents[j] not = 0 and not stop
         if P[j]=2 print "Project ", i
         end if
      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,
    LVL 48

    Expert Comment

    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:
    |   |--D
    LVL 2

    Assisted Solution

    I hope the following code will help you generating the tree.......
    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)
                      string Connectionstring="YOUR CONNECTION STRING";
                      //Connecting to DB
                            cnn.ConnectionTimeout = 25;
                            cnn.Open(Connectionstring, null,null,0);                  
                            MessageBox.Show("Connection Failed!", this.Text, MessageBoxButtons.OK, MessageBoxIcon.Warning);

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


                      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)
                      Recordset rs = new Recordset();      
                      rs.Open   ( "SELECT childs from your table WHERE parent =" + parentnodetext + "'" ,cnn,
                                        ADODB.CursorTypeEnum.adOpenStatic ,ADODB.LockTypeEnum.adLockReadOnly ,0);

                      while(!rs.EOF )
                            label1.Text =trackCNT.ToString();
                            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);


    good luck,

    Author Comment

    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!

    Author Comment

    Thanks for the responses.  I used some of the ideas here, I really like the algorithm from JoseParrot.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Highfive Gives IT Their Time Back

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    This is an explanation of a simple data model to help parse a JSON feed
    Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
    In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    737 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    20 Experts available now in Live!

    Get 1:1 Help Now