4

Java を使用して有向グラフを実装しました。これはプロジェクト プランナー用で、1 つのノードがさまざまなプロパティを持つタスクを表します。トポロジカル ソートを正常に実装しましたが、タスクの依存関係が完了したらすぐに並列タスクを実行/実行する方法が必要です。

これが私の実装です:

import java.util.ArrayList;
import java.util.List;
import java.util.*;

public class Task implements Comparable<Task> {
    int number;
    String name;
    int time;
    int staff;
    int earliestStart, latestStart;
    List<Integer> dependencies;
    List<Task> outEdges;
    int cntPredecessors;
    Status status;
    public enum Status {UNVISITED,RUNNING,VISITED};
    @Override
    public String toString() {
        return "Task{" +
                "number=" + number +
                ", name='" + name + '\'' +
                ", time=" + time +
                ", staff=" + staff +
                ", dependencies=" + dependencies +
                '}';
    }

    public Task(int number, String name, int time, int staff) {
        setNumber(number);
        setName(name);
        setTime(time);
        setStaff(staff);
        dependencies=new ArrayList<>();
        outEdges=new ArrayList<>();
        status = Status.UNVISITED;
     }

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getTime() {
        return time;
    }

    public void setTime(int time) {
        this.time = time;
    }

    public int getStaff() {
        return staff;
    }

    public void setStaff(int staff) {
        this.staff = staff;
    }

    public List<Integer> getDependencies() {
        return dependencies;
    }

    public void setDependencies(List<Integer> dependencies) {
        this.dependencies = dependencies;
    }

    public List<Task> getOutEdges() {return outEdges; }

    public void setOutEdge(Task t) {outEdges.add(t); }



    public int getIndegrees() { return cntPredecessors; }

    public void setIndegree() { cntPredecessors = dependencies.size();}

    public Status getStatus() {return this.status; }

    public Task findTaskWithNoInDegree() {
            if (this.cntPredecessors == 0) return this;
            return null;
    }
    

    public int compareTo(Task other) {

        return Integer.compare(this.time, other.time);

        }
} //END class Task

// The class Main represents the Task objects in a graph

import java.util.*;

public class Main {
    static int maxnr = 0;

    public static void main(String[] args) {
        Map<Integer, Task> map=new HashMap<>();
        Scanner scanner = new Scanner(Main.class.getResourceAsStream("/res/house.txt"), "UTF-8");
        
        Main mainObject = new Main();
        map = mainObject.fromScanner(scanner);
        System.out.println("DEBUG: maxnr " + maxnr);
        mainObject.setInDegrees(map);
        mainObject.setOutEdges(map);

        //System.out.println("DEBUG: Size of outEdges for Task 1 is : " + map.get(1).getOutEdges().size());
        //System.out.println("DEBUG: Indegrees for Task 8 is : " + map.get(8).getIndegrees());
        mainObject.topSort(maxnr,map);

        for(Integer k:map.keySet()) {
            //System.out.println("DEBUG outEdges for Task number " + map.get(k).getNumber() + " " + map.get(k).getOutEdges());
        }

    } // END of void main(String[] args)


    public void setInDegrees(Map<Integer, Task> map) {
        for(Integer k:map.keySet()) {
            Task task = map.get(k);
            task.setIndegree();
        }
    }


