Graph Coloring with CLP(FD)

Question

I am trying to solve the map/graph coloring problem using CLP(FD) in Prolog. I took the predicates from the paper "A comparison of CLP(FD) and ASP solutions to NP-complete problems" and I'm trying with the following example:

coloring(K, Output) :- graph(Nodes, Edges),
    create_output(Nodes, Colors, Output), domain(Colors, 1, K),
    different(Output, Edges), labeling([ff], Colors).
create_output([],[],[]).
create_output([N | Nodes], [C|Colors], [N-C|Output]) :-
    create_output(Nodes, Colors, Output).
different(_, []).
different(Output, [[A,B]|R]) :- member(A-CA, Output),
    member(B-CB, Output), CA #\= CB, different(Output, R).
graph([1,2,3,4,5],[(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)]).

but when I run the query

create_output([1,2,3,4,5],[a,b,c,d],A).

it gives me false even that for this graph it is possible to use only 4 colors (a,b,c,d). When I add another color it works fine, it seems that set of nodes should be same size as set of colors. But this is not what map coloring should do. Anyone is able to help me understand what's the problem with the predicates above?

Answer 1

I think create_output/3 should be called with only Nodes instantiated. It will create the other 2 lists with domain variables (that is, color indexes) and associations between nodes and colors.

Anyway, from the code below, you can see that the real problem is in the head of different/2, where a list has been used instead of a 'tuple' to match an edge...

:- module(mapcolor,
          [coloring/2]).

:- use_module(library(clpfd)).

coloring(K, Output) :-
    graph(Nodes, Edges),
    create_output(Nodes, Colors, Output),
    domain(Colors, 1, K),
    different(Output, Edges),
    labeling([ff], Colors).

domain(Colors, Low, High) :- Colors ins Low .. High.

create_output([],[],[]).
create_output([N | Nodes], [C|Colors], [N-C|Output]) :-
    create_output(Nodes, Colors, Output).

different(_, []).
different(Output, [(A,B)|R]) :-  % note: was [[A,B]|R]
    member(A-CA, Output),
    member(B-CB, Output),
    CA #\= CB,
    different(Output, R).

graph([1,2,3,4,5],[(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)]).

Note that the graph can be colored with just 2 colors:

?- coloring(2,C).
C = [1-1, 2-2, 3-2, 4-1, 5-1] ;
C = [1-2, 2-1, 3-1, 4-2, 5-2] ;
false.

With 4 colors, there are a lot of solutions...