CC-17 : Check if graph is Bipartisan graph.

Description:

A bipartisan graph is it can be divided into two sets (with unique elements) such that all edges of graph have one vertex in one of the sets and destination vertex in the second set. Given an input graph and check if is a bipartisan graph.

Test cases and expected outputs:

Input Parameters	Expected outputs
Adjacency list: vertex 0->1 vertex 1->0->2 vertex 2->1->3 vertex 3->2	Is graph Bipartite: true
Adjacency list: vertex 0->1->2 vertex 1->0->2 vertex 2->1->3->0 vertex 3->2	Is graph Bipartite: false

Pseudocode:

checkBipartisan (int[][] matrix) method:

Iterate through vertices of vertices using a for loop with iIdx as loop variable with values from 0 to count of count of vertices:

Set visited[iIdx] = -1.

Iterate through vertices of vertices using a for loop with iIdx as loop variable with values from 0 to count of count of vertices:

If visited[iIdx] == -1:

If call to dfsBipartisan(iIdx,0) returns false, return false from the method.

Return true.

dfsBipartisan (intt vertex, int set) method:

Set visited[vertex]=set.

Set Iterator itr to list of adjacent nodes of vertex from the adjacencyLists.

Iterate through adjacent nodes of vertex:

If visited[adjacentNode]==-1:

If call to dfsBipartisan(iIdx, 1-set) returns false, return false from the method.

Else If visited[adjacentNode]==set:

Return false.

Return true.

Code:

public class GraphCheckBipartite {

private int vertices;
private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
private int[] visited;
String dfsTraversal=new String();
	 
public GraphCheckBipartite(int vertices) {
	this.vertices=vertices;
	visited=new int[vertices];
	for (int iIdx=0; iIdx < vertices; iIdx++) {
		adjacencyLists.add(new ArrayList<Integer>());
		visited[iIdx]=-1;
	}
}
	 
public void addEdge(int source, int dest) {
	adjacencyLists.get(source).add(dest);
	adjacencyLists.get(dest).add(source);
}

public boolean dfsBipartisan(int vertex, int set) {
	visited[vertex]=set;
		 
	Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	while (itr.hasNext()) {
	int adjacentNode=itr.next();
	if (visited[adjacentNode]==-1) {
		if (dfsBipartisan(adjacentNode,1-set)==false) {
			return false;
		}
	}else {
		if (visited[adjacentNode]==set) {
			return false;
		}
	}
	}
	return true;
}	  
	 
public boolean checkBipartite() {
	for (int iIdx=0;iIdx< vertices;iIdx++) {
		if (visited[iIdx]==-1) {
			if (dfsBipartisan(iIdx,0)==false) {
				return false;
			}
		}
	}
	return true;
}	 
}

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.

import java.util.ArrayList;
import java.util.Iterator;

public class GraphCheckBipartite {

private int vertices;
private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
private int[] visited;
String dfsTraversal=new String();
	 
public GraphCheckBipartite(int vertices) {
	this.vertices=vertices;
	visited=new int[vertices];
	for (int iIdx=0; iIdx < vertices; iIdx++) {
		adjacencyLists.add(new ArrayList<Integer>());
		visited[iIdx]=-1;
	}
}
	 
public void addEdge(int source, int dest) {
	adjacencyLists.get(source).add(dest);
	adjacencyLists.get(dest).add(source);
}

public boolean dfsBipartisan(int vertex, int set) {
	visited[vertex]=set;
		 
	Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	while (itr.hasNext()) {
	int adjacentNode=itr.next();
	if (visited[adjacentNode]==-1) {
		if (dfsBipartisan(adjacentNode,1-set)==false) {
			return false;
		}
	}else {
		if (visited[adjacentNode]==set) {
			return false;
		}
	}
	}
	return true;
}	  
	 
public boolean checkBipartite() {
	for (int iIdx=0;iIdx< vertices;iIdx++) {
		if (visited[iIdx]==-1) {
			if (dfsBipartisan(iIdx,0)==false) {
				return false;
			}
		}
	}
	return true;
}	 
	 
public void displayGraph() {
	for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		System.out.println();
		System.out.print("vertex "+iIdx);
		for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		}
	}
}
public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	GraphCheckBipartite gph=new GraphCheckBipartite(4);
	
	gph.addEdge(0, 1);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.displayGraph();
	retVal=gph.checkBipartite();
	System.out.println();
	System.out.println("Is graph Bipartite: "+ retVal);
	
	gph=new GraphCheckBipartite(4);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.displayGraph();
	retVal=gph.checkBipartite();
	System.out.println();
	System.out.println("Is graph Bipartite: "+ retVal);
	
	gph=new GraphCheckBipartite(4);
	gph.addEdge(0, 1);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(0, 2);
	gph.displayGraph();
	retVal=gph.checkBipartite();
	System.out.println();
	System.out.println("Is graph Bipartite: "+ retVal);
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
			
}
}