Search code examples
answer-set-programmingclingo

How do I tell my graph coloring problem program to only assign color 1 one time?


Basically, I have a graph coloring program where each node with an edge to another node has to be different colors. Here, is my code:

node(1..4).

edge(1,2).
edge(2,3).
edge(3,4).
edge(4,1).
edge(2,4).

color(1..3).

{ assign(N,C) : color(C) } = 1 :- node(N).

1 { assign(N,1) : color(1) } 1 :- node(N). %line in question

:- edge(N,M), assign(N,C), assign(M,C).

How would I tell the program to only assign color 1, once? The line labeled %line in question is the line giving me problems. Here is another solution I tried that didn't work:

node(1..4).

edge(1,2).
edge(2,3).
edge(3,4).
edge(4,1).
edge(2,4).

color(1..3).

{ assign(N,C) : color(C) } = 1 :- node(N).

:- edge(N,M), assign(N,C), assign(M,C).

vtx(Node, Color) :- node(Node), color(Color).

1 { vtx(N, 1) : color(1) } 1 :- node(N).

#show vtx/2.

If anyone could help me out it would be much appreciated.


Solution

  • In this simple case of restricting a single color to be used once, you can write the a single constraint

    :- assign(N, 1), assign(M, 1), node(N), node(M), N!=M.