Thursday, November 27, 2014

Warshall algorithm in Graph in Java.

In directed graph if we starts from a vertex we may not be able to reach some vertices. For example consider below graph, if we start from vertex D we can only reach C other vertices are unreachable from D. In some graph applications we need to know which vertices we can reach if we starts from a particular vertex.

Fig 1
Using Warshall algorithm we can modify adjacency matrix of graph to generate transistive closure of graph using which we can know what all vertices are reachable from a particular vertex. For finding transistive closure using warshall algorithm we modify adjacency matrix whenever we find transitive property between vertices for connections. For example in above graph there is an edge from A to D and another edge from D to C, so there is path from A to C and we modify entry for row A and column C in adjacency matrix to indicate connection.

Consider below directed graph. Using below java code for warshall algorithm we will find transistve closure for below graph.
Fig 2


Java code:
001 /*Warshall Algorithm to find Transistive Closure 
002  * of a Directed Graph.
003  * @author Anuj
004  * */
005 public class Warshall {
006         private Graph graph;
007         
008         /*
009          * Adding vertices and Edges to 
010          * graph.
011          * */
012         private void setGraph(){
013                 graph = new Graph(5);
014                 graph.addVertex('A');
015                 graph.addVertex('B');
016                 graph.addVertex('C');
017                 graph.addVertex('D');
018                 graph.addVertex('E');
019                 
020                 graph.addEdge(0, 1);
021                 graph.addEdge(1, 2);
022                 graph.addEdge(2, 4);
023                 graph.addEdge(3, 1);
024                 graph.addEdge(3, 4);
025         }
026         
027         /*
028          * In this method warshall algorithm runs.
029          *Adjacency Matrix of a directed graph is modified to 
030          *generate transistive closure of graph. 
031          * */
032         private void warshallAlgo(){
033                 int numVerts = graph.numVerts;
034                 
035                 for (int k = 0; k < numVerts; k++) {
036                         for (int i = 0; i < numVerts; i++) {
037                                 if(graph.adjMatrix[i][k]==0){
038                                         continue;
039                                 }
040                                 for (int j = 0; j < numVerts; j++) {
041                                         if(graph.adjMatrix[k][j]==1){
042                                                 graph.adjMatrix[i][j] = 1;
043                                         }
044                                 }
045                         }
046                 }
047         }
048 
049         public static void main(String[] args) {
050                 Warshall warshall = new Warshall();
051                 warshall.setGraph();
052                 System.out.println("Adjacency matrix of Graph is:");
053                 warshall.graph.displayMatrx(warshall.graph.adjMatrix);
054                 System.out.println();
055                 warshall.warshallAlgo();
056                 //Adjacency matrix is modified to generate transistive closure 
057                 //in method warshallAlgo().
058                 System.out.println("Transistive Closure of Graph is:");
059                 warshall.graph.displayMatrx(warshall.graph.adjMatrix);
060         }
061 }
062 
063 
064 class Graph{
065      int maxVertsNum;
066          int numVerts;
067          Vertex [] vertexList;
068          int [][] adjMatrix;
069         
070         public Graph(int maxVerts){
071                 maxVertsNum = maxVerts;
072                 numVerts = 0;
073                 vertexList = new Vertex[maxVertsNum];
074                 adjMatrix = new int[maxVertsNum][maxVertsNum];
075                 //Initializing all entries to zero.
076                 for (int i = 0; i < maxVertsNum; i++) {
077                         for (int j = 0; j < maxVertsNum; j++) {
078                                 adjMatrix[i][j] = 0;
079                         }
080                 }
081         }
082         
083         public void addVertex(char label){
084                 if(numVerts < maxVertsNum){
085                         vertexList[numVerts++] = new Vertex(label);
086                 }
087         }
088         
089         /*
090          * Adding an edge to a directed graph.
091          * */
092         public void addEdge(int start, int end){
093                 if(start < numVerts && end < numVerts){
094                         adjMatrix[start][end] = 1;
095                 }
096         }
097         
098         public void display(int idx){
099                 System.out.print(vertexList[idx].label);
100         }
101         
102         /*
103          * Method to display 2-D array in row 
104          * and column form with labels of vertices in 
105          * row and column.
106          * */
107         public void displayMatrx(int [][] array){
108                 System.out.print("  ");
109                 for (int i = 0; i < numVerts; i++) {
110                         System.out.print(vertexList[i].label+" ");
111                 }
112                 System.out.println();
113                 for (int i = 0; i < numVerts; i++) {
114                         System.out.print(vertexList[i].label+" ");
115                         for (int j = 0; j < numVerts; j++) {
116                                 System.out.print(array[i][j]+" ");
117                         }
118                         System.out.println();
119                 }
120         }
121 }
122 
123 class Vertex{
124         char label;
125         
126         public Vertex(char label){
127                 this.label = label;
128         }
129 }
Java2html

