Critical Paths - The code snippet
(Page 4 of 4 )
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!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
