/* 

  Minimum Vertex Cover Problem in Picat.

  From GLPK:s example mvcp.mod
  """
  MVCP, Minimum Vertex Cover Problem 

  Written in GNU MathProg by Andrew Makhorin <mao@gnu.org>

  The Minimum Vertex Cover Problem in a network G = (V, E), where V
  is a set of nodes, E is a set of arcs, is to find a subset V' within
  V such that each edge (i,j) in E has at least one its endpoint in V'
  and which minimizes the sum of node weights w(i) over V'.

  Reference:
  Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
  A guide to the theory of NP-completeness [Graph Theory, Covering and
  Partitioning, Minimum Vertex Cover, GT1].
  """


  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 ?=>
  data(1,NumNodes,NumEdges,E),

  % x[i] = 1 means that node i is included into V' 
  X = new_list(NumNodes),
  X :: 0..1,

  % w[i] is weight of vertex i (all has weight 1)
  W = new_list(NumNodes,1),

  % we need to minimize the sum of node weights over V' 
  scalar_product(W,X,#=,Z),

  % each edge (i,j) must have node i or j (or both) in V' 
  foreach(I in 1..NumEdges)
     X[E[I,1]] + X[E[I,2]] #>= 1
  end,


  solve($[min(Z)], X),

  println(z=Z),
  println(x=X),
  fail,
  
  nl.

go => true.


%
% data
%

% """
% These data correspond to an example from [Papadimitriou].
% 
% Optimal solution is 6 (greedy heuristic gives 13)
% """
data(1,NumNodes,NumEdges,E) =>
  NumNodes = 19,
  NumEdges = 27,

  L = [A1,A2,A3,A4,A5,A6,A7,
       B1,B2,B3,B4,B5,B6,
       C1,C2,C3,C4,C5,C6],
  L = 1..L.len,

  E = {{A1,B1},
       {B1,C1},
       {A1,B2},
       {B2,C2},
       {A2,B3},
       {B3,C3},
       {A2,B4},
       {B4,C4},
       {A3,B5},
       {B5,C5},
       {A3,B6},
       {B6,C6},
       {A4,B1},
       {A4,B2},
       {A4,B3},
       {A5,B4},
       {A5,B5},
       {A5,B6},
       {A6,B1},
       {A6,B2},
       {A6,B3},
       {A6,B4},
       {A7,B2},
       {A7,B3},
       {A7,B4},
       {A7,B5},
       {A7,B6}}.