diff options
Diffstat (limited to 'lib/spack/external/altgraph/GraphAlgo.py')
| -rw-r--r-- | lib/spack/external/altgraph/GraphAlgo.py | 53 |
1 files changed, 29 insertions, 24 deletions
diff --git a/lib/spack/external/altgraph/GraphAlgo.py b/lib/spack/external/altgraph/GraphAlgo.py index b51e536314..f93e73dcda 100644 --- a/lib/spack/external/altgraph/GraphAlgo.py +++ b/lib/spack/external/altgraph/GraphAlgo.py @@ -1,7 +1,7 @@ -''' +""" altgraph.GraphAlgo - Graph algorithms ===================================== -''' +""" from altgraph import GraphError @@ -28,9 +28,9 @@ def dijkstra(graph, start, end=None): Adapted to altgraph by Istvan Albert, Pennsylvania State University - June, 9 2004 """ - D = {} # dictionary of final distances - P = {} # dictionary of predecessors - Q = _priorityDictionary() # estimated distances of non-final vertices + D = {} # dictionary of final distances + P = {} # dictionary of predecessors + Q = _priorityDictionary() # estimated distances of non-final vertices Q[start] = 0 for v in Q: @@ -44,7 +44,8 @@ def dijkstra(graph, start, end=None): if w in D: if vwLength < D[w]: raise GraphError( - "Dijkstra: found better path to already-final vertex") + "Dijkstra: found better path to already-final vertex" + ) elif w not in Q or vwLength < Q[w]: Q[w] = vwLength P[w] = v @@ -76,7 +77,7 @@ def shortest_path(graph, start, end): # Utility classes and functions # class _priorityDictionary(dict): - ''' + """ Priority dictionary using binary heaps (internal use only) David Eppstein, UC Irvine, 8 Mar 2002 @@ -92,22 +93,22 @@ class _priorityDictionary(dict): order. Each item is not removed until the next item is requested, so D[x] will still return a useful value until the next iteration of the for-loop. Each operation takes logarithmic amortized time. - ''' + """ def __init__(self): - ''' + """ Initialize priorityDictionary by creating binary heap of pairs (value,key). Note that changing or removing a dict entry will not remove the old pair from the heap until it is found by smallest() or until the heap is rebuilt. - ''' + """ self.__heap = [] dict.__init__(self) def smallest(self): - ''' + """ Find smallest item after removing deleted items from front of heap. - ''' + """ if len(self) == 0: raise IndexError("smallest of empty priorityDictionary") heap = self.__heap @@ -115,9 +116,11 @@ class _priorityDictionary(dict): lastItem = heap.pop() insertionPoint = 0 while 1: - smallChild = 2*insertionPoint+1 - if smallChild+1 < len(heap) and \ - heap[smallChild] > heap[smallChild+1]: + smallChild = 2 * insertionPoint + 1 + if ( + smallChild + 1 < len(heap) + and heap[smallChild] > heap[smallChild + 1] + ): smallChild += 1 if smallChild >= len(heap) or lastItem <= heap[smallChild]: heap[insertionPoint] = lastItem @@ -127,22 +130,24 @@ class _priorityDictionary(dict): return heap[0][1] def __iter__(self): - ''' + """ Create destructive sorted iterator of priorityDictionary. - ''' + """ + def iterfn(): while len(self) > 0: x = self.smallest() yield x del self[x] + return iterfn() def __setitem__(self, key, val): - ''' + """ Change value stored in dictionary and add corresponding pair to heap. Rebuilds the heap if the number of deleted items gets large, to avoid memory leakage. - ''' + """ dict.__setitem__(self, key, val) heap = self.__heap if len(heap) > 2 * len(self): @@ -152,15 +157,15 @@ class _priorityDictionary(dict): newPair = (val, key) insertionPoint = len(heap) heap.append(None) - while insertionPoint > 0 and newPair < heap[(insertionPoint-1)//2]: - heap[insertionPoint] = heap[(insertionPoint-1)//2] - insertionPoint = (insertionPoint-1)//2 + while insertionPoint > 0 and newPair < heap[(insertionPoint - 1) // 2]: + heap[insertionPoint] = heap[(insertionPoint - 1) // 2] + insertionPoint = (insertionPoint - 1) // 2 heap[insertionPoint] = newPair def setdefault(self, key, val): - ''' + """ Reimplement setdefault to pass through our customized __setitem__. - ''' + """ if key not in self: self[key] = val return self[key] |