Définition de l'heure de début la plus récente pour les nœuds dans le graphique acyclique dirigé

Question

J'ai créé un groupe de base de données constitué d'objets de classe nœud. Chaque nœud connaît son heure de début la plus proche, son heure de fin la plus proche, ainsi que son propre temps. Chaque nœud a également un List<Task> innNodes et un List<Task> outNodes.

Ce que j'ai fait jusqu'ici est le tri par tri topologique.

Comment puis-je définir la dernière heure de début pour chaque nœud de ce graphique?

J'ai essayé de faire ce que j'ai fait en réglant earliest start time, qui était une recherche de profondeur en commençant par le nœud-racine, cette fois-ci en le faisant inverser en commençant par le dernier nœud.

Drawn picture of my Graph (Edit: 2 -> 7)

Ce que j'ai essayé de faire:

/* 
*@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); 
     } 
    } 
} 

Edit: aussi essayé, dosn't encore du travail

//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); 
      } 
     } 
    } 

} 

Cette sortie :

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 ou ceux curieux cela a travaillé:

/* 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; 
    } 
}