CC-1 : Implement Bi-Directional/ Undirectional graph using Adjacency Matrix.

Description:

Create and test a custom Bi-Directional/unidirectional Graph implementation using Adjacency Matrix.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphAdjacencyMatrix gph=new GraphAdjacencyMatrix(5); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 4); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.displayGraph();	0 1 2 3 4 vertex 0 0 1 1 1 1 vertex 1 1 0 1 0 0 vertex 2 1 1 0 1 0 vertex 3 1 0 1 0 1 vertex 4 1 0 0 1 0

Next let’s see the logic involved in adding/ deleting vertex to graph.

Addition/Deletion of a vertex to Undirected Graph.

Pseudocode:

Initialize an int variable named vertices to hold the number of vertices in the graph.

Initialize a two-dimensional int array names adjacencyMatrix to hold the information of edge connections between vertices of the graph. The count of the rows and columns of the adjacencyMatrix should be same as the count of vertices in the graph. Initially data at all indexes in adjancencyMatrix will be set to 0 indicating no edges/ connections between the vertices.

Each adjacencyMatrix row index represents a vertex of the graph.

If current row vertex at row index R is connected to vertex at column index C, then adjacencyMatrix[R][C] will be set to 1, else it will be set to 0.

To add edge between vertice n1 and vertice n2, add following mapping to adjacencyMatrix, indicating a bi-directional/ Undirectional edge:

adjacencyMatrix[n1][n2]=1.

adjacencyMatrix[n2][n1]=1.

To remove edge between vertice n1 and vertice n2, remove following mapping from adjacencyMatrix:

adjacencyMatrix[n1][n2]=0.

adjacencyMatrix[n2][n1]=0.

Code:

public class GraphAdjacencyMatrix {

 private int vertices;
 private int[][] adjacencyMatrix;
 
 public GraphAdjacencyMatrix(int vertices) {
	 this.vertices=vertices;
	 adjacencyMatrix=new int[vertices][vertices];
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyMatrix[source][dest]=1;
	 adjacencyMatrix[dest][source]=1;
 }
 
 public void removeEdge(int source, int dest) {
	 adjacencyMatrix[source][dest]=0;
	 adjacencyMatrix[dest][source]=0;
 }
 }

Displaying the edges/ connections in adjacency matrix

Pseudocode:

To display the edges/connections in adjacency matrix notation we can display the rows and columns of adjacency matrix index-wise.

Code:

public void displayGraph() {
	 System.out.println();
	 System.out.print("           ");
	 for (int jIdx=0;jIdx< adjacencyMatrix[0].length;jIdx++) {
		 System.out.print(" "+jIdx);
	 }
	 System.out.println();System.out.println();
	 for (int iIdx=0;iIdx< adjacencyMatrix.length;iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx+"   ");
		 for (int jIdx=0;jIdx< adjacencyMatrix[iIdx].length;jIdx++) {
			 System.out.print(" "+adjacencyMatrix[iIdx][jIdx]);
		 }
	 }
 }

Traversing the nodes of a Graph

Graph nodes can be traversed using Breadth first and Depth first algorithms. These traversal mechanisms are covered in the code challenges below.

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphAdjacencyMatrix {

 private int vertices;
 private int[][] adjacencyMatrix;
 
 public GraphAdjacencyMatrix(int vertices) {
	 this.vertices=vertices;
	 adjacencyMatrix=new int[vertices][vertices];
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyMatrix[source][dest]=1;
	 adjacencyMatrix[dest][source]=1;
 }
 
 public void removeEdge(int source, int dest) {
	 adjacencyMatrix[source][dest]=0;
	 adjacencyMatrix[dest][source]=0;
 }
 
 public void displayGraph() {
	 System.out.println();
	 System.out.print("           ");
	 for (int jIdx=0;jIdx< adjacencyMatrix[0].length;jIdx++) {
		 System.out.print(" "+jIdx);
	 }
	 System.out.println();System.out.println();
	 for (int iIdx=0;iIdx< adjacencyMatrix.length;iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx+"   ");
		 for (int jIdx=0;jIdx< adjacencyMatrix[iIdx].length;jIdx++) {
			 System.out.print(" "+adjacencyMatrix[iIdx][jIdx]);
		 }
	 }
 }
 


public static void main(String[] args) {
	/**********************
	 Test cases given below
	 *********************/

	try {
	GraphAdjacencyMatrix gph=new GraphAdjacencyMatrix(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 4);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	
		
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
		
}
}