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

Source Code for Module graphadt.graphtypes

  1  ''' 
  2  Graph abstract data types of the pyGraphADT package. 
  3   
  4  Python version by Danver Braganza 
  5  designed to follow the signatures of code originally authored by  
  6  Michael J. Dinneen, with contributions by Sonny Datt. 
  7   
  8  2010 February 
  9   
 10  This module is part of the pyGraphADT package, and contains the definitions of 
 11  graph types. 
 12   
 13  This module is designed for use in the teaching of the Computer Science 220  
 14  course at the University of Auckland. 
 15  ''' 
 16   
 17  from graphadt import representations 
 18   
 19  from exceptions import NotImplementedError 
 20  from abc import ABCMeta, abstractmethod 
 21  from collections import defaultdict 
 22   
 23  __all__ = ['Graph','DirectedGraph', 'UndirectedGraph', 'DirectedAdjListsGraph',  
 24             'DirectedAdjMatrixGraph', 'UndirectedAdjListsGraph',  
 25             'UndirectedAdjMatrixGraph', 'WeightedDirectedAdjListsGraph',  
 26             'WeightedUndirectedAdjListsGraph'] 
27 28 -class Graph(object):
29 ''' 30 This is the basic definition of a graph. A graph, defined by this class 31 is to be a collection of consecutively-numbered vertices starting from zero, 32 and a collection of 2-ary relations between these vertices, representing 33 arcs or edges. 34 35 Graphs are implemented as wrappers of encapsulated Representation objects. 36 This means that graph object code for Adjacency Lists and Adjacency Matrix 37 representations can be identical. 38 39 Constructors: 40 -__init__(self, representation) -> default constructor 41 -copy(cls, g) -> copy constructor 42 -read(cls, stream) -> file reader constructor 43 44 Mutators: 45 -addVertices(n) 46 -addEdge(i, j) 47 -removeVertex(i) 48 -removeEdge(i, j) 49 50 Accessors: 51 -isEdge(i, j) 52 -degree(i) 53 -inDegree(i) 54 -order() 55 -size() 56 -neighbours(i) 57 58 Utility: 59 -__repr__() -- print a string representation of this graph 60 61 28/01/10: Graph is now an abstract class. This will not work in python 2.5 62 ''' 63 __metaclass__ = ABCMeta 64
65 - def __init__(self, representation):
66 ''' 67 Constructs an instance of this graph, and sets the hidden representation 68 to the parameter. 69 70 @param representation: the state of the graph to be copied 71 @type representation: graphADT.representations.Representation 72 ''' 73 self._representation = representation
74 75 @classmethod
76 - def copy(cls, g):
77 ''' 78 Creates an instance of cls, which is a copy of g. 79 80 The instance returned by this method is distinct from g, is of type 81 cls, and is at least as connected as g. 82 83 g need not be of the same type as cls. In fact, copying a 84 directed graph to an undirected graph is a standard way to create 85 its underlying graph. 86 87 @param cls: a concrete subclass of graph 88 @type cls: class 89 @param g: the graph to be copied 90 @type g: graphadt.graphtypes.Graph 91 92 Warning: A Graph itself is an abstract class, Graph.copy(g) is an 93 invalid method call. 94 ''' 95 96 newinstance = cls() 97 n = g.order() 98 newinstance.addVertices(n) 99 for i in range(n): 100 for j in g.neighbours(i): 101 newinstance.defaultConnector(i, j) 102 return newinstance
103 104 @abstractmethod
105 - def defaultConnector(self, i, j):
106 ''' 107 Joins i and j using the default connector type for this graph. 108 109 The default connector is the connector (Arc or Edge) used when constructing this graph 110 from other representations, such as when reading from file streams or copying 111 other graphs 112 113 This method is not intended for use in external code, it is for internal code which 114 does not know whether to create arcs or edges. 115 116 @param i: The label of the vertex from which the connection will be made 117 @type i: integer 118 @param j: The label of the vertex to which the connection will be made 119 (order is only important if the defaultConnector is an arc) 120 @type j: integer 121 ''' 122 return False
123
124 - def addVertices(self, n):
125 ''' 126 Adds n vertices to this graph. 127 128 This method adds n unconnected vertices to this graph. The vertices are numbered 129 consecutively, continuing from the highest numbered vertex already in the graph. 130 131 @param n: the number of vertices to add 132 @type n: integer 133 @raise ValueError: if n is negative 134 ''' 135 self._representation.addVertices(n)
136
137 - def removeVertex(self, i):
138 ''' 139 Removes vertex with label i from this graph. 140 141 This method removes the vertex with label i from this graph. All edges connected to it 142 are also removed. All the vertices labelled higher than this vertex are relabelled. 143 144 @param i: the label of the vertex to remove 145 @type i: integer 146 @raise ValueError: if i is not a valid vertex label in this graph. 147 ''' 148 self._representation.removeVertex(i)
149
150 - def addEdge(self, i, j):
151 ''' 152 Creates an edge between i and j 153 154 This method creates an edge between i and j. Edges are bi-directional, so the order of 155 the parameters i and j does not matter. Self-loops, i.e. edges where i == j, are allowed. 156 157 @param i: The label of the vertex from which the connection will be made 158 @type i: integer 159 @param j: The label of the vertex to which the connection will be made 160 @type j: integer 161 @raise ValueError: if either of i or j is not a valid vertex label in this graph. 162 163 ''' 164 self._representation.addArc(i, j) 165 self._representation.addArc(j, i)
166
167 - def removeEdge(self, i, j):
168 ''' 169 Removes any edge or arcs between i and j 170 171 This method removes the edge between i and j. If such an edge does not exist, this 172 method will remove the arc (i, j) or (j, i), if they exist. 173 174 @param i: The label of a vertex in this graph 175 @type i: integer 176 @param j: The label of a vertex in this graph 177 @type j: integer 178 @raise ValueError: if either of i or j is not a valid vertex label in this graph. 179 ''' 180 self._representation.removeArc(i, j) 181 self._representation.removeArc(j, i)
182
183 - def isEdge(self, i, j):
184 ''' 185 Returns True if and only if there exists and edge between i and j 186 187 @param i: The label of a vertex in this graph 188 @type i: integer 189 @param j: The label of a vertex in this graph 190 @type j: integer 191 @raise ValueError: if either of i or j is not a valid vertex label in this graph. 192 @return: True iff there is a biderectional edge between i and j 193 @rtype: boolean 194 ''' 195 196 return self._representation.isArc(i, j) and self._representation.isArc(j, i)
197
198 - def degree(self, i):
199 ''' 200 Returns the outdegree of vertex i. 201 202 This method returns the outdegree of vertex i, which is the number of vertices 203 directly connected by outgoing edges or arcs from i. 204 205 @param i: The label of a vertex in this graph 206 @type i: integer 207 208 @raise ValueError: if i is not a valid vertex label in this graph. 209 @return: the outdegree of vertex with label i. 210 @rtype: number 211 ''' 212 213 return self._representation.degree(i)
214 215 @abstractmethod
216 - def inDegree(self, i):
217 ''' 218 Returns the indegree of vertex i. 219 220 This method returns the indegree of vertex i, which is the number 221 of vertices which directly connect to i with incoming edges or arcs. 222 223 @param i: The label of a vertex in this graph 224 @type i: integer 225 226 @raise ValueError: if i is not a valid vertex label in this graph. 227 @return: the indegree of vertex with label i. 228 @rtype: number 229 230 ''' 231 232 raise NotImplementedError()
233
234 - def order(self):
235 ''' 236 Returns the number of vertices within this graph. 237 238 @return: the number of vertices in this graph. 239 @rtype: number 240 241 ''' 242 return self._representation.order()
243 244 @abstractmethod
245 - def size(self):
246 ''' 247 Returns the number of edges of an undirected graph or the number of 248 arcs in an directed graph. 249 250 @return: the number of connectors in this graph 251 @rtype: number 252 253 ''' 254 raise NotImplementedError()
255
256 - def neighbours(self, i):
257 ''' 258 Returns an iterable collection of all the vertices to which the vertex 259 with index i connects 260 261 This method returns an iterable collection of all the neighbours of vertex i. 262 A vertex j is defined to be the neighbour of vertex i if there exists an edge 263 between i and j, or if there exists an arc from i to j. 264 265 266 @param i: The label of a vertex in this graph 267 @type i: integer 268 269 @raise ValueError: if i is not a valid vertex label in this graph. 270 @return: the labels of the neighbours of vertex i 271 @rtype: list 272 ''' 273 274 return self._representation.neighbours(i)
275 276 neighbors = neighbours # Permit the American spelling 277
278 - def __repr__(self):
279 ''' 280 Equivalent of Java's toString 281 282 This method returns a string representation of this graph. The precise format 283 of this representation depends on the type of representation encapsulated 284 within this graph. 285 286 @return: string representation of this graph 287 @rtype: string 288 289 ''' 290 return str(self._representation)
291 292 @classmethod
293 - def read(cls, stream):
294 ''' 295 Constructs a graph to be equivalent to some stream data. 296 297 This method reads a stream of data from a file or similar source, and creates an 298 instance of type concrete type cls, which is set up to be equivalent to the data. 299 300 Note that an instance of type cls must accept the format of data being read. 301 302 @param cls: a concrete subclass of graph 303 @type cls: class 304 @param stream: the data to be duplicated 305 @raise ValueError: if stream is of the wrong format 306 307 ''' 308 newinstance = cls() 309 newinstance._representation.read(stream, newinstance.defaultConnector) 310 return newinstance
311
312 -class DirectedGraph(Graph):
313 ''' 314 This class defines a Directed Graph. The Directed Graph class extends the Graph 315 class and enables the creation of directed arcs. 316 317 This class provides several methods for modifying and accessing arcs, as well as extending 318 certain accessors to provide more accurate functionality. 319 320 Mutators: 321 -addArc(n) 322 -removeArc(i, j) 323 324 Accessors: 325 -isArc(i, j) 326 -inDegree(i) 327 -size() 328 329 If a Directed Graph contains two symmetric arcs, it is considered to contain the edge. 330 ''' 331
332 - def addArc(self, i, j):
333 ''' 334 Creates an arc from i to j 335 336 This method creates an arc from i to j. Arcs are uni-directional, and so the order of 337 the parameters i and j does matter. Self-loops, i.e. arcs where i == j, are allowed, 338 but are indistinguishable from edges. 339 340 341 @param i: The label of a vertex in this graph 342 @type i: integer 343 @param j: The label of a vertex in this graph 344 @type j: integer 345 @raises ValueError: if either i or j is not a valid vertex label in this graph. 346 ''' 347 348 self._representation.addArc(i, j)
349
350 - def removeArc(self, i, j):
351 ''' 352 Removes an arc from i to j 353 354 This method removes an arc from i to j. Note that if an edge between i and j 355 exists, this method can 'split' the edge and remove the outbound arc, so that 356 the arc (j, i) in the other direction, is left. 357 358 359 360 ''' 361 self._representation.removeArc(i, j)
362
363 - def isArc(self, i, j):
364 ''' 365 Returns True if and only if j is adjacent to i. 366 367 This method returns true if there is an arc from i to j. However, it also returns 368 true if there is an edge between i and j. 369 370 @param i: The label of a vertex in this graph 371 @type i: integer 372 @param j: The label of a vertex in this graph 373 @type j: integer 374 @raises ValueError: if either i or j is not a valid vertex label in this graph. 375 376 @return: True iff there is an arc between i and j 377 @rtype: boolean 378 379 ''' 380 381 return self._representation.isArc(i, j)
382
383 - def inDegree(self, i):
384 ''' 385 Returns the number of arcs and edges going into i. 386 387 Parameter: i -- a non-negative integer representing a vertex in this graph 388 389 Raises : ValueError if either i or j is not a valid vertex label in this graph. 390 ''' 391 392 return self._representation.inDegree(i)
393
394 - def size(self):
395 ''' 396 Returns the number of arcs in this graph. 397 398 This method returns the number of arcs in this graph. An edge counts as two 399 arcs. 400 401 @return: the number of arcs in this graph 402 @rtype: integer 403 404 ''' 405 406 return self._representation.size()
407
408 - def defaultConnector(self, i, j):
409 ''' 410 The default connector of this graph is the arc. 411 412 ''' 413 self.addArc(i, j)
414
415 -class UndirectedGraph(Graph):
416 ''' 417 This class defines the Undirected Graph. The Undirected Graph class extends the Graph 418 class, and has some behaviour customised for an undirected graph. 419 ''' 420 421 422 # def addArc(self, i, j): 423 # Undefined for Undirected Graphs 424 425 # def removeArc(self, i, j): 426 # Undefined for Undirected Graphs 427 428 # def isArc(self, i, j): 429 # Undefined for Undirected Graphs 430
431 - def defaultConnector(self, i, j):
432 ''' 433 The default connector of an undirected graph is an edge. 434 ''' 435 self.addEdge(i, j)
436
437 - def inDegree(self, i):
438 ''' 439 Returns the degree of vertex i, since indegree and outdegree are 440 equivalent in a directed graph. 441 @rtype: integer 442 @return: the degree of vertex i 443 ''' 444 # In-degree and out-degree are equivalent in undirected graph 445 # But out-degree is potentially computationally cheaper 446 return self.degree(i)
447
448 - def size(self):
449 ''' 450 Returns the number of edges of this graph. 451 452 The size of an undirected graph is defined as the number of edges. 453 Since the inner representation object only stores the number of arcs, 454 this number of arcs must be halved. However, self-arcs are NOT counted twice, 455 and halving this number leads to errors. Therefore, the number of edges 456 is equal to half the number of non-self arcs, plus the self-arc. 457 458 @return: the number of edges 459 @rtype: integer 460 ''' 461 size = self._representation.size() 462 selfEdges = self._representation.selfEdges() 463 size -= selfEdges 464 return size // 2 + selfEdges # Divide non-self edges by two to account
465 # for two arcs to an edge
466 467 -class DirectedAdjListsGraph(DirectedGraph):
468 ''' 469 Convenience class which constructs a directed graph and sets the inner representation 470 to an AdjacencyListsRepresentation. 471 '''
472 - def __init__(self):
474
475 -class DirectedAdjMatrixGraph(DirectedGraph):
476 ''' 477 Convenience class which constructs a directed graph and sets the inner representation 478 to an AdjacencyMatrixRepresentation. 479 ''' 480
481 - def __init__(self):
483
484 -class UndirectedAdjListsGraph(UndirectedGraph):
485 ''' 486 Convenience class which constructs an undirected graph and sets the inner representation 487 to an AdjacencyListsRepresentation. 488 ''' 489
490 - def __init__(self):
492
493 -class UndirectedAdjMatrixGraph(UndirectedGraph):
494 ''' 495 Convenience class which constructs an undirected graph and sets the inner representation 496 to an AdjacencyMatrixRepresentation. 497 ''' 498
499 - def __init__(self):
501
502 503 -class WeightedGraph(Graph):
504 ''' 505 This abstract class manages the weights of edges of a graph. 506 507 A weighted graph wraps an inner representation, and provides a few more functions 508 for manipulating weights. WeightedGraph is only a mixin class. 509 510 One of the key invariants is that if this class returns True for self.isArc(i, j), 511 then self.getArcWeight(i, j) must return a legitimate weight, or zero if none was set. 512 513 However, the output of self.getArcWeight(i, j), called with arbitrary arguments, 514 is not guaranteed. 515 516 Note: a weighted graph is an abstract class, and intended to be inherited from. 517 ''' 518
519 - def __init__(self):
520 ''' 521 Creates a mapping dictionary of edge weights, and assigns all edges a 522 default weight of 0 523 524 Note: You MUST call the other Graph class's constructor _before_ calling this one. 525 ''' 526 self._weights = defaultdict(lambda : 0) 527 528 529 # Warning: this is a really bad way to register THIS object to be 530 # Notified whenever a arc is removed from the representation. 531 # Basically, we replace the method call on the representation with an intercepting 532 # call on this object, which then calls the representation method correctly. 533 534 self._repremoveArc = self._representation.removeArc 535 self._representation.removeArc = self._removeArc
536 537 @classmethod
538 - def copy(cls, g):
539 ''' 540 Extends Graph.copy to copy weighted graphs. 541 542 This method creates a copy graph g. The copy is of type cls. If g is a 543 weighted graph, the weights are copied as well. 544 ''' 545 546 newinstance = Graph.copy(cls, g) 547 if hasattr(g, 'getArcWeight'): 548 for i in range(g.order()): 549 for j in range(g.order()): 550 self.setArcWeight(i, j, g.getArcWeight(i, j))
551
552 - def setArcWeight(self, i, j, w):
553 ''' 554 Sets the weight of arc (i, j) to w. 555 556 @param i: The label of a vertex in this graph 557 @type i: integer 558 @param j: The label of a vertex in this graph 559 @type j: integer 560 @param w: the weight of arc i,j 561 @raise ValueError: if i or j are not valid vertices in this graph 562 @raise ValueError: if arc (i, j) does not exist 563 ''' 564 if not self._representation.isArc(i, j): 565 raise ValueError('No such Arc exists') 566 self._weights[i, j] = w
567
568 - def getArcWeight(self, i, j):
569 ''' 570 Returns the weight of arc (i, j), or zero if no weight was set. 571 572 @param i: The label of a vertex in this graph 573 @type i: integer 574 @param j: The label of a vertex in this graph 575 @type j: integer 576 @returns: the weight of arc i, j 577 @raise ValueError: if i or j are not valid vertices in this graph 578 @raise ValueError: if arc (i, j) does not exist 579 ''' 580 if not self._representation.isArc(i, j): 581 raise ValueError('No such Arc exists') 582 return self._weights[i, j]
583
584 - def getNeighbourWeights(self, i):
585 ''' 586 Returns a list of weights of the neighbours of i. 587 588 This method returns a list of the weights of the arcs out of i, in 589 a direct correspondence to the list returned by neighbours(i). In other words, 590 for every element at index j in neighbours, the weight of the arc from i to 591 j is the jth element of getNeighbourWeights, 592 593 594 @param i: The label of a vertex in this graph 595 @type i: integer 596 @returns: the weights of all neighbours of i 597 @rtype: list 598 @raise ValueError: if i is not a valid vertex in this graph 599 600 ''' 601 return [self.getArcWeight(i, j) for j in self._representation.neighbours(i)]
602
603 - def _removeArc(self, i, j):
604 ''' 605 Removes a given arc from this graph, and cleans up the weights. 606 607 @param i: vertex from which the arc leads 608 @type i: integer 609 @param j: vertex from which the arc leads 610 @type j: integer 611 ''' 612 self._repremoveArc(i, j) # This is really bad programming practice. This is a bound method 613 # Of a different object, completely breaking encapsulation 614 # However, the solution would probably require more work, or some 615 # kind of Aspect Oriented Programming, which I don't have time to 616 # implement 617 618 if (i, j) in self._weights: 619 del self._weights[i,j]
620
621 - def removeVertex(self, v):
622 ''' 623 Removes a given vertex from this graph, and cleans up the weights. 624 625 @param v: label of a vertex 626 @type v: integer 627 628 @raises ValueError: if v does not represent a vertex in this graph. 629 ''' 630 Graph.removeVertex(self, v) 631 for (i, j) in self._weights: 632 if i < v and j < v: continue 633 weight = self._weights[i, j] 634 del self._weights[i, j] 635 if i == v or j == v: continue 636 if i > v: i -= 1 637 if j > v: j -= 1 638 self._weights[i, j] = weight
639
640 641 -class WeightedDirectedAdjListsGraph(WeightedGraph, DirectedAdjListsGraph):
642 ''' 643 Convenience class which uses multiple inheritance to achieve weighted, Directed 644 behaviour using an underlying Adjacency Lists Representation. 645 646 Note: this class has not been completely tested. Some faults may still exist. 647 ''' 648
649 - def __init__(self):
652
653 654 -class WeightedUndirectedAdjListsGraph(WeightedGraph, UndirectedAdjListsGraph):
655 ''' 656 Convenience class which uses multiple inheritance to achieve weighted, Directed 657 behaviour using an underlying Adjacency Lists Representation. 658 659 Note: this class has not been completely tested. Some faults may still exist. 660 ''' 661
662 - def __init__(self):
665