Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Finding Chromatic Number w/ Brute Force Algorithm

  1. #1
    Junior Member
    Join Date
    Nov 2011
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Finding Chromatic Number w/ Brute Force Algorithm

    Hello, I'm new to the forums here and really in a bind.

    I'm trying to implement this pseudocode:

    //graph G, vertices n, vertices are numbered 0, 1 . . n-1
    //G is stored in adjacency list or adjacency matrix p
    //colors are stored in array q
    //q[i] has color of vertex i, initially all 0
     
    //colors G using minimum number of colors, returns chromatic number
    int color()
    {
         for(i = 1 to n)
         {
              //if G can be colored using i colors starting at vertex 0
              if(color(0,i))
              {
                   chromatic number is i, return it
              }
         }
    }
     
    //colors G using m colors starting at vertex v
    boolean color(v,m)
    {
         if(v exceeds n - 1)
              all vertices have been colored, success
         else
         {
              for(i = 1 to m)
              {
                   assign color i to vertex v
     
                   check whether colors of v and its neighbors conflict
     
                   if(colors do not conflict)
                   {
                        color the rest of G using m colors starting at vertex v+1
                        done by recursive call color(v+1,m)
     
                        if(the rest of G can be colored)
                             all vertices have been colored, success
                   }
              }
              assign color 0 to vertex v and fail, this happens when
              none of the m colors can be assigned to vertex v
         }
    }
     
    //in color() method, chromatic numbers can be tried in ascending order
    //(i = 1 to n) or descending order (i = n to 1), and both orders can be
    //used to find a range of possible values of the chromatic number

    I thought that my implementation was working because I tested it with a small sample graph and got the correct output. However, when testing with large graphs this algorithm was solving them in seconds, but is supposed to have a runtime of hours. I think that I may be missing a recursive call somewhere, or maybe am breaking out of the function too early somehow.

    Anyway, here is my implementation of the above pseudocode. I am sincerely grateful for any help that you guys can provide. Thanks

    Explanation of my variables:

    this.size = the number of vertices in the graph
    this.vertexColors = 1 dimensional array with this.size number of elements. holds
    a chromatic number for each vertex
    this.inputMatrix = a this.size x this.size element 2d matrix. only holds 0s and 1s.
    the 0s represent no line between vertices, and a 1 represents a line

    Example:
    vertex
    1 2 3 4

    vertex 1 0 0 0 0
    vertex 2 0 0 1 0
    vertex 3 0 0 0 0
    vertex 4 0 0 0 0

    This represents a line connecting vertex 2 and 3. A 1 in row 3, column 2 would mean the same thing. It is also not necessary to have a 1 in both of those to represent the line, just one will work.

    My implementation:

        //colors graph using minimum number of colors, returns chromatic number
        public int colorAscending()
        {
            for(int i = 1; i < this.size + 1; i++)
            {
                //if graph can be colored using i colors starting at
                //vertex 0
                if(colorAscending(0,i))
                {
                    return i;
                }
            }
            //syntactically necessary return statement. should never get here
            return 0;
        }
     
     
     
     
     
     
        //v = current vertex, m = number of colors to try
        //colors graph using m colors starting at vertex v
        private boolean colorAscending(int v, int m)
        {
            if(v > this.size - 1)
            {
                //all vertices have been colored, success
                return true;
            }
            else
            {
                for(int i = 1; i < m+1; i++)
                {
                    //assign color i to vertex v
                    this.vertexColors[v] = i;
     
                    //check whether colors of v and its neighbors conflict
                    if(!checkForConflict(v))
                    {
                        if(colorAscending(v+1,m))
                        {
                            return true;
                        }
                        else
                        {
                            return false;
                        }
                    }
                }
                //assign color 0 to vertex v and fail
                this.vertexColors[v] = 0;
                return false;
            }
        }
     
     
     
     
     
        //checks if vertices adjacent to v have the same color or not
        private boolean checkForConflict(int vertex)
        {
            for(int i = 0; i < this.size; i++)
            {
                if((this.inputMatrix[i][vertex] == 1) &&
                        (this.vertexColors[i] == this.vertexColors[vertex]))
                {
                    return true;
                }
            }
            return false;
        }
    Last edited by thecrazytaco; November 15th, 2011 at 05:51 PM.


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,470
    My Mood
    Grumpy
    Thanks
    0
    Thanked 159 Times in 150 Posts

    Default Re: Finding Chromatic Number w/ Brute Force Algorithm

    Improving the world one idiot at a time!

  3. #3
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: Finding Chromatic Number w/ Brute Force Algorithm

    Can you explain the flow of your implementation. Which function calls first and next and next?
    This implementation is taking us no where.
    Please provide SSCCE

Similar Threads

  1. Finding all Permutations that add up to a number.
    By godsfearme in forum What's Wrong With My Code?
    Replies: 0
    Last Post: December 28th, 2010, 02:54 PM
  2. Finding out number of Palindromes in a Sentence
    By rameshiit19 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 12th, 2010, 09:44 PM
  3. Finding the highest number in an array?
    By halfwaygone in forum Algorithms & Recursion
    Replies: 1
    Last Post: April 17th, 2010, 03:56 PM
  4. Inputing file (.txt) and finding the highest number in the file
    By alf in forum What's Wrong With My Code?
    Replies: 3
    Last Post: March 15th, 2010, 09:11 AM
  5. Problem with Brute Force
    By mortis1572 in forum File I/O & Other I/O Streams
    Replies: 0
    Last Post: March 14th, 2010, 09:52 AM