diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.digraph-class.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.digraph-class.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,2103 @@ + + + + + graph.digraph + + + + + + + + + + + + + + + + + + + + + + + +
   Home      Trees      Indices      Help    + + +
python-graph
+ + + + + +
+ + Package graph :: + Class digraph + + + + +
+
+ +

Class digraph

+
+object --+
+         |
+        digraph
+
+ +
+

Digraph class.

+

Digraphs are built of nodes and directed edges.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ Instance Methods
+   + + + + + + +
__init__(self)
+ Initialize a digraph.		 + + +
+ +
+ iterator + + + + + + +
__getitem__(self, + node)
+ Return a iterator passing through all neighbors of the given node.		 + + +
+ +
+ iterator + + + + + + +
__iter__(self)
+ Return a iterator passing through all nodes in the digraph.		 + + +
+ +
+ number + + + + + + +
__len__(self)
+ Return the order of the digraph when requested by len().		 + + +
+ +
+ string + + + + + + +
__str__(self)
+ Return a string representing the digraph when requested by str() (or + print).		 + + +
+ +
+   + + + + + + +
add_edge(self, + u, + v, + wt=1, + label='', + attrs=[])
+ Add an directed edge (u,v) to the graph connecting nodes u to v.		 + + +
+ +
+   + + + + + + +
add_edge_attribute(self, + u, + v, + attr)
+ Add attribute to the given edge.		 + + +
+ +
+   + + + + + + +
add_graph(self, + graph)
+ Add other graph to the graph.		 + + +
+ +
+   + + + + + + +
add_node(self, + node, + attrs=[])
+ Add given node to the graph.		 + + +
+ +
+   + + + + + + +
add_node_attribute(self, + node, + attr)
+ Add attribute to the given node.		 + + +
+ +
+   + + + + + + +
add_nodes(self, + nodelist)
+ Add given nodes to the graph.		 + + +
+ +
+   + + + + + + +
add_spanning_tree(self, + st)
+ Add a spanning tree to the graph.		 + + +
+ +
+   + + + + + + +
complete(self)
+ Make the graph a complete graph.		 + + +
+ +
+ number + + + + + + +
degree(self, + node)
+ Return the degree of the given node.		 + + +
+ +
+   + + + + + + +
del_edge(self, + u, + v)
+ Remove an directed edge (u, v) from the graph.		 + + +
+ +
+   + + + + + + +
del_node(self, + node)
+ Remove a node from the graph.		 + + +
+ +
+ list + + + + + + +
edges(self)
+ Return all edges in the graph.		 + + +
+ +
+ list + + + + + + +
get_edge_attributes(self, + u, + v)
+ Return the attributes of the given edge.		 + + +
+ +
+ string + + + + + + +
get_edge_label(self, + u, + v)
+ Get the label of an edge.		 + + +
+ +
+ number + + + + + + +
get_edge_weight(self, + u, + v)
+ Get the weight of an edge.		 + + +
+ +
+ list + + + + + + +
get_node_attributes(self, + node)
+ Return the attributes of the given node.		 + + +
+ +
+ boolean + + + + + + +
has_edge(self, + u, + v)
+ Return whether an edge between nodes u and v exists.		 + + +
+ +
+ boolean + + + + + + +
has_node(self, + node)
+ Return whether the requested node exists.		 + + +
+ +
+ list + + + + + + +
incidents(self, + node)
+ Return all nodes that are incident to the given node.		 + + +
+ +
+ graph + + + + + + +
inverse(self)
+ Return the inverse of the graph.		 + + +
+ +
+ list + + + + + + +
neighbors(self, + node)
+ Return all nodes that are directly accessible from given node.		 + + +
+ +
+ list + + + + + + +
nodes(self)
+ Return node list.		 + + +
+ +
+ number + + + + + + +
order(self, + node)
+ Return the order of the given node.		 + + +
+ +
+   + + + + + + +
set_edge_label(self, + u, + v, + label)
+ Set the label of an edge.		 + + +
+ +
+   + + + + + + +
set_edge_weight(self, + u, + v, + wt)
+ Set the weight of an edge.		 + + +
+ +
+ iterator + + + + + + +
traversal(self, + node, + order='pre')
+ Graph traversal iterator.		 + + +
+ +
+   + + + + + + +
generate(self, + num_nodes, + num_edges, + weight_range=(1, 1))
+ Add nodes and random edges to the graph.		 + + +
+ +
+   + + + + + + +
read(self, + string, + fmt='xml')
+ Read a graph from a string.		 + + +
+ +
+ string + + + + + + +
write(self, + fmt='xml')
+ Write the graph to a string.		 + + +
+ +
+ dictionary + + + + + + +
accessibility(self)
+ Accessibility matrix (transitive closure).		 + + +
+ +
+ dictionary + + + + + + +
breadth_first_search(self, + root=None)
+ Breadth-first search.		 + + +
+ +
+ list + + + + + + +
cut_edges(self)
+ Return the cut-edges of the given graph.		 + + +
+ +
+ list + + + + + + +
cut_nodes(self)
+ Return the cut-nodes of the given graph.		 + + +
+ +
+ tuple + + + + + + +
depth_first_search(self, + root=None)
+ Depht-first search.		 + + +
+ +
+ list + + + + + + +
minimal_spanning_tree(self, + root=None)
+ Minimal spanning tree.		 + + +
+ +
+ list + + + + + + +
mutual_accessibility(self)
+ Mutual-accessibility matrix (strongly connected components).		 + + +
+ +
+ tuple + + + + + + +
shortest_path(self, + source)
+ Return the shortest path distance between source node and all other + nodes using Dijkstra's algorithm.		 + + +
+ +
+ list + + + + + + +
topological_sorting(self)
+ Topological sorting.		 + + +
+ +
+

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

+
+ + + + + + + + + +
+ Properties
+

Inherited from object: + __class__ +

+
+ + + + + + +
+ Method Details
+ +
+ +
+ + +
+

__init__(self) +
(Constructor) +

+ 		  +
+ +

Initialize a digraph.

+
+
Overrides: + object.__init__ +
+
+
+
+ +
+ +
+ + +
+

__getitem__(self, + node) +
(Indexing operator) +

+ 		  +
+ +

Return a iterator passing through all neighbors of the given node.

+
+
Returns: iterator
+
Iterator passing through all neighbors of the given node.
+
+
+
+ +
+ +
+ + +
+

__iter__(self) +

+ 		  +
+ +

Return a iterator passing through all nodes in the digraph.

+
+
Returns: iterator
+
Iterator passing through all nodes in the digraph.
+
+
+
+ +
+ +
+ + +
+

__len__(self) +
(Length operator) +

+ 		  +
+ +

Return the order of the digraph when requested by len().

+
+
Returns: number
+
Size of the graph.
+
+
+
+ +
+ +
+ + +
+

__str__(self) +
(Informal representation operator) +

+ 		  +
+ +

Return a string representing the digraph when requested by str() (or + print).

+
+
Returns: string
+
String representing the graph.
+
Overrides: + object.__str__ +
+
+
+
+ +
+ +
+ + +
+

add_edge(self, + u, + v, + wt=1, + label='', + attrs=[]) +

+ 		  +
+ +

Add an directed edge (u,v) to the graph connecting nodes u to v.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
  • wt (number) - Edge weight.
    • +
  • label (string) - Edge label.
    • +
  • attrs (list) - List of node attributes specified as (attribute, value) tuples.
    • +
+
+
+
+ +
+ +
+ + +
+

add_edge_attribute(self, + u, + v, + attr) +

+ 		  +
+ +

Add attribute to the given edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
  • attr (tuple) - Node attribute specified as a tuple in the form (attribute, + value).
    • +
+
+
+
+ +
+ +
+ + +
+

add_graph(self, + graph) +

+ 		  +
+ +

Add other graph to the graph.

+
+
Parameters:
+
    +
  • graph (graph) - Graph
    • +
+
+

Attention: + Attributes and labels are not preserved. +

+
+
+ +
+ +
+ + +
+

add_node(self, + node, + attrs=[]) +

+ 		  +
+ +

Add given node to the graph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
    • +
  • attrs (list) - List of node attributes specified as (attribute, value) tuples.
    • +
+
+

Attention: + While nodes can be of any type, it's strongly recommended to use + only numbers and single-line strings as node identifiers if you + intend to use write(). +

+
+
+ +
+ +
+ + +
+

add_node_attribute(self, + node, + attr) +

+ 		  +
+ +

Add attribute to the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
    • +
  • attr (tuple) - Node attribute specified as a tuple in the form (attribute, + value).
    • +
+
+
+
+ +
+ +
+ + +
+

