How to iterate through 2d array in constraint in minizinc correctly?-CodePudding

I want to solve the problem of coloring the graph. It is the problem when a graph should be colored in a minimum number of colors subject to no adjacent vertices is colored in the same color. Here is my code with a toy graph.

int: N_Vertices=4;
int: N_Edges=3;
array[1..N_Edges, 1..2] of int: Adjacency;
Adjacency = [| 0, 1
             | 1, 2
             | 1, 3|];
array [1..N_Vertices] of var int: coloring;

constraint forall(e in 1..N_Edges)(coloring[Adjacency[e, 1]] != coloring[Adjacency[e, 2]]);
constraint forall(c in coloring)(c >= 0);

solve minimize (max(coloring));

But it gives

 WARNING: undefined result becomes false in Boolean context
  (array access out of bounds)
Playground:11:
  in call 'forall'
  in array comprehension expression
    with e = 1
  in binary '!=' operator expression
  in array access

  WARNING: model inconsistency detected
Playground:11:
  in call 'forall'
  in array comprehension expression
    with e = 1
  in binary '!=' operator expression
  in array access
=====UNSATISFIABLE=====

I suppose I do something wrong with Adjacency iteration in the first constraint. How should I do it properly?

CodePudding user response：

The problem is with Adjacency: The values are in base 0 but coloring has base 1 (array[1..N_Vertices]). MiniZinc has base 1 indexing as default.

The simplest is to change the indices in Adjacency to base 1 instead:

Adjacency = [| 1, 2
             | 2, 3
             | 2, 4|];

Then the solution would be:

coloring = array1d(1..4, [1, 0, 1, 1]);
----------
==========

If you want to keep the base 0 indices in Adjacency, then you have to do some other adjustments by replacing 1..N_Edges with 0..N_Edges-1:

int: N_Vertices=4;
int: N_Edges=3;
array[0..N_Edges-1, 1..2] of int: Adjacency;        

Adjacency = array2d(0..N_Edges-1,1..2,[| 0, 1
             | 1, 2
             | 1, 3|]);

array[0..N_Vertices-1] of var int: coloring;
constraint forall(e in 0..N_Edges-1)(coloring[Adjacency[e, 1]] != coloring[Adjacency[e, 2]]);
constraint forall(c in coloring)(c >= 0);

The answer:

coloring = array1d(1..4, [1, 0, 1, 1]);

Also, I recommend that you give coloring a proper domain instead of var int, e.g.:

array[0..N_Vertices-1] of 0..4: coloring; % recommended
% ....
% Then this is not needed:
% constraint forall(c in coloring)(c >= 0);