This is the result:
First you need to represent the graph with adjacency matrix as follows:
(Also you can represent the graph with adj ency list as well )
0,1,0,0,1,0,0
1,0,0,0,0,1,0
0,0,0,1,0,1,0
0,0,1,0,0,0,1
1,0,0,0,0,0,0
0,1,1,0,0,0,0
0,0,0,1,0,0,0
Save this as a CSV file.This is the input to my program. I have used BFS algorithm for the implementation:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class ColourFinder {
private static Integer[][] aMatrix = null;
private static int size = 0;
private static Map nodes = new HashMap();
private static List queue = new ArrayList();
public static enum Colour {
NO_COLOR, BLACK, RED
}
/**
* @param args
*/
public static void main(String[] args) {
String path = null;
boolean run = true;
while (run) {
System.out
.print("Enter csv file path containing the graph representation in ajacency matrix: ");
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
try {
path = br.readLine();
run = false;
} catch (IOException e) {
System.out.println("Error occured! Please try again." + e);
}
}
setMatrix(path);
createNodes();
BFS();
}
private static void BFS() {
Node node;
Node ajacentNode;
Colour colour;
Integer[] aMatrixRow;
Colour nbrColour;
node = nodes.get(1);
node.setColour(Colour.RED);
System.out
.println("\n+++++++++++++++++++++++++++++++++++++++++++++++++++++++\n Source node: "
+ node);
enqueue(node);
while (queue.size() != 0) {
node = dequeue();
System.out
.println("=======================================================\n Current node: "
+ node);
colour = node.getColour();
aMatrixRow = aMatrix[node.getNodeNo() - 1];
for (int i = 0; i < aMatrixRow.length; i++) {
if (aMatrixRow[i] == 1) {
ajacentNode = nodes.get(i + 1);
System.out.println("Neighbor node initial colour: "
+ ajacentNode);
nbrColour = ajacentNode.getColour();
if (!nbrColour.equals(colour)) {
if (nbrColour.equals(Colour.NO_COLOR)) {
CheckColours(ajacentNode, colour);
enqueue(ajacentNode);
System.out.println("Neighbor node after coloured: "
+ ajacentNode);
} else {
System.out
.println("Neighbor node already has opposite colour: "
+ ajacentNode);
}
} else {
System.out
.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++\n Neighbor node colour is simillar to it's neighbor "
+ ajacentNode);
System.out
.println("Therefore Graph is not 2-colorable");
System.exit(0);
}
}
}
}
System.out
.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++\n Graph is 2-colorable");
}
private static void CheckColours(Node ajacentNode, Colour colour) {
switch (colour) {
case RED:
ajacentNode.setColour(Colour.BLACK);
break;
case BLACK:
ajacentNode.setColour(Colour.RED);
break;
}
}
private static void enqueue(Node node) {
queue.add(node);
}
private static Node dequeue() {
Node node = queue.get(0);
queue.remove(0);
return node;
}
private static void createNodes() {
Node node;
for (int i = 0; i < size; i++) {
node = new Node();
node.setColour(Colour.NO_COLOR);
node.setNodeNo(i + 1);
nodes.put(i + 1, node);
}
}
private static void setMatrix(String path) {
int j = 0;
String[] row;
File file;
Scanner scan;
try {
file = new File(path);
scan = new Scanner(file);
System.out.println("Ajacency Matrix for the graph:\n");
while (scan.hasNext()) {
System.out.println((size++) + "| " + scan.next());
}
aMatrix = new Integer[size][size];
scan = new Scanner(file);
while (scan.hasNext()) {
row = scan.next().split(",");
if (size == row.length) {
for (int i = 0; i < row.length; i++) {
aMatrix[j][i] = new Integer(row[i]);
}
j++;
} else {
System.out.println("Incorrect ajacency matrix in csv file "
+ file.getAbsolutePath());
aMatrix = null;
System.exit(0);
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
System.exit(1);
}
}
public static class Node {
private Colour colour;
private int nodeNo;
public Colour getColour() {
return colour;
}
public void setColour(Colour colour) {
this.colour = colour;
}
public int getNodeNo() {
return nodeNo;
}
public void setNodeNo(int nodeNo) {
this.nodeNo = nodeNo;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return nodeNo + "->" + colour;
}
}
}
