Package graph :: Class graph

Class graph

Graph class.

Instance Methods
 
__init__(self)
Initialize a graph.
number
__len__(self)
Return the size of the graph when requested by len().
string
__str__(self)
Return a string representing the graph when requested by str() (or print).
 
generate(self, num_nodes, num_edges, directed=False)
Add nodes and random edges to the graph.
 
read(self, string, fmt=None)
Read a graph from a string.
string
write(self, fmt=None)
Write the graph to a string.
 
add_arrow(self, u, v, wt=1)
Add an arrow (u,v) to the directed graph connecting node u to node v.
 
add_edge(self, u, v, wt=1)
Add an edge (u,v) to the graph connecting nodes u and v.
 
add_graph(self, graph)
Add other graph to the graph.
 
add_nodes(self, nodelist)
Add given nodes to the graph.
 
add_spanning_tree(self, st)
Add a spanning tree to the graph.
 
del_arrow(self, u, v)
Remove an arrow (u, v) from the directed graph.
 
del_edge(self, u, v)
Remove an edge (u, v) from the graph.
number
get_arrow_weight(self, u, v)
Get the weight of an arrow.
number
get_edge_weight(self, u, v)
Get the weight of an arrow.
list
get_edges(self, node)
Return all outgoing edges from given node.
list
get_nodes(self)
Return node list.
boolean
has_arrow(self, u, v)
Return whether an arrow from node u to node v exists.
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.
dictionary
accessibility(self)
Accessibility matrix (transitive closure).
dictionary
breadth_first_search(self, root=None)
Breadth-first search.
dictionary
connected_components(self)
Connected components.
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.
Method Details

__len__(self)
(Length operator)

 

Return the size of the graph when requested by len().

Returns: number
Size of the graph.

__str__(self)
(Informal representation operator)

 

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

Returns: string
String representing the graph.

generate(self, num_nodes, num_edges, directed=False)

 

Add nodes and random edges to the graph.

Parameters:
  • num_nodes (number) - Number of nodes.
  • num_edges (number) - Number of edges.
  • directed (boolean) - Wether the generated graph should be directed or not.

read(self, string, fmt=None)

 

Read a graph from a string. Nodes and arrows 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)

write(self, fmt=None)

 

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. 'dot' - DOT Language (for GraphViz)
    3. 'dotwt' - DOT Language with weight information
Returns: string
String specifying the graph.

add_arrow(self, u, v, wt=1)

 

Add an arrow (u,v) to the directed graph connecting node u to node v.

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

add_edge(self, u, v, wt=1)

 

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

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

Attention: This function should not be used in directed graphs: use add_arrow() instead.

add_graph(self, graph)

 

Add other graph to the graph.

Parameters:
  • graph (graph) - Graph

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 identificators if you intend to use write().

add_spanning_tree(self, st)

 

Add a spanning tree to the graph.

Parameters:
  • st (dictionary) - Spanning tree.

del_arrow(self, u, v)

 

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

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

del_edge(self, u, v)

 

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

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

Attention: This function should not be used in directed graphs: use del_arrow() instead.

get_arrow_weight(self, u, v)

 

Get the weight of an arrow.

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

get_edge_weight(self, u, v)

 

Get the weight of an arrow.

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

get_edges(self, node)

 

Return all outgoing edges from given node.

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

get_nodes(self)

 

Return node list.

Returns: list
Node list.

has_arrow(self, u, v)

 

Return whether an arrow from node u to node v exists.

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

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.

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
Generated spanning tree

connected_components(self)

 

Connected components.

Returns: dictionary
Pairing that associates each node to its connected component.

Attention: Indentification of connected components is meaningful only for non-directed graphs.

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. Graph's preordering
  3. 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.
  1. Shortest path spanning tree (each key points to previous node in the shortest path transversal)
  2. 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.