Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'd like to implement a brute force algorithm to search ALL the different colorings of a map.

In terms of graph theory I'd like to find all four colorings of the vertices of a planar graph (the dual representing the map).

I need help or hints to put me on the right direction.

I'm interested in maps in which each face is an opaque rectangle layered on all previous rectangles, overlapping partially. Each consecutive rectangle starts at a consecutive y coordinate. The next picture should better clarify what I mean.

The faces are numbered from 1 to n

  • face 1 is the face on the bottom of the pile
  • face (n-1) is the face at the top
  • face n is the infinite face surrounding all others

For the meaning of different colorings you can refer to this question:

I was thinking to pre-set the colors of faces and use a classical brute force algorithm to get four coloring of the map. I already implemented the brute

force algorithm to find the proper coloring of a map and I can also force the color of faces to find particolar colorings.

The problem is that I'm not coming up with an algorithm to do it automatically and to be sure to find ALL colorings.

To see what I have so far, you can watch this video on youtube:

http://www.youtube.com/watch?v=sP9gnOLpG9w

What I know is that:

  • Since the colors of three neighboor faces can be arbitrary, face number n, face number 1 and the face touching both (face n and face 1), can have these fixed colors: blue, red, green

Manually I found these colorings:


This is a cross site post on cstheory.

share|improve this question

4 Answers 4

You can generate all 4 (or other number) colorings using Sage, an open source computer math system. You can use it free online without having to install it at http://www.sagenb.org/

If you can input your graph in Sage to the symbol G, then the following code will print all the graph G with all the different colorings

for C in sage.graphs.graph_coloring.all_graph_colorings(G, 4):
    G.plot(vertex_colors = C)
share|improve this answer

You can reduce any problem of vertex coloring to a problem of finding the Grobner basis for some ideal in $k[x_1,..,x_n]$. And this last problem can be solved with Butchberger (?) Algorithm. You can try that for the dual of your graph, probably not the best approach.

Google returned many pages which contain this basic idea, here is one example:

Graph coloring and Grobner bases

share|improve this answer
    
Wow, how fast! I'll take a look into it. For my level it seems too difficult to understand and implement, but i'll try to see what I can do. I was hoping for a simpler approach to the problem! Thanks for the info –  Mario Stefanutti Mar 15 '12 at 17:05
2  
Groebner basis are rarely computed by Buchberger's algorithm. Typically faster algorithms F4 and F5 (IIRC) of Faugère are used. IIRC, Singular software has the fastest Groebner basis implementation. –  user2468 Mar 15 '12 at 18:11

This C code below generates all $4$-colourings of a graph with <=31 vertices. It's a basic depth-first search, backtracking algorithm.

  • It's not designed to be overly efficient, but some obvious improvements have been made. I believe there would be vastly better implementations out there (this problem screams SSE). (But my impression is that you're after a simple but effective solution.)
  • It's restricted to graphs with at most 31 vertices since I use bitwise operations. On a 64-bit machine this could be increased. Otherwise, a more complicated version would be required (e.g. dividing the adjacency matrix into 4 smaller adjacency matrices).
  • We can assume the vertex $0$ is coloured $0$ (this saves a run-time factor of $4$). [If you want to include the other colourings, add $+d$ too all colours, as $d$ runs over $0,1,2,3$.]
  • It generates a random graph to work on initially. This will need to be edited to allow your own input.

Keep in mind that, depending on the density of your input graph, there might be gazillions of $4$-colourings, and, in such a case, no program would be able to run to completion, regardless of how good your algorithm is and how good your coding skills are. Merely iterating through all possible $4$-colourings, even with the aid of an oracle, would be too slow.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NR_VERTICES 31
#define MAX_NR_EDGES MAX_NR_VERTICES*(MAX_NR_VERTICES-1)/2
#define VERBOSE 0

const int n=31;

/* the u-th bit of adjacency[v] is 1 whenever {u,v} is an edge in the graph */
int adjacency[MAX_NR_VERTICES];

/* colour[v] is the colour of vertex v */
int colour[MAX_NR_VERTICES];

