gPy.Hypergraphs

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

13 -class HypergraphError(Exception):

14 pass

15

16 -class RedundancyError(HypergraphError):

17 pass

18

19 -class GraphicalityError(HypergraphError):

20 pass

21

22 -class DecomposabilityError(HypergraphError):

23 pass

24 25

26 -class Incidence(object):

27 """ 28 Graphs and hypergraphs are implemented differently, so even though hypergraphs are a 29 generalisation of graphs there is no direct inheritance relation defined for the 30 relevant classes. 31 32 The name 'Incidence' should not be taken too seriously. There's nothing here specific to incidence 33 structures. 34 35 This abstract class contains those few methods which are sufficiently abstract to work 36 for both graphs and hypergraphs 37 """ 38

39 - def reachable(self,a,s):

40 """Return all vertices not in C{a} to which there is a path from a vertex in C{a} 41 which includes no vertices in C{s} 42 43 'Vertices' in C{s} which are not in the hypergraph/graph are silently ignored. 44 45 @param a: Set of vertices 46 @type a: Iterable 47 @param s: Blocking set of vertices 48 @type s: Iterable 49 @return: Vertices not in C{a} reachable from C{a} by a path avoiding C{s} 50 @rtype: List 51 @raise ValueError: If C{a} and C{s} are not disjoint 52 @raise KeyError: If C{a} contains a non-existent vertex 53 """ 54 55 # bug fix thanks to Richard Lewis 56 if hasattr(self,'_ch'): 57 if hasattr(self,'_ne'): 58 def neighbours(vertex): 59 return self.neighbours(vertex) | self._ch[vertex]

60 else: 61 def neighbours(vertex): 62 return self._ch[vertex]

63 else: 64 def neighbours(vertex): 65 return self.neighbours(vertex) 66 67 banned = set(s) 68 if banned.intersection(a): 69 raise ValueError("Sets are not disjoint") 70 banned.update(a) 71 frontier = list(a) 72 reachable = [] 73 while frontier: 74 new_vertices = neighbours(frontier.pop()) - banned 75 reachable.extend(new_vertices) 76 frontier.extend(new_vertices) 77 banned.update(new_vertices) 78 return reachable 79 80

81 - def separates(self,a,b,s):

82 """Return whether C{s} separates C{a} from C{b} in C{self} 83 84 'Vertices' in C{s} which are not in the graph/hypergraph are silently ignored. 85 86 @param a: Set of vertices 87 @type a: Iterable 88 @param b: Set of vertices 89 @type b: Iterable 90 @param s: Set of vertices possibly separating C{a} from C{b} 91 @type s: Iterable 92 @return: Whether C{s} separates C{a} from C{b} 93 @rtype: Boolean 94 @raise ValueError: If C{a}, C{b} and C{s} are not disjoint 95 @raise KeyError: If C{a} or C{b} contain a non-existent vertex 96 """ 97 98 # bug fix thanks to Richard Lewis 99 if hasattr(self,'_ch'): 100 def neighbours(vertex): 101 return self.neighbours(vertex) | self._ch[vertex]

102 else: 103 def neighbours(vertex): 104 return self.neighbours(vertex) 105 106 107 a, b, s = set(a), set(b), frozenset(s) 108 if len(a|b|s) != len(a) + len(b) + len(s): 109 raise ValueError("Sets are not disjoint") 110 a_open, b_open = list(a), list(b) 111 a_seen, b_seen = a|s, b|s 112 while a_open: 113 new_vertices = neighbours(a_open.pop(0)) - a_seen 114 if new_vertices & b: 115 return False 116 a_seen.update(new_vertices) 117 a.update(new_vertices) 118 a_open.extend(new_vertices) 119 a, b = b, a 120 a_open, b_open = b_open, a_open 121 a_seen, b_seen = b_seen, a_seen 122 return True 123 124

125 -class Hypergraph(Incidence):

126 """A hypergraph is a collection of hyperedges. A hyperedge is a set of vertices. 127 128 The base set is defined implicitly as the union of the hyperedges. 129 @ivar _hyperedges: The distinct hyperedges in the hypergraph. Each hyperedge is a frozenset 130 @type _hyperedges: Set 131 @ivar _star: Maps a vertex to the set of hyperedges which 132 contain it. (Effectively represents the I{dual} hypergraph.) 133 @type _star: Dictionary 134 @ivar _extras: If repeated hyperedges exist, maps each repeated hyperedge to the 135 number of times it is repeated. (If repeated once, the hyperedge occurs twice.) 136 @type _extras: Dictionary 137 """ 138

139 - def __init__(self,hyperedges=()):

140 """Initialise a hypergraph 141 142 @param hyperedges: Initial hyperedges (or an existing hypergraph) 143 @type hyperedges: Iterable of iterables (or L{Hypergraph}) 144 @raise TypeError: If C{hyperedges} is not of the right form. 145 """ 146 if isinstance(hyperedges,Hypergraph): 147 self.__dict__ = hyperedges.__dict__ 148 else: 149 self._hyperedges = set() 150 self._star = {} 151 for hyperedge in hyperedges: 152 self.add_hyperedge(hyperedge)

153

154 - def __contains__(self,hyperedge):

155 """Return whether a hyperedge is in the hypergraph 156 157 @param hyperedge: hyperedge 158 @type hyperedge: Iterable 159 @return: Whether C{hyperedge} is in the hypergraph 160 @rtype: Boolean 161 """ 162 return frozenset(hyperedge) in self._hyperedges

163

164 - def __eq__(self,other):

165 """Return whether C{self} and C{other} are 166 identical hypergraphs (not merely isomorphic) 167 168 Irrespective of class 169 @param other: Hypergraph 170 @type other: L{Hypergraph} 171 @return: C{self} and C{other} are identical hypergraphs 172 @rtype: Boolean 173 """ 174 if self._hyperedges == other._hyperedges: 175 if hasattr(self,'_extras'): 176 for hyperedge, reps in self._extras.items(): 177 try: 178 if other._extras[hyperedge] != reps: 179 return False 180 except (AttributeError, KeyError): 181 return False 182 elif hasattr(other,'_extras'): 183 return False 184 return True 185 else: 186 return False

187

188 - def __ge__(self,other):

189 """Return whether C{self} >= C{other} 190 191 C{self} >= C{other} if every hyperedge in C{other} is contained in a 192 hyperedge in C{self} 193 194 Irrespective of class 195 @param other: Hypergraph 196 @type other: L{Hypergraph} 197 @return: Whether C{self} >= C{other} 198 @rtype: Boolean 199 """ 200 return other <= self

201

202 - def __getitem__(self,vertex):

203 """Return the star of C{vertex}: the set of hyperedges which contain C{vertex} 204 205 B{Altering the returned set will alter the hypergraph, so don't do it!} 206 A safer option is to use the L{star} method. 207 Note that a set object is returned, not a hypergraph object. 208 209 @param vertex: The vertex whose star is sought 210 @type vertex: String 211 @return: The star of C{vertex}: the hyperedges each of which contain C{vertex} 212 @rtype: Set 213 @raise KeyError: If C{vertex} is not in the (hyper)graph 214 """ 215 return self._star[vertex]

216 217

218 - def __iter__(self):

219 """Return an iterator over the B{distinct} hyperedges in the hypergraph 220 221 To allow C{for hyperedge in hypergraph: ...} constructions. 222 @return: An iterator over the B{distinct} hyperedges in the hypergraph 223 @rtype: Iterator 224 """ 225 return iter(self._hyperedges)

226

227 - def __le__(self,other):

228 """Return whether C{self} <= C{other} 229 230 C{self} <= C{other} if every hyperedge in C{self} is contained in a 231 hyperedge in C{other} 232 233 Irrespective of class 234 @param other: Hypergraph 235 @type other: L{Hypergraph} 236 @return: Whether C{self} <= C{other} 237 @rtype: Boolean 238 """ 239 for hyperedge in self: 240 if not other.would_be_redundant(hyperedge): 241 return False 242 return True

243

244 - def __len__(self):

245 """Return the number of hyperedges in the hypergraph 246 247 @return: The number of hyperedges in the hypergraph 248 @rtype: Int 249 """ 250 n = len(self._hyperedges) 251 try: 252 for m in self._extras.values(): 253 n += m 254 except AttributeError: 255 pass 256 return n

257 258

259 - def __ne__(self,other):

260 """Return whether C{self} and C{other} are 261 not identical hypergraphs 262 263 Irrespective of class 264 @param other: Hypergraph 265 @type other: L{Hypergraph} 266 @return: Whether C{self} and C{other} are not identical hypergraphs 267 @rtype: Boolean 268 """ 269 return not (self == other)

270

271 - def __repr__(self):

272 """Return 'official' string representation of the hypergraph 273 274 Can be used to construct the hypergraph using e.g. C{eval} 275 @return: The 'official' string representation of the hypergraph 276 @rtype: String 277 """ 278 if self.__class__ == Hypergraph: 279 return 'Hypergraph(%s)' % self._hyperedges 280 else: 281 return '%s(Hypergraph(%s))' % (self.__class__.__name__, self._hyperedges)

282

283 - def __str__(self):

284 """Return pretty representation of a hypergraph 285 286 @return: Pretty representation of a hypergraph 287 @rtype: String 288 """ 289 hs = [] 290 for hyperedge in self._hyperedges: 291 hs.append(', '.join([pretty_str_set(hyperedge)] * (self.multiplicity(hyperedge)))) 292 return '( %s )' % ', '.join(hs)

293

294 - def add_hyperedge(self,hyperedge):

295 """Add a hyperedge 296 297 @param hyperedge: The vertices in the hyperedge 298 @type hyperedge: Iterable 299 """ 300 hyperedge = frozenset(hyperedge) 301 if hyperedge in self._hyperedges: 302 try: 303 self._extras[hyperedge] += 1 304 except AttributeError: 305 self._extras = {hyperedge:1} 306 except KeyError: 307 self._extras[hyperedge] = 1 308 else: 309 self._add_hyperedge(hyperedge)

310

311 - def copy(self):

312 """Return a deep copy of the hypergraph 313 314 @return: A copy of C{self} 315 @rtype: The same as C{self} 316 """ 317 hg = Hypergraph() 318 hg._hyperedges.update(self._hyperedges) 319 for vertex, hyperedges in self._star.items(): 320 hg._star[vertex] = hyperedges.copy() 321 if self.__class__ == Hypergraph: 322 if hasattr(self,'_extras'): 323 hg._extras = self._extras.copy() 324 return hg 325 else: 326 return self.__class__(hg,check=False)

327 328

329 - def discard_hyperedge(self,hyperedge):

330 """Remove a hyperedge (and any repetitions), 331 or do nothing if the hyperedge does not exist 332 333 @param hyperedge: The hyperedge to be removed 334 @type hyperedge: Iterable 335 """ 336 try: 337 self.remove_hyperedge(hyperedge) 338 except KeyError: 339 pass

340

341 - def discard_hyperedges(self,hyperedges):

342 """For each hyperedge in C{hyperedges}, remove it (and any repetitions), 343 or do nothing if it does not exist 344 345 @param hyperedges: Hyperedges to be removed 346 @type hyperedges: Iterable 347 """ 348 for hyperedge in hyperedges: 349 self.discard_hyperedge(hyperedge)

350

351 - def discard_vertex(self,vertex):

