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.
Re: Can this be done in SQL? Find the transitive relation ... I am strugling get the following done in SQL.... http://www.bookpool.com/sm/0977671542, section on transitive closure... There are several key graph concepts that would guide your intuition ... Figure 6.5: Reachability as an equivalence relation: graph from fig. ... (comp.databases.oracle.server)
Re: Help needed: Is Quick-Union-Find the right solution to this problem ? ... That's a solved problem (checking for cycles in a directed graph using ... > What you want is a "transitive closure" of the graph. ... I did a bit of research and studied two approaches to Warshall... which is pretty easy to accomplish or I might have an array of strings ... (comp.programming)
Re: Knowledge in Action (Reiter) - example 2.1.1 ...Logical Foundations for Specifying and Implementing Dynamical ... transitive closure of a graph, G, and says that the following "naive" ... model of the above naive definition for transitive closure.... (sci.logic)
Knowledge in Action (Reiter) - example 2.1.1 ... "Consider the directed graph with two vertices a and b, and with a single directed edge G. ... It is easy to check that this structure is a model of the above naive definition for transitive closure.... (sci.logic)
Re: Transitive Order of a Relation ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ... The transitive order of a transitive relation is 1. ... (sci.math)
