The Kitchen Sink and Other Oddities

Atabey Kaygun

Transitive closure of a directed graph

Description of the problem

A directed graph \(G=(V,E)\) is called transitive if for every pair of vertices \(a,b\in V\) if there is a path from \(a\) to \(b\) then \((a,b)\in E\). The transitive closure of \(G\) is the smallest transitive subgraph of the complete graph \(K(V) := (V, V\times V)\) containing \(G\).

Today I will look into developing an algorithm which constructs the transitive closure of a directed graph.

A solution

The algorithm works as follows: for every pair of vertices \(a,b\in V\) we will check if there is a path between them. If this is the case, then we will add an edge of the form \((a,b)\) to \(E\).

 import igraph

 def transitiveClosure(G):
     for a in G.vs():
         for b in G.vs():
             u = a.get_shortest_paths(b)
             if len(u[0]) > 2:
                G.add_edge(a,b)
     return G

Consider the following graph before the closure operator.

 g = igraph.Graph(4)
 g.to_directed()
 g.add_edges([(0,1),(1,2),(0,2),(2,3)])
image

And now, after the closure operator.

image