Output: 
Adjacency matrix of Graph is:
  A B C D E 
A 0 1 0 0 0 
B 0 0 1 0 0 
C 0 0 0 0 1 
D 0 1 0 0 1 
E 0 0 0 0 0 

Transistive Closure of Graph is:
  A B C D E 
A 0 1 1 0 1 
B 0 0 1 0 1 
C 0 0 0 0 1 
D 0 1 1 0 1 
E 0 0 0 0 0

Explanation:
In warshall algorithm for finding transitive closure of graph we modify adjacency matrix of graph. For example in Fig 2 graph if there is an edge from A to B and another edge from B to C then A and C are connected and we modify entry in adjacency matrix to enter 1 for row A and column C. In above code method warshallAlgo contains logic for warshall algorithm. There are 3 for loops used in warshall algorithm. Vertex represented by outermost for loop using int variable k acts as intermediate vertex like B in example I just mentioned above that is connected with 2 different vertex. In 1st inner for loop with i as loop variable we check for all vertices if there is an edge to vertices represented by outermost loop i.e. an edge from i to k, if there is no edge we do not go to 2nd inner for loop and continue with next iteration of 1st inner for loop. 2nd inner loop having j as loop variable is entered only when there is an edge from i to k. In 2nd for loop we check if there is an edge from vertices of outermost for loop to in the direction of vertices of 2nd inner for loop i.e. an edge from k to j. If there an edge from k to j thats mean i to j is a connected path and we modify adjacency matrix entry for row i and column j.
Warshall algorithm has time complexity of O(N^3). But after transistive closure has been generated it will take only O(1) time to find if a vertex is reachable from a particular vertex.
Posted by at No comments:

Tuesday, November 25, 2014

Breadth First Search (BFS) in a Graph in Java.

BFS like DFS is a way to traverse the graph. In BFS algorithm the graph is traversed as close as possible to the root node. Queue is used in the implementation of the breadth first search.We visit all the vertices that are at the distance of one edge away from current vertex. Then for each of those vertices that are one edge away it explores their unvisited vertices that are one edge away.

In BFS starting vertex is visited and inserted at end of queue then we keep on doing below 2 steps until queue is empty.
1. Remove an item from head of queue and make it current vertex
2. Visit all adjacent unvisited vertices of current vertex one by one and add them to end of queue. When there is no unvisited vertex left we follow step 1.



In above graph for BFS we starts at vertex A and visit all unvisited vertices that are one edge away from A and insert them to queue. Vertices that are inserted in queue are BFHI. After that we remove vertex at head of queue i.e. B and make it current vertex and visit its adjacent vertices and add them to queue. Queue content after we visit all of B adjcaent unvisited vertices is FHICD. Then we remove F and make it current vertex and we keep on repeating above 2 steps for BFS. Final order in which vertices are visited is ABFHICDGJE.

Java Code For BFS:


 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
import java.util.LinkedList;
import java.util.Queue;

public class BFS {
 private GraphAdjacencyMatrix graph;
 private Queue<Integer> queue;

 public BFS(){
  queue = new LinkedList<Integer>();
 }
 
 public void bfs(){
  graph.vertexList[0].isVisited = true;
  graph.display(0);
  queue.add(0);
  
  while(!queue.isEmpty()){
   int vert = queue.remove();
   int idx;
   
   while((idx=getAdjUnvistedVertex(vert))!=-1){
    graph.vertexList[idx].isVisited = true;
    graph.display(idx);
    queue.add(idx);
   }
  }
 }
 
 public int getAdjUnvistedVertex(int vert){
  for (int i = 0; i < graph.vertexList.length; i++) {
   if(graph.adjMatrix[vert][i] == 1 && !graph.vertexList[i].isVisited){
    return i;
   }
  }
  return -1;
 }
 
