Directed Acyclic Graph의 노드에 최신 시작 시간 설정

Question

노드 노드의 개체로 구성된 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; 
    } 
}