Prolog - transitive closure of a graph

Author

transitive closure of a graph

Ori80

2007-01-23, 7:18 pm

Hi. I'm a newbie and I'm learning prolog (swi-prolog).
I'm trying to write a function to calculate the transitive closure of a
directed acyclic graph.
The graph has to be represented by a list of arcs (e.g.
[[1,2],[2,3],[2,5],[3,4]] for a graph that has the vertex 1 connected
to the vertex 2, the vertex 2 connected to vertex 3 and 5, and so on).
What I need to do is to calculate the transitive closure of this graph
(that is [[1,2],[2,3],[2,5],[3,4], [2,4], [1,3], [1,4], [1,5]] for the
previous graph)

I had a look at the transitive_closure function for ugraphs but I
didn't understand so much how it works.

Thanks in advance!!

peter.vanweert@gmail.com

2007-01-23, 7:19 pm

Ori80 schreef:
> Hi. I'm a newbie and I'm learning prolog (swi-prolog).
> I'm trying to write a function to calculate the transitive closure of a
> directed acyclic graph.
> The graph has to be represented by a list of arcs (e.g.
> [[1,2],[2,3],[2,5],[3,4]] for a graph that has the vertex 1 connected
> to the vertex 2, the vertex 2 connected to vertex 3 and 5, and so on).
> What I need to do is to calculate the transitive closure of this graph
> (that is [[1,2],[2,3],[2,5],[3,4], [2,4], [1,3], [1,4], [1,5]] for the
> previous graph)

A very direct, naive implementation would be:

transitive_closure(Graph, Result) :-
findall([X,Z], (member([X,Y],Graph), member([Y,Z],Graph), \+
member([X,Z], Graph)), Found),
( Found == [] ->
Result = Graph
;
append(Graph, Found, Temp),
transitive_closure(Temp, Result)
).

Cheers,
Peter

Sponsored Links