Lab 3 314

gistfile1.txt

/*
 * Zachary Collins
 * Discrete 314
 * November 29
 * Lab 3
 */

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Bipartite
{
    public static int V = 6; // No. of Vertices
 
    public static void main (String[] args) {
    	ArrayList<int[][]> graphs = new ArrayList<int[][]>();
    	
    	//Given input 1
    	int Graph1[][]
        = {
        	{0, 0, 0, 1, 1, 0},
            {0, 0, 0, 1, 1, 1},
            {0, 0, 0, 0, 1, 1},
            {1, 1, 0, 0, 0, 0},
            {1, 1, 1, 0, 0, 0},
            {0, 1, 1, 0, 0, 0},
        };
    	
    	//Given input 2
        int Graph2[][]
        = {
    		{0, 1, 0, 1, 0, 0},
            {1, 0, 1, 0, 0, 1},
            {0, 1, 0, 1, 0, 0},
            {1, 0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0, 1},
            {0, 1, 0, 0, 1, 0},
        };
        
        //Add both created graph inputs to the graphs arraylist
        graphs.add(Graph1);
        graphs.add(Graph2);
        
        Bipartite bip = new Bipartite();
        
        //Run tests on all graphs inside the graphs arraylist.  *Note* given inputs all have 6 vertices. Adjust if necessarys
        for (int i=0; i<graphs.size(); i++) {
            if (bip.isBipartite(Graph1, 0)) {
            	System.out.println("Input Graph "+(i+1)+" is bipartite");
            }
             else {
            	 System.out.println("Input Graph "+(i+1)+" is not bipartite");
             }
        }
    }
    
    /**
     * 
     * @param Graph
     * @param start
     * @return boolean true or false, t = graph is bipartite, false=graph is not bipartite
     */
    boolean isBipartite(int Graph[][],int start)
    {	
    	// 'Color' or differentiate appropriate vertices using 0, 1, and -1
        int colorArr[] = new int[V];
        
        //Create linked list  
        LinkedList<Integer> q = new LinkedList<Integer>();

        for (int i=0; i < V; ++i) {
            colorArr[i] = -1;
        }
 
        // Assign first 'Color' of 1 to start
        colorArr[start] = 1;
        q.add(start);
 
        // Run while there are vertices in queue (Similar to BFS)
        while (q.size() != 0) {
 
            // Dequeue a vertex from queue
            int u = q.poll();
 
            // Find all non-colored adjacent vertices
            for (int v=0; v<V; ++v) {
                //Edge from v to u exists
                if (Graph[u][v]==1 && colorArr[v]==-1) {
                	//Alternate color
                	colorArr[v] = 1-colorArr[u];
                    q.add(v);
                }
 
                //Color same color as U
                else if (Graph[u][v]==1 && colorArr[v]==colorArr[u]) {
                    return false;
                }
            }
        }
        //Color all with other color
        return true;
    }
}