The critical path method or just CPM is a mathematically based algorithm for scheduling a set of project activities.

The essential technique for using CPM is to construct a model of the project that includes the following:

• A list of all activities required to complete the project (also known as Work Breakdown Structure),
• The time (duration) that each activity will take to completion, and
• The dependencies between the activities.

For a test case let's assume the following picture:

In the picture above we have circles that represent activities identified by capitalized letters.

The red number inside each circle indicates the time spent to complete the activity.

The upper left and right numbers represent the earliest start time and earliest end time of each activity respectively. The lower left and right numbers represent the latest start time and latest end time of each activity respectively.

The circles with a red border represent the critical path for this given set of activities.

A class that represents each activity was firstly modeled. This class has as properties the activity's ID, description and duration along with the earliest start time (est), latest start time (lst), earliest end time (eet) and latest end time (let).

The dependencies between each activity is stored in two arrays, the successors and predecessors arrays.

public class Activity
{
  private string id;
  private string description;
  private int duration;
  private int est;
  private int lst;
  private int eet;
  private int let;

  private Activity[] successors;
  private Activity[] predecessors;

  ...
}

The CPM algorithm uses the activities data to calculate the longest path of planned activities to the end of the project, and the earliest and latest that each activity can start and finish without making the project longer.
This process determines which activities are "critical" (i.e., on the longest path) and which have "total float" (i.e., can be delayed without making the project longer).

To accomplish that two methods were created: one called WalkListAhead and the other called WalkListAback.

The WalkListAhead method receives the array that stores the activities already entered and performs the forward walking inside the array of activities calculating for each activity its earliest start time and earliest end time.

After the forward walking the WalkListAback performs the backward walking calculating for each activity its latest start time and latest end time.

See the following code:

private static Activity[] WalkListAhead(Activity[] list)
{
  list[0].Eet = list[0].Est + list[0].Duration;

  for(int i = 1; i < na; i++)
  {
    foreach(Activity activity in list[i].Predecessors)
    {
      if(list[i].Est < activity.Eet)
        list[i].Est = activity.Eet;
    }

    list[i].Eet = list[i].Est + list[i].Duration;
  }

  return list;
}

private static Activity[] WalkListAback(Activity[] list)
{
  list[na - 1].Let = list[na - 1].Eet;
  list[na - 1].Lst = list[na - 1].Let - list[na - 1].Duration;

  for(int i = na - 2; i >= 0; i--)
  {
    foreach(Activity activity in list[i].Successors)
    {
      if(list[i].Let == 0)
        list[i].Let = activity.Lst;
      else
        if(list[i].Let > activity.Lst)
          list[i].Let = activity.Lst;
    }

    list[i].Lst = list[i].Let - list[i].Duration;
  }

  return list;
}

To determine the critical path a method called CriticalPath verifies if each activity's earliest end time minus the latest end time and earliest start time minus the latest start time are equal zero. If so, then the activity is part of the critical path and its id is written in the screen. The project's total duration is also shown.

See the code:

private static void CriticalPath(Activity[] list)
{
  Console.Write("\n          Critical Path: ");

  foreach(Activity activity in list)
  {
    if((activity.Eet - activity.Let == 0) && (activity.Est -
activity.Lst == 0))
      Console.Write("{0} ", activity.Id);
  }

  Console.Write("\n\n         Total duration: {0}\n\n",
list[list.Length - 1].Eet);
}

While developing this code I and my brother in faith Wellington Magalhães Leite had a great time together. We learned great things about data structures and we could master our programming skills.

I remember that to hand in this code regarding the Software Engineering discipline taught by Rodrigo dos Santos Macedo we worked till late evening. As a result we got a great grade!

Get the complete code at http://leniel.googlepages.com/CriticalPathMethod.rar.

Update 4/22/2011

I cross-posted this at a CodeProject article. There I show a big screenshot of the running console application with user data input. The app finds the Critical Path and Total days (duration) shown at the bottom part of the screenshot.

You can use the free Microsoft Visual C# Express to open the project and play with it. :)

Update 5/21/2011

Emil Lerch found a couple of small bugs in our original project and fixed them along the way. He has taken the CPM engine and refactored it as a generic IEnumerable extension method. He managed to write a great amount of code and I’m impressed with all the refactoring that makes use of Generics, Lambdas, etc.

Emil’s Project highlights:

Critical Paths in .NET: Extension Method

This is a rewrite of Critical Path Method Implementation in C#. It has the following features over and above the original:

• It uses generics to avoid type dependency. Extra metadata is stored internally
• The public method is an extension method based on IEnumerable, so any list works
• Task information can come in any order. Pass in a lambda to tell the engine how to get a task's predecessors and another lambda to get the task length and it will figure out the rest
• If a loop is detected in the path, an exception will be thrown

It is used in a production web site and is stable at this point.

His version of our code can be found at:

https://github.com/elerch/Critical-Path-Extension-Method-for-.NET