diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.digraph-class.html --- a/thirdparty/python-graph/docs/graph.digraph-class.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,2103 +0,0 @@ - - - - - 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 -
- - - -