Critical Path Method Algorithm

Question

Where can I find a Java implementation of the Critical Path Method Algorithm? I am sure there's some implementation in the cloud. I have already searched on google obviously, but haven't found any implementation that works well. That's why I am asking.

Thanks in advance.

Answer 1

There's a Java applet at cut-the-knot.org. There's also an online calculator at sporkforge.com.

References

• Wikipedia/Critical path method

Answer 2

Here is an implementation of the algorithm based on the explanation provided on this page There is a wrapper class to hold the task, cost, and critical path cost. It starts by calculating the critical cost as the maximum critical cost of all dependencies plus its own cost. Then once the critical costs are available it uses a comparator to sort the tasks based on the critical cost with dependency as a tie breaker (choosing randomly if there is no dependency). Note that an exception will be thrown if there is a cycle and it will fail if any of the costs are negative.

Here is the implementation:

public class CriticalPath {

  public static void main(String[] args) {
    //The example dependency graph from
    //http://www.ctl.ua.edu/math103/scheduling/scheduling_algorithms.htm
    HashSet<Task> allTasks = new HashSet<Task>();
    Task end = new Task("End", 0);
    Task F = new Task("F", 2, end);
    Task A = new Task("A", 3, end);
    Task X = new Task("X", 4, F, A);
    Task Q = new Task("Q", 2, A, X);
    Task start = new Task("Start", 0, Q);
    allTasks.add(end);
    allTasks.add(F);
    allTasks.add(A);
    allTasks.add(X);
    allTasks.add(Q);
    allTasks.add(start);
    System.out.println("Critical Path: "+Arrays.toString(criticalPath(allTasks)));
  }

  //A wrapper class to hold the tasks during the calculation
  public static class Task{
    //the actual cost of the task
    public int cost;
    //the cost of the task along the critical path
    public int criticalCost;
    //a name for the task for printing
    public String name;
    //the tasks on which this task is dependant
    public HashSet<Task> dependencies = new HashSet<Task>();
    public Task(String name, int cost, Task... dependencies) {
      this.name = name;
      this.cost = cost;
      for(Task t : dependencies){
        this.dependencies.add(t);
      }
    }
    @Override
    public String toString() {
      return name+": "+criticalCost;
    }
    public boolean isDependent(Task t){
      //is t a direct dependency?
      if(dependencies.contains(t)){
        return true;
      }
      //is t an indirect dependency
      for(Task dep : dependencies){
        if(dep.isDependent(t)){
          return true;
        }
      }
      return false;
    }
  }

  public static Task[] criticalPath(Set<Task> tasks){
    //tasks whose critical cost has been calculated
    HashSet<Task> completed = new HashSet<Task>();
    //tasks whose ciritcal cost needs to be calculated
    HashSet<Task> remaining = new HashSet<Task>(tasks);

    //Backflow algorithm
    //while there are tasks whose critical cost isn't calculated.
    while(!remaining.isEmpty()){
      boolean progress = false;

      //find a new task to calculate
      for(Iterator<Task> it = remaining.iterator();it.hasNext();){
        Task task = it.next();
        if(completed.containsAll(task.dependencies)){
          //all dependencies calculated, critical cost is max dependency
          //critical cost, plus our cost
          int critical = 0;
          for(Task t : task.dependencies){
            if(t.criticalCost > critical){
              critical = t.criticalCost;
            }
          }
          task.criticalCost = critical+task.cost;
          //set task as calculated an remove
          completed.add(task);
          it.remove();
          //note we are making progress
          progress = true;
        }
      }
      //If we haven't made any progress then a cycle must exist in
      //the graph and we wont be able to calculate the critical path
      if(!progress) throw new RuntimeException("Cyclic dependency, algorithm stopped!");
    }

    //get the tasks
    Task[] ret = completed.toArray(new Task[0]);
    //create a priority list
    Arrays.sort(ret, new Comparator<Task>() {

      @Override
      public int compare(Task o1, Task o2) {
        //sort by cost
        int i= o2.criticalCost-o1.criticalCost;
        if(i != 0)return i;

        //using dependency as a tie breaker
        //note if a is dependent on b then
        //critical cost a must be >= critical cost of b
        if(o1.isDependent(o2))return -1;
        if(o2.isDependent(o1))return 1;
        return 0;
      }
    });

    return ret;
  }
}