Use this tag for the transitive closure of a relationship or when related to graph theory.
References:
Questions tagged [transitive-closure]
148 questions
46
votes
3 answers
Definition of a path/trail/walk
Many predicates define some kind of an acyclic path built from edges defined via a binary relation, quite similarly to defining transitive closure. A generic definition is thus called for.
Note that the notions defined in graph theory do not readily…
false
- 10,264
- 13
- 101
- 209
27
votes
1 answer
Definition of Reflexive Transitive Closure
Many predicates essentially use some form of transitive closure, only to discover that termination has to be addressed too. Why not solve this once and forever with closure0/3:
:- meta_predicate closure0(2,?,?).
:- meta_predicate closure(2,?,?).
:-…
false
- 10,264
- 13
- 101
- 209
15
votes
4 answers
Define graph in Prolog: edge and path, finding if there is a path between two vertices
I'm very new to Prolog. I defined in graph.pl the following graph:
And here's my Prolog code:
edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).
I understand it…
yak
- 3,770
- 19
- 60
- 111
10
votes
3 answers
More efficiently compute transitive closures of each dependents while incrementally building the directed graph
I need to answer the question: given a node in a dependency graph, group its dependents by their own transitive dependents which would be impacted by a particular start node.
In other words, given a node in a dependency graph, find the set of sets…
jayphelps
- 15,276
- 3
- 41
- 54
9
votes
2 answers
Depth First Search Algorithm Prolog
I am hoping you could help me with this.
I am trying to learn about Depth First search algorithm in Prolog and I have come across the following code
go(Start, Goal) :-
empty_stack(Empty_been_list),
stack(Start, Empty_been_list, Been_list),
…
Sean Gray
- 133
- 2
- 2
- 8
7
votes
2 answers
Spark example program runs very slow
I tried to use Spark to work on simple graph problem. I found an example program in Spark source folder: transitive_closure.py, which computes the transitive closure in a graph with no more than 200 edges and vertices. But in my own laptop, it runs…
c21
- 231
- 3
- 7
7
votes
1 answer
How to use Warshall's algorithm for transitive closure to determine canonical LR(1) parser closures?
I'm trying to implement Warshall's algorithm to quickly compute LR(1) closures.
I think I understand how it works for LR(0):
The nodes of the graph are LR items, like A → B • C
The edges are "transitions" starting from A → B • C to C → • D
The…
user541686
- 205,094
- 128
- 528
- 886
6
votes
4 answers
How to generate transitive closure of set of tuples?
What is the best way to generate transitive closure of a set of tuples?
Example:
Input Set((1, 2), (2, 3), (3, 4), (5, 0))
Output Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))
aioobe
- 413,195
- 112
- 811
- 826
6
votes
2 answers
In prolog, why doesn't adding "edge(X, Y) :- edge(Y, X)." alone work for converting a directed graph definition to an undirected graph
I'm just learning Prolog, and I'm reviewing lecture notes and all the notes say is that:
given the following definition for directed graphs:
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).
If we wanted to make this an undirected…
Leggy
- 147
- 7
5
votes
2 answers
Transitive closure from a list using Haskell
I need to produce transitive closure on list using Haskell.
So far I got this:
import Data.List
qq [] = []
qq [x] = [x]
qq x = vv (sort x)
vv (x:xs) = [x] ++ (member [x] [xs]) ++ (qq xs)
member x [y] = [(x1, y2) | (x1, x2) <- x, (y1, y2) <- qq…
Alex
- 468
- 1
- 9
- 19
4
votes
1 answer
SQL - Convert non-null adjacency list to path
I am working with some tables that represent a file system, and I need to select the full path of each folder as a flattened string.
The first table lists the details of each folder:
CREATE TABLE Folders(
FolderID int IDENTITY(1,1) NOT NULL,
…
JamesFaix
- 8,050
- 9
- 37
- 73
4
votes
1 answer
Stop condition for recursion in prolog
Here are the facts that I have in my knowledge base (http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/recursion.html (Recursion Exercise 2)):
taller(bob,mike). % bob is taller than mike
taller(mike,jim). % mike is taller than…
Karim Mtl
- 1,223
- 3
- 11
- 39
4
votes
1 answer
How to express a transitive relationship
I want to express a transitive relationship. If A references B and B references C then A references C. I have this:
proj(A).
proj(B).
proj(C).
ref(A,B).
ref(B,C).
When I query using proj(A) I obtain:
[46] ?-proj(A).
A = _639
What does "_639"…
P.Brian.Mackey
- 43,228
- 68
- 238
- 348
4
votes
2 answers
transitive closure over a symmetric relation in prolog
I am a prolog beginner and I want to create the "brother" relation.
The relation should be symmetric as in if brother(alin, alex) is true, brother(alex, alin) should be as well.
It should also be transitive as in if brother(alin, alex) and…
colegu
- 370
- 2
- 12
4
votes
3 answers
what is the difference between Cycle and circuit
I have confusion that what is the differnce between the two ?
Cycle and circuit so please make me sure by diagrams if possible.
what i have in mind is that the cycle is always in undirected graph the circuit is always a directed graph. please…
Sss
- 1,519
- 8
- 37
- 67