[ Reference Manual | Alphabetic Index ]

# library(cycle)

Cycle constraint   [more]

## Predicates

cycle(+Edges, ++EdgeWeights, -CycleCost)
A constraint that forces a Hamiltonian cycle in a directed graph
cycle(+Edges, ++EdgeWeights, -CycleCost, ++Configuration)
A constraint that forces a Hamiltonian cycle in a directed graph

## Description

```	A configurable constraint that forces the existence of a Hamiltonian cycle in a directed graph.
The constraint uses the ic and eplex libraries to achieve different levels of filtering. For more
details see cycle/4.
Parts of the filtering algorithm have been inspired by or are implementations of ideas presented by
John H.Hooker in "Rossi F., van Beek P., Walsh T. (Eds.), Handbook of Constraint Programming,
chap. 15. 2006 Elsevier.".

The constraint will be refined and new filtering techniques will be added as time will allow to
work on the subject.
```

## Examples

```
:-lib(cycle).
:-lib(ic).
:-lib(branch_and_bound).
cycle_example:-
%edge weight matrix,
%the example data has been provided by Prof. Antoni Niederliński
EdgeWeightMx=[](
[](  0,384,484,214,234,267,524,656,446,371,459,561,585,683,634,751),
[](384,  0,156,411,296,167,339,379,340,432,485,545,483,500,565,642),
[](484,156,  0,453,323,217,213,223,281,442,452,479,394,370,500,516),
[](214,411,453,  0,130,259,413,601,303,157,245,356,422,542,427,585),
[](234,296,323,130,  0,129,310,491,212,178,261,335,354,465,403,517),
[](267,167,217,259,129,  0,255,389,205,265,318,391,348,421,430,516),
[](524,339,213,413,310,255,  0,188,134,344,319,297,181,161,295,303),
[](656,379,223,601,491,389,188,  0,322,532,507,485,363,260,477,430),
[](446,340,281,303,212,205,134,322,  0,204,181,196,143,242,220,306),
[](371,432,442,157,178,265,344,532,204,  0, 86,199,300,428,268,433),
[](459,485,452,245,261,318,319,507,181, 86,  0,113,220,382,182,347),
[](561,545,479,356,335,391,297,485,196,199,113,  0,156,323, 75,244),
[](585,483,394,422,354,348,181,363,143,300,220,156,  0,167,114,163),
[](683,500,370,542,465,421,161,260,242,428,382,323,167,  0,269,170),
[](634,565,500,427,403,430,295,477,220,268,182, 75,114,269,  0,165),
[](751,642,516,585,517,516,303,430,306,433,347,244,163,170,165,  0)
),
%the cities are: Szczecin,Gdańsk,Olsztyn,Zielona Góra,Poznań,Bydgoszcz,Warszawa,
%Białystok,Łódz,Wrocław,Opole,Katowice,Kielce,Lublin,Kraków,Rzeszów.

dim(EdgeWeightMx,[CityCount,CityCount]),
length(EdgeDstCityLi,CityCount),
%the edge variables' domains, any city can be reached from any other
ic:(EdgeDstCityLi#::1..CityCount),
%the edges (i,j) where i==j will be removed by the constraint
cycle(EdgeDstCityLi,EdgeWeightMx,SumOfEdgeWeights),

%search
cputime(StartTime),
SearchGoal=search(EdgeDstCityLi, 0, most_constrained, indomain_max, complete, []),
bb_min(SearchGoal, SumOfEdgeWeights, bb_options{strategy:dichotomic}),
cputime(EndTime),
SearchTime is EndTime - StartTime,

%print result
printf("Search time=%2.2fs  ",[SearchTime]),printf("Cost=%w",[SumOfEdgeWeights]),nl,
write("Edges="),writeln(EdgeDstCityLi),
true.
```