Graph Colouring program

Question

I've been asked to create a Java program, wherein I accept a predefined number of vertices first, and then all the edges which exist in the graph as number pairs. My code is supposed to accept the edges, create the 'graph' and color all the vertices.

My problem is with the coloring. The method 'setColor' is supposed to accept the degree of the graph each time it is called. The getBiggestVertex method is supposed to return the vertex to be coloured. It is then colored. For some reason however, when I display the colors of the vertices, I constantly get either 0 or 1 or -1.

I'm unable to figure out why I am getting this output, could someone please help?

Graph Class:

import java.util.ArrayList;
import java.util.Scanner;


public class Graph {
    ArrayList <Vertex> vertices = new ArrayList<Vertex>();
    public Graph(){
        Scanner sc = new Scanner(System.in);
        int noOfVertices = sc.nextInt();

        for(int i = 0; i <noOfVertices; i++){
            addVertex();
        }

        String input = sc.next();

        while(!input.equals("-1")){
            String vertex [] = input.split(",");
            addEdge(vertices.get(Integer.parseInt(vertex[0])), vertices.get(Integer.parseInt(vertex[1])));
            input = sc.next();
        }
        for(int i = 0; i<vertices.size(); i++){
            getBiggestVertex().setColor(vertices.size());
        }
    }

    public Vertex getBiggestVertex(){
        Vertex bVertex = new Vertex(-1);
            for(int i = 0; i < vertices.size(); i++){
                Vertex v = vertices.get(i);
                if(v.colour ==-1){
                    if(v.getDegree() > bVertex.getDegree()){
                        bVertex = v;
                    } else if(v.getDegree() == bVertex.getDegree()){
                        if(v.vertexNumber < bVertex.vertexNumber){
                            bVertex = v;
                        }
                    } else if(v.getDegree() < bVertex.getDegree()){

                    }
                }
            }
        return bVertex;
    }
    public void addVertex(){
        vertices.add(new Vertex(vertices.size()));
    }

    public Vertex getVertex(int index){
        return vertices.get(index); 
    }

    public void addEdge(Vertex v1, Vertex v2){
        v1.addAdjacency(v2);
        v2.addAdjacency(v1);
    }

}

Vertex Class:

    import java.util.LinkedList;


public class Vertex {
    int vertexNumber, colour;
    LinkedList <Vertex> adjacencies = new LinkedList<Vertex>();
    public Vertex(int vertexNum){
        vertexNumber = vertexNum;
        colour = -1;
    }
    public void addAdjacency(Vertex v){
        adjacencies.add(v);
    }
    public boolean isAdjacent(Vertex v){
        boolean adj = false;
        for(int i = 0; i < adjacencies.size(); i++){
            if(adjacencies.get(i) == v){
                adj = true;
            }
        }
        return adj;
    }
    public int getDegree(){
        return adjacencies.size();
    }
    public void setColor(int degree){
        int [] used = new int[degree];
        for(int i = 0; i < adjacencies.size(); i++){
            int c = adjacencies.get(i).colour;
            System.out.println("Color of " + i + " = " + c);
            used[c+1] = 1;

        }
        int unusedColor = 0;
        while(used[unusedColor] == 1){
            unusedColor ++;
        }
        colour = unusedColor;
    }
}

collapsar collapsar · Accepted Answer · 2015-11-11T01:12:43

I assume that -1 represents a vertex color not yet defined.

There are several issues with your code, most of which center around setColor method:

When checking the colors of adjacent vertices, the range of color codes is shifted by 1 to serve as indices into the usage marker array used. However, after having visited all neighbours the first color you test for is 0.

This process colors a vertex that only has uncolored neighbours with 1. In case all neighbours have been colored, the assigned color will be 0.

Moreover in getBiggestVertex, the condition (v.vertexNumber < bVertex.vertexNumber) will never fire for vertices with an outdegree of 0 when all remaining vertices without assigned colors have outdegree 0 ( bVertex is initialised with the minimal vertex number of -1 and will never be reassigned ).

That means in particular that you may produce paths of vertices of the same color. Notably the following graph will be given an invalid colouring :

results in the colouring

 c(1)   = -1
 c(2)   = 1
 c(3)   = 1
 c(4)   = 1
 c(5)   = -1
 c(6)   = -1
 c(7)   = -1
 c(8)   = -1
 c(9)   = 0
 c(10)  = -1
 c(11)  = -1

where node 3 would need a new color 2 and -1 is an invalid color (which may be construed ex post as valid, of course).

Rectify the code by

maintaining bidirectional adjacencies (so a,b implies that a is adjacent to b and vice versa )
writing used[c] instead of used[c+1].

or check the colors of predecessor vertices as well.

In addition to the flawed color assignment, consider the following suggestions to improve your code:

The max degree is a property of the graph and thus should be a property of the graph class. Thus you do not need to allocate the worst case degree of the current number of vertices - 1 for the used array in setColor.
The node(s) with the highest degree in the graph need not be recomputed from scratch on every use but may be a property of the graph class as well
Taking the previous advice one step further, you may sort the vertices of the graph by decreasing degree before the colouring process storing this list. The should relieve you from the repeated calls to getBiggestVertex, you visit the nodes in the same order as they appear in the list.

Graph Colouring program

1 Answers