Home » Core Java » How to find a Bipartite Graph?

About Frank Yee

Frank holds a Bachelor of Science in Biology from The City University of New York (The City College of New York) and a Bachelor of Arts in Computer Science from The City University of New York (Hunter College). As an undergraduate, he had taken courses where programs were written in Fortran, Basic, Pascal, COBOL, and Assembly Language for the IBM 4341 Mainframe. He has been a software developer for over 30 years having built desktop apps, mobile apps and web apps. He has built software in C/C++, VisualBasic, TCL, Java, PHP, XML/XSLT, Perl, Shell Scripting and Python. Frank was also an educator in The City University of New York (Borough of Manhattan Community College, New York City College of Technology) having taught courses in Pascal, VisualBasic, C++ for over 10 years. Finally, he has recently helped students create programs in Lisp, R, Masm, Haskell, Scheme and Prolog.

How to find a Bipartite Graph?

Hello there, in this article we will show how to find if a graph is a Bipartite Graph through detailed examples.

1. Introduction

In this article, we will define a bipartite graph, explore the properties of a bipartite graph, document an algorithm used to determine whether a graph is bipartite or not, and implement this algorithm in Java.

Finally, we will discuss the Time Complexity of various ways of implementing this algorithm.

2. Bipartite graph examples

A real-life application of a bipartite graph may be the use of vertices or nodes to represent entities in biological systems such as proteins, genes, and other molecules and the relationships between them which are indicated by edges. Another may be the utilization in order to establish relationships between attributes of individuals and their resultant compatibilities represented by edges in a dating site app.

3. Definitions

TermDescription
VertexUsed to represent an entity or location, for example, cities, buildings can be represented by a vertex
EdgeUsed to represent a relationship between vertices
GraphContains vertices and edges
Bipartite GraphA graph in which vertices can be placed into either one of two sets, with the properties enumerated in the following section (Properties of Bipartite Graphs).
Self EdgeAn edge that links a vertex to itself
Undirected GraphA graph in which a vertex A that links to another vertex B, will have vertex B reciprocally link to vertex A
Adjacency ListA list that represents other vertices linked to a particular vertex.
Adjacency MatrixA matrix (rows of columns, R x C) that represent edges found between vertices.
Definitions

4. Properties of Bipartite Graphs

  • Vertices can be separated into 2 separate sets.
  • A vertex can belong to only one set and not the other.
  • Vertices of one set can only have edges with vertices of the other set.
  • Vertices of one set will not have edges with vertices within the set they belong to.
  • Vertices will not have edges with themselves.

5. Algorithm to Determine if a Graph is Bipartite

Vertices can be numbered from 0 to N-1, where N is the number
of vertices being considered.

Create an array of size N initialized to UNASSIGNED. This array will contain
an indication of whether a vertex is in set 1 or set 2 when the
code has completed.

choose a vertex from 0 to N-1.

update the corresponding array element with set indicator, set_1 or set_2.

place vertex in a queue (list).

while the list has a vertex
    remove the first vertex from the  queue
    
    for all of the vertices which have edges with this vertex, 
        if they have been assigned already and if it has the same set indicator
            this is not a bipartite graph
        otherwise assign the opposite set indicator
        put the vertex just assigned a set indicator to the queue.
        
    if there are no more vertices determine if there are any more unassigned vertices
        if there are unassigned vertices, assign a set to it and add that to the queue
        if no more, we are done.

6. Implementation

This implementation will illustrate the determination of whether an undirected graph with no self edges is a bipartite graph by separating each vertex into one of two sets. Every vertex will belong to either set 1 or set 2 but not both. The implementation will use an adjacency matrix to represent the edges of the graph. One indicates an edge and a zero indicates no edge exists.

6.1 Sample Code

Go to Sample Code Output

import java.util.ArrayList;

public class GraphIsBipartite {
	final static int UNASSIGNED = 0;
	final static int SET_1 		= 1;
	final static int SET_2 		= 2;
	
