fuzz.graph

58 """\ 59 Crisp graph class (used for alpha cuts and crisp methods). 60 """ 61 setcls = set 62

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

64 """\ 65 Construct a crisp graph from optional iterables. 66 67 @param viter: The iterable for the vertex set (optional). 68 @type viter: C{object} 69 @param eiter: The iterable for the edge set (optional). 70 @type eiter: C{object} 71 @param directed: Defines the graph as directed or undirected. 72 @type directed: C{bool} 73 """ 74 self._directed = directed 75 self._V = self.setcls() 76 self._E = self.setcls() 77 if viter is not None: 78 for vertex in viter: 79 self.add_vertex(vertex) 80 if eiter is not None: 81 for edge in eiter: 82 self.add_edge(edge)

83

84 - def __repr__(self):

85 """\ 86 Return string representation of this graph. 87 88 @return: String representation. 89 @rtype: C{string} 90 """ 91 return 'V: %s\nE: %s' % (self._V, self._E)

92 93 __str__ = __repr__ 94 95 @property

96 - def directed(self):

97 """\ 98 Return whether this graph is directed. This should only be set by the 99 constructor and is read-only afterward. 100 101 @rtype: C{bool} 102 """ 103 return self._directed

104

105 - def add_vertex(self, vertex):

106 """\ 107 Add a vertex to the graph. 108 109 @param vertex: The vertex to add. 110 @type vertex: C{object} 111 """ 112 try: 113 hash(vertex) 114 except TypeError: 115 raise TypeError("vertex must be a hashable object") 116 self._V.add(vertex)

117

118 - def remove_vertex(self, vertex):

119 """\ 120 Remove a vertex and all edges connected to it from the graph. 121 122 @param vertex: The vertex to remove. 123 @type vertex: C{object} 124 """ 125 if not vertex in self._V: 126 raise KeyError(vertex) 127 for edge in self.edges(): 128 if vertex in edge: 129 self.remove_edge(edge.tail, edge.head) 130 self._V.remove(vertex)

131

132 - def add_edge(self, edge):

133 """\ 134 Add an edge to the graph. 135 136 @param edge: The edge to add. 137 @type edge: L{GraphEdge} 138 """ 139 if not isinstance(edge, GraphEdge): 140 raise TypeError("edge must be a GraphEdge") 141 if not edge.tail in self.vertices or not edge.head in self.vertices: 142 raise KeyError("tail and head must be in vertex set") 143 if edge in self.edges(): 144 raise ValueError("edge already exists") 145 self._E.add(edge)

146

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

148 """\ 149 Remove an edge from the graph by tail and head. 150 151 @param tail: The tail vertex of the edge. 152 @type tail: C{object} 153 @param head: The head vertex of the edge. 154 @type head: C{object} 155 """ 156 for edge in self.edges(tail, head): 157 self._E.remove(edge)

158 159 @property

160 - def vertices(self):

161 """\ 162 Return a set of vertices in the graph. 163 164 @rtype: C{set} 165 """ 166 return self._V

167

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

169 """\ 170 Return a set of edges with tail and/or head optionally specified. 171 172 @param tail: The tail vertex constraint (optional). 173 @type tail: C{object} 174 @param head: The head vertex constraint (optional). 175 @type head: C{object} 176 @return: The set of edges specified. 177 @rtype: C{set} 178 """ 179 if (tail is not None and not tail in self.vertices) \ 180 or (head is not None and not head in self.vertices): 181 raise KeyError("specified tail/head must be in vertex set") 182 eset = set([edge for edge in self._E \ 183 if (tail is None or edge.tail == tail) \ 184 and (head is None or edge.head == head)]) 185 if not self.directed: 186 eset |= set([edge for edge in self._E \ 187 if (tail is None or edge.head == tail) \ 188 and (head is None or edge.tail == head)]) 189 return eset

190

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

192 """\ 193 Return the weight of an edge. Returns 1 for the base unweighted graph. 194 195 @param tail: The tail vertex. 196 @type tail: C{object} 197 @param head: The head vertex. 198 @type head: C{object} 199 @return: The weight of the edge from tail to head. 200 @rtype: C{float} 201 """ 202 if tail == head: 203 return 0.0 204 elif GraphEdge((tail, head)) in self.edges(): 205 return 1.0 206 else: 207 return float('inf')

208

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

210 """\ 211 Return a list of edges, sorted in ascending order by weight, with tail 212 and/or head optionally specified. 213 214 @param tail: The tail vertex constraint (optional). 215 @type tail: C{object} 216 @param head: The head vertex constraint (optional). 217 @type head: C{object} 218 @return: The list of edges sorted by weight. 219 @rtype: C{list} 220 """ 221 ebw = [] 222 for edge in self.edges(tail, head): 223 ebw.append((edge, self.weight(edge.tail, edge.head))) 224 ebw.sort(cmp = lambda a, b: cmp(a[1], b[1])) 225 for i in range(len(ebw)): 226 ebw[i] = ebw[i][0] 227 return ebw

228 229 # Convenience functions 230

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

232 """\ 233 Connect a pair of vertices with a new edge. Convenience wrapper for 234 add_edge(). 235 236 @param tail: The tail vertex. 237 @type tail: C{object} 238 @param head: The head vertex. 239 @type head: C{object} 240 """ 241 self.add_edge(GraphEdge((tail, head)))

242

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

244 """\ 245 Disconnect a pair of vertices by removing the edge between them. 246 Convenience wrapper for remove_edge(). 247 248 @param tail: The tail vertex. 249 @type tail: C{object} 250 @param head: The head vertex. 251 @type head: C{object} 252 """ 253 self.remove_edge(GraphEdge((tail, head)))

254 255 # Binary graph operations 256

257 - def __eq__(self, other):

258 """\ 259 Compare two graphs for equality. Does not recognize isomorphism 260 (vertex identifiers must be the same). 261 262 @param other: The other graph. 263 @type other: L{Graph} 264 @return: True if equal, false otherwise. 265 @rtype: C{bool} 266 """ 267 self._binary_sanity_check(other) 268 if self._V != other._V or self._E != other._E: 269 return False 270 return True

271

272 - def __ne__(self, other):

273 """\ 274 Compare two graphs for inequality. 275 276 @param other: The other graph. 277 @type other: L{Graph} 278 @return: True if not equal, false otherwise. 279 @rtype: C{bool} 280 """ 281 return not self == other

282

283 - def issubgraph(self, other):

284 """\ 285 Report whether another graph contains this graph. 286 287 @param other: The other graph. 288 @type other: L{Graph} 289 @return: True if a subgraph, false otherwise. 290 @rtype: C{bool} 291 """ 292 self._binary_sanity_check(other) 293 if self._V <= other._V and self._E <= other._E: 294 return True 295 return False

296

297 - def issupergraph(self, other):

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

310 311 __le__ = issubgraph 312 __ge__ = issupergraph 313

314 - def __lt__(self, other):

315 """\ 316 Report whether another graph strictly contains this graph. 317 318 @param other: The other graph. 319 @type other: L{Graph} 320 @return: True if a strict subgraph, false otherwise. 321 @rtype: C{bool} 322 """ 323 if self.issubgraph(other) and self != other: 324 return True 325 return False

326

327 - def __gt__(self, other):

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

338 339 @staticmethod

340 - def _binary_sanity_check(other):

341 """\ 342 Check that the other argument to a binary operation is also a graph, 343 raising a TypeError otherwise. 344 345 @param other: The other argument. 346 @type other: L{Graph} 347 """ 348 if not isinstance(other, Graph): 349 raise TypeError("binary operation only permitted between graphs")

350 351 # Connectivity-related functions 352

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

354 """\ 355 Report whether two vertices are adjacent (directly connected by an 356 edge). 357 358 @param tail: The tail vertex. 359 @type tail: C{object} 360 @param head: The head vertex. 361 @type head: C{object} 362 @return: True if adjacent, false otherwise. 363 @rtype: C{bool} 364 """ 365 if tail == head: 366 return False 367 if self.edges(tail, head): 368 return True 369 return False

370

371 - def neighbors(self, vertex):

372 """\ 373 Return a set of vertices which are adjacent to the specified vertex. 374 375 @param vertex: The vertex. 376 @type vertex: C{object} 377 @return: The set of vertices adjacent to vertex. 378 @rtype: C{set} 379 """ 380 return set([v for v in self.vertices if self.adjacent(vertex, v)])

381

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

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

410 411 # Shortest path algorithms 412

413 - def dijkstra(self, start):

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

442

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

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

465

466 - def floyd_warshall(self):

467 """\ 468 Floyd-Warshall algorithm (shortest path length between all pairs of 469 vertices). 470 471 @return: A 2D dictionary of pairwise shortest path lengths. 472 @rtype: C{dict} of C{dict} of C{double} 473 """ 474 path = {} 475 for i in self.vertices: 476 path[i] = {} 477 for j in self.vertices: 478 path[i][j] = self.weight(i, j) 479 for k in self.vertices: 480 for i in self.vertices: 481 for j in self.vertices: 482 path[i][j] = min(path[i][j], path[i][k] + path[k][j]) 483 return path

484 485 # Subgraph algorithms 486

487 - def minimum_spanning_tree(self):

488 """\ 489 Minimum spanning tree (Kruskal's algorithm). 490 491 @return: The minimum spanning tree. 492 @rtype: L{Graph} 493 """ 494 if self.directed: 495 raise TypeError("Kruskal's algorithm is for undirected graphs only") 496 # create a list of edges sorted by weight 497 Q = self.edges_by_weight() 498 # initialize the minimum spanning tree 499 T = Graph(viter = self.vertices, directed = False) 500 # construct the tree 501 while len(Q) and len(T.edges()) < len(self.edges()): 502 edge = Q.pop(0) 503 if not T.connected(edge.tail, edge.head): 504 T.add_edge(edge) 505 return T

506

507 - def shortest_path_subgraph(self):

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

Source Code for Module fuzz.graph