Minizinc models for common graph problems

coloring.mzn

%%% Graph Coloring

%% Constants.
int: V;
int: E = length(edges1d) div 2;
int: k;

set of int: NODES = 1..V;
set of int: EDGES = 1..E;
set of int: COLORS = 1..k;

array[int] of NODES: edges1d;
array[EDGES, 1..2] of NODES: edges = array2d(EDGES, 1..2, edges1d);

%% Variables.
array[NODES] of var COLORS: color;

%% Constraints.

constraint forall (i in EDGES) (
  color[edges[i,1]] != color[edges[i,2]]
);

k = 3;
solve satisfy;

max-stable.mzn

%%% Maximum Independent (Stable) Set

%% Constants.
int: V;
int: E = length(edges1d) div 2;

set of int: NODES = 1..V;
set of int: EDGES = 1..E;

array[int] of NODES: edges1d;
array[EDGES, 1..2] of NODES: edges = array2d(EDGES, 1..2, edges1d);

%% Variables.
array[NODES] of var bool: stable; % is node in stable set?
var NODES: k = sum(i in NODES)(bool2int(stable[i])); % size of stable set (to be maximized)

%% Constraints.

constraint forall (i in EDGES) (
  not( stable[edges[i,1]] /\ stable[edges[i,2]])
);

%% Solution.
solve maximize k;

output [
  "stable = \(stable)", "\n",
  "k = \(k)", "\n",
  "stable set = \({ v | v in NODES where stable[v] })", "\n",
];

min-coloring.mzn

%%% Minimum Graph Coloring

%% Constants.
int: V;
int: E = length(edges1d) div 2;
var int: k;

set of int: NODES = 1..V;
set of int: EDGES = 1..E;
set of int: COLORS = 1..V;

array[int] of NODES: edges1d;
array[EDGES, 1..2] of NODES: edges = array2d(EDGES, 1..2, edges1d);

%% Variables.
array[NODES] of var COLORS: color;

%% Constraints.

constraint forall (i in EDGES) (
  color[edges[i,1]] != color[edges[i,2]]
);

constraint forall (i in NODES) (
  color[i] <= k
);

%% Solution.
solve minimize k;

peterson5.dzn

V = 10;
edges1d = [
  1, 3,
  3, 5,
  5, 2,
  2, 4,
  4, 1,
  1, 6,
  2, 7,
  3, 8,
  4, 9,
  5, 10,
  6, 7,
  7, 8,
  8, 9,
  9, 10,
  10, 6
];