 public void setGraph(){
  graph = new GraphAdjacencyMatrix(10);
  graph.addVertex('A');
  graph.addVertex('B');
  graph.addVertex('C');
  graph.addVertex('D');
  graph.addVertex('E');
  graph.addVertex('F');
  graph.addVertex('G');
  graph.addVertex('H');
  graph.addVertex('I');
  graph.addVertex('J');
  
  graph.addEdge(0, 1);
  graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(3, 4);
  graph.addEdge(0, 5);
  graph.addEdge(5, 6);
  graph.addEdge(0, 7);
  graph.addEdge(0, 8);
  graph.addEdge(8, 9);
 }
 
 public static void main(String[] args) {
  BFS bfsObj = new BFS();
  bfsObj.setGraph();
  bfsObj.bfs();
 }
} 
 
Output:
ABFHICDGJE
Posted by at No comments:

Depth First Search (DFS) in a Graph in Java.

DFS is a way to traverse the graph. To traverse a graph means to visit the vertices of graph in some systematic order. In this algorithm we select a root node or starting node and traverse the graph in such a way that it tries to go far from the root node. For implementing DFS stack is used and knowledge of below 3 stack operations is required to understand dfs  program in this tutorial.
Stack operations:
1. push: add an item on the top of stack.
2. peek: return the value of topmost item on stack without removing it.
3. pop: remove topmost item and return its value

DFS starts from a vertex, marks it visited and push this vertex on stack. Then it keeps on doing following 2 steps until stack is empty.
1. Peek at top of stack to get a vertex and visit its adjacent unvisited vertex and push that vertex on stack.
2. If a vertex that is peeked does not have adjacent unvisited vertex then pop that vertex of stack and again peek at top of stack and find its adjacent unvisited vertex.

In below graph when dfs is applied vertices are visited in order ABCDEFGHIJ. Starting vertex is A and it is marked as visited and pushed on stack then we visit adjacent unvisited vertex of A which B and it is also pushed on stack. Then C is visited, which is adjacent to B and unvisited and pushed on stack and since C does not have any adjacent unvisited vertex it is popped off from stack. Now we have B on top of stack and we again check next adjacent unvisited vertex of B which is D and it is pushed on to stack. After we keep on following above 2 steps for dfs we get desired output.

Java code for dfs is given below. Above graph is represented in below code for dfs. I have used graph code from my previous post on representation of graph.



 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
public class DFS {
 private GraphAdjacencyMatrix graph;
 private Stack<Integer> stack;
 
 public DFS(){
  stack = new Stack<Integer>();
 }
 
 public void dfs(){
  graph.vertexList[0].isVisited = true;
  graph.display(0);
  stack.push(0);
  int vert;
  int idx;
  
  while(!stack.isEmpty()){
   vert = stack.peek();
   
   if((idx=getAdjUnvistedVertex(vert))!=-1){
    graph.vertexList[idx].isVisited = true;
    graph.display(idx);
    stack.push(idx);
   }else{
    stack.pop();
   }
  }
 }
 
 public int getAdjUnvistedVertex(int vert){
  for (int i = 0; i < graph.vertexList.length; i++) {
   if(graph.adjMatrix[vert][i] == 1 && !graph.vertexList[i].isVisited){
    return i;
   }
  }
  return -1;
 }
 
 public void setGraph(){
  graph = new GraphAdjacencyMatrix(10);
  graph.addVertex('A');
  graph.addVertex('B');
  graph.addVertex('C');
  graph.addVertex('D');
  graph.addVertex('E');
  graph.addVertex('F');
  graph.addVertex('G');
  graph.addVertex('H');
  graph.addVertex('I');
  graph.addVertex('J');
  
  graph.addEdge(0, 1);
  graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(3, 4);
  graph.addEdge(0, 5);
  graph.addEdge(5, 6);
  graph.addEdge(0, 7);
  graph.addEdge(0, 8);
  graph.addEdge(8, 9);
 }
 
 public static void main(String[] args) {
  DFS dfsObj = new DFS();
  dfsObj.setGraph();
  dfsObj.dfs();
 }
}
Output:
ABCDEFGHIJ

