Finding regions in Python

dom_tree.py

import networkx as nx


class DominatorTreeNode(object):
	__slots__ = ("value", "depth", "parent", "children")

	def __init__(self, value):
		self.value = value
		self.depth = None
		self.parent = None
		self.children = []

	def assign_depth(self, depth):
		self.depth = depth
		for child in self.children:
			child.assign_depth(depth+1)

	def as_digraph(self, graph):
		for child in self.children:
			g.add_edge(self.value, child.value)
			child.as_digraph(g)


class DominatorTree(object):
	def __init__(self, dominators):
		self.nodes = {}
		self.root = None

		for dominator, dominated in dominators.iteritems():
			dominator_node = self.nodes.get(dominator)
			if not dominator_node:
				dominator_node = DominatorTreeNode(dominator)
				self.nodes[dominator] = dominator_node
			dominated_node = self.nodes.get(dominator)
			if not dominated_node:
				dominated_node = DominatorTreeNode(dominated)
			if dominator_node is dominated_node:
				self.root = dominator_node
			else:
				dominator_node.children.append(dominated_node)
				dominated_node.parent = dominator_node

		self.root.assign_depth(0)

	def dominates(self, a, b):
		"""Checks if `a` dominates `b`."""
		a_node = self.nodes[a]
		b_node = self.nodes[b]
		while a_node.depth <= b_node.depth:
			if a_node is b_node:
				return True
			b_node = b_node.parent
		return False

	def as_digraph(self):
		"""Returns the tree as a directed graph."""
		g = nx.DiGraph()
		self.root.as_digraph(g)
		return g