Re: searchtree visualized as graph

Manuel Weindorf wrote:
> 
> ist it possible to visualize a searchtree like the one which results from a
> problem like that:
> 
> the edges of a graph are represented as siple facts:
> 
> e(a,c).
> e(c,b).
> e(b,d).
> e(d,c).
> e(a,e).
> 
> A subgraph is wanted asking the following question:
> 
> alldifferent( [V1,V2,V3,V4] ), e(V1,V2), e(V2, V3), e(V3,V4), e(V4,V2)



The library fd_search provides a generic search predicate
for finite domain problems (search/6) which has a built-in
facility to generate daVinci graphs.

It would normally be used like this:

:- lib(fd_search).
:- lib(fd).

top1(Nodes) :-
	Nodes = [V1,V2,V3,V4],	% variables
	Nodes :: [a,b,c,d],

	...,			% constraints

	search(Nodes, 0, input_order, indomain, complete,
		[node(daVinci)]).



Although in your example you are not using a standard labeling
predicate like indomain, you can still use search/6 when you
write your own choice-predicate. As follows:

:- lib(fd_search).
:- lib(fd).

top2(Nodes) :-
	Nodes = [V1,V2,V3,V4],	% variables
	Nodes :: [a,b,c,d],

	alldifferent(Nodes),	% constraints

	Edges = [e(V1,V2), e(V2, V3), e(V3,V4), e(V4,V2)],
	search(Edges, 0, input_order, choose_edge, complete,
		[node(daVinci)]).

choose_edge(e(X,Y)) :-
	e(X,Y).

e(a,c).
e(c,b).
e(b,d).
e(d,c).
e(a,e).



An additional hint (not related to visualisation): In your
code, you use the e/2 predicate to make choices, i.e. you
are labeling edges.  Alternatively, you could be labeling
nodes, but then you must have constraints for the edges.
The library propia gives you an easy way of doing this:

:- lib(propia).

top3(Nodes) :-
	Nodes = [V1,V2,V3,V4],	% variables
	Nodes :: [a,b,c,d],

	alldifferent(Nodes),	% constraints
	e(V1,V2) infers ac,
	e(V2,V3) infers ac,
	e(V3,V4) infers ac,
	e(V4,V2) infers ac,

	search(Nodes, 0, input_order, indomain, complete,
		[node(daVinci)]).

The "infers ac" annotation turns the (nondeterministic) e/2
predicate into a (deterministic) constraint that maintains
arc consistency. The search part can then simply label the nodes
using any of the standard finite-domain methods and heuristics.

-- 
 Joachim Schimpf              /             phone: +44 20 7594 8187
 IC-Parc, Imperial College   /            mailto:J.Schimpf@ic.ac.uk
 London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse