Data Structures and Algorithms with Object-Oriented Design Patterns in C++

# Application: Critical Path Analysis

In the introduction to this chapter it is stated that there are myriad applications of graphs. In this section we consider one such application--critical path analysis . Critical path analysis crops up in a number of different contexts, from the planning of construction projects to the analysis of combinational logic circuits.

For example, consider the scheduling of activities required to construct a building. Before the foundation can be poured, it is necessary to dig a hole in the ground. After the building has been framed, the electricians and the plumbers can rough-in the electrical and water services and this rough-in must be completed before the insulation is put up and the walls are closed in.

We can represent the set of activities and the scheduling constraints using a vertex-weighted, directed acyclic graph (DAG). Each vertex represents an activity and the weight on the vertex represents the time required to complete the activity. The directed edges represent the sequencing constraints. I.e., an edge from vertex v to vertex w indicates that activity v must complete before w may begin. Clearly, such a graph must be acyclic.

A graph in which the vertices represent activities is called an activity-node graph . Figure  shows an example of of an activity-node graph. In such a graph it is understood that independent activities may proceed in parallel. For example, after activity A is completed, activities B and C may proceed in parallel. However, activity D cannot begin until both B and C are done.

Figure: An Activity-Node Graph

Critical path analysis answers the following questions:

1. What is the minimum amount of time needed to complete all activities?
2. For a given activity v, is it possible to delay the completion of that activity without affecting the overall completion time? If yes, by how much can the completion of activity v be delayed?

The activity-node graph is a vertex-weighted graph. However, the algorithms presented in the preceding sections all require edge-weighted graphs. Therefore, we must convert the vertex-weighted graph into its edge-weighted dual . In the dual graph the edges represent the activities, and the vertices represent the commencement and termination of activities. For this reason, the dual graph is called an event-node graph .

Figure  shows the event-node graph corresponding to the activity node graph given in Figure . Where an activity depends on more than one predecessor it is necessary to insert dummy edges.

Figure: The Event-Node Graph corresponding to Figure

For example, activity D cannot commence until both B and C are finished. In the event-node graph vertex 2 represents the termination of activity B and vertex 3 represents the termination of activity C. It is necessary to introduce vertex 4 to represent the event that both B and C have completed. Edges and represent this synchronization constraint. Since these edges do not represent activities, the edge weights are zero.

For each vertex v in the event node graph we define two times. The first is the earliest event time  for event v. It is the earliest time at which event v can occur assuming the first event begins at time zero. The earliest event time is given by

where is the initial event, is the set of incident edges on vertex w and C(v,w) is the weight on vertex (v,w).

Similarly, is the latest event time  for event v. It is the latest time at which event v can occur The latest event time is given by

where is the final event.

Given the earliest and latest event times for all events, we can compute time available for each activity. E.g., consider an activity represented by edge (v,w). The amount of time available for the activity is and the time required for that activity is C(v,w). We define the slack time  for an activity as the amount of time by which an activity can be delayed with affecting the overall completion time of the project. The slack time for the activity represented by edge (v,w) is given by

Activities with zero slack are critical . I.e., critical activities must be completed on time--any delay affects the overall completion time. A critical path  is a path in the event-node graph from the initial vertex to the final vertex comprised solely of critical activities.

Table  gives the results from obtained from the critical path analysis of the activity-node graph shown in Figure . The tabulated results indicate the critical path is

 activity C(v,w) S(v,w) A 3 0 3 0 B 1 3 7 3 C 4 3 7 0 D 1 7 8 0 E 9 8 17 0 F 5 8 17 4 G 2 17 18 0