/* 
 * Closed path search in CHR(chr)
 * Author: Seiji OGAWA, 2011-03-31
 * 
 * Examples are taken from:
 *   http://dtai.cs.kuleuven.be/CHR/examples.shtml
 *
 * If you'd like to change parameter N, 
 * please change the 1st argument of query: start("N").
 *
 */

% ノード番号I(I<N)毎に, I, I+1, I+2の3頂点からなるedge群を初期グラフとして与える
% N = 5 のときの初期グラフは
%   edge(1,2), edge(2,3), edge(3,1).
%   edge(2,3), edge(3,4), edge(4,2).
%   edge(3,4), edge(4,5), edge(5,3).
%   edge(4,5), edge(5,1), edge(1,4).

:- use_module(library(chr)).
:- chr_option(optimize, full).
%:- chr_type list(X) ---> [] ; [X|list(X)].
:- chr_constraint e(+dense_int), edge(+dense_int, +dense_int), cycle(+int, +int, +int), 
                  i(+int, +int), j/0, f/1, start/1, time/1, list/1.
%:- chr_trace.

start(S) <=>
  cputime(X),
  i(S, 0),
  list([]), 
  cputime(Y),
  Z is Y-X,
  time(Z).

i(M, I), list(H) <=> I < M | I1 is I+1, i(M, I1), list([I|H]).
i(M, M) <=> j.
j, list([HX, HY, HZ | R]) <=>
  edge(HX, HY), edge(HY, HZ), edge(HZ, HX), list([HY, HZ | R]), f(HX).
list([HX, HY, HZ | R]) <=> 
  edge(HX, HY), edge(HY, HZ), edge(HZ, HX), list([HY, HZ | R]).
list([HX, HY]), f(HZ) <=> 
  edge(HX, HY), edge(HY, HZ), edge(HZ, HX).

findcycle @ edge(X, Y), edge(Y, Z), edge(Z, X) <=> cycle(X, Y, Z).