fuzz.graph

70 """\ 71 Crisp graph class (used for alpha cuts and crisp methods). 72 """ 73 _setcls = set 74

75 - def __init__(self, viter=None, eiter=None, directed=True):

76 """\ 77 Construct a crisp graph from optional iterables. 78 79 @param viter: The iterable for the vertex set (optional). 80 @type viter: C{object} 81 @param eiter: The iterable for the edge set (optional). 82 @type eiter: C{object} 83 @param directed: Defines the graph as directed or undirected. 84 @type directed: C{bool} 85 """ 86 self._directed = directed 87 self._V = self._setcls() 88 self._E = self._setcls() 89 if viter is not None: 90 for vertex in viter: 91 self.add_vertex(vertex) 92 if eiter is not None: 93 for edge in eiter: 94 self.add_edge(edge)

95

96 - def __repr__(self):

97 """\ 98 Return the canonical representation of a graph. 99 100 @return: Canonical representation. 101 @rtype: C{str} 102 """ 103 return '%s(viter=%s, eiter=%s, directed=%s)' \ 104 % (self.__class__.__name__, self._V, self._E, self.directed)

105

106 - def __str__(self):

107 """\ 108 Return the string representation of a graph. 109 110 @return: String representation. 111 @rtype: C{str} 112 """ 113 return '%s (%s): vertices: %s, edges: %s' % (self.__class__.__name__, 114 'directed' if self.directed else 'undirected', self._V, self._E)

115 116 @property

117 - def directed(self):

118 """\ 119 Return whether this graph is directed. This should only be set by the 120 constructor and is read-only afterward. 121 122 @rtype: C{bool} 123 """ 124 return self._directed

125

126 - def add_vertex(self, vertex):

127 """\ 128 Add a vertex to the graph. 129 130 @param vertex: The vertex to add. 131 @type vertex: C{object} 132 """ 133 try: 134 hash(vertex) 135 except TypeError: 136 raise TypeError('vertex must be a hashable object') 137 self._V.add(vertex)

138

139 - def remove_vertex(self, vertex):

140 """\ 141 Remove a vertex and all edges connected to it from the graph. 142 143 @param vertex: The vertex to remove. 144 @type vertex: C{object} 145 """ 146 if not vertex in self._V: 147 raise KeyError(vertex) 148 for edge in self.edges(): 149 if vertex in edge: 150 self.remove_edge(edge.tail, edge.head) 151 self._V.remove(vertex)

152

153 - def add_edge(self, edge):

154 """\ 155 Add an edge to the graph. 156 157 @param edge: The edge to add. 158 @type edge: L{GraphEdge} 159 """ 160 if not isinstance(edge, GraphEdge): 161 raise TypeError('edge must be a GraphEdge') 162 if not edge.tail in self.vertices() or not edge.head in self.vertices(): 163 raise KeyError('tail and head must be in vertex set') 164 if edge in self.edges(): 165 raise ValueError('edge already exists') 166 self._E.add(edge)

167

168 - def remove_edge(self, tail, head):

169 """\ 170 Remove an edge from the graph by tail and head. 171 172 @param tail: The tail vertex of the edge. 173 @type tail: C{object} 174 @param head: The head vertex of the edge. 175 @type head: C{object} 176 """ 177 for edge in self.edges(tail, head): 178 self._E.remove(edge)

179

180 - def vertices(self):

181 """\ 182 Return a set of vertices in the graph. 183 184 @rtype: C{set} 185 """ 186 return self._V

187

188 - def edges(self, tail=None, head=None):

189 """\ 190 Return a set of edges with tail and/or head optionally specified. 191 192 @param tail: The tail vertex constraint (optional). 193 @type tail: C{object} 194 @param head: The head vertex constraint (optional). 195 @type head: C{object} 196 @return: The set of edges specified. 197 @rtype: C{set} 198 """ 199 if (tail is not None and not tail in self.vertices()) \ 200 or (head is not None and not head in self.vertices()): 201 raise KeyError('specified tail/head must be in vertex set') 202 eset = set([edge for edge in self._E \ 203 if (tail is None or edge.tail == tail) \ 204 and (head is None or edge.head == head)]) 205 if not self.directed: 206 eset |= set([edge for edge in self._E \ 207 if (tail is None or edge.head == tail) \ 208 and (head is None or edge.tail == head)]) 209 return eset

210

211 - def weight(self, tail, head):

212 """\ 213 Return the weight of an edge. Returns 1 for the base unweighted graph. 214 215 @param tail: The tail vertex. 216 @type tail: C{object} 217 @param head: The head vertex. 218 @type head: C{object} 219 @return: The weight of the edge from tail to head. 220 @rtype: C{float} 221 """ 222 return 0.0 if tail == head \ 223 else 1.0 if GraphEdge((tail, head)) in self.edges() \ 224 else float('inf')

