digraph.py

class Digraph:
	def __init__(self):
		self.d = {}

	def has(self, x, y):
		return x in self.d and y in self.d[x]

	def _safe_get(self, x):
		return self.d.setdefault(x, set())

	def add(self, x, y):
		if x == y: raise ValueError("reflexive edge is not allowed")
		self._safe_get(x).add(y)

	def rem(self, x, y):
		if x in self.d:
			self.d[x].discard(y)

	def keys(self):
		return self.d.keys()

	def transitive_closure(self):
		for x in self.d:
			for y in self.d:
				for z in self._safe_get(y):
					if self.has(x, y):
						self.add(x, z)

	def transitive_reduce(self):
		closure = self.copy()
		closure.transitive_closure()
		for x in self.d:
			for y in self.d:
				for z in closure._safe_get(y):
					if closure.has(x, y):
						self.rem(x, z)

	def dump(self):
		for x in self.d:
			for y in self.d[x]:
				print "[" + x + "] -> [" + y + "]"
				
	def copy(self):
		d = Digraph()
		for x in self.d:
			for y in self.d[x]:
				d.add(x, y)
		return d