Calculating the critical path of a graph

11,658

First of all, I'm assuming we have a directed acyclic graph (DAG).

1 - We need to find, for each vertex, the minimum possible starting time of each activity. This is like finding the longest path for each vertex in the graph. For general graphs this is NP-hard, but since the graph is a DAG, we may use a topological sort to do this in polynomial time.

2 - Compute the indegree of each vertex (that is, count the number of edges entering them). Since the graph is acyclic, there is at least one vertex that has indegree zero. Put all such vertices on a queue. Also, initialize an array of distances as 0.

Pseudo-code

# Compute the indegree
for each vertex v from the graph:
    for each neighbor u of v:
        indegree[u] += 1

queue Q = empty queue
distance = array filled with zeroes
for each vertex v:
    if indegree[v] = 0:
        insert v on Q

3 - Select the first vertex v from the queue. For each neighbor u of v, update distance[u] as distance[u] = max(distance[u], distances[v] + time(v, u)), where time(v, u) is the time necessary to perform task (u, v). Remove v from the graph. This can be done my decreasing the indegree of each of its neighbors. Enqueue any new vertex that now have 0 indegree. Repeat this procedure until all vertex are processed.

Pseudo-code

while Q is not empty:
    v = get front element from Q
    for each neighbor u of v:
        distance[u] = max(distance[u], distance[v] + time(v, u))
        indegree[u] -= 1
        if indegree[u] = 0:
            insert u on Q

4 - Now, select the vertex x with the largest distance. This is the minimum total project duration.

5 - We need to re-construct the critical path. A task (u, v) is on the critical path if has tight times, that is, distance[u] + time(u, v) = distance[v]. So, start with vertex x and search for a path to a starting vertex, with the following constraint: if you're in a vertex a, you can only go to vertex b, with there's an edge (b, a) such that distance[a] = distance[b] + time(b, a).

6 - For the edges that were not on the path, you need to find the total slack and the free slack. The free slack is easy: to not delay the following task, you need to compute the amount of time between the start of the next task and the end time of the current one. This can be found by the equation: distance[v] - (distance[u] + time(u, v)) for each (u, v).

7 - To find the total slack you'll need a new piece of information, that is the latest time a task may begin without delaying the whole project. This can be done by reverting the direction of the edges of your graph. Then, starting with vertex x, initialize an array late with the total project duration.

8 - Again, using the topological order, whenever you dequeue a vertex v, for all its neighbors u, you do late[u] = min(late[u], late[v] - time(v, u)). After reverting the directions bacj, it's easy to see that the total slack is given by late[v] - (late[u] + time(u, v)) for each edge (u, v).

9 - Finally, as far as I understood, you have to mark with an R all edges that have total slack > free slack.

Share:
11,658
fran.sand66
Author by

fran.sand66

Kick-butt Developer, RESTafarian lover. White belt in Data Science. Human After All.

Updated on June 04, 2022

Comments

  • fran.sand66
    fran.sand66 over 1 year

    for homework of graph theory, I asked to calculate the (s) Critical (s) Routes (s) and timing slack of a project under the following format:

    Entry: The first line of input will be an integer C, which indicates the number of test cases (graphs modeling the activities of a project). The first line of each test case contains two integers N and M respectively, where N represents the number of nodes in the project and the amount M of activities. Then come m lines, each with 3 integers I, J and D, where I and J represent the start and end node of an activity.

    The entry should be read from the file "entrada.in" which will be in the program folder. Be considered a bonus if your program provides the opportunity to read the file from any path through a graphical interface (ie, without write the full path).

    Output:

    In the first line of each test case must display the following string "Case G: Duration Total P", where G represents the number of test case (starting at 1) and P the total project duration. Then X lines on which activities should be expressed for the (s) Critical (s) Route (s) of the project, following the same format as the input (except the integer that represents the duration), but additionally, the edges are be ordered (as the first priority should be taking home nodes from lower to higher and end nodes as the second lowest to highest). Then must follow "Y" lines, corresponding to noncritical activities, following the same order listed above. For each noncritical activity should show 4 integers, I, J, T and F, where T and F represent the total slack and free slack of each activity respectively. Additionally you must add an R at the end of the line if the activity is marked with a red flag. Should obviate the dummy activities are not part of the critical path for output.

    After each test case should print a blank line. The output should be written in the file "salida.out. "

    Example: example of entry and output

    I need to tell me some idea of how to do what I required, I am not asking for a solution just a little help (pseudocode for example), Thanks to all