352 """Remove C{vertex} from the hypergraph, or do nothing if it is not there 353 354 @param vertex: The vertex to remove 355 @type vertex: String 356 @raise RedundancyError: If C{self} is of class L{ReducedHypergraph} (or one of 357 its subclasses) and a redundant hyperedge is produced 358 """ 359 try: 360 self.remove_vertex(vertex) 361 except KeyError: 362 pass

363

364 - def discard_vertices(self,vertices):

365 """Remove C{vertices} from the hypergraph 366 367 @param vertices: The vertices to remove 368 @type vertices: Iterable 369 @raise RedundancyError: If C{self} is of class L{ReducedHypergraph} (or one of 370 its subclasses) and a redundant hyperedge is produced 371 """ 372 for vertex in vertices: 373 self.discard_vertex(vertex)

374

375 - def dual(self):

376 """Return the dual of the hypergraph 377 378 @todo: make more efficient 379 """ 380 mp = {} 381 # map each hyperedge to a set of numbers, 382 # these will be the new vertices 383 for i, h in enumerate(self.hyperedges()): 384 try: 385 mp[h].append(i) 386 except KeyError: 387 mp[h] = [i] 388 # each vertex produces an edge in the dual 389 new_edges = [] 390 for hs in self._star.values(): 391 new_edge = [] 392 for h in hs: 393 new_edge.extend(mp[h]) 394 new_edges.append(new_edge) 395 return Hypergraph(new_edges)

396

397 - def grahams(self):

398 """Run Graham's algorithm on a hypergraph 399 400 If the hypergraph is decomposable then upon return C{self} is either 401 empty or contains a single empty hyperedge. 402 """ 403 if self.is_empty(): 404 return self 405 406 self.red() 407 408 cardinality = {} 409 with_cardinality = [frozenset()] 410 max = 0 411 for vertex, star in self._star.items(): 412 card = len(star) 413 cardinality[vertex] = card 414 if card > max: 415 for i in range(card-max): 416 with_cardinality.append(set()) 417 max = card 418 with_cardinality[card].add(vertex) 419 420 while with_cardinality[1]: 421 new_hs = self.remove_vertices(with_cardinality[1]) 422 with_cardinality[1] = set() 423 for hyperedge in new_hs: 424 if self.is_redundant(hyperedge): 425 self.remove_hyperedge_once(hyperedge) 426 for vertex in hyperedge: 427 card = cardinality[vertex] 428 with_cardinality[card].remove(vertex) 429 card -= 1 430 cardinality[vertex] = card 431 with_cardinality[card].add(vertex) 432 return self

433

434 - def gui_grahams_algorithm(self,parent,width=400,height=300,**config):

435 436 import Graphs 437 438 def add_to_set(dkt,key,member): 439 try: 440 dkt[key].add(member) 441 except KeyError: 442 dkt[key] = set([member])

443 444 state, labels = {}, {} 445 top = Tkinter.Frame(parent) 446 top.pack() 447 state_frame = Tkinter.Frame(top) 448 state_frame.pack(side=Tkinter.LEFT) 449 Tkinter.Label(state_frame,text='Original').grid() 450 Tkinter.Label(state_frame,text='Current').grid(column=1,row=0) 451 for i, hyperedge in enumerate(self._hyperedges): 452 state[hyperedge] = set(hyperedge) 453 Tkinter.Label(state_frame,text=pretty_str_set(hyperedge)).grid(row=i+1,sticky=Tkinter.W) 454 labels[hyperedge] = Tkinter.Label(state_frame,text=pretty_str_set(hyperedge)) 455 labels[hyperedge].grid(column=1,row=i+1,sticky=Tkinter.W) 456 457 cardinality = {} 458 in_only_one = {} 459 for vertex, hyperedges in self._star.items(): 460 nh = len(hyperedges) 461 if nh == 1: 462 add_to_set(in_only_one,member(hyperedges),vertex) 463 else: 464 cardinality[vertex] = nh 465 join_forest = Graphs.UForest(self._hyperedges) 466 467 graph = self.two_section() 468 gc = GraphCanvas(graph,top,edit=False, 469 colour_user_actions=False, 470 width=width,height=height,**config) 471 gc.pack(side=Tkinter.LEFT) 472 bottom = Tkinter.Frame(parent) 473 bottom.pack() 474 gcj = GraphCanvas(join_forest,bottom,edit=False, 475 colour_user_actions=False, 476 pp_vertex=pretty_str_set, 477 width=width,height=height,**config) 478 gcj.pack() 479 varslabel = Tkinter.Label(bottom) 480 varslabel.pack(side=Tkinter.LEFT) 481 sel = frozenset() 482 for h, vs in in_only_one.items(): 483 if sorted(h) > sorted(sel): 484 v = vs 485 sel = h 486 if len(v) == 1: 487 print 'About to remove vertex', tuple(v)[0], 'since it is only present in', pretty_str_set(sel) 488 else: 489 print 'About to remove vertices', tuple(v), 'since they are only present in', pretty_str_set(sel) 490 def handler(self=self,in_only_one=in_only_one,state=state, 491 cardinality=cardinality,labels=labels, 492 gc=gc,gcj=gcj,varslabel=varslabel,join_forest=join_forest, 493 add_to_set=add_to_set): 494 self._gui_graham(in_only_one,state,cardinality,labels, 495 gc,gcj,varslabel,join_forest,add_to_set)

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

498 - def _gui_graham(self,in_only_one,state,cardinality,labels, 499 gc,gcj,varslabel,join_forest,add_to_set):

500 if not in_only_one: 501 print 'Finished' 502 return 503 hyperedge = frozenset() 504 for h, vs in in_only_one.items(): 505 if sorted(h) > sorted(hyperedge): 506 hyperedge = h 507 vertices = vs 508 del in_only_one[hyperedge] 509 #hyperedge, vertices = in_only_one.popitem() 510 residue = state[hyperedge] 511 residue -= vertices 512 labels[hyperedge].config(text=pretty_str_set(residue)) 513 for vertex in vertices: 514 gc.vertex_config(vertex,fill='grey') 515 if residue: 516 cp = residue.copy() 517 v = cp.pop() 518 proper_supersets = self._star[v] - set([hyperedge]) 519 proper_supersets.intersection(state) 520 for vertex in cp: 521 proper_supersets &= self._star[vertex] 522 if not proper_supersets: 523 break 524 if proper_supersets: 525 del state[hyperedge] 526 labels[hyperedge].config(fg='grey') 527 receiver = member(proper_supersets) 528 join_forest.put_line(hyperedge,receiver) 529 gcj.drawarc_vertices(hyperedge,receiver) 530 for vertex in residue: 531 nh = cardinality[vertex] 532 if nh == 2: 533 add_to_set(in_only_one,receiver,vertex) 534 else: 535 cardinality[vertex] = nh - 1 536 else: 537 del state[hyperedge] 538 sel = frozenset() 539 for h, vs in in_only_one.items(): 540 if sorted(h) > sorted(sel): 541 v = vs 542 sel = h 543 if sel: 544 if len(v) == 1: 545 print 'About to remove vertex', tuple(v)[0], 'since it is only present in', pretty_str_set(sel) 546 else: 547 print 'About to remove vertices', tuple(v), 'since they are only present in', pretty_str_set(sel) 548 elif len(state) > 1: 549 flag = False 550 print 'No vertex is in only one hyperedge' 551 for hyperedge, current in state.items(): 552 for h, c in state.items(): 553 if current is not c and current <= c: 554 flag = True 555 print 'Removing', pretty_str_set(current), 'since it is contained in', pretty_str_set(c) 556 del state[hyperedge] 557 labels[hyperedge].config(fg='grey') 558 join_forest.put_line(hyperedge,h) 559 gcj.drawarc_vertices(hyperedge,h) 560 for vertex in hyperedge: 561 nh = cardinality[vertex] 562 if nh == 2: 563 add_to_set(in_only_one,receiver,vertex) 564 else: 565 cardinality[vertex] = nh - 1 566 if not flag: 567 print 'No redundant hyperedges' 568 sel = frozenset() 569 for h, vs in in_only_one.items(): 570 if sorted(h) > sorted(sel): 571 v = vs 572 sel = h 573 if sel: 574 if len(v) == 1: 575 print 'About to remove vertex', tuple(v)[0], 'since it is only present in', pretty_str_set(sel) 576 else: 577 print 'About to remove vertices', tuple(v), 'since they are only present in', pretty_str_set(sel)

578

579 - def gui_display(self,parent,**config):

580 """Display a hypergraph using a GUI 581 582 Shows the representative graph 583 584 Ignores repeated hyperedges, so not quite accurate for non-simple hypergraphs 585 586 @param parent: Parent window for GUI 587 @type parent: Suitable Tkinter widget 588 @param config: Configuration options for the GUI 589 @type config: Various 590 @return: The GUI 591 @rtype: L{GraphCanvas} 592 """ 593 return self.representative_graph().gui_display(parent,**config)

594

595 - def hyperedges(self):

596 """Return a list of the hyperedges in the hypergraph 597 598 @return: A list of the hyperedges in the hypergraph 599 @rtype: List 600 """ 601 hs = [] 602 for h in self._hyperedges: 603 hs.extend([h] * self.multiplicity(h)) 604 return hs

605

606 - def is_arboreal(self):

607 """Return whether the hypergraph is arboreal 608 609 A hypergraph is arboreal iff its dual is acyclic (ie decomposable) 610 611 @return: Whether the hypergraph is decomposable 612 @rtype: Boolean 613 """ 614 return self.dual().is_decomposable()

615

616 - def is_decomposable(self):

617 """Return whether the hypergraph is decomposable 618 619 Uses L{maximum_cardinality_search} 620 621 @return: Whether the hypergraph is decomposable 622 @rtype: Boolean 623 """ 624 return bool(self.maximum_cardinality_search(decomp_check=True))

625 626 is_acyclic = is_decomposable 627

628 - def is_empty(self):

629 return self._hyperedges == set()

630 631

632 - def is_graphical(self):

633 """Return whether the hypergraph is graphical 634 635 @return: Whether the hypergraph is graphical 636 @rtype: Boolean 637 @todo: Implement efficiently 638 """ 639 if self._hyperedges == set(): 640 return True 641 r = ReducedHypergraph(self.copy(),modify=True) 642 return r == r.two_section().hypergraph()

643 644 is_conformal = is_graphical 645

646 - def is_reduced(self):

647 """Test whether a hypergraph is reduced 648 649 @return: Whether a hypergraph is reduced 650 @rtype: Boolean 651 """ 652 if self._hyperedges == set(): 653 return True 654 if hasattr(self,'_extras'): 655 return False 656 if emptyset in self._hyperedges: 657 if len(self._hyperedges) > 1: 658 return False 659 else: 660 return True 661 done = set() 662 for star in self._star.values(): 663 for hyperedge in star.difference(done): 664 for other_hyperedge in star: 665 if other_hyperedge is not hyperedge and other_hyperedge >= hyperedge: 666 return False 667 done.add(hyperedge) 668 return True

669 670

671 - def is_redundant(self,hyperedge,check=False):

672 """Whether C{hyperedge} is a redundant hyperedge of the hypergraph 673 674 @param hyperedge: Hyperedge 675 @type hyperedge: Iterable 676 @return: False if not redundant, otherwise the set of distinct 677 containing hyperedges 678 @rtype: Boolean or set 679 @raise ValueError: If C{check=True} and C{hyperedge} is not in the hypergraph. 680 So this is only really useful for testing the redundancy of existing hyperedges. 681 To test the redundancy of hyperedges which may not already be in the hypergraph 682 use L{makes_unreduced}. 683 """ 684 if hyperedge not in self: 685 if check: 686 raise ValueError("%s not in %s" % (hyperedge,self)) 687 else: 688 return False 689 if hyperedge: 690 for vertex in hyperedge: 691 try: 692 cs.intersection_update( 693 self._star[vertex]) 694 except NameError: 695 cs = self._star[vertex].copy() 696 if len(cs) == 1: 697 if not hasattr(self,'_extras') or hyperedge not in self._extras: 698 return False 699 else: 700 cs = self._hyperedges.copy() 701 if not hasattr(self,'_extras') or hyperedge not in self._extras: 702 cs.remove(hyperedge) 703 return cs

704

705 - def is_separating(self):

706 """Whether the hypergraph is a separating hypergraph 707 708 A hypergraph is separating if, for every vertex v, the intersection 709 of all hyperedges in v's star equals {v} 710 711 @return: Whether the hypergraph is a separating hypergraph 712 @rtype: Boolean 713 """ 714 for hyperedges in self._star.values(): 715 tmp = hyperedges.copy() 716 st = tmp.pop() 717 while len(st) > 1: 718 try: 719 st &= tmp.pop() 720 except KeyError: 721 return False 722 return True

723 724

725 - def is_simple(self):

726 """Test whether a hypergraph is simple 727 728 @return: Whether a hypergraph is simple 729 @rtype: Boolean 730 """ 731 return not hasattr(self,'_extras')

732

733 - def join(self,hypergraph):

734 """Return the join of C{self} and C{hypergraph} 735 736 @return: C{self ^ hypergraph} 737 @rtype: ReducedHypergraph 738 """ 739 join_hg = SimpleHypergraph() 740 for he1 in self._hyperedges: 741 for he2 in hypergraph._hyperedges: 742 try: 743 join_hg.add_hyperedge(he1 & he2) 744 # if he1 & he2 already there 745 except ValueError: 746 pass 747 join_hg.make_reduced() 748 return join_hg

749 750

751 - def join_forest(self,choose=None):

752 """Return a join forest graph, assuming decomposability 753 754 Any repeated hyperedges are ignored 755 756 Uses L{maximum_cardinality_search}. See that method for bibliographical 757 references. 758 @return: A join forest graph 759 @rtype: L{Graphs.UForest} 760 @raise DecomposabilityError: If hypergraph is not decomposable 761 """ 762 import Graphs 763 result = self.maximum_cardinality_search(choose,True) 764 if result: 765 receiver = result[1] 766 join_forest = Graphs.UForest(self._hyperedges.copy()) 767 for sender, recipient in receiver.items(): 768 join_forest.put_line(sender,recipient) 769 else: 770 raise DecomposabilityError("%s is not decomposable" % self) 771 return join_forest

772 773 774 775

776 - def join_forest_ve(self):

777 """Return a join forest for the hypergraph using vertex elimination 778 779 Source is annotated. 780 Refs:: 781 782 @TechReport{graham79, 783 author = {M. H. Graham}, 784 title = {On the universal relation}, 785 institution = {University of Toronto}, 786 year = 1979, 787 address = {Toronto, Canada} 788 } 789 790 @article{322389, 791 author = {Catriel Beeri and Ronald Fagin and David Maier and Mihalis Yannakakis}, 792 title = {On the Desirability of Acyclic Database Schemes}, 793 journal = {Journal of the {ACM}}, 794 volume = {30}, 795 number = {3}, 796 year = {1983}, 797 issn = {0004-5411}, 798 pages = {479--513}, 799 doi = {http://doi.acm.org/10.1145/2402.322389}, 800 publisher = {ACM Press}, 801 address = {New York, NY, USA}, 802 } 803 804 @return: A join forest for the hypergraph 805 @rtype: L{Graphs.UForest} 806 @raise RedundancyError: If hypergraph is not reduced 807 @raise ValueError: If the hypergraph is reduced but not decomposable 808 """ 809 810 # Graham's algorithm is as follows: 811 # Apply the following two operations until neither applies: 812 # 1. Delete a vertex that it is in only one hyperedge 813 # 2. Delete a redundant hyperedge 814 # If the hypergraph is decomposable all vertices will eventually be deleted. 815 816 # Beeri et al show that Graham's algorithm can be used to construct 817 # a join tree from a decomposable hypergraph. The vertices of the join tree are the 818 # hyperedges of the hypergraph. If a non-empty hyperedge is deleted at step 2 of Graham's algorithm 819 # then, in the join tree, an edge is drawn between it and one of the hyperedges containing it. 820 821 # This method implements this approach. The only difference from Graham's algorithm 822 # is that in step 1 all 'isolated' vertices in the selected hyperedge are removed. Only 823 # once this is done is there any prospect of the hyperedge being redundant. 824 825 # Since hyperedges will be altered we set up 'state' (lines 1-3) which maps hyperedges 826 # from their (immutable) initial state to their 827 # (mutable) current state. If a hyperedge is deleted it is removed from 'state'. 828 # In lines 4-11 is set up the mapping 'in_only_one'. A hyperedge is a key in this mapping if it 829 # contains a vertex which appears in no other edges (an 'isolated' vertex). 830 # The value associated with this key is 831 # just the set of vertices only appearing in the hyperedge. If a vertex appears in more than one 832 # hyperedge, we record how many in the mapping 'cardinality'. 833 834 # The join forest is initialised to have the hyperedges as vertices, and no edges at line 12. 835 836 # The main loop is executed as long as there is a vertex contained in only one edge (line 13). 837 838 # A hyperedge containing vertices not found elsewhere is selected and these vertices are 839 # then deleted from it (lines 14-16). If residual vertices exist in the hyperedge (line 17), we 840 # need to check for redundancy. Lines 18-25 do this by constructing 'proper_supersets': the set of 841 # remaining (line 21) hyperedges containing all vertices in 'residue'. 842 # If (line 26) this is non-empty, then the hyperedge is removed (line 27) and an arbitrary 843 # member of proper_supersets is chosen for the required connection in the join tree (line 28). 844 # If a hyperedge has been removed it is necessary to update 'in_only_one' 845 # and 'cardinality' appropriately (lines 30-35). 846 847 # Lines 36,37: If there were no residual vertices then the hyperedge has become empty. 848 # So, if there are 849 # any other remaining hyperedges, it will be redundant, but no join forest edges need be drawn. 850 851 # Termination: If there remain undeleted edges (and hence undeleted vertices) then the hypergraph 852 # was not decomposable (lines 38,39) 853 # otherwise all is well and the join forest can be returned (line 40). 854 855 import Graphs 856 857 if not self.is_reduced(): 858 raise RedundancyError("%s is not reduced" % self) 859 860 def add_to_set(dkt,key,member): 861 try: 862 dkt[key].add(member) 863 except KeyError: 864 dkt[key] = set([member])

865 866 state = {} # 1 867 for hyperedge in self._hyperedges: # 2 868 state[hyperedge] = set(hyperedge) # 3 869 cardinality = {} # 4 870 in_only_one = {} # 5 871 for vertex, hyperedges in self._star.items(): # 6 872 nh = len(hyperedges) # 7 873 if nh == 1: # 8 874 add_to_set(in_only_one,member(hyperedges),vertex) # 9 875 else: #10 876 cardinality[vertex] = nh #11 877 join_forest = Graphs.UForest(self._hyperedges) # 12 878 while in_only_one: # 13 879 hyperedge, vertices = in_only_one.popitem() # 14 880 residue = state[hyperedge] # 15 881 residue -= vertices # 16 882 if residue: # 17 883 cp = residue.copy() # 18 884 v = cp.pop() # 19 885 proper_supersets = self._star[v] - set([hyperedge]) # 20 886 proper_supersets.intersection(state) # 21 887 for vertex in cp: # 22 888 proper_supersets &= self._star[vertex] # 23 889 if not proper_supersets: # 24 890 break # 25 891 if proper_supersets: # 26 892 del state[hyperedge] # 27 893 receiver = member(proper_supersets) # 28 894 join_forest.put_line(hyperedge,receiver) # 29 895 for vertex in residue: # 30 896 nh = cardinality[vertex] # 31 897 if nh == 2: # 32 898 add_to_set(in_only_one,receiver,vertex) # 33 899 else: # 34 900 cardinality[vertex] = nh - 1 # 35 901 else: # 36 902 del state[hyperedge] # 37 903 if state: # 38 904 raise ValueError("Hypergraph was not decomposable, no join forest is possible") # 39 905 return join_forest # 40 906

907 - def make_decomposable(self,criterion=None):

908 """Return a L{DecomposableHypergraph} produced by eliminating variables from C{self} 909 using C{criterion} 910 911 Destroys C{self} in the process. 912 913 @param criterion: Function giving criterion for choosing next vertex to eliminate 914 @type criterion: Function 915 @return: Decomposable hypergraph, destination dictionary 916 @rtype: Tuple 917 """ 918 if criterion is None: 919 def criterion(hg): 920 first = True 921 for v, star in hg._star.items(): 922 card = len(star) 923 if card == 1: 924 return v 925 if first or card < minimum: 926 minimum = card 927 optimal = v 928 first = False 929 return optimal

930 dhg = DecomposableHypergraph() 931 arrows = {} 932 original_hyperedges = self._hyperedges.copy() 933 destination = {} 934 while self._star: 935 vertex = criterion(self) 936 new_hyperedge = set() 937 originals = [] 938 # make the new hyperedge produced by eliminating 939 for hyperedge in self._star[vertex].copy(): 940 new_hyperedge |= hyperedge 941 if hyperedge in original_hyperedges: 942 originals.append(hyperedge) 943 self.remove_hyperedge(hyperedge) 944 if not dhg.would_be_redundant(new_hyperedge): 945 frozen_new_hyperedge = frozenset(new_hyperedge) 946 dhg.add_hyperedge(frozen_new_hyperedge) 947 dest = frozen_new_hyperedge 948 else: 949 # hack! 950 for hyperedge in dhg._hyperedges: 951 if new_hyperedge <= hyperedge: 952 dest = hyperedge 953 break 954 for original in originals: 955 destination[original] = dest 956 new_hyperedge.remove(vertex) 957 if new_hyperedge not in self: 958 self.add_hyperedge(new_hyperedge) 959 return dhg, destination 960 961

962 - def make_decomposable2(self,elimination_ordering=None):

963 """Return a L{DecomposableHypergraph} produced by eliminating variables from C{self} 964 in the order given by C{elimination_ordering}. 965 966 Destroys C{self} in the process. 967 968 If no C{elimination_ordering} is given 969 L{Graphs.UGraph.maximum_cardinality_search} is used 970 to provide one. 971 972 @todo: This is simple but inefficient at present. 973 974 @param elimination_ordering: Order in which to eliminate variables 975 @type elimination_ordering: Sequence 976 @return: Decomposable hypergraph, destination dictionary 977 @rtype: Tuple 978 """ 979 if elimination_ordering is None: 980 # order_dict = ReducedHypergraph( 981 # self.copy(),modify=True).maximum_cardinality_search()[0] 982 # would be better to do this directly on the hypergaph 983 order_dict = self.two_section().maximum_cardinality_search()[0] 984 elimination_ordering = [None] * len(order_dict) 985 for variable, index in order_dict.items(): 986 elimination_ordering[index] = variable 987 dhg = DecomposableHypergraph() 988 original_hyperedges = self._hyperedges.copy() 989 destination = {} 990 for vertex in elimination_ordering: 991 new_hyperedge = set() 992 originals = [] 993 for hyperedge in self._star[vertex].copy(): 994 new_hyperedge |= hyperedge 995 if hyperedge in original_hyperedges: 996 originals.append(hyperedge) 997 self.remove_hyperedge(hyperedge) 998 if not dhg.would_be_redundant(new_hyperedge): 999 frozen_new_hyperedge = frozenset(new_hyperedge) 1000 dhg.add_hyperedge(frozen_new_hyperedge) 1001 dest = frozen_new_hyperedge 1002 else: 1003 # hack! 1004 for hyperedge in dhg._hyperedges: 1005 if new_hyperedge <= hyperedge: 1006 dest = hyperedge 1007 break 1008 for original in originals: 1009 destination[original] = dest 1010 new_hyperedge.remove(vertex) 1011 if new_hyperedge not in self: 1012 self.add_hyperedge(new_hyperedge) 1013 return dhg, destination

1014 1015 1016

1017 - def makes_unreduced(self,hyperedge):

1018 """True if C{hyperedge} is a subset or superset of a hyperedge in the 1019 hypergraph ... 1020 1021 ... irrespective of whether C{self} is already reduced or not 1022 @param hyperedge: Hyperedge 1023 @type hyperedge: Iterable 1024 @return: Whether C{hyperedge} (would) cause redundancy 1025 """ 1026 hyperedge = frozenset(hyperedge) 1027 #needs to be made more efficient 1028 for he in self._hyperedges: 1029 if he >= hyperedge or he <= hyperedge: 1030 return True 1031 return False

1032

1033 - def matrix(self,sort=False):

1034 """Return the incidence matrix for a hyperedge 1035 """ 1036 hyperedges = self.hyperedges() 1037 if sort: 1038 ky = {} 1039 for h in hyperedges: 1040 ky[h] = sorted(h) 1041 def kyf(x): return ky[x] 1042 hyperedges.sort(key=kyf) 1043 vertices = sorted(self._star) 1044 else: 1045 vertices = self._star 1046 cols = {} 1047 for col, h in enumerate(hyperedges): 1048 try: 1049 cols[h].append(col) 1050 except KeyError: 1051 cols[h] = [col] 1052 matrix = [] 1053 zeros = [0] * len(hyperedges) 1054 for vertex in vertices: 1055 row = zeros[:] 1056 for hyperedge in self._star[vertex]: 1057 for col in cols[hyperedge]: 1058 row[col] = 1 1059 matrix.append(row) 1060 return matrix

1061

1062 - def matrix_generate(self,matrix,transpose=False):

1063 """Add hyperedges, vertices using an incidence matrix 1064 """ 1065 rn = range(len(matrix[0])) # no. of hyperedges 1066 rm = range(len(matrix)) # no. of vertices 1067 if transpose: 1068 for row in rm: 1069 hyperedge = [] 1070 for col in rn: 1071 if matrix[row][col] == 1: 1072 hyperedge.append(col) 1073 self.add_hyperedge(hyperedge) 1074 else: 1075 for col in rn: 1076 hyperedge = [] 1077 for row in rm: 1078 if matrix[row][col] == 1: 1079 hyperedge.append(row) 1080 self.add_hyperedge(hyperedge) 1081 return self

1082

1083 - def msc_decompcover(self):

1084 """DON'T USE: STILL BEING WRITTEN""" 1085 def getmax(s): 1086 l = 0 1087 for x in s: 1088 if len(x) > l: 1089 l = len(x) 1090 biggest = x 1091 s.remove(biggest) 1092 return biggest

1093 eliminated_in, receiver = self.maximum_cardinality_search(getmax) 1094 newhs = {} 1095 for hyperedge in self._hyperedges: 1096 newhs[hyperedge] = set(hyperedge) 1097 #TODO propogate properly 1098 for sender, receiver in receiver.items(): 1099 newhs[receiver] |= sender - eliminated_in.get(sender,frozenset()) 1100 return Hypergraph(newhs.values()) 1101 1102

1103 - def maximum_cardinality_search(self, 1104 choose=None,decomp_check=False):

1105 """ 1106 Multiple hyperedges are ignored, so if the hypergraph is non-simple this produces the 1107 same result as if multiple hyperedges had been deleted. 1108 1109 @param choose: Function for breaking ties when selecting a hyperedge with 1110 maximum cardinality. If C{None} ties are broken arbitrarily. 1111 @type choose: A function which removes and returns an element from a set. 1112 @param decomp_check: If C{True} then C{False} is returned as soon as it is 1113 established that C{self} is not decomposable 1114 @type decomp_check: Boolean 1115 @return: If C{decomp_check=True} and C{self} is not decomposable then 1116 C{False} is returned. Otherwise (1) For each selected hyperedge the set 1117 of vertices eliminated there 1118 and (2) for each hyperedge the hyperedge (if any) which `absorbs' it 1119 @rtype: C{False} or Tuple, a pair of dictionaries 1120 """ 1121 if choose is None: 1122 def choose(s): return s.pop() 1123 1124 sets = [self._hyperedges.copy()] 1125 cardinality = dict( 1126 zip(self._hyperedges,[0] * len(self._hyperedges))) 1127 eliminated_in = {} 1128 eliminated_vertices = set() 1129 receiver = {} 1130 1131 def ok(h): 1132 return (h - eliminated_in.get(h,frozenset()) 1133 <= receiver.get(h,frozenset()))

1134 1135 while sets: 1136 if not sets[-1]: 1137 sets.pop() 1138 continue 1139 selected_hyperedge = choose(sets[-1]) 1140 eliminated_here = ( 1141 selected_hyperedge - eliminated_vertices) 1142 eliminated_vertices.update(eliminated_here) 1143 eliminated_in[selected_hyperedge] = eliminated_here 1144 if decomp_check and not ok(selected_hyperedge): 1145 return False 1146 else: 1147 del cardinality[selected_hyperedge] 1148 for vertex in eliminated_here: 1149 for hyperedge in ( 1150 self._star[vertex].intersection(cardinality)): 1151 receiver[hyperedge] = selected_hyperedge 1152 card_h = cardinality[hyperedge] 1153 sets[card_h].remove(hyperedge) 1154 card_h += 1 1155 if card_h == len(hyperedge): 1156 if decomp_check and not ok(hyperedge): 1157 return False 1158 else: 1159 del cardinality[hyperedge] 1160 else: 1161 cardinality[hyperedge] = card_h 1162 try: 1163 sets[card_h].add(hyperedge) 1164 except IndexError: 1165 sets.append(set([hyperedge])) 1166 return eliminated_in, receiver 1167 1168 1169

1170 - def merge(self,hyperedges):

1171 """Replace hyperedges by their union. 1172 1173 All repetitions of a hyperedge in C{hyperedges} will go. 1174 1175 @param hyperedges: The hyperedges to merge 1176 @type hyperedges: Iterable 1177 """ 1178 new_hyperedge = set() 1179 for hyperedge in hyperedges: 1180 hyperedge = frozenset(hyperedge) 1181 new_hyperedge.update(hyperedge) 1182 self.remove_hyperedge(hyperedge) 1183 self.add_hyperedge(frozenset(new_hyperedge))

1184

1185 - def multiplicity(self,hyperedge):

1186 """Return how often C{hyperedge} occurs in the hypergraph 1187 1188 Returns 0 if C{hyperedge} is not in the hypergraph 1189 1190 @param hyperedge: hyperedge 1191 @type hyperedge: Iterable 1192 @return: How often C{hyperedge} occurs in the hypergraph 1193 @rtype: Int 1194 @raise KeyError: If C{hyperedge} contains vertices not in the hypergraph 1195 """ 1196 hyperedge = frozenset(hyperedge) 1197 try: 1198 return self._extras[hyperedge] + 1 1199 except (AttributeError, KeyError): 1200 if hyperedge in self._hyperedges: 1201 return 1 1202 elif hyperedge <= self.vertices(): 1203 return 0 1204 else: 1205 raise KeyError('%s contains vertices not in %s' % (hyperedge, self.vertices()))

1206

1207 - def neighbours(self,vertex):

1208 """Return the set of all those vertices each of which is in 1209 a hyperedge with C{vertex} 1210 1211 C{vertex} is not included amongst the neighbours 1212 1213 @param vertex: The vertex whose neighbours are sought 1214 @type vertex: String 1215 @return: Neighbours of C{vertex} 1216 @rtype: Set 1217 """ 1218 neighbours = set() 1219 for hyperedge in self._star[vertex]: 1220 neighbours.update(hyperedge) 1221 neighbours.remove(vertex) 1222 return neighbours

1223

1224 - def order(self):

1225 """Return the number of vertices in the hypergraph 1226 1227 @return: The number of vertices in the hypergraph 1228 @rtype: Int 1229 """ 1230 return len(self._star)

1231 1232

1233 - def red(self):

1234 """Reduce the hypergraph 1235 1236 Does not change the class of C{self} 1237 1238 Any hyperedge contained in another is removed 1239 @return: Any redundant hyperedges 1240 @rtype: List 1241 """ 1242 deleted = self.simplify() 1243 redundant = self.redundant_hyperedges() 1244 for redundant_hyperedge in redundant: 1245 self.remove_hyperedge(redundant_hyperedge) 1246 deleted.extend(list(redundant)) 1247 return deleted

1248 1249 # def reduced(self): 1250 # """Return a new hypergraph which is the reduced version of 1251 # C{self} 1252 1253 # Does not alter C{self} 1254 # @return: The reduced version of C{self} 1255 # @rtype: L{ReducedHypergraph} 1256 # """ 1257 # cp = self.copy() 1258 # cp.make_reduced() 1259 # return cp 1260 1261 # def red_hyperedges(self): 1262 # """Returns the set of redundant hyperedges in the hypergraph. 1263 1264 # Multiple occurrences of a hyperedge are ignored. 1265 1266 # @return: Set of redundant hyperedges 1267 # @rtype: Set 1268 # """ 1269 # if emptyset in self._hyperedges and len(self._hyperedges) > 1: 1270 # red = set([emptyset]) 1271 # else: 1272 # red = set() 1273 # done = set() 1274 # for star in self._star.values(): 1275 # for hyperedge in star.difference(done): 1276 # for other_hyperedge in star: 1277 # if other_hyperedge is not hyperedge and other_hyperedge >= hyperedge: 1278 # red.add(hyperedge) 1279 # break 1280 # done.add(hyperedge) 1281 # return red 1282

1283 - def redundant_hyperedges(self,only_redundant=True):

1284 """Returns a dictionary mapping, by default, each distinct redundant hyperedge to 1285 the set of distinct hyperedges which properly contain it. 1286 1287 A strictly redundant hyperedge is one properly contained in another 1288 1289 @param only_redundant: Whether only redundant hyperedges are included as keys 1290 in the returned dictionary. If false, non-redundant hyperedges are included and are mapped 1291 to the empty set. 1292 @type only_redundant: Boolean 1293 @return: Set of superset hyperedges for each (by default redundant) hyperedge 1294 @rtype: Dictionary 1295 """ 1296 supersets = {} 1297 for hyperedge in self._hyperedges: 1298 if not hyperedge: 1299 supersets[hyperedge] = self._hyperedges - set([hyperedge]) 1300 continue 1301 1302 vertices = tuple(hyperedge) 1303 possible_supersets = self._star[vertices[0]] - set([hyperedge]) 1304 for vertex in vertices[1:]: 1305 possible_supersets.intersection_update(self._star[vertex]) 1306 if not possible_supersets: 1307 break 1308 if possible_supersets: 1309 supersets[hyperedge] = possible_supersets 1310 1311 if not only_redundant: 1312 for hyperedge in self._hyperedges.difference(supersets): 1313 supersets[hyperedge] = set() 1314 1315 return supersets

1316 1317 # if emptyset in self._hyperedges: 1318 # supersets = {emptyset:self._hyperedges - set(emptyset)} 1319 # else: 1320 # supersets = {} 1321 # for star in self._star.values(): 1322 # for hyperedge in star.difference(supersets): 1323 # supersets[hyperedge] = set() 1324 # for other_hyperedge in star: 1325 # if other_hyperedge is not hyperedge and other_hyperedge >= hyperedge: 1326 # supersets[hyperedge].add(other_hyperedge) 1327 # if only_redundant: 1328 # for hyperedge, supsets in supersets.items(): 1329 # if supsets == set(): 1330 # del supersets[hyperedge] 1331 # return supersets 1332

1333 - def remove_hyperedge(self,hyperedge):

1334 """Remove a hyperedge (including any repetitions of it) 1335 1336 @param hyperedge: The hyperedge to be removed 1337 @type hyperedge: Iterable 1338 @raise KeyError: If C{hyperedge} is not in the hypergraph 1339 """ 1340 hyperedge = frozenset(hyperedge) 1341 self._hyperedges.remove(hyperedge) 1342 for vertex in hyperedge: 1343 self._star[vertex].remove(hyperedge) 1344 if not self._star[vertex]: 1345 del self._star[vertex] 1346 try: 1347 del self._extras[hyperedge] 1348 except (AttributeError, KeyError): 1349 pass

1350

1351 - def remove_hyperedge_once(self,hyperedge):

1352 """Remove one occurrence of a hyperedge 1353 1354 If the hyperedge is repeated a repetition is removed. 1355 1356 @param hyperedge: The hyperedge to be removed 1357 @type hyperedge: Iterable 1358 @raise KeyError: If C{hyperedge} is not in the hypergraph 1359 """ 1360 hyperedge = frozenset(hyperedge) 1361 try: 1362 n = self._extras[hyperedge] 1363 if n == 1: 1364 del self._extras[hyperedge] 1365 else: 1366 self._extras[hyperedge] = n-1 1367 except (AttributeError, KeyError): 1368 self.remove_hyperedge(hyperedge)

1369

1370 - def remove_hyperedges(self,hyperedges):

1371 """Remove distinct hyperedges 1372 1373 Each hyperedge in C{hyperedges} is removed together with any repetitions 1374 1375 @param hyperedges: Distinct hyperedges to be removed 1376 @type hyperedges: Sequence 1377 @raise KeyError: If some hyperedge in C{hyperedges} does not exist 1378 """ 1379 for hyperedge in hyperedges: 1380 self.remove_hyperedge(hyperedge)

1381 1382 1383

1384 - def remove_vertex(self,vertex):

1385 """Remove C{vertex} from the hypergraph 1386 1387 @param vertex: The vertex to remove 1388 @type vertex: String 1389 @raise KeyError: If C{vertex} is not in the hypergraph 1390 @raise RedundancyError: TOFIX: If C{self} is of class L{ReducedHypergraph} (or one of 1391 its subclasses) and a redundant hyperedge is produced 1392 """ 1393 return self.remove_vertices(frozenset([vertex]))

1394 # new_hs = [] 1395 # for hyperedge in self._star[vertex]: 1396 # smaller = hyperedge - set([vertex]) 1397 # new_hs.append(smaller) 1398 # self._hyperedges.remove(hyperedge) 1399 # try: 1400 # del self._extras[hyperedge] 1401 # except (AttributeError, KeyError): 1402 # pass 1403 # if smaller in self._hyperedges: 1404 # if not isinstance(self,SimpleHypergraph): 1405 # try: 1406 # self._extras[smaller] += 1 1407 # except AttributeError: 1408 # self._extras = {smaller:1} 1409 # except KeyError: 1410 # self._extras[smaller] = 1 1411 # else: 1412 # self._hyperedges.add(smaller) 1413 # for v in smaller: 1414 # tmp = self._star[v] 1415 # tmp.remove(hyperedge) 1416 # tmp.add(smaller) 1417 # del self._star[vertex] 1418 # return new_hs 1419 1420

1421 - def remove_vertices(self,vertices):

1422 """Remove C{vertices} from the hypergraph 1423 1424 @param vertices: The vertices to remove 1425 @type vertices: Set 1426 @raise KeyError: If C{vertex} is not in the hypergraph 1427 @raise RedundancyError: If C{self} is of class L{ReducedHypergraph} (or one of 1428 its subclasses) and a redundant hyperedge is produced 1429 """ 1430 return self.restriction(vertices,True)

1431

1432 - def rename_vertices(self,renaming,check=True):

1433 """Rename the vertices of a hypergraph 1434 1435 New hypergraph is isomorphic to existing one. 1436 1437 @param renaming: Map from existing vertices to new vertices 1438 @type renaming: Dictionary 1439 @return: Isomorphic hypergrah with new names for vertices 1440 @rtype: Same class as C{self} 1441 @raise KeyError: If an existing vertex is missing from C{renaming} 1442 @raise ValueError: If two existing vertices are mapped to the name new name 1443 """ 1444 if check: 1445 chk_st = set() 1446 for newname in renaming.values(): 1447 if newname in chk_st: 1448 raise ValueError('%s appears more than once as a new name' % newname) 1449 chk_st.add(newname) 1450 newhs = [] 1451 for hyperedge in self._hyperedges: 1452 newh = [] 1453 for v in hyperedge: 1454 newh.append(renaming[v]) 1455 newhs.extend([newh] * self.multiplicity(hyperedge)) 1456 return self.__class__(newhs)

1457 1458

1459 - def representative_graph(self):

1460 """Return the representative graph of a hypergraph 1461 1462 The vertices of the graph are hyperedges of the hypergraph. Two 1463 vertices are connected if the corresponding hyperedges intersect 1464 1465 Ignores repeated hyperedges, so not quite accurate for non-simple hypergraphs 1466 1467 Also known as the line-graph of the hypergraph 1468 1469 @return: The representative graph of the hypergraph 1470 @rtype: L{UGraph} 1471 """ 1472 import Graphs 1473 rg = Graphs.UGraph(self._hyperedges) 1474 for star in self._star.values(): 1475 rg.complete(star) 1476 return rg

1477

1478 - def restriction(self,vertices,inverted=False):

1479 """Restrict the hypergraph to contain only C{vertices} 1480 1481 @param vertices: The vertices to restrict the hypergraph to, 1482 unless C{inverted=True} in which case the vertices to remove. 1483 @type vertices: Iterable 1484 @param inverted: Whether to remove C{vertices} 1485 @type inverted: Boolean 1486 @return: New hyperedges produced 1487 @rtype: List 1488 """ 1489 if inverted: 1490 going = vertices 1491 staying = self.vertices().difference(vertices) 1492 else: 1493 staying = frozenset(vertices) 1494 going = self.vertices() - staying 1495 done = set() 1496 smallers = [] 1497 for v in going: 1498 try: 1499 for h in self._star[v] - done: 1500 smaller = h & staying 1501 done.add(h) 1502 smallers.append(smaller) 1503 self.remove_hyperedge(h) 1504 self.add_hyperedge(smaller) 1505 except KeyError: 1506 pass 1507 return smallers

1508

1509 - def simplify(self):

1510 """Simplify a hypergraph 1511 1512 Returning repeated hyperedges deleted 1513 1514 @return: Repeated hyperedges 1515 @rtype: list of frozensets 1516 """ 1517 reps = [] 1518 try: 1519 for hyperedge, rep in self._extras.items(): 1520 reps.extend([hyperedge]*rep) 1521 del self._extras 1522 except AttributeError: 1523 pass 1524 return reps

1525 1526 size = __len__ 1527

1528 - def star(self,vertex):

1529 """Return the star of C{vertex}: the set of hyperedges which contain C{vertex} 1530 1531 Altering the returned set B{will not} alter the hypergraph. 1532 Note that a set object is returned, not a hypergraph object. 1533 1534 @param vertex: The vertex whose star is sought 1535 @type vertex: String 1536 @return: The star of C{vertex}: the hyperedges each of which contain C{vertex} 1537 @rtype: Set 1538 @raise KeyError: If C{vertex} is not in the (hyper)graph 1539 """ 1540 return self._star[vertex].copy()

1541 1542

1543 - def star_size(self,vertex):

1544 """Return a count of the number of distinct hyperedges containing a vertex 1545 1546 @param vertex: The vertex for which containing hyperedges are sought 1547 @type vertex: String 1548 @return: The number of hyperedges each of which contain C{vertex} 1549 @rtype: Int 1550 @raise KeyError: If C{vertex} is not in the (hyper)graph 1551 """ 1552 return len(self._star[vertex])

1553

1554 - def stars(self,vertices):

1555 """Return the hyperedges each of which contain at 1556 least one vertex in C{vertices} 1557 1558 @param vertices: The vertices for which containing hyperedges are sought 1559 @type vertices: Sequence 1560 @return: The set of hyperedges each of which contain at least one vertex in C{vertices} 1561 @rtype: Set 1562 @raise KeyError: If C{vertices} contains a vertex not in the (hyper)graph 1563 """ 1564 hyperedges = set() 1565 for vertex in vertices: 1566 hyperedges.update(self._star[vertex]) 1567 return hyperedges

1568 1569

1570 - def two_section(self):

1571 """Return the 2-section of a hypergraph 1572 1573 This graph contains an undirected edge for any pair of distinct vertices 1574 which are both members of a hyperedge. 1575 @return: The interaction graph 1576 @rtype: L{UGraph} 1577 """ 1578 import Graphs 1579 ig = Graphs.UGraph() 1580 for hyperedge in self._hyperedges: 1581 ig.add_clique(hyperedge) 1582 return ig

1583

1584 - def vertices(self):

1585 """Return the vertices (base set) of the hypergraph 1586 1587 @return: The vertices (base set) of the hypergraph 1588 @rtype: Set 1589 """ 1590 return set(self._star)

1591

1592 - def would_be_redundant(self,hyperedge):

1593 """Whether C{hyperedge} would be redundant if it 1594 were added to the hypergraph 1595 1596 If C{hyperedge} is already in the hypergraph it is considered 1597 that it would be redundant if added. 1598 1599 @param hyperedge: A potential hyperedge 1600 @type hyperedge: Iterable 1601 """ 1602 if not hyperedge: 1603 if self._hyperedges: 1604 return True 1605 else: 1606 return False 1607 for vertex in hyperedge: 1608 try: 1609 try: 1610 cs.intersection_update( 1611 self._star[vertex]) 1612 if not cs: 1613 return False 1614 except NameError: 1615 cs = self._star[vertex].copy() 1616 except KeyError: 1617 return False 1618 return True

1619 1620

1621 - def _add_hyperedge(self,hyperedge):

1622 """add a hyperedge known to be new""" 1623 self._hyperedges.add(hyperedge) 1624 for vertex in hyperedge: 1625 try: 1626 self._star[vertex].add(hyperedge) 1627 except KeyError: # new vertex 1628 self._star[vertex] = set([hyperedge])

1629

1630 -class SimpleHypergraph(Hypergraph):

1631 """A simple hypergraph has no repeated hyperedges and thus is a B{set} of hyperedges. 1632 """ 1633

1634 - def __init__(self,hypergraph=(),check=True,modify=False):

1635 """Initialise a simple hypergraph 1636 1637 @param hypergraph: Hypergraph/hyperedges used to generate new simple hypergraph 1638 @type hypergraph: L{Hypergraph} or iterable of iterables 1639 @param check: In the case that C{modify=False}, whether to check that 1640 C{hypergraph} is simple 1641 @type check: Boolean 1642 @param modify: Whether C{hypergraph} is to modified to be made simple 1643 @type modify: Boolean 1644 @raise TypeError: If C{hyperedges} is not of the right form. 1645 @raise ValueError: If C{hyperedges} contains repeats. 1646 """ 1647 if not isinstance(hypergraph,Hypergraph): 1648 hypergraph = Hypergraph(hypergraph) 1649 if hasattr(hypergraph,'_extras'): 1650 if modify: 1651 del hypergraph._extras 1652 elif check: 1653 raise ValueError( 1654 "Can't make a simple hypergraph because these hyperedges: %s are repeated this many times: %s, respectively" % 1655 (self._extras.keys(),self._extras.values())) 1656 self.__dict__ = hypergraph.__dict__

1657

1658 - def __str__(self):

1659 """Return pretty representation of a hypergraph 1660 1661 @return: Pretty representation of a hypergraph 1662 @rtype: String 1663 """ 1664 return '{ %s }' % ', '.join( 1665 [pretty_str_set(hyperedge) for hyperedge in self._hyperedges] 1666 )

1667

1668 - def add_hyperedge(self,hyperedge):

1669 """Add a hyperedge to a simple hypergraph 1670 1671 @param hyperedge: The vertices in the hyperedge 1672 @type hyperedge: Iterable 1673 @raise ValueError: If C{hyperedge} already in hypergraph 1674 """ 1675 hyperedge = frozenset(hyperedge) 1676 if hyperedge in self._hyperedges: 1677 raise ValueError('%s already in hypergraph' % hyperedge) 1678 else: 1679 Hypergraph._add_hyperedge(self,hyperedge)

1680

1681 -class ReducedHypergraph(SimpleHypergraph):

1682 """Hypergraphs without redundant hyperedges 1683 """ 1684

1685 - def __init__(self,hypergraph=(),check=True,modify=False,trace=False):

1686 """Initialise a reduced hypergraph 1687 1688 If C{hypergraph} is indeed a hypergraph then the new 1689 L{ReducedHypergraph} object has identical attributes to 1690 C{hypergraph}. 1691 1692 If C{hypergraph} is not a hypergraph then it is assumed to be 1693 a collection of hyperedges, a C{Hypergraph} object is created 1694 from these hyperedges as the first step of construction and 1695 execution proceeds exactly as if this C{Hypergraph} object had 1696 been the original value of C{hypergraph}. The default value 1697 for C{hypergraph} constructs is an empty C{ReducedHypergraph}). 1698 1699 @param hypergraph: Hypergraph/hyperedges used to generate new reduced hypergraph 1700 @type hypergraph: L{Hypergraph} or iterable of iterables 1701 @param check: In the case that C{modify=False}, whether to check that 1702 C{hypergraph} is reduced 1703 @type check: Boolean 1704 @param modify: Whether C{hypergraph} is to modified to be made reduced 1705 @type modify: Boolean 1706 @param trace: In the case where C{modify=True} whether a mapping 1707 from removed redundant hyperedges to the set of hyperedges containing them 1708 should be created. If so, it is stored in a C{trace} attribute of C{self} 1709 @type trace: Boolean 1710 @raise RedundancyError: If C{check=True,modify=False} and C{hypergraph} is not reduced. 1711 @raise TypeError: If C{hypergraph} is not a hypergraph or an iterable of 1712 hyperedges. 1713 """ 1714 if not isinstance(hypergraph,Hypergraph): 1715 hypergraph = Hypergraph(hypergraph) 1716 if modify: 1717 reds = hypergraph.redundant_hyperedges() 1718 for red in reds: 1719 hypergraph.remove_hyperedge(red) 1720 if trace: 1721 hypergraph.trace = reds 1722 elif check and not hypergraph.is_reduced(): 1723 for h in hypergraph: 1724 if hypergraph.is_redundant(h): 1725 break 1726 raise RedundancyError("%s is not reduced due to %s" % (hypergraph,h)) 1727 self.__dict__ = hypergraph.__dict__

1728 1729

1730 - def add_hyperedge(self,hyperedge,check=True):

1731 """Add a hyperedge 1732 1733 @param hyperedge: The vertices in the hyperedge 1734 @type hyperedge: Frozenset 1735 @param check: Whether to check that adding C{hyperedge} does not introduce redundancy 1736 @type check: Boolean 1737 @raise RedundancyError: If C{check} is True and adding C{hyperedge} would render the 1738 hypergraph no longer reduced. 1739 """ 1740 if check and self.makes_unreduced(hyperedge): 1741 raise RedundancyError("Adding %s would make %s no longer reduced" % 1742 (pretty_str_set(hyperedge),self)) 1743 Hypergraph.add_hyperedge(self,hyperedge)

1744

1745 - def is_graphical(self):

1746 return self == self.two_section().hypergraph()

1747 1748 # def red(self): 1749 # return 1750 1751 # def reduced(self): 1752 # return self.copy() 1753

1754 - def is_reduced(self):

1755 return True

1756

1757 - def reduction(self):

1758 """Apply the 'Reduction Algorithm' of Tarjan and Yannakakis 1759 1760 SIAM J Computing 13 (1984) 566-579 1761 On return C{self} will be the I{reduction} of the original C{self}. 1762 Despite the name, this is not the same as reducing the hypergraph by 1763 removing redundant hyperedges. 1764 @return: The removed hyperedges 1765 @rtype: List 1766 """ 1767 removed = [] 1768 while True: 1769 for vertex, hyperedges in self._star.items(): 1770 if len(hyperedges) == 1: 1771 hyperedge = member(hyperedges) # only 1 member 1772 self.remove_hyperedge(hyperedge) 1773 new_hyperedge = hyperedge - set([vertex]) 1774 try: 1775 self.add_hyperedge(new_hyperedge) 1776 except RedundancyError: 1777 removed.append(new_hyperedge) 1778 break 1779 else: 1780 return removed

1781

1782 - def redundant_hyperedges(self):

1783 return {}

1784 1785

1786 -class GraphicalHypergraph(Hypergraph):

1787 """For a hypergraph H to be I{graphical}, the hyperedges of red(H) must be the cliques of 1788 an (undirected) graph. 1789 """

1790 - def __init__(self,hypergraph=(),check=True):

1791 """Initialise a graphical hypergraph 1792 1793 If C{hypergraph} is indeed a hypergraph then the new 1794 L{GraphicalHypergraph} object has identical attributes to 1795 C{hypergraph}. 1796 1797 If C{hypergraph} is not a hypergraph then it is assumed to be 1798 a collection of hyperedges, a C{Hypergraph} object is created 1799 from these hyperedges as the first step of construction and 1800 execution proceeds exactly as if this C{Hypergraph} object had 1801 been the original value of C{hypergraph}. The default value 1802 for C{hypergraph} constructs is an empty C{GraphicalHypergraph}). 1803 1804 @param hypergraph: Hypergraph/hyperedges used to generate new graphical hypergraph 1805 @type hypergraph: L{Hypergraph} or iterable of iterables 1806 @param check: Whether to check that C{hypergraph} is reduced and graphical 1807 @type check: Boolean 1808 @raise GraphicalityError: If C{hypergraph} is not graphical. 1809 @raise TypeError: If C{hypergraph} is not a hypergraph or an iterable of 1810 hyperedges. 1811 """ 1812 if not isinstance(hypergraph,Hypergraph): 1813 hypergraph = Hypergraph(hypergraph) 1814 if check and not hypergraph.is_graphical(): 1815 raise GraphicalityError("%s is not graphical" % hypergraph) 1816 self.__dict__ = hypergraph.__dict__

1817

1818 - def is_graphical(self):

1819 return True

1820 1821

1822 -class ReducedGraphicalHypergraph(GraphicalHypergraph,ReducedHypergraph):

1823 """For a hypergraph H to be I{graphical}, the hyperedges of red(H) must be the cliques of 1824 an (undirected) graph. 1825 1826 A ReducedGraphicalHypergraph object is both reduced and graphical so its 1827 hyperedges are the cliques of an (undirected) graph. 1828 """

1829 - def __init__(self,hypergraph=(),check=True):

1830 """Initialise a graphical reduced hypergraph 1831 1832 If C{hypergraph} is indeed a hypergraph then the new 1833 L{ReducedGraphicalHypergraph} object has identical attributes to 1834 C{hypergraph}. 1835 1836 If C{hypergraph} is not a hypergraph then it is assumed to be 1837 a collection of hyperedges, a C{Hypergraph} object is created 1838 from these hyperedges as the first step of construction and 1839 execution proceeds exactly as if this C{Hypergraph} object had 1840 been the original value of C{hypergraph}. The default value 1841 for C{hypergraph} constructs is an empty C{ReducedGraphicalHypergraph}). 1842 1843 @param hypergraph: Hypergraph/hyperedges used to generate new reduced 1844 graphical hypergraph 1845 @type hypergraph: L{Hypergraph} or iterable of iterables 1846 @param check: Whether to check that C{hypergraph} is reduced and graphical 1847 @type check: Boolean 1848 @raise RedundancyError: If C{check=True} and C{hypergraph} is not reduced. 1849 @raise GraphicalityError: If C{check=True} and C{hypergraph} is not graphical. 1850 """ 1851 if not isinstance(hypergraph,Hypergraph): 1852 hypergraph = Hypergraph(hypergraph) 1853 if check: 1854 if not hypergraph.is_reduced(): 1855 raise RedundancyError("%s is not reduced" % hypergraph) 1856 if not hypergraph.is_graphical(): 1857 raise GraphicalityError("%s is not graphical" % hypergraph) 1858 self.__dict__ = hypergraph.__dict__

1859 1860 1861

1862 -class DecomposableHypergraph(GraphicalHypergraph):

1863 """For a graphical hypergraph to be I{decomposable}, the 1864 hyperedges of red(H) must be the cliques of some (undirected) 1865 B{decomposable} graph. 1866 1867 """

1868 - def __init__(self,hypergraph=(),check=True,modify=False, 1869 trace=False,elimination_order=None):

1870 """Initialise a decomposable hypergraph 1871 1872 If C{hypergraph} is indeed a hypergraph then the new 1873 L{DecomposableHypergraph} object has identical attributes to 1874 C{hypergraph}. 1875 1876 If C{hypergraph} is not a hypergraph then it is assumed to be 1877 a collection of hyperedges, a C{Hypergraph} object is created 1878 from these hyperedges as the first step of construction and 1879 execution proceeds exactly as if this C{Hypergraph} object had 1880 been the original value of C{hypergraph}. The default value 1881 for C{hypergraph} constructs is an empty C{DecomposableHypergraph}). 1882 1883 @param hypergraph: Hypergraph/hyperedges used to generate new 1884 decomposable hypergraph 1885 @type hypergraph: L{Hypergraph} or iterable of iterables 1886 @param check: In the case that C{modify=False}, whether to check that 1887 C{hypergraph} is decomposable 1888 @type check: Boolean 1889 @param modify: Whether C{hypergraph} is to be modified to be made decomposable 1890 @type modify: Boolean 1891 @param trace: In the case where C{modify=True} whether a mapping 1892 from each hyperedge to the new hyperedge into which it has been merged 1893 should be created. If so, it is stored in a C{trace} attribute of C{self} 1894 @type trace: Boolean 1895 @param elimination_order: If supplied 1896 and C{modify=True}, the elimination order to use to make the C{hypergraph} 1897 decomposable. (If not supplied maximum cardinality search is used to generate an order.) 1898 @type elimination_order: Sequence 1899 @raise DecomposabilityError: If C{check=True,modify=False} and C{hypergraph} 1900 is not decomposable. 1901 """ 1902 if not isinstance(hypergraph,Hypergraph): 1903 hypergraph = Hypergraph(hypergraph) 1904 if check or modify: 1905 JoinForest(hypergraph,modify,trace,elimination_order) 1906 del hypergraph._uforest 1907 self.__dict__ = hypergraph.__dict__

1908

1909 - def is_decomposable(self):

1910 return True

1911 1912 # def __init__(self,hypergraph,elimination_ordering=None,force=False): 1913 # """Construct a decomposable hypergraph from an existing hypergraph 1914 1915 # If C{force} is C{False} then the assumption is that C{hypergraph} 1916 # is decomposable and it will be the constructed decomposable hypergraph. 1917 # If C{force} is C{True} then a new decomposable hypergraph is created by merging 1918 # hyperedges in C{hypergraph} 1919 1920 # If C{elimination_ordering} is given it is ... 1921 # """ 1922 # self._hyperedges = set() 1923 # self._star = {} 1924 # if elimination_ordering is None: 1925 # if force: 1926 # elimination_ordering = self.find_elimination_ordering_force(hypergraph,[]) 1927 # else: 1928 # elimination_ordering = self.find_elimnation_ordering_no_force(hypergraph,[]) 1929 # else: 1930 # if force: 1931 # self.use_ordering_force(hypergraph,elimination_ordering) 1932 # else: 1933 # self.use_ordering_no_force(hypergraph,elimination_ordering) 1934 # self._elimination_ordering = tuple(elimination_ordering) 1935 1936 # def find_elimination_ordering(self,hypergraph,order_prefix,force): 1937 # pass 1938 1939 # def use_ordering_no_force(self,hypergraph,elimination_ordering): 1940 # if not elimination_ordering: 1941 # return 1942 # vertex = elimination_ordering.pop(0) 1943 # vertex_hyperedges = hypergraph.hyperedges_containing_vertex(vertex) 1944 # if len(vertex_hyperedges) != 1: 1945 # raise ValueError("Vertex %s in more than one hyperedge in %s." % vertex, hypergraph) 1946 # hyperedge = member(vertex_hyperedges) 1947 # hypergraph.remove_hyperedge(hyperedge) 1948 # new_hyperege = hyperedge - set([vertex]) 1949 # if not hypergraph.would_be_redundant(new_hyperedge): 1950 # hypergraph.add_hyperedge(new_hyperedge) 1951 # self.use_ordering_no_force(self,hypergraph,elimination_ordering) 1952

1953 -class ReducedDecomposableHypergraph(DecomposableHypergraph,ReducedGraphicalHypergraph):

1954 """For a graphical hypergraph to be I{decomposable}, and 1955 I{reduced} the hyperedges of H must be the cliques of some 1956 (undirected) B{decomposable} graph. 1957 """

1958 1959

1960 -class JoinForest(DecomposableHypergraph):

1961 """A L{DecomposableHypergraph} whose hyperedges are the vertices of a join forest 1962 1963 @ivar _uforest: The join forest itself 1964 @type _uforest: L{Graphs.UForest} 1965 #@ivar _elimination_ordering: An elimination ordering consistent with the 1966 #hypergraph's L{_uforest} 1967 #@type _elimination_ordering: Tuple 1968 #@ivar destination: Maps hyperedges in the hypergraph from which the instance was 1969 #created to hyperedges in the instance. Can be deleted without altering the instance. 1970 #@type destination: Dictionary 1971 #@ivar edges: The edges of the instance's L{_uforest} when the instance was 1972 #created. Each edge is a frozenset 1973 #with the two connected cliques as members. Can be deleted without altering the instance. 1974 #@type edges: List 1975 """ 1976

1977 - def __init__(self,hypergraph=(),modify=False, 1978 trace=False,elimination_order=None):

1979 """Construct join forest from a hypergraph 1980 1981 If C{hypergraph} is indeed a hypergraph then the new 1982 L{JoinForest} object has identical attributes to 1983 C{hypergraph} (plus a new one of its own). 1984 1985 If C{hypergraph} is not a hypergraph then it is assumed to be 1986 a collection of hyperedges, a C{Hypergraph} object is created 1987 from these hyperedges as the first step of construction and 1988 execution proceeds exactly as if this C{Hypergraph} object had 1989 been the original value of C{hypergraph}. The default value 1990 for C{hypergraph} constructs an empty C{JoinForest}). 1991 1992 @param hypergraph: Hypergraph/hyperedges used to generate new 1993 join forest 1994 @type hypergraph: L{Hypergraph} or iterable of iterables 1995 @param modify: Whether C{hypergraph} is to modified to be made decomposable 1996 @type modify: Boolean 1997 @param trace: In the case where C{modify=True} whether a mapping 1998 from each hyperedge to the new hyperedge into which it has been merged 1999 should be created. If so, it is stored in a C{trace} attribute of C{self} 2000 @type trace: Boolean 2001 @param elimination_order: If supplied 2002 and C{modify=True}, the elimination order to use to make the C{hypergraph} 2003 decomposable. (If not supplied maximum cardinality search is used to generate an order.) 2004 @type elimination_order: Sequence 2005 @raise DecomposabilityError: If C{modify=False} and C{hypergraph} is not decomposable. 2006 """ 2007 if not isinstance(hypergraph,Hypergraph): 2008 hypergraph = Hypergraph(hypergraph) 2009 if modify: 2010 # would be better to make join forest here 2011 dg, trace_dict = hypergraph.make_decomposable2(elimination_order) 2012 hypergraph.__dict__ = dg.__dict__ 2013 if trace: 2014 hypergraph.trace = trace_dict 2015 hypergraph._uforest = hypergraph.join_forest() 2016 self.__dict__ = hypergraph.__dict__

2017

2018 - def __str__(self):

2019 forest_str = str(self._uforest) 2020 for hyperedge in self._hyperedges: 2021 forest_str = forest_str.replace(str(hyperedge),pretty_str_set(hyperedge)) 2022 return '%s\n%s' % (Hypergraph.__str__(self),forest_str)

2023

2024 - def copy(self):

2025 cp = JoinForest() 2026 cp._hyperedges.update(self._hyperedges) 2027 for vertex, hyperedges in self._star.items(): 2028 cp._star[vertex] = hyperedges.copy() 2029 cp._uforest = self._uforest.copy() 2030 return cp

2031

2032 - def join_forest(self):

2033 return self._uforest

2034 2035 # self._hyperedges = hypergraph._hyperedges 2036 # self._star = hypergraph._star 2037 # self._elimination_ordering = hypergraph._elimination_ordering 2038 # join_forest = UForest(self._hyperedges) 2039 # tmp_hypergraph = hypergraph.copy() 2040 # orig = {} 2041 # for hyperedge in hypergraph: 2042 # orig[hyperedge] = hyperedge 2043 # elimination_ordering = list(hypergraph._elimination_ordering) 2044 # while elimination_ordering: 2045 # vertex_hyperedge = member(tmp_hypergraph.hyperedges_containing_vertex(vertex)) 2046 # tmp_hypergraph.remove_hyperedge(vertex_hyperedge) 2047 # new_hyperedge = vertex_hyperedge - set([vertex]) 2048 # superset = hypergraph.superset(new_hyperedge) 2049 # if superset: 2050 # join_forest.put_line(orig[vertex_hyperedge],orig[superset]) 2051 # else: 2052 # orig[new_hyperedge] = orig[vertex_hyperedge] 2053 # tmp_hypergraph.add_hyperedge(new_hyperedge) 2054 # del orig[vertex_hyperedge] 2055 # self._uforest = join_forest 2056 2057 2058 # def __init__(self,hypergraph,variables): 2059 # """ 2060 # Construct a join forest from an arbitrary hypergraph 2061 # and an elimination ordering 2062 2063 # @param hypergraph: Generating hypergraph 2064 # @type hypergraph: L{Hypergraph} 2065 # @param variables: Elimination ordering 2066 # @type variables: Sequence 2067 # @raise ValueError: If C{variables} is not an ordering of the vertices in C{hypergraph} 2068 # """ 2069 # if sorted(variables) != sorted(hypergraph.vertices()): 2070 # raise ValueError("%s not an ordering of %s" % (variables,hypergraph.vertices())) 2071 # DecomposableHypergraph.__init__(self) 2072 # uf = UForest() 2073 # frm = {} 2074 # destination = {} 2075 # edges = [] 2076 # for variable in variables: 2077 # clique = set() 2078 # hyperedges = hypergraph.hyperedges_containing_vertex(variable) 2079 # for hyperedge in hyperedges: 2080 # clique.update(hyperedge) 2081 # hypergraph.remove_hyperedge(hyperedge) 2082 2083 # messages = hyperedges.intersection(frm) 2084 # container = None 2085 # for msg in messages: 2086 # if clique <= msg: 2087 # clique = frm[msg][0] 2088 # container = msg 2089 # break 2090 # if container is None: 2091 # clique = frozenset(clique) 2092 # self.add_hyperedge(clique,check=False) 2093 # uf.add_vertex(clique) 2094 # else: 2095 # messages.remove(container) 2096 2097 # hyperedges.difference_update(messages) 2098 # for original_hyperedge in hyperedges: 2099 # destination[original_hyperedge] = clique 2100 2101 # for msg in messages: 2102 # for sender in frm[msg]: 2103 # uf.put_line(sender,clique) 2104 # edges.append(frozenset([sender,clique])) 2105 # del frm[msg] 2106 2107 # new_msg = clique - set([variable]) 2108 # if new_msg: 2109 # hypergraph.add_hyperedge(new_msg) 2110 # try: 2111 # frm[new_msg].append(clique) 2112 # except KeyError: 2113 # frm[new_msg] = [clique] 2114 # self._uforest = uf 2115 # self._elimination_ordering = tuple(variables) 2116 # self.destination = destination 2117 # self.edges = edges 2118

2119 - def clique(self):

2120 """Return an arbitrary clique 2121 2122 @return: An arbitrary clique 2123 @rtype: Frozenset 2124 """ 2125 for clique in self._hyperedges: 2126 return clique

2127

2128 - def clique_neighbours(self,clique,banned=emptyset):

2129 """Return neighbours of a clique in the join forest 2130 2131 Excludes the cliques in C{banned} 2132 @param clique: Cliques whose neighbours are sought 2133 @type clique: Frozenset 2134 @param banned: Neighbours to exclude from result 2135 @type banned: set or frozenset 2136 """ 2137 return self._uforest.neighbours(clique) - banned

2138

2139 - def perfect_sequence(self,root=None):

2140 """Return an ordering of the cliques obeying the running intersection 2141 property 2142 2143 @param root: A root hyperedge for the ordering; it will be the 2144 first element of the returned ordering. If not supplied, it is chosen 2145 arbitrarily. 2146 @type root: An iterable 2147 @return: An ordering of the cliques obeying the running intersection 2148 property 2149 @rtype: List 2150 @raise ValueError: If C{root} is supplied but not in join forest. 2151 """ 2152 unnumbered = self._hyperedges.copy() 2153 sequence = [] 2154 if root is not None: 2155 root = frozenset(root) 2156 if root not in unnumbered: 2157 raise ValueError("Root %s not in join forest") 2158 while unnumbered: 2159 if root is None: 2160 root = unnumbered.pop() 2161 else: 2162 unnumbered.remove(root) 2163 frontier = set([root]) 2164 sequence.append(root) 2165 while frontier: 2166 clique = frontier.pop() 2167 for nbr in self._uforest.neighbours(clique) & unnumbered: 2168 sequence.append(nbr) 2169 unnumbered.remove(nbr) 2170 frontier.add(nbr) 2171 root = None 2172 return sequence

2173

2174 -class ReducedJoinForest(JoinForest,ReducedDecomposableHypergraph):

2175 """A L{ReducedDecomposableHypergraph} whose hyperedges are the vertices of a join forest 2176 """

2177 - def __str__(self):

2178 forest_str = str(self._uforest) 2179 for hyperedge in self._hyperedges: 2180 forest_str = forest_str.replace(str(hyperedge),pretty_str_set(hyperedge)) 2181 return '%s\n%s' % (ReducedHypergraph.__str__(self),forest_str)

2182 2183 2184 2185 # def grahams2(self): 2186 # """Run Graham's algorithm on a hypergraph 2187 2188 # If the hypergraph is decomposable then upon return C{self} is either 2189 # empty or contains a single empty hyperedge. 2190 # """ 2191 # if self.is_empty(): 2192 # return self 2193 2194 # self.red() 2195 2196 # cardinality = {} 2197 # sets = [set()] 2198 # max = 0 2199 # for vertex, star in self._star.items(): 2200 # card = len(star) - 1 2201 # cardinality[vertex] = card 2202 # if card > max: 2203 # for i in range(card-max): 2204 # sets.append(set()) 2205 # max = card 2206 # sets[card].add(vertex) 2207 2208 # while sets[0] != set(): 2209 # for vertex in sets[0]: 2210 # self.remove_vertex(vertex) 2211 # sets[0] = set() 2212 # for redundant_hyperedge in self.red(): 2213 # for vertex in redundant_hyperedge: 2214 # card = cardinality[vertex] 2215 # sets[card].remove(vertex) 2216 # card -= 1 2217 # cardinality[vertex] = card 2218 # sets[card].add(vertex) 2219 # return self 2220 2221 # def is_decomposable(self): 2222 # """Return whether the hypergraph is decomposable 2223 2224 # @return: Whether the hypergraph is decomposable 2225 # @rtype: Boolean 2226 # @todo: Implement efficiently 2227 # """ 2228 # if self._hyperedges == set(): 2229 # return True 2230 # try: 2231 # ReducedHyperGraph(self,modify=True).join_forest() 2232 # return True 2233 # except DecomposabilityError: 2234 # return False 2235 2236 # def join_forest(self): 2237 # """Return a join forest graph, assuming decomposability 2238 2239 # Uses L{maximum_cardinality_search}. See that method for bibliographical 2240 # references. 2241 # @return: A join forest graph 2242 # @rtype: L{UForest} 2243 # @raise RedundancyError: If hypergraph is not reduced 2244 # @raise DecomposabilityError: If hypergraph is reduced but not decomposable 2245 # """ 2246 # alpha, beta, gamma, inv_gamma, r = self.maximum_cardinality_search() 2247 # index = {} 2248 # for i, hyperedge in enumerate(r): 2249 # for other in inv_gamma[i]: 2250 # for vertex in other: 2251 # if beta[vertex] < i and vertex not in hyperedge: 2252 # raise DecomposabilityError("%s is not decomposable" % self) 2253 # join_forest = UForest(self._hyperedges) 2254 # for hyperedge in self._hyperedges: 2255 # try: 2256 # join_forest.put_line(hyperedge,r[gamma[hyperedge]]) 2257 # except KeyError: 2258 # pass 2259 # return join_forest 2260 2261 # def make_reduced(self): 2262 # """Reduce the hypergraph and make it 2263 # a L{ReducedHyperGraph} object 2264 2265 # @return: Set of superset hyperedges for each redundant hyperedge 2266 # @rtype: Dictionary 2267 # """ 2268 # supersets = self.redundant_hyperedges() 2269 # for redundant_hyperedge in supersets: 2270 # self.remove_hyperedge(redundant_hyperedge) 2271 # self.__class__ = ReducedHyperGraph 2272 # return supersets 2273 2274 # def maximum_cardinality_search(self,choose=None): 2275 # """Return maximum cardinality search 2276 2277 # This is 'Restricted Maximum Cardinality Search on Hypergraphs' as presented in the 2278 # reference below. Note there are two errors in the algorithm as presented there: '.. i:=i+1' 2279 # should be '..i:=i-1' on line 9. Also the 'j:=j+1' statement near the end needs to be moved 2280 # into the loop over vertices to ensure it is big enough. 2281 2282 # Ref:: 2283 2284 # @Article{tarjan84:_simpl, 2285 # author = {Robert E. Tarjan and Mihalis Yannakakis}, 2286 # title = {Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, 2287 # journal = {{SIAM} Journal of Computing}, 2288 # year = 1984, 2289 # volume = 13, 2290 # number = 3, 2291 # pages = {566--579}, 2292 # month = {August} 2293 2294 # Returns C{(alpha, beta, gamma, inv_gamma, r)} where 2295 # - C{alpha} is a dictionary mapping each vertex to its index in the generated vertex ordering. 2296 # Note that the first vertex to be numbered comes I{last} in this ordering. 2297 # Note that here the lowest index is 0, not 1 as in the original presentation 2298 # - C{beta} is a dictionary mapping each hyperedge to its index in generated hyperedge ordering. 2299 # Note that the first hyperedge to be numbered comes I{first} in this ordering. 2300 # C{beta} also maps each I{vertex} C{v} to 2301 # min {beta[hyperedge] : hyperedge gets 'selected' and v in hyperedge} 2302 # Note that beta[v] < beta[w] implies alpha[v] > alpha[w] 2303 # Note that here the lowest index is 0, not 1 as in the original presentation 2304 # - C{gamma} is a dictionary mapping hyperedges as follows: 2305 # - If a hyperedge is not selected then gamma[hyperedge] = max{beta[v]:v in hyperedge} 2306 # - If a hyperedge is selected then 2307 # gamma[hyperedge] = max{beta[v]:v in hyperedge and beta[v] < beta[hyperedge]} 2308 # if this is defined 2309 # - C{inv_gamma} is just a list representing the inverse mapping to C{gamma} 2310 # - C{r} is the generated hyperedge ordering (inverse of C{beta}) 2311 2312 # @param choose: Function for choosing between hyperedges with an equally high number of numbered vertices. 2313 # If unsupplied the choice is arbitrary. 2314 # @type choose: A function which removes and returns an element from a set. 2315 # @return: C{(alpha, beta, gamma, inv_gamma, r)} where these have the same meanings as in reference above. 2316 # C{inv_gamma} is just the mapping gamma inverted. 2317 # @rtype: Tuple 2318 # @raise RedundancyError: If hypergraph is not reduced 2319 # """ 2320 # if not self.is_reduced(): 2321 # raise RedundancyError("%s is not reduced" % self) 2322 2323 # if choose is None: 2324 # def choose(set): return set.pop() 2325 2326 # n = len(self._star) 2327 # sets = [] 2328 # for i in range(n+1): 2329 # sets.append(set()) 2330 # cardinality = {} 2331 # inv_gamma = [] 2332 # for hyperedge in self._hyperedges: 2333 # cardinality[hyperedge] = 0 2334 # inv_gamma.append(set()) 2335 # sets[0] |= self._hyperedges 2336 # alpha, beta, gamma = {}, {}, {} 2337 # i, j, k = n, 0, -1 2338 # r = [] 2339 2340 # while j >= 0 and sets[j]: # 'and sets[j] for empty hypergraphs' 2341 # hyperedge = choose(sets[j]) 2342 # k += 1 2343 2344 # beta[hyperedge] = k 2345 # r.append(hyperedge) 2346 # del cardinality[hyperedge] 2347 2348 # for vertex in hyperedge.difference(alpha): 2349 # i -= 1 2350 2351 # alpha[vertex] = i 2352 # beta[vertex] = k 2353 2354 # for other_hyperedge in self._star[vertex].intersection(cardinality): 2355 # gamma[other_hyperedge] = k 2356 # inv_gamma[k].add(other_hyperedge) 2357 2358 # card = cardinality[other_hyperedge] 2359 # sets[card].remove(other_hyperedge) 2360 # card += 1 2361 # cardinality[other_hyperedge] = card 2362 2363 # if card < len(other_hyperedge): 2364 # sets[card].add(other_hyperedge) 2365 # else: 2366 # del cardinality[other_hyperedge] 2367 # j += 1 2368 # while j >= 0 and not sets[j]: 2369 # j -= 1 2370 # return alpha, beta, gamma, inv_gamma, r 2371 2372 # w < v, v < z => w < z 2373 # same as v < z, z < w => v < w 2374 #clause = (ord_atom[v,w],-ord_atom[v,z],ord_atom[w,z]) 2375 #hard_clauses.append(clause) 2376 #if comments: 2377 # print >> fobj, 'c Clause %s since %s < %s & %s < %s => %s < %s' % ( 2378 # clause, w,v,v,z,w,z) 2379 # w < z, z < v => w < v 2380 # same as 2381 # v < w, w < z => v < z 2382 #clause = (-ord_atom[w,z],ord_atom[v,z],-ord_atom[v,w]) 2383 #hard_clauses.append(clause) 2384 #if comments: 2385 # print >> fobj, 'c Clause %s since %s < %s & %s < %s => %s < %s' % ( 2386 # clause, w,v,v,z,w,z) 2387 # z < v, v < w => z < w 2388 # same as v < w, w < z => v < z 2389 #clause = (ord_atom[v,z],-ord_atom[v,w],-ord_atom[w,z]) 2390 #hard_clauses.append(clause) 2391 #if comments: 2392 # print >> fobj, 'c Clause %s since %s < %s & %s < %s => %s < %s' % ( 2393 # clause, w,v,v,z,w,z) 2394 # z < w, w < v => z < v 2395 #clause = (ord_atom[w,z],ord_atom[v,w],-ord_atom[v,z]) 2396

Source Code for Module gPy.Hypergraphs