Re: [eclipse-clp-users] Need help creating a custom reified constraint

From: Marco Gavanelli <marco.gavanelli_at_...17...>
Date: Thu, 08 Apr 2010 18:49:07 +0200
Dear Philipp,

Philipp Marcus wrote:
> Hi,
> 
> i need help creating a custom reified constraint. Given the following 
> program, whereby the predicate existsPath/3 tells, if there exists a 
> path between two nodes in a graph with the paths given in a List called 
> PathList.
> 
>    :-lib(propia).
>    :-lib(fd).
> 
>    :- export struct( path(sourceNode,targetNode,distance,edgesPassed)).
> 
>    existsPath(X,Y,PathList) :-
>         member(path{sourceNode:X,targetNode:Y},PathList) infers fd.
> 
> 
> a possible call of the program would be:
> 
> Y#::["X","Y","K","L","I"],
> existsPath("X",Y,
>     [path{sourceNode:"X",targetNode:"K"},
>     path{sourceNode:"X",targetNode:"I"}]).
> Now I need to create a reified version of that constraint, looking 
> something like:
> 
> existsPath(X,Y,PathList,B)
> 
> but I don't know how to do that. I would be really happy if someone 
> could help me with this problem.

First you have to write a predicate that is true whenever your 
constraint is false:

notmember(_,[]).
notmember(path{sourceNode:XA,targetNode:YA},[path{sourceNode:XB,targetNode:YB}|T]):-
	XA#\= XB #\/ YA#\= YB,
	notmember(path{sourceNode:XA,targetNode:YA},T).

Then you embed it into a predicate with the added boolean argument:

existsPath(X,Y,PathList,1):-
     member(path{sourceNode:X,targetNode:Y},PathList).
existsPath(X,Y,PathList,0):-
     notmember(path{sourceNode:X,targetNode:Y},PathList).

Then you use Propia:

existsPath_constr(X,Y,PathList,B):-
	existsPath(X,Y,PathList,B) infers most.

In your example:


[eclipse 22]: Y#::["X","Y","K","L","I"],
existsPath_constr("X",Y,
     [path{sourceNode:"X",targetNode:"K"},
     path{sourceNode:"X",targetNode:"I"}],B)			.

Y = Y{["I", "K", "L", "X", "Y"]}
B = B{[0, 1]}


Delayed goals:
	existsPath("X", Y{["I", "K", "L", "X", "Y"]}, [path("X", "K", _1044, 
_1058), path("X", "I", _1072, _1086)], B{[0, 1]}) infers most
Yes (0.00s cpu)
[eclipse 23]: Y#::["X","Y","K","L","I"],
existsPath_constr("X",Y,
     [path{sourceNode:"X",targe	tNode:"K"},
     	path{sourceNode:"X",tar	getNode:"I"}],B), B=1.

Y = Y{["I", "K"]}
B = 1


Delayed goals:
	existsPath("X", Y{["I", "K"]}, [path("X", "K", _1103, _1117), path("X", 
"I", _1131, _1145)], 1) infers most
Yes (0.00s cpu)
[eclipse 24]: Y#::["X","Y","K","L","I"],
existsPath_constr("X",Y,
     [path{sourceNode:"X",targetNode:"K"},
     path{sourceNode:"X",targetNode:"I"}],B), B=0.

Y = Y{["L", "X", "Y"]}
B = 0


Delayed goals:
	existsPath("X", Y{["L", "X", "Y"]}, [path("X", "K", _1103, _1117), 
path("X", "I", _1131, _1145)], 0) infers most
Yes (0.00s cpu)


Best,
Marco

-- 
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://www.ing.unife.it/docenti/MarcoGavanelli/
Received on Thu Apr 08 2010 - 16:49:18 CEST

This archive was generated by hypermail 2.3.0 : Thu Feb 22 2024 - 18:13:20 CET