Prolog. Construct a transitive closure of a graph

Question

I'm very new to Prolog. I have such a graph:

edge(a,e).
edge(e,f).
edge(f,d).
edge(d,a).

I define a transitive closure as:

p(X,Y) :- edge(X,Y).
tran(X,Z) :- p(X,Y), p(Y,Z).

I need to construct a transitive closure of a graph. Please let me know how to proceed with it.

Does this answer your question? [How to express "ancestor" recursively](https://stackoverflow.com/questions/64048419/how-to-express-ancestor-recursively) — MWB, Nov 29 '20 at 23:00

score 2 · Answer 1 · answered Nov 29 '20 at 17:58

2

The problem with trans/2 is that it will only walk two edges, not an arbitrary number.

We can define a predicate tran(X, Z) that holds if edge(X, Z) holds, or edge(X, Y) and then tran(Y, Z). We thus in the latter follow one edge and then recurse on tran/2:

tran(X, Z) :-
    edge(X, Z).
tran(X, Z) :-
    edge(X, Y),
    tran(Y, Z).

answered Nov 29 '20 at 17:58

Willem Van Onsem

443,496
30
428
555

How do I add edges that satisfy a condition to a graph? – vlad-kom Nov 30 '20 at 18:50
@willemvanonsem - what about loops? Your program might loop forever. See https://stackoverflow.com/questions/27258188/prolog-eliminating-cycles-from-indirect-relation – peak Dec 14 '20 at 06:39
@peak: in that case you add an accomulator: a list with items already seen. – Willem Van Onsem Dec 14 '20 at 08:14

Prolog. Construct a transitive closure of a graph

1 Answers1