Graphs and paths - Data Structures and Problem Solving Using Java - page 560

14.5.4 an application: critical-path analysis

An important use of acyclic graphs is critical-path analysis, a form of analy-
sis used to schedule tasks associated with a project. The graph shown in
Figure 14.33 provides an example. Each vertex represents an activity that
must be completed, along with the time needed to complete it. The graph is
thus called an activity-node graph, in which vertices represent activities and
edges represent precedence relationships. An edge ( v , w ) indicates that activity
v must be completed before activity w may begin, which implies that the
graph must be acyclic. We assume that any activities that do not depend
(either directly or indirectly) on each other can be performed in parallel by
different servers.

Critical-path analy-
sis is used to
schedule tasks
associated with a
project.

This type of graph could be (and frequently is) used to model construction
projects. Two important questions must be answered. First, what is the earliest
completion time for the project? The answer, as the graph shows, is 10 time
units—required along path A , C , F, H . Second, which activities can be
delayed, and by how long, without affecting the minimum completion time?
For instance, delaying any of A, C, F, or H would push the completion time
past 10 time units. However, activity B is less critical and can be delayed up to
2 time units without affecting the final completion time.

An activity-node
graph represents
activities as vertices
and precedence
relationships as
edges.

To perform these calculations, we convert the activity-node graph to an
event-node graph, in which each event corresponds to the completion of an
activity and all its dependent activities. Events reachable from a node v in the
event-node graph may not commence until after the event v is completed. This
graph can be constructed automatically or by hand (from the activity-node
graph). Dummy edges and vertices may need to be inserted to avoid introduc-
ing false dependencies (or false lack of dependencies). The event-node graph
corresponding to the activity-node graph in Figure 14.33 is shown in
Figure 14.34.
To find the earliest completion time of the project, we merely need to find
the length of the longest path from the first event to the last event. For general
graphs, the longest-path problem generally does not make sense because of

The event-node
graph consists of
event vertices that
correspond to the
completion of an
activity and all its
dependent
activities.

figure 14.33
An activity-node
graph

C 3 F 3

A 3

Start Finish

D 2 G 2 H 1

B 2

E 1 K 4