/* 

  Graph partition in Picat.

  From Pascal Van Hentenryck & Laurent Michel:
   "Constraint-based local search", page 6f.
  where the object is to partition a graph such that
   - the number of nodes in each partition is the same
   - the number of edges between each partition is minimized (the cost).
  
  The graph is from page 6 (the connections are in the array nodes below).
  
  There are 4 solution with minimal number of edges between 
  the two sets (5). Node 1 has been set to partition 1 (symmetry breaking).
  The first solution is the one in the book.

   {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 24}, {6, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}

  Here are the other three solutions:
    {1, 3, 4, 5, 7, 8, 9, 10, 11, 12, 20, 24}, {2, 6, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23}
    {1, 4, 5, 7, 8, 9, 10, 11, 12, 20, 22, 24}, {2, 3, 6, 13, 14, 15, 16, 17, 18, 19, 21, 23}
    {1, 4, 5, 8, 9, 10, 11, 12, 20, 22, 23, 24}, {2, 3, 6, 7, 13, 14, 15, 16, 17, 18, 19, 21}

  For three partitions (m=3), this model yields one solution with cost 7:
    {1, 2, 3, 4, 5, 7, 8, 9}, {10, 11, 12, 20, 21, 22, 23, 24}, {6, 13, 14, 15, 16, 17, 18, 19}
  
  For four partitions (m=4) the minimal cost is 10, e.g. the following solution (which is
  unique apart from symmetries)
    {1, 3, 4, 5, 7, 8}, {6, 13, 14, 15, 16, 17}, {9, 10, 11, 12, 20, 24}, {2, 18, 19, 21, 22, 23}


  Here are all optimal solutions for the possible partitions:

  m = 2
  [n = 24,m = 2,size = 12]

  1 = [1,2,3,4,5,7,8,9,10,11,12,24]
  2 = [6,13,14,15,16,17,18,19,20,21,22,23]
  z = 5

  m = 3
  [n = 24,m = 3,size = 8]

  1 = [1,2,3,4,5,7,8,9]
  2 = [10,11,12,20,21,22,23,24]
  3 = [6,13,14,15,16,17,18,19]
  z = 7

  m = 4
  [n = 24,m = 4,size = 6]

  1 = [1,3,4,5,7,8]
  2 = [6,13,14,15,16,17]
  3 = [9,10,11,12,20,24]
  4 = [2,18,19,21,22,23]
  z = 10

  m = 6
  [n = 24,m = 6,size = 4]

  1 = [1,3,4,12]
  2 = [10,11,20,22]
  3 = [6,15,16,17]
  4 = [5,7,8,9]
  5 = [2,21,23,24]
  6 = [13,14,18,19]
  z = 14

  m = 8
  [n = 24,m = 8,size = 3]

  1 = [1,2,3]
  2 = [15,16,17]
  3 = [20,22,23]
  4 = [6,13,14]
  5 = [4,5,7]
  6 = [8,9,10]
  7 = [11,12,24]
  8 = [18,19,21]
  z = 18

  m = 12
  [n = 24,m = 12,size = 2]




  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.


main => go.

go ?=>
  nolog,
  nodes(Nodes),
  N = Nodes.len,
  M = 2, % number of partitions  (2,3,4,6,12 i.e. the divisors of n)

  graph_partition(Nodes,M, X,Z),
  print_partition(X,N,M),
  println(z=Z),
  nl,
  fail,

  nl.

go => true.


%
% Show all optimal solutions
% 
go2 ?=>
  nolog,
  nodes(Nodes),
  N = Nodes.len,
  M = 2, % number of partitions  (2,3,4,6,12 i.e. the divisors of n)

  Z #= 5,
  graph_partition(Nodes,M, X,Z),
  % println(x=X),
  print_partition(X,N,M),
  println(z=Z),
  nl,
  fail,

  nl.

go2 => true.

%
% Show optimal solutions for the possible partitions.
% 
go3 ?=>
  nolog,
  nodes(Nodes),
  N = Nodes.len,
  foreach(M in 2..N, N mod M == 0)
    println(m=M),
    time2(graph_partition(Nodes,M, X,Z)),
    print_partition(X,N,M),
    println(z=Z),
    nl
  end,

  nl.

go3 => true.

%
% Print the partition
%
print_partition(X,N,M) =>
  foreach(I in 1..M)
    println(I=[J : J in 1..N, X[J] == I])
  end.

%
% Solve the graph partition problem:
% find the minimal value of Z.
%
graph_partition(Nodes,M, X,Z) =>
  N = Nodes.len,
  Size = N div M,
  println([n=N,m=M,size=Size]),
  
  % assign each number to a partition
  X = new_list(N),
  X :: 1..M, 

  % Number of edges between partitions. To be minimized.
  Z #= sum([
           sum([(P1 #= X[I])*(X[J] #= P2) : P1 in 1..M, P2 in P1+1..M])
           : I in 1..N, J in Nodes[I]]),

  % Ensure that we got the same number of elements (Size) 
  % in each partition.
  Gcc = $[P-Size : P in 1..M],
  global_cardinality(X,Gcc),

  X[1] #= 1, % symmetry breaking

  Vars = X ++ Gcc,
  if var(Z) then
    solve($[min(Z),ff],Vars)
  else
    solve(Vars)  
  end.


%
% data
%
nodes(Nodes) =>
  Nodes = {
{3,4},                % 1
{3,6},                % 2
{1,2},                % 3
{1,5,12},             % 4
{4,7,8},              % 5
{3,7,13,14,15,16,17}, % 6
{5,6,9},              % 7
{5,9},                % 8
{7,8,10,12},          % 9
{9,11,20},            % 10
{10,12,20,24},        % 11
{4,9,11,24},          % 12
{6,14},               % 13
{6,16,18},            % 14
{6,16},               % 15
{6,15,17,18},         % 16
{6,16,20},            % 17
{14,16,19,20,21},     % 18
{18,23},              % 19
{10,11,17,22},        % 20
{18,23},              % 21
{20,23},              % 22
{21,22,24},           % 23
{11,12,23}            % 24
}.