    public void setOutEdges(Map<Integer, Task> map) {
        for(Integer k:map.keySet()) {
            // map.get(k).setIndegrees();
            for(Integer dep:map.get(k).getDependencies()) {
                //System.out.println("DEBUG: "+ dep);
                //System.out.print(" DEBUG:  Name is "  + map.get(dep).getName());
                map.get(dep).setOutEdge(map.get(k));
            }
            //System.out.println(map.get(k));
        }
    } //END of setOutEdges()
        // toplogical sort # Big O(|V| +|E|)  for indegree calc and since the code only looks at each edge once!
        // S is Set of all nodes with no incoming edges
    public void topSort(int maxnr, Map<Integer, Task> map) {
        ArrayList<Task> L = new ArrayList<Task>(maxnr);
        //LinkedList<Task> L = new LinkedList<>();
        //HashSet<Task> S = new HashSet<>(maxnr);
        LinkedList<Task> S = new LinkedList<>();

        for(Integer n:map.keySet()) {
            if(map.get(n).getIndegrees() == 0) {
                S.add(map.get(n));
            }
        }
        System.out.println("DEBUG: Set S is " + S);
        //HashSet<Task> S2 = new HashSet<>(S);

        Task t;
        int counter= 0;
        while(!S.isEmpty()) {
            //System.out.print("Topsort: Task and S. " + t.getNumber());
            t = S.iterator().next();
            S.remove(t);
            //System.out.print("Topsort : " + t.getNumber());
            L.add(t);
            //System.out.println("Starting " + t.getNumber());
            counter++;

            for(Iterator<Task> it = t.outEdges.iterator(); it.hasNext();) {
                Task w =  it.next();
                w.cntPredecessors--;
                if (w.getIndegrees() == 0) {
                    S.add(w);
                   // System.out.println("Starting " + w.getNumber());
                }
            }
        }
        System.out.println();

        if (counter < maxnr) {
            System.out.println("Cycle detected, topsort not possible");
        } else {
            //System.out.println("Topsort : " + Arrays.toString(L.toArray()));
            Iterator<Task> topsortIt = L.iterator();
            System.out.print("\n Topsort list is: ");
            while (topsortIt.hasNext()) {
                System.out.print(" " + topsortIt.next().getNumber());
            }
            System.out.println();
        }
    } //END of topSort()

    public Map fromScanner(Scanner scanner) {
    Map<Integer, Task> map=new HashMap<>();
    maxnr = scanner.nextInt();
    while (scanner.hasNextLine()) {
        String line=scanner.nextLine();
        if (line.isEmpty() ) continue;
        Scanner s2=new Scanner(line);
        Task task = new Task(s2.nextInt(), s2.next(), s2.nextInt(), s2.nextInt());
        while (s2.hasNextInt()) {
            int i = s2.nextInt();
            if (i != 0) {
                task.getDependencies().add(i);
            }
        }
        map.put(task.getNumber(), task);
    }
    return map;
    } //END of fromScanner()

    } //END of class Main

house.txt の内容: 最初の行 (数字) は最大ノード数/タスク数です。列は次のとおりです。タスク番号、名前、完了までに必要な時間、人員要件、依存関係のエッジ (0 で終了)。

8
1   Build-walls     4 2       5       0
2   Build-roofs     6 4       1       0
3   Put-on-wallpapers   1 2       1       2       0
4   Put-on-tiles        1 3       2       0
5   Build-foundation    4 2       0
6   Make-floor          2 2       5       0
7   Put-carpet-floor    4 2       6       2       0
8   Move-in         4 4       3       7       0

着信エッジがない (つまり、依存関係がない) タスクを最初に開始する必要があります。タスクの実行は、たとえば上記の入力のように出力する必要があります。

Time: 0      Starting: 5   // Task 5 only one with no  dependencies
        Current staff: 2 

Time: 4      Finished: 5
             Starting: 6
             Starting: 1
        Current staff: 4   // sum of manpower from Task 6 and 1 => 2 +  2 = 4

Time: 6     Finished: 6
       Current staff: 2    

Time: 8     Finished: 1
            Finished: 1  
            Starting: 2
            Starting: 3 
       Current staff: 6

4

3 に答える 3

1

いくつかの方法があります。

Java 8CompletableFutureまたは GuavaListenableFutureを使用して実装できます。

あなたのタスクはRunnableorを実装する必要がありCallableます。現在のタスクを実行するときは、preTasks再帰的に実行し(タスクが複合モードの場合、前のタスクであることを認識します)、それらが完了していることを確認する必要があります(ステータスなどを表すフラグを介して)。

そのようです:

CompletableFuture.allOf(predecessor).thenRunAsync(current)...
Futures.allAsList(predecessor)...
于 2021-02-20T03:24:11.550 に答える