Friday, 21 November 2014
Sunday, 16 November 2014
Longest and Shortest path from a given source vertex to all vertices
Shortest Path:
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:
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 + " "); } }
|
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 :
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
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
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); } }
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.
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; } }
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.
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; }
Subscribe to:
Posts (Atom)