|
|
|---|
| |
class digraph: | class digraph: |
def __init__(self): | def __init__(self): |
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: |
return | return |
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: |
return | return |
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 |
| |
def firstzero(self): | def firstzero(self): |
"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 |
|
return None | return None |
| |
def depth(self, mykey): |
|
depth=0 |
|
while (self.dict[mykey][1]): |
|
depth=depth+1 |
|
mykey=self.dict[mykey][1][0] |
|
return depth |
|
|
|
def allzeros(self): |
|
"returns all nodes with zero references, or NULL if no such node exists" |
|
zerolist = [] |
|
for x in self.dict.keys(): |
|
mys = string.split(x) |
|
if mys[0] != "blocks" and self.dict[x][0]==0: |
|
zerolist.append(x) |
|
return zerolist |
|
|
|
def hasallzeros(self): | def hasallzeros(self): |
"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) |
| |
def hasnode(self,mynode): |
|
return self.dict.has_key(mynode) |
|
| |
def copy(self): |
|
mygraph=digraph() |
|
for x in self.dict.keys(): |
|
mygraph.dict[x]=self.dict[x][:] |
|
mygraph.okeys=self.okeys[:] |
|
return mygraph |
|
| |
def elog_process(cpv, mysettings): | def elog_process(cpv, mysettings): |
mylogfiles = listdir(mysettings["T"]+"/logging/") | mylogfiles = listdir(mysettings["T"]+"/logging/") |
|
|
|---|
if not mycurkey: | if not mycurkey: |
print "!!! Error: circular dependencies:" | print "!!! Error: circular dependencies:" |
print | print |
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): |
print y,"depends on",x | print y,"depends on",x |
print | print |
sys.exit(1) | sys.exit(1) |
