# Graph coloring with s(CASP)

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)]
``````

That is fairly easy 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 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

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

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.