Critical Paths

Keep it simple, as long as it still works. This should be the main guiding motto of everyone in the world. If you need to solve a problem that looks complicated, think of a method to simplify it, and resolve it with some simple and easy algorithm that everyone may comprehend if necessary. Thankfully, the critical path determination technique is based on this simple idea.

For those of you who periodically check back for another article about graphs, welcome back. This is the tenth part of a 13-part series. As I promised last week, the topic for today will be critical paths. For the others who just arrived here, on this specific technique let me state that this article is part of my article series related to the domain of graphs.

In order to understand the article you will absolutely need to have a general concept of graphs, and you should have read my article about the Shortest Path Algorithms in Graphs. More specifically, you will need to understand the algorithm based on topological order.

The problem itself is probably harder to understand than to see through its solution. Therefore, in the first section of the article I am going to focus on presenting the issue. Most importantly, we’ll see how we can simplify it by translating it to a graph. After we are done with this, I shall continue with the strategy we will apply to solve it.

Finally, I will present all this implemented in the C language (and some minimal usage of the C++ language for the presence of references), and show you how we can print out the solution from the data generated in the step before. Let us get on with it!

{mospagebreak title=The problem and translating it} 

Assume that we have a construction company. Constructing a building, for instance, is a job composed of multiple sub-jobs. Therefore, when the company gets an assignment to create a building, the head of the company will first break down the main job into multiple sub-jobs in order to simplify the process, and to better monitor the building’s progress. 

Considering his experience, he will probably make an estimate of how long each of the sub-jobs should take and sign the contract accordingly. The question is that, given the time requirement for each individual sub-job, what is the shortest time within which the building can be completed?

We need to consider that some of the jobs should only be done after we complete a set of previous jobs. For example, we cannot start painting the wall until we put the walls up in the first place. Additionally, what are the sub-assignments that cannot be delayed and need to be completed in time so we do not face penalties for delay of the main project?

Some sub-jobs can be completed within a given time interval, while a few must be completed exactly one after the other, otherwise the whole project would be delayed. These are the critical jobs for which the construction company will have to take extra care. 

Now we will translate all this into a graph problem. Let the edges represent the jobs, and the weight of the edges will be the time required to complete the task. These will build a graph having a single source vertex (edges only going out from it) representing the start point of the work, and a single drain (terminal) vertex representing the end point of the work.

We will arrange the other edges that the graph will represent as the connections between the jobs. If a job can only be done after another is completed, then that task will follow from the vertex where the previously-required job ended. Thus, a job can only be done if all of its incoming edge representing jobs are complete.

The solution of the whole is the longest road from the source vertex and the drain (terminal) vertex. Following this way of thinking, we will also find the road through which the longest road goes. The edges that build this will be those that are the critical ones. Increasing the length of any of these edges (i.e. increasing the sub-job time required to complete it) will also increase the overall time needed to complete the building.

As for the other jobs, these will all have an earliest time to start when their critical edges related to the starting vertex are complete, and a final time when they must be started in order to finish them by the time that the end node of the edge “enters” a critical node. For the critical jobs, the earliest time to start the job and the latest time to do this are the same of course. As for the others, we can start them any time between these intervals.

{mospagebreak title=The solution}

It is important to note that here we have no circles in the graph. Considering this, we can apply with a little modification the algorithm we used to calculate the shortest road inside a graph with no circle inside it. Yes, you are right; it is the topological order-based technique.

Here it is a graph drawn so that you can see and understand this better:

–>Image Courtesy of Kátai Zoltán- Introduction to Graphs<–

Practically, we are going to invert the topological order shortest-path algorithm and query for the longest road. You remember that the topological sort allowed us to order the vertexes in a way that all of the edges were directed from the left to the right.

This way we could just follow with the edges in this order, to perform an approximation with each edge. We start from the root vertex of course. If we follow this principle, by the time we arrive at a vertex, we’ve already performed approximations through all of its incoming edges, and now we will have the shortest road from the root to this vertex.

This is possible because the shortest path’s sub-road is also the shortest road. So now, we will invert the statement, and instead of searching for the minimal distance between the source and the outgoing edges of a vertex, we will search for the maximum distance. From this, we will find out the longest road from the drain.

We invert the graph, calculate the maximum length, and now we will get the longest roads from the source. For all the distances for which we did not yet calculate the maximum distance, we will have inside this two arrays minus one. The arrays are named intuitively the Longest Road Drain (lr_drain) and the Longest Road Source (lr_source).

Our function will return as a result the maximum road value and generate the roads through the maximum leads within some additional arrays. There will be one for the normal call and one for the inverse graph call.