/* a counter for the number of colourings */
int nr_colourings;

void generate_4_colourings_backtracking_algorithm(int v) {
  /* attempts to use colour c for vertex v */
  for(int c=0;c<4;c++) {
    for(int u=0;u<v;u++) {
      /* checks if there is a vertex u adjacent to v coloured c */
      /* only the vertices before v have been coloured thusfar */
      if((adjacency[v] & 1 << u) && colour[u]==c) { goto dont_use_this_colour; }
    }

    /* trying colour c for vertex v */
    colour[v]=c;

    if(v==n-1) {
      /* found a proper colouring */
      nr_colourings++;
      /* if VERBOSE is set to 1, this will print the colouring to the screen */
      if(VERBOSE) { printf("colouring %d: ",nr_colourings); for(int u=0;u<n;u++) { printf("%d ",colour[u]); } printf("\n"); }
    }
    else {
      /* normal backtracking step */
      generate_4_colourings_backtracking_algorithm(v+1);
    }

    dont_use_this_colour: ;
  }
}

int main() {
  if(n>MAX_NR_VERTICES) { return 0; }

  /* generates a random list of edges for the graph */
  srand(time(NULL));
  int u;
  for(int v=0;v<n;v++) {
    int nr_edges=3;
    for(int i=0;i<nr_edges;i++) {
      do { u=rand()%n; } while (u==v);
      adjacency[v] |= 1 << u;
      adjacency[u] |= 1 << v;
    }
  }
  printf("Adjacency matrix:\n"); for(int v=0;v<n;v++) { for(int u=0;u<n;u++) { printf("%d",(adjacency[v] >> u) & 1); } printf("\n"); } printf("\n");
  /* finished generating random graph */

  /* by symmetry, we can assume vertex 0 is coloured 0 */
  colour[0]=0;
  generate_4_colourings_backtracking_algorithm(1);

  printf("Found %d canonical 4-colourings; %d total 4-colourings\n",nr_colourings,4*nr_colourings);

  return 1;
}
share|improve this answer

Input: A planar graph $G(V,E)$.

Output: A printed list of every valid 4 coloring of $G$.

  • For all functions $f : V \to \{1,2,3,4\}$
    • If $f(V)$ is a valid coloring of $G$
      • Print $f(V)$
share|improve this answer
    
How do I find all functions f:V→{1,2,3,4}? All possible functions, without filtering them first (for not valid coloring), seem to be a very high number of solutions. –  Mario Stefanutti Mar 15 '12 at 17:21
    
There are $4^{|V|}$ such functions. This should not matter because you said that you are interested in a brute force algorithm. There is a 1-to-1 correspondence bettwen $|V|$-tuples in $\{1,2,3,4\}^{|V|}$ and functions $f : V \to \{1,2,3,4\}$. For the direction that you care about, from a $|V|$-tuple $u = (u_1, u_2, \ldots, u_{|V|}) \in \{1,2,3,4\}$, define $f_u(i) = u_i$. Even more concretely. Instead of using $\{1,2,3,4\}$, use $\{0,1,2,3\}$. Then a $|V|$-tuple in $\{0,1,2,3\}^{|V|}$ is the same as a number between 0 and 333...3 (where there are $|V|$ 3's) in base 4. –  Tyson Williams Mar 15 '12 at 17:36
    
@Mario Does this make sense? –  Tyson Williams Mar 16 '12 at 16:33
    
Yes it does, but that is exactly why I'm looking for an algorithm. I'm working with graphs that have 30-50 vertices and that makes impossible to find all possible colorings and then filter them out. I'l like to write something similar to the function colorIt() inside this java code: - maps-coloring.git.sourceforge.net/git/… implementing for example a new method called findAllColorings() –  Mario Stefanutti Mar 16 '12 at 18:47
    
@Mario This is an algorithm, a brute force algorithm like you requested. If you want something efficient (in the output size), then this is probably a good question to ask on TCS.SE. –  Tyson Williams Mar 17 '12 at 3:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.