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
等