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 addnode(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 delnode(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)

		"returns all nodes in the dictionary"

		return self.order[:]

		return self.dict.keys()

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

		"""Returns the first node with no children or else the first node

		for x in self.okeys:

		only soft-deps on children. Returns None if all children on every

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

		node are hard-deps."""

				return x

		for node in self.order:

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

				return node

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

		zeros = []

		zerolist = []

		for node in self.nodes:

		for x in self.dict.keys():

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

			mys = string.split(x)

				zeros.append(node)

			if mys[0] != "blocks" and self.dict[x][0]==0:

		return zeros

				zerolist.append(x)

		return zerolist

	def depth(self, node):

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

		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)

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

		for node in self.nodes:

		zerolist = []

			if self.nodes[node][0]:

		for x in self.dict.keys():

				return False

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

		return True

				return 0

		return 1

		if len(self.dict)==0:

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

			return 1

		return len(self.nodes) == 0

		return 0

	def hasnode(self,mynode):

	def hasnode(self, node):

		return self.dict.has_key(mynode)

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

		return node in self.nodes

		mygraph=digraph()

		clone = digraph()

		for x in self.dict.keys():

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

			mygraph.dict[x]=self.dict[x][:]

		clone.order = self.order[:]

			mygraph.okeys=self.okeys[:]

		return clone

		return mygraph

	def child_nodes(self, node):

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

	def parent_nodes(self, node):

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

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