How to - Graph Coloring in Prolog

Question

I'm trying to make the simple graph coloring algorithm in Prolog, but I'm having a bit of a hard time understanding the language. I know what I want to do - I want to go to a vertex, find all the other vertices connected to it, check my vertex's color, and depending on that, color the other vertices with different colors. I'm just having a hard time translating this to Prolog. If it was a C dialect or Java, it would be a piece of cake for me, but this is giving me fits.

This is what I have so far:

main:- graph_coloring.

%color_list([blue, red, green, yellow, white], colors).
%vertex_list([a, b, c, d], vertices).
%edge_list([(a,b),(b,c),(c,d)], edges).

%Our graph
color(blue).
color(red).
color(green).
color(black).
color(white).

%graph([a-b, b-c, b-d, c-d]).

vertex(a).
vertex(b).
vertex(c).
vertex(d).

%Subject to changing, so are asserted into listener at runtime.
init_dynamic_facts:-
    assertz(vertex_color(a, none)),
    assertz(vertex_color(b, none)),
    assertz(vertex_color(c, none)),
    assertz(vertex_color(d, none)),
    assertz(location(a)).

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

is_connect(A,B):-
    edge(A,B).
is_connect(A,B):-
    edge(B,A).

connections(Vertex):-
    edge(Vertex,X).
connections(Vertex):-
    edge(X,Vertex).

move(Vertex):-
    retract(location(_)),
    asserta(location(Vertex)).

paint_vertex(Vertex, Color):-
    retract(vertex_color(Vertex,_)),
    asserta(vertex_color(Vertex, Color)).

find_vertex_color(Vertex):-
    vertex_color(Vertex, X).


graph_coloring:-

    location(Current_vertex),
    vertex_color(Current_vertex, Curr_color),
    ( Curr_color =:= none ->
        connections(Current_vertex, Others),
        vertex_color(Others, Other_colors),
        paint_vertex(Current_vertex, 

How can I complete this algorithm?

(edited: more code under graph_coloring)

Answer 1

I think you are trying to think in a way that is not natural for Prolog programs; that is, you are trying not to use recursion :) What I've came up with is the following, which however may not be entirely correct (it's late, and I don't have a good reputation when trying to think at times like this...:) )

Let's assume that you have the graph described by the following facts:

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

and that the available colors are

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

(you only need 3 colors to color a planar graph, so let's just use 3 here). Let's also assume that you want the answer to be given as a [Vertex-Color] list, where the list will contain a color for every vertex of your graph. I believe the following is a correct solution:

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

The first clause says that if there is no edge from V to any other vertex, just try all possible colors. The second clause says that vertex V will get color C, and vertex V1 will get color C1 if there is an edge from V to V1, where V != V1 and C != C1. (I also assumed that your graph is connected, i.e. there are no vertices which are not connected to other vertices).

And since we only want solutions where all the vertices have colors, we will only keep lists of length |V|, where V is the set of vertices you have. You can implement this restriction in various ways; I prefer to use "findall/3":

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

Now, by consulting this program and asking |?- colors(X). you will get all the possible color assignments for the vertices of your graph.

If anyone finds a problem I am almost sure there exists in the above solution, please, do let us know :)

Spyros

Answer 2

I would like to mention this problem is a typical constraint satisfaction problem and can be efficiency solved using the CSP module of SWI-Prolog. Here is the full algorithm:

:- use_module(library(clpfd)). 

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

vertex(a).
vertex(b).
vertex(c).
vertex(d).
vertex(e).

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


colorGraph(ColorList) :- 
  findall((X, Y), edge(X, Y), Edges),
  findall(X, vertex(X), Vertexes),
  findall(hasColor(X, _), member(X, Vertexes), ColorList),
  createConstraint(Edges,ColorList),
  colorNodes(ColorList).

createConstraint([],_).
createConstraint([(V1,V2)|RL],ColorList):-
  member(hasColor(V1,C1),ColorList),
  member(hasColor(V2,C2),ColorList),
  dif(C1,C2),
  createConstraint(RL,ColorList).

colorNodes([]).
colorNodes([hasColor(_,C)|Nodes]) :-
  color(C),
  colorNodes(Nodes).

color/1 indicates the colors available, vertex/1 indicates the vertexes in the graph and edge/2 defines the couples between the vertexes. Moreover, colorGraph(?List) determines the color of the vertexes, where List is a list of hasColor(Vertex, Color) clauses, Vertex being the colored vertex using Color.

Let's details each part of the algorithm above to understand what happens.

:- use_module(library(clpfd)).

It indicates to SWI-Prolog to load the module containing the predicates for constraint satisfaction problems.

colorGraph(ColorList) :- 
  findall((X, Y), edge(X, Y), Edges),
  findall(X, vertex(X), Vertexes),
  findall(hasColor(X, _), member(X, Vertexes), ColorList),
  createConstraint(Edges,ColorList),
  colorNodes(ColorList).

The predicate colorGraph/1 is the entry point of the algorithm. It converts the clauses of edges/vertexes into lists, constraints the ColorList to have the list of vertexes defined and finally create the constraints on the colors and assign the colors (they are two separated operations).

createConstraint([],_).
createConstraint([(V1,V2)|RL],ColorList):-
  member(hasColor(V1,C1),ColorList),
  member(hasColor(V2,C2),ColorList),
  dif(C1,C2),
  createConstraint(RL,ColorList).

The predictate createConstraint/2 simply states that two linked vertexes must have a different color. This is worth mentioning dif/2 is a CSP predicate.

colorNodes([]).
colorNodes([hasColor(_,C)|Nodes]) :-
  color(C),
  colorNodes(Nodes).

The predicate colorNodes/1 assigns the right color to the vertexes. Prolog is going to take care to assign the right colors based on the constraints defined above.

Finally, the results can be found by calling the predicate colorGraph/1, such as:

?- colorGraph(L).
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, red)] ;
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, blue)] ;
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, green)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, red)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, blue)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, green)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, red)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, blue)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, green)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, red)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, blue)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, green)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, red)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, blue)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, green)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, red)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, blue)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, green)] ;