225

226 - def edges_by_weight(self, tail=None, head=None):

227 """\ 228 Return a list of edges, sorted in ascending order by weight, with tail 229 and/or head optionally specified. 230 231 @param tail: The tail vertex constraint (optional). 232 @type tail: C{object} 233 @param head: The head vertex constraint (optional). 234 @type head: C{object} 235 @return: The list of edges sorted by weight. 236 @rtype: C{list} 237 """ 238 ebw = [] 239 for edge in self.edges(tail, head): 240 ebw.append((edge, self.weight(edge.tail, edge.head))) 241 ebw.sort(cmp = lambda a, b: cmp(a[1], b[1])) 242 for i in range(len(ebw)): 243 ebw[i] = ebw[i][0] 244 return ebw

245 246 # Convenience functions 247

248 - def connect(self, tail, head):

249 """\ 250 Connect a pair of vertices with a new edge. Convenience wrapper for 251 add_edge(). 252 253 @param tail: The tail vertex. 254 @type tail: C{object} 255 @param head: The head vertex. 256 @type head: C{object} 257 """ 258 self.add_edge(GraphEdge((tail, head)))

259

260 - def disconnect(self, tail, head):

261 """\ 262 Disconnect a pair of vertices by removing the edge between them. 263 Convenience wrapper for remove_edge(). 264 265 @param tail: The tail vertex. 266 @type tail: C{object} 267 @param head: The head vertex. 268 @type head: C{object} 269 """ 270 self.remove_edge(tail, head)

271 272 # Binary graph operations 273

274 - def __eq__(self, other):

275 """\ 276 Compare two graphs for equality. Does not recognize isomorphism 277 (vertex identifiers must be the same). 278 279 @param other: The other graph. 280 @type other: L{Graph} 281 @return: True if equal, false otherwise. 282 @rtype: C{bool} 283 """ 284 self._binary_sanity_check(other) 285 if self._V != other._V or self._E != other._E: 286 return False 287 return True

288

289 - def __ne__(self, other):

290 """\ 291 Compare two graphs for inequality. 292 293 @param other: The other graph. 294 @type other: L{Graph} 295 @return: True if not equal, false otherwise. 296 @rtype: C{bool} 297 """ 298 return not self == other

299

300 - def issubgraph(self, other):

301 """\ 302 Report whether another graph contains this graph. 303 304 @param other: The other graph. 305 @type other: L{Graph} 306 @return: True if a subgraph, false otherwise. 307 @rtype: C{bool} 308 """ 309 self._binary_sanity_check(other) 310 return True if self._V <= other._V and self._E <= other._E else False

311

312 - def issupergraph(self, other):

313 """\ 314 Report whether this graph contains another graph. 315 316 @param other: The other graph. 317 @type other: L{Graph} 318 @return: True if a supergraph, false otherwise. 319 @rtype: C{bool} 320 """ 321 self._binary_sanity_check(other) 322 return True if self._V >= other._V and self._E >= other._E else False

323 324 __le__ = issubgraph 325 __ge__ = issupergraph 326

327 - def __lt__(self, other):

328 """\ 329 Report whether another graph strictly contains this graph. 330 331 @param other: The other graph. 332 @type other: L{Graph} 333 @return: True if a strict subgraph, false otherwise. 334 @rtype: C{bool} 335 """ 336 return True if self.issubgraph(other) and self != other else False

337

338 - def __gt__(self, other):

339 """\ 340 Report whether this graph strictly contains another graph. 341 342 @param other: The other graph. 343 @type other: L{Graph} 344 @return: True if a strict supergraph, false otherwise. 345 """ 346 return True if self.issupergraph(other) and self != other else False

347 348 @staticmethod

349 - def _binary_sanity_check(other):

350 """\ 351 Check that the other argument to a binary operation is also a graph, 352 raising a TypeError otherwise. 353 354 @param other: The other argument. 355 @type other: L{Graph} 356 """ 357 if not isinstance(other, Graph): 358 raise TypeError('operation only permitted between graphs')

359 360 # Connectivity-related functions 361

362 - def adjacent(self, tail, head):

363 """\ 364 Report whether two vertices are adjacent (directly connected by an 365 edge). 366 367 @param tail: The tail vertex. 368 @type tail: C{object} 369 @param head: The head vertex. 370 @type head: C{object} 371 @return: True if adjacent, false otherwise. 372 @rtype: C{bool} 373 """ 374 return False if tail == head \ 375 else True if self.edges(tail, head) \ 376 else False

377

378 - def neighbors(self, vertex):