	public static boolean isUndirectedGraph(int [][] graphAdjacencyMap) {
		boolean rv = true;
		
		for (int i = 0; i < graphAdjacencyMap.length; i++) {
			for (int j = 0; j < graphAdjacencyMap[i].length; j++) {
				if (graphAdjacencyMap[i][j] != graphAdjacencyMap[j][i]) {
					rv = false;
					System.out.printf("failed undirected Test: map[%d][%d]: %d  map[%d][%d]: %d\n", i, j, graphAdjacencyMap[i][j], j, i, graphAdjacencyMap[j][i]);
					break;
				}

			}
		}
		return rv;
	}
	public static boolean hasSelfEdge(int [][] graphAdjacencyMap) {
		boolean rv = false;
		
		for (int i = 0; i < graphAdjacencyMap.length; i++) {
			if (graphAdjacencyMap[i][i] == 1) {
				rv = true;
				System.out.printf("self edge map[%d][%d]: %d\n", i, i, graphAdjacencyMap[i][i]);
				break;
			}
		}
		return rv;
	}
	public static int nextUnassigned(int [] assigned) {
		int unassigned = -1;
		for (int i = 0; i < assigned.length; i++) {
			if (assigned[i] == UNASSIGNED) {
				unassigned = i;
				break;
			}
		}
		return unassigned;
	}
	public static boolean isBipartite(int [][] graphAdjacencyMap) {
		boolean rv = true;
		int index = 0;
		
		ArrayList<Integer>al = new ArrayList<Integer>();
		int [] setAssignment = new int[graphAdjacencyMap.length];

		for(int i = 0; i < setAssignment.length; i++)
			setAssignment[i] = UNASSIGNED;  
		setAssignment[index] = SET_1; 
		al.add(index);            

		while(al.size() > 0 && rv) {
			int u = al.get(0);
			al.remove(0);
	
			for(int v = 0; v < setAssignment.length; v++) {
				if(graphAdjacencyMap[u][v] == 1) {
                    if (setAssignment[v] == UNASSIGNED) {
					    if(setAssignment[u] == SET_1)
						    setAssignment[v] = SET_2;
					    else if(setAssignment[u] == SET_2)
						    setAssignment[v] = SET_1;
					    al.add(v);         
                    } else if(setAssignment[v] == setAssignment[u]) {
					    rv = false;
					    break;
                    }
				}
			}
			if (al.size() == 0) {
				if (nextUnassigned(setAssignment) >= 0) {
					index = nextUnassigned(setAssignment);					
					al.add(index);
					setAssignment[index] = SET_1;
				}
			}
		}
		if (rv) {
			String set1 = "";
			String set2 = "";
			for (int i = 0; i < setAssignment.length; i++) {
				if (setAssignment[i] == SET_1) {
					if (set1.length() > 0)
						set1 += ", ";
					set1 += i;
				} else if (setAssignment[i] == SET_2) {
					if (set2.length() > 0)
						set2 += ", ";
					set2 += i;
				} 
			}
			System.out.println(String.format("     SET_1 [ %s ]", set1));
			System.out.println(String.format("     SET_2 [ %s ]", set2));
		}
		return rv;		
	}
	public static boolean isValidMap(int [][] graphAdjacencyMap) {
		boolean rv = true;

		for (int i = 0; i < graphAdjacencyMap.length; i++) {
			if (graphAdjacencyMap[i].length != graphAdjacencyMap.length) {
				rv = false;
				break;
			}			
		}
		return rv;
	}
	public static void printMap(int [][] map) {
		String output = "[\n";
		
		for (int i = 0; i < map.length; i++) {
			output += "  [ ";
			for (int j = 0; j < map[i].length; j++) {
				if (j != 0)
					output += ", ";
				output += String.format("%2d", map[i][j]);
			}			
			output += " ],\n";
		}
		output += "]\n";
		
		System.out.println(output);
	}
	public static String repeat(String repeatStr, int times) {
		String str = "";
		
		for (int i = 0; i < times; i++) str += repeatStr;
		
		return str;
	}
	public static void main(String [] args) {
		
		int [][][] graphAdjacencyMaps = {
										 // is bipartite
										 {
										  {0, 0, 1, 0, 1},
										  {0, 0, 0, 1, 0},
										  {1, 0, 0, 0, 0},
										  {0, 1, 0, 0, 0},
										  {1, 0, 0, 0, 0},
										 },
										 {
										  {0, 1, 0, 0, 0, 1},
									      {1, 0, 1, 0, 0, 0},
										  {0, 1, 0, 1, 0, 0},
										  {0, 0, 1, 0, 1, 0},
										  {0, 0, 0, 1, 0, 1},
										  {1, 0, 0, 0, 1, 0}
										 },
										 // is not bipartite
										 {
										  {0, 1, 1, 1, 0, 0},
										  {1, 0, 0, 1, 1, 0},
										  {1, 0, 0, 1, 0, 1},
										  {1, 1, 1, 0, 1, 1},
										  {0, 1, 0, 1, 0, 1},
										  {0, 0, 1, 1, 1, 0}
										 },
		};
		for (int [][] graphAdjacencyMap: graphAdjacencyMaps) {
			System.out.println(repeat("*", 40));
			printMap(graphAdjacencyMap);
			
			if (isValidMap(graphAdjacencyMap)) {
				if (!hasSelfEdge(graphAdjacencyMap)) {
					if (isUndirectedGraph(graphAdjacencyMap)) {
						if (isBipartite(graphAdjacencyMap)) {
							System.out.println("Is bipartite");
						} else 
							System.out.println("Is not bipartite");
					} else {
						System.out.println("This graph is undirected. Cannot be processed");
					}
				} else {
					System.out.println("This graph has self edge. Cannot be processed");
				}
			} else {
				System.out.println("This graph is not a square matrix. Cannot be processed");
			}
			System.out.println(repeat("*", 40));
		}
	}
}

