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

Casey Duncan casey at zope.com
Mon Aug 18 01:36:05 EDT 2003


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

Modified Files:
	test_graph.py 
Log Message:
Move shortestPath and allPaths methods from graph.edges to graph
Change interface to reflect that paths are lists of nodes, not edges
Implement graph.allPaths method and test
Add identity tests for DirectedIdGraph test suite


=== Packages/pypes/pypes/tests/test_graph.py 1.5 => 1.6 ===
--- Packages/pypes/pypes/tests/test_graph.py:1.5	Sun Aug 10 23:17:38 2003
+++ Packages/pypes/pypes/tests/test_graph.py	Mon Aug 18 00:36:00 2003
@@ -20,7 +20,7 @@
 from random import randint
 from zope.interface.verify import verifyObject
 from Persistence import Persistent
-from common import PypesTestCase, PypesPersistentTest
+from common import PypesTestCase, PypesPersistentTest, TestClass, sort
 from pypes import graph
 
 
@@ -380,7 +380,7 @@
         
     def testShortestPathMatrixWithoutValues(self):
         nodes = self._makeMatrix()
-        result = self.graph.edges.shortestPath(nodes[0, 0], nodes[4, 4])
+        result = self.graph.shortestPath(nodes[0, 0], nodes[4, 4])
         self.failIf(result is None)
         i, x1, y1 = 0, 0, 0
         path = [nodes[x1, y1]]
@@ -397,7 +397,7 @@
         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.shortestPath(ob1, ob3), None) 
         
     def testShortestPathWithValues(self):
         objs = [self._newObj() for i in range(5)]
@@ -408,12 +408,12 @@
         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),
+            self.graph.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)
+        result = self.graph.shortestPath(nodes[0, 0], nodes[4, 4], 1)
         self.failIf(result is None)
         i, x1, y1 = 0, 0, 0
         path = [nodes[x1, y1]]
@@ -430,7 +430,127 @@
         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)
+        self.assertEqual(self.graph.shortestPath(ob1, ob3, 1), None)
+    
+    def testShortestPathWithBogusSource(self):
+        from pypes.exceptions import GraphLookupError
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob3, ob2, 3)
+        self.assertRaises(
+            GraphLookupError, self.graph.shortestPath, ob1, ob2)
+    
+    def testShortestPathWithBogusTarget(self):
+        from pypes.exceptions import GraphLookupError
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob3, ob2, 3)
+        self.assertRaises(
+            GraphLookupError, self.graph.shortestPath, ob2, ob1)
+        
+    def testAllPathsSimple(self):
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2)
+        self.graph.edges.add(ob1, ob3)
+        self.graph.edges.add(ob2, ob3)
+        paths = list(self.graph.allPaths())
+        expected = [[ob1, ob2], [ob1, ob2, ob3], [ob1, ob3], [ob2, ob3]]
+        self.assertEqual(sort(paths), sort(expected))
+    
+    def testAllPathsSimpleWithSource(self):
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2)
+        self.graph.edges.add(ob1, ob3)
+        self.graph.edges.add(ob2, ob3)
+        paths = list(self.graph.allPaths(source=ob1))
+        expected = [[ob1, ob2], [ob1, ob2, ob3], [ob1, ob3]]
+        self.assertEqual(sort(paths), sort(expected))
+        paths = list(self.graph.allPaths(source=ob2))
+        self.assertEqual(paths, [[ob2, ob3]])
+        paths = list(self.graph.allPaths(source=ob3))
+        self.assertEqual(paths, [])
+    
+    def testAllPathsSimpleWithTarget(self):
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2)
+        self.graph.edges.add(ob1, ob3)
+        self.graph.edges.add(ob2, ob3)
+        paths = list(self.graph.allPaths(target=ob1))
+        self.assertEqual(paths, [])
+        paths = list(self.graph.allPaths(target=ob2))
+        self.assertEqual(paths, [[ob1, ob2]])
+        paths = list(self.graph.allPaths(target=ob3))
+        expected = [[ob1, ob2, ob3], [ob1, ob3], [ob2, ob3]]
+        self.assertEqual(sort(paths), sort(expected))
+    
+    def testAllPathsSimpleWithSourceAndTarget(self):
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2)
+        self.graph.edges.add(ob1, ob3)
+        self.graph.edges.add(ob2, ob3)
+        paths = list(self.graph.allPaths(ob1, ob2))
+        self.assertEqual(paths, [[ob1, ob2]])
+        paths = list(self.graph.allPaths(ob1, ob3))
+        expected = [[ob1, ob2, ob3], [ob1, ob3], [ob2, ob3]]
+        paths = list(self.graph.allPaths(ob2, ob3))
+        self.assertEqual(paths, [[ob2, ob3]])  
+        paths = list(self.graph.allPaths(ob2, ob1))
+        self.assertEqual(paths, [])  
+        
+    def testAllPathsWithCycle(self):
+        from pypes.graph import cycle
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob1, ob2)
+        self.graph.edges.add(ob2, ob1)
+        self.graph.edges.add(ob3, ob1)
+        paths = list(self.graph.allPaths())
+        expected = [[ob1, ob2], cycle([ob1, ob2, ob1]), 
+                    [ob2, ob1], cycle([ob2, ob1, ob2]),
+                    [ob3, ob1], [ob3, ob1, ob2], cycle([ob3, ob1, ob2, ob1])]
+        paths.sort()
+        expected.sort()
+        self.assertEqual(paths, expected)
+        for i in range(len(paths)):
+            self.failUnless(type(paths[i]) is type(expected[i]))
+
+    def testAllPathsWithBogusSource(self):
+        from pypes.exceptions import GraphLookupError
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob3, ob2)
+        self.assertRaises(GraphLookupError, self.graph.allPaths(ob1, ob2).next)
+    
+    def testAllPathsWithBogusTarget(self):
+        from pypes.exceptions import GraphLookupError
+        ob1, ob2, ob3 = self._newObj(), self._newObj(), self._newObj()
+        self.graph.edges.add(ob3, ob2)
+        self.assertRaises(GraphLookupError, self.graph.allPaths(ob3, ob1).next)
+
+    def testAllPathsFullyConnected(self):
+        objs = [self._newObj() for i in range(3)]
+        for s in objs:
+            for t in objs:
+                self.graph.edges.add(s, t)
+        allpaths = list(self.graph.allPaths())
+        count = 0
+        for i in objs:
+            for j in objs:
+                self.failUnless([i, j] in allpaths)
+                count += 1
+                if j is not i:
+                    for k in objs:
+                        self.failUnless([i, j, k] in allpaths)
+                        count += 1
+                        if k not in (j, i):
+                            for m in objs:
+                                self.failUnless([i, j, k, m] in allpaths)
+                                count += 1
+        self.assertEqual(count, len(allpaths))
+    
+    def testAllPathsUnconnected(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)
+        self.assertEqual(list(self.graph.allPaths()), [])
+        
         
 class TestDirectedIdGraph(PypesTestCase, TestDirectedGraph):
     
