[Zope-CVS] CVS: Packages/pypes/pypes - exceptions.py:1.2 graph.py:1.5 interfaces.py:1.3

[Casey Duncan]

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

Modified Files:
	exceptions.py graph.py interfaces.py 
Log Message:
Implement topological sorting of graph nodes


=== Packages/pypes/pypes/exceptions.py 1.1.1.1 => 1.2 ===
--- Packages/pypes/pypes/exceptions.py:1.1.1.1	Mon Aug  4 00:46:02 2003
+++ Packages/pypes/pypes/exceptions.py	Sun Aug 10 22:32:15 2003
@@ -43,3 +43,6 @@
     
 class GraphValueError(PypesError):
     """Value could not be retreived from graph"""
+    
+class GraphCycleError(PypesError):
+    """Cycle detected during operation for acyclic graph"""


=== Packages/pypes/pypes/graph.py 1.4 => 1.5 ===
--- Packages/pypes/pypes/graph.py:1.4	Sat Aug  9 00:06:59 2003
+++ Packages/pypes/pypes/graph.py	Sun Aug 10 22:32:15 2003
@@ -27,6 +27,7 @@
 from pypes.interfaces import IGraph, IGraphEdges, IGraphNodes
 from pypes.exceptions\
     import IdentityError, IdentityKeyError, GraphLookupError, GraphValueError
+from pypes.exceptions import GraphCycleError
 
 _marker = object()
 
@@ -258,11 +259,11 @@
         if path[-1] is target:
             return path
     
-    def _dijkstraSearch(self, source, target):
-        """Return the shortest list of nodes connecting source to target
-        with the smallest cumulative distance derived from the edge values
-        using Dijkstra's algorithm. Note, this does not work correctly if 
-        edges have negative values
+    def _dijkstraSearch(self, source, target):        
+        """Return the list of nodes connecting source to target with the
+        smallest cumulative distance derived from the edge values using
+        Dijkstra's algorithm. Note, this does not work correctly if  edges have
+        negative values 
         """
         nodes = PQueue()
         nodes.insert(source, None)
@@ -270,9 +271,7 @@
         while nodes:
             n, nd = nodes.popMin()
             referers, targets = self._nodes[n]
-            if targets is None:
-                continue
-            else:
+            if targets is not None:
                 if not isinstance(targets, self._nodeSetFactory):
                     targets = (targets,)
                 for t in targets:
@@ -368,7 +367,42 @@
         return iter(self._nodes.keys())
 
     def iterTopological(self):
-        raise NotImplementedError
+        UNDISCOVERED = None
+        DISCOVERED = 1
+        EXPLORED = 2
+        status = {}
+        nodes = []
+        for n in self._nodes.keys():
+            if n not in status:
+                nodes.append(n)
+            while nodes:
+                dn = nodes[-1]
+                if status.get(dn) == EXPLORED:
+                    nodes.pop()
+                else:
+                    referers, targets = self._nodes[dn]
+                    is_explored = True
+                    if targets is not None:
+                        status[dn] = DISCOVERED
+                        if isinstance(targets, self._nodeSetFactory):
+                            for t in targets:
+                                ts = status.get(t)
+                                if ts == UNDISCOVERED:
+                                    is_explored = False
+                                    nodes.append(t)
+                                elif ts == DISCOVERED:
+                                    raise GraphCycleError, t
+                        else:
+                            ts = status.get(targets)
+                            if ts == UNDISCOVERED:
+                                is_explored = False
+                                nodes.append(targets)
+                            elif ts == DISCOVERED:
+                                raise GraphCycleError, targets
+                    if is_explored:
+                        status[dn] = EXPLORED
+                        nodes.pop()
+                        yield dn
     
     def degree(self, node):
         try:


=== Packages/pypes/pypes/interfaces.py 1.2 => 1.3 ===
--- Packages/pypes/pypes/interfaces.py:1.2	Fri Aug  8 00:57:49 2003
+++ Packages/pypes/pypes/interfaces.py	Sun Aug 10 22:32:15 2003
@@ -270,7 +270,7 @@
     def iterTopological():
         """Return an iterator of the nodes in topologically sorted order. 
         The graph must be directed and acyclic. If a cycle is encountered
-        or the graph is not directed raise GraphSortError.
+        during iteration, raise GraphCycleError.
         """
         
     def degree(node):