Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

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 gif 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.

   figure54769
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 gif shows the event-node graph corresponding to the activity node graph given in Figure gif. Where an activity depends on more than one predecessor it is necessary to insert dummy edges.

   figure55363
Figure: The Event-Node Graph corresponding to Figure gif

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 tex2html_wrap_inline73157 and tex2html_wrap_inline73159 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 tex2html_wrap_inline73163 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

  equation55587

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

Similarly, tex2html_wrap_inline73179 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

  equation55597

where tex2html_wrap_inline73185 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 tex2html_wrap_inline73189 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

  equation55608

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 gif gives the results from obtained from the critical path analysis of the activity-node graph shown in Figure gif. The tabulated results indicate the critical path is

displaymath73117

 

 

activity C(v,w) tex2html_wrap_inline73163 tex2html_wrap_inline73199 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
Table: Critical Path Analysis Results for the Activity-Node Graph in Figure gif