graph_lib.py

Description
graph_lib.py is a file that includes the Python class Graph.  Graph is loosely modelled after the Library of Efficient Data types and Algorithms (LEDA).  It includes methods for constructing graphs, BFS and DFS traversals, topological sort, etc.
It uses a dictionary for nodes and edges to represent G=(V,E).  Where V is the set of nodes (vertices), and E is the set of directed edges.
Node's may be named arbitrarily.  Edges are assigned names.  Arbitrary data may be attached to both an edge and a node.


Version
This document covers version 1.0.1 June 7,1999.

Version 1.0.1

Hiding a node will now hide all of its in arcs and out arcs as well.  Restoring the node will restore its in arcs and out arcs, too.
A new method degree_list is added as well.

Author and copyright
Written by Nathan Denny.  This code is in the public domain.  No warranty on correctness.

Example

#--Creates a triangle and then does BFS and DFS.
G=Graph( )
G.add_node(0)
G.add_node(1)
G.add_node(2)
G.add_edge(0,1)
G.add_edge(1,2)
G.add_edge(2,0)
print G.bfs( )
print G.dfs( )


graph_lib.Graph

__init__(self)

Creates an empty graph.  That is V={ }, E={ }
copy(self,G)
Creates a replica of G into self.  That is all of the nodes in self will have the same names as the nodes in G, and all the edges of G will be in self -- HOWEVER, the edge id's are not directly mapped.  That is, after a copy operation, a node X in G will then have a twin, node X in self.  Node Y in G will have its twin, node Y in self.  If there is an edge e in G that connects X->Y, there will be an edge that connects X->Y in self, but it's name will not be e.
References to data attached to nodes and edges will be copied if the data has a copy method.  If it does not, a common reference is used instead.
add_node(self, node_id, node_data)
Adds a new node to the set, V, names the node node_id and attaches to the new node a reference to node_data.  If no node_data is specified it is assumed to be the object None.
add_edge(self, head_id, tail_id, edge_data)
Adds an edge to the set E.  The new edge will be a directed edge from the node, head_id, to the node, tail_id.  A reference to edge_data is attached to the edge.  If no edge_data is specified the edge data is assumed to be the object, None.
delete_node(self, node_id)
Removes the node named node_id from the set V, and removes all edges of the form ?->node_id and node_id->? from the set E.
delete_edge(self, edge_id)
Removes the named edge from the set E.
hide_node(self, node_id)
Removes the named node from the set V, but does not delete the node.  It moves the named node to a special set of "hidden" nodes.  Hidden nodes are transparent to graph operations.  This method also hides all in arcs and out arcs of the node.
hide_edge(self, edge_id)
Removes the named edge from the set E, but does not delete the edge.  It moves the named edge to a special set of "hidden" edges.  Hidden edges are transparent to graph operations.
restore_node(self, node_id)
Removes the named node from the hidden edge set and returns it to the set V  and all of the associated hidden in arcs and out arcs.
restore_all_nodes(self)
Restores all hidden nodes.
restore_edge(self, edge_id)
Removes the named edge from the hidden edge set and returns it to the set E.
restore_all_edges(self)
Restores all hidden edges.
has_node(self, node_id)
Returns 1 if the set V has a node with name node_id and 0 otherwise.
edge(self, head_id, tail_id)
Returns the edge name of the edge that connects the node head_id to the node tail_id.
number_of_nodes(self)
Returns |V|.
number_of_edges(self)
Returns |E|.
node_list(self)
Returns a list of the names of nodes in V.
edge_list(self)
Returns a list of all the names of edges E.
number_of_hidden_edges(self)
Returns the number of edges that are hidden.
number_of_hidden_nodes(self)
Returns the number of hidden nodes.  (Easy, eh?)
hidden_node_list(self)
Returns a list of the names of all of the hidden nodes.
hidden_edge_list(self)
Returns a list of the names of all of the hidden edges.
node_data(self, node_id)
Returns a reference to the data attached to the named node.
edge_data(self, edge_id)
Returns a reference to the data attached to the
head(self, edge)
Returns the name of the head of the named edge.
tail(self, edge)
Returns the name of the tail of the named edge.
in_arcs(self, node_id)
Returns a list of names of in edges.  ie. edges that have the form ?->X
out_arcs(self, node_id)
Returns a list of names of out edges.  ie. edges that have the form X->?
arc_list(self, node_id)
Returns a list of the names of in and out edges.
out_degree(self, node_id)
Returns the number of out edges of the named node.
in_degree(self, node_id)
Returns the number of in edges of the named node.
degree(self, node_id)
Returns the number of in and out edges of the named node.
topological_sort(self)
Returns a list of nodes sorted into some topological order.  After sorting the nodes, the method performs a sanity check and throughs an exception, Graph_topological_error, if the graph appears to be cyclic.  The exception will contain the
list of nodes that have been successfully sorted.  (Good for DAG-ifying a cyclic graph.)
reverse_topological_sort(self)
Returns a list of nodes sorted in some reverse topological order.  Similar to above, the method will throw a Graph_topological_error if the graph appears to be cyclic.
dfs(self, source_id)
Returns a list of nodes in some depth first order beginning from the node, source_id.  Cycles are ignored.
bfs(self, source_id)
Returns a list of nodes in some breadth first order beginning from the node, source_id.  Cycles are ignored.
back_bfs(self)
Returns a list of nodes in some back breadth first order, beginning from the node, source_id.  The back BFS follows back edges (in arcs) of each node.  Cycles are ignored.