# Python Program to Find the Transitive Closure of a Graph

«
»

This is a Python program to find the transitive closure of a graph.

Problem Description

The transitive closure is computed by finding all vertex pairs i, j such that there is a path from i to j.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function transitive_closure that takes a Graph object as argument.
3. A dictionary reachable is created that can be indexed with two vertices and all the values set to infinity.
4. The above is implemented by creating a dictionary with keys as the start vertices and values as another inner dictionary. This inner dictionary contains keys as the destination vertices and value as the the corresponding value for each vertex pair.
5. reachable[v][w] will be True iff there is a path from vertex u to v.
6. For all edges from v to n, reachable[v][n] = True.
7. For all vertices v, reachable[v][v] = True.
8. The algorithm then performs reachable[v][w] = reachable[v][w] OR (reachable[v][p] AND reachable[p][w]) for each possible pair v, w of vertices.
9. The above is repeated for each vertex p in the graph.
10. The dictionary reachable is returned.
11. Formally, the algorithm consists of first defining P(k)[i][j] which is True iff there is a path from i to j using only the vertices 1, …, k where i and j are not necessarily included.
12. For all edges (i, j), P(0)[i][j] = True.
13. To find P(k)[i][j], note that if there is a path from i to j using only vertices 1, …, k, there is a path without k in it or there is a path with k.
14. If k is not present, P(k)[i][j] = P(k – 1)[i][j].
15. If k is present, P(k)[i][j] = (P(k – 1)[i][k] AND P(k – 1)[k][j]).
16. So we simply OR the above two values and set P(k)[i][j] to it.
17. The program is an implementation of this algorithm but uses only O(n2) space instead of O(n3) space which a straightforward implementation of the above algorithm would take.

Program/Source Code

Here is the source code of a Python program to find the transitive closure of a graph. The program output is shown below.

```class Graph:
def __init__(self):
# dictionary containing keys that map to the corresponding vertex object
self.vertices = {}

"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex

def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]

def __contains__(self, key):
return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
"""Add edge from src_key to dest_key with given weight."""

def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __len__(self):
return len(self.vertices)

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}

def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key

def add_neighbour(self, dest, weight):
"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight

def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()

def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]

def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to

def transitive_closure(g):
"""Return dictionary reachable.

reachable[u][v] = True iff there is a path from vertex u to v.

g is a Graph object which can have negative edge weights.
"""
reachable = {v:dict.fromkeys(g, False) for v in g}

for v in g:
for n in v.get_neighbours():
reachable[v][n] = True

for v in g:
reachable[v][v] = True

for p in g:
for v in g:
for w in g:
if reachable[v][p] and reachable[p][w]:
reachable[v][w] = True

return reachable

g = Graph()
print('add edge <src> <dest>')
print('transitive-closure')
print('display')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
suboperation = do[1]
if suboperation == 'vertex':
key = int(do[2])
if key not in g:
else:
elif suboperation == 'edge':
src = int(do[2])
dest = int(do[3])
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
else:

elif operation == 'transitive-closure':
reachable = transitive_closure(g)
print('All pairs (u, v) such that there is a path from u to v: ')
for start in g:
for end in g:
if reachable[start][end]:
print('{}, {}'.format(start.get_key(), end.get_key()))

elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()

print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()

elif operation == 'quit':
break```
Program Explanation

1. An instance of Graph is created.
2. A menu is presented to the user to perform various operations on the graph.
3. To find whether there is path between any pair, transitive_closure is called to get the dictionary reachable.

Note: Join free Sanfoundry classes at Telegram or Youtube
Runtime Test Cases
```Case 1:
add edge <src> <dest> <weight>
transitive-closure
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? transitive-closure
All pairs (u, v) such that there is a path from u to v:
1, 1
2, 2
What would you like to do? add edge 1 2 1
What would you like to do? transitive-closure
All pairs (u, v) such that there is a path from u to v:
1, 1
1, 2
2, 2
What would you like to do? add vertex 3
What would you like to do? add edge 2 3 1
What would you like to do? transitive-closure
All pairs (u, v) such that there is a path from u to v:
1, 1
1, 2
1, 3
2, 2
2, 3
3, 3
What would you like to do? quit

Case 2:
add edge <src> <dest>
transitive-closure
display
quit
What would you like to do? add vertex 0
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add edge 0 1
What would you like to do? add edge 0 2
What would you like to do? add edge 1 2
What would you like to do? add edge 2 0
What would you like to do? add edge 2 3
What would you like to do? transitive-closure
All pairs (u, v) such that there is a path from u to v:
0, 0
0, 1
0, 2
0, 3
1, 0
1, 1
1, 2
1, 3
2, 0
2, 1
2, 2
2, 3
3, 3
What would you like to do? quit```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Take Python Programming Mock Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10