[Zope-CVS] CVS: Packages/pypes/pypes - graph.py:1.4

[Casey Duncan]

Update of /cvs-repository/Packages/pypes/pypes
In directory cvs.zope.org:/tmp/cvs-serv11242

Modified Files:
	graph.py 
Log Message:
implement shortestPath method that uses edge values


=== Packages/pypes/pypes/graph.py 1.3 => 1.4 ===
--- Packages/pypes/pypes/graph.py:1.3	Fri Aug  8 00:57:49 2003
+++ Packages/pypes/pypes/graph.py	Sat Aug  9 00:06:59 2003
@@ -264,8 +264,33 @@
         using Dijkstra's algorithm. Note, this does not work correctly if 
         edges have negative values
         """
-        raise NotImplementedError        
-               
+        nodes = PQueue()
+        nodes.insert(source, None)
+        pred = {}
+        while nodes:
+            n, nd = nodes.popMin()
+            referers, targets = self._nodes[n]
+            if targets is None:
+                continue
+            else:
+                if not isinstance(targets, self._nodeSetFactory):
+                    targets = (targets,)
+                for t in targets:
+                    td = self._edge_values[n, t]
+                    if nd is not None:
+                        td += nd
+                    if t in pred and td >= pred[t][1]:
+                        continue
+                    nodes.insert(t, td)
+                    pred[t] = n, td
+        if target in pred:
+            path = []
+            while target is not source:
+                path.append(target)
+                target, nil = pred[target]
+            path.append(source)
+            path.reverse()
+            return path
     
 class DirectedGraphNodes(ObjectNodeStore, Persistent):
     """Directed graph nodes accessor"""
@@ -601,22 +626,24 @@
             k.append(key)
     
     def popMin(self):
-        """Return the key with the minimum value and remove it from the queue"""
+        """Return the key, value pair with the minimum value and remove it from
+        the queue"""
         minval = self._keys.minKey()
         keys = self._keys[minval]
-        r = keys.pop()
+        k = keys.pop()
         if not keys:
             del self._keys[minval]
-        return r
+        return k, minval
     
     def popMax(self):
-        """Return the key with the maximum value and remove it from the queue"""
+        """Return the key, value with the maximum value and remove it from the 
+        queue"""
         maxval = self._keys.maxKey()
         keys = self._keys[maxval]
-        r = keys.pop()
+        k = keys.pop()
         if not keys:
             del self._keys[maxval]
-        return r
+        return k, maxval
     
     def __nonzero__(self):
         return bool(self._keys)