Graph coloring with s(CASP)

Help!
1

I was playing around with s(CASP) in SWISH and tried to solve a simple graph coloring problem (three vertices connected like a triangle):

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

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

color(red).
color(green).

colorize(N,C) :- vertex(N), color(C).
:- edge(N1,N2), colorize(N1,C), colorize(N2,C).

My query is …

?- ? colorize(N,C).

… which should yield no results, since it is not possible with two colors, but it does give me some results.

Questions:

  1. What am I missing?
  2. When adding a third color, how can I get the colorization result as a list? For example:
[(a, red), (b, green), (c, blue)]
2

That is fairly easy :slight_smile: Global constraints in the Prolog embedded mode should be written as

 false :- edge(N1,N2), colorize(N1,C), colorize(N2,C).

instead of just :- edge(N1,N2), colorize(N1,C), colorize(N2,C). as this is Prolog’s syntax for directives.

With that you get indeed no models. But … you also get no models with three colors. See SWISH -- SWI-Prolog for SHaring

I am not entirely sure why not :frowning: It is consistent in the SWISH, commandline and original Ciao version and I think it is a misconception about what global constraints mean.

If you can generate a model you can use scasp/2 to extract the model:

?- scasp(Query, [model(Model)]).
1 Like
4

Hi Jan, you are right, it is difficult to work with global constraints from Prolog’s point of view…
Note that the predicate colorize/2 is always true, there is only one model in which each node is colorized with each color…

To generate various models and prune the incorrect models you need even loops.

1 Like
5

Thank you all for the replies, I have a working solution now. However, it does not utilize a global constraint:

:- use_module(library(scasp)).

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

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

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

colorize(N,C) :- vertex(N), color(C), not sameColoredNeighbor(N,C), not doubleColored(N,C).

sameColoredNeighbor(N,C) :- edge(N,OtherN), colorize(OtherN, C).

doubleColored(N,C) :- color(OtherC), C \= OtherC, colorize(N, OtherC).

And the query:

scasp(colorize(_,_), [model(Model)]), findall((N,C), member(colorize(N,C), Model), Colorization).

However, this needs 2.8 seconds for all solutions, which seems a bit much for three vertices …

Still, I would prefer the global constraint (if it would work), because it is much more readable.