Graph coloring problem is one of the most famous NP-Complete problems. Many algorithms have been proposed and implemented for this problem, see here, here and here. Trick’s implementation is one of simplest program for graph coloring. A efficient algorithm is implemented by few hundreds lines of C codes.

Unfortunately, this program cannot process the graphs that consisted by more than 10,000 nodes. After a brief review of the codes, I found some marcos are used in this program to define the maximum size of input graph, and the input graph and all necessary variable are stored in static arrays. For the graph that contains 10,000 nodes, user should modify a marco named MAX_NODES to more than 10,000 to handle such large graphs. On my 4GB mem desktop computer, the source codes cannot be compiled successful for such large graphs. I have modified the codes. Now, the arrays for all graph size related variables are declaimed dynamically. Graphs that contain 40,000 nodes can be processed on my desktop computer now.

The modified source code can be download from trick.c.

A small project has been set up on Google code. Latest version of this file can be got from the subversion server. http://code.google.com/p/gossipcoder/

Comment is welcome.

ChangLog:
Jul 02, 2010 add Google code project info

Aug 08, 2010

A improved version for big graph has been upload to google code. Bitset container is used to store the network to reduce requirement of memory.