1from apgl.graph.DictGraph import DictGraph
2from apgl.util.Util import Util
3import unittest
4import numpy
5import logging
6import numpy.testing as nptst
7
8class DictGraphTest(unittest.TestCase):
9    def setUp(self):
10        self.graph = DictGraph()
11        self.graph.addEdge(0, 1, 1)
12        self.graph.addEdge(1, 3, 1)
13        self.graph.addEdge(0, 2, 2)
14        self.graph.addEdge(2, 3, 5)
15        self.graph.addEdge(0, 4, 1)
16        self.graph.addEdge(3, 4, 1)
17        self.graph.setVertex(5, None)
18
19        self.graph2 = DictGraph(False)
20        self.graph2.addEdge(0, 1, 1)
21        self.graph2.addEdge(1, 3, 1)
22        self.graph2.addEdge(0, 2, 2)
23        self.graph2.addEdge(2, 3, 5)
24        self.graph2.addEdge(0, 4, 1)
25        self.graph2.addEdge(3, 4, 1)
26        self.graph2.setVertex(5, 1)
27
28    def testInit(self):
29        dictGraph = DictGraph()
30
31    def testAddEdge(self):
32        dictGraph = DictGraph()
33        dictGraph.addEdge("A", "B", [1,2,3])
34        dictGraph.addEdge("A", "C", "HelloThere")
35        dictGraph.addEdge(12, 8, [1,2,3, 12])
36
37        self.assertEquals(dictGraph.getEdge("A", "B"), [1,2,3])
38        self.assertEquals(dictGraph.getEdge("B", "A"), [1,2,3])
39        self.assertEquals(dictGraph.getEdge("A", "C"), "HelloThere")
40        self.assertEquals(dictGraph.getEdge("C", "A"), "HelloThere")
41        self.assertEquals(dictGraph.getEdge(12, 8), [1,2,3, 12])
42        self.assertEquals(dictGraph.getEdge(8, 12), [1,2,3, 12])
43
44        dictGraph.addEdge(2, 8)
45
46        dictGraph = DictGraph(False)
47        dictGraph.addEdge("A", "B", [1,2,3])
48        dictGraph.addEdge("A", "C", "HelloThere")
49        dictGraph.addEdge(12, 8, [1,2,3, 12])
50
51        self.assertEquals(dictGraph.getEdge("A", "B"), [1,2,3])
52        self.assertEquals(dictGraph.getEdge("B", "A"), None)
53        self.assertEquals(dictGraph.getEdge("A", "C"), "HelloThere")
54        self.assertEquals(dictGraph.getEdge("C", "A"), None)
55        self.assertEquals(dictGraph.getEdge(12, 8), [1,2,3, 12])
56        self.assertEquals(dictGraph.getEdge(8, 12), None)
57
58        dictGraph.addEdge(2, 8)
59
60        #Test directed graphs
61
62    def testRemoveEdge(self):
63        dictGraph = DictGraph()
64        dictGraph.addEdge(1, 2, 12)
65        dictGraph.addEdge(1, 3, 18)
66        dictGraph.addEdge(3, 4, 1)
67
68        self.assertEquals(dictGraph.getEdge(1, 2), 12)
69        self.assertEquals(dictGraph.getEdge(1, 3), 18)
70        self.assertEquals(dictGraph.getEdge(3, 4), 1)
71
72        dictGraph.removeEdge(1, 3)
73
74        self.assertEquals(dictGraph.getEdge(1, 3), None)
75        self.assertEquals(dictGraph.getEdge(1, 2), 12)
76        self.assertEquals(dictGraph.getEdge(3, 4), 1)
77
78        #Some tests on directed graphs
79        dictGraph = DictGraph(False)
80        dictGraph.addEdge(1, 2, 12)
81        dictGraph.addEdge(2, 1, 12)
82
83        dictGraph.removeEdge(1, 2)
84        self.assertEquals(dictGraph.getEdge(1, 2), None)
85        self.assertEquals(dictGraph.getEdge(2, 1), 12)
86
87    def testIsUndirected(self):
88        dictGraph = DictGraph(True)
89        self.assertEquals(dictGraph.isUndirected(), True)
90
91        dictGraph = DictGraph(False)
92        self.assertEquals(dictGraph.isUndirected(), False)
93
94    def testGetNumEdges(self):
95        dictGraph = DictGraph(True)
96        self.assertEquals(dictGraph.getNumEdges(), 0)
97
98        dictGraph.addEdge(1, 2, 12)
99        dictGraph.addEdge(1, 3, 18)
100        dictGraph.addEdge(3, 4, 1)
101        self.assertEquals(dictGraph.getNumEdges(), 3)
102
103        dictGraph.addEdge(3, 4, 1)
104        self.assertEquals(dictGraph.getNumEdges(), 3)
105
106        dictGraph.addEdge(3, 5, 1)
107        self.assertEquals(dictGraph.getNumEdges(), 4)
108
109        dictGraph.addEdge(3, 3, 1)
110        self.assertEquals(dictGraph.getNumEdges(), 5)
111
112        #Identical tests with directed graphs
113        dictGraph = DictGraph(False)
114        self.assertEquals(dictGraph.getNumEdges(), 0)
115
116        dictGraph.addEdge(1, 2, 12)
117        dictGraph.addEdge(1, 3, 18)
118        dictGraph.addEdge(3, 4, 1)
119        self.assertEquals(dictGraph.getNumEdges(), 3)
120
121        dictGraph.addEdge(3, 4, 1)
122        self.assertEquals(dictGraph.getNumEdges(), 3)
123
124        dictGraph.addEdge(3, 5, 1)
125        self.assertEquals(dictGraph.getNumEdges(), 4)
126
127        dictGraph.addEdge(3, 3, 1)
128        self.assertEquals(dictGraph.getNumEdges(), 5)
129
130    def testGetEdge(self):
131        dictGraph = DictGraph(True)
132        dictGraph.addEdge(1, 2, 12)
133
134        self.assertEquals(dictGraph.getEdge(1, 2), 12)
135        self.assertEquals(dictGraph.getEdge(2, 1), 12)
136        self.assertEquals(dictGraph.getEdge(2, 2), None)
137        self.assertRaises(ValueError, dictGraph.getEdge, 5, 8)
138
139        dictGraph = DictGraph(False)
140        dictGraph.addEdge(1, 2, 12)
141
142        self.assertEquals(dictGraph.getEdge(1, 2), 12)
143        self.assertEquals(dictGraph.getEdge(2, 1), None)
144
145    def testGetNeighbours(self):
146        dictGraph = DictGraph(True)
147        dictGraph.addEdge(1, 2, 12)
148        dictGraph.addEdge(1, 3, 18)
149        dictGraph.addEdge(1, 4, 1)
150        dictGraph.addEdge(3, 4, 1)
151        dictGraph.addEdge(2, 2, 1)
152        dictGraph.setVertex(5, 12)
153
154        self.assertEquals(dictGraph.neighbours(1), [2, 3, 4])
155        self.assertEquals(dictGraph.neighbours(3), [1, 4])
156        self.assertEquals(dictGraph.neighbours(2), [1, 2])
157        self.assertEquals(dictGraph.neighbours(5), [])
158
159        #Directed graphs
160        dictGraph = DictGraph(False)
161        dictGraph.addEdge(1, 2, 12)
162        dictGraph.addEdge(1, 3, 18)
163        dictGraph.addEdge(1, 4, 1)
164        dictGraph.addEdge(3, 4, 1)
165        dictGraph.addEdge(2, 2, 1)
166        dictGraph.setVertex(5, 12)
167
168        self.assertEquals(dictGraph.neighbours(1), [2,3,4])
169        self.assertEquals(dictGraph.neighbours(3), [4])
170        self.assertEquals(dictGraph.neighbours(2), [2])
171        self.assertEquals(dictGraph.neighbours(5), [])
172
173    def testGetVertex(self):
174        dictGraph = DictGraph(True)
175        dictGraph.addEdge(1, 2, 12)
176        dictGraph.addEdge(1, 3, 18)
177        dictGraph.setVertex(5, 12)
178
179        self.assertEquals(dictGraph.getVertex(1), None)
180        self.assertEquals(dictGraph.getVertex(2), None)
181        self.assertEquals(dictGraph.getVertex(3), None)
182        self.assertEquals(dictGraph.getVertex(5), 12)
183
184        self.assertRaises(ValueError, dictGraph.getVertex, 4)
185
186        #Directed graphs
187        dictGraph = DictGraph(False)
188        dictGraph.addEdge(1, 2, 12)
189        dictGraph.addEdge(1, 3, 18)
190        dictGraph.setVertex(5, 12)
191
192        self.assertEquals(dictGraph.getVertex(1), None)
193        self.assertEquals(dictGraph.getVertex(2), None)
194        self.assertEquals(dictGraph.getVertex(3), None)
195        self.assertEquals(dictGraph.getVertex(5), 12)
196
197        self.assertRaises(ValueError, dictGraph.getVertex, 4)
198
199    def testAddVertex(self):
200        dictGraph = DictGraph(True)
201        dictGraph.addEdge(1, 2, 12)
202        dictGraph.addEdge(1, 3, 18)
203        dictGraph.setVertex(5, 12)
204
205        self.assertEquals(dictGraph.getVertex(5), 12)
206
207        dictGraph.setVertex(5, 22)
208        self.assertEquals(dictGraph.getVertex(5), 22)
209
210        dictGraph.addEdge(5, 11, 18)
211        self.assertEquals(dictGraph.getVertex(5), 22)
212
213    def testGetAllVertexIds(self):
214        dictGraph = DictGraph(True)
215        dictGraph.addEdge(1, 2, 12)
216        dictGraph.addEdge(1, 3, 18)
217        dictGraph.setVertex(5, 12)
218
219        self.assertEquals(dictGraph.getAllVertexIds(), [1, 2, 3, 5])
220
221    def testGetAllEdges(self):
222        dictGraph = DictGraph(True)
223        dictGraph.setVertex(5, 12)
224        dictGraph.addEdge(1, 2, 12)
225        dictGraph.addEdge(1, 3, 18)
226
227        edges = dictGraph.getAllEdges()
228
229        self.assertEquals(len(edges), 2)
230        self.assertTrue((1,2) in edges)
231        self.assertTrue((1,3) in edges)
232
233        dictGraph = DictGraph(False)
234        dictGraph.setVertex(5, 12)
235        dictGraph.addEdge(1, 2, 12)
236        dictGraph.addEdge(2, 1, 12)
237        dictGraph.addEdge(1, 3, 18)
238
239        edges = dictGraph.getAllEdges()
240
241        self.assertEquals(len(edges), 3)
242        self.assertTrue((1,2) in edges)
243        self.assertTrue((2,1) in edges)
244        self.assertTrue((1,3) in edges)
245
246    def testDensity(self):
247        numVertices = 10
248        graph = DictGraph(True)
249        for i in range(numVertices):
250            graph.setVertex(i, 0)
251
252        graph.addEdge(0, 1)
253        self.assertEquals(graph.density(), float(1)/45)
254
255        graph.addEdge(0, 2)
256        self.assertEquals(graph.density(), float(2)/45)
257
258        graph = DictGraph(False)
259        for i in range(numVertices):
260            graph.setVertex(i, 0)
261        graph.addEdge(0, 1)
262        self.assertEquals(graph.density(), float(1)/90)
263
264        graph.addEdge(0, 2)
265        self.assertEquals(graph.density(), float(2)/90)
266
267        #Test a graph with 1 vertex
268        graph = DictGraph(True)
269        graph.setVertex(0, 12)
270
271        self.assertEquals(graph.density(), 0)
272
273        graph.addEdge(0, 0)
274        self.assertEquals(graph.density(), 1)
275
276    def testSetVertices(self):
277        graph = DictGraph()
278
279        vertexIndices = [1, 2, 3]
280        vertices = ["a", "b", "c"]
281
282        graph.setVertices(vertexIndices, vertices)
283
284        vertexIndices2 = graph.getAllVertexIds()
285        vertices2 = graph.getVertices(vertexIndices2)
286
287        self.assertEquals(vertexIndices, vertexIndices2)
288        self.assertEquals(vertices, vertices2)
289
290    def testGetWeightMatrix(self):
291        graph = DictGraph()
292        graph.addEdge("a", "b")
293        graph.addEdge("a", "c")
294        graph.addEdge("a", "d")
295        graph.addEdge("d", "e")
296
297        W = graph.getWeightMatrix()
298        keys = graph.getAllVertexIds()
299
300        for i in range(len(keys)):
301            for j in range(len(keys)):
302                if W[i, j] == 1:
303                    self.assertEquals(graph.getEdge(keys[i], keys[j]), 1)
304                else:
305                    self.assertEquals(graph.getEdge(keys[i], keys[j]), None)
306
307        #Try a directed graph
308        graph = DictGraph(False)
309        graph.addEdge("a", "b")
310        graph.addEdge("a", "c")
311        graph.addEdge("a", "d")
312        graph.addEdge("d", "e")
313
314        W = graph.getWeightMatrix()
315
316        for i in range(len(keys)):
317            for j in range(len(keys)):
318                if W[i, j] == 1:
319                    self.assertEquals(graph.getEdge(keys[i], keys[j]), 1)
320                else:
321                    self.assertEquals(graph.getEdge(keys[i], keys[j]), None)
322
323    def testGetSparseWeightMatrix(self):
324        graph = DictGraph()
325        graph.addEdge("a", "b")
326        graph.addEdge("a", "c")
327        graph.addEdge("a", "d")
328        graph.addEdge("d", "e")
329
330        W = graph.getSparseWeightMatrix()
331        keys = graph.getAllVertexIds()
332
333        for i in range(len(keys)):
334            for j in range(len(keys)):
335                if W[i, j] == 1:
336                    self.assertEquals(graph.getEdge(keys[i], keys[j]), 1)
337                else:
338                    self.assertEquals(graph.getEdge(keys[i], keys[j]), None)
339
340        #Try a directed graph
341        graph = DictGraph(False)
342        graph.addEdge("a", "b")
343        graph.addEdge("a", "c")
344        graph.addEdge("a", "d")
345        graph.addEdge("d", "e")
346
347        W = graph.getSparseWeightMatrix()
348
349        for i in range(len(keys)):
350            for j in range(len(keys)):
351                if W[i, j] == 1:
352                    self.assertEquals(graph.getEdge(keys[i], keys[j]), 1)
353                else:
354                    self.assertEquals(graph.getEdge(keys[i], keys[j]), None)
355
356    def testGetAllEdgeIndices(self):
357        graph = DictGraph()
358        graph.addEdge("a", "b")
359        graph.addEdge("a", "c")
360        graph.addEdge("a", "d")
361        graph.addEdge("d", "e")
362
363        edgeIndices = graph.getAllEdgeIndices()
364        keys = graph.getAllVertexIds()
365
366        self.assertEquals(edgeIndices.shape[0], graph.getNumEdges())
367        for i in range(edgeIndices.shape[0]):
368            self.assertTrue(graph.getEdge(keys[int(edgeIndices[i, 0])], keys[edgeIndices[i, 1]]) == 1)
369
370        graph = DictGraph(False)
371        graph.addEdge("a", "b")
372        graph.addEdge("b", "a")
373        graph.addEdge("a", "c")
374        graph.addEdge("a", "d")
375        graph.addEdge("d", "e")
376
377        edgeIndices = graph.getAllEdgeIndices()
378        keys = graph.getAllVertexIds()
379        self.assertEquals(edgeIndices.shape[0], graph.getNumEdges())
380        for i in range(edgeIndices.shape[0]):
381            self.assertTrue(graph.getEdge(keys[int(edgeIndices[i, 0])], keys[edgeIndices[i, 1]]) == 1)
382
383    def testGetItem(self):
384        graph = DictGraph()
385        graph.addEdge(1, 1, 0.1)
386        graph.addEdge(1, 3, 0.5)
387        graph.addEdge(2, 4, 1)
388        graph.addEdge(2, 3, 2)
389        graph.setVertex(0, "abc")
390
391        self.assertEquals(graph[1,1], 0.1)
392        self.assertEquals(graph[1,3], 0.5)
393
394
395    def testSetItem(self):
396        graph = DictGraph()
397        graph.addEdge(1, 1, 0.1)
398        graph.addEdge(1, 3, 0.5)
399
400        self.assertEquals(graph[1,3], 0.5)
401        graph[1, 3] = 2
402        self.assertEquals(graph[1,3], 2)
403
404    def testAddEdges(self):
405        graph = DictGraph()
406
407        edgeList = [(1, 2), (2, 1), (5, 2), (8, 8)]
408
409        graph.addEdges(edgeList)
410        self.assertEquals(graph.getNumEdges(), 3)
411        self.assertEquals(graph.getEdge(1, 2), 1)
412        self.assertEquals(graph.getEdge(5, 2), 1)
413        self.assertEquals(graph.getEdge(2, 1), 1)
414        self.assertEquals(graph.getEdge(8, 8), 1)
415
416        edgeValues = [1, 2, 3, 4]
417        graph.addEdges(edgeList, edgeValues)
418        self.assertEquals(graph.getEdge(1, 2), 2)
419        self.assertEquals(graph.getEdge(5, 2), 3)
420        self.assertEquals(graph.getEdge(2, 1), 2)
421        self.assertEquals(graph.getEdge(8, 8), 4)
422
423        #Now test directed graphs
424        graph = DictGraph(False)
425        graph.addEdges(edgeList)
426        self.assertEquals(graph.getNumEdges(), 4)
427        self.assertEquals(graph.getEdge(1, 2), 1)
428        self.assertEquals(graph.getEdge(5, 2), 1)
429        self.assertEquals(graph.getEdge(2, 1), 1)
430        self.assertEquals(graph.getEdge(8, 8), 1)
431
432        edgeValues = [1, 2, 3, 4]
433        graph.addEdges(edgeList, edgeValues)
434        self.assertEquals(graph.getEdge(1, 2), 1)
435        self.assertEquals(graph.getEdge(5, 2), 3)
436        self.assertEquals(graph.getEdge(2, 1), 2)
437        self.assertEquals(graph.getEdge(8, 8), 4)
438
439
440    def testSubgraph(self):
441        graph = DictGraph()
442
443        graph.addEdge(0, 1)
444        graph.addEdge(0, 2)
445        graph.addEdge(0, 3)
446        graph.addEdge(1, 2)
447        graph.addEdge(2, 3)
448        graph.setVertex(0, "abc")
449        graph.setVertex(3, "cde")
450
451        self.assertEquals(graph.getNumEdges(), 5)
452
453        subgraph = graph.subgraph([0, 1, 2])
454        self.assertEquals(subgraph.getNumVertices(), 3)
455        self.assertEquals(subgraph.getNumEdges(), 3)
456        self.assertEquals(subgraph.isUndirected(), True)
457        self.assertEquals(subgraph.getEdge(0, 1), 1)
458        self.assertEquals(subgraph.getEdge(0, 2), 1)
459        self.assertEquals(subgraph.getEdge(1, 2), 1)
460        self.assertEquals(subgraph.getVertex(0), "abc")
461
462        #Check the original graph is fine
463        self.assertEquals(graph.getNumVertices(), 4)
464        self.assertEquals(graph.getNumEdges(), 5)
465        self.assertEquals(graph.getVertex(0), "abc")
466        self.assertEquals(graph.getVertex(3), "cde")
467
468        #Now a quick test for directed graphs
469        graph = DictGraph(False)
470
471        graph.addEdge(0, 1)
472        graph.addEdge(0, 2)
473        graph.addEdge(0, 3)
474        graph.addEdge(1, 2)
475        graph.addEdge(2, 3)
476
477        subgraph = graph.subgraph([0, 1, 2])
478        self.assertEquals(subgraph.getNumEdges(), 3)
479        self.assertEquals(subgraph.isUndirected(), False)
480        self.assertEquals(subgraph.getEdge(0, 1), 1)
481        self.assertEquals(subgraph.getEdge(0, 2), 1)
482        self.assertEquals(subgraph.getEdge(1, 2), 1)
483
484    def testNeighbourOf(self):
485        graph = DictGraph(True)
486
487        graph.addEdge(0, 1)
488        graph.addEdge(0, 2)
489        graph.addEdge(0, 3)
490        graph.addEdge(1, 2)
491        graph.addEdge(2, 3)
492
493        for i in range(4):
494            self.assertEquals(graph.neighbours(i), graph.neighbourOf(i))
495
496        #Now test directed graph
497        graph = DictGraph(False)
498
499        graph.addEdge(0, 1)
500        graph.addEdge(0, 2)
501        graph.addEdge(0, 3)
502        graph.addEdge(1, 2)
503        graph.addEdge(2, 3)
504
505        self.assertEquals(graph.neighbourOf(0), [])
506        self.assertEquals(graph.neighbourOf(1), [0])
507        self.assertEquals(graph.neighbourOf(2), [0,1])
508        self.assertEquals(graph.neighbourOf(3), [0, 2])
509
510
511    def testOutDegreeSequence(self):
512        graph = DictGraph(True)
513
514        graph.addEdge(0, 1)
515        graph.addEdge(0, 2)
516        graph.addEdge(0, 3)
517        graph.addEdge(1, 2)
518        graph.addEdge(2, 3)
519
520        degSeq, vertices = graph.outDegreeSequence()
521
522        self.assertTrue((degSeq == numpy.array([ 3,  2,  3,  2.])).all())
523        self.assertTrue(vertices == [0, 1, 2, 3])
524
525        #Test results on a directed graph
526        graph = DictGraph(False)
527        graph.addEdge(0, 1)
528        graph.addEdge(0, 2)
529        graph.addEdge(0, 3)
530        graph.addEdge(1, 2)
531        graph.addEdge(2, 3)
532
533        degSeq, vertices = graph.outDegreeSequence()
534        self.assertTrue((degSeq == numpy.array([ 3,  1,  1,  0])).all())
535
536    def testInDegreeSequence(self):
537        graph = DictGraph(True)
538
539        graph.addEdge(0, 1)
540        graph.addEdge(0, 2)
541        graph.addEdge(0, 3)
542        graph.addEdge(1, 2)
543        graph.addEdge(2, 3)
544
545        degSeq, vertices = graph.inDegreeSequence()
546
547        self.assertTrue((degSeq == numpy.array([ 3,  2,  3,  2.])).all())
548        self.assertTrue(vertices == [0, 1, 2, 3])
549
550        #Test results on a directed graph
551        graph = DictGraph(False)
552        graph.addEdge(0, 1)
553        graph.addEdge(0, 2)
554        graph.addEdge(0, 3)
555        graph.addEdge(1, 2)
556        graph.addEdge(2, 3)
557
558        degSeq, vertices = graph.inDegreeSequence()
559        self.assertTrue((degSeq == numpy.array([ 0,  1,  2,  2])).all())
560
561    def testVertexExists(self):
562        graph = DictGraph(False)
563        graph.addEdge(0, 1)
564        graph.addEdge(0, 2)
565        graph.addEdge(0, 3)
566        graph.addEdge(1, 2)
567        graph.addEdge(2, 3)
568
569        self.assertTrue(graph.vertexExists(0))
570        self.assertTrue(graph.vertexExists(1))
571        self.assertTrue(graph.vertexExists(2))
572        self.assertTrue(graph.vertexExists(3))
573        self.assertFalse(graph.vertexExists(4))
574
575    def testRemoveVertex(self):
576        graph = DictGraph()
577        graph.addEdge(0, 1)
578        graph.addEdge(0, 2)
579        graph.addEdge(0, 3)
580        graph.addEdge(1, 2)
581        graph.addEdge(2, 3)
582        graph.addEdge(3, 4)
583
584        graph.removeVertex(4)
585        self.assertFalse(graph.vertexExists(4))
586        self.assertFalse(graph.edgeExists(3, 4))
587
588        graph.removeVertex(3)
589        self.assertFalse(graph.vertexExists(3))
590        self.assertFalse(graph.edgeExists(2, 3))
591        self.assertFalse(graph.edgeExists(0, 3))
592
593        graph.removeVertex(2)
594        self.assertFalse(graph.vertexExists(2))
595        self.assertFalse(graph.edgeExists(1, 2))
596        self.assertFalse(graph.edgeExists(0, 2))
597
598        self.assertTrue(graph.getAllVertexIds() == [0, 1])
599        self.assertTrue(graph.getAllEdges() == [(0, 1)])
600
601        #Try directed graph
602        graph = DictGraph(False)
603        graph.addEdge(0, 1)
604        graph.addEdge(1, 0)
605        graph.addEdge(0, 3)
606        graph.addEdge(1, 2)
607        graph.addEdge(2, 3)
608        graph.addEdge(3, 4)
609
610        graph.removeVertex(0)
611
612        self.assertFalse(graph.vertexExists(0))
613        self.assertFalse(graph.edgeExists(0, 1))
614        self.assertFalse(graph.edgeExists(0, 3))
615        self.assertFalse(graph.edgeExists(1, 0))
616
617        graph.removeVertex(2)
618        self.assertFalse(graph.vertexExists(2))
619        self.assertFalse(graph.edgeExists(1, 2))
620        self.assertFalse(graph.edgeExists(2, 3))
621
622        self.assertTrue(graph.getAllVertexIds() == [1, 3, 4])
623        self.assertTrue(graph.getAllEdges() == [(3, 4)])
624
625    def testToSparseGraph(self):
626        graph = DictGraph()
627        graph.addEdge(0, 1)
628        graph.addEdge(0, 2)
629        graph.addEdge(0, 3)
630        graph.addEdge(1, 2)
631        graph.addEdge(2, 3)
632        graph.addEdge(3, 4)
633
634        graph2 = graph.toSparseGraph()
635
636        self.assertEquals(graph2[0, 1], 1)
637        self.assertEquals(graph2[0, 2], 1)
638        self.assertEquals(graph2[0, 3], 1)
639        self.assertEquals(graph2[2, 1], 1)
640        self.assertEquals(graph2[2, 3], 1)
641        self.assertEquals(graph2[3, 4], 1)
642
643    def testDepthFirstSearch(self):
644        graph = DictGraph()
645        graph.addEdge(0, 1)
646        graph.addEdge(1, 2)
647        graph.addEdge(1, 3)
648        graph.addEdge(2, 6)
649        graph.addEdge(4, 5)
650
651        self.assertEquals(graph.depthFirstSearch(0), [0,1,2,6,3])
652        self.assertEquals(graph.depthFirstSearch(1), [1,0,2,6,3])
653        self.assertEquals(graph.depthFirstSearch(6), [6,2,1,0,3])
654        self.assertEquals(graph.depthFirstSearch(4), [4, 5])
655        self.assertEquals(graph.depthFirstSearch(5), [5, 4])
656
657    def testBreadthFirstSearch(self):
658        graph = DictGraph()
659        graph.addEdge(0, 1)
660        graph.addEdge(0, 7)
661        graph.addEdge(7, 8)
662        graph.addEdge(7, 9)
663        graph.addEdge(1, 2)
664        graph.addEdge(1, 3)
665        graph.addEdge(2, 6)
666        graph.addEdge(4, 5)
667
668        self.assertEquals(graph.breadthFirstSearch(0), [0,1, 7,2,3,8,9,6])
669        self.assertEquals(graph.breadthFirstSearch(1), [1,0,2,3,7,6,8,9])
670        self.assertEquals(graph.breadthFirstSearch(6), [6, 2,1,0,3,7,8,9])
671        self.assertEquals(graph.breadthFirstSearch(4), [4, 5])
672        self.assertEquals(graph.breadthFirstSearch(5), [5, 4])
673        self.assertEquals(graph.breadthFirstSearch(7), [7, 0, 8, 9, 1, 2, 3, 6])
674
675    def testDegreeSequence(self):
676        graph = DictGraph()
677        graph.setVertex("a", 10)
678        graph["b", "c"] = 1
679        graph["b", "d"] = 1
680        graph["d", "e"] = 1
681        graph["e", "e"] = 1
682
683        degreeDict = {}
684        degreeDict2 = {"a": 0, "b": 2, "c": 1, "d": 2, "e": 3}
685
686        for i, id in enumerate(graph.getAllVertexIds()):
687            degreeDict[id] = graph.degreeSequence()[i]
688
689        self.assertEquals(degreeDict, degreeDict2)
690
691    def testGetNumDirEdges(self):
692        graph = DictGraph()
693        graph.addEdge(0, 1, 0.1)
694        graph.addEdge(1, 2, 0.1)
695
696        self.assertTrue(graph.getNumDirEdges() == 4)
697        graph.addEdge(1, 1)
698        self.assertTrue(graph.getNumDirEdges() == 5)
699
700        graph = DictGraph(False)
701        graph.addEdge(0, 1)
702        graph.addEdge(1, 2)
703
704        self.assertTrue(graph.getNumDirEdges() == 2)
705        graph.addEdge(1, 1)
706        self.assertTrue(graph.getNumDirEdges() == 3)
707
708    def testDijkstrasAlgorithm(self):
709        graph = DictGraph()
710
711        graph.addEdge(0, 1, 1)
712        graph.addEdge(1, 2, 1)
713        graph.addEdge(1, 3, 1)
714        graph.addEdge(2, 4, 1)
715        graph.setVertex(4, 1)
716
717        self.assertTrue((graph.dijkstrasAlgorithm(0) == numpy.array([0, 1, 2, 2, 3])).all())
718        self.assertTrue((graph.dijkstrasAlgorithm(1) == numpy.array([1, 0, 1, 1, 2])).all())
719        self.assertTrue((graph.dijkstrasAlgorithm(2) == numpy.array([2, 1, 0, 2, 1])).all())
720        self.assertTrue((graph.dijkstrasAlgorithm(3) == numpy.array([2, 1, 2, 0, 3])).all())
721        self.assertTrue((graph.dijkstrasAlgorithm(4) == numpy.array([3, 2, 1, 3, 0])).all())
722
723
724        #Test a graph which has an isolated node
725        graph = DictGraph()
726        graph.setVertex(5, 1)
727
728        graph.addEdge(0, 1, 1)
729        graph.addEdge(1, 2, 1)
730        graph.addEdge(1, 3, 1)
731
732        self.assertTrue((graph.dijkstrasAlgorithm(0) == numpy.array([0, 1, 2, 2, numpy.inf])).all())
733
734        #Test a graph in a ring
735        graph = DictGraph()
736
737        graph.addEdge(0, 1, 1)
738        graph.addEdge(1, 2, 1)
739        graph.addEdge(2, 3, 1)
740        graph.addEdge(3, 4, 1)
741        graph.addEdge(4, 0, 1)
742
743        self.assertTrue((graph.dijkstrasAlgorithm(0) == numpy.array([0, 1, 2, 2, 1])).all())
744
745        #Try case in which vertex ids are not numbers
746        graph = DictGraph()
747
748        graph.addEdge("a", "b", 1)
749        graph.addEdge("b", "c", 1)
750        graph.addEdge("b", "d", 1)
751        graph.addEdge("c", "e", 1)
752
753        inds = Util.argsort(graph.getAllVertexIds())
754        self.assertTrue((graph.dijkstrasAlgorithm("a")[inds] == numpy.array([0, 1, 2, 2, 3])).all())
755        self.assertTrue((graph.dijkstrasAlgorithm("b")[inds] == numpy.array([1, 0, 1, 1, 2])).all())
756        self.assertTrue((graph.dijkstrasAlgorithm("c")[inds] == numpy.array([2, 1, 0, 2, 1])).all())
757        self.assertTrue((graph.dijkstrasAlgorithm("d")[inds] == numpy.array([2, 1, 2, 0, 3])).all())
758        self.assertTrue((graph.dijkstrasAlgorithm("e")[inds] == numpy.array([3, 2, 1, 3, 0])).all())
759
760    def testAdjacencyList(self):
761        graph = DictGraph()
762        graph.addEdge("a", "b", 1)
763        graph.addEdge("b", "c", 1)
764        graph.addEdge("b", "d", 1)
765        graph.addEdge("c", "e", 1)
766        graph.setVertex("f", 1)
767
768        neighbourIndices, neighbourWeights = graph.adjacencyList()
769
770        vertexIds = graph.getAllVertexIds()
771
772        for i in range(len(neighbourIndices)):
773            for k, j in enumerate(neighbourIndices[i]):
774                self.assertTrue(graph.edgeExists(vertexIds[i], vertexIds[j]))
775                self.assertEquals(graph[vertexIds[i], vertexIds[j]], neighbourWeights[i][k])
776
777    def testFindAllDistances(self):
778        P = self.graph.findAllDistances()
779
780        P2 = numpy.zeros((self.graph.size, self.graph.size))
781        P2[0, :] = numpy.array([0, 1, 2, 2, 1, numpy.inf])
782        P2[1, :] = numpy.array([1, 0, 3, 1, 2, numpy.inf])
783        P2[2, :] = numpy.array([2, 3, 0, 4, 3, numpy.inf])
784        P2[3, :] = numpy.array([2, 1, 4, 0, 1, numpy.inf])
785        P2[4, :] = numpy.array([1, 2, 3, 1, 0, numpy.inf])
786        P2[5, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, numpy.inf, numpy.inf, 0])
787
788        self.assertTrue((P == P2).all())
789
790        #Now test the directed graph
791        P = self.graph2.findAllDistances()
792
793        P2 = numpy.zeros((self.graph.size, self.graph.size))
794        P2[0, :] = numpy.array([0, 1, 2, 2, 1, numpy.inf])
795        P2[1, :] = numpy.array([numpy.inf, 0, numpy.inf, 1, 2, numpy.inf])
796        P2[2, :] = numpy.array([numpy.inf, numpy.inf, 0, 5, 6, numpy.inf])
797        P2[3, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, 0, 1, numpy.inf])
798        P2[4, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, numpy.inf, 0, numpy.inf])
799        P2[5, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, numpy.inf, numpy.inf, 0])
800
801        self.assertTrue((P == P2).all())
802
803    def testToIGraph(self):
804        try:
805            import igraph
806        except ImportError as error:
807            logging.debug(error)
808            return
809
810        graph = DictGraph()
811
812        graph["a", "b"] = 1
813        graph["b", "c"] = 2
814
815        ig = graph.toIGraph()
816
817        self.assertEquals(len(ig.vs), 3)
818        self.assertEquals(ig[0, 2], 1)
819        self.assertEquals(ig[1, 2], 1)
820
821if __name__ == "__main__":
822    #import sys;sys.argv = ['', 'Test.testName']
823    unittest.main()
824