self.dict={}

		"""Create an empty digraph"""

		#okeys = keys, in order they were added (to optimize firstzero() ordering)

		self.okeys=[]

		# { node : ( { child : hard_dep } , { parent : hard_dep } ) }

		self.nodes = {}

	def addnode(self,mykey,myparent):

		self.order = []

		if not self.dict.has_key(mykey):

			self.okeys.append(mykey)

	def add(self, node, parent, hard_dep=True):

			if myparent is None:

		"""Adds the specified node with the specified parent. If the dep

				self.dict[mykey]=[0,[]]

		is a hard-dep and the node already has a relationship to the parent

			else:

		the relationship is ensured to be hard."""

				self.dict[mykey]=[0,[myparent]]

				self.dict[myparent][0]=self.dict[myparent][0]+1

		if node not in self.nodes:

			self.nodes[node] = ({}, {})

			self.order.append(node)

		if not parent:

		if myparent and (not myparent in self.dict[mykey][1]):

			self.dict[mykey][1].append(myparent)

		if parent not in self.nodes:

			self.dict[myparent][0]=self.dict[myparent][0]+1

			self.nodes[parent] = ({}, {})

			self.order.append(parent)

	def delnode(self,mykey):

		if not self.dict.has_key(mykey):

		if parent in self.nodes[node][1]:

			if hard_dep:

				self.nodes[node][1][parent] = True

		else:

			self.nodes[node][1][parent] = hard_dep

		if node in self.nodes[parent][0]:

			if hard_dep:

				self.nodes[parent][0][node] = True

		else:

			self.nodes[parent][0][node] = hard_dep

	def remove(self, node):

		"""Removes the specified node from the digraph, also removing

		and ties to other nodes in the digraph. Does nothing if the node

		doesn't exist."""

		if node not in self.nodes:

		for x in self.dict[mykey][1]:

			self.dict[x][0]=self.dict[x][0]-1

		for parent in self.nodes[node][1]:

		del self.dict[mykey]

			del self.nodes[parent][0][node]

		while 1:

		for child in self.nodes[node][0]:

			try:

			del self.nodes[child][1][node]

				self.okeys.remove(mykey)

			except ValueError:

		del self.nodes[node]

				break

		self.order.remove(node)

	def allnodes(self):

	def contains(self, node):

		"returns all nodes in the dictionary"

		"""Checks if the digraph contains mynode"""

		return self.dict.keys()

		return node in self.nodes

	def all_nodes(self):

		return self.order[:]

	def child_nodes(self, node):

		return self.nodes[node][0].keys()

	def parent_nodes(self, node):

		return self.nodes[node][1].keys()

	def leaf_nodes(self, include_soft_deps=False):

		leaf_nodes = []

		for node in self.nodes:

			is_leaf_node = True

			if include_soft_deps:

				for child in self.nodes[node][0]:

					if self.nodes[node][0][child]:

						is_leaf_node = False

						break

			if is_leaf_node:

				leaf_nodes.append(node)

		return leaf_nodes

	def is_empty(self):

		"""Checks if the digraph is empty"""

		return len(self.nodes) == 0

	def clone(self):

		clone = digraph()

		clone.nodes = copy.deepcopy(self.nodes)

		clone.order = self.order[:]

		return clone

	# Backward compatibility

	addnode = add

	delnode = remove

	allnodes = all_nodes

	allzeros = leaf_nodes

	hasnode = contains

	empty = is_empty

	copy = clone

		"returns first node with zero references, or NULL if no such node exists"

		leaf_nodes = self.leaf_nodes()

		for x in self.okeys:

		if leaf_nodes:

			if self.dict[x][0]==0:

			return leaf_nodes[0]

				return x

		"returns 0/1, Are all nodes zeros? 1 : 0"

		return len(self.leaf_nodes() == 0)

		zerolist = []

		for x in self.dict.keys():

			if self.dict[x][0]!=0:

				return 0

		return 1

	def empty(self):

	def depth(self, node):

		if len(self.dict)==0:

		"""Find how many nodes are in the parent chain of the passed node

			return 1

		return 0

		This method doesn't make sense unless there is no more than one

		parent for each node. As this digraph is capable of having multiple

		parents on a node, this implementation chooses an arbitrary parent

		for calculations, stopping as soon as a loop is detected in order

		to mimic the sorts of counts that would have previously been

		returned.

		This method is only used by emerge's --tree option. That option

		needs to be reworked to not use this so that this method can be

		removed altogether."""

		parents = {}

		while self.nodes[node][1]:

			parent = self.nodes[node][1].keys()[0]

			if parent in parents:

				break

			parents[parent] = True

			node = parent

		return len(parents)

				for x in mygraph.dict.keys():

				for x in mygraph.allnodes():

					for y in mygraph.dict[x][1]:

					for y in mygraph.parent_nodes(x):