Package graphadt :: Module algorithms
[hide private]
[frames] | no frames]

Source Code for Module graphadt.algorithms

  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   
31 -def getBFSParents(g, v):
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 # If v is our root, we say it is its own parent 64 65 for vfrom, vto in BFSIt(g, v): 66 if parents[vto] is None: 67 parents[vto] = vfrom 68 return parents
69 70
71 -def BFS(g, v):
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
110 -def BFSIt(g, v):
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 # Whether we've seen it or not, yield it 143 if not seen[vto]: 144 seen[vto] = True 145 toGrow.append(vto) # Only if we've not seen it, queue it
146
147 -class Countpair(object):
148 - def __getattribute__(self, name):
149 object.__setattr__(self, name, object.__getattribute__(self, name) + 1) 150 return object.__getattribute__(self, name)
151
152 - def __init__(self):
153 self.pre = 0 154 self.post = 0
155
156 -def DFS(g, v):
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
203 -def isConnected(g):
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 #Trivially connected 224 225 g = UndirectedAdjListsGraph.copy(g) 226 return BFS(g, 0)[0] == g.order()
227
228 -def isStronglyConnected(g):
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
260 -def strongComponents(g):
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
298 -def getDFSParents(g, v, parents=None):
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
341 -def isAcyclic(g):
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 # All vertices spanned 385 return True
386
387 -def isAcyclicUndirected(g):
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
413 -def girth(g):
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
451 -def isBipartite(g):
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) # important for when arbitrary choices can conflict 469 470 n = g.order() 471 colour = [None] * n 472 for v in range(n): 473 if not colour[v] == None: # if we've seen it before 474 continue # never mind about it 475 colour[v] = False # Arbitrary choice for this one 476 toGrow = deque([v]) 477 while toGrow: 478 grow = toGrow.popleft() 479 for u in g.neighbours(grow): 480 if colour[u] == None: #Not coloured yet 481 colour[u] = not colour[grow] #Colour it the "other" colour from this one 482 toGrow.append(u) 483 else: 484 if colour[u] == colour[grow]: 485 #Whoops, we cannot colour this. 486 return False 487 #Coloured all the connected vertices in a satisfactory manner 488 return True
489
490 -def topSort1(g, v):
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
538 -def topSort2(g):
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 # If this node is now precedent free, 575 # And has not been sorted 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
586 -def maxDistance(g, v):
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 # Create an n-long vector filled with n 617 # I.e., set all to maximum distance 618 depth = 0 619 dist[v] = depth 620 distlist = [v] 621 count = 1 # Number of discovered vertices 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]): # First time we're seeing this vertex 628 dist[j] = depth 629 count += 1 # We've discovered one more vertex 630 nextlist.append(j) 631 distlist = nextlist 632 if count == n: # If we've found them all 633 return depth - 1, dist # Return the depth of the last vertex 634 else: 635 return float('infinity'), dist # Else return infinity
636 637
638 -def distanceMatrix(g):
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
659 -def diameter(g):
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
681 -def radius(g):
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: # A graph with no vertices has 0 698 return 0 # radius 699 for v in range(g.order()): 700 d, dist = maxDistance(g, v) 701 smallestDistance = min(smallestDistance, d) 702 return smallestDistance
703