379 """\ 380 Return a set of vertices which are adjacent to the specified vertex. 381 382 @param vertex: The vertex. 383 @type vertex: C{object} 384 @return: The set of vertices adjacent to vertex. 385 @rtype: C{set} 386 """ 387 return set([v for v in self.vertices() if self.adjacent(vertex, v)])

388

389 - def connected(self, tail, head):

390 """\ 391 Report whether two vertices are connected. Uses a breadth-first search 392 algorithm. 393 394 @param tail: The tail vertex. 395 @type tail: C{object} 396 @param head: The head vertex. 397 @type head: C{object} 398 @return: True if adjacent, false otherwise. 399 @rtype: C{bool} 400 """ 401 if tail == head: 402 return False 403 D = set() 404 N = self.neighbors(tail) - D 405 while True: 406 if head in N: 407 return True 408 D |= N 409 P = set() 410 for vertex in N: 411 P |= self.neighbors(vertex) 412 P -= D 413 if not len(P): 414 break 415 N = P.copy() 416 return False

417 418 # Shortest path algorithms 419

420 - def dijkstra(self, start):

421 """\ 422 Dijkstra's algorithm (shortest paths from start vertex to all other 423 vertices). 424 425 @param start: The start vertex. 426 @type start: C{object} 427 @return: The 'previous" array of Dijkstra's algorithm. 428 @rtype: C{list} 429 """ 430 dist = {} 431 prev = {} 432 Q = set(self.vertices()) 433 for vertex in self.vertices(): 434 dist[ vertex ] = float('inf') 435 prev[ vertex ] = None 436 dist[ start ] = 0.0 437 while len(Q): 438 u = None 439 for vertex in Q: 440 if not u or dist[vertex] < dist[u]: 441 u = vertex 442 Q.remove(u) 443 for vertex in self.neighbors(u): 444 alt = dist[u] + self.weight(u, vertex) 445 if alt < dist[vertex]: 446 dist[vertex] = alt 447 prev[vertex] = u 448 return prev

449

450 - def shortest_path(self, start, end):

451 """\ 452 Find the shortest path from the start vertex to the end vertex using 453 Dijkstra's algorithm. 454 455 @param start: The start vertex. 456 @type start: C{object} 457 @param end: The end vertex. 458 @type end: C{object} 459 @return: Shortest path vertex list and total distance. 460 @rtype: C{list}, C{float} 461 """ 462 path = [] 463 u = end 464 prev = self.dijkstra(start) 465 dist = 0.0 466 while u in prev.keys(): 467 path.insert(0, u) 468 if prev[u]: 469 dist += self.weight(prev[u], u) 470 u = prev[u] 471 return path, dist

472

473 - def floyd_warshall(self):

474 """\ 475 Floyd-Warshall algorithm (shortest path length between all pairs of 476 vertices). 477 478 @return: A 2D dictionary of pairwise shortest path lengths. 479 @rtype: C{dict} of C{dict} of C{double} 480 """ 481 path = {} 482 for i in self.vertices(): 483 path[i] = {} 484 for j in self.vertices(): 485 path[i][j] = self.weight(i, j) 486 for k in self.vertices(): 487 for i in self.vertices(): 488 for j in self.vertices(): 489 path[i][j] = min(path[i][j], path[i][k] + path[k][j]) 490 return path

491 492 # Subgraph algorithms 493

494 - def minimum_spanning_tree(self):

495 """\ 496 Minimum spanning tree (Kruskal's algorithm). 497 498 @return: The minimum spanning tree. 499 @rtype: L{Graph} 500 """ 501 if self.directed: 502 raise TypeError('MST cannot be found for directed graphs') 503 # create a list of edges sorted by weight 504 Q = self.edges_by_weight() 505 # initialize the minimum spanning tree 506 T = Graph(viter=self.vertices(), directed=False) 507 # construct the tree 508 while len(Q) and len(T.edges()) < len(self.edges()): 509 edge = Q.pop(0) 510 if not T.connected(edge.tail, edge.head): 511 T.add_edge(edge) 512 return T

513

514 - def shortest_path_subgraph(self):

515 """\ 516 Shortest path subgraph, containing only strong edges (edges which form 517 part of a shortest path between some pair of vertices). 518 519 @return: The shortest path subgraph. 520 @rtype: L{Graph} 521 """ 522 # initialize the shortest path subgraph 523 G = Graph(self.vertices(), self.edges(), self.directed) 524 # compute all-pairs shortest paths 525 path = self.floyd_warshall() 526 # remove all non-strong edges 527 for edge in self.edges(): 528 if self.weight(edge.tail, edge.head) > path[edge.tail][edge.head]: 529 G.remove_edge(edge.tail, edge.head) 530 return G

Source Code for Module fuzz.graph