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: 'pre' - Preordering (default) 'post' - Postordering 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: 'xml' - XML (default)

### 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: 'xml' - XML (default) 'dot' - DOT Language (for GraphViz) 'dotwt' - DOT Language with weight information 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. Generated spanning tree Graph's level-based ordering

### 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: Generated spanning tree Graph's preordering Graph's postordering

### 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. Shortest path spanning tree Shortest distance from given source to each target node 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.