/* 

  Global constraint binary tree in Picat.

  From Global constraint catalog:
  http://www.emn.fr/x-info/sdemasse/gccat/Cbinary_tree.html
  """
  Constraint

      binary_tree​(NTREES,​NODES)​
  ...
  Purpose

     Cover the digraph G described by the NODES collection with NTREES 
     binary trees in such a way that each vertex of G belongs to exactly 
     one binary tree. The edges of the binary trees are directed from 
     their leaves to their respective root.
  
  Example
      (
      2,<
      index-1 succ-1,
      index-2 succ-3,
      index-3 succ-5,
      index-4 succ-7,
      index-5 succ-1,
      index-6 succ-1,
      index-7 succ-7,
      index-8 succ-5
      >
      )

      The binary_tree constraint holds since its second argument corresponds 
      to the 2 (i.e., the first argument of the binary_tree constraint) 
      binary trees depicted by Figure 4.38.1. [See the referred page and below]
  """
  

  The graph (two trees):
        1    7  
       /\    | 
      5  6   4
     / \  
    3   8
    |   
    2   


  Notes:

  1) This model uses a brute force variant by building a 
     "progress matrix" where each step states the parent
     node in the tree.
     The last row contains is all the parents.
     For the example above the following parent matrix
     is created:    

       tree = [1,3,5,7,1,3,7,5]
       Parents:
       [1,3,5,7,1,3,7,5]
       [1,5,1,7,1,5,7,1]
       [1,1,1,7,1,1,7,1]
       [1,1,1,7,1,1,7,1]
       [1,1,1,7,1,1,7,1]
       [1,1,1,7,1,1,7,1]
       [1,1,1,7,1,1,7,1]
       [1,1,1,7,1,1,7,1]
       num_trees = 2
       roots = [1,7]
       non_roots = [2,3,4,5,6,8]
       cycles = []

     Note that in the successor array (Tree), the root(s) has themselves as 
     a successor.

  2) It assumes that the successors represents a tree,
     and don't check for cycles. Cycles will be shown 
     in the parent matrix as alternating parents. 

       tree = [1,3,2,4,5,6,8,7]
       [1,3,2,4,5,6,8,7]
       [1,2,3,4,5,6,7,8]
       [1,3,2,4,5,6,8,7]
       [1,2,3,4,5,6,7,8]
       [1,3,2,4,5,6,8,7]
       [1,2,3,4,5,6,7,8]
       [1,3,2,4,5,6,8,7]
       [1,2,3,4,5,6,7,8]
       num_trees = 8
       roots = [1]
       cycles = [[2,3],[7,8]]

     If the tree contains a cycle the value of NumTrees is not
     reliable.

     Perhaps this should be detected in the model as well 
     (and not just after the fact).

  3) The model is multidirectional, i.e. it may generate trees
     given just the value of num_trees.


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

*/

import cp.
% import sat.

main => go.

go =>
  nolog,
  N = 8,

  % successors
  Tree = new_list(N),
  Tree :: 1..N,
  
  NumTrees :: 1..N,


  % the "parent matrix"
  Parents = new_array(N,N),
  Parents :: 1..N,

  %       1 2 3 4 5 6 7 8
  Tree = [1,3,5,7,1,1,7,5], % the example from the description
  % Tree = [1,3,5,7,1,3,7,5], % the example from above
  % Tree = [1,1,1,2,2,3,3,4], % as binary as we can come with 8 nodes...
  % Tree = [1,1,1,1,2,5,6,7], % 1 has three nodes, else is down from 2
  
  % The following has two cycles, 2<->3, 7<->8 which is shown 
  % in the parent matrix as alternating successors.
  % Tree = [1,3,2,4,5,6,8,7],
  % Tree = [1,2,3,4,5,7,8,6], % triple cycle 6->7->8

  % NumTrees = 2,

  binary_tree(NumTrees, Tree,Parents),

  Vars = Tree.vars ++ Parents.vars ++ [NumTrees],
  solve($[min,split],Vars),

  Roots = [I : I in 1..N, Parents[1,I] == I],
  NonRoots = [I : I in 1..N, not membchk(I,Roots)],

  % Identify cycles (from cycle.pi)
  Cycles1 = new_map(),
  foreach(J in 1..N)
    T = [Parents[I,J] : I in 1..N].remove_dups,
    foreach(K in T)
      Cycles1.put(J,Cycles1.get(J,[])++[K])
    end
  end,
  Cycles = [V.sort : K=V in Cycles1, V.len > 1,
                     % A cycle does not include any root node
                     C = [1 : R in Roots, membchk(R,V)],
                     C.len == 0].remove_dups,  

  % Cycles.len > 0,  % Checking for cycles
  % Cycles.len == 1,
  % Cycles[1].len == 6,

  println(tree=Tree),
  println("Parents:"),
  foreach(Row in Parents)
    println(Row.to_list)
  end,
  println(num_trees=NumTrees),
  println(roots=Roots),
  println(non_roots=NonRoots),
  
  println(cycles=Cycles),
  nl,
  fail,
  
  nl.


binary_tree(NumTrees,Tree,Parents) =>
  N = Tree.len,
  
  % first row is the tree
  foreach(J in 1..N) 
     Parents[1,J] #= Tree[J]
  end,
  % now: each step gives the path nearer the root
  foreach(I in 2..N)
     foreach(J in 1..N) 
        % Parents[I,J] #= Tree[Parents[I-1,J]]
        element(Parents[I-1,J],Tree,Parents[I,J])
     end
  end,
  nvalue(NumTrees, [Parents[N,J] : J in 1..N]).