/* 

  Minimum Feedback Vertex Set Problem in Picat.

  From GLPK:s example vfvsp.mod
  """
  MFVSP, Minimum Feedback Vertex Set Problem

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

  The Minimum Feedback Vertex Set Problem for a given directed graph
  G = (V, E), where V is a set of vertices and E is a set of arcs, is
  to find a minimal subset of vertices, which being removed from the
  graph make it acyclic.

  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 Feedback Vertex Set, GT8].
  """


  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,N,NumEdges,E),

  % x[i] = 1 means that i is a feedback vertex 
  X = new_list(NumEdges),
  X :: 0..1,

  % """
  % It is known that a digraph G = (V, E) is acyclic if and only if its
  % vertices can be assigned numbers from 1 to |V| in such a way that
  % k[i] + 1 <= k[j] for every arc (i->j) in E, where k[i] is a number
  % assigned to vertex i. We may use this condition to require that the
  % digraph G = (V, E \ E'), where E' is a subset of feedback arcs, is
  % acyclic. 
  %
  % k[i] is a number assigned to vertex i 
  % """
  K = new_list(N),
  K :: 1..N,

  % the objective is to minimize the cardinality of a subset of feedback
  % vertices 
  Obj #= sum(X),

  % note that x[i] = 1 or x[j] = 1 leads to a redundant constraint 
  foreach(I in 1..NumEdges)
    K[E[I,2]] - K[E[I,1]] #>= 1 - NumEdges * (X[E[I,1]] + X[E[I,2]])
  end,

  Vars = X ++ K,
  solve($[min(Obj)],Vars),

  println(obj=Obj),
  println(x=X),
  println(k=K),
  nl,
  
  nl.

go => true.


%
% data
%

% From the GLPK model
% The optimal solution is 3
data(1,N,NumEdges,E) =>
  N = 15,
  NumEdges = 23,
  E = {
  {1,2},
  {2,3},
  {3,4},
  {3,8},
  {4,9},
  {5,1},
  {6,5},
  {7,5},
  {8,6},
  {8,7},
  {8,9},
  {9,10},
  {10,11},
  {10,14},
  {11,15},
  {12,7},
  {12,8},
  {12,13},
  {13,8},
  {13,12},
  {13,14},
  {14,9},
  {15,14}}.