Package mdp :: Package graph :: Class Graph
[hide private]
[frames] | no frames]

Class Graph


Represent a directed graph.

Instance Methods [hide private]
 
__init__(self)
x.__init__(...) initializes x; see help(type(x)) for signature
 
_bfs(self, neighbors_fct, root, visit_fct=None)
 
_dfs(self, neighbors_fct, root, visit_fct=None)
 
add_edge(self, head, tail, data=None)
Add an edge going from head to tail.
 
add_full_connectivity(self, from_nodes, to_nodes)
Add full connectivity from a group of nodes to another one.
 
add_node(self, data=None)
 
add_nodes(self, data)
Add many nodes at once.
 
add_tree(self, tree)
Add a tree to the graph.
 
bfs(self, root, visit_fct=None)
Return a list of nodes in some Breadth First order starting from a root node.
 
connected_components(self)
Return a list of lists containing the nodes of all connected components of the graph.
 
dfs(self, root, visit_fct=None)
Return a list of nodes in some Depth First order starting from a root node.
 
is_weakly_connected(self)
Return True if the graph is weakly connected.
 
remove_edge(self, edge)
 
remove_node(self, node)
 
topological_sort(self)
Perform a topological sort of the nodes.
 
undirected_bfs(self, root, visit_fct=None)
Perform Breadth First sort.
 
undirected_dfs(self, root, visit_fct=None)
Perform Depth First sort.

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self)
(Constructor)

 
x.__init__(...) initializes x; see help(type(x)) for signature

Overrides: object.__init__
(inherited documentation)

_bfs(self, neighbors_fct, root, visit_fct=None)

 

_dfs(self, neighbors_fct, root, visit_fct=None)

 

add_edge(self, head, tail, data=None)

 
Add an edge going from head to tail.
head : head node
tail : tail node

add_full_connectivity(self, from_nodes, to_nodes)

 
Add full connectivity from a group of nodes to another one.
Return a list of lists of edges, one for each node in 'from_nodes'.

Example: create a two-layer graph with full connectivity.
>>> g = Graph()
>>> layer1 = g.add_nodes(10)
>>> layer2 = g.add_nodes(5)
>>> g.add_full_connectivity(layer1, layer2)

add_node(self, data=None)

 

add_nodes(self, data)

 
Add many nodes at once.

data -- number of nodes to add or sequence of data values, one for
        each new node

add_tree(self, tree)

 
Add a tree to the graph.

The tree is specified with a nested list of tuple, in a LISP-like
notation. The values specified in the list become the values of
the single nodes.

Return an equivalent nested list with the nodes instead of the values.

Example:
>>> a=b=c=d=e=None
>>> g.add_tree( (a, b, (c, d ,e)) )
corresponds to this tree structure, with all node values set to None:

        a
       /               b   c
         /                 d   e

bfs(self, root, visit_fct=None)

 
Return a list of nodes in some Breadth First order starting from
a root node. If defined, visit_fct is applied on each visited node.

Note the returned list does not have to contain all nodes in the
graph, but only the ones reachable from the root.

connected_components(self)

 
Return a list of lists containing the nodes of all connected
components of the graph.

dfs(self, root, visit_fct=None)

 
Return a list of nodes in some Depth First order starting from
a root node. If defined, visit_fct is applied on each visited node.

The returned list does not have to contain all nodes in the
graph, but only the ones reachable from the root.

is_weakly_connected(self)

 
Return True if the graph is weakly connected.

remove_edge(self, edge)

 

remove_node(self, node)

 

topological_sort(self)

 
Perform a topological sort of the nodes. If the graph has a cycle,
throw a GraphTopologicalException with the list of successfully
ordered nodes.

undirected_bfs(self, root, visit_fct=None)

 
Perform Breadth First sort.

This function is identical to bfs, but the sort is performed on
the equivalent undirected version of the graph.

undirected_dfs(self, root, visit_fct=None)

 
Perform Depth First sort.

This function is identical to dfs, but the sort is performed on
the equivalent undirected version of the graph.