In above program in while loop of method dfs() we keep on checking if stack is empty. If stack is not empty we peek on vertex present on top of stack and get its adjacent unvisited vertex using method getAdjUnvistedVertex. After that vertex isVisited variable is marked true so that program remember we have visited that vertex and it is printed on output and pushed on stack. If a vertex does not have any adjacent unvisited vertex we pop it from stack. For finding adjacent unvisited vertex inside method getAdjUnvistedVertex there is if condition inside for loop
if(graph.adjMatrix[vert][i] == 1 && !graph.vertexList[i].isVisited){
if graph.adjMatrix[vert][i] == 1  it means there is edge between vert and i, where vert is vertex currently on top of stack and vertex i is checked if it is visited or not using !graph.vertexList[i].isVisited if both conditions are true that vertex is returned as adjacent unvisted vertex.


Posted by at No comments:

Monday, November 24, 2014

Graph representation using adjacency matrix and adjacency list in Java.

In computer science graphs are data structures that can be used to model many types of physical problems. Graph is a collection of vertices and edges, edge represent connection between two vertices. For example, in a graph representing a city various vertices can represent important landmarks of city and edges can represent roads connecting various landmarks.

Below are few graph terms-
Adjacent - A vertex is said to be adjacent to another vertex if it connected by single edge.
Fig 3.0


 For example in above graph vertices adjacent to A are B and C.
Similarly A and C are adjacent to vertex A.

Paths - It is sequence of various connected edges. For example in above figure ACD, ABCD are various paths.

Connected Graph - A graph is said to be connected if there exist a path from any vertex to any other vertex of graph. Graph represented by Fig. 3.0 is connected graph.

Disconnected Graph - A graph is said to be disconnected if it is not connected i.e. if we start from one vertex of graph and we can not reach some vertices thats means there is no connection with those vertices. Below figure is example of disconnected graph, if we start from A we can not reach B and D. Similarly if we start from B or D we can not reach A and C.
Fig. 3.1

Directed Graph -  A Graph is said to be directed if edges have direction.
Fig. 3.2
Fig. 3.2 is an example of directed graph. Edge AB has direction i.e. you can go from A to B but not from B to A. Fig. 3.0 and Fig. 3.1 are example of undirected graph, you can go either way in edge of undirected graph. In fig. 3.0 for edge AB we can go A to B or B to A.

Weighted Graph - In weighted graph every edge has some weight.
Fig. 3.3
If vertices in above graphs represent places in a city then edges weight can represent distance in Km. between those places or may be it can represent cost of ticket between those places.

Java code to represent a Graph.
There are two different ways to represent edges of a graph in programming - adjacency matrix and adjacency lists. I will be discussing both these methods in this post.

Representation using Adjacency matrix. 


 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
public class GraphAdjacencyMatrix {
 protected int maxVertsNum;
 protected int numVerts;
 protected Vertex [] vertexList;
 protected int [][] adjMatrix;
 
 public GraphAdjacencyMatrix(int maxVerts){
  maxVertsNum = maxVerts;
  numVerts = 0;
  vertexList = new Vertex[maxVertsNum];
  adjMatrix = new int[maxVertsNum][maxVertsNum];
  //Initializing all entries to zero.
  for (int i = 0; i < maxVertsNum; i++) {
   for (int j = 0; j < maxVertsNum; j++) {
    adjMatrix[i][j] = 0;
   }
  }
 }
 
 public void addVertex(char label){
  if(numVerts < maxVertsNum){
   vertexList[numVerts++] = new Vertex(label);
  }
 }
 
 public void addEdge(int start, int end){
  if(start < numVerts && end < numVerts){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
  }
 }
 
 public boolean hasEdge(int src, int dest){
  return adjMatrix[src][dest]==1;
 }
 
 public boolean isVertexVisited(int vertex){
  return vertexList[vertex].isVisited;
 }
 
 public void display(int idx){
  System.out.print(vertexList[idx].label);
 }
 
 public void displayAllEdges(){
  System.out.println("All edges are:");
  for (int i = 0; i < numVerts; i++) {
   for (int j = 0; j < numVerts; j++) {
    if(adjMatrix[i][j]==1){
     System.out.print(vertexList[i].label+""+vertexList[j].label);
     System.out.print(" ");
    }
   }
  }
  System.out.println();
 }

 public static void main(String[] args) {
  GraphAdjacencyMatrix graph = new GraphAdjacencyMatrix(5);
  graph.addVertex('A'); //0
  graph.addVertex('B'); //1
  graph.addVertex('C'); //2
  graph.addVertex('D'); //3
  
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 2);
  graph.addEdge(2, 3);
  
  graph.displayAllEdges();
  
  System.out.println("Is there an edge between "+graph.vertexList[0].label+" and "+graph.vertexList[2].label+" = "+graph.hasEdge(0, 2));
  System.out.println("Is there an edge between "+graph.vertexList[1].label+" and "+graph.vertexList[3].label+" = "+graph.hasEdge(1, 3));
 }
}

class Vertex{
 public char label;
 public boolean isVisited = false;
 
 public Vertex(char label){
  this.label = label;
 }
}
Output:
All edges are:
AB AC BA BC CA CB CD DC
Is there an edge between A and C = true
Is there an edge between B and D = false

Explanation:
Below table represent adjacency matrix of graph that is made in above program and fig 3.0 represent same graph.  2-D array adjMatrix is used to hold connection between various vertices. For example there is connection between AB and BA so 1 is present in row A column B and row B column A. Since this adjacency matrix is for undirected graph so both AB and BA is 1. There is no connection between A and D so row A and column D has 0. Whenever we add an edge between 2 vertices in graph the corresponding value in adjacency matrix is set to 1 in addEdge method.


Representation of Graph using Adjacency List:
In adjacency list approach for each vertex we have a list that contains all of its adjacent vertices.

Java Code:


 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
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class GraphAdjacencyList {
 private List<List<Integer>> adjList;
 private int maxVerts;
 private int numVerts;
 private Vertex[] vertList;
 
 public GraphAdjacencyList(int maxVerts){
  this.maxVerts = maxVerts;
  numVerts = 0;
  adjList = new ArrayList<List<Integer>>();
  vertList = new Vertex[maxVerts];
  for (int i = 0; i < maxVerts; i++) {
   adjList.add(new LinkedList<Integer>());
  }
 }

 public void addVertex(char label){
  if(numVerts < maxVerts){
   vertList[numVerts++] = new Vertex(label);
  }
 }
 
 public void addEdge(int src, int dest){
  if(src < numVerts && dest < numVerts){
   adjList.get(src).add(dest);
   adjList.get(dest).add(src);
  }
 }
 
 public boolean hasEdge(int src, int dest){
  return adjList.get(src).contains(dest);
 }
 
 public void display(int idx){
  System.out.print(vertList[idx].label);
 }
 
 public void displayAllEdges(){
  for (int i = 0; i < adjList.size(); i++) {
   List<Integer> adjVertex = adjList.get(i);
   for (int j = 0; j < adjVertex.size(); j++) {
    System.out.print(""+vertList[i].label+""+vertList[adjVertex.get(j)].label+" ");
   }
  }
  System.out.println();
 }
 
 public static void main(String[] args) {
  GraphAdjacencyList graph = new GraphAdjacencyList(5);
  graph.addVertex('A'); //0
  graph.addVertex('B'); //1
  graph.addVertex('C'); //2
  graph.addVertex('D'); //3
  
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 2);
  graph.addEdge(2, 3);
  
  graph.displayAllEdges();
  
  System.out.println("Vertices adjacent to "+graph.vertList[0].label+" are ");
  List<Integer> list = graph.adjList.get(0);
  for (int i = 0; i < list.size(); i++) {
   System.out.print(graph.vertList[list.get(i)].label);
  }
 }
}
Output:
AB AC BA BC CA CB CD DC
Vertices adjacent to A are
BC

Explanation:
For every vertex we have list that contains adjacent vertices to that vertex. Whenever an edge is added between 2 vertices the destination vertex is added to adjacency list of source vertex. The vertices adjacent to various vertex are:
Vertex            Adjacent vertices in adjacency list
A         -         B, C
B         -         A, C
C         -         A, B D
D         -         C

 When to use Adjacency matrix and Adjacency list:
1. In adjacency matrix approach space usage is proportional to V^2 where V is number of vertices in graph. So if graph is sparse i.e. it has less number of edges between various vertices then adjacency matrix approach will result in waste of space because in adjacency matrix of sparse graph lot of entries will be 0 indicating no connection. So if in sparse graph we use adjacency list approach we will be storing only vertcies that are connected to given vertex in a list for that vertex. In adjacency list approach space is proportional to both total edges and vertices. So if we have sparse array it will be better to use adjacency list to save space.

2. In adjacency matrix approach operation to check whether there is an edge between 2 vertices is fast and it take O(1) time because for that we have to check entry in array, where is in adjacency list approach we have to iterate over list to find if there is an edge between 2 vertices so it is slow and takes O(V) time. So if we need fast time to check if there is edge between 2 particular vertices then adjacency matrix approach is better.
Posted by at 1 comment:
Subscribe to: Posts (Atom)