|
|
|---|
| |
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 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: |
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 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: |
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 allnodes(self): |
"returns all nodes in the dictionary" |
return self.order[:] |
return self.dict.keys() |
|
| |
def firstzero(self): | def firstzero(self): |
"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 |
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): | def allzeros(self): |
"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) |
| |
def hasallzeros(self): | def hasallzeros(self): |
"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 |
|
| |
def empty(self): | def empty(self): |
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 |
| |
def copy(self): | def copy(self): |
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() |
|
|
| |
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) |
