All geek questions in one place

Critical Path Method Algorithm

Where can I find the Java implementation of the critical path method algorithm? I'm sure there is some kind of implementation in the cloud. I already searched on google but did not find any implementation that works well. That is why I ask.

Thanks in advance.

+3
source share
3 answers

Here is the implementation of the algorithm based on the explanation provided on this page. There is a wrapper class for storing task cost, cost and critical path. It begins by calculating the critical value as the maximum critical value of all dependencies plus its own costs. Then, when critical costs are available, it uses a comparator to sort tasks based on critical costs with a dependency as a tight switch (random selection if there is no dependency). Note that an exception will be thrown if there is a loop, 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;
  }
}
+5
source

Jessup. , / , node . ( , )

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());
    }
}
+2

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

References

0
source

Source: https://habr.com/ru/post/1748753/

More articles:


All Articles