Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.oz.au (Richard O'keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Duplicate Solutions
Message-ID: <2986@goanna.oz.au>
Date: 16 Mar 90 08:12:04 GMT
References: <11500023@hpldola.HP.COM>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 78

In article <11500023@hpldola.HP.COM>,
patch@hpldola.HP.COM (Pat Chkoreff) writes:
> Occasionally I have written a predicate that yields duplicate solutions, and
> I've wondered how to make each solution occur uniquely.  For example, I have
> a multigraph:
> 	node(X).             % X is a node.
> 	edge(E, X, Y).       % E is a directed edge from node X to node Y.
> 	joined(X, Y).        % There exists an edge from node X to node Y.

The ideal thing, of course, would be to write down directly exactly what
you mean:

	joined(X, Y) :- E^edge(E, X, Y).

and have the system figure it out automatically.  Alas, even in NU Prolog
(where you write "some E edge(E, X, Y)" you still get the duplicates.
setof/3 *is* a good way to do it (bagof/3 won't do, precisely because
it *doesn't* eliminate duplicates):

	joined(X, Y) :-
		setof((X->Y), E^edge(E,X,Y), Arcs),
		member((X->Y), Arcs).

This is a quite general way of computing a projection without
duplicates:
	p(X1, ..., Xn) :-
		setof(*(X1,...,Xn), Y1^...^Ym^q(X1,...,Xn,Y1,...,Ym), L),
		member(*(X1,...,Xn), L).

This does not compute any unwanted answers, and it's even one of the few
cases where a broken setof/3 can get away with yielding L=[].

Don't knock this until you have tried it.  Any method which can handle
queries to joined(_,_) which are not ground is going to have to keep
track of the answers _somehow_.

Another approach is to distinguish between the repeated solutions
somehow, and return a particular representative.   For argument's sake,
let's suppose we add a new predicate
	representative(E)
which is to be true when E is the chosen representative for a group of
edges between the same nodes.  We have the constraint
	edge(E1, X, Y) & representative(E1) &
	edge(E2, X, Y) & representative(E2) -> E1 = E2
Then we can define
	joined(X, Y) :-
		edge(E, X, Y),
		representative(E).

This doesn't look at any solutions of edge/3 which are not relative,
and does not have to store or sort solutions.

Tim Finin wrote
:   You are correct, I think, in looking to change your data model
:   and/or algorithm to avoid generating duplicate solutions when
:   they are not appropriate.
Agreed.

:   joined(X, Y) :- edge(_, X, Y), !.
:   joined(X, Y) :- once(edge(_, X, Y)).
He also points out the problem, which is that these approaches only
work when called with X, Y both ground.

Sharon J Correll wrote
:   How about:
:   joined(X,Y) :- node(X), node(Y), an_edge(X, Y).
:   an_edge(X, Y) :- edge(_, X, Y), !.
which is fine.  This has no unexpected solutions.  The cost issue is
interesting, though.  Assuming that X and Y are both variables (the
worst case), that there are N nodes, E edges, and J solutions of
joined/2, we find

	setof method	cost = O(E + E.lg E + J)
	representative	cost = O(E + J)
	node/node/test	cost = O(N*N + J)

What the coefficients are depends on the Prolog you are using.  (A nice
fast setof wouldn't hurt).