java - 设置有向无环图中节点的最晚开始时间

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

}

此输出:

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

对于那些好奇的人来说，这有效:

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