Maximum path length between two vertices in a DAG

Question

Given a Directed Acyclic Graph, G and two vertices u and v, I need to find the longest u-v path in G. DFS calls explore function to store visited vertices in the visited[] boolean array (if vertex is visited the value in array is set true, otherwise it's false). Vertices u and v are never marked as visited. Variable MAX stores the max path; when STOP vertex is reached in explore() function MAX is set to max of current path length and MAX value. The code doesn't work right.

import java.util.Iterator;
import java.util.LinkedList;

public class DAG2 {
int vertex;
LinkedList<Integer> list[];

int START, STOP;
int length = 0;
int MAX = 0;

public DAG2(int vertex) {

    this.vertex = vertex;
    list = new LinkedList[vertex];
    for (int i = 0; i < vertex; i++) {
        list[i] = new LinkedList<>();
    }

}

public void addEdge(int source, int destination) {

    // add edge
    list[source].addFirst(destination);

}

void DFS(int u, int v) {

    boolean[] visited = new boolean[this.vertex];
    START = u;
    STOP = v;
    explore(v, visited);
}

private void explore(int v, boolean[] visited) {
    // TODO Auto-generated method stub

    visited[v] = true;
    visited[START] = false;
    visited[STOP] = false;

    Iterator<Integer> i = list[v].listIterator();

    while (i.hasNext()) {
        int n = i.next();
        length++;
        if (n == STOP) {
            MAX = Math.max(MAX, length);
            length = 0;
        }

        if (!visited[n])
            explore(n, visited);
    }
}

public static void main(String args[]) {
    DAG2 g = new DAG2(8);

    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);
    g.addEdge(3, 6);
    g.addEdge(4, 7);
    g.addEdge(5, 7);
    g.addEdge(6, 5);
    g.addEdge(6, 7);
    // new
    g.addEdge(2, 3);
    g.addEdge(3, 5);
    g.addEdge(5, 4);

}
}

John Bayko John Bayko · Accepted Answer · 2019-10-06T04:47:42

The first thing I notice about the "visited" array is that if you're looking for more than one path, you might visit a node more than once (because more than one math might lead to it, e.g. 1 -> 3 -> 4 and 1 -> 2 -> 3 -> 4 will both visit 3).

My first instinct for a depth first search is to use a recursive search. I put together one like that looks like this:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class DAG {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    public void addEdge(final int src, final int dst) {
        if (!graph.containsKey(src)) {
            graph.put(src, new LinkedList<Integer>());
        }
        graph.get(src).add(dst);
    }

    public List<Integer> findMaxPath(final int start, final int end) {
        if (start == end) {
            // The path is just this element, so return a list with just the
            // start (or end).
            final List<Integer> path = new LinkedList<>();
            path.add(start);
            return path;
        }

        if (!graph.containsKey(start)) {
            // There is no path forward.
            return null;
        }

        List<Integer> longestPath = null;

        for (Integer next : graph.get(start)) {
            final List<Integer> newPath = findMaxPath(next, end);
            if (null != newPath) {
                // Found a new path
                if ( (null == longestPath)
                  || (newPath.size() > longestPath.size()) )
                {
                    // It was longer than the previous longest,
                    // it is new longest.
                    longestPath = newPath;
                }
            }
        }

        if (null != longestPath) {
            // A path was found, include this node as the start of the path.
            longestPath.add(0, start);
        }
        return longestPath;
    }

    public static void main(final String[] args) {
        final DAG g = new DAG();

        g.addEdge(1, 2); 
        g.addEdge(1, 3); 
        g.addEdge(1, 6); 
        g.addEdge(2, 4); 
        g.addEdge(3, 5); 
        g.addEdge(6, 7); 
        g.addEdge(7, 4); 
        g.addEdge(2, 6);
        printPath(g.findMaxPath(1, 5));

        g.addEdge(4, 5);  // Make a longer path.
        printPath(g.findMaxPath(1, 5));
    }

    private static void printPath(final List<Integer> path) {
        System.out.println("Path:");
        if (null != path) {
            for (Integer p : path) {
                System.out.println(" " + p);
            }
        } else {
            System.out.println(" null");
        }
    }
}

To convert it into a non-recursive method, you can use a List as a Stack. Where findMaxPath() calls itself, instead you would push() the current node on the stack and use the next one, when that's done pop() the node and continue. Put all that in a loop, and it should work.

Maximum path length between two vertices in a DAG

1 Answers