add_nodes(self, + nodelist) +

+ 		  +
+ +

Add given nodes to the graph.

+
+
Parameters:
+
    +
  • nodelist (list) - List of nodes to be added to the graph.
    • +
+
+

Attention: + While nodes can be of any type, it's strongly recommended to use + only numbers and single-line strings as node identifiers if you + intend to use write(). +

+
+
+ +
+ +
+ + +
+

add_spanning_tree(self, + st) +

+ 		  +
+ +

Add a spanning tree to the graph.

+
+
Parameters:
+
    +
  • st (dictionary) - Spanning tree.
    • +
+
+
+
+ +
+ +
+ + +
+

complete(self) +

+ 		  +
+ +

Make the graph a complete graph.

+
+
+

Attention: + This will modify the current graph. +

+
+
+ +
+ +
+ + +
+

degree(self, + node) +

+ 		  +
+ +

Return the degree of the given node.

+
+
Returns: number
+
Order of the given node.
+
+
+
+ +
+ +
+ + +
+

del_edge(self, + u, + v) +

+ 		  +
+ +

Remove an directed edge (u, v) from the graph.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
+
+
+
+ +
+ +
+ + +
+

del_node(self, + node) +

+ 		  +
+ +

Remove a node from the graph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
    • +
+
+
+
+ +
+ +
+ + +
+

edges(self) +

+ 		  +
+ +

Return all edges in the graph.

+
+
Returns: list
+
List of all edges in the graph.
+
+
+
+ +
+ +
+ + +
+

get_edge_attributes(self, + u, + v) +

+ 		  +
+ +

Return the attributes of the given edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
+
Returns: list
+
List of attributes specified tuples in the form (attribute, + value).
+
+
+
+ +
+ +
+ + +
+

get_edge_label(self, + u, + v) +

+ 		  +
+ +

Get the label of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
+
Returns: string
+
Edge label
+
+
+
+ +
+ +
+ + +
+

get_edge_weight(self, + u, + v) +

+ 		  +
+ +

Get the weight of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
+
Returns: number
+
Edge weight.
+
+
+
+ +
+ +
+ + +
+

get_node_attributes(self, + node) +

+ 		  +
+ +

Return the attributes of the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
    • +
+
Returns: list
+
List of attributes specified tuples in the form (attribute, + value).
+
+
+
+ +
+ +
+ + +
+

has_edge(self, + u, + v) +

+ 		  +
+ +

Return whether an edge between nodes u and v exists.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
+
Returns: boolean
+
Truth-value for edge existence.
+
+
+
+ +
+ +
+ + +
+

has_node(self, + node) +

+ 		  +
+ +

Return whether the requested node exists.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
    • +
+
Returns: boolean
+
Truth-value for node existence.
+
+
+
+ +
+ +
+ + +
+

incidents(self, + node) +

+ 		  +
+ +

Return all nodes that are incident to the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
    • +
+
Returns: list
+
List of nodes directly accessible from given node.
+
+
+
+ +
+ +
+ + +
+

inverse(self) +

+ 		  +
+ +

Return the inverse of the graph.

+
+
Returns: graph
+
Complement graph for the graph.
+
+
+
+ +
+ +
+ + +
+

neighbors(self, + node) +

+ 		  +
+ +

Return all nodes that are directly accessible from given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
    • +
+
Returns: list
+
List of nodes directly accessible from given node.
+
+
+
+ +
+ +
+ + +
+

nodes(self) +

+ 		  +
+ +

Return node list.

+
+
Returns: list
+
Node list.
+
+
+
+ +
+ +
+ + +
+

order(self, + node) +

+ 		  +
+ +

Return the order of the given node.

+
+
Returns: number
+
Order of the given node.
+
+
+
+ +
+ +
+ + +
+

set_edge_label(self, + u, + v, + label) +

+ 		  +
+ +

Set the label of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
  • label (string) - Edge label.
    • +
+
+
+
+ +
+ +
+ + +
+

set_edge_weight(self, + u, + v, + wt) +

+ 		  +
+ +

Set the weight of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
    • +
  • v (node) - Other node.
    • +
  • wt (number) - Edge weight.
    • +
+
+
+
+ +
+ +
+ + +
+

traversal(self, + node, + order='pre') +

+ 		  +
+ +

Graph traversal iterator.