@@ -438,7 +558,100 @@
         from pypes.graph import DirectedIdGraph
         self.graph = DirectedIdGraph()
         PypesTestCase.setUp(self)
-
+        
+    def testAddNodeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob = TestClass()
+        self.assertRaises(IdentityError, self.graph.nodes.add, ob)
+        
+    def testRemoveNodeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob = TestClass()
+        self.assertRaises(IdentityError, self.graph.nodes.remove, ob)
+        
+    def testContainsNodeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob = TestClass()
+        try:
+            ob in self.graph.nodes
+        except IdentityError:
+            pass
+        except:
+            raise
+        else:
+            self.fail()
+    
+    def testDegreeNodeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob = TestClass()
+        self.assertRaises(IdentityError, self.graph.nodes.degree, ob)
+    
+    def testSourcesNodeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob = TestClass()
+        self.assertRaises(IdentityError, self.graph.nodes.sources, ob)
+    
+    def testTargetsNodeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob = TestClass()
+        self.assertRaises(IdentityError, self.graph.nodes.targets, ob)
+        
+    def testAddEdgeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        self.assertRaises(IdentityError, self.graph.edges.add, ob1, ob2)
+        self.assertRaises(IdentityError, self.graph.edges.add, ob2, ob1)
+        
+    def testRemoveEdgeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        self.assertRaises(IdentityError, self.graph.edges.remove, ob1, ob2)
+        self.assertRaises(IdentityError, self.graph.edges.remove, ob2, ob1)
+        
+    def testGetEdgeValueUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        self.assertRaises(IdentityError, self.graph.edges.get, ob1, ob2)
+        self.assertRaises(IdentityError, self.graph.edges.get, ob2, ob1)
+        
+    def testSetEdgeValueUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        self.assertRaises(IdentityError, self.graph.edges.set, ob1, ob2, 0)
+        self.assertRaises(IdentityError, self.graph.edges.set, ob2, ob1, 0)
+        
+    def testContainsEdgeUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        try:
+            (ob1, ob2) in self.graph.edges
+        except IdentityError:
+            pass
+        except:
+            raise
+        else:
+            self.fail()
+        try:
+            (ob2, ob1) in self.graph.edges
+        except IdentityError:
+            pass
+        except:
+            raise
+        else:
+            self.fail()
+            
+    def testShortestPathUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        self.assertRaises(IdentityError, self.graph.shortestPath, ob1, ob2)
+        self.assertRaises(IdentityError, self.graph.shortestPath, ob2, ob1)
+            
+    def testAllPathsUnregistered(self):
+        from pypes.exceptions import IdentityError
+        ob1, ob2 = TestClass(), self._newObj()
+        self.assertRaises(IdentityError, self.graph.allPaths(ob1, ob2).next)
+        
+        
 class TestPQueue(unittest.TestCase):
     
     def setUp(self):




More information about the Zope-CVS mailing list