gPy.Graphs

1 """Graphs 2 3 @var _version: Version of this module 4 @type _version: String 5 """ 6 7 import Tkinter 8 import random 9 from Utils import member, emptyset, pretty_str_set, scrolled_frame 10 from IO import read_twlib, GraphCanvas 11 from Hypergraphs import Incidence, ReducedGraphicalHypergraph 12 13 _version = '$Id: Graphs.py,v 1.2 2008/10/07 09:09:58 jc Exp $'

14 15 -class GraphError(Exception):

16 pass

17

18 -class CycleError(GraphError):

19 pass

20

21 -class DirectedCycleError(GraphError):

22 pass

23

24 -class ExistingVertexError(GraphError):

25 pass

26

27 -class LineError(GraphError):

28 pass

29

30 -class ArrowError(GraphError):

31 pass

32

33 -class EdgeError(GraphError):

34 pass

35

36 -class ArcError(GraphError):

37 pass

38

39 -class _AbsDiGraph(Incidence):

40 """Abstract class containing methods which are appropriate only 41 for graphs where arrows are allowed. 42 """ 43

44 - def add_arrow(self,frm,to):

45 """Add an arrow (directed edge) between two 46 existing vertices 47 48 Does not affect any lines from C{frm} to C{to} 49 @param frm: One of the vertices connected by the line 50 @type frm: Any immutable type 51 @param to: The other vertex connected by the line 52 @type to: Any immutable type 53 @raise KeyError: If either vertex does not exist 54 """ 55 self._ch[frm].add(to) 56 self._pa[to].add(frm)

57

58 - def add_arrows(self,arrows):

59 """Add a collection of arrows to the graph 60 61 @param arrows: The arrows to add 62 @type arrows: An iterator over pairs (of vertices). 63 Each pair is a sequence of length 2 64 @raise KeyError: If a vertex does not exist 65 """ 66 for arrow in arrows: 67 self.add_arrow(arrow[0],arrow[1])

68

69 - def put_arrow(self,frm,to):

70 """Put an arrow (directed edge) between two 71 existing vertices 72 73 Any pre-existing line between C{frm} and C{to} will be deleted. 74 @param frm: One of the vertices connected by the line 75 @type frm: Immutable type 76 @param to: The other vertex connected by the line 77 @type to: Immutable type 78 @raise KeyError: If either vertex does not exist 79 @raise DirectedCycleError: If C{self} is an ADG and the 80 arrow would create a directed cycle 81 """ 82 self.add_arrow(frm,to) 83 self.discard_line(frm,to)

84

85 - def put_arrows(self,arrows):

86 """Add a collection of arrows to the graph 87 88 Any pre-existing lines will be deleted. 89 @param arrows: The arrows to add 90 @type arrows: An iterator over pairs (of vertices). 91 Each pair is a sequence of length 2 92 @raise KeyError: If a vertex does not exist 93 @raise DirectedCycleError: If C{self} is an ADG and one of the 94 arrows would create a directed cycle 95 """ 96 for arrow in arrows: 97 self.put_arrow(arrow[0],arrow[1])

98

99 - def put_family(self,child,parents):

100 """Put arrows from all C{parents} to C{child}, 101 creating vertices when needed 102 103 Any existing lines between parents and children 104 will be overwritten 105 @param child: The vertex to which all added arrows will point 106 @type child: Immutable type 107 @param parents: The collection of vertices from which there will be 108 arrows pointing to child 109 @type parents: An iterator over immutable types 110 @raise DirectedCycleError: If C{self} is an ADG and one of the 111 arrows would create a directed cycle 112 """ 113 existing_vertices = self.vertices() 114 if child not in existing_vertices: 115 self.add_vertex(child) 116 for parent in parents: 117 if parent not in existing_vertices: 118 self.add_vertex(parent) 119 self.put_arrow(parent,child)

120

121 - def remove_arrow(self,frm,to):

122 """Remove an arrow between two existing vertices 123 124 @param frm: One of the vertices connected by the possible arrow 125 @type frm: Immutable type 126 @param to: The other vertex connected by the possible arrow 127 @type to: Immutable type 128 @raise KeyError: If either vertex does not exist 129 @raise KeyError: If the arrow is not there 130 """ 131 self._pa[to].remove(frm) 132 self._ch[frm].remove(to)

133

134 135 -class _AbsGraph(Incidence):

136 """Abstract class with method suitable for all types of graph 137 138 @ivar _pa: Maps each vertex to its parents 139 @type _pa: Dictionary 140 @ivar _ch: Maps each vertex to its children 141 @type _ch: Dictionary 142 @ivar _ne: Maps each vertex to its neighbours 143 @type _ne: Dictionary 144 @ivar _vertex_positions: Maps vertices to canvas co-ordinates 145 @type _vertex_positions: Dictionary 146 """ 147

148 - def __init__(self,vertices=(),arrows=(),lines=(),vertex_positions=None):

149 """Graph initialisation 150 151 @param vertices: The vertices of the graph 152 @type vertices: An iterator/sequence over immutable types 153 @param arrows: The arrows of the graph 154 @type arrows: An iterator/sequence over pairs (of vertices). 155 Each pair is a sequence of length 2. 156 @param lines: The lines of the graph 157 @type lines: An iterator/sequence over pairs (of vertices). 158 Each pair is a sequence of length 2. 159 @param vertex_positions: A mapping from vertices to canvas 160 co-ordinates 161 @type vertex_positions: Dictionary 162 @raise KeyError: If C{arrows} or C{lines} contains a vertex not included in 163 C{vertices} 164 @raise ExistingVertexError: If C{vertices} repeats a vertex. 165 """ 166 if vertex_positions is None: 167 vertex_positions = {} 168 self.reinit(vertices,arrows,lines,vertex_positions)

169

170 - def __eq__(self,other):

171 """Graphs of different classes are considered equal if they have the same vertices, arrows 172 and lines 173 174 @return: Whether the graphs are equal 175 @rtype: Boolean 176 """ 177 return ( 178 self._pa == other._pa and 179 self._ne == other._ne 180 )

181

182 - def __ne__(self,other):

183 """Graphs of different classes are considered equal if they 184 have the same vertices, arrows and lines 185 186 @return: Whether the graphs are not equal 187 @rtype: Boolean 188 """ 189 return ( 190 self._pa != other._pa or 191 self._ne != other._ne 192 )

193

194 - def __repr__(self):

195 """Formal string representation of a graph 196 """ 197 return '%s(%s,%s,%s,%s)' % ( 198 self.__class__.__name__, 199 sorted(self.vertexlist()), 200 sorted(self.arrows()), 201 sorted(self.lines()), 202 self._vertex_positions)

203

204 - def __str__(self):

205 """Pretty string representation of a graph 206 207 Vertices, arrows and edges are presented in 208 sorted order 209 @return: Pretty string representation of a graph 210 @rtype: String 211 """ 212 out = 'Vertices:\n%s\n' % sorted(self.vertexlist()) 213 arrows = self.arrows() 214 if arrows: 215 out += 'Arrows:\n' 216 for arrow in sorted(arrows): 217 out += '%s -> %s\n' % arrow 218 lines = self.lines() 219 if lines: 220 out += 'Lines:\n' 221 for line in sorted(lines): 222 out += '%s - %s\n' % line 223 return out

224

225 - def add_vertex(self,vertex):

226 '''Adds a vertex to a graph 227 228 @param vertex: The vertex to add 229 @type vertex: Anything immutable 230 @raise ExistingVertexError: If vertex already exists 231 ''' 232 if vertex in self._pa: 233 raise ExistingVertexError 234 for dkt in (self._pa, self._ch, self._ne): 235 dkt[vertex] = set()

236 237

238 - def add_vertices(self,vertices):

239 """Add a collection of vertices to the graph 240 241 @param vertices: The vertices to add 242 @type vertices: An iterator/sequence over immutable types 243 """ 244 for vertex in vertices: 245 self.add_vertex(vertex)

246

247 - def arbitrary_vertex(self):

248 """Returns an arbitrary vertex in the graph 249 250 @return: A vertex in the graph 251 @rtype: Anything immutable 252 """ 253 return self._pa.keys()[0]

254

255 - def arrows(self):

256 """Return a list of arrows 257 258 @return: A list of arrows 259 @rtype: List of C{(vertex,child)} tuples 260 """ 261 arrows = [] 262 for vertex, children in self._ch.items(): 263 for child in children: 264 arrows.append((vertex,child)) 265 return arrows

266

267 - def child(self,vertex):

268 """Return an arbitrary child of C{vertex} 269 270 @return: A vertex which is a child of C{vertex} or None 271 if it has no children 272 @rtype: An immutable type (typically a String) 273 """ 274 for child in self._ch[vertex]: 275 return child

276 277

278 - def children(self,vertex):

279 """Return the children of vertex 280 281 @return: The children of C{vertex} 282 @rtype: Set 283 """ 284 return self._ch[vertex]

285

286 - def copy(self):

287 """Return a copy a graph 288 289 @return: A copy of the graph 290 @rtype: Same class as C{self} 291 """ 292 cp = self.__class__() 293 for attr, val in vars(self).items(): 294 if attr == '_vertex_positions': 295 setattr(cp,attr,val.copy()) 296 continue 297 setattr(cp,attr,{}) 298 for vertex, vertices in val.items(): 299 getattr(cp,attr)[vertex] = vertices.copy() 300 return cp

301

302 - def delete_vertex(self,vertex):

303 """Deletes a vertex from a graph 304 305 @param vertex: The vertex to delete 306 @type vertex: Immutable type 307 @raise KeyError: If the vertex does not exist 308 """ 309 for dkt in (self._pa, self._ch, self._ne): 310 del dkt[vertex] 311 for vertices in dkt.values(): 312 vertices.discard(vertex)

313

314 - def diff(self,other):

315 pass

316

317 - def discard_arrow(self,frm,to):

318 """Discard any arrow between two existing vertices 319 320 If there is no such arrow nothing happens 321 @param frm: One of the vertices connected by the possible arrow 322 @type frm: Immutable type 323 @param to: The other vertex connected by the possible arrow 324 @type to: Immutable type 325 @raise KeyError: If either vertex does not exist 326 """ 327 self._pa[to].discard(frm) 328 self._ch[frm].discard(to)

329

330 - def discard_line(self,frm,to):

331 """Discard the line between two existing vertices 332 (if it exists) 333 334 If there is no such line nothing happens 335 @param frm: One of the vertices connected by the possible arrow 336 @type frm: Immutable type 337 @param to: The other vertex connected by the possible arrow 338 @type to: Immutable type 339 @raise KeyError: If either vertex does not exist 340 """ 341 self._ne[to].discard(frm) 342 self._ne[frm].discard(to)

