Longest Path in a Directed Acyclic Graph (DAG). | Solution in Java

Dear friends,

I am here with you with yet another problem. Given a Directed Acyclic Graph how can we compute the longest path from any source.

This post is based upon the post from geeksfrogeeks.org :
http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

I have also solved same problem using adjacency matrix :
 http://krishnalearnings.blogspot.in/2015/08/code-in-java-for-finding-longest-path.html

In the below solution, I have used adjacency list.

I have implemented my own Stack (exceptions like stack full, stack empty have not been taken care, considering careful usage of stack in the solution )

Below is a DAG, lets find the longest path from Node with value '2'.

public class LongestPath {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(1, 2, 5);
        graph.addEdge(1, 3, 3);
        graph.addEdge(2, 4, 6);
        graph.addEdge(2, 3, 2);
        graph.addEdge(3, 5, 4);
        graph.addEdge(3, 6, 2);
        graph.addEdge(3, 4, 7);
        graph.addEdge(4, 6, 1);
        graph.addEdge(4, 5, -1);
        graph.addEdge(5, 6, -2);
        graph.findLongestPath(2);

    }

    public static class Graph {
        Vertex[] vertices;
        int size;
        int maxSize;
        Stack stack;

        public Graph(int maxSize) {
            vertices = new Vertex[maxSize];
            this.maxSize = maxSize;
            stack = new Stack(maxSize);
            for (int i = 0; i < maxSize; i++) {
                addVertex(i + 1);
            }
        }

        public void addVertex(int data) {
            vertices[size++] = new Vertex(data);
        }

        public void addEdge(int source, int destination, int weight) {
            vertices[source - 1].adj = new Neighbour(destination - 1, weight, vertices[source - 1].adj);
        }

        public class Vertex {
            int data;
            Neighbour adj;
            int cost =  Integer.MIN_VALUE;
            State state = State.NEW;

            public Vertex(int data) {
                this.data = data;
            }
        }

        public class Stack {
            Vertex[] stack;
            int maxSize;
            int size;

            public Stack(int maxSize) {
                this.maxSize = maxSize;
                stack = new Vertex[maxSize];
            }

            public void push(Vertex data) {
                stack[size++] = data;
            }

            public Vertex pop() {
                return stack[--size];
            }

            public boolean isEmpty() {
                return size == 0;
            }
        }

        public enum State {
            NEW, VISITED
        }

        public class Neighbour {
            int index;
            Neighbour next;
            int weight;

            Neighbour(int index, int weight, Neighbour next) {
                this.index = index;
                this.next = next;
                this.weight = weight;
            }
        }

        public void findLongestPath(int source) {
            applyTopologicalSort();
            vertices[source-1].cost = 0;
            while (!stack.isEmpty()) {
                Vertex u = stack.pop();
                if(u.cost != Integer.MIN_VALUE){
                    Neighbour temp = u.adj;
                    while(temp != null){
                        Vertex v = vertices[temp.index];
                        if(v.cost < (temp.weight+u.cost)){
                            v.cost = temp.weight+u.cost;
                        }
                        temp = temp.next;
                    }
                }
            }
            System.out.println("Longest distances...");
            
            for(int i = 0; i < maxSize; i++){
                System.out.println("Longest path from 2 to " + (i+1)+ " "+vertices[i].cost);
            }
        }

        private void applyTopologicalSort() {
            for (int i = 0; i < maxSize; i++) {
                if (vertices[i].state != State.VISITED) {
                    dfs(vertices[i]);
                }
            }
        }

        public void dfs(Vertex u) {
            Neighbour temp = u.adj;
            u.state = State.VISITED;
            while (temp != null) {
                Vertex v = vertices[temp.index];
                if (v.state == State.NEW) {
                    dfs(v);
                }
                temp = temp.next;
            }
            stack.push(u);
        }
    }

}

Code in Java for finding Longest Path in Directed Acyclic Graph | Using Topological sorting

Dear Friends,

I am here with you with a problem based on Directed A-cyclic Graph [DAG].

Given a DAG, we are supposed to find the longest path in it.

Friends Please find below the code in java for this problem.

package com.learn.dag.longest.path;

public class LongestPathInDAG {
    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 5, 1);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);
        int s = 1;
        g.findLongestPath(s);
    }

    public static class Graph {
        private int V;
        private int[][] matrix;
        private int[] vertices;
        private boolean[] visited;
        private int[] distances;
        private int[] predecessor;
        private Stack stack;

        public Graph(int V) {
            this.V = V;
            vertices = new int[V];
            visited = new boolean[V];
            predecessor = new int[V];
            distances = new int[V];
            matrix = new int[V][V];
            stack = new Stack(V);
            for (int i = 0; i < V; i++) {
                addVertex(i);
                distances[i] = Integer.MIN_VALUE;
                predecessor[i] = -1;
            }
        }

        private void addVertex(int name) {
            vertices[name] = name;
        }

        public void addEdge(int source, int destination, int weight) {
            matrix[source][destination] = weight;
        }

        public void findLongestPath(int source) {
            invokeTopologicalSort();
            distances[source] = 0; // Initialize source with 0
            updateMaxDistanceForAllAdjVertices(); // for all nodes connected,
                                                    // directly or indirectly,
                                                    // with source will have
                                                    // their distances
                                                    // calculated
            printDistances(source);
            printPath(source);
        }

        private void printDistances(int source) {
            System.out.println("Distances from source " + source + " are as follows: ");
            for (int to = 0; to < V; to++) {
                int distance = distances[to];
                System.out.print("from " + source + " to " + to + ": ");
                if (distance == Integer.MIN_VALUE) {
                    System.out.println(" -Infinity ");
                } else {
                    System.out.println(distance + " ");
                }
            }
            System.out.println();
        }

        private void printPath(int source) {
            System.out.println("Path from source " + source + " to other nodes are as follows: ");
            for (int i = 0; i < V; i++) {
                if (distances[i] == Integer.MIN_VALUE) {
                    System.out.println("No Path from " + source + " to " + i);
                } else if (i != source) {
                    int from = predecessor[i];
                    System.out.print("Path from " + source + " to " + i + ": ");
                    if (from == source) {
                        System.out.print(from + " ");
                    }
                    while (from != source) {
                        System.out.print(from + " ");
                        from = predecessor[from];
                    }
                    System.out.print(i + " ");
                    System.out.println();
                }
            }
        }

        private void updateMaxDistanceForAllAdjVertices() {
            while (!stack.isEmpty()) {
                int from = stack.pop();
                if (distances[from] != Integer.MIN_VALUE) {
                    for (int adjacent = 0; adjacent < V; adjacent++) {
                        if (matrix[from][adjacent] != 0) {
                            if (distances[adjacent] < distances[from] + matrix[from][adjacent]) {
                                predecessor[adjacent] = from;
                                distances[adjacent] = distances[from] + matrix[from][adjacent];
                            }
                        }
                    }
                }
            }
        }

        private void invokeTopologicalSort() {
            for (int i = 0; i < V; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }
        }

        private void dfs(int source) {
            visited[source] = true;
            for (int adjacent = 0; adjacent < V; adjacent++) {
                if (matrix[source][adjacent] != 0 && !visited[adjacent]) {
                    dfs(adjacent);
                }
            }
            stack.push(source);
        }

    }

    public static class Stack {
        private int maxSize;
        private int[] stack;
        private int top = -1;
        private int size = 0;

        public Stack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }

        public void push(int item) {
            stack[++top] = item;
            size++;
        }

        public int pop() {
            int item = stack[top--];
            size--;
            return item;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }
}