Home       Trees       Indices       Help   
gPy
Package gPy :: Module Graphs :: Class DiGraph
[hide private]
[frames] | no frames]

Class DiGraph

source code

Graphs with only directed edges (i.e. arrows)

A graph with A->B and B<-A is not allowed, since this produces an undirected edge.

Instance Methods [hide private]
 
__init__(self, vertices=(), arrows=(), vertex_positions=None)
Graph initialisation		 source code
 
__repr__(self)
Formal string representation of a graph		 source code
frozenset of vertices
ancestors(self, vertex)
Returns the set of all ancestors of vertex.		 source code
Generator iterator
connect(self, vertex, vertices)
Iterates over digraphs produced by making vertex a parent to subsets of vertices		 source code
frozenset of vertices
descendants(self, vertex)
Returns the set of all descendants of vertex.		 source code
 
dfsvisit(self, vertex, visited, order)
Visit unvisited vertices in depth-first fashion and append them to a topological ordering of vertices		 source code
iterator
enumerate_cycles(self, lim)
Enumerates all cycles in a digraph of length at most lim		 source code
 
essential_graph(self)
Return the essential graph of self		 source code
 
generate_from_vertices(cls, vertices) source code
Generator iterator
generate(self, vertices)
Generate digraphs which respect the order of vertices		 source code
List of tuples of vertices
minimal_cycles(self, source)
Return all minimal cycles involving source.		 source code
List of lists of vertices
minimal_paths(self, source, sink)
Return all minimal (non-direct) paths from source to sink.		 source code
List
topological_order(self)
Return a topological ordering of the vertices		 source code
 
_ancestors(self, vertex, ancestors)
Add ancestors of vertex not in ancestors to ancestors		 source code
 
_descendants(self, vertex, descendants)
Add descendants of vertex not already in descendants to descendants		 source code
 
_minimaldfs(self, current, sink, before_current, paths)
current is last vertex on current path before_current is all previous vertices		 source code
 
_tarjan_backtrack(self, start, v, marked, marked_stack, point_stack, lim) 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 _AbsDiGraph: add_arrow, add_arrows, put_arrow, put_arrows, put_family, remove_arrow

Inherited from Hypergraphs.Incidence: reachable, separates

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

Class Methods [hide private]
 
families(self) source code
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=(), arrows=(), 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)

ancestors(self, vertex)

source code 

Returns the set of all ancestors of vertex.

Parameters:
  • vertex (Immutable) - A vertex in the graph
Returns: frozenset of vertices
ancestors of vertex

connect(self, vertex, vertices)

source code 

Iterates over digraphs produced by making vertex a parent to subsets of vertices

Parameters:
  • vertex (Immutable) - Parent vertex
  • vertices (Sequence) - Potential children
Returns: Generator iterator
Generator of digraphs

descendants(self, vertex)

source code 

Returns the set of all descendants of vertex.

Parameters:
  • vertex (Immutable) - A vertex in the graph
Returns: frozenset of vertices
descendants of vertex

dfsvisit(self, vertex, visited, order)

source code 

Visit unvisited vertices in depth-first fashion and append them to a topological ordering of vertices

Parameters:
  • vertex (Immutable type (typically String)) - First vertex to visit
  • visited (Set) - Nodes already visited
  • order (List) - Topological ordering of vertices

enumerate_cycles(self, lim)

source code 

Enumerates all cycles in a digraph of length at most lim

Ref:

@article{tarjan:211, author = {Robert Tarjan}, title = {Enumeration of the Elementary Circuits of a Directed Graph}, publisher = {SIAM}, year = {1973}, journal = {SIAM Journal on Computing}, volume = {2}, number = {3}, pages = {211-216}, keywords = {algorithm; backtracking; circuit; cycle; digraph; graph}, url = {http://link.aip.org/link/?SMJ/2/211/1}, doi = {10.1137/0202017} }

@TechReport{tarjan72:_enumer, author = {Robert Tarjan}, title = {Enumeration of the elementary circuits of a directed graph}, institution = {Cornell University}, year = 1972, number = {72-145}, address = {Ithaca, NY}, month = {September} }

Time bound is O((V+E)(C+1)) where C is the (potentially large) number of cycles.

Returns: iterator
Yields all cycles in the digraph

essential_graph(self)

source code 

Return the essential graph of self

Uses Chickering's algorithm

generate(self, vertices)

source code 

Generate digraphs which respect the order of vertices

Generates all digraphs produced by adding arrows to self which are between vertices in vertices and which respect the order of vertices in vertices.

Parameters:
  • vertices (Tuple) - Ordered vertices
Returns: Generator iterator
Generator of digraphs which respect the order of vertices

minimal_cycles(self, source)

source code 

Return all minimal cycles involving source.

Parameters:
  • source (Immutable) - Source vertex
Returns: List of tuples of vertices
Minimal cycles

minimal_paths(self, source, sink)

source code 

Return all minimal (non-direct) paths from source to sink.

A path source,v1,v2,.. sink is minimal if there are no non-consecutive vertices joined by an edge in self, (with the possible exception of source to sink) and all vertices are distinct. (There are no short-cuts provided by edges).

Parameters:
  • source (Immutable) - Source vertex
  • sink (Immutable) - Sink vertex
Returns: List of lists of vertices
Minimal paths

topological_order(self)

source code 

Return a topological ordering of the vertices

Children come after their parents in the ordering

Returns: List
A topological ordering of the vertices

   Home       Trees       Indices       Help   
gPy
Generated by Epydoc 3.0.1 on Thu Oct 15 15:34:06 2009 http://epydoc.sourceforge.net