Friday 21 November 2014

Java Collections

Posted by at No comments:
Labels:

Java Concurrency and Threading

Posted by at No comments:
Labels:

Sunday 16 November 2014

Longest and Shortest path from a given source vertex to all vertices

Shortest Path:
For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.
We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.

 Longest path:
We initialize distances to all vertices as minus infinite and distance to source as 0, then we find topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
Reference :: GeeksforGeeks

 Java implementation:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
package g4g.Graph;/**
 * Created by seesunda on 11/15/2014.
 */

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.InputStream;

class AdjNode {
    int v;
    int weight;

    AdjNode(int v,int w) {
        this.v = v;
        this.weight = w;
    }
}

class Pathgraph {
    int v;
    ArrayList<AdjNode>[] alist;
    int[] indegree;

    Pathgraph(int v) {
        this.v = v;
        this.alist = new ArrayList[v];
        this.indegree = new int[v];
    }

    public void initilaize(){
        for(int i=0;i<alist.length;i++)
            alist[i] = new ArrayList<AdjNode>();
    }

    public void addEdge(int u,int v,int weight) {
        AdjNode node = new AdjNode(v,weight);
        alist[u].add(node);
        indegree[v]++;
    }

    public ArrayList<Integer> TopoSort() {
        Queue<Integer> q = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        boolean[] visited = new boolean[alist.length];

        for(int i=0;i<indegree.length;i++) {
            if(indegree[i] == 0) { q.add(i);  visited[i] = true; break;}
        }

        while(!q.isEmpty()) {
            int u = q.poll();

            result.add(u);
            for(int i=0;i<alist[u].size();i++) {
                AdjNode n = alist[u].get(i);
                int v = n.v;
                indegree[v]--;
            }

            for(int i=0;i<alist.length;i++) {
                if(!visited[i] && indegree[i] == 0) { q.add(i); visited[i] = true;}
            }
        }

        return result;
    }

    public int[] longestPath(int s) {
        int[] dist = new int[alist.length];
        Arrays.fill(dist,Integer.MIN_VALUE);

        dist[s] = 0;

        ArrayList<Integer> topoOrder = TopoSort();
        for(int i=s;i<topoOrder.size();i++) {
            int u = topoOrder.get(i);
            //System.out.println(u);
            for(int j=0;j<alist[u].size();j++) {
                AdjNode node = alist[u].get(j);
                int v = node.v;
                int weight = node.weight;
                //System.out.println(v + " " + weight);
                if(dist[v] < dist[u] + weight ) dist[v] = dist[u]+weight;
            }
        }

        return dist;

    }

    public int[] shortestPath(int s) {
        int[] dist = new int[alist.length];
        Arrays.fill(dist,Integer.MAX_VALUE);

        dist[s] = 0;

        ArrayList<Integer> topoOrder = TopoSort();
        for(int i=s;i<topoOrder.size();i++) {
            int u = topoOrder.get(i);
            //System.out.println(u);
            for(int j=0;j<alist[u].size();j++) {
                AdjNode node = alist[u].get(j);
                int v = node.v;
                int weight = node.weight;
                //System.out.println(v + " " + weight);
                if(dist[v] > dist[u] + weight ) dist[v] = dist[u]+weight;
            }
        }

        return dist;

    }

    public static void main(String[] args) {
        Pathgraph g = new Pathgraph(6);
        g.initilaize();
        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;
        System.out.println("Longest distances from source vertex " );
        int[] lPath = g.longestPath(s);
        for(int k : lPath)
            System.out.print(k + " ");
        System.out.println();

        Pathgraph g1 = new Pathgraph(6);
        g1.initilaize();
        g1.addEdge(0, 1, 5);
        g1.addEdge(0, 2, 3);
        g1.addEdge(1, 3, 6);
        g1.addEdge(1, 2, 2);
        g1.addEdge(2, 4, 4);
        g1.addEdge(2, 5, 2);
        g1.addEdge(2, 3, 7);
        g1.addEdge(3, 4, -1);
        g1.addEdge(4, 5, -2);
        System.out.println("Shortest distances from given source vertex " );
        int[] sPath = g1.shortestPath(s);
        for(int k : sPath)
            System.out.print(k + " ");
    }
}
 

























Posted by



at





No comments:
  


















Labels:

















          

        

          

        

Saturday 15 November 2014


          

        









Topological Sorting - SPOJ pblm PFDEP Solution in Java












Topological sorting: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.



Applications:

Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization



Reference Video:

https://www.youtube.com/watch?v=W9cfpsPJwhc&index=50&list=PLLH73N9cB21W1TZ6zz1dLkyIm50HylGyg


Problem from SPOJ:

http://www.spoj.com/problems/PFDEP/



Solution :






public void solve(int testNumber, PFDEPInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int n = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[n];
        for(int i=0;i<n;i++) alist[i] = new ArrayList<Integer>();
        int[] indegree = new int[n];

        int m = in.nextInt();
        while(m-- > 0) {
            int v = in.nextInt()-1;
            int k = in.nextInt();
            indegree[v] += k;
            while(k-->0) {
                alist[in.nextInt()-1].add(v);
            }
        }
        ArrayList<Integer> result = TopoSort(alist,indegree);
        int i=0;
        for(i=0;i<result.size()-1;i++) out.print(result.get(i) + " ");
        out.print(result.get(i));
    }

    public ArrayList<Integer> TopoSort(ArrayList<Integer>[] alist,int[] indegree){
        Queue<Integer> q = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        boolean[] visited = new boolean[alist.length];

        for(int i=0;i<indegree.length;i++) {
            if(indegree[i] == 0) { q.add(i);  visited[i] = true; break;}
        }

        while(!q.isEmpty()) {
            int u = q.poll();
            result.add(u+1);

            for(int i=0;i<alist[u].size();i++) {
                int v = alist[u].get(i);
                indegree[v]--;
            }

            for(int i=0;i<alist.length;i++) {
                if(!visited[i] && indegree[i] == 0) { q.add(i); visited[i] = true; break;}
            }
        }
        return result;
    }
}







