library(cycle)

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.	
	

About

• Author: Lukasz Domagala
• Copyright © www.redber.pl
• Date: 2010/06/05 21:41