% 
% All paths (with a graph representation) in MiniZinc.
% 
% Problem from http://www.anselm.edu/homepage/mmalita/logic/message.txt
% """
% Email is out of order at St. Mary's College and the teacher wants 
% to tell Robert something urgent.
% The teacher meets Craig and asks him to tell Robert she wants to speak 
% with him. 
% Craig says that if he meets Robert its OK, but else he will send the message 
% to everyone he meets and the message will go further.
% Each student tells each student he meets that the teacher waits for Robert
% in her office.
% The students meet each other (we don't know in what order):
% 1) Craig meets John and Jason
% 2) Jason meets Kiki and Adam and David
% 3) Adam meets Scott and Jeremy
% 4) Jeremy meets John and Scott
% 5) Kiki meets Chris
% 6) Chris meets David and Adam
% 7) David meets Robert
%
% Do you think the teacher will wait for ever in her office?
% Display all the possible paths from Craig to Robert.
%
% """
% 

% This model is derived from the model message_sending.mzn.

% 
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

int: n = 10;
set of int: N = 1..n;
int: num_edges = 13;

int: Adam = 1;
int: Chris = 2;
int: Craig = 3;
int: David = 4;
int: Jason = 5;
int: Jeremy = 6;
int: John = 7;
int: Kiki = 8;
int: Robert = 9;
int: Scott = 10;

array[N] of var 0..n: x; % 0 is no edge
array[1..num_edges, 1..2] of N: graph;
var int: path_len = sum(i in N) (bool2int(x[i] > 0));

%
% all values are different (range 1..n) or 0
%
predicate all_different_except_0(array[int] of var int: x) =
  let {
      int: n = length(x)
   }
   in
   forall(i,j in 1..n where i != j) (
        (x[i] > 0 /\ x[j] > 0) -> x[i] != x[j]
   )
;


%
% y is the last element which is > 0. All elements after y is 0
%
predicate last_not_0(array[int] of var int: x, var int: y) =
   exists(i in N) (
      x[i] = y
      /\ % all elements in x after y are 0
      forall(j in i+1..n) (x[j] = 0)
      /\ % all elements in x before y are > 0
      forall(j in 1..i) (x[j] > 0)
   )
;

%
% all_paths
% 
% (Well, all paths are generated only if the solver generates all
%  possible solutions.)
%
predicate all_paths(array[int] of var int: x, 
                    array[int, 1..2] of var int: graph) =
   forall(i in 2..length(x)) (
     x[i] = 0
     \/
     (
       x[i] > 0
       /\
       x[i-1] > 0
       /\
       exists(j in index_set_1of2(graph)) (
         ( graph[j,1] = x[i-1] /\ graph[j,2] = x[i]   )
         \/
         ( graph[j,1] = x[i]   /\ graph[j,2] = x[i-1] )
       )
     )
   )
;

% solve satisfy;
% solve :: int_search(x, "first_fail", "indomain", "complete") satisfy;

% as a shortest path problem:  
solve :: int_search(x, "first_fail", "indomain", "complete") minimize path_len;


constraint
   all_different_except_0(x) 
   /\
   x[1] = Craig
   /\
   last_not_0(x, Robert)
   /\
   all_paths(x, graph)
;

%
% The graph
%
graph = array2d(1..num_edges, 1..2, 
  [
   Craig, John,
   Craig, Jason,
   Jason, Kiki,
   Jason, Adam, 
   Jason, David,
   Adam, Scott, 
   Adam, Jeremy,
   Jeremy, John,
   Jeremy, Scott,
   Kiki, Chris,
   Chris, David,
   Chris, Adam,
   David, Robert
  ]);