In the case of both calls we will find out the same maximum road length; what differs is only the shortest roads between the stations of the critical path. Also, from the first call, we will find out the longest road path as well. The second call on the inverse is only required to find out the earliest time possible to start a job.

The algorithm itself is a combination of the depth search algorithm and the topological order-based technique to find out the shortest (now the longest) road inside a graph. Instead of first building the topological order and later using it, we will make the approximation as soon as we get the node, so we do not need to store it.

Furthermore, we save any preliminary results in the longsetroad array, so we will call the recursion only if, for that vertex, we have received approximation yet. This will mean that, in that index, the array is minus one. This way we will approximate with each edge at most once, and ensure that we can save the vertex, through we polished our maximum road a little in the nextCritNode array. All of this will become clearer as soon as you read the next page.  

{mospagebreak title=The code snippet} 

Now applying our programming knowledge and a little recursion, we will end up with the following code.

void Crit_Path(int source, int drain)

{

memset (lr_source, -1, sizeof(int)*(n+1));

memset (lr_drain, -1, sizeof(int)*(n+1));

 

lr_drain[drain] = 0;

lr_source[source] = 0;

 

int Crit_PathLength =

LongestRoad(vertexList, source,drain,lr_drain, nextCritVert);

 

inverse(vertexList, vertexList_inver);

 

Crit_PathLength =

LongestRoad(vertexList_inver, drain,source, lr_source, prevCritVert );

 

printf_s("nn The Critical Road: %dnn",Crit_PathLength);

// print the critical timing scheduled

for ( int i = source; i; ) {

printf(" %d ->>" , i);

i = nextCritVert[i];

}

 

printf("n");

 

//print the critical timing schedule

for (int i = 1; i <= n; ++i)

{

printf("n%d —> nEarliest time : %dn", i,lr_source[i]);

 

printf("Furthest possible moment : %dn",

Crit_PathLength – lr_drain[i]);

 

printf("Delay allowed: %dn", Crit_PathLength-lr_source[i] – lr_drain[i]);

 

}

}

int LongestRoad(pListIt*& graph, int& current, int& drain,

int*& lr, int*& nextCritNode)

{

pListIt v;

 

v = graph[current];

 

while(v)

{

if (lr[v->value] == -1)

{

lr[v->value] =

LongestRoad(graph, v->value, drain, lr, nextCritNode);

}

if ( lr[v->value] + timeMat[current][v->value] > lr[current]

&& timeMat[current][v->value] != INFINITY)

{

lr[current] = lr[v->value] + timeMat[current][v->value];

nextCritNode[current] = v->value;

}

v = v->p_next;

}

return lr[current];

}

 

Now let us try it out for the graph presented on the previous page. Our input will look as follows: 

12 1

1 3 4

1 2 3

2 4 6

2 7 17

3 4 8

3 6 9

3 9 4

4 5 9

4 6 0

4 7 8

5 7 5

5 10 2

6 8 3

6 9 9

6 11 6

7 12 8

8 10 7

9 11 11

10 12 6

11 12 3

 

 

The Critical Road: 36

 

1 ->> 3 ->> 6 ->> 9 ->> 11 ->> 12 ->>

 

1 —>

Earliest time : 0

Furthest possible moment : 0

Delay allowed: 0

 

2 —>

Earliest time : 3

Furthest possible moment : 7

Delay allowed: 4

 

3 —>

Earliest time : 4

Furthest possible moment : 4

Delay allowed: 0

 

4 —>

Earliest time : 12

Furthest possible moment : 13

Delay allowed: 1

 

11 —>

Earliest time : 33

Furthest possible moment : 33

Delay allowed: 0

 

12 —>

Earliest time : 36

Furthest possible moment : 36

Delay allowed: 0

Now from the upper output I removed a part, because I did not wanted to enlarge this more than necessary. This should be enough to observe that the algorithm works flawlessly, and we were able to get all the information in which we were interested. If you want to look over the entire output or just play with it a little, I’m adding the C/C++ source code in a downloadable form. Compile it and it’s ready for you to satisfy your curiosity:  

–>Critical Paths.zip<– 

This coves what you should understand today, however, make sure it’s crystal clear to you. If you have any kind of questions remaining, ask them here on the blog or join our forum over at DevHardware and direct your questions to our experts. Remember that there is no wrong question, just wrong answers. Rating my article is also appreciated. I’m finishing this article with the promise that next time we will look into network flows. Live With Passion!

[gp-comments width="770" linklove="off" ]