/* 

  Maximum Flow Problem, integer programming in Picat.

  From GLPK:s example maxflow.mod
  """
  MAXFLOW, Maximum Flow Problem

  Written in GNU MathProg by Andrew Makhorin <mao@mai2.rcnet.ru>

  The Maximum Flow Problem in a network G = (V, E), where V is a set
  of nodes, E within V x V is a set of arcs, is to maximize the flow
  from one given node s (source) to another given node t (sink) subject
  to conservation of flow constraints at each node and flow capacities
  on each arc.
  """

  One of many optimal solutions:
  flow = 29
  x = [6,23,10,0,0,10,23,4,15,4,7,8,11,18]

  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,S,T,NumEdges,E,A),
  
  % x[i,j] is elementary flow through arc (i,j) to be found 
  X = new_list(NumEdges),
  X :: 0..max(A),

  % total flow from s to t 
  Flow :: 0..sum(A),

  % Flow :: 0..100,
  
  foreach(I in 1..NumEdges)
    X[I] #=< A[I]
  end,

  foreach(I in 1..N)
    % node[i] is conservation constraint for node i 
    % 
    % summary flow into node i through all ingoing arcs 
    sum([X[K] : K in 1..NumEdges, E[K,2] == I]) + Flow*(I #= S)
    #= % must equal 
    % summary flow from node i through all outgoing arcs 
    sum([X[K] : K in 1..NumEdges, E[K,1] == I])  + Flow*(I #= T)
  end,
 
  % objective is to maximize the total flow through the network 
  solve($[max(Flow)],X),

  println(flow=Flow),
  println(x=X),
  nl,
  fail,
  
  nl.

go => true.

%
% data
%

% From GLPK maxflow.mod
% """
% These data correspond to an example from [Christofides]. 
%
% Optimal solution is 29 
% """
data(1,N,S,T,NumEdges,E,A) =>
  N = 9,
  S = 1,
  T = N,

  NumEdges = 14,
  E = {{1, 2}, 
       {1, 4},
       {2, 3},
       {2, 4},
       {3, 5},
       {3, 8},
       {4, 5},
       {5, 2},
       {5, 6},
       {5, 7},
       {6, 7},
       {6, 8},
       {7, 9},
       {8, 9}},
  A = [14,23,10, 9,12,18,26,11,25, 4, 7, 8,15,20].