Time Complexity: O(V+E) - V - no of vertices and E - no of Edges














Posted by



at





No comments:
  


















Labels:

















          

        

          

        

Friday 14 November 2014


          

        









Graph : Depth First Traversal and Breadth First Traversal for connected Graphs in Java












Assumption : Given Graph is connected.



PS : For Traversal in Disconnected Graph, refer the post of Detecting Cycle in Graph










import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class TGraph {

    int v;
    ArrayList<Integer>[] alist;
    boolean[] visited;


    TGraph(int v) {
        this.v = v;
        this.alist = new ArrayList[v];
        this.visited = new boolean[v];
    }

    public void initList(){
        for(int i=0;i<alist.length;i++)
            alist[i] = new ArrayList<Integer>();
    }

    public void addEdge(int u,int v) {
        alist[u].add(v);
    }

    public void BFS(int u) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(u);
        while(!q.isEmpty()) {
            int v = q.poll();
            visited[v] = true;
            for(int i=0;i<alist[v].size();i++) {
              int n = alist[v].get(i);
                if(!visited[n]) q.add(n);
            }
            System.out.print(v + " ");
        }
    }


    public void DFS(int u) {
        visited[u] = true;
        System.out.print(u + " ");
        for(int i=0;i<alist[u].size();i++) {
            int v = alist[u].get(i);
            if(!visited[v]) DFS(v);
        }
    }

    public static void main(String[] args) {
        TGraph g= new TGraph(4);
        g.initList();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("Breadth First Traversal (starting from vertex 2)");
        g.BFS(2);
        System.out.println();


        System.out.println("Depth First Traversal (starting from vertex 2)");
        TGraph g1 = new TGraph(4);
        g1.initList();
        g1.addEdge(0, 1);
        g1.addEdge(0, 2);
        g1.addEdge(1, 2);
        g1.addEdge(2, 0);
        g1.addEdge(2, 3);
        g1.addEdge(3, 3);
        g1.DFS(2);
    }


}















Posted by



at





No comments:
  


















Labels:

















          

        

          

        

Thursday 13 November 2014


          

        









Detecting Cycle in Directed Graph - DFS 












Back Edge : A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS



Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. 



Keep track of the vertices already visited by DFS Traversal. While traversing further, if we visit any of the vertex that is already visited then there is a back edge and hence there is cycle in the graph.







public void solve(int testNumber, CycleDirInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int v = in.nextInt();
        int e = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[v];
        for(int i=0;i<v;i++) alist[i] = new ArrayList<Integer>();
        while(e-->0) {
            int n1 = in.nextInt();
            int n2 = in.nextInt();
            alist[n1].add(n2);
            //alist[n2].add(n1);
        }
        boolean[] visited = new boolean[v];
        boolean[] explored = new boolean[v];

        if(hasCycleUtil(v,alist,visited,explored)) {
            System.out.println("Contains Cycle");
        }
        else
            System.out.println("Nocycle");
    }

    public boolean hasCycleUtil(int v,ArrayList<Integer>[] alist,boolean[] visited,boolean[] explored) {
        for(int i=0;i<v;i++) {
            if(!visited[i]) {
                if(hasCycle(i,alist,visited,explored)) return true;
            }
        }
        return false;
    }

    public boolean hasCycle(int v,ArrayList<Integer>[] alist,boolean[] visited,boolean[] explored) {
        visited[v] = true;
        explored[v] = true;

        for(int i=0;i<alist[v].size();i++) {
            int n = alist[v].get(i);
            if(!visited[n]) {
                if(hasCycle(n,alist,visited,explored)) return true;
            }
            else if(explored[n]) return true;
        }

        explored[v] = false;
        return false;
    }
}












Posted by



at





No comments:
  


















Labels:

























Detecting Cycle in undirected Graph or Check if the given graph is tree.












We can use DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. 



Assumption ::There are no parallel edges between any two vertices.











public void solve(int testNumber, EvenTreeInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int v = in.nextInt();
        int e = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[v];
        for(int i=0;i<v;i++) alist[i] = new ArrayList<Integer>();
        while(e-->0) {
            int n1 = in.nextInt();
            int n2 = in.nextInt();
            alist[n1-1].add(n2-1);
            alist[n2-1].add(n1-1);
        }

        boolean[] visited = new boolean[v];
        int[] parent = {-1};
        boolean[] isTree = {true};
        if(isTreeUtil(v,alist,visited,parent)){
            System.out.println("YES");
        }
        else System.out.println("NO");
    }

    public boolean isTreeUtil(int v,ArrayList<Integer>[] alist, boolean[] visited,int[] parent) {

        for(int i=0;i<v;i++) {
            if(!visited[i]) {
               if(!isTree(i, alist, visited, parent)) return false;
            }
        }
        return true;
    }

    public boolean isTree(int v,ArrayList<Integer>[] alist,boolean[] visited,int[] parent) {

        visited[v] = true;

        for(int i=0;i<alist[v].size();i++) {
            int n = alist[v].get(i);
            if(!visited[n]) {
                parent[0] = v;
                if(!isTree(n,alist,visited,parent)) return false;
            }
            else {
                if(n != parent[0]) return false;
            }
        }
        return true;
    }















Posted by



at





No comments:
  


















Labels:

















        

      









Subscribe to:
Posts (Atom)