6.2 Sample Code Output

Go to Sample Code

****************************************
[
  [  0,  0,  1,  0,  1 ],
  [  0,  0,  0,  1,  0 ],
  [  1,  0,  0,  0,  0 ],
  [  0,  1,  0,  0,  0 ],
  [  1,  0,  0,  0,  0 ],
]

     SET_1 [ 0, 1 ]
     SET_2 [ 2, 3, 4 ]
Is bipartite
****************************************
****************************************
[
  [  0,  1,  0,  0,  0,  1 ],
  [  1,  0,  1,  0,  0,  0 ],
  [  0,  1,  0,  1,  0,  0 ],
  [  0,  0,  1,  0,  1,  0 ],
  [  0,  0,  0,  1,  0,  1 ],
  [  1,  0,  0,  0,  1,  0 ],
]

     SET_1 [ 0, 2, 4 ]
     SET_2 [ 1, 3, 5 ]
Is bipartite
****************************************
****************************************
[
  [  0,  1,  1,  1,  0,  0 ],
  [  1,  0,  0,  1,  1,  0 ],
  [  1,  0,  0,  1,  0,  1 ],
  [  1,  1,  1,  0,  1,  1 ],
  [  0,  1,  0,  1,  0,  1 ],
  [  0,  0,  1,  1,  1,  0 ],
]

Is not bipartite
****************************************

7. Time Complexity Analysis

There are two common ways to implement the algorithm to determine whether a graph is bipartite or not. One way is using an adjacency list where an array of vertices is maintained and for each vertex, maintain a list or array of vertices that are adjacent to it. These represent the edges. This will be represented by V x E, where V is the number of vertices and E is the number of edges.

The other way is to use an adjacency matrix where an array of edges is maintained and a 1 represents that an edge exists for a pair of vertices whereas a 0 represents the absence of one. This will be a V x V matrix.

For the adjacency list, the Worst Scenario Time Complexity will be Big O ( V x E ). In using the adjacency matrix, the Time Complexity will be Big O( V x V ) or Big O( V^2 ). Big O( V x E ) in most cases will be a more efficient implementation.

8. Summary

The example in this article was implemented using the adjacency matrix. It will be left up to the reader to explore the implementation using the adjacency list.

9. Download the Source Code

Download
You can download the full source code of this example here: How to Find If a Graph Is Bipartite?

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments