Menu
▾
▴
#17 Inspect tables
Dear,
first of all, thanks a lot for your help and your
reactivity.
I have some problems to inspects my tables.
Consider the folowing logic program (taken
from "Logic Programming and Model Checking"):
------------------------------------------
:-table reach/2.
trans(a,b).
trans(b,c).
trans(c,b).
trans(c,d).
reach(X,Y):-trans(X,Y).
reach(X,Y):-trans(X,Int),reach(Int,Y).
------------------------------------------
the goal :
?- reach(a,X). gives
X=c
X=d
X=b.
Is there a general way to know how the solver had
reached the goal?
Indeed, to reach 'c' we have first reach 'b' and to
reach 'd' we have first reach 'c'.
In fact, I would like to write a predicate such as
how_have_we_reach/2 wich give :
?-how_have_we_reach(a,d).
[a,b,c,d]
Is it possible?
thanks for your help, best regards,
Hugues
Logged In: NO
Hi Hugues,
The problem is that in any graph with a cycle, there may be
infinitely many paths between two nodes. For example, while
[a,b,c,d] is a path that shows you can reach d from a, so
are [a,b,c,b,c,d], [a,b,c,b,c,b,c,d], etc. So what you
probably want (?) are paths that don't include a cycle,
i.e., don't contain the same node twice. And this can be
specified, as for example:
:- import member/2 from basics.
trans(a,b).
trans(b,c).
trans(c,b).
trans(c,d).
reach(X,Y,P0,[Y|P0]) :- \+ member(Y,P0),trans(X,Y).
reach(X,Y,P0,P):-trans(X,Int),\+member(Int,P0),reach(Int,Y,[Int|P0],P).
Here you should call reach(S,T,[S],Path), and the Path will
be in reverse order.
Notice I didn't table this, since the check for membership
in the path will force termination. I could, of course,
table it, but I doubt that it would help.
If you're trying to do this for a very large graph and
efficiency is important, you would probably want to first
check that there is indeed a path between two nodes before
trying to find them. So you might add a call to
reach(Int,Y) just before the last call in the second rule
for reach/4.
Regards,
-David
Logged In: YES
user_id=13011
Originator: NO
Taken care of.