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

[Casey Duncan]

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

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


=== Packages/pypes/pypes/tests/test_graph.py 1.2 => 1.3 ===
--- Packages/pypes/pypes/tests/test_graph.py:1.2	Fri Aug  8 00:57:54 2003
+++ Packages/pypes/pypes/tests/test_graph.py	Sat Aug  9 00:07:03 2003
@@ -308,24 +308,28 @@
         self.assertEqual(list(self.graph.nodes.sources(ob3, 1)), [ob1, ob2])
         self.assertEqual(list(self.graph.nodes.sources(ob2, 1)), [ob1, ob2])
         self.assertEqual(list(self.graph.nodes.sources(ob1, 1)), [ob1, ob2])
-        
-    def testShortestPathWithoutValues(self):
+    
+    def _makeMatrix(self):
         nodes = {}
         for y in range(5):
             for x in range(5):
                 n = nodes[x,y] = self._newObj()
                 if x:
                     if (x + y) % 2:
-                        self.graph.edges.add(nodes[x-1, y], n)
+                        self.graph.edges.add(nodes[x-1, y], n, 1)
                     else:
-                        self.graph.edges.add(n, nodes[x-1, y])
+                        self.graph.edges.add(n, nodes[x-1, y], 1)
                 if y:
                     if (x + y) % 2:
-                        self.graph.edges.add(n, nodes[x, y-1])
+                        self.graph.edges.add(n, nodes[x, y-1], 1)
                     else:
-                        self.graph.edges.add(nodes[x, y-1], n)
+                        self.graph.edges.add(nodes[x, y-1], n, 1)
                 elif not x:
                     self.graph.nodes.add(n)
+        return nodes
+        
+    def testShortestPathMatrixWithoutValues(self):
+        nodes = self._makeMatrix()
         result = self.graph.edges.shortestPath(nodes[0, 0], nodes[4, 4])
         self.failIf(result is None)
         i, x1, y1 = 0, 0, 0
@@ -343,7 +347,40 @@
         ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
         self.graph.edges.add(ob1, ob2)
         self.graph.edges.add(ob3, ob2)
-        self.assertEqual(self.graph.edges.shortestPath(ob1, ob3), None)        
+        self.assertEqual(self.graph.edges.shortestPath(ob1, ob3), None) 
+        
+    def testShortestPathWithValues(self):
+        objs = [self._newObj() for i in range(5)]
+        self.graph.edges.add(objs[0], objs[1], 10)
+        self.graph.edges.add(objs[0], objs[2], 2)
+        self.graph.edges.add(objs[2], objs[1], 10)
+        self.graph.edges.add(objs[2], objs[3], 1)
+        self.graph.edges.add(objs[3], objs[4], 1)
+        self.graph.edges.add(objs[4], objs[1], 3)
+        self.assertEqual(
+            self.graph.edges.shortestPath(objs[0], objs[1], 1),
+            [objs[0], objs[2], objs[3], objs[4], objs[1]])
+    
+    def testShortestPathMatrixWithValues(self):
+        nodes = self._makeMatrix()
+        result = self.graph.edges.shortestPath(nodes[0, 0], nodes[4, 4], 1)
+        self.failIf(result is None)
+        i, x1, y1 = 0, 0, 0
+        path = [nodes[x1, y1]]
+        while x1 < 4 or y1 < 4:
+            if i % 2:
+                y1 += 1
+            else:
+                x1 += 1
+            path.append(nodes[x1, y1])
+            i += 1
+        self.assertEqual(result, path)
+            
+    def testShortestPathWithValuesUnreachable(self):
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2, 3)
+        self.graph.edges.add(ob3, ob2, 4)
+        self.assertEqual(self.graph.edges.shortestPath(ob1, ob3, 1), None)
         
 class TestDirectedIdGraph(PypesTestCase, TestDirectedGraph):
     
@@ -365,8 +402,14 @@
             self.q.insert(str(i), i)
         values.sort()
         while self.q:
-            self.assertEqual(self.q.popMin(), str(values.pop(0)))
-            self.assertEqual(self.q.popMax(), str(values.pop()))
+            k, m = self.q.popMin()
+            v = values.pop(0)
+            self.assertEqual(k, str(v))
+            self.assertEqual(m, v)
+            k, m = self.q.popMax()
+            v = values.pop()
+            self.assertEqual(k, str(v))
+            self.assertEqual(m, v)
         
 if __name__ == '__main__':
     unittest.main()