Finding Longest Path in Directed Acyclic Graph

Question

I need to find the longest path from node 0 for a set of Directed Acyclic Graphs. I am using the Longest Path Problem algorithm from Wikipedia. I have got the algorithm working for most graphs, but for others it doesn't give a correct result. The algorithm is:

private static int DAGLongestPath(Graph G) {
int n = G.order();
int[] topOrder = new int[n];
topOrder = topSort2(G);

for (int i = 0; i < topOrder.length; i++) {
    topOrder[i] -= 1;
}   

int[] lengthTo = new int[n];
for (int i = 0; i < n; i++) lengthTo[i] = 0;

for (int i = 0; i < topOrder.length; i++) { //for each vertex v in topOrder(G) do
    ArrayList<Integer> neighbors = new ArrayList<Integer>();
    neighbors = G.neighbors(topOrder[i]);
    int v = topOrder[i];
    for (int j = 0; j < neighbors.size(); j++) {
        int w = neighbors.get(j);
        if(lengthTo[w] <= lengthTo[v] + 1) {
            lengthTo[w] = lengthTo[v] + 1;
        }
    }   
}   

int max = 0;
for (int i = 0; i < n; i++ ) {
    max = Math.max(max, lengthTo[i]);
}
return max;
}

The graph implementation uses an Adjacency List to store the graphs. If I pass a graph like:

9 // Number of nodes
0: 1 2 
1: 2 3 4
2: 4 8
3: 5 6
4: 6 7 8
5:
6:
7:
8: 7

I get the answer 5, which is correct. However, if I pass the graph:

8 // Number of nodes
0: 2 3
1:
2:
3: 5
4: 5
5: 2
6: 7
7: 4

Then I get 2, when the correct answer should be 3.

The TopSort2 algorithm I am using is:

public static int[] topSort2(Graph G){
    int n = G.order();
    int[] sort = new int[n];

    int[] inDeg = new int[n];
    for (int i=0; i<n; i++) inDeg[i] = G.inDegree(i);

    int cnt = 0;
    boolean progress = true;
    //
    while (progress){
        progress = false;

        for (int v=0; v<n; v++){
            if (inDeg[v] == 0){
                sort[v] = ++cnt;
                progress = true;
                inDeg[v] = -1;

                ArrayList<Integer> nbrs = G.neighbors(v);
                for (int u : nbrs){
                    inDeg[u] = inDeg[u] - 1;
                }
            }
        } // for v

    } // while nodes exist with inDegree == 0.

    return sort;
}

DFS algorithms are:

private static int doDFS(Graph G, int v, int[] PreOrder, int[] PostOrder, countPair cnt){
    PreOrder[v] = cnt.inc1();
    int dfsTotal = 0;

    ArrayList<Integer> nbrs = G.neighbors(v);
    for (int i : nbrs) {
        if (PreOrder[i] == 0) {
            int dfsTemp = doDFS(G, i, PreOrder, PostOrder, cnt);
            dfsTotal = Math.max(dfsTotal, dfsTemp);
        }
    }
    PostOrder[v] = cnt.inc2();
    if(nbrs.size() > 0 ) {
        dfsTotal++;
    }
    return dfsTotal;
}

public static int DFS(Graph G, int v, int[] PreOrder, int[] PostOrder){
    int n = G.order();
    int total = 0;
    for (int i=0; i<n; i++) PreOrder[i] = PostOrder[i] = 0;

    countPair cnt = new countPair();
    total = doDFS(G, v, PreOrder, PostOrder, cnt);

    return total;
}

private static class countPair {       // private counters for DFS search
    int cnt1, cnt2;
    int inc1() { return ++cnt1; }
    int inc2() { return ++cnt2; }
}

i think the second correct answer should be 4, 6->7->4->5->2, also are you sure your topSort2() function is correct? — xvatar
Oh right, I'm getting the longest path from node 0. TopSort function I posted above. — Te Riu Warren

xvatar xvatar · Accepted Answer · 2012-06-03T03:42:41

I think the problem is your topSort2() function

In the int[] sort returned by the function, the index denotes the vertex and the content denotes the order. i.e. if you have sort[1] = 2, you mean vertex 1 is the second vertex

However when you use it, you take the content as the vertex. i.e. you take topOrder[i] as a vertex, while actually i should be the vertex

Finding Longest Path in Directed Acyclic Graph

1 Answers