A solution to cyclic references in a planning tree

I have recently found myself working on a basic planning use case involving tasks and predecessors. One of the hardest things of working in such a requirement is the fact that a particular change on one single task node may affect the rest of the tree (parents and successors) if their relationship is defined in a particular way. The following example explains what I am talking about under the restriction of a nine-to-five calendar, monday through friday calendar:

Indx Name            Predecessors    Effort    StartDate    EndDate     Resource
0    - PlanningRoot                  24h       12/04/2010   14/04/2010
1      - Node1                       20h       12/04/2010   14/04/2010
2        - Task1                     12h       12/04/2010   13/04/2010  Resource1
3        - Task2     [2]             8h        13/04/2010   14/04/2010  Resource1
4      - Node2       [1]             4h        14/04/2010   14/04/2010
5        - Node21                    4h        14/04/2010   14/04/2010
6          - Task3                   4h        14/04/2010   14/04/2010  Resource2

Figure 1. A simple plan.

As you can see from Figure 1, this is a two-day plan with three specific tasks assigned to resources 1 and 2. The important thing to note here is that, by the way predecessors are defined, a subtle modification such as increasing the estimated effort on Task1 may cause a chain of modifications that will end up on the whole schedule being delayed. Not that there is anything wong with delays, it’s just that this type of consistency is a little bit hard to achieve considering the many variables participating here, including:

  • The project’s default calendar.
  • The resource’s calendar.
  • Each task’s effort and start date.
  • Each task’s predecessors.
  • The resource assigned to each task. This is important because the resource imposes its calendar as a restriction to the task. For example, if the resource works tuesdays and wednesdays only, the task’s duration will be longer.
  • The percentage of assignation of the resource to the specified task.
  • Other variables I haven’t thought of yet :p.

Now, if you have a schedule with completely isolated tasks (with no predecessors defined), the job gets to be easier. But life is tough and predecessors are a reality, so you have to accept them and move on. Seriously, I don’t consider predecessors one of my favorite friends, but they sure make the life of project managers easy. The thing with predecessors is that they impose really hard restrictions on the date a particular task is started. Besides, a task can have multiple predecessors. This means that all predecessor tasks must be finished by the time this task is supposed to start. And the task must not start months or years after de last predecessor was finished, but it must try to start as soon as it can.

The algorithm used to deal with all of these problems is quite demanding and I will probably write about it in later posts. For this post, I will focus on a more punctual problem related to predecessors and the detection of cycles between them. A cyclic relationship is not desirable when processing planning nodes since it can lead to the good old StackOverflowException leaving our application useless. I had to dedicate a long part of my time just to analyze the many different types of cyclic relationships that can happen. The following figures illustrate some of them:

Indx Name            Predecessors
0    - PlanningRoot
1        - Task1     [1]

Figure 2. Self cyclic relationship.

Indx Name            Predecessors
0    - PlanningRoot
1        - Task1     [2]
2        - Task2     [1]

Figure 3. Direct cyclic relationship.

Indx Name            Predecessors
0    - PlanningRoot
1        - Task1     [3]
2        - Task2     [1]
3        - Task2     [2]

Figure 4. Successor-of-successor cyclic relationship.

Indx Name            Predecessors
0    - PlanningRoot
1        - Node1
2          - Task1 [3]
3        - Node2
4          - Task2 [1]

Figure 5. Parent-of-successor cyclic relationship.

I can go on infinitely showing you how many types of cyclic relationships exist and how many combinations of them can exist. So I rather show you the rules I came up with in order to avoid these types of relationships:

  1. A node cannot have itself as predecessor.
  2. A node cannot have a child, child-of-child, etc. as its predecessor.
  3. A node cannot have a parent, parent-of-parent, etc. as its predecessor.
  4. A predecessor node cannot be a successor, successor-of-successor, etc.
  5. A predecessor cannot be a child, child-of-child, etc. of a successor, successor-of-successor, etc.
  6. A predecessor cannot be the parent, parent-of-parent, etc. of a successor, successor-of-successor, etc.
  7. A predecessor cannot be the successor, successor-of-successor, etc. from a child, child-of-child, etc. of a successor, successor-of-successor, etc. This is sort of a combination of (4) and (5).
  8. A predecessor cannot be the successor, successor-of-successor, etc. from a parent, parent-of-parent, etc. of a successor, successor-of-successor, etc. Combination of (3) and (5).

So that’s it. Simple huh? Well, I cannot say it did not demand much time from me. But finally, I got to where I needed to be. Once the rules are defined, the rest is just hard work. The following figures show a reduced version of the solution I designed to solve the cyclic reference problem.

public class ScheduleNode {
  private List<ScheduleNode> predecessors;
  private List<ScheduleNode> successors;
  public getPredecessors() {
    if (successors == null) {
      predecessors = new ArrayList<ScheduleNode>();
    }
    return predecessors;
  }
  public getSuccessors() {
    if (successors == null) {
      successors = new ArrayList<ScheduleNode>();
    }
    return successors;
  }
}

Figure 6. ScheduleNode class representing the schedule tree model.

public class ScheduleUtil {
  public static void predsValid(final ScheduleNode node) {
    if (node.getPredecessors().size() == 0) {
      return;
    }
    for (ScheduleNode pred : node.getPredecessors()) {
      if (isSelf(node, pred)) {
        // Handle cyclic ref.
      }
      if (isChild(node, pred)) {
        // Handle cyclic ref.
      }
      if (isParent(node, pred)) {
        // Handle cyclic ref.
      }
      if (isSuccessor(node, pred)) {
        // Handle cyclic ref.
      }
    }
  }
}

Figure 7. Main algorithm to avoid cyclic references among nodes.

As you can see, the solution is fairly simple and it covers all of the scenarios described previously. Additionally, you can check out the almost-full source code here. Tell me what you think of it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s