1 '''
2 Unweighted graph algorithms of the pyGraphADT package.
3
4 Python version by Danver Braganza
5 based on code originally authored by Michael J. Dinneen, with contributions by
6 Sonny Datt.
7
8 2010 February
9
10 This module is part of the pyGraphADT package, and contains a number of basic
11 graph algorithms which operate upon the graph abstract types included in this
12 same package.
13
14 This module is designed to be used in the teaching of the Computer Science 220
15 course at the University of Auckland.
16 '''
17
18 from graphadt.graphtypes import DirectedAdjListsGraph, UndirectedAdjListsGraph
19 from graphadt.graphtypes import UndirectedGraph, DirectedGraph
20
21 from math import isinf
22 from exceptions import ValueError
23 from collections import deque
24
25 __all__ = ['getBFSParents', 'BFS', 'DFS', 'isConnected', 'isStronglyConnected',
26 'strongComponents', 'getDFSParents', 'isAcyclic', 'girth',
27 'isBipartite', 'topSort1', 'topSort2', 'maxDistance',
28 'distanceMatrix', 'diameter', 'radius',
29 ]
30
32 '''
33 Returns a list containing the direct ancestors of every vertex as
34 discovered during a breadth-first search starting from node v.
35
36 This function performs a breadth-first search starting at the vertex
37 labelled v. A list is returned such that the element at index i
38 is the label of the direct parent of vertex i. If a vertex has not
39 been discovered during the BFS traversal (due to being disconnected)
40 its parent is set to None. Furthermore, the parent of v is set to
41 itself.
42
43 Note: The correct labels of the parents are used. This may conflict with
44 some versions of the Java implementation, where indices are
45 incremented by one.
46
47 @type g: L{graphadt.graphtypes.Graph}
48 @param g: a graph
49 @type v: number
50 @param v: the integer label of a vertex
51
52 @returns: index of parent or None
53 @rtype: list of integers
54
55
56 @raise ValueError: if v is not the label of a vertex in g
57 '''
58
59 if not g.order() > v >= 0:
60 raise ValueError('Value of v out of range')
61
62 parents = [None] * g.order()
63 parents[v] = v
64
65 for vfrom, vto in BFSIt(g, v):
66 if parents[vto] is None:
67 parents[vto] = vfrom
68 return parents
69
70
72 '''
73 Performs breadth-first search from vertex v and returns number of vertices
74 discovered and a list showing the order vertices was discovered.
75
76 This function performs a breadth-first search starting from vertex v, and
77 returns a tuple containing two values. The first value is the number of
78 vertices discovered during breadth-first search, and the second a list where
79 element i is the order in which vertex i was discovered. If vertex i is not
80 discovered by this search, then element i of this list is set to None.
81
82 Note: Numberings in this list start from zero.
83
84 @param g: a graph
85 @type g: L{graphadt.graphtypes.Graph}
86 @param v: the integer label of a vertex
87 @type v: number
88
89 @return: an integer containing the number of vertices dicovered,
90 a list comprised of integers and one or more None.
91 @rtype: tuple
92
93 @raise ValueError: if v is not the label of a vertex in g
94 '''
95
96 if not g.order() > v >= 0:
97 raise ValueError('Value of v out of range')
98 levelorder = [None] * g.order()
99 level = 0
100 levelorder[v] = level
101
102 for vfrom, vto in BFSIt(g, v):
103 if levelorder[vto] == None:
104 level += 1
105 levelorder[vto] = level
106
107 level += 1
108 return level, levelorder
109
111 '''
112 Iterates over the vertices in graph g in breadth-first order.
113
114 This function iterates over the vertices in a graph is breadth-first order.
115 It will repeat vertices if there are cycles in the graph, but will not
116 expand them. This is so that code which makes use of this iterator can
117 detect cycles, while trusting that this iterator will never loop infinitely.
118
119 This function is not intended to be called by external code.
120
121 @param g: a graph
122 @type g: L{graphadt.graphtypes.Graph}
123 @param v: the integer label of a vertex
124 @type v: number
125 @return: yields (vfrom, vto), where vfrom is the current parent vertex,
126 and vto is the vertex being discovered.
127 @rtype: tuple
128
129 @raises ValueError: if v is not the label of a vertex in g
130 @raises StopIteration: if all vertices have been discovered.
131 '''
132 if not g.order() > v >= 0:
133 raise ValueError('Value of v out of range')
134 seen = [False] * g.order()
135
136 seen[v] = True
137 toGrow = deque([v])
138
139 while toGrow:
140 vfrom = toGrow.popleft()
141 for vto in g.neighbours(vfrom):
142 yield vfrom, vto
143 if not seen[vto]:
144 seen[vto] = True
145 toGrow.append(vto)
146
151
153 self.pre = 0
154 self.post = 0
155
157 '''
158 Performs depth-first search from vertex v, and returns number of vertices
159 discovered as well as two lists showing the pre-order and post-order in which
160 vertices were discovered.
161
162 This function performs a depth-first search starting from vertex v, and
163 returns a tuple containing three values. The first value is the number of
164 vertices discovered during the search. The second value is a list of
165 preorders, where element i is the order in which vertex i was first visited.
166 The third value is a list of postorders, where element i is the order it
167 which vertex i was lat visited. If a node is never visited, its preorder
168 and postorder will both be None.
169
170 Note: Numbering of order in both lists start from zero.
171
172 @param g: a graph
173 @type g: L{graphadt.graphtypes.Graph}
174 @param v: the integer label of a vertex
175 @type v: number
176
177 @return: a tuple of: integer representing total vertices discovered
178 preorder : a list containing the preorders of every vertex
179 postorder: a list containing the postorders of every vertex
180 @rtype: tuple
181
182 @raise ValueError: if v is not the label of a vertex in g
183 '''
184
185 if not g.order() > v >= 0:
186 raise ValueError('Value of v out of range')
187
188 def doDFS(g, v, preorder, postorder, count):
189 '''
190 '''
191 preorder[v] = count.pre
192 for i in g.neighbours(v):
193 if preorder[i] is None:
194 preorder, postorder, count = doDFS(g, i, preorder, postorder, count)
195 postorder[v] = count.post
196 return preorder, postorder, count
197
198 preorder = [None] * g.order()
199 postorder = [None] * g.order()
200 preorder, postorder, count = doDFS(g, v, preorder, postorder, Countpair())
201 return postorder[v], preorder, postorder
202
204 '''
205 True if and only if the graph g is connected.
206
207 This function checks for connectedness of graph g by converting it into an
208 undirected graph, and then performing breadth-first search. G is considered
209 connected if this breadth-first search is able to discover all nodes.
210
211 Note: if g is a directed graph, then this function returns True if g is weakly
212 connected.
213
214 @param g: a graph
215 @type g: L{graphadt.graphtypes.Graph}
216
217 @return: True if and only if graph g is connected
218 False otherwise
219 @rtype: boolean
220 '''
221
222 if g.order() == 0:
223 return True
224
225 g = UndirectedAdjListsGraph.copy(g)
226 return BFS(g, 0)[0] == g.order()
227
229 '''
230 Returns True if and only if the graph g is strongly connected.
231
232 This function returns true if and only if g is strongly connected. A
233 strongly connected graph is defined as one where for every pair of vertices
234 u and v, there exists a path from u to v.
235
236 @param g: a graph
237 @type g: L{graphadt.graphtypes.Graph}
238
239 @return: True if and only if graph g is strongly connected
240 False otherwise
241 @rtype: boolean
242
243 '''
244
245 n = g.order()
246 if g.order() == 0:
247 return True
248
249 if DFS(g, 0)[0] < n:
250 return False
251
252 reversed = DirectedAdjListsGraph()
253 reversed.addVertices(n)
254 for i in range(n):
255 for j in g.neighbours(i):
256 reversed.addArc(j, i)
257
258 return DFS(reversed, 0)[0] == n
259
261 '''
262 Finds the strong components of graph g.
263
264 This function finds the strong components of graph g. For any pair of
265 vertices v, u, if there is a path from v to u and a path from u to v, then
266 u and v must belong to the same strongly-connected-component.
267
268 This function returns a list where the element at index i is the label of
269 the component to which vertex i belongs. If graph g is strongly connected,
270 every element in this list will be 0, since every vertex is in component 0.
271
272 Note: Numberings in this list start from zero.
273 To find the number of components, use max(strongComponents(g)) + 1
274
275
276 @param g: a graph
277 @type g: L{graphadt.graphtypes.Graph}
278
279 @return: a list comprised of integers.
280
281 @raises ValueError: if v is not the label of a vertex in g
282 '''
283
284 scc = [None] * g.order()
285 component = 0
286
287 for i in range(g.order()):
288 if scc[i] is None:
289 scc[i] = component
290 trash, comp = BFS(g,i)
291 for j, depth in (enumerate(comp)):
292 if depth is not None:
293 if BFS(g, j)[1][i] is not None:
294 scc[j] = component
295 component += 1
296 return scc
297
299 '''
300 Returns a list containing the direct ancestors of every vertex as
301 discovered during a depth-first search starting from node v.
302
303 This function performs a depth-first search starting at the vertex
304 labelled v. A list is returned such that the element at index i
305 is the label of the direct parent of vertex i. If a vertex has not
306 been discovered during the DFS traversal (due to being disconnected)
307 its parent is set to None. Furthermore, the parent of v is set to
308 itself.
309
310 @param g: a graph
311 @type g: L{graphadt.graphtypes.Graph}
312 @param v: the integer label of a vertex
313 @type v: number
314
315
316 @return: a list comprised of integers and one or more None.
317 @rtype: list
318
319 @Raises ValueError: if v is not the label of a vertex in g
320
321 Note: The correct labels of the parents are used. This may conflict with
322 some versions of the Java implementation, where indices returned are
323 incremented by one.
324 '''
325
326 if not g.order() > v >= 0:
327 raise ValueError('Value of v out of range')
328
329 if parents is None:
330 parents = [None] * g.order()
331 if parents[v] == None:
332 parents[v] = v
333
334 for i in g.neighbours(v):
335 if parents[i] is None:
336 parents[i] = v
337 getDFSParents(g, i, parents)
338
339 return parents
340
342 '''
343 Returns True if and only if g is an Acyclic graph.
344
345 This function checks g for cycles. If g is an undirected graph, cycles of
346 length 2 will be ignored. If g is a directed graph, then any edges in g will
347 count as a cycle of length 2.
348
349 Any self-loops in g will also be counted as cycles.
350
351 @param g: the graph
352 @type g: graphadt.graphtypes.Graph
353
354 @rtype: boolean
355 @return:True if and only if g is acyclic
356
357 '''
358
359 n = g.order()
360 if g.order() == 0:
361 return True
362
363 if isinstance(g, UndirectedGraph):
364 return isAcyclicUndirected(g)
365
366 span = [False] * n
367
368 count = 0
369 for i in range(n):
370 if span[i]: continue
371
372 componentcount, preorder, postorder = DFS(g, i)
373 for j in range(n):
374 if preorder[j] is not None:
375 span[j] == True
376
377 for k in g.neighbours(j):
378 if k == j:
379 return False
380 if preorder[k] < preorder[j]:
381 return False
382
383 count += componentcount
384 if count == n: break
385 return True
386
388
389 '''
390 True if, given that g is an undirected graph, it is also acyclic.
391
392 Not meant to be called by external code
393
394 @param g: the graph
395 @type g: graphadt.graphtypes.Graph
396
397
398 @returns:True if and only if g is acyclic
399 @rtype: boolean
400
401
402 '''
403 n = g.order()
404 m = g.size()
405
406 if m > n:
407 return False
408
409 components = max(strongComponents(g)) + 1
410
411 return n == m + components
412
414 '''
415 Returns the girth of g.
416
417 This function only returns values for graphs with girth >= 3 or 1.
418 Girth 1 is caused by self-loops.
419 Girth >= 3 is the normal case of cycles
420 Girth infinity indicates no cycles
421 Girth 2 is never returned, because every undirected edge would otherwise
422 create a cycle of girth 2. If the only cycle which exists is of girth 2,
423 infinity is returned instead.
424
425 @param g: the graph
426 @type g: graphadt.graphtypes.Graph
427
428 @returns: length of smallest cycle in g
429 @rtype: integer or infinity
430
431
432 '''
433
434 best = float('infinity')
435 n = g.order()
436 for i in range(n):
437 depth = [None] * n
438 depth[i] = 0
439 parent = [None] * n
440 for vfrom, vto in BFSIt(g, i):
441 if depth[vto] == None:
442 depth[vto] = depth[vfrom] + 1
443 parent[vto] = vfrom
444 else:
445 if not parent[vfrom] == vto:
446 looplength = depth[vfrom] + depth[vto] + 1
447 best = min(best, looplength)
448 return best
449
450
452
453 '''
454 Returns True if and only if g is bipartite
455
456 This function verifies whether g is bipartite by attempting a 2-colouring
457 of the vertices. If the colouring succeeds, the function returns True, else
458 False
459
460 @param g: the graph
461 @type g: graphadt.graphtypes.Graph
462
463 @rtype: boolean
464 @returns: True if and only if g is bipartite
465
466 '''
467
468 g = UndirectedAdjListsGraph.copy(g)
469
470 n = g.order()
471 colour = [None] * n
472 for v in range(n):
473 if not colour[v] == None:
474 continue
475 colour[v] = False
476 toGrow = deque([v])
477 while toGrow:
478 grow = toGrow.popleft()
479 for u in g.neighbours(grow):
480 if colour[u] == None:
481 colour[u] = not colour[grow]
482 toGrow.append(u)
483 else:
484 if colour[u] == colour[grow]:
485
486 return False
487
488 return True
489
491 '''
492 Sorts the vertices in DirectedGraph g in a topological order
493
494 This function performs a depth-first search of g, starting at v, to determine
495 the dependencies and then returns a topological ordering of the vertices
496 such that for every vertex v, its ancestors in g appear earlier in the
497 ordering.
498
499 The ordering is represented by a list with element i being the order of
500 vertex i. If vertex i is not discoverable by a depth-first search from v,
501 element i of this list will be None.
502
503 g must be a directed acyclic graph, or an error is raised.
504
505 If g is not a connected graph, it may be better to use topSort2 instead.
506
507 @param g: the graph to sort
508 @type g: graphadt.graphtypes.Graph
509 @param v: the label of a vertex
510 @type v: integer
511
512 @rtype: is of zero or more integers and zero or more None
513 @returns: zero or more integers and zero or more None
514
515 @raises ValueError: if g is not a directed acyclic graph
516 @raises ValueError: if v is not a vertex in g
517 '''
518
519 if not g.order() > v >= 0:
520 raise ValueError('Value of v out of range')
521
522 if not isinstance(g, DirectedGraph):
523 raise ValueError('G must be a directed graph')
524
525 if not isAcyclic(g):
526 raise ValueError('G must be an acyclic graph')
527
528 sort = [None] * g.order()
529
530 level, preorder, postorder = DFS(g, v)
531
532 for i in range(len(postorder)):
533 if postorder[i] is not None:
534 sort[i] = level - postorder[i]
535 return sort
536
537
539 '''
540 Sorts the vertices in DirectedGraph g in a topological order
541
542 This function returns a topological ordering of the vertices such that for
543 every vertex v, its ancestors in g appear earlier in the ordering.
544
545 The ordering is represented by a list with element i being the order of
546 vertex i.
547
548 g must be a directed acyclic graph, or an error is raised.
549
550 @param g: the graph to sort
551 @type g: graphadt.graphtypes.Graph
552
553 @rtype: is of zero or more integers and zero or more None
554 @returns: zero or more integers and zero or more None
555
556 @raises ValueError: if g is not a directed acyclic graph
557 '''
558 if not isinstance(g, DirectedGraph):
559 raise ValueError('G must be a directed graph')
560
561 if not isAcyclic(g):
562 raise ValueError('G must be an acyclic graph')
563
564 n = g.order()
565 sort = [None] * n
566 inDeg = [g.inDegree(i) for i in range(n)]
567 count = 0
568
569 progress = True
570 while progress:
571 progress = False
572
573 for v in range(n):
574
575
576 if inDeg[v] == 0 and sort[v] == None:
577 sort[v] = count
578 count += 1
579 progress = True
580
581 for i in g.neighbours(v):
582 inDeg[i] -= 1
583 return sort
584
585
587 '''
588 Returns the length to the shortest path to the furthest vertex from v, as
589 well as the distance to all the other vertices.
590
591 This function computes the eccentricity of vertex v in graph g by
592 performing breadth-first search and noting the distance of the last
593 node to be discovered. This function also computes the distance of every
594 vertex discovered in this way. Vertices that cannot be discovered are set
595 to a distance of infinity. If all nodes are not discovered, the
596 eccentricity of v is set to infinity.
597
598 This function returns a tuple where the first element is the eccentricity of
599 v. The second element is a list, where element i is the shortest distance
600 from vertex v to vertex i.
601
602 @param g: the graph
603 @type g: graphadt.graphtypes.Graph
604 @param v: the label of a vertex
605 @type v: integer
606
607 @returns: eccentricity of v, distance of other vertices from v
608 @rtype: tuple -> integer or infinity, list
609
610 @raises ValueError: if v is not the label of a vertex in g
611 '''
612 n = g.order()
613 if not g.order() > v >= 0:
614 raise ValueError('Value of v out of range')
615
616 dist = [float('infinity')] * n
617
618 depth = 0
619 dist[v] = depth
620 distlist = [v]
621 count = 1
622 while distlist:
623 depth += 1
624 nextlist = []
625 for i in distlist:
626 for j in g.neighbours(i):
627 if isinf(dist[j]):
628 dist[j] = depth
629 count += 1
630 nextlist.append(j)
631 distlist = nextlist
632 if count == n:
633 return depth - 1, dist
634 else:
635 return float('infinity'), dist
636
637
639 '''
640 Returns a matrix of all the distances between vertices in g.
641
642 This function returns an n x n matrix, where n is the size of the vertex set
643 of g. The value at element i,j of this matrix is the shortest distance from
644 vertex i to vertex j. If j is not reachable from i, then the element at i,j
645 is set to infinity.
646
647 @param g: the graph
648 @type g: graphadt.graphtypes.Graph
649
650 @returns: distance matrix of g
651 @rtype: list of lists
652 '''
653
654 matrix = []
655 for v in range(g.order()):
656 matrix.append(maxDistance(g,v)[1])
657 return matrix
658
660 '''
661 Returns the diameter of g.
662
663 The diameter of g is defined as the maximum eccentricity of its vertices.
664 This function calculates the eccentricity of every vertex in g and then
665 returns the maximum.
666
667 @param g: the graph
668 @type g: graphadt.graphtypes.Graph
669
670 @returns: the diameter of g
671 @rtype: integer or infinity
672
673 '''
674
675 largestDistance = 0
676 for v in range(g.order()):
677 d, dist = maxDistance(g, v)
678 largestDistance = max(largestDistance, d)
679 return largestDistance
680
682 '''
683 Returns the radius of g.
684
685 The radius of g is defined as the minimum eccentricity of its vertices.
686 This function calculates the eccentricity of every vertex in g and then
687 returns the minimum.
688
689 @param g: the graph
690 @type g: graphadt.graphtypes.Graph
691
692 @returns: the radius of g
693 @rtype: integer or infinity
694 '''
695
696 smallestDistance = float('inf')
697 if g.order() == 0:
698 return 0
699 for v in range(g.order()):
700 d, dist = maxDistance(g, v)
701 smallestDistance = min(smallestDistance, d)
702 return smallestDistance
703