343

344 - def edges(self):

345 """Return a list of the edges in the graph 346 347 @return: A list of edges 348 @rtype: List 349 """ 350 edges = [] 351 for dkt in (self._ne, self._ch): 352 for vertex, others in dkt.items(): 353 for other in others: 354 edges.append((vertex,other)) 355 return edges

356

357 - def extend_paths(self,paths):

358 """Iterates over paths which can be produced by adding 359 one vertex to a path in C{paths} 360 361 Each path is actually a tuple C{path_set,path} 362 where C{path_set} is the set of all vertices in the 363 path, and C{path} is a list representing the path itself 364 365 @param paths: Paths to extend 366 @type paths: List 367 @return: Generator of paths 368 @rtype: Generator iterator 369 """ 370 for path_set, path in paths: 371 last_vertex = path[-1] 372 for new_vertex in ((self._ne[last_vertex] | 373 self._ch[last_vertex]) - path_set): 374 new_vertex_list = [new_vertex] 375 yield (path_set | set(new_vertex_list), 376 path + new_vertex_list)

377 378

379 - def get_gui_graph_kill(self,gui,win=None):

380 """Set the graph to match the one displayed on a GUI, 381 and perhaps kill the GUI 382 383 @param gui: The GUI 384 @type gui: L{GraphCanvas} object 385 @param win: Window to kill 386 @type win: C{Tkinter} object 387 """ 388 vertices, arrows, lines, vertex_positions = gui.graph() 389 try: 390 self.reinit(vertices,arrows,lines,vertex_positions) 391 if win is not None: 392 win.destroy() 393 except AttributeError, msg: 394 print 'Graph contains an illegal edge', msg

395

396 - def gui_edit(self,parent,**config):

397 """Edit a graph using a GUI 398 399 @param parent: Parent window for GUI 400 @type parent: Suitable Tkinter widget 401 @param config: Configuration options for the GUI 402 @type config: Various 403 """ 404 gui_main = Tkinter.Frame(parent) 405 gui_main.pack() 406 canvas = GraphCanvas(self, gui_main, **config) 407 canvas.pack() 408 bottom = Tkinter.Frame(gui_main) 409 bottom.pack() 410 for (txt,cmd) in (('Reset', canvas.original_state), 411 ('Delete', canvas.zap), 412 ('Save', lambda gui=canvas: self.get_gui_graph_kill(gui)), 413 ('Done', (lambda gui=canvas,win=gui_main: 414 self.get_gui_graph_kill(gui,win))), 415 ('Quit', (lambda gui=canvas,win=parent: 416 self.get_gui_graph_kill(gui,win))), 417 ('Help', self._gui_help)): 418 button = Tkinter.Button(bottom,text=txt,command=cmd) 419 button.bind('<Return>', lambda event: cmd()) 420 button.pack(side=Tkinter.LEFT)

421 422 423

424 - def gui_display(self,parent,scrollable=False,**config):

425 """Display a graph using a GUI 426 427 @param parent: Parent window for GUI 428 @type parent: Suitable Tkinter widget 429 @param config: Configuration options for the GUI 430 @type config: Various 431 @return: The GUI 432 @rtype: L{GraphCanvas} 433 """ 434 if scrollable: 435 return self.gui_display(scrolled_frame(parent),False,width=10000,height=1000,**config) 436 gui_main = GraphCanvas(self, parent, edit=False, **config) 437 gui_main.pack() 438 return gui_main

439 440

441 - def is_neighbour(self,vertex1,vertex2):

442 """Return whether C{vertex1} is a neighbour of C{vertex2} 443 444 @param vertex1: Vertex 445 @type vertex1: Immutable 446 @param vertex2: Vertex 447 @type vertex2: Immutable 448 @raise KeyError: If C{vertex1} is not a vertex 449 """ 450 return vertex2 in self._ne[vertex1]

451

452 - def is_parent(self,parent,child):

453 """Return whether C{parent} is a parent of C{child} 454 455 @param parent: Potential parent vertex 456 @type parent: Immutable 457 @param child: Potential child vertex 458 @type child: Immutable 459 @return: Whether C{parent} is a parent of C{child} 460 @rtype: Boolean 461 @raise KeyError: If C{child} is not a vertex 462 """ 463 return parent in self._pa[child]

464 465 466

467 - def lines(self):

468 """Returns an ordered list of lines in the graph 469 470 @return: An ordered list of lines in the graph 471 @rtype: List 472 """ 473 lines = [] 474 vertices = set(self._ne.keys()) 475 while vertices: 476 vertex1 = vertices.pop() 477 for vertex2 in self._ne[vertex1] & vertices: 478 if vertex1 < vertex2: 479 lines.append((vertex1,vertex2)) 480 else: 481 lines.append((vertex2,vertex1)) 482 return lines

483

484 - def moralise(self):

485 """Return a moralised version of the graph 486 487 All parents are married, and directions are dropped. 488 The moral graph will share its vertex co-ordinates, if any, with C{self} 489 @return: The moralised graph 490 @rtype: L{UGraph} object 491 """ 492 markov = UGraph(self.vertexlist(),lines=self.lines(),vertex_positions=self._vertex_positions) 493 for child, parents in self._pa.items(): 494 for parent in parents: 495 markov.put_line(child,parent) 496 markov.complete(parents) 497 return markov

498 499

500 - def neighbours(self,vertex):

501 """Return the set (not a copy) of neighbours of a vertex 502 503 Neighbours are connected by undirected edges (lines) 504 @return: Neighbours of C{vertex} 505 @rtype: Set 506 """ 507 return self._ne[vertex]

508

509 - def orphanlist(self):

510 """Return a list containing all nodes with no parents 511 512 @return: Nodes with no parents 513 @rtype: List 514 """ 515 orphanlist = [] 516 for child, parents in self._pa.items(): 517 if not parents: 518 orphanlist.append(child) 519 return orphanlist

520

521 - def parent(self,vertex):

522 """Return an arbitrary parent of vertex 523 524 @return: A vertex which is a parent of C{vertex} or None 525 if it has no parents 526 @rtype: An immutable type (typically a String) 527 """ 528 for parent in self._pa[vertex]: 529 return parent

530

531 - def num_parents(self,vertex):

532 """Return the number of parents of vertex 533 534 @return: The number of parents of C{vertex} 535 @rtype: Integer 536 @raise KeyError: If C{vertex} is not in the graph. 537 """ 538 return len(self._pa[vertex])

539

540 - def num_parentsets(self):

541 """Iterate over the number of parents of vertices 542 543 (In no particular order) 544 """ 545 for ps in self._pa.values(): 546 yield len(ps)

547

548 - def parents(self,vertex):

549 """Return (a copy of) the parents of vertex 550 551 @return: The parents of C{vertex} 552 @rtype: Set 553 @raise KeyError: If C{vertex} is not in the graph. 554 """ 555 return self._pa[vertex].copy()

556

557 - def parentsets(self):

558 """Iterate over (copies of) all parent sets 559 """ 560 for ps in self._pa.values(): 561 yield ps.copy()

562

563 - def paths(self,vertex):

564 """Iterates over paths starting with C{vertex} 565 566 Each path is actually a tuple C{path_set,path} 567 where C{path_set} is the set of all vertices in the 568 path, and C{path} is a list representing the path itself 569 570 @param vertex: Vertex from which all paths start 571 @type vertex: Immutable 572 @return: Generator of paths 573 @rtype: Generator iterator 574 """ 575 path = (set([vertex]),[vertex]) 576 yield path 577 paths = [path] 578 while paths: 579 new_paths = [] 580 for new_path in self.extend_paths(paths): 581 new_paths.append(new_path) 582 yield new_path 583 paths = new_paths

584

585 - def put_vertex(self,vertex):

586 '''Adds a vertex to a graph or does nothing if it already exists 587 588 @param vertex: The vertex to add 589 @type vertex: Immutable type 590 ''' 591 if vertex not in self._pa: 592 for dkt in (self._pa, self._ch, self._ne): 593 dkt[vertex] = set()

594 595

596 - def reinit(self,vertices,arrows,lines,vertex_positions):

597 """(Re-)initialise a graph 598 599 Pre-existing state will be deleted. 600 @param vertices: The vertices of the graph 601 @type vertices: An iterator/sequence over immutable types 602 @param arrows: The arrows of the graph 603 @type arrows: An iterator/sequence over pairs (of vertices). 604 Each pair is a sequence of length 2. 605 @param lines: The lines of the graph 606 @type lines: An iterator/sequence over pairs (of vertices). 607 Each pair is a sequence of length 2. 608 @param vertex_positions: A mapping from vertices to canvas 609 co-ordinates 610 @type vertex_positions: Dictionary 611 @raise KeyError: If C{arrows} or C{lines} contains a vertex not included in 612 C{vertices} 613 """ 614 self._pa = {} 615 self._ch = {} 616 self._ne = {} 617 self.add_vertices(vertices) 618 if arrows: 619 self.add_arrows(arrows) 620 if lines: 621 self.add_lines(lines) 622 self._vertex_positions = vertex_positions

623

624 - def remove_vertex(self,vertex):

625 """Remove a vertex 626 627 @param vertex: Vertex to be removed 628 @type vertex: Immutable 629 @raise KeyError: If C{vertex} is not in the graph 630 """ 631 for parent in self._pa[vertex]: 632 self._ch[parent].remove(vertex) 633 for child in self._ch[vertex]: 634 self._pa[child].remove(vertex) 635 for nbr in self._ne[vertex]: 636 self._ne[nbr].remove(vertex) 637 del self._pa[vertex] 638 del self._ch[vertex] 639 del self._ne[vertex] 640 try: 641 del self._vertex_positions[vertex] 642 except KeyError: 643 pass

644

645 - def set_vertex_positions(self,coords):

646 """ 647 Position each vertex according to the co-ordinates in C{coords} 648 649 @param coords: A dictionary mapping some (maybe all) vertices to a co-ordinate for display 650 @type coords: Dictionary 651 """ 652 self._vertex_positions.update(coords)

653

654 - def shd(self, b):

655 """Structural Hamming distance to graph b from C{self} 656 657 +1 for a missing edge (directed or not) 658 +1 for an incorrectly oriented edge 659 +1 for an extra edge (directed or not) 660 661 Only works on simple graphs (those without multiple connections between vertices) 662 663 @param b: Graph to compare to C{self} 664 @type b: L{Graph} 665 @return: Structural Hamming distance to graph b from C{self} 666 @rtype: Int 667 """ 668 if self.vertices() != b.vertices(): 669 raise ValueError('Graphs must have the same vertex sets') 670 671 d = 0 672 vertices = self._pa.keys() 673 for i, v in enumerate(vertices): 674 for w in vertices[i+1:]: 675 if w in self._pa[v]: 676 if w not in b._pa[v]: 677 d += 1 678 elif w in self._ch[v]: 679 if w not in b._ch[v]: 680 d += 1 681 elif w in self._ne[v]: 682 if w not in b._ne[v]: 683 d += 1 684 elif (w in b._pa[v]) or (w in b._ch[v]) or (w in b._ne[v]): 685 d += 1 686 return d

687 688 689 690

691 - def is_subset_of_parents(self,child,vertices):

692 """Return whether C{vertices} is a subset of the parents of C{child} 693 694 @param child: Child vertex 695 @type child: Immutable 696 @param vertices: Set of vertices 697 @type vertices: Iterable 698 @return: Whether C{vertices} is a subset of C{child}'s parents 699 @rtype: Boolean 700 @raise KeyError: If C{child} is not a vertex 701 """ 702 703 return self._pa[child].issuperset(vertices)

704 705

706 - def is_superset_of_parents(self,child,vertices):

707 """Return whether C{vertices} is a superset of the parents of C{child} 708 709 @param child: Child vertex 710 @type child: Immutable 711 @param vertices: Set of vertices 712 @type vertices: Iterable 713 @return: Whether C{vertices} is a superset of C{child}'s parents 714 @rtype: Boolean 715 @raise KeyError: If C{child} is not a vertex 716 """ 717 718 return self._pa[child].issubset(vertices)

719

720 - def vertex_positions(self):

721 """ 722 Return a dictionary mapping each vertex to a co-ordinate for display 723 724 @return: A dictionary mapping some (maybe all) vertices to a co-ordinate for display 725 @rtype: Dictionary 726 """ 727 return self._vertex_positions.copy()

728

729 - def vertexlist(self):

730 """Returns a list of the vertices in the graph 731 732 @return: A list of the vertices in the graph 733 @rtype: List 734 """ 735 return self._pa.keys()

736

737 - def vertices(self):

738 """Returns the set of vertices in the graph 739 740 Can be altered without affecting C{self} 741 @return: The set of vertices in the graph 742 @rtype: Set 743 """ 744 return set(self._pa)

745

746 - def _gui_help(self):

747 """Display help for editing graphs in a top-level window 748 """ 749 top = Tkinter.Toplevel() 750 top.title('Graph editing help') 751 Tkinter.Label(top,text=self._edit_help_msg,justify=Tkinter.LEFT).pack()

752 753 _edit_help_msg = """ 754 Select an object with the left mouse button. 755 Clicking on a node with the right button will draw a 756 line to the selected node (if any). 757 Clicking on a node with the middle button will draw an 758 arrow to the selected node (if any). 759 760 You will be prevented from saving a graph with an illegal edge 761 (e.g. an arrow in an undirected graph). 762 763 'Reset': Return the canvas to its original state 764 'Delete': Delete the selected object (node or edge) 765 'Save': Save the graph, but do not remove the canvas 766 'Done': Save the graph removing canvas and these buttons, but leaving the parent 767 'Quit': Save the graph and destroy the parent window 768 'Help': Generate this message 769 """

770

771 772 773 -class _AbsMixedGraph(Incidence):

774 """Abstract class containing methods which are appropriate only for 775 graphs where both lines and arrows are allowed. 776 """ 777

778 - def put_edge(self,frm,to):

779 """Put an edge (in the mathematical sense) 780 781 @param frm: One of the vertices connected by the edge 782 @type frm: Immutable type 783 @param to: The other vertex connected by the edge 784 @type to: Immutable type 785 @raise KeyError: If either vertex does not exist 786 """ 787 if frm in self._ch[to]: 788 self.put_line(frm,to) 789 else: 790 self.put_arrow(frm,to)

791

792 793 794 795 -class _AbsUGraph(Incidence):

796 """Abstract class containing methods which are appropriate only for 797 graphs where lines are allowed. 798 799 @cvar _edit_help_msg: Help message for editing graphs 800 @type _edit_help_msg: String 801 """ 802

803 - def add_clique(self,vertices):

804 """Add a clique with the specified vertices to the graph 805 806 Vertices may include new vertices. All vertices will be connected 807 by undirected edges. 808 @param vertices: Vertices to pairwise connect 809 @type vertices: Iterable 810 """ 811 for vertex in vertices: 812 try: 813 self.add_vertex(vertex) 814 except ExistingVertexError: 815 pass 816 self.complete(vertices)

817 818

819 - def add_line(self,frm,to):

820 """Add a line (undirected edge) between two 821 existing vertices 822 823 @param frm: One of the vertices connected by the line 824 @type frm: Any immutable type 825 @param to: The other vertex connected by the line 826 @type to: Any immutable type 827 @raise KeyError: If either vertex does not exist 828 """ 829 self._ne[frm].add(to) 830 self._ne[to].add(frm)

831

832 - def add_lines(self,lines):

833 """Add a collection of lines to the graph 834 835 @param lines: The lines to add 836 @type lines: An iterator over pairs of vertices. 837 Each pair is a sequence of length 2 838 @raise KeyError: If a vertex does not exist 839 """ 840 for line in lines: 841 self.add_line(line[0],line[1])

842

843 - def complete(self,vertices):

844 '''Pairwise connects all C{vertices} by undirected edges 845 846 Any existing directed edges are removed 847 @param vertices: Vertices to pairwise connect 848 @type vertices: Iterable 849 @raise KeyError: If a vertex does not exist 850 ''' 851 if not vertices: 852 return 853 vs = list(vertices) 854 vertex1 = vs.pop() 855 while vs: 856 for vertex2 in vs: 857 self.put_line(vertex1,vertex2) 858 vertex1 = vs.pop()

859

860 - def put_line(self,frm,to):

861 """Put a line (undirected edge) between two 862 existing vertices 863 864 Any pre-existing arrow between C{frm} and C{to} in either 865 direction will be deleted. 866 @param frm: One of the vertices connected by the line 867 @type frm: Immutable type 868 @param to: The other vertex connected by the line 869 @type to: Immutable type 870 @raise KeyError: If either vertex does not exist 871 """ 872 self._ne[frm].add(to) 873 self._ne[to].add(frm) 874 self.discard_arrow(frm,to) 875 self.discard_arrow(to,frm)

876

877 - def put_lines(self,lines):

878 """Add a collection of lines to the graph 879 880 Any pre-existing arrows in either 881 direction will be deleted. 882 @param lines: The lines to add 883 @type lines: An iterator over pairs of vertices. 884 Each pair is a sequence of length 2 885 @raise KeyError: If a vertex does not exist 886 """ 887 for line in lines: 888 self.put_line(line[0],line[1])

889

890 - def remove_line(self,frm,to):

891 """Remove a line from the graph 892 893 @param frm: One of the vertices connected by the line 894 @type frm: Immutable type 895 @param to: The other vertex connected by the line 896 @type to: Immutable type 897 @raise KeyError: If either vertex does not exist 898 @raise KeyError: If the line is not there 899 """ 900 self._ne[frm].remove(to) 901 self._ne[to].remove(frm)

902

903 904 -class Graph(_AbsGraph,_AbsDiGraph,_AbsUGraph,_AbsMixedGraph):

905 """Unrestricted graphs""" 906 pass

907

908 909 -class DiGraph(_AbsGraph,_AbsDiGraph):

910 """Graphs with only directed edges (i.e. arrows) 911 912 A graph with A->B and B<-A is not allowed, since this produces an 913 undirected edge. 914 """ 915

916 - def __init__(self,vertices=(),arrows=(),vertex_positions=None):

917 _AbsGraph.__init__(self,vertices,arrows,(),vertex_positions)

918 919

920 - def __repr__(self):

921 return '%s(%s,%s,%s)' % ( 922 self.__class__.__name__, 923 sorted(self.vertexlist()), 924 sorted(self.arrows()), 925 self._vertex_positions)

926

927 - def ancestors(self,vertex):

928 """Returns the set of all ancestors of C{vertex}. 929 @param vertex: A vertex in the graph 930 @type vertex: Immutable 931 @return: ancestors of C{vertex} 932 @rtype: frozenset of vertices 933 """ 934 ancestors = set() 935 self._ancestors(vertex,ancestors) 936 return frozenset(ancestors)

937

938 - def connect(self,vertex,vertices):

939 """Iterates over digraphs produced by making C{vertex} a parent 940 to subsets of C{vertices} 941 942 @param vertex: Parent vertex 943 @type vertex: Immutable 944 @param vertices: Potential children 945 @type vertices: Sequence 946 @return: Generator of digraphs 947 @rtype: Generator iterator 948 """ 949 if vertices: 950 first = vertices[0] 951 for adg in self.connect(vertex,vertices[1:]): 952 yield adg 953 adg.add_arrow(vertex,first) 954 yield adg 955 adg.remove_arrow(vertex,first) 956 else: 957 yield self

958 959

960 - def descendants(self,vertex):

961 """Returns the set of all descendants of C{vertex}. 962 @param vertex: A vertex in the graph 963 @type vertex: Immutable 964 @return: descendants of C{vertex} 965 @rtype: frozenset of vertices 966 """ 967 descendants = set() 968 self._descendants(vertex,descendants) 969 return frozenset(descendants)

970

971 - def dfsvisit(self,vertex,visited,order):

972 """Visit unvisited vertices in depth-first fashion and append 973 them to a topological ordering of vertices 974 975 @param vertex: First vertex to visit 976 @type vertex: Immutable type (typically String) 977 @param visited: Nodes already visited 978 @type visited: Set 979 @param order: Topological ordering of vertices 980 @type order: List 981 """ 982 for parent in self._pa[vertex]: 983 if parent not in visited: 984 self.dfsvisit(parent,visited,order) 985 visited.add(vertex) 986 order.append(vertex)

987 988

989 - def enumerate_cycles(self,lim):

990 """Enumerates all cycles in a digraph 991 of length at most C{lim} 992 993 Ref:: 994 995 996 E{@}article{tarjan:211, 997 author = {Robert Tarjan}, 998 title = {Enumeration of the Elementary Circuits of a Directed Graph}, 999 publisher = {SIAM}, 1000 year = {1973}, 1001 journal = {SIAM Journal on Computing}, 1002 volume = {2}, 1003 number = {3}, 1004 pages = {211-216}, 1005 keywords = {algorithm; backtracking; circuit; cycle; digraph; graph}, 1006 url = {http://link.aip.org/link/?SMJ/2/211/1}, 1007 doi = {10.1137/0202017} 1008 } 1009 1010 E{@}TechReport{tarjan72:_enumer, 1011 author = {Robert Tarjan}, 1012 title = {Enumeration of the elementary circuits of a directed graph}, 1013 institution = {Cornell University}, 1014 year = 1972, 1015 number = {72-145}, 1016 address = {Ithaca, NY}, 1017 month = {September} 1018 } 1019 1020 Time bound is O((V+E)(C+1)) where C is the (potentially large) 1021 number of cycles. 1022 1023 @return: Yields all cycles in the digraph 1024 @rtype: iterator 1025 """ 1026 for v in sorted(self._pa): 1027 for cycle in self._tarjan_backtrack(v,v,set(),[],[],lim-1): 1028 yield cycle

1029

1030 - def essential_graph(self):

1031 """Return the essential graph of C{self} 1032 1033 Uses Chickering's algorithm 1034 """ 1035 # ORDER-EDGES 1036 order = self.topological_order() 1037 order_map = dict(zip(order,range(len(order)))) 1038 ordered_edges = [] 1039 for y_node in order: 1040 y_parents_plus = [(order_map[x_node],x_node) for x_node in self.parents(y_node)] 1041 y_parents_plus.sort(reverse=True) 1042 for x_node_plus in y_parents_plus: 1043 ordered_edges.append((x_node_plus[1],y_node)) 1044 1045 # LABEL-EDGES 1046 essential_graph = Graph() 1047 essential_graph.add_vertices(self.vertices()) 1048 def known(x_node,y_node): 1049 return x_node in essential_graph.parents(y_node) or \ 1050 x_node in essential_graph.neighbours(y_node)

1051 for (x_node,y_node) in ordered_edges: 1052 if known(x_node,y_node): 1053 continue 1054 y_parents = self.parents(y_node) 1055 for w_node in essential_graph.parents(x_node): 1056 if w_node not in y_parents: 1057 for y_parent in y_parents: 1058 essential_graph.add_arrow(y_parent,y_node) 1059 break 1060 else: 1061 essential_graph.add_arrow(w_node,y_node) 1062 else: 1063 for z_node in y_parents: 1064 if z_node != x_node and z_node not in self.parents(x_node): 1065 method = essential_graph.add_arrow 1066 break 1067 else: 1068 method = essential_graph.add_line 1069 for y_parent in y_parents: 1070 if not known(y_parent,y_node): 1071 method(y_parent,y_node) 1072 return essential_graph

1073 1074 1075 @classmethod 1076

1077 - def families(self):

1078 for v, pa in self._pa.items(): 1079 yield v, frozenset(pa)

1080 1081

1082 - def generate_from_vertices(cls,vertices):

1083 adg = cls(vertices) 1084 for gen_adg in adg.generate(vertices): 1085 yield gen_adg

1086

1087 - def generate(self,vertices):

1088 """Generate digraphs which respect the order of C{vertices} 1089 1090 Generates all digraphs produced by adding arrows to C{self} which 1091 are between vertices in C{vertices} and which respect the order of vertices 1092 in C{vertices}. 1093 1094 @param vertices: Ordered vertices 1095 @type vertices: Tuple 1096 @return: Generator of digraphs which respect the order of C{vertices} 1097 @rtype: Generator iterator 1098 """ 1099 if vertices: 1100 rest = vertices[1:] 1101 for adg in self.generate(rest): 1102 for adg2 in adg.connect(vertices[0],rest): 1103 yield adg2 1104 else: 1105 yield self

1106

1107 - def minimal_cycles(self,source):

1108 """Return all minimal cycles involving C{source}. 1109 1110 @param source: Source vertex 1111 @type source: Immutable 1112 @return: Minimal cycles 1113 @rtype: List of tuples of vertices 1114 """ 1115 cycles = [] 1116 for child in self._ch[source]: 1117 self._minimaldfs(child,source,(),cycles) 1118 return cycles

1119 1120

1121 - def minimal_paths(self,source,sink):

1122 """Return all minimal (non-direct) paths from C{source} to C{sink}. 1123 1124 A path C{source,v1,v2,.. sink} is minimal if there are no non-consecutive 1125 vertices joined by an edge in C{self}, (with the possible exception of source to sink) 1126 and all vertices are distinct. 1127 (There are no short-cuts provided by edges). 1128 @param source: Source vertex 1129 @type source: Immutable 1130 @param sink: Sink vertex 1131 @type sink: Immutable 1132 @return: Minimal paths 1133 @rtype: List of lists of vertices 1134 """ 1135 paths = [] 1136 self._minimaldfs(source,sink,(),paths) 1137 return paths

1138

1139 - def topological_order(self):

1140 """Return a topological ordering of the vertices 1141 1142 Children come after their parents in the ordering 1143 @return: A topological ordering of the vertices 1144 @rtype: List 1145 """ 1146 visited = set() 1147 order = [] 1148 for vertex in self.vertexlist(): 1149 if vertex not in visited: 1150 self.dfsvisit(vertex,visited,order) 1151 return order

1152

1153 - def _ancestors(self,vertex,ancestors):

1154 """Add ancestors of C{vertex} not in C{ancestors} to 1155 C{ancestors} 1156 """ 1157 for pa in self._pa[vertex] - ancestors: 1158 ancestors.add(pa) 1159 self._ancestors(pa,ancestors)

1160

1161 - def _descendants(self,vertex,descendants):

1162 """Add descendants of C{vertex} not already in C{descendants} to 1163 C{descendants} 1164 """ 1165 for pa in self._pa[vertex] - descendants: 1166 descendants.add(pa) 1167 self._descendants(pa,descendants)

1168

1169 - def _minimaldfs(self,current,sink,before_current,paths):

1170 """current is last vertex on current path 1171 before_current is all previous vertices 1172 """ 1173 for child in self._ch[current]: 1174 # short cuts from source to sink do not count 1175 for i, v in enumerate(before_current): 1176 if v == child or (child in self._ch[v] and (i>0 or child != sink)): 1177 break #this child no good 1178 else: 1179 if child == sink: 1180 paths.append(before_current + (current,sink)) 1181 else: 1182 self._minimaldfs(child,sink,before_current+(current,),paths)

1183 1184 1185 1186 1187

1188 - def _tarjan_backtrack(self,start,v,marked,marked_stack,point_stack,lim):

1189 if len(point_stack) <= lim: 1190 f = False 1191 point_stack.append(v) 1192 marked.add(v) 1193 marked_stack.append(v) 1194 for w in self._ch[v]: 1195 1196 if w < start: 1197 continue 1198 elif w == start: 1199 yield tuple(point_stack+[start]) 1200 f = True 1201 elif w not in marked: 1202 g = False 1203 for cycle in self._tarjan_backtrack(start,w,marked,marked_stack,point_stack,lim): 1204 yield cycle 1205 g = True 1206 f = f or g 1207 if f: 1208 while marked_stack[-1] != v: 1209 u = marked_stack.pop() 1210 marked.remove(u) 1211 marked_stack.pop() # remove v 1212 marked.remove(v) 1213 point_stack.pop() # remove v

1214

1215 -class DiForest(DiGraph):

1216 """Undirected graphs where each connectivity component is a tree 1217 """ 1218 pass

1219

1220 -class ADG(DiGraph):

1221 """Acyclic directed graphs 1222 1223 @ivar _an: Maps each vertex to its ancestors 1224 @type _an: Dictionary 1225 @ivar _de: Maps each vertex to its descendants 1226 @type _de: Dictionary 1227 """ 1228 1229

1230 - def __init__(self,vertices=(),arrows=(),vertex_positions=None):

1231 self._an = {} 1232 self._de = {} 1233 DiGraph.__init__(self,vertices,arrows,vertex_positions)

1234

1235 - def ancestor(self,an,de):

1236 """Return whether C{an} is an ancestor of C{de} 1237 1238 @param an: Potential ancestor 1239 @type an: Immutable 1240 @param de: Potential descendant 1241 @type de: Immutable 1242 @return: Whether C{an} is an ancestor of C{de} 1243 @rtype: Boolean 1244 """ 1245 return an in self._an[de]

1246

1247 - def ancestors(self, vertex):

1248 return frozenset(self._an[vertex])

1249

1250 - def ancestral_adg(self, vertices):

1251 """Return the subgraph of the vertices in the small ancestral set 1252 of C{vertices}""" 1253 # find the smallest ancestral set of the vertices 1254 an = set(vertices) 1255 for vertex in vertices: 1256 an |= self._an[vertex] 1257 1258 # find all arrows among vertices in the ancestral set 1259 arr = [] 1260 for vertex in an: 1261 for ch in self._ch[vertex] & an: 1262 arr.append((vertex,ch)) 1263 for pa in self._pa[vertex] & an: 1264 arr.append((pa,vertex)) 1265 1266 return ADG(vertices=an, arrows=arr)

1267 1268

1269 - def descendants(self, vertex):

1270 return frozenset(self._de[vertex])

1271

1272 - def add_vertex(self,vertex):

1273 DiGraph.add_vertex(self,vertex) 1274 self._an[vertex] = set() 1275 self._de[vertex] = set()

1276

1277 - def add_arrow(self,frm,to):

1278 """Add an arrow (directed edge) between two 1279 existing vertices 1280 1281 @param frm: One of the vertices connected by the line 1282 @type frm: Immutable type 1283 @param to: The other vertex connected by the line 1284 @type to: Immutable type 1285 @raise KeyError: If either vertex does not exist 1286 @raise DirectedCycleError: If the arrow would create a directed cycle 1287 """ 1288 if to in self._an[frm]: 1289 raise DirectedCycleError 1290 DiGraph.add_arrow(self,frm,to) 1291 1292 #update the ancestors of to and to's descendants 1293 self._an[to].add(frm) 1294 self._an[to].update(self._an[frm]) 1295 for de in self._de[to]: 1296 self._an[de].add(frm) 1297 self._an[de].update(self._an[frm]) 1298 1299 #update the descendants of frm and frm's ancestors 1300 self._de[frm].add(to) 1301 self._de[frm].update(self._de[to]) 1302 for an in self._an[frm]: 1303 self._de[an].add(to) 1304 self._de[an].update(self._de[to])

1305

1306 - def connect(self,vertex,vertices):

1307 """Iterates over all the the ADGs produced by connecting C{vertex} to 1308 C{vertices} 1309 1310 For each vertex in C{vertices}, C{vertex} can be 1)unconnected, 2)a parent 1311 or 3) a child. 1312 Assumes C{vertex} initially not connected to any C{vertices} in C{self} 1313 """ 1314 if vertices: 1315 first = vertices[0] 1316 for adg in self.connect(vertex,vertices[1:]): 1317 1318 # unconnected 1319 yield adg 1320 1321 # parent 1322 try: 1323 adg.add_arrow(vertex,first) 1324 yield adg 1325 adg.remove_arrow(vertex,first) 1326 except DirectedCycleError: 1327 pass 1328 1329 # child 1330 try: 1331 adg.add_arrow(first,vertex) 1332 yield adg 1333 adg.remove_arrow(first,vertex) 1334 except DirectedCycleError: 1335 pass 1336 else: 1337 yield self

1338

1339 - def connect(self,vertex,vertices):

1340 """Iterates over all the the ADGs produced by connecting C{vertex} to 1341 C{vertices} 1342 1343 For each vertex in C{vertices}, C{vertex} can be 1)unconnected, 2)a parent 1344 or 3) a child. 1345 Assumes C{vertex} initially not connected to any C{vertices} in C{self} 1346 """ 1347 if vertices: 1348 first = vertices[0] 1349 for adg in self.connect(vertex,vertices[1:]): 1350 1351 # unconnected 1352 yield adg 1353 1354 # parent 1355 try: 1356 adg.add_arrow(vertex,first) 1357 yield adg 1358 adg.remove_arrow(vertex,first) 1359 except DirectedCycleError: 1360 pass 1361 1362 # child 1363 try: 1364 adg.add_arrow(first,vertex) 1365 yield adg 1366 adg.remove_arrow(first,vertex) 1367 except DirectedCycleError: 1368 pass 1369 else: 1370 yield self

1371 1372

1373 - def connect2(self,vertex,vertices):

1374 """Iterates over all the the ADGs produced by connecting C{vertex} to 1375 C{vertices} 1376 1377 Makes copies to avoid expensive arrow removal 1378 1379 For each vertex in C{vertices}, C{vertex} can be 1)unconnected, 2)a parent 1380 or 3) a child. 1381 Assumes C{vertex} initially not connected to any C{vertices} in C{self} 1382 """ 1383 if vertices: 1384 first = vertices[0] 1385 for adg in self.connect2(vertex,vertices[1:]): 1386 1387 # unconnected 1388 yield adg 1389 1390 # parent 1391 try: 1392 cp = adg.copy() 1393 cp.add_arrow(vertex,first) 1394 yield cp 1395 except DirectedCycleError: 1396 pass 1397 1398 # child 1399 try: 1400 cp = adg.copy() 1401 cp.add_arrow(first,vertex) 1402 yield cp 1403 except DirectedCycleError: 1404 pass 1405 else: 1406 yield self.copy()

1407 1408

1409 - def encoding_family(self,inv_atom_ids,predicate='has_parents'):

1410 """Return the numbers encoding C{self} 1411 1412 @param inv_atom_ids: Mapping from logical atoms to numbers 1413 @type inv_atom_ids: Dictionary 1414 @param predicate: The predicate symbol used for the relation beween a child 1415 and its parent set 1416 @type predicate: String 1417 @return: The numbers encoding C{self}, not in any particular order 1418 @rtype: List (of positive integers) 1419 @raise KeyError: if a family is missing 1420 """ 1421 return [inv_atom_ids[(predicate,child,frozenset(parents))] for child,parents in self._pa.items()]

1422 1423

1424 - def remove_arrow(self,frm,to):

1425 """ 1426 @todo: Needs improving 1427 """ 1428 DiGraph.remove_arrow(self,frm,to) 1429 1430 # expensive 1431 for an in self._an[frm]: 1432 for de in self._de[to]: 1433 if not self._ancestor(an,de): 1434 self._an[de].remove(an) 1435 self._de[an].remove(de) 1436 if not self._ancestor(an,to): 1437 self._an[to].remove(an) 1438 self._de[an].remove(to) 1439 for de in self._de[to]: 1440 if not self._ancestor(frm,de): 1441 self._an[de].remove(frm) 1442 self._de[frm].remove(de) 1443 if not self._ancestor(frm,to): 1444 self._an[to].remove(frm) 1445 self._de[frm].remove(to)

1446

1447 - def remove_vertex(self,vertex):

1448 1449 # very inefficient 1450 for child in self._ch[vertex].copy(): 1451 self.remove_arrow(vertex,child) 1452 for parent in self._pa[vertex].copy(): 1453 self.remove_arrow(parent,vertex) 1454 del self._pa[vertex] 1455 del self._ch[vertex] 1456 del self._ne[vertex] 1457 del self._an[vertex] 1458 del self._de[vertex]

1459 1460

1461 - def _ancestor(self,an,de):

1462 """True if C{an} is an ancestor of C{de} 1463 1464 Does check without using the _an or _de dictionaries 1465 So can be used for updating these dictionaries 1466 """ 1467 for pa in self._pa[de]: 1468 if pa == an or self._ancestor(an,pa): 1469 return True 1470 return False

1471

1472 1473 1474 -class UGraph(_AbsGraph,_AbsUGraph):

1475 """Graphs with only undirected edges (i.e. lines) 1476 """ 1477

1478 - def __init__(self,vertices=(),lines=(),vertex_positions=None):

1479 _AbsGraph.__init__(self,vertices,(),lines,vertex_positions)

1480 1481

1482 - def __repr__(self):

1483 return '%s(%s,%s)' % ( 1484 self.__class__.__name__, 1485 sorted(self.vertexlist()), 1486 sorted(self.lines()))

1487

1488 - def extend_compsub(self,compsub,candidates,notset,hypergraph):

1489 """Extend a complete subset of the graph to find cliques 1490 1491 This is for Version 1 of Bron and Kerbosch's algorithm. Version 2 is better, 1492 but more complex. 1493 1494 Checks whether C{candidates} includes all neighbours of some element of C{notset} 1495 in which case no clique can be formed:: 1496 1497 @Article{bron73:_algor, 1498 author = {Bron, C. and Kerbosch, J.}, 1499 title = {Algorithm 457: finding all cliques of an undirected graph}, 1500 journal = {Communications of the {ACM}}, 1501 year = 1973, 1502 volume = 16, 1503 pages = {575--577} 1504 } 1505 1506 @param compsub: The complete set of vertices to be extended 1507 @type compsub: Set 1508 @param candidates: Candidates available to extend C{compsub}, 1509 @type candidates: Set 1510 @param notset: Vertices that have previously served as candidates and which 1511 are now explicitly excluded 1512 @type notset: Set 1513 @param hypergraph: The graphical hypergraph to which any found cliques will be added. 1514 @type hypergraph: L{ReducedGraphicalHypergraph} 1515 """ 1516 # 1-3: This is the branch and bound step. 1517 # Note that notitem will never be removed at line 8 1518 # so notset will never become empty 1519 # 7: For a new clique we need at least one member which does 1520 # not neighbour previously processed candidates 1521 # if candidate is one of these, then new_notset (line 8) will be 1522 # empty 1523 1524 for notitem in notset: # 1 1525 if candidates <= self._ne[notitem]: # 2 1526 return # 3 1527 while candidates: # 4 1528 candidate = candidates.pop() # 5 1529 compsub.add(candidate) # 6 1530 new_candidates = candidates & self._ne[candidate] # 7 1531 new_notset = notset & self._ne[candidate] # 8 1532 self.extend_compsub(compsub,new_candidates,new_notset,hypergraph) 1533 compsub.remove(candidate) 1534 notset.add(candidate) 1535 if not notset: 1536 hypergraph.add_hyperedge(compsub)

1537

1538 - def twdp(self,up=None,monitor=False):

1539 """Exact treewidth computation from Bodlaender et al 1540 """ 1541 v = frozenset(self.vertices()) 1542 n = len(v) 1543 if up is None: 1544 up = n - 1 1545 before = [((),-1)] 1546 found = False 1547 for i in range(1,n+1): 1548 now = {} 1549 for s, r in before: 1550 if found: 1551 if r >= up: 1552 continue 1553 elif r > up: 1554 continue 1555 ss = set(s) 1556 for x in v - ss: 1557 1558 todo = set([x]) 1559 done = set([x]) 1560 while todo: 1561 new = set() 1562 for vertex in todo: 1563 new |= self._ne[vertex] 1564 new -= done 1565 todo = new & ss 1566 done |= new 1567 q = len(done - ss) - 1 1568 1569 r1 = max(r,q) 1570 if found: 1571 if r1 >= up: 1572 continue 1573 elif r1 > up: 1574 continue 1575 1576 key = frozenset(ss|set([x])) 1577 try: 1578 t = now[key][2] 1579 if r1 < t: 1580 now[key] = s,x,r1 1581 except KeyError: 1582 now[key] = s,x,r1 1583 if found: 1584 if n-i-1 < up: 1585 found = (s+((x),), r1) 1586 up = max(r1,n-i-1) 1587 elif n-i-1 <= up: 1588 found = (s+((x),), r1) 1589 up = max(r1,n-i-1) 1590 before = [(s+((x),), r1) for (s,x,r1) in now.values()] 1591 if monitor: 1592 print i, len(before) 1593 return found

1594

1595 - def gui_triangulate(self,parent,elimination_order, 1596 original_colour='black', 1597 eliminating_colour='red', 1598 uneliminated_neighbour_colour='green', 1599 eliminated_colour='grey', 1600 fill_in_colour='blue', 1601 width=400, 1602 height=350, 1603 **config):

1604 """Triangulate the graph using C{elimination_order} 1605 and display the process graphically. 1606 1607 Alters C{self} 1608 1609 @param parent: A widget in which the graph will be displayed 1610 @type parent: A suitable Tkinter object, eg a Frame. 1611 @param original_colour: Colour for uneliminated vertices not 1612 participating in an elimination 1613 @type original_colour: String 1614 @param eliminating_colour: Colour for the vertex being eliminated 1615 @type eliminating_colour: String 1616 @param uneliminated_neighbour_colour: Colour for uneliminated neighbours 1617 of the the vertex being eliminated 1618 @type uneliminated_neighbour_colour: String 1619 @param eliminated_colour: Colour for eliminated vertices 1620 @type eliminated_colour: String 1621 @param fill_in_colour: Colour for fill-in lines 1622 @type fill_in_colour: String 1623 @param elimination_order: The elimination order 1624 @type elimination_order: An iterator (typically a list) 1625 @param config: Configuration options for the GUI 1626 @type config: Various 1627 @return: The triangulated graph 1628 @rtype: Same class as C{self} 1629 """ 1630 gc = GraphCanvas(self,parent,edit=False, 1631 colour_user_actions=False, 1632 width=width,height=height,**config) 1633 gc.pack() 1634 bottom = Tkinter.Frame(parent) 1635 bottom.pack() 1636 labels = [] 1637 for vertex in elimination_order: 1638 label = Tkinter.Label(bottom,text=vertex) 1639 labels.append(label) 1640 label.pack(side=Tkinter.LEFT) 1641 eliminated = set() 1642 i = [0] 1643 def handler(self=self, elimination_order=elimination_order, 1644 eliminated=eliminated,gc=gc, 1645 original_colour=original_colour, 1646 eliminating_colour=eliminating_colour, 1647 uneliminated_neighbour_colour=uneliminated_neighbour_colour, 1648 eliminated_colour=eliminated_colour, 1649 fill_in_colour=fill_in_colour,i=i,labels=labels 1650 ): 1651 j=i[0] 1652 if j > 0: 1653 labels[j-1].config(fg=eliminated_colour) 1654 try: 1655 labels[j].config(fg=eliminating_colour) 1656 i[0]=j+1 1657 except IndexError: 1658 labels[j-1].config(fg=eliminated_colour) 1659 return self._gui_elim_one(elimination_order,eliminated,gc, 1660 original_colour,eliminating_colour, 1661 uneliminated_neighbour_colour, 1662 eliminated_colour,fill_in_colour)

1663 Tkinter.Button(bottom,text='Next',command=handler).pack()

1664 1665

1666 - def gui_maximum_cardinality_search( 1667 self,parent,choose=None,width=400,height=350,**config):

1668 1669 if choose is None: 1670 def choose(set): return set.pop() 1671 1672 vertices = self.vertices() # 1 1673 sets = [] # 2 1674 alpha = {} # 3 1675 alpha_inv = [] # 4 1676 cardinality = {} # 5 1677 for vertex in vertices: # 6 1678 cardinality[vertex] = 0 # 7 1679 sets.append(set()) # 8 1680 alpha_inv.append(None) # 9 1681 sets[0] = vertices #10 1682 j = [0] #12 1683 i = [len(vertices)-1] 1684 1685 gc = GraphCanvas(self,parent,edit=False, 1686 colour_user_actions=False, 1687 width=width,height=height,**config) 1688 gc.pack() 1689 bottom = Tkinter.Frame(parent) 1690 bottom.pack() 1691 label = Tkinter.Label(bottom,text=str(alpha_inv)) 1692 label.pack(side=Tkinter.LEFT) 1693 def handler(self=self,i=i,j=j,alpha=alpha,alpha_inv=alpha_inv, 1694 cardinality=cardinality,sets=sets,choose=choose): 1695 if not sets[j[0]]: 1696 return 1697 v=self._gui_maxcard_one(i,j,alpha,alpha_inv,cardinality,sets,choose) 1698 gc.vertex_config(v,fill='grey') 1699 label.config(text=str(alpha_inv))

1700 Tkinter.Button(bottom,text='Next',command=handler).pack() 1701

1702 - def hypergraph(self):

1703 """Return the clique hypergraph of an undirected graph 1704 1705 Uses Bron and Kerbosch algorithm, see L{extend_compsub} 1706 @return: The clique hypergraph of an undirected graph 1707 @rtype: L{ReducedGraphicalHypergraph} 1708 """ 1709 cliques = ReducedGraphicalHypergraph() 1710 self.extend_compsub(set([]),self.vertices(),set([]),cliques) 1711 return cliques 1712 1713 clique_hypergraph = hypergraph

1714

1715 - def is_triangulated(self):

1716 """Return whether the graph is triangulated 1717 1718 Uses L{maximum_cardinality_search}, see that method for acknowledgements 1719 1720 @return: Whether the graph is triangulated (aka 'decomposable', 'chordal') 1721 @rtype: Boolean 1722 """ 1723 return self.triangulate( 1724 self.maximum_cardinality_search()[0],zero_fillin_check=True)

1725 1726 is_chordal = is_triangulated 1727 1728 is_decomposable = is_triangulated 1729

1730 - def maximum_cardinality_search(self,choose=None):

1731 """Return maximum cardinality search 1732 1733 Ref:: 1734 1735 @Article{tarjan84:_simpl, 1736 author = {Robert E. Tarjan and Mihalis Yannakakis}, 1737 title = {Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, 1738 journal = {{SIAM} Journal of Computing}, 1739 year = 1984, 1740 volume = 13, 1741 number = 3, 1742 pages = {566--579}, 1743 month = {August} 1744 """ 1745 1746 # As Tarjan and Yannakakis put it the basic idea is: 1747 # "Number the vertices from n to 1 in decreasing order. As the next 1748 # vertex to number, select the vertex adjacent to the largest number 1749 # of previously numbered vertices, breaking ties arbitrarily". 1750 1751 # The following implements their algorithm, execpt that numbering is from 1752 # n-1 to 0, and the user can specify a tie-breaker (the 'choose' function) 1753 # if desired. 1754 1755 # Lines 1-12 are initialisation. The key data structure is the dictionary 1756 # 'cardinality' which throughout maps each unnumbered vertex to the number of 1757 # numbered vertices adjacent to it. The list 'sets' is such that sets[i] 1758 # is a set containing all unnumbered vertices with cardinality i. Initially no vertices 1759 # are numbered so all vertices have cardinality zero (lines 7 and 10). 1760 # alpha and alpha_inv will contain the vertex numbering on return. alpha maps 1761 # each vertex to its number, and alpha_inv is just the inverse mapping (see lines 1762 # 17 and 18). Eventually all the None values in alpha_inv (line 9) will be replaced 1763 # by the appropriate integers. j is the largest value such that sets[j] is non-empty. 1764 1765 # Line 9a adds a dummy empty set so that j in line 24 never causes an IndexError 1766 1767 # In the main loop (lines 13-26) we number vertices from i=n-1 down to i=0 1768 # (The 'range' function (13) generates a list with precisely this sequence of integers.) 1769 # The loop invariant is that 'cardinality', 'sets' and 'j' maintain the 1770 # properties described above. In particular, 1771 # sets[j] contains all unnumbered vertices with maximum cardinality. 1772 1773 # Line 14 assigns v to be a maximum cardinality vertex and removes it 1774 # from sets[j]. This assignment is then stored (lines 15,16) 1775 1776 # Now that v has been numbered the cardinalities of all its unnumbered 1777 # neighbours [given by the set self._ne[v].difference(alpha) in line 17 ] 1778 # need to be incremented. 1779 # Lines 17-22 update 'sets' and 'cardinality' accordingly. Lines 23-35 1780 # maintain the loop invariant for j 1781 1782 if choose is None: 1783 def choose(set): return set.pop() 1784 1785 vertices = self.vertices() # 1 1786 sets = [] # 2 1787 alpha = {} # 3 1788 alpha_inv = [] # 4 1789 cardinality = {} # 5 1790 for vertex in vertices: # 6 1791 cardinality[vertex] = 0 # 7 1792 sets.append(set()) # 8 1793 alpha_inv.append(None) # 9 1794 sets.append(set()) # 9a 1795 sets[0] = vertices #10 1796 j = 0 #12 1797 1798 for i in range(len(vertices)-1,-1,-1): # 13 1799 v = choose(sets[j]) # 14 1800 alpha[v] = i # 15 1801 alpha_inv[i] = v # 16 1802 for w in self._ne[v].difference(alpha): # 17 1803 card_w = cardinality[w] # 18 1804 sets[card_w].remove(w) # 19 1805 card_w += 1 # 20 1806 sets[card_w].add(w) # 21 1807 cardinality[w] = card_w # 22 1808 j += 1 # 23 1809 while j >= 0 and sets[j] == emptyset: # 24 1810 j -= 1 # 25 1811 return alpha, alpha_inv # 26

1812

1813 - def put_line(self,frm,to):

1814 """Add a line (undirected edge) to the graph between two 1815 existing vertices 1816 1817 @param frm: One of the vertices connected by the line 1818 @type frm: Immutable type 1819 @param to: The other vertex connected by the line 1820 @type to: Immutable type 1821 @raise KeyError: If either vertex does not exist 1822 """ 1823 self._ne[frm].add(to) 1824 self._ne[to].add(frm)

1825

1826 - def random_graph(self,n,m):

1827 n0 = len(self._ne) 1828 if sorted(self._ne) != range(n0): 1829 raise ValueError("Method only works on graphs with vertices named 0,1,..n") 1830 self.add_vertices(range(n0,n0+n)) 1831 for new_edge in random.sample(xrange(n*n),m): 1832 self.put_line(n0 + (new_edge/n), n0 + (new_edge%n)) 1833 return self

1834 1835 1836 # def junction_tree(self,elimination_order): 1837 # """Return a junction tree""" 1838 # old_cliques = {} 1839 # eliminated = set() 1840 # waiting = set() 1841 # forest = UForest() 1842 # for v in elimination_order: 1843 # message = self._ne[v] - eliminated 1844 # parents = old_cliques.get(v,set()) & waiting 1845 # for waiting_clique in parents: 1846 # if message <= waiting_clique: 1847 # v_clique = waiting_clique 1848 # parents.remove(v_clique) 1849 # break 1850 # else: 1851 # v_clique = frozenset(message | set([v])) 1852 # waiting.add(v_clique) 1853 # forest.add_vertex(v_clique) 1854 # self.complete(message) 1855 # for waiting_clique in parents: 1856 # forest.put_line(waiting_clique,v_clique) 1857 # waiting.remove(waiting_clique) 1858 # for var in message: 1859 # try: 1860 # old_cliques[var].add(v_clique) 1861 # except KeyError: 1862 # old_cliques[var] = set(v_clique) 1863 # eliminated.add(v) 1864 # return forest 1865 1866 1867 1868

1869 - def zero_fillin_check(self,elimination_order=None):

1870 if elimination_order is None: 1871 elimination_order = self.maximum_cardinality_search()[0] 1872 eliminated = set() 1873 for vertex in elimination_order: 1874 message = self._ne[vertex] - eliminated 1875 while message: 1876 nbr = message.pop() 1877 for other_nbr in message: 1878 if other_nbr not in self._ne[nbr]: 1879 return False 1880 eliminated.add(vertex) 1881 return self

1882

1883 - def triangulate2(self,elimination_order):

1884 """Triangulate the graph B{inefficiently!} using C{elimination_order} 1885 1886 Triangulates the graph by eliminating vertices in the order given by 1887 C{elimination_order}. When a vertex is eliminated all its uneliminated 1888 neighbours must be a complete set (all pairwise connected by edges). Extra edges 1889 are added, if necessary, to ensure this is the case. 1890 1891 'Eliminated' vertices are not actually deleted, just marked as 'eliminated', 1892 so you don't end up with an empty graph! 1893 1894 @param elimination_order: The elimination order 1895 @type elimination_order: An iterator (typically a list) 1896 """ 1897 eliminated = set() 1898 for vertex in elimination_order: 1899 message = self._ne[vertex] - eliminated 1900 self.complete(message) 1901 eliminated.add(vertex) 1902 return self

1903

1904 - def triangulate(self,elimination_order,zero_fillin_check=False,modify=True):

1905 """Triangulate the graph using C{elimination_order} 1906 1907 Alters C{self} by default 1908 1909 Ref:: 1910 1911 @Article{tarjan84:_simpl, 1912 author = {Robert E. Tarjan and Mihalis Yannakakis}, 1913 title = {Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, 1914 journal = {{SIAM} Journal of Computing}, 1915 year = 1984, 1916 volume = 13, 1917 number = 3, 1918 pages = {566--579}, 1919 month = {August} 1920 1921 @param elimination_order: The elimination order 1922 @type elimination_order: An iterator (typically a list) 1923 @param zero_fillin_check: If set the method returns whether C{elimination_order} is a zero 1924 fill-in and does not alter C{self} 1925 @type zero_fillin_check: Boolean 1926 @param modify: Whether to add the fill-in edges to C{self} 1927 @type modify: Boolean 1928 @return: (As long as C{zero_fillin_check=False}), the fill-in (added edges) produced by C{elimination_order} 1929 @rtype: (As long as C{zero_fillin_check=False}), the list of tuples, each tuple is an unordered pair of vertices 1930 """ 1931 # This algorithm exploits the notion of a vertex's 1932 # *follower*. The follower of vertex v is the earliest vertex 1933 # in the elimination order coming after v which is adjacent to 1934 # v in the elimination graph (i.e. the graph formed by adding 1935 # the fill-in edges). A vertex need not have a follower - the 1936 # last vertex never has one. 1937 1938 # Define f*(x) to be the {x, f(x), f(f(x)), ... }, ie the path 1939 # of followers starting with x. Theorem 3 of the above 1940 # reference establishes the following. If v comes before w in 1941 # the elimination ordering then there is a v-w edge in the 1942 # elimination graph if and only if there is a vertex x which 1943 # is (i) adjacent to w in the orginal graph and (ii) where v 1944 # is a member of f*(x) 1945 1946 # This result leads to the following algorithm. The vertices 1947 # are processed in order. For each vertex w the neighbours 1948 # which come before w are considered. For each of these 1949 # neighbours x, the vertices in f*(x) coming before w are 1950 # found and connected to w. 1951 1952 # A variant of this is implemented as follows. Dictionary f 1953 # stores the `follower' mapping and the list fill_in records 1954 # fill-in edges. They are initialised in lines 1 and 1955 # 2. Vertices w are considered according to the given order 1956 # (line 3). 1957 1958 # A dummy value of w for the follower of w is assigned (line 1959 # 4). self._ne[w] on line 5 is the set of neighbours of w. By 1960 # intersecting this with the dictionary f the variable 1961 # `earlier_neighbours' contains only neighbours of w earlier 1962 # in the elimination order. The set `done' (of which more 1963 # later) is these neighbours together with w. 1964 1965 # Each earlier neighbour x is considered in turn (line 7). If 1966 # the follower of x has yet to be found then f[x] in line 8 is 1967 # x otherwise it is the follower of x. In the latter case, the 1968 # chain of followers of x are considered (lines 9-13) until we 1969 # hit one that has already been `done'. Any vertex in such a 1970 # chain is a follower of an earlier neighbour of w which is 1971 # not itself an existing neighbour of w and so a fill-in edge 1972 # is needed (line 11). x at line 11 cannot be an existing 1973 # neighbour since all earlier neighbours are in the set `done' 1974 # and x is not (line 9) and all later neighbours cannot be 1975 # reached yet by a chain of followers. Note that the set 1976 # `done' also prevents revisiting sequences of followers due 1977 # to line 10. Lines 9a and 9b provide an early exit if all that 1978 # is required is a check for a zero fill-in. 1979 1980 # If the x at the end of one of these chains is found to 1981 # contain a dummy value for its follower this is replaced by 1982 # the true value - w - in lines 13-14. 1983 1984 # Lines 16-18 add the fill-in edges to the graph (if that is 1985 # required) and return the fillin-edges. Lines 14a and 14b return 1986 # the appropriate boolean value if a check is being done. 1987 1988 f = {} # 1 1989 fill_in = [] # 2 1990 for w in elimination_order: # 3 1991 f[w] = w # 4 1992 earlier_neighbours = self._ne[w].intersection(f) # 5 1993 done = set([w]) | earlier_neighbours # 6 1994 for x in earlier_neighbours: # 7 1995 x = f[x] # 8 1996 while x not in done: # 9 1997 if zero_fillin_check: # 9a 1998 return False # 9b 1999 done.add(x) # 10 2000 fill_in.append((x,w)) # 11 2001 x = f[x] # 12 2002 if f[x] == x: # 13 2003 f[x] = w # 14 2004 if zero_fillin_check: # 14a 2005 return True # 14b 2006 if modify: # 15 2007 self.put_lines(fill_in) # 16 2008 return fill_in # 17

2009 2010 # def triangulate(self,elimination_order): 2011 # """Tarjan and Yannakakis version 2012 # """ 2013 # f = {} 2014 # index = {} 2015 # new_edges = [] 2016 # for i, w in enumerate(elimination_order): 2017 # f[w] = w 2018 # index[w] = i 2019 # for v in self._ne[w].intersection(f): 2020 # x = v 2021 # while index[x] < i: 2022 # index[x] = i 2023 # if x not in self._ne[w]: 2024 # new_edges.append((x,w)) 2025 # x = f[x] 2026 # if f[x] == x: 2027 # f[x] = w 2028 # self.put_lines(new_edges) 2029 # return new_edges 2030 2031 2032

2033 - def _gui_elim_one(self,elimination_order,eliminated,gc, 2034 original_colour,eliminating_colour, 2035 uneliminated_neighbour_colour, 2036 eliminated_colour,fill_in_colour):

2037 if not elimination_order: 2038 for v in self.vertexlist(): 2039 gc.vertex_config(v,fill=eliminated_colour) 2040 return 2041 vertex = elimination_order.pop(0) 2042 message = self._ne[vertex] - eliminated 2043 for v in self.vertexlist(): 2044 if v == vertex: 2045 gc.vertex_config(v,fill=eliminating_colour) 2046 elif v in message: 2047 gc.vertex_config(v,fill=uneliminated_neighbour_colour) 2048 elif v in elimination_order: 2049 gc.vertex_config(v,fill=original_colour) 2050 else: 2051 gc.vertex_config(v,fill=eliminated_colour) 2052 msg = message.copy() 2053 while message: 2054 v1 = message.pop() 2055 for v2 in message - self._ne[v1]: 2056 gc.drawarc_vertices(v1,v2) 2057 gc.arc_config(v1,v2,fill=fill_in_colour) 2058 self.complete(msg) 2059 eliminated.add(vertex)

2060

2061 - def _gui_maxcard_one(self,i,j,alpha,alpha_inv,cardinality,sets,choose):

2062 i0=i[0] 2063 j0=j[0] 2064 v = choose(sets[j0]) # 14 2065 alpha[v] = i0 # 15 2066 alpha_inv[i0] = v # 16 2067 for w in self._ne[v].difference(alpha): # 17 2068 card_w = cardinality[w] # 18 2069 sets[card_w].remove(w) # 19 2070 card_w += 1 # 20 2071 sets[card_w].add(w) # 21 2072 cardinality[w] = card_w # 22 2073 j0 += 1 # 23 2074 while j0 >= 0 and not sets[j0]: # 24 2075 j0 -= 1 # 25 2076 i[0] -= 1 2077 j[0]=j0 2078 return v

2079

2080 2081 -class UForest(UGraph):

2082 """Undirected graphs where each connectivity component is a tree 2083 2084 @ivar _co: Maps each vertex to the set of all other vertices in its connectivity component 2085 @type _co: Dictionary 2086 """ 2087

2088 - def __init__(self,vertices=(),lines=(),vertex_positions=None):

2089 """TODO: There is currently no check that the input lines make a forest! 2090 """ 2091 self._co = {} 2092 UGraph.__init__(self,vertices,lines,vertex_positions)

2093

2094 - def add_vertex(self,vertex):

2095 """Adds a vertex to a graph 2096 2097 @param vertex: The vertex to add 2098 @type vertex: Anything immutable 2099 @raise ExistingVertexError: If vertex already exists 2100 """ 2101 UGraph.add_vertex(self,vertex) 2102 self._co[vertex] = set([vertex])

2103

2104 - def ordered_edges_towards_root(self):

2105 """Return a list of edges directed towards a root for each tree in the forest 2106 2107 Return a list of directed edges of form C{(frm,to)} where C{to} is 2108 nearer to an arbitrarily chosen root than C{frm} and where an edge closer to the root than another 2109 comes later in the returned list. There is a directed edge for each 2110 undirected edge in each tree in the forest. 2111 2112 @return: Directed edges 2113 @rtype: List 2114 """ 2115 edges = [] 2116 for tree in self.tree_vertices(): 2117 edges.extend(self.ordered_edges_towards_root_tree(member(tree))) 2118 return edges

2119 2120

2121 - def ordered_edges_towards_root_tree(self,root):

2122 """Return a list of edges directed towards a root 2123 2124 Return a list of directed edges of form C{(frm,to)} where C{to} is 2125 nearer to C{root} than C{frm} and where an edge closer to the root than another 2126 comes later in the returned list. There is a directed edge for each 2127 undirected edge in the tree containing C{root}. 2128 2129 @param root: Vertex towards which to direct edges 2130 @type root: Anything immutable 2131 @return: Directed edges 2132 @rtype: List 2133 """ 2134 return self.ordered_edges_towards_root_tree_cut(root,root)

2135

2136 - def ordered_edges_towards_root_tree_cut(self,root,block):

