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

[Casey Duncan]

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

Modified Files:
	test_graph.py 
Log Message:
Add shortestPath implementation without values
Begin roughing out implementation the uses values


=== Packages/pypes/pypes/tests/test_graph.py 1.1.1.1 => 1.2 ===
--- Packages/pypes/pypes/tests/test_graph.py:1.1.1.1	Mon Aug  4 00:46:06 2003
+++ Packages/pypes/pypes/tests/test_graph.py	Fri Aug  8 00:57:54 2003
@@ -308,13 +308,65 @@
         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):
+        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)
+                    else:
+                        self.graph.edges.add(n, nodes[x-1, y])
+                if y:
+                    if (x + y) % 2:
+                        self.graph.edges.add(n, nodes[x, y-1])
+                    else:
+                        self.graph.edges.add(nodes[x, y-1], n)
+                elif not x:
+                    self.graph.nodes.add(n)
+        result = self.graph.edges.shortestPath(nodes[0, 0], nodes[4, 4])
+        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 testShortestPathUnreachable(self):
+        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)        
+        
 class TestDirectedIdGraph(PypesTestCase, TestDirectedGraph):
     
     def setUp(self):
         from pypes.graph import DirectedIdGraph
         self.graph = DirectedIdGraph()
         PypesTestCase.setUp(self)
+
+class TestPQueue(unittest.TestCase):
+    
+    def setUp(self):
+        from pypes.graph import PQueue
+        self.q = PQueue()
+    
+    def testInsertAndPop(self):
+        from random import randint
+        values = [randint(0, 10000) for i in range(10)]
+        for i in values:
+            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()))
         
 if __name__ == '__main__':
     unittest.main()