Painting graphs

Some time ago, a question was asked in StackOverflow about how we can use Prolog to compute the (or a single) coloring for a graph. After some thought, I came up with the following solution, which of course I am not really sure is correct, although it seems to give the correct results on the cases I looked at.


Let's start with describing our graph; we will use edge/2 facts to represent eges. A fact edge(a,b) means that there exists an edge between vertices a and b, as usual. Similarly for the colors, we will use color/1 to represent the available colors for our...painting :) So the initial database looks like this:

edge(a,b).
edge(b,c)
edge(b,d).
edge(c,d).

color(blue).
color(red).
color(green).




And now, for the real work :) We will represent the final coloring as a list of Vertice-Color pairs, where of course there should be no more than 1 pairs with the same vertex as the first element. As a base case, we will use what intuition says: vertex a gets a color c if there is no edge going out of a, assuming that we have colored the path(s) leading to a. In Prolog, this gets translated as:


coloring([V-C]) :- 
 color(C), 
 \+ edge(V,_).



Next, the recursive case. We will append a V-C pair on the front of the coloring list, if we can paint V with a color C, there is an edge from V to another vertex V1, and coloring the rest of the graph yields a color to V1 different than C. This is a brute-force algorithm; it tries to assign all the possible colors to vertices, until it finds a particular coloring that satisfies all the constraints. Translated in Prolog:


coloring([V-C,V1-C1|Coloring]) :-
        color(C),
        edge(V,V1),
        V \== V1,
        coloring([V1-C1|Coloring]),
        C1 \== C. 



Finally, we need a way of getting all the possible colorings for a graph. That's easy, using the findall/3 predicate. It works as follows; given an answer pattern in the first argument, calls the goal given in the second argument, and returns a list with all the results in the third. Pretty cool, huh? :)


:- import length/2 from basics.


colors(X) :-
        coloring(X),
        findall(V,edge(V,_),List),
        length(List,Len),
        length(X,Len). 



We just need one more thing; to check that the length of the solution is actually as long as the number of distinct vertices of the graph (we don't want solutions that only give colors to some of the vertices, right?). And that's it! Just call 


|?- colors(X). 


from your favorite Prolog interpreter, and you'll get all the possible colorings for your graph! Feeling like Picasso already? :)