Transitive Reduction of a Graph

Transitive Reduction.md

#Transitive Reduction

Given a DAG (directed acyclic graph), it computes the minimal subgraph that has the same transitive closure. This is the most comfortable way of visualizing for example a partial order (with is transitive).

Uses Graphviz to visualize the results:

transitive_reduction.py

#!/usr/bin/python

# Transitive Reduction:
# Given a DAG (directed acyclic graph), it computes the minimal subgraph
# that has the same transitive closure. This is the most comfortable way 
# of visualizing for example a partial order (with is transitive).

graph = [[1,2,3],[],[3,4,5],[5],[5],[],[5,7],[4]] #adjacency list of G

print "digraph G {"
print "  subgraph cluster_0 {"
print "    label = \"before\";"

N = len(graph)

for i in xrange(N):
	print "   ", i;
	for other in graph[i]:
		print "   ", i, "->", str(other)+";"
print "  }"

n = len(graph)
indeg = n*[0]
for vecs in graph:
	for i in vecs:
		indeg[i] += 1

indegs = [[] for i in xrange(n)]
for i in xrange(n):
	indegs[indeg[i]].append(i)


def decreaseIndegree(e):
	global indeg
	g = indeg[e]
	indeg[e] -= 1
	indegs[g].remove(e)
	indegs[g-1].append(e)

def remove(r, elems):
	global grafo, indeg
	for e in elems:
		if e in graph[r]:
			graph[r].remove(e)
			decreaseIndegree(e)

def removeRoot(r):
	global graph, indeg
	children = graph[r]
	for child in children:
		decreaseIndegree(child)

def bfs(r):
	global graph
	INF = 10000
	dist = n * [INF]
	dist[r] = 0
	queue = [r]
	while queue:
		node = queue.pop()
		remove(r, [i for i in graph[node] if dist[i]==1])
		for child in graph[node]:
			if dist[child] == INF:
				queue.append(child)
			dist[child] = min(dist[child], dist[node]+1)

while indegs[0]:
	root = indegs[0].pop()
	bfs(root)
	removeRoot(root)

print "  subgraph cluster_after {"
print "    label = \"after\";"

for i in xrange(len(graph)):
	print "    ", i+N, " [label = \"" + str(i) + "'\"];"
	for other in graph[i]:
		print "   ", i+N, "->", other+N, ";"

print "  }" #close after digraph
print "}" #close digraph