2137 """Return a list of edges directed towards a root excluding those 2138 directed towards the root's neghbour C{block}. 2139 2140 If there is no C{root,block} edge then no blocking occurs 2141 2142 Return a list of directed edges of form C{(frm,to)} where C{to} is 2143 nearer to C{root} than C{frm} and where an edge closer to C{root} than another 2144 comes later in the returned list. If C{block} neighbours C{root} then 2145 there is a directed edge for each 2146 undirected edge in the tree formed by removing C{block} and all vertices which C{block} 2147 separates from C{root}. If C{block} does not neighbour C{root} then there is a directed edge for each 2148 undirected edge in the entire tree containing C{root}. 2149 2150 @param root: Vertex towards which to direct edges 2151 @type root: Anything immutable 2152 @param block: Vertex which blocks directed edges 2153 @type block: Anything immutable 2154 @return: Directed edges 2155 @rtype: List 2156 """ 2157 edges = [] 2158 for vertex in self._ne[root]: 2159 if vertex != block: 2160 edges.extend(self.ordered_edges_towards_root_tree_cut(vertex,root)) 2161 edges.append((vertex,root)) 2162 return edges

2163

2164 - def put_line(self,frm,to):

2165 """Add a line (undirected edge) to the graph between two 2166 existing vertices 2167 2168 @param frm: One of the vertices connected by the line 2169 @type frm: Immutable type 2170 @param to: The other vertex connected by the line 2171 @type to: Immutable type 2172 @raise KeyError: If either vertex does not exist 2173 @raise CycleError: If adding the line would create a cycle 2174 """ 2175 if frm in self._co[to]: 2176 raise CycleError 2177 UGraph.put_line(self,frm,to) 2178 self._co[frm].update(self._co[to]) 2179 self._co[to].update(self._co[frm])

2180

2181 - def tree_vertices(self):

2182 """Return the vertices of each tree in the forest 2183 2184 @return: The vertices of each tree in the forest 2185 @rtype: Set of frozensets 2186 """ 2187 vertices = set() 2188 for tree in self._co.values(): 2189 vertices.add(frozenset(tree)) 2190 return vertices

2191

2192 2193 2194 -class EssentialGraph(Graph):

2195 2196 import copy 2197 2198

2199 - def __init__(self, *args, **kwargs):

2200 super(EssentialGraph,self).__init__(*args, **kwargs) 2201 self._constrained_order = None

2202

2203 - def adjacents(self,vertex):

2204 return self._ne.get(vertex,emptyset) | self._ch.get(vertex,emptyset) | self._pa.get(vertex, emptyset)

2205

2206 - def copy(self):

2207 return copy.deepcopy(self)

2208

2209 - def constrain_order(self, order):

2210 self._constrained_order = order

2211

2212 - def directed_path(self,a,b):

2213 # bfs. 2214 if a == b: 2215 return True 2216 2217 fringe = [a] 2218 while fringe: 2219 next = set() 2220 for a in fringe: 2221 ch = self.children(a) 2222 if b in ch: 2223 return True 2224 next |= ch 2225 fringe = next 2226 return False

2227 2228 @staticmethod

2229 - def from_graph(graph):

2230 graph.__class__ = EssentialGraph 2231 graph._constrained_order = None 2232 return graph

2233

2234 - def is_potential_parent(self, parent, child):

2235 # NOTE: must NOT be applied to R1-R4 below since these constraints by 2236 # themselves have been proven necessary (verma and pearl) and 2237 # sufficient (meeks, 1995) 2238 if self._constrained_order is None: 2239 return True 2240 2241 # it had better be the case that child and parent are in constrained 2242 # order. 2243 if child not in self._constrained_order or parent not in self._constrained_order: 2244 return True 2245 2246 # does child come after parent in the constrained order? 2247 return self._constrained_order.index(child) > self._constrained_order.index(parent)

2248

2249 - def no_arrow_loops(self):

2250 for a, b in self.arrows(): 2251 if self.directed_path(b, a): 2252 raise DirectedCycleError,'loop detected between '+str((a,b))

2253

2254 - def orient(self, keep_class=False):

2255 """Orient an essential graph into a DAG. The class of self becomes ADG unless C{keep_class} 2256 From E{@}inproceedingsE{lb}meek95, 2257 author = {C. Meek}, 2258 title = {Causal inference and causal explanation with background knowledge}, 2259 year = {1995}, 2260 booktitle = {Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence}, 2261 editor = {S. Hanks and P. Besnard}, 2262 pages = {403--410}, 2263 publisher = {Morgan Kaufmann} 2264 } 2265 """ 2266 lines = self.lines() 2267 while lines: 2268 # pick an undirected edge 2269 edge = lines.pop() 2270 2271 # skip if removed 2272 if edge[0] not in self.neighbours(edge[1]): 2273 continue 2274 2275 # orient it according to ordering constraint (if any) 2276 self.remove_line(edge[0],edge[1]) 2277 if self.is_potential_parent(edge[0], edge[1]): 2278 self.add_arrow(edge[0], edge[1]) 2279 else: 2280 self.add_arrow(edge[1], edge[0]) 2281 2282 # propagate the implications of this orientation 2283 self.resolve() 2284 2285 if not keep_class: 2286 self = ADG(vertices=self.vertices(), arrows=self.arrows()) 2287 2288 return self

2289

2290 - def resolve(self):

2291 # add as many directed edges as possible such that no new v-structures 2292 # nor cycles are created. 2293 self.no_arrow_loops() 2294 progress = True 2295 while progress: 2296 progress = False 2297 # these were proved to be sufficient (meek, 1995) and are from pearl (2000) 2298 progress |= self._complete_chain() 2299 self.no_arrow_loops() 2300 progress |= self._bounce_potential_cycles() 2301 self.no_arrow_loops() 2302 progress |= self._complete_colliders() 2303 self.no_arrow_loops() 2304 progress |= self._bounce_chain() 2305 self.no_arrow_loops()

2306 2307 # impose order constraint 2308

2309 - def _orient_from_order(self):

2310 if self._constrained_order is None: 2311 return 2312 lines = self.lines() 2313 for a,b in lines: 2314 if not self.is_potential_parent(a, b): 2315 self.remove_line(a,b) 2316 self.add_arrow(b, a) 2317 elif not self.is_potential_parent(b, a): 2318 self.remove_line(a,b) 2319 self.add_arrow(a, b)

2320 2321 2322 # graph operators for resolution 2323

2324 - def _complete_chain(self):

2325 # complete a -> b - c => a -> b -> c 2326 # since we have added all colliders. 2327 # R1 2328 progress = False 2329 for a,b in self.arrows(): 2330 new_arrows = set() 2331 for c in self.neighbours(b) - self.adjacents(a): 2332 new_arrows.add((b,c)) 2333 2334 for b,c in new_arrows: 2335 progress = True 2336 self.remove_line(b,c) 2337 self.add_arrow(b,c) 2338 return progress

2339

2340 - def _bounce_potential_cycles(self):

2341 # if there exists a directed edge a -> c -> b, and an undirected edge a - 2342 # b, then it must be the case that a -> b; else a cycle would be 2343 # created. 2344 # R2 2345 progress = False 2346 for a,b in self.lines(): 2347 if self._bounce_cycles(a,b): 2348 progress = True 2349 else: 2350 progress |= self._bounce_cycles(b,a) 2351 return progress

2352

2353 - def _bounce_cycles(self,a,b):

2354 # if a directed path exists A -> C -> B and A - B, then it must be that A 2355 # -> B otherwise a cycle would be created (A - B must exist). 2356 if not (self.children(a) & self.parents(b)): 2357 return False 2358 self.remove_line(a,b) 2359 self.add_arrow(a,b) 2360 return True

2361

2362 - def _complete_colliders(self):

2363 # given: 2364 # a 2365 # / | \ 2366 # c | d 2367 # _\| | |/_ 2368 # b 2369 # orient as: 2370 # a 2371 # / | \ 2372 # c | d 2373 # _\|\|/|/_ 2374 # b 2375 # given an undirected edge A - B, and two non-adjacent nodes (C,D) making B 2376 # a collider, direct A -> B. XXX: justification? 2377 # R3 2378 progress = False 2379 for c,b in self.arrows(): 2380 done = False 2381 n_c = frozenset([c]) | self.adjacents(c) 2382 p_b_nc = self.parents(b) - n_c 2383 for a in self.neighbours(b) & self.neighbours(c): 2384 for d in p_b_nc & self.neighbours(a): 2385 progress = True 2386 self.remove_line(a,b) 2387 self.add_arrow(a,b) 2388 done = True 2389 break 2390 if done: 2391 break 2392 return progress

2393

2394 - def _bounce_chain(self):

2395 # given: 2396 # a 2397 # / | \ 2398 # b _ * c 2399 # |\ | |/_ 2400 # d 2401 # orient as: 2402 # a 2403 # |/_ | \ 2404 # b _ * c 2405 # |\ | |/_ 2406 # d 2407 # given an undirected edge A - B, with a chain C -> D -> B, such that 2408 # B and C are non-adjacent and A and D are adjacent, orient A -> B. 2409 # R4 2410 progress = False 2411 for d,b in self.arrows(): 2412 done = False 2413 n_b = frozenset([b]) | self.adjacents(b) 2414 p_d_nb = self.parents(d) - n_b 2415 for a in self.neighbours(b) & self.adjacents(d): 2416 for c in p_d_nb & self.neighbours(a): 2417 progress = True 2418 self.remove_line(a,b) 2419 self.add_arrow(a,b) 2420 done = True 2421 break 2422 if done: 2423 break 2424 return progress

2425

2426 -class MutilatedADG(ADG):

2427 @staticmethod

2428 - def from_adg(adg):

2429 madg = adg.copy() 2430 madg.__class__ = MutilatedADG 2431 madg._mutilated_edges = {} 2432 return madg

2433

2434 - def __init__(self):

2435 super(MutilatedADG, self).__init__() 2436 self._mutilated_edges = {}

2437 2438 # copied from _AbsGraph: 2439 # $Id: Graphs.py,v 1.2 2008/10/07 09:09:58 jc Exp $

2440 - def copy(self):

2441 """Return a copy a graph 2442 2443 @return: A copy of the graph 2444 @rtype: Same class as C{self} 2445 """ 2446 cp = self.__class__() 2447 for attr, val in vars(self).items(): 2448 if attr == '_vertex_positions': 2449 setattr(cp,attr,val.copy()) 2450 continue 2451 setattr(cp,attr,{}) 2452 for vertex, vertices in val.items(): 2453 if hasattr(vertices,'copy'): 2454 getattr(cp,attr)[vertex] = vertices.copy() 2455 else: 2456 getattr(cp,attr)[vertex] = vertices 2457 return cp

2458

2459 - def remove_arrow(self, src, dst):

2460 super(MutilatedADG, self).remove_arrow(src, dst) 2461 self._mutilated_edges[src] = dst

2462

2463 - def mutilated_edges(self):

2464 return self._mutilated_edges.iteritems()

2465

Source Code for Module gPy.Graphs