指示された非循環グラフのノードに最新の開始時刻を設定する

Question

私はノードNodeのオブジェクトで構成されるDAGを作成しました。すべてのノードは、それ自身の最も早い開始時間、最も早い終了時間、およびそれ自身の時間を知っている。すべてのノードにはList<Task> innNodesとList<Task> outNodesもあります。

私がこれまで行ってきたことは、トポロジカルソートを使ってソートしています。

このグラフの各ノードの最新の開始時刻を設定するにはどうすればよいですか？

earliest start timeは、ルートノードから深さ優先検索を開始していましたが、今回は逆に最後のノードから開始していました。

Drawn picture of my Graph（編集：2 - > 7）私が実行しようとしました何

：

/* 
*@param maxLen is the earliest finish time of the last node 
*/ 
private void setLatest(Node root, Node last, int maxLen){ 
    int latest = maxLen; 
    latest -= last.getTime(); 
    last.latestStart = latest; 
    for(Node n : last.getInnNodes()){ 
     if (n.latestStart == 0){ 
      if(n == root){ 
       continue; 
      } 
      n.latestStart = latest; 
      setLatest(root, n, latest); 
     } 
    } 
} 

編集：また、まだ作業

//cntNext is 2 for root, and 0 for leafs 
public void setLatest(){ 
    Stack<Node> stack = new Stack<Node>(); 
    List<Node> list = new ArrayList<Node>(sorted); 
    int rootTime = getRoot().earliestStart; 
    for(Node n : leafs){ 
     n.latestStart = leafTime; 
     stack.push(n); 
    } 
    while(!stack.isEmpty()){ 
     Node n = stack.pop(); 
     int time = n.latestStart; 
     for (Node v : n.getInnNodes()){ 
      list.remove(v); 
      v.cntNext--; 
      if(v.cntNext == 0){ 
       time -= v.getTime(); 
       v.latestStart = time; 
       stack.push(v); 
      } 
     } 
    } 

} 

この出力をdosn't、これを試してみました：

ID: 5 Earliest Start: 0 Latest Start: 0 (Expected 0) 
ID: 6 Earliest Start: 4 Latest Start: 12 (Expected 12) 
ID: 1 Earliest Start: 4 Latest Start: 13 (Expected 4) 
ID: 2 Earliest Start: 8 Latest Start: 11 (Expected 8) 
ID: 4 Earliest Start: 14 Latest Start: 0 (Expected 14) 
ID: 3 Earliest Start: 14 Latest Start: 17 (Expected 14) 
ID: 7 Earliest Start: 14 Latest Start: 14 (Expected 14) 
ID: 8 Earliest Start: 18 Latest Start: 18 (Expected 18) 

Answer 1

Fまたは好奇心をそそられた人は、この仕事をしました：

/* Reverse topological sort using stack */ 

public void setLatestStart(){ 
    int critical = earliestProjectFinishTime; 
    int time = critical; 
    HashSet<Node> S = new HashSet<Node>(); 

    for(Node n : leafs){       /* set latest start time of all leaves to critical, as no node depend on them */ 
     n.latestStart = time - n.getTime(); 
     S.add(n); 
    } 

    while(!S.isEmpty()){ 
     Node n = S.iterator().next(); 
     S.remove(n); 
     time = n.latestStart; 
     for(Node m : n.getInnNodes()){ 
      if(m.latestStart > time || m.latestStart == 0){    /* this protects the node from being overwritten by non-critical nodes */ 
       m.latestStart = time - m.getTime(); 
       S.add(m); 
      } 
     } 
    } 
    for(Node n : roots){ 
     n.latestStart = 0; 
    } 
}