Ndtyjky

I am required to write a program that takes in an input file (which represents a graph) and outputs the chromatic number along with the vertices colors. I wrote a program that does this successfully, however I am given a large input file and the program runs indefinitely. I need to make the program narrow down the chromatic number to a range of ten values. Can anyone give me some advice as to how I can accomplish this. I will post my code below for reference.

Any help would be appreciated. Thanks!

import java.util.*;

import java.io.*;



public class chromatic_num {

    public static int n;

    public static int q;

    public static int matrix;

    public static List<Integer> list;



    public static void main(String args) throws IOException {

        //reads input from file

        BufferedReader br;

        try {

            br = new BufferedReader(new InputStreamReader(new FileInputStream("file1.txt")));

        } catch (FileNotFoundException e) {

            throw new RuntimeException();

        }

        String line;

        boolean readFirstLine = false;

        // new array list to store input

        list = new ArrayList<Integer>();

        // read file line by line

        while ((line = br.readLine()) != null)   {

            // prints content

            String toks = line.split(" ");

            if (readFirstLine) {

                list.add(Integer.parseInt(toks[0]));

                list.add(Integer.parseInt(toks[1]));

            }

            else {

                readFirstLine = true;

                n = Integer.parseInt(toks[0]);

            }

        }

        // finds max edges

        n = Collections.max(list);

        // for adjacency matrix

        matrix = new int[n][n];

        // constructs adj. matrix

        int count = 0;

        Integer v1 = 0, v2 = 0;

        for (Integer v : list) {

            if (count % 2 == 0) {

                v1 = v - 1;

            }

            else {

                v2 = v - 1;

                matrix[v1][v2] = 1;

                matrix[v2][v1] = 1;

            }

            count++;

        }

        // new array to store colors

        q = new int[n]; 

        chromatic_num chromatic = new chromatic_num();

        //print solution to screen

        System.out.println(chromatic.color());       

        for (int i = 0; i < n; i++) {

            System.out.println("" + (i + 1) + " " + q[i]);

        }

        //print solution to file

        try {

          System.setOut(new PrintStream(new FileOutputStream("chromatic_num.txt")));

        } catch (FileNotFoundException e) {

            throw new RuntimeException();

        }



        System.out.println(chromatic.color());

        for (int i = 0; i < n; i++) {

            System.out.println("" + (i + 1) + " " + q[i]);

        }

        br.close();     

    }

    //color G using minimum number of colors, returns chromatic number

    public int color()

    {

        //for (int t = 0

        for (int i = 1; i <= n; i++)

        {

            //if G can be colored using i colors starting at vertex 0

            //System.out.println("colored using " + i + " colors starting at vertex 1");

            if (color(0,i)) {

                //chromatic number is i, return it

                return i;

            }

            else {

                for (int j = 0; j < n; j++) {

                    q[j] = 0;

                }

            }

        }

        return 0;

    }



    //colors G using m colors starting at vertex v

    public boolean color(int v, int m)

    {

        if (v > n - 1) {

            //all vertices have been colored, success

            return true;

        }

        else

        {

            for (int i = 1; i <= m; i++)

            {

                //assign color i to vertex v

                q[v] = i;

                //System.out.println("color " + i + " to vertex " + (v + 1));



                //check whether colors of v and its neighbors conflict

                boolean hasConflicted = hasConflicted(v);

                //System.out.println("hasConflicted = " + hasConflicted);

                if (hasConflicted == false)

                {

                    //color the rest of G using m colors starting at vertex v+1, done by recursive call color(v+1, m)

                    boolean success = color(v + 1, m);



                    //if (the rest of G can be colored)

                    //  all vertices have been colored, success

                    if (success) {

                        return true;

                    }

                }

            }

            //assign color 0 to vertex v and fail, this happens when none of the m colors can be assigned to vertex v

            q[v] = 0;

            return false;

        }

    }

    public boolean hasConflicted(int v) {

        for (int i = 0; i < n; i++)

        {

            if (i != v && matrix[i][v] == 1 && q[i] == q[v]) {

                return true;

            }

        }

        return false;

    }

}