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']
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
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
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
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
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
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
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
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
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
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
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
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
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
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
277
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
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
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
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
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
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
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
409 '''
410 The default connector of this graph is the arc.
411
412 '''
413 self.addArc(i, j)
414
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
423
424
425
426
427
428
429
430
432 '''
433 The default connector of an undirected graph is an edge.
434 '''
435 self.addEdge(i, j)
436
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
445
446 return self.degree(i)
447
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
465
468 '''
469 Convenience class which constructs a directed graph and sets the inner representation
470 to an AdjacencyListsRepresentation.
471 '''
474
476 '''
477 Convenience class which constructs a directed graph and sets the inner representation
478 to an AdjacencyMatrixRepresentation.
479 '''
480
483
485 '''
486 Convenience class which constructs an undirected graph and sets the inner representation
487 to an AdjacencyListsRepresentation.
488 '''
489
492
494 '''
495 Convenience class which constructs an undirected graph and sets the inner representation
496 to an AdjacencyMatrixRepresentation.
497 '''
498
501
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
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
530
531
532
533
534 self._repremoveArc = self._representation.removeArc
535 self._representation.removeArc = self._removeArc
536
537 @classmethod
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
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
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
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
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)
613
614
615
616
617
618 if (i, j) in self._weights:
619 del self._weights[i,j]
620
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
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
652
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
665