Thursday, February 19, 2015

Graph Coloring Problem : Backtracking Solution Java Implementation

Tutorial : https://www.youtube.com/watch?v=Cl3A_9hokjU

Source:

import java.util.*;
import java.io.*; 
import java.math.*;

public class GraphColoring {
    static int connected[][];
    static int[] colors;
    static int nColors;
    static int nNodes;
    
    static int getNodeColor(int k){
        do{ 
            int j;
            //Assign the next color
            colors[k] = colors[k]+1; 
            
            //If all colors have been tested on this node, 
            //return because there are no more new colors left 
            //to be considered for this node
            if(colors[k]==nColors+1)return 0;
            
            //Check to see if some connected node already has this color
            for(j=1;j<=nNodes;++j){ 
                if(connected[k][j] == 1 && colors[k] == colors[j] && k!=j){ 
                    break;
                }
            }  
            if(j==nNodes+1)return colors[k];
        }while(true);
    }
    
    static void mColoring(int k){
        do{ 
            //get a color for this node
            colors[k] = getNodeColor(k); 
            
            //if no more colors can be applied to this node, return
            if(colors[k] == 0)return;
            
            //if all the nodes have been assigned colors successfully, print the color assignments
            if(k==nNodes){System.out.println("Color Assignment: "+Arrays.toString(colors));
            //return /*don't quit until all possible assignments have been found*/
            }
            //consider the next node
            else mColoring(k+1);
        }while(true);
    }
    
    public static void main(String[] args) throws Exception{ 
            nColors = 3;
            connected = new int[][]{
                {0, 0, 0, 0, 0},
                {0, 1, 1, 0, 1},
                {0, 1, 1, 1, 1},
                {0, 0, 1, 1, 1},
                {0, 1, 1, 1, 1},
            }; 
            nNodes = connected.length-1;
            colors = new int[nNodes+1];
            
            mColoring(1);
    } 
}

Output:

Color Assignment: [0, 1, 2, 1, 3]
Color Assignment: [0, 1, 3, 1, 2]
Color Assignment: [0, 2, 1, 2, 3]
Color Assignment: [0, 2, 3, 2, 1]
Color Assignment: [0, 3, 1, 3, 2]
Color Assignment: [0, 3, 2, 3, 1]

No comments:

Post a Comment