+
+
Parameters:
+
    +
  • node (node) - Node.
    • +
  • order (string) - traversal ordering. Possible values are: +
      +
    1. + 'pre' - Preordering (default) +
      2. +
    +
      +
    1. + 'post' - Postordering +
      2. +
    • +
+
Returns: iterator
+
Traversal iterator.
+
+
+
+ +
+ +
+ + +
+

generate(self, + num_nodes, + num_edges, + weight_range=(1, 1)) +

+ 		  +
+ +

Add nodes and random edges to the graph.

+
+
Parameters:
+
    +
  • num_nodes (number) - Number of nodes.
    • +
  • num_edges (number) - Number of edges.
    • +
  • weight_range (tuple) - tuple of two integers as lower and upper limits on randomly + generated weights (uniform distribution).
    • +
+
+
+
+ +
+ +
+ + +
+

read(self, + string, + fmt='xml') +

+ 		  +
+ +

Read a graph from a string. Nodes and edges specified in the input + will be added to the current graph.

+
+
Parameters:
+
    +
  • string (string) - Input string specifying a graph.
    • +
  • fmt (string) - Input format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
      2. +
    • +
+
+
+
+ +
+ +
+ + +
+

write(self, + fmt='xml') +

+ 		  +
+ +

Write the graph to a string. Depending of the output format, this + string can be used by read() to rebuild the graph.

+
+
Parameters:
+
    +
  • fmt (string) - Output format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
      2. +
    2. + 'dot' - DOT Language (for GraphViz) +
      3. +
    3. + 'dotwt' - DOT Language with weight information +
      4. +
    • +
+
Returns: string
+
String specifying the graph.
+
+
+
+ +
+ +
+ + +
+

accessibility(self) +

+ 		  +
+ +

Accessibility matrix (transitive closure).

+
+
Returns: dictionary
+
Accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

breadth_first_search(self, + root=None) +

+ 		  +
+ +

Breadth-first search.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
    • +
+
Returns: dictionary
+
A tuple containing a dictionary and a list. +
    +
  1. + Generated spanning tree +
    2. +
  2. + Graph's level-based ordering +
    3. +
+
+
+
+ +
+ +
+ + +
+

cut_edges(self) +

+ 		  +
+ +

Return the cut-edges of the given graph.

+
+
Returns: list
+
List of cut-edges.
+
+
+
+ +
+ +
+ + +
+

cut_nodes(self) +

+ 		  +
+ +

Return the cut-nodes of the given graph.

+
+
Returns: list
+
List of cut-nodes.
+
+
+
+ +
+ +
+ + +
+

depth_first_search(self, + root=None) +

+ 		  +
+ +

Depht-first search.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
    • +
+
Returns: tuple
+
tupple containing a dictionary and two lists: +
    +
  1. + Generated spanning tree +
    2. +
  2. + Graph's preordering +
    3. +
  3. + Graph's postordering +
    4. +
+
+
+
+ +
+ +
+ + +
+

minimal_spanning_tree(self, + root=None) +

+ 		  +
+ +

Minimal spanning tree.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
    • +
+
Returns: list
+
Generated spanning tree.
+
+

Attention: + Minimal spanning tree meaningful only for weighted graphs. +

+
+
+ +
+ +
+ + +
+

mutual_accessibility(self) +

+ 		  +
+ +

Mutual-accessibility matrix (strongly connected components).

+
+
Returns: list
+
Mutual-accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

shortest_path(self, + source) +

+ 		  +
+ +

Return the shortest path distance between source node and all other + nodes using Dijkstra's algorithm.

+
+
Parameters:
+
    +
  • source (node) - Node from which to start the search.
    • +
+
Returns: tuple
+
A tuple containing two dictionaries, each keyed by target nodes. +
    +
  1. + Shortest path spanning tree +
    2. +
  2. + Shortest distance from given source to each target node +
    3. +
+

Inaccessible target nodes do not appear in either + dictionary.

+
+

Attention: + All weights must be nonnegative. +

+
+
+ +
+ +
+ + +
+

topological_sorting(self) +

+ 		  +
+ +

Topological sorting.

+
+
Returns: list
+
Topological sorting for the graph.
+
+

Attention: + Topological sorting is meaningful only for directed acyclic graphs. +

+
+
+
+ + + + + + + + + + + + + + + + + + +
   Home      Trees      Indices      Help    + + +
python-graph
+ + + + + +
+ Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 + + http://epydoc.sourceforge.net +
+ + + +