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

[Casey Duncan]

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

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


=== Packages/pypes/pypes/tests/test_graph.py 1.3 => 1.4 ===
--- Packages/pypes/pypes/tests/test_graph.py:1.3	Sat Aug  9 00:07:03 2003
+++ Packages/pypes/pypes/tests/test_graph.py	Sun Aug 10 22:32:19 2003
@@ -245,9 +245,58 @@
         value = 0
         for source, target in edges:
             self.failUnless(((source, target), value) in items)
-            value += 1    
+            value += 1
+    
+    def testIterTopologicalSimple(self):
+        objs = [self._newObj() for i in range(5)]
+        for i in range(4):
+            self.graph.edges.add(objs[i], objs[i+1])
+        objs.reverse()
+        self.assertEqual(list(self.graph.nodes.iterTopological()), objs)
+    
+    def testIterTopologicalWithCycle(self):
+        from pypes.exceptions import GraphCycleError
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2)
+        self.graph.edges.add(ob2, ob3)
+        self.graph.edges.add(ob3, ob1)
+        self.assertRaises(
+            GraphCycleError, list, self.graph.nodes.iterTopological())
+    
+    def testIterTopologicalNonTree(self):
+        objs = [self._newObj() for i in range(7)]
+        self.graph.edges.add(objs[0], objs[1])
+        self.graph.edges.add(objs[1], objs[2])
+        self.graph.edges.add(objs[2], objs[5])
+        self.graph.edges.add(objs[3], objs[0])
+        self.graph.edges.add(objs[3], objs[1])
+        self.graph.edges.add(objs[3], objs[2])
+        self.graph.edges.add(objs[3], objs[4])
+        self.graph.edges.add(objs[3], objs[5])
+        self.graph.edges.add(objs[3], objs[6])
+        self.graph.edges.add(objs[4], objs[5])
+        self.graph.edges.add(objs[6], objs[4])
+        tsort = list(self.graph.nodes.iterTopological())
+        self.assertEqual(len(tsort), len(objs))  
+        self.failUnless(objs[5] is tsort[0])
+        self.failUnless(objs[3] is tsort[-1])
+        idx = tsort.index
+        self.failUnless(idx(objs[0]) > idx(objs[1]))
+        self.failUnless(idx(objs[1]) > idx(objs[2]))
+        self.failUnless(idx(objs[6]) > idx(objs[4]))
+    
+    def testIterTopologicalDisconnected(self):
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.nodes.add(ob1)
+        self.graph.nodes.add(ob2)
+        self.graph.nodes.add(ob3)
+        tsort = list(self.graph.nodes.iterTopological())
+        self.assertEqual(len(tsort), 3)
+        self.failUnless(ob1 in tsort)
+        self.failUnless(ob2 in tsort)
+        self.failUnless(ob3 in tsort)
        
-    ## XXX Need to add transitiveClosure, iterTopological and shortestPath tests
+    ## XXX Need to add transitiveClosure tests
     
     def testDegree(self):
         ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
@@ -410,6 +459,8 @@
             v = values.pop()
             self.assertEqual(k, str(v))
             self.assertEqual(m, v)
+
+
         
 if __name__ == '__main__':
     unittest.main()