How to - Graph Coloring in Prolog
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
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)] ;