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

Source Code for Module graphadt.representations

  1  ''' 
  2  Representations for the internal state of graphs in the pyGraphADT 
  3  package 
  4   
  5  By Danver Braganza 
  6  2009/12/22 
  7   
  8  This module specifies the interface of representations which may be used within the graph package. 
  9   
 10  A Representation encapsulates the design decision of how the actual graph information is stored, 
 11  and exposes a consistent interface, regardless of whether it is a list or matrix. 
 12   
 13  Two standard representations are also included: AdjacencyLists and AdjancecyMatrix. 
 14  ''' 
 15   
 16  from exceptions import NotImplementedError 
 17  from exceptions import ValueError 
 18  from abc import ABCMeta, abstractmethod 
 19   
 20  __all__ = ['Representation', 'AdjacencyLists', 'AdjacencyMatrix'] 
21 22 -class Representation():
23 ''' 24 This abstract class specifies the interface for the representation of the state within a graph. 25 26 The state of a graph is defined to be the vertices contained within it, as well as the arcs 27 between those vertices. Vertices are always numbered consecutively, starting from zero. Deleting 28 a vertex causes all higher numbered vertices to be renumbered. 29 30 Arcs are two-ary relations upon the set of vertices, and are directed. Arcs retain their meaning 31 during deletion, i.e. they must be renumbered along with the vertices. An arc incident or outgoing 32 from a deleted vertex is also deleted. 33 34 Edges are not explicitly modelled by this representation. However, by convention, the user may 35 choose to represent an edge by a pair of symmetric arcs together represents an edge. 36 37 This class is meant to be used internally within the pyGraphADT package only. If you want to 38 model a graph, used a subclass of the Graph type in graphadt.graphtypes. 39 ''' 40 41 __metaclass__ = ABCMeta 42 43 @abstractmethod
44 - def read(self, stream, defaultConstructor):
45 ''' 46 Sets the state of this representation to the data contained in some stream s. 47 48 This method lets this representation set its state from a stream. 49 The parameter defaultConstructor should be the method to call to connect two 50 Vertices in this graph. 51 52 @param stream: the stream must support the 'readlines()' method. 53 @param defaultConstructor: a method which can be called upon this object 54 which specifies how connections are to be made. 55 @type defaultConstructor: unbound function 56 @type stream: filestream supporting readlines() 57 ''' 58 59 raise NotImplementedError()
60 61 @abstractmethod
62 - def empty(self):
63 ''' 64 Removes all vertices from this graph. 65 ''' 66 raise NotImplementedError()
67 68 @abstractmethod
69 - def addVertices(self, n):
70 ''' 71 Creates records for n new vertices 72 73 @param n: label of a vertex in this representation 74 @type n: number 75 ''' 76 raise NotImplementedError()
77 78 @abstractmethod
79 - def removeVertex(self, i):
80 ''' 81 This method deletes the record of vertex labelled i, and all arcs connected to it. 82 All the vertices labelled higher than this vertex are relabelled. 83 84 @param i: a label of a vertex in this representation 85 @type i: number 86 87 @raises ValueError: if no such label i exists 88 ''' 89 raise NotImplementedError()
90 91 @abstractmethod
92 - def addArc(self, i, j):
93 ''' 94 Records that in this state there is an arc from vertex with label i to vertex with label 95 j 96 97 @param i: a label of a vertex in this representation 98 @type i: number 99 @param j: a label of a vertex in this representation 100 @type j: number 101 102 @raises ValueError: if no such labels exist 103 104 ''' 105 106 raise NotImplementedError()
107 108 @abstractmethod
109 - def removeArc(self, i, j):
110 ''' 111 Removes a directional connection from vertex i to vertex j, from the state of this 112 representation if it exists. If such a connection does not exist, no error is raised. 113 114 @param i: a label of a vertex in this representation 115 @type i: number 116 @param j: a label of a vertex in this representation 117 @type j: number 118 119 @raises ValueError: if no such labels exist 120 ''' 121 raise NotImplementedError()
122 123 @abstractmethod
124 - def isArc(self, i, j):
125 ''' 126 Returns True if and only if there is an arc connecting i to j. 127 128 @param i: a label of a vertex in this representation 129 @type i: number 130 @param j: a label of a vertex in this representation 131 @type j: number 132 133 @returns: True if there is an arc from vertex with label i to vertex with 134 label j in this state. 135 False otherwise 136 @rtype: boolean 137 138 @raises ValueError: if no such labels exist 139 ''' 140 141 raise NotImplementedError()
142 143 @abstractmethod
144 - def inDegree(self, i):
145 ''' 146 Returns the number of other vertices which are connected to i 147 148 @param i: a label of a vertex in this representation 149 @type i: number 150 151 @return: the number of arcs incident on i, as integer. 152 @rtype: number 153 @raises ValueError: if no such labels exist 154 ''' 155 156 raise NotImplementedError()
157 158 @abstractmethod
159 - def degree(self, i):
160 ''' 161 Returns the number of vertices to which vertex i connects 162 163 @param i: a label of a vertex in this representation 164 @type i: number 165 @returns: the number of arcs outgoing from i, as integer. 166 @rtype: number 167 Raises: ValueError if no such label i exists. 168 ''' 169 170 raise NotImplementedError()
171 172 @abstractmethod
173 - def neighbours(self, i):
174 ''' 175 Returns an iterable collection of all the vertices to which 176 the vertex with index i connects 177 178 @param i: a label of a vertex in this representation 179 @type i: number 180 181 @returns: all the vertices j, such that there is an arc (i, j). J must 182 be sorted, and safe for modification. 183 @rtype: list 184 185 @raises ValueError: if no such labels exist 186 ''' 187 188 raise NotImplementedError()
189 190 @abstractmethod
191 - def size(self):
192 ''' 193 Returns the number of arcs in this graph, as an integer. 194 195 @return: the number of arcs in this representation 196 @rtype: number 197 ''' 198 199 raise NotImplementedError()
200
201 - def selfEdges(self):
202 ''' 203 Returns the number of arcs in this representation from any vertex to itself, as an integer. 204 205 @return: the number of self loops in this representation 206 @rtype: number 207 ''' 208 209 selfEdges = 0 210 for i in range(self.order()): 211 if i in self.neighbours(i): 212 selfEdges += 1 213 return selfEdges
214 215 216 @abstractmethod
217 - def order(self):
218 ''' 219 Returns the number of vertices in this graph. 220 221 @return: the number of vertices in this graph 222 @rtype: number 223 ''' 224 225 raise NotImplementedError()
226 227 @abstractmethod
228 - def __str__(self):
229 ''' 230 Returns a string representation of this object's state. It should always be the case that 231 self.read() and str(self) should be compatible: the output of str should be valid input 232 for self.read() 233 234 @rtype: string 235 @returns: a string representation of this object's state 236 ''' 237 raise NotImplementedError()
238
239 -class AdjacencyLists(Representation):
240 ''' 241 AdjacencyLists extends and realises the abstract class Representation. 242 243 AdjacencyLists stores the state of vertices and arcs as a list of lists. 244 The arc (i,j) is represented by the list at element i containing the value j. 245 ''' 246
247 - def __init__(self):
248 self._adj = [] # Creates an internal empty array signifying an empty graph
249 250 # Mutators
251 - def empty(self):
252 self._adj = []
253
254 - def addVertices(self, n):
255 if not 0 <= n: 256 raise ValueError('Argument cannot be negative: n' % (n)) 257 258 for i in range(n): 259 self._adj.append([])
260
261 - def removeVertex(self, i):
262 if not 0 <= i < self.order(): 263 raise ValueError('Arguments out of bounds: v = %s' % v) 264 265 del self._adj[i] # Delete this vertex's adjacency list 266 267 for otherVertex in range(self.order()): 268 current = self._adj[otherVertex] 269 270 try: 271 current.remove(i) # Remove vertex i if it appears 272 except ValueError: 273 # It didn't appear 274 pass 275 276 for j in range(len(current)): # Relabel all higher vertices 277 if current[j] > i: 278 current[j] -= 1
279
280 - def addArc(self, i, j):
281 if not (0 <= i < self.order() and 0 <= j < self.order()): 282 raise ValueError('Arguments out of bounds: i = %s and j = %s' % (i, j)) 283 284 if not self.isArc(i, j): # This could be faster if instead of adjacency lists 285 self._adj[i].append(j) # We used adjacency sets.
286 287
288 - def removeArc(self, i, j):
289 if not (0 <= i < self.order() and 0 <= j < self.order()): 290 raise ValueError('Arguments out of bounds: i = %s and j = %s' % (i, j)) 291 292 try: 293 self._adj[i].remove(j) 294 except ValueError: 295 pass # Not Found
296
297 - def isArc(self, i, j):
298 if not (0 <= i < self.order() and 0 <= j < self.order()): 299 raise ValueError('Arguments out of bounds: i = %s and j = %s' % (i, j)) 300 301 return j in self._adj[i]
302
303 - def degree(self, i):
304 if not 0 <= i < self.order(): 305 raise ValueError('Argument out of bounds: i = %s' % i) 306 307 return len(self._adj[i])
308
309 - def inDegree(self, i):
310 if not 0 <= i < self.order(): 311 raise ValueError('Argument out of bounds: i = %s' % i) 312 313 retval = 0 314 for j in range(self.order()): 315 if self.isArc(j, i): 316 retval += 1 317 return retval
318
319 - def neighbours(self, i):
320 if not 0 <= i < self.order(): 321 raise ValueError('Argument out of bounds: i = %s' % i) 322 323 return sorted(self._adj[i]) # Returning a copy that is safe for modification
324
325 - def order(self):
326 return len(self._adj)
327
328 - def size(self):
329 return reduce( 330 lambda x, y : x + y, # Add up 331 map (len, self._adj), # The lengths of every row 332 0 # Initial value 0 333 )
334 335
336 - def __str__(self):
337 retval = '' 338 retval += str(self.order()) + '\n' 339 for i in range(self.order()): 340 retval += ' '.join( 341 map(str, 342 self.neighbours(i)) 343 ) + '\n' 344 return retval
345
346 - def read(self, stream, defaultConnector):
347 self.empty() 348 order = int(stream.readline().strip()) 349 self.addVertices(order) 350 for i in range(order): 351 for neighbour in map(int, stream.readline().strip().split()): 352 defaultConnector(i, neighbour)
353
354 -class AdjacencyMatrix(Representation):
355 ''' 356 AdjacencyMatrix extends and realises the abstract class Representation. 357 358 AdjacencyMatrix stores the state of vertices and arcs as a square matrix. 359 The arc (i,j) is represented by a value of True at element (i, j). 360 361 Note : In python, multi dimensional arrays are not built in, so this 362 matrix is stored as a jagged array, or an array of arrays. 363 ''' 364
365 - def __init__(self):
366 self._adj = []
367
368 - def empty(self):
369 self._adj = []
370
371 - def addVertices(self, n):
372 if not 0 <= n: 373 raise ValueError('Argument cannot be negative: n' % (n)) 374 375 old_order = len(self._adj) 376 377 for r in self._adj: 378 r += [0] * n # Extend each existing row 379 380 for i in range(n): 381 self._adj.append( 382 [0] * (old_order + n) # Add n new rows 383 )
384
385 - def removeVertex(self, i):
386 if not 0 <= i < self.order(): 387 raise ValueError('Argument out of bounds: i = %s' % i) 388 389 del self._adj[i] 390 for row in self._adj: 391 del row[i]
392
393 - def addArc(self, i, j):
394 if not (0 <= i < self.order() and 0 <= j < self.order()): 395 raise ValueError('Arguments out of bounds: i = %s and j = %s' % (i, j)) 396 397 self._adj[i][j] = True
398 399
400 - def removeArc(self, i, j):
401 if not (0 <= i < self.order() and 0 <= j < self.order()): 402 raise ValueError('Arguments out of bounds: i = %s and j = %s' % (i, j)) 403 404 self._adj[i][j] = False
405 406
407 - def isArc(self, i, j):
408 if not (0 <= i < self.order() and 0 <= j < self.order()): 409 raise ValueError('Arguments out of bounds: i = %s and j = %s' % (i, j)) 410 411 return self._adj[i][j]
412
413 - def degree(self, i): # Count the Trues in a row
414 if not 0 <= i < self.order(): 415 raise ValueError('Argument out of bounds: i = %s' % i) 416 417 return reduce (lambda x, y: x + y, # Add up all the booleans 418 self._adj[i], # True == 1 419 0 # Starting with 0 420 )
421
422 - def inDegree(self, i): # Count the Trues in a column
423 if not 0 <= i < self.order(): 424 raise ValueError('Argument out of bounds: i = %s' % i) 425 426 return reduce (lambda x, y: x + y[i], # Add up the ith element 427 self._adj, # In every row 428 0 # initial value of 0 429 ) 430
431 - def neighbours(self, i):
432 if not 0 <= i < self.order(): 433 raise ValueError('Argument out of bounds: i = %s' % i) 434 435 neighbours = [] 436 for j in range(self.order()): 437 if self._adj[i][j]: 438 neighbours.append(j) 439 return neighbours
440
441 - def order(self):
442 return len(self._adj)
443
444 - def size(self):
445 add = lambda x, y: x + sum(y) 446 return reduce(add, 447 self._adj, 0)
448
449 - def __str__(self):
450 retval = '' 451 n = self.order() 452 retval += str(n) + '\n' 453 for i in range(n): 454 for j in range(n): 455 if self._adj[i][j]: 456 retval += '1' 457 else: 458 retval += '0' 459 if not j == n - 1: 460 retval += " " 461 retval += '\n' 462 return retval
463
464 - def read(self, stream, defaultConnector):
465 self.empty() 466 order = int(stream.readline().strip()) 467 self.addVertices(order) 468 for i in range(order): 469 for neighbour, flag in enumerate(map(int, stream.readline().strip().split())): 470 if flag == 1: 471 defaultConnector(i, neighbour)
472