Skip to content

Instantly share code, notes, and snippets.

@zahlenteufel
Last active August 29, 2015 13:57
Show Gist options
  • Save zahlenteufel/9718295 to your computer and use it in GitHub Desktop.
Save zahlenteufel/9718295 to your computer and use it in GitHub Desktop.
Transitive Reduction of a Graph

#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:

Sample

#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment