Package gPy :: Module Graphs :: Class UGraph

[frames] | no frames]

Class UGraph

source code

Graphs with only undirected edges (i.e. lines)

Instance Methods

[hide private]

__init__(self, vertices=(), lines=(), vertex_positions=None)
Graph initialisation source code

__repr__(self)
Formal string representation of a graph

source code

extend_compsub(self, compsub, candidates, notset, hypergraph)
Extend a complete subset of the graph to find cliques

source code

twdp(self, up=None, monitor=False)
Exact treewidth computation from Bodlaender et al

source code

Same class as self

gui_triangulate(self, parent, elimination_order, original_colour='black', eliminating_colour='red', uneliminated_neighbour_colour='green', eliminated_colour='grey', fill_in_colour='blue', width=400, height=350, **config)
Triangulate the graph using elimination_order and display the process graphically. source code

gui_maximum_cardinality_search(self, parent, choose=None, width=400, height=350, **config)

source code

ReducedGraphicalHypergraph

hypergraph(self)
Return the clique hypergraph of an undirected graph

source code

Boolean

is_triangulated(self)
Return whether the graph is triangulated

source code

Boolean

is_chordal(self)
Return whether the graph is triangulated

source code

Boolean

is_decomposable(self)
Return whether the graph is triangulated

source code

maximum_cardinality_search(self, choose=None)
Return maximum cardinality search

source code

put_line(self, frm, to)
Add a line (undirected edge) to the graph between two existing vertices

source code

random_graph(self, n, m)

source code

zero_fillin_check(self, elimination_order=None)

source code

triangulate2(self, elimination_order)
Triangulate the graph inefficiently! using elimination_order source code

(As long as zero_fillin_check=False), the list of tuples, each tuple is an unordered pair of vertices

triangulate(self, elimination_order, zero_fillin_check=False, modify=True)
Triangulate the graph using elimination_order source code

_gui_elim_one(self, elimination_order, eliminated, gc, original_colour, eliminating_colour, uneliminated_neighbour_colour, eliminated_colour, fill_in_colour)

source code

_gui_maxcard_one(self, i, j, alpha, alpha_inv, cardinality, sets, choose)

source code

Inherited from _AbsGraph: __eq__, __ne__, __str__, add_vertex, add_vertices, arbitrary_vertex, arrows, child, children, copy, delete_vertex, diff, discard_arrow, discard_line, edges, extend_paths, get_gui_graph_kill, gui_display, gui_edit, is_neighbour, is_parent, is_subset_of_parents, is_superset_of_parents, lines, moralise, neighbours, num_parents, num_parentsets, orphanlist, parent, parents, parentsets, paths, put_vertex, reinit, remove_vertex, set_vertex_positions, shd, vertex_positions, vertexlist, vertices

Inherited from _AbsGraph (private): _gui_help

Inherited from _AbsUGraph: add_clique, add_line, add_lines, complete, put_lines, remove_line

Inherited from Hypergraphs.Incidence: reachable, separates

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

Class Variables

[hide private]

Inherited from _AbsGraph (private): _edit_help_msg

Instance Variables

[hide private]

Inherited from _AbsGraph (private): _ch, _ne, _pa, _vertex_positions

Properties

[hide private]

Inherited from object: __class__

Method Details

[hide private]

init(self, vertices=`()`, lines=`()`, vertex_positions=None)
(Constructor)

source code

Graph initialisation

Parameters:

vertices - The vertices of the graph
arrows - The arrows of the graph
lines - The lines of the graph
vertex_positions - A mapping from vertices to canvas co-ordinates

Raises:

KeyError - If arrows or lines contains a vertex not included in vertices
ExistingVertexError - If vertices repeats a vertex.

Overrides: object.__init__

(inherited documentation)

repr(self)
(Representation operator)

source code

Formal string representation of a graph

Overrides: object.__repr__: (inherited documentation)

extend_compsub(self, compsub, candidates, notset, hypergraph)

source code

Extend a complete subset of the graph to find cliques

This is for Version 1 of Bron and Kerbosch's algorithm. Version 2 is better, but more complex.

Checks whether candidates includes all neighbours of some element of notset in which case no clique can be formed:

@Article{bron73:_algor,
author =        {Bron, C. and Kerbosch, J.},
title =         {Algorithm 457: finding all cliques of an undirected graph},
journal =       {Communications of the {ACM}},
year =          1973,
volume =        16,
pages =         {575--577}
}

Parameters:

compsub (Set) - The complete set of vertices to be extended
candidates (Set) - Candidates available to extend compsub,
notset (Set) - Vertices that have previously served as candidates and which are now explicitly excluded
hypergraph (ReducedGraphicalHypergraph) - The graphical hypergraph to which any found cliques will be added.

