Critical Path Method Algorithm

Where can I find a Java implementation of the Critical 开发者_StackOverflow中文版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.

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;
  }
}

Here is the another version of Jessup's code. I simply add some other functions and now the code calculates earliest/latest start and finish times, slack and whether the node is on the critical path or not. (I simply added the functions and get the result, I haven't put much effort on algorithm and coding)

public class CriticalPath {
    public static int maxCost;
    public static String format = "%1$-10s %2$-5s %3$-5s %4$-5s %5$-5s %6$-5s %7$-10s\n";

    public static void main(String[] args) {
        // The example dependency graph
        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);
        Task[] result = criticalPath(allTasks);
        print(result);
        // System.out.println("Critical Path: " + Arrays.toString(result));
    }

    // 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 earliest start
        public int earlyStart;
        // the earliest finish
        public int earlyFinish;
        // the latest start
        public int latestStart;
        // the latest finish
        public int latestFinish;
        // 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);
            }
            this.earlyFinish = -1;
        }

        public void setLatest() {
            latestStart = maxCost - criticalCost;
            latestFinish = latestStart + cost;
        }

        public String[] toStringArray() {
            String criticalCond = earlyStart == latestStart ? "Yes" : "No";
            String[] toString = { name, earlyStart + "", earlyFinish + "", latestStart + "", latestFinish + "",
                    latestStart - earlyStart + "", criticalCond };
            return toString;
        }

        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 critical 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 cost
        maxCost(tasks);
        HashSet<Task> initialNodes = initials(tasks);
        calculateEarly(initialNodes);

        // 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) {
                return o1.name.compareTo(o2.name);
            }
        });

        return ret;
    }

    public static void calculateEarly(HashSet<Task> initials) {
        for (Task initial : initials) {
            initial.earlyStart = 0;
            initial.earlyFinish = initial.cost;
            setEarly(initial);
        }
    }

    public static void setEarly(Task initial) {
        int completionTime = initial.earlyFinish;
        for (Task t : initial.dependencies) {
            if (completionTime >= t.earlyStart) {
                t.earlyStart = completionTime;
                t.earlyFinish = completionTime + t.cost;
            }
            setEarly(t);
        }
    }

    public static HashSet<Task> initials(Set<Task> tasks) {
        HashSet<Task> remaining = new HashSet<Task>(tasks);
        for (Task t : tasks) {
            for (Task td : t.dependencies) {
                remaining.remove(td);
            }
        }

        System.out.print("Initial nodes: ");
        for (Task t : remaining)
            System.out.print(t.name + " ");
        System.out.print("\n\n");
        return remaining;
    }

    public static void maxCost(Set<Task> tasks) {
        int max = -1;
        for (Task t : tasks) {
            if (t.criticalCost > max)
                max = t.criticalCost;
        }
        maxCost = max;
        System.out.println("Critical path length (cost): " + maxCost);
        for (Task t : tasks) {
            t.setLatest();
        }
    }

    public static void print(Task[] tasks) {
        System.out.format(format, "Task", "ES", "EF", "LS", "LF", "Slack", "Critical?");
        for (Task t : tasks)
            System.out.format(format, (Object[]) t.toStringArray());
    }
}

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

References

• Wikipedia/Critical path method