[frames] | no frames]

# Class Hypergraph

source code

A hypergraph is a collection of hyperedges. A hyperedge is a set of vertices.

The base set is defined implicitly as the union of the hyperedges.

 Instance Methods

 __init__(self, hyperedges=`(``)`) Initialise a hypergraph source code
Boolean
 __contains__(self, hyperedge) Return whether a hyperedge is in the hypergraph source code
Boolean
 __eq__(self, other) Return whether `self` and `other` are identical hypergraphs (not merely isomorphic) source code
Boolean
 __ge__(self, other) Return whether `self` >= `other` source code
Set
 __getitem__(self, vertex) Return the star of `vertex`: the set of hyperedges which contain `vertex` source code
Iterator
 __iter__(self) Return an iterator over the distinct hyperedges in the hypergraph source code
Boolean
 __le__(self, other) Return whether `self` <= `other` source code
Int
 __len__(self) Return the number of hyperedges in the hypergraph source code
Boolean
 __ne__(self, other) Return whether `self` and `other` are not identical hypergraphs source code
String
 __repr__(self) Return 'official' string representation of the hypergraph source code
String
 __str__(self) Return pretty representation of a hypergraph source code

The same as `self`
 copy(self) Return a deep copy of the hypergraph source code

 discard_hyperedge(self, hyperedge) Remove a hyperedge (and any repetitions), or do nothing if the hyperedge does not exist source code

 discard_hyperedges(self, hyperedges) For each hyperedge in `hyperedges`, remove it (and any repetitions), or do nothing if it does not exist source code

 discard_vertex(self, vertex) Remove `vertex` from the hypergraph, or do nothing if it is not there source code

 discard_vertices(self, vertices) Remove `vertices` from the hypergraph source code

 dual(self) Return the dual of the hypergraph source code

 grahams(self) Run Graham's algorithm on a hypergraph source code

 gui_grahams_algorithm(self, parent, width=400, height=300, **config) source code

 _gui_graham(self, in_only_one, state, cardinality, labels, gc, gcj, varslabel, join_forest, add_to_set) source code
GraphCanvas
 gui_display(self, parent, **config) Display a hypergraph using a GUI source code
List
 hyperedges(self) Return a list of the hyperedges in the hypergraph source code
Boolean
 is_arboreal(self) Return whether the hypergraph is arboreal source code
Boolean
 is_decomposable(self) Return whether the hypergraph is decomposable source code
Boolean
 is_acyclic(self) Return whether the hypergraph is decomposable source code

 is_empty(self) source code
Boolean
 is_graphical(self) Return whether the hypergraph is graphical source code
Boolean
 is_conformal(self) Return whether the hypergraph is graphical source code
Boolean
 is_reduced(self) Test whether a hypergraph is reduced source code
Boolean or set
 is_redundant(self, hyperedge, check=False) Whether `hyperedge` is a redundant hyperedge of the hypergraph source code
Boolean
 is_separating(self) Whether the hypergraph is a separating hypergraph source code
Boolean
 is_simple(self) Test whether a hypergraph is simple source code
ReducedHypergraph
 join(self, hypergraph) Return the join of `self` and `hypergraph` source code
Graphs.UForest
 join_forest(self, choose=None) Return a join forest graph, assuming decomposability source code
Graphs.UForest
 join_forest_ve(self) Return a join forest for the hypergraph using vertex elimination source code
Tuple
 make_decomposable(self, criterion=None) Return a DecomposableHypergraph produced by eliminating variables from `self` using `criterion` source code
Tuple
 make_decomposable2(self, elimination_ordering=None) Return a DecomposableHypergraph produced by eliminating variables from `self` in the order given by `elimination_ordering`. source code

 makes_unreduced(self, hyperedge) True if `hyperedge` is a subset or superset of a hyperedge in the hypergraph ... source code

 matrix(self, sort=False) Return the incidence matrix for a hyperedge source code

 matrix_generate(self, matrix, transpose=False) Add hyperedges, vertices using an incidence matrix source code

 msc_decompcover(self) DON'T USE: STILL BEING WRITTEN source code
`False` or Tuple, a pair of dictionaries
 maximum_cardinality_search(self, choose=None, decomp_check=False) Multiple hyperedges are ignored, so if the hypergraph is non-simple this produces the same result as if multiple hyperedges had been deleted. source code

 merge(self, hyperedges) Replace hyperedges by their union. source code
Int
 multiplicity(self, hyperedge) Return how often `hyperedge` occurs in the hypergraph source code
Set
 neighbours(self, vertex) Return the set of all those vertices each of which is in a hyperedge with `vertex` source code
Int
 order(self) Return the number of vertices in the hypergraph source code
List
 red(self) Reduce the hypergraph source code
Dictionary
 redundant_hyperedges(self, only_redundant=True) Returns a dictionary mapping, by default, each distinct redundant hyperedge to the set of distinct hyperedges which properly contain it. source code

 remove_hyperedge(self, hyperedge) Remove a hyperedge (including any repetitions of it) source code

 remove_hyperedge_once(self, hyperedge) Remove one occurrence of a hyperedge source code

 remove_hyperedges(self, hyperedges) Remove distinct hyperedges source code

 remove_vertex(self, vertex) Remove `vertex` from the hypergraph source code

 remove_vertices(self, vertices) Remove `vertices` from the hypergraph source code
Same class as `self`
 rename_vertices(self, renaming, check=True) Rename the vertices of a hypergraph source code
UGraph
 representative_graph(self) Return the representative graph of a hypergraph source code
List
 restriction(self, vertices, inverted=False) Restrict the hypergraph to contain only `vertices` source code
list of frozensets
 simplify(self) Simplify a hypergraph source code
Int
 size(self) Return the number of hyperedges in the hypergraph source code
Set
 star(self, vertex) Return the star of `vertex`: the set of hyperedges which contain `vertex` source code
Int
 star_size(self, vertex) Return a count of the number of distinct hyperedges containing a vertex source code
Set
 stars(self, vertices) Return the hyperedges each of which contain at least one vertex in `vertices` source code
UGraph
 two_section(self) Return the 2-section of a hypergraph source code
Set
 vertices(self) Return the vertices (base set) of the hypergraph source code

 would_be_redundant(self, hyperedge) Whether `hyperedge` would be redundant if it were added to the hypergraph source code

Inherited from `Incidence`: `reachable`, `separates`

Inherited from `object`: `__delattr__`, `__getattribute__`, `__hash__`, `__new__`, `__reduce__`, `__reduce_ex__`, `__setattr__`

 Instance Variables
Dictionary _extras
If repeated hyperedges exist, maps each repeated hyperedge to the number of times it is repeated.
Set _hyperedges
The distinct hyperedges in the hypergraph.
Dictionary _star
Maps a vertex to the set of hyperedges which contain it.
 Properties

Inherited from `object`: `__class__`

 Method Details

### __init__(self, hyperedges=`(``)`)(Constructor)

source code

Initialise a hypergraph

Parameters:
• `hyperedges` (Iterable of iterables (or Hypergraph)) - Initial hyperedges (or an existing hypergraph)
Raises:
• `TypeError` - If `hyperedges` is not of the right form.
Overrides: object.__init__

### __contains__(self, hyperedge)(In operator)

source code

Return whether a hyperedge is in the hypergraph

Parameters:
• `hyperedge` (Iterable) - hyperedge
Returns: Boolean
Whether `hyperedge` is in the hypergraph

### __eq__(self, other)(Equality operator)

source code

Return whether `self` and `other` are identical hypergraphs (not merely isomorphic)

Irrespective of class

Parameters:
Returns: Boolean
`self` and `other` are identical hypergraphs

### __ge__(self, other)(Greater-than-or-equals operator)

source code

Return whether `self` >= `other`

`self` >= `other` if every hyperedge in `other` is contained in a hyperedge in `self`

Irrespective of class

Parameters:
Returns: Boolean
Whether `self` >= `other`

### __getitem__(self, vertex)(Indexing operator)

source code

Return the star of `vertex`: the set of hyperedges which contain `vertex`

Altering the returned set will alter the hypergraph, so don't do it! A safer option is to use the star method. Note that a set object is returned, not a hypergraph object.

Parameters:
• `vertex` (String) - The vertex whose star is sought
Returns: Set
The star of `vertex`: the hyperedges each of which contain `vertex`
Raises:
• `KeyError` - If `vertex` is not in the (hyper)graph

### __iter__(self)

source code

Return an iterator over the distinct hyperedges in the hypergraph

To allow `for hyperedge in hypergraph: ...` constructions.

Returns: Iterator
An iterator over the distinct hyperedges in the hypergraph

### __le__(self, other)(Less-than-or-equals operator)

source code

Return whether `self` <= `other`

`self` <= `other` if every hyperedge in `self` is contained in a hyperedge in `other`

Irrespective of class

Parameters:
Returns: Boolean
Whether `self` <= `other`

### __len__(self)(Length operator)

source code

Return the number of hyperedges in the hypergraph

Returns: Int
The number of hyperedges in the hypergraph

### __ne__(self, other)

source code

Return whether `self` and `other` are not identical hypergraphs

Irrespective of class

Parameters:
Returns: Boolean
Whether `self` and `other` are not identical hypergraphs

### __repr__(self)(Representation operator)

source code

Return 'official' string representation of the hypergraph

Can be used to construct the hypergraph using e.g. `eval`

Returns: String
The 'official' string representation of the hypergraph
Overrides: object.__repr__

### __str__(self)(Informal representation operator)

source code

Return pretty representation of a hypergraph

Returns: String
Pretty representation of a hypergraph
Overrides: object.__str__

source code

Parameters:
• `hyperedge` (Iterable) - The vertices in the hyperedge

### copy(self)

source code

Return a deep copy of the hypergraph

Returns: The same as `self`
A copy of `self`

source code

Remove a hyperedge (and any repetitions), or do nothing if the hyperedge does not exist

Parameters:
• `hyperedge` (Iterable) - The hyperedge to be removed

source code

For each hyperedge in `hyperedges`, remove it (and any repetitions), or do nothing if it does not exist

Parameters:
• `hyperedges` (Iterable) - Hyperedges to be removed

source code

Remove `vertex` from the hypergraph, or do nothing if it is not there

Parameters:
• `vertex` (String) - The vertex to remove
Raises:
• `RedundancyError` - If `self` is of class ReducedHypergraph (or one of its subclasses) and a redundant hyperedge is produced

source code

Remove `vertices` from the hypergraph

Parameters:
• `vertices` (Iterable) - The vertices to remove
Raises:
• `RedundancyError` - If `self` is of class ReducedHypergraph (or one of its subclasses) and a redundant hyperedge is produced

### dual(self)

source code

Return the dual of the hypergraph

To Do: make more efficient

### grahams(self)

source code

Run Graham's algorithm on a hypergraph

If the hypergraph is decomposable then upon return `self` is either empty or contains a single empty hyperedge.

### gui_display(self, parent, **config)

source code

Display a hypergraph using a GUI

Shows the representative graph

Ignores repeated hyperedges, so not quite accurate for non-simple hypergraphs

Parameters:
• `parent` (Suitable Tkinter widget) - Parent window for GUI
• `config` (Various) - Configuration options for the GUI
Returns: GraphCanvas
The GUI

### hyperedges(self)

source code

Return a list of the hyperedges in the hypergraph

Returns: List
A list of the hyperedges in the hypergraph

### is_arboreal(self)

source code

Return whether the hypergraph is arboreal

A hypergraph is arboreal iff its dual is acyclic (ie decomposable)

Returns: Boolean
Whether the hypergraph is decomposable

### is_decomposable(self)

source code

Return whether the hypergraph is decomposable

Returns: Boolean
Whether the hypergraph is decomposable

### is_acyclic(self)

source code

Return whether the hypergraph is decomposable

Returns: Boolean
Whether the hypergraph is decomposable

### is_graphical(self)

source code

Return whether the hypergraph is graphical

Returns: Boolean
Whether the hypergraph is graphical

To Do: Implement efficiently

### is_conformal(self)

source code

Return whether the hypergraph is graphical

Returns: Boolean
Whether the hypergraph is graphical

To Do: Implement efficiently

### is_reduced(self)

source code

Test whether a hypergraph is reduced

Returns: Boolean
Whether a hypergraph is reduced

### is_redundant(self, hyperedge, check=False)

source code

Whether `hyperedge` is a redundant hyperedge of the hypergraph

Parameters:
• `hyperedge` (Iterable) - Hyperedge
Returns: Boolean or set
False if not redundant, otherwise the set of distinct containing hyperedges
Raises:
• `ValueError` - If `check=True` and `hyperedge` is not in the hypergraph. So this is only really useful for testing the redundancy of existing hyperedges. To test the redundancy of hyperedges which may not already be in the hypergraph use makes_unreduced.

### is_separating(self)

source code

Whether the hypergraph is a separating hypergraph

A hypergraph is separating if, for every vertex v, the intersection of all hyperedges in v's star equals {v}

Returns: Boolean
Whether the hypergraph is a separating hypergraph

### is_simple(self)

source code

Test whether a hypergraph is simple

Returns: Boolean
Whether a hypergraph is simple

### join(self, hypergraph)

source code

Return the join of `self` and `hypergraph`

Returns: ReducedHypergraph
`self ^ hypergraph`

### join_forest(self, choose=None)

source code

Return a join forest graph, assuming decomposability

Any repeated hyperedges are ignored

Uses maximum_cardinality_search. See that method for bibliographical references.

Returns: Graphs.UForest
A join forest graph
Raises:
• `DecomposabilityError` - If hypergraph is not decomposable

### join_forest_ve(self)

source code

Return a join forest for the hypergraph using vertex elimination

Source is annotated. Refs:

``` @TechReport{graham79,
author =      {M. H. Graham},
title =       {On the universal relation},
institution =  {University of Toronto},
year =        1979,
}

@article{322389,
author = {Catriel Beeri and Ronald Fagin and David Maier and Mihalis Yannakakis},
title = {On the Desirability of Acyclic Database Schemes},
journal = {Journal of the  {ACM}},
volume = {30},
number = {3},
year = {1983},
issn = {0004-5411},
pages = {479--513},
doi = {http://doi.acm.org/10.1145/2402.322389},
publisher = {ACM Press},
address = {New York, NY, USA},
}
```
Returns: Graphs.UForest
A join forest for the hypergraph
Raises:
• `RedundancyError` - If hypergraph is not reduced
• `ValueError` - If the hypergraph is reduced but not decomposable

### make_decomposable(self, criterion=None)

source code

Return a DecomposableHypergraph produced by eliminating variables from `self` using `criterion`

Destroys `self` in the process.

Parameters:
• `criterion` (Function) - Function giving criterion for choosing next vertex to eliminate
Returns: Tuple
Decomposable hypergraph, destination dictionary

### make_decomposable2(self, elimination_ordering=None)

source code

Return a DecomposableHypergraph produced by eliminating variables from `self` in the order given by `elimination_ordering`.

Destroys `self` in the process.

If no `elimination_ordering` is given Graphs.UGraph.maximum_cardinality_search is used to provide one.

Parameters:
• `elimination_ordering` (Sequence) - Order in which to eliminate variables
Returns: Tuple
Decomposable hypergraph, destination dictionary

To Do: This is simple but inefficient at present.

### makes_unreduced(self, hyperedge)

source code

True if `hyperedge` is a subset or superset of a hyperedge in the hypergraph ...

... irrespective of whether `self` is already reduced or not

Parameters:
• `hyperedge` (Iterable) - Hyperedge
Returns:
Whether `hyperedge` (would) cause redundancy

### maximum_cardinality_search(self, choose=None, decomp_check=False)

source code

Multiple hyperedges are ignored, so if the hypergraph is non-simple this produces the same result as if multiple hyperedges had been deleted.

Parameters:
• `choose` (A function which removes and returns an element from a set.) - Function for breaking ties when selecting a hyperedge with maximum cardinality. If `None` ties are broken arbitrarily.
• `decomp_check` (Boolean) - If `True` then `False` is returned as soon as it is established that `self` is not decomposable
Returns: `False` or Tuple, a pair of dictionaries
If `decomp_check=True` and `self` is not decomposable then `False` is returned. Otherwise (1) For each selected hyperedge the set of vertices eliminated there and (2) for each hyperedge the hyperedge (if any) which `absorbs' it

### merge(self, hyperedges)

source code

Replace hyperedges by their union.

All repetitions of a hyperedge in `hyperedges` will go.

Parameters:
• `hyperedges` (Iterable) - The hyperedges to merge

### multiplicity(self, hyperedge)

source code

Return how often `hyperedge` occurs in the hypergraph

Returns 0 if `hyperedge` is not in the hypergraph

Parameters:
• `hyperedge` (Iterable) - hyperedge
Returns: Int
How often `hyperedge` occurs in the hypergraph
Raises:
• `KeyError` - If `hyperedge` contains vertices not in the hypergraph

### neighbours(self, vertex)

source code

Return the set of all those vertices each of which is in a hyperedge with `vertex`

`vertex` is not included amongst the neighbours

Parameters:
• `vertex` (String) - The vertex whose neighbours are sought
Returns: Set
Neighbours of `vertex`

### order(self)

source code

Return the number of vertices in the hypergraph

Returns: Int
The number of vertices in the hypergraph

### red(self)

source code

Reduce the hypergraph

Does not change the class of `self`

Any hyperedge contained in another is removed

Returns: List
Any redundant hyperedges

### redundant_hyperedges(self, only_redundant=True)

source code

Returns a dictionary mapping, by default, each distinct redundant hyperedge to the set of distinct hyperedges which properly contain it.

A strictly redundant hyperedge is one properly contained in another

Parameters:
• `only_redundant` (Boolean) - Whether only redundant hyperedges are included as keys in the returned dictionary. If false, non-redundant hyperedges are included and are mapped to the empty set.
Returns: Dictionary
Set of superset hyperedges for each (by default redundant) hyperedge

### remove_hyperedge(self, hyperedge)

source code

Remove a hyperedge (including any repetitions of it)

Parameters:
• `hyperedge` (Iterable) - The hyperedge to be removed
Raises:
• `KeyError` - If `hyperedge` is not in the hypergraph

### remove_hyperedge_once(self, hyperedge)

source code

Remove one occurrence of a hyperedge

If the hyperedge is repeated a repetition is removed.

Parameters:
• `hyperedge` (Iterable) - The hyperedge to be removed
Raises:
• `KeyError` - If `hyperedge` is not in the hypergraph

### remove_hyperedges(self, hyperedges)

source code

Remove distinct hyperedges

Each hyperedge in `hyperedges` is removed together with any repetitions

Parameters:
• `hyperedges` (Sequence) - Distinct hyperedges to be removed
Raises:
• `KeyError` - If some hyperedge in `hyperedges` does not exist

### remove_vertex(self, vertex)

source code

Remove `vertex` from the hypergraph

Parameters:
• `vertex` (String) - The vertex to remove
Raises:
• `KeyError` - If `vertex` is not in the hypergraph
• `RedundancyError` - TOFIX: If `self` is of class ReducedHypergraph (or one of its subclasses) and a redundant hyperedge is produced

### remove_vertices(self, vertices)

source code

Remove `vertices` from the hypergraph

Parameters:
• `vertices` (Set) - The vertices to remove
Raises:
• `KeyError` - If `vertex` is not in the hypergraph
• `RedundancyError` - If `self` is of class ReducedHypergraph (or one of its subclasses) and a redundant hyperedge is produced

### rename_vertices(self, renaming, check=True)

source code

Rename the vertices of a hypergraph

New hypergraph is isomorphic to existing one.

Parameters:
• `renaming` (Dictionary) - Map from existing vertices to new vertices
Returns: Same class as `self`
Isomorphic hypergrah with new names for vertices
Raises:
• `KeyError` - If an existing vertex is missing from `renaming`
• `ValueError` - If two existing vertices are mapped to the name new name

### representative_graph(self)

source code

Return the representative graph of a hypergraph

The vertices of the graph are hyperedges of the hypergraph. Two vertices are connected if the corresponding hyperedges intersect

Ignores repeated hyperedges, so not quite accurate for non-simple hypergraphs

Also known as the line-graph of the hypergraph

Returns: UGraph
The representative graph of the hypergraph

### restriction(self, vertices, inverted=False)

source code

Restrict the hypergraph to contain only `vertices`

Parameters:
• `vertices` (Iterable) - The vertices to restrict the hypergraph to, unless `inverted=True` in which case the vertices to remove.
• `inverted` (Boolean) - Whether to remove `vertices`
Returns: List
New hyperedges produced

### simplify(self)

source code

Simplify a hypergraph

Returning repeated hyperedges deleted

Returns: list of frozensets
Repeated hyperedges

### size(self)

source code

Return the number of hyperedges in the hypergraph

Returns: Int
The number of hyperedges in the hypergraph

### star(self, vertex)

source code

Return the star of `vertex`: the set of hyperedges which contain `vertex`

Altering the returned set will not alter the hypergraph. Note that a set object is returned, not a hypergraph object.

Parameters:
• `vertex` (String) - The vertex whose star is sought
Returns: Set
The star of `vertex`: the hyperedges each of which contain `vertex`
Raises:
• `KeyError` - If `vertex` is not in the (hyper)graph

### star_size(self, vertex)

source code

Return a count of the number of distinct hyperedges containing a vertex

Parameters:
• `vertex` (String) - The vertex for which containing hyperedges are sought
Returns: Int
The number of hyperedges each of which contain `vertex`
Raises:
• `KeyError` - If `vertex` is not in the (hyper)graph

### stars(self, vertices)

source code

Return the hyperedges each of which contain at least one vertex in `vertices`

Parameters:
• `vertices` (Sequence) - The vertices for which containing hyperedges are sought
Returns: Set
The set of hyperedges each of which contain at least one vertex in `vertices`
Raises:
• `KeyError` - If `vertices` contains a vertex not in the (hyper)graph

### two_section(self)

source code

Return the 2-section of a hypergraph

This graph contains an undirected edge for any pair of distinct vertices which are both members of a hyperedge.

Returns: UGraph
The interaction graph

### vertices(self)

source code

Return the vertices (base set) of the hypergraph

Returns: Set
The vertices (base set) of the hypergraph

### would_be_redundant(self, hyperedge)

source code

Whether `hyperedge` would be redundant if it were added to the hypergraph

If `hyperedge` is already in the hypergraph it is considered that it would be redundant if added.

Parameters:
• `hyperedge` (Iterable) - A potential hyperedge

 Instance Variable Details

### _extras

If repeated hyperedges exist, maps each repeated hyperedge to the number of times it is repeated. (If repeated once, the hyperedge occurs twice.)
Type:
Dictionary

### _hyperedges

The distinct hyperedges in the hypergraph. Each hyperedge is a frozenset
Type:
Set

### _star

Maps a vertex to the set of hyperedges which contain it. (Effectively represents the dual hypergraph.)
Type:
Dictionary

 Generated by Epydoc 3.0.1 on Thu Oct 15 15:34:08 2009 http://epydoc.sourceforge.net