Home > Archive > Prolog > November 2007 > equivalentClass
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| alp@rsu.ru 2007-11-22, 4:28 am |
| Hello.
I need to represent equivalent relation in prolog (using perl
AI::Prolog or Mandarax).
I use the following rules
/* First two rules describe, that we have a symmetric relationship */
equivClass1(A,B):-equivClassSimple(A,B).
equivClass1(A,B):-equivClassSimple(B,A).
/* Last two rules describe, that we have transitive relationship */
equivClassTC(X,Z):-equivClass1(X,Z).
equivClassTC(X,Z):-equivClass1(X,Y),equivClassTC(Y,Z).
I have data
equivClassSimple(a,b).
equivClassSimple(b,c).
equivClassSimple(b,d).
equivClassSimple(d,e).
And I'm asking equivClassTC(X,Y) to select all equivalent class pairs.
And I'm getting infinite loop.
What am I doing wrong and how to describe such relationship?
| |
| Chip Eastham 2007-11-23, 4:25 am |
| On Nov 22, 3:49 am, a...@rsu.ru wrote:
> Hello.
> I need to represent equivalent relation in prolog (using perl
> AI::Prolog or Mandarax).
>
> I use the following rules
> /* First two rules describe, that we have a symmetric relationship */
> equivClass1(A,B):-equivClassSimple(A,B).
> equivClass1(A,B):-equivClassSimple(B,A).
> /* Last two rules describe, that we have transitive relationship */
> equivClassTC(X,Z):-equivClass1(X,Z).
> equivClassTC(X,Z):-equivClass1(X,Y),equivClassTC(Y,Z).
>
> I have data
> equivClassSimple(a,b).
> equivClassSimple(b,c).
> equivClassSimple(b,d).
> equivClassSimple(d,e).
>
> And I'm asking equivClassTC(X,Y) to select all equivalent class pairs.
> And I'm getting infinite loop.
> What am I doing wrong and how to describe such relationship?
This actually seems to come up fairly often in this group, as
a search here on "transitive closure" will illustrate.
The "transitive closure" of a relation is the equivalence
relation that minimally contains that given relation.
Another way to think about it is in terms of the connected
components of a graph. Using the original relation as the
edges of an undirected (simple) graph, find all the graph's
connected components, aka equivalence classes.
[BTW, you omitted one property of an equivalence relation
in your treatment, the reflexive property.]
The short answer is that to compute the equivalence classes
or connected components, we can avoid looping by ensuring
that paths from A to B do not revisit any nodes more than
once.
One way to implement this relies on assert to keep
track of which nodes have been visited. A purer Prolog
approach would be to introduce an auxiliary argument that
makes explicit the path/list of nodes visited while trying
to go from A to B, but at the expense of inefficiently
reconstructing connections time and again. Some Prolog
implementations have "tabling" of selected predicates,
which allows the "naive" approach you had in mind to
avoid infinite looping automatically.
Let's say your have your simple original data:
simple(a,b).
simple(b,c).
simple(b,d).
simple(d,e).
If you can provide bound values for the first and
second arguments, a transitive closure can be coded
as:
tc(A,B) :- tClosure([A],B).
tClosure([A|_],A).
tClosure([H|T],B) :-
(simple(H,X);simple(X,H)),
not(member(X,[H|T])),
tClosure([X,H|T],B).
The idea is to replace the initial node A in our
predicate tc/2 with a list of "visited" nodes in
the predicate tClosure/2, which we initially call
with first argument [A]. The predicate tc(A,B)
will succeed if and only if a path can be found
from A to B such that:
(i) each step in the path is either "simple" or
the inverse of "simple"
(ii) the path never "crosses" itself, ie. never
revisits a previous node
If you need to call the closure with unbound
arguments, then an approach using assert (or the
equivalent but behind-the-scenes management of
this using tabling) would be more efficient.
regards, chip
| |
| alp@rsu.ru 2007-11-23, 7:08 pm |
| On 23 =CE=CF=D1=C2, 07:59, Chip Eastham <hardm...@gmail.com> wrote:
> simple(a,b).
> simple(b,c).
> simple(b,d).
> simple(d,e).
>
> If you can provide bound values for the first and
> second arguments, a transitive closure can be coded
> as:
>
> tc(A,B) :- tClosure([A],B).
>
> tClosure([A|_],A).
> tClosure([H|T],B) :-
> (simple(H,X);simple(X,H)),
> not(member(X,[H|T])),
> tClosure([X,H|T],B).
>
Thank you for answer. The idea is clear, however, the rule tClosure([A|
_],A). doesn't lead to variable unification...
| |
| Chip Eastham 2007-11-23, 7:08 pm |
| On Nov 23, 9:17 am, a...@rsu.ru wrote:
> On 23 =CE=CF=D1=C2, 07:59, Chip Eastham <hardm...@gmail.com> wrote:
>
>
>
>
>
>
>
> Thank you for answer. The idea is clear, however, the rule tClosure([A|
> _],A). doesn't lead to variable unification...
I think what you're saying is that you get no satisfactory
results from calling tc(A,B) with both arguments unbound.
You can try calling tc(A,B) with just the first argument
bound, e.g. preceding the call to tc/2 with a generator
of arguments like member(A,[a,b,c,d,e]).
The particular example you gave had directed edges that
formed a strict hierarchy. In such a case the directed
paths cannot form loops, and the code accordingly can
prevent looping in a simpler way. But I gave the more
general solution because it seemed that may be your
question.
regards, chip
|
|
|
|
|