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']
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
63 '''
64 Removes all vertices from this graph.
65 '''
66 raise NotImplementedError()
67
68 @abstractmethod
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
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
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
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
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
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
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
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
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
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
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
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
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
249
250
253
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
262 if not 0 <= i < self.order():
263 raise ValueError('Arguments out of bounds: v = %s' % v)
264
265 del self._adj[i]
266
267 for otherVertex in range(self.order()):
268 current = self._adj[otherVertex]
269
270 try:
271 current.remove(i)
272 except ValueError:
273
274 pass
275
276 for j in range(len(current)):
277 if current[j] > i:
278 current[j] -= 1
279
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):
285 self._adj[i].append(j)
286
287
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
296
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
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
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
320 if not 0 <= i < self.order():
321 raise ValueError('Argument out of bounds: i = %s' % i)
322
323 return sorted(self._adj[i])
324
326 return len(self._adj)
327
329 return reduce(
330 lambda x, y : x + y,
331 map (len, self._adj),
332 0
333 )
334
335
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):
353
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
367
370
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
379
380 for i in range(n):
381 self._adj.append(
382 [0] * (old_order + n)
383 )
384
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
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
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
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
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,
418 self._adj[i],
419 0
420 )
421
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],
427 self._adj,
428 0
429 )
430
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
442 return len(self._adj)
443
445 add = lambda x, y: x + sum(y)
446 return reduce(add,
447 self._adj, 0)
448
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