From: Joachim Schimpf <j.schimpf_at_icparc.ic.ac.uk>

Date: Fri 03 Aug 2001 05:58:31 PM GMT

Message-ID: <3B6AE647.5E51708D@icparc.ic.ac.uk>

Date: Fri 03 Aug 2001 05:58:31 PM GMT

Message-ID: <3B6AE647.5E51708D@icparc.ic.ac.uk>

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/eclipseReceived on Fri Aug 03 19:00:55 2001

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:09 PM GMT GMT
*