gui_triangulate(self, parent, elimination_order, original_colour=`'black'`, eliminating_colour=`'red'`, uneliminated_neighbour_colour=`'green'`, eliminated_colour=`'grey'`, fill_in_colour=`'blue'`, width=400, height=350, **config)

source code

Triangulate the graph using elimination_order and display the process graphically.

Alters self

Parameters:

parent (A suitable Tkinter object, eg a Frame.) - A widget in which the graph will be displayed
original_colour (String) - Colour for uneliminated vertices not participating in an elimination
eliminating_colour (String) - Colour for the vertex being eliminated
uneliminated_neighbour_colour (String) - Colour for uneliminated neighbours of the the vertex being eliminated
eliminated_colour (String) - Colour for eliminated vertices
fill_in_colour (String) - Colour for fill-in lines
elimination_order (An iterator (typically a list)) - The elimination order
config (Various) - Configuration options for the GUI

Returns: Same class as self

The triangulated graph

hypergraph(self)

source code

Return the clique hypergraph of an undirected graph

Uses Bron and Kerbosch algorithm, see extend_compsub

Returns: ReducedGraphicalHypergraph: The clique hypergraph of an undirected graph

is_triangulated(self)

source code

Return whether the graph is triangulated

Uses maximum_cardinality_search, see that method for acknowledgements

Returns: Boolean: Whether the graph is triangulated (aka 'decomposable', 'chordal')

is_chordal(self)

source code

Return whether the graph is triangulated

Uses maximum_cardinality_search, see that method for acknowledgements

Returns: Boolean: Whether the graph is triangulated (aka 'decomposable', 'chordal')

is_decomposable(self)

source code

Return whether the graph is triangulated

Uses maximum_cardinality_search, see that method for acknowledgements

Returns: Boolean: Whether the graph is triangulated (aka 'decomposable', 'chordal')

maximum_cardinality_search(self, choose=None)

source code

Return maximum cardinality search

Ref:

@Article{tarjan84:_simpl,
author =        {Robert E. Tarjan and Mihalis Yannakakis},
title =         {Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, 
journal =       {{SIAM} Journal of Computing},
year =          1984,
volume =        13,
number =        3,
pages =         {566--579},
month =         {August}

put_line(self, frm, to)

source code

Add a line (undirected edge) to the graph between two existing vertices

Parameters:

frm (Immutable type) - One of the vertices connected by the line
to (Immutable type) - The other vertex connected by the line

Raises:

KeyError - If either vertex does not exist

Overrides: _AbsUGraph.put_line

triangulate2(self, elimination_order)

source code

Triangulate the graph inefficiently! using elimination_order

Triangulates the graph by eliminating vertices in the order given by elimination_order. When a vertex is eliminated all its uneliminated neighbours must be a complete set (all pairwise connected by edges). Extra edges are added, if necessary, to ensure this is the case.

'Eliminated' vertices are not actually deleted, just marked as 'eliminated', so you don't end up with an empty graph!

Parameters:

elimination_order (An iterator (typically a list)) - The elimination order

triangulate(self, elimination_order, zero_fillin_check=False, modify=True)

source code

Triangulate the graph using elimination_order

Alters self by default

Ref:

@Article{tarjan84:_simpl,
author =        {Robert E. Tarjan and Mihalis Yannakakis},
title =         {Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, 
journal =       {{SIAM} Journal of Computing},
year =          1984,
volume =        13,
number =        3,
pages =         {566--579},
month =         {August}

Parameters:

elimination_order (An iterator (typically a list)) - The elimination order
zero_fillin_check (Boolean) - If set the method returns whether elimination_order is a zero fill-in and does not alter self
modify (Boolean) - Whether to add the fill-in edges to self

Returns: (As long as zero_fillin_check=False), the list of tuples, each tuple is an unordered pair of vertices

(As long as zero_fillin_check=False), the fill-in (added edges) produced by elimination_order

Class UGraph

__init__(self, vertices=(), lines=(), vertex_positions=None) (Constructor)

__repr__(self) (Representation operator)

extend_compsub(self, compsub, candidates, notset, hypergraph)

gui_triangulate(self, parent, elimination_order, original_colour='black', eliminating_colour='red', uneliminated_neighbour_colour='green', eliminated_colour='grey', fill_in_colour='blue', width=400, height=350, **config)

hypergraph(self)

is_triangulated(self)

is_chordal(self)

is_decomposable(self)

maximum_cardinality_search(self, choose=None)

put_line(self, frm, to)

triangulate2(self, elimination_order)

triangulate(self, elimination_order, zero_fillin_check=False, modify=True)

init(self, vertices=`()`, lines=`()`, vertex_positions=None)
(Constructor)

repr(self)
(Representation operator)

gui_triangulate(self, parent, elimination_order, original_colour=`'black'`, eliminating_colour=`'red'`, uneliminated_neighbour_colour=`'green'`, eliminated_colour=`'grey'`, fill_in_colour=`'blue'`, width=400, height=350, **config)