__Description__

graph_lib.py is a file that includes the Python
class ** Graph**.

It uses a dictionary for nodes and edges to represent

Node's may be named arbitrarily. Edges are assigned names. Arbitrary data may be attached to both an edge and a node.

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 methodis added as well.degree_list

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

`#--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( )`

`__init__( self)`

Creates an empty graph. That is,V={ }E={ }

Creates a replica ofinto self. That is all of the nodes in self will have the same names as the nodes inG, and all the edges ofGwill be in self -- HOWEVER, the edge id's are not directly mapped. That is, after a copy operation, a nodeGinXwill then have a twin, nodeGin self. NodeXinYwill have its twin, nodeGin self. If there is an edgeYinethat connectsG->X, there will be an edge that connectsY->Xin self, but it's name will not beY.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.

Adds a new node to the set,, names the node node_id and attaches to the new node a reference toV. If nonode_datais specified it is assumed to be the objectnode_dataNone.

Adds an edge to the set. The new edge will be a directed edge from the node,E, to the node,head_id. A reference totail_idis attached to the edge. If noedge_datais specified the edge data is assumed to be the object,edge_dataNone.

Removes the node namednode_idfrom the set, and removes all edges of the formV->?andnode_id->node_idfrom the set?.E

Removes the named edge from the set.E

Removes the named node from the set, 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.V

Removes the named edge from the set, 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.E

Removes the named node from the hidden edge set and returns it to the setand all of the associated hidden in arcs and out arcs.V

Restores all hidden nodes.

Removes the named edge from the hidden edge set and returns it to the set.E

Restores all hidden edges.

Returns1if the sethas a node with nameVandnode_id0otherwise.

Returns the edge name of the edge that connects the nodeto the nodehead_id.tail_id

Returns.|V|

Returns.|E|

Returns a list of the names of nodes in.V

Returns a list of all the names of edges.E

Returns the number of edges that are hidden.

Returns the number of hidden nodes. (Easy, eh?)

Returns a list of the names of all of the hidden nodes.

Returns a list of the names of all of the hidden edges.

Returns a reference to the data attached to the named node.

Returns a reference to the data attached to the

Returns the name of the head of the named edge.

Returns the name of the tail of the named edge.

Returns a list of names of in edges. ie. edges that have the form->?X

Returns a list of names of out edges. ie. edges that have the form->X?

Returns a list of the names of in and out edges.

Returns the number of out edges of the named node.

Returns the number of in edges of the named node.

Returns the number of in and out edges of the named node.

Returns a list of nodes sorted into some topological order. After sorting the nodes, the method performs a sanity check and throughs an exception,, if the graph appears to be cyclic. The exception will contain theGraph_topological_error

list of nodes that have been successfully sorted. (Good for DAG-ifying a cyclic graph.)

Returns a list of nodes sorted in some reverse topological order. Similar to above, the method will throw aif the graph appears to be cyclic.Graph_topological_error

Returns a list of nodes in some depth first order beginning from the node,. Cycles are ignored.source_id

Returns a list of nodes in some breadth first order beginning from the node,. Cycles are ignored.source_id

Returns a list of nodes in some back breadth first order, beginning from the node,. The back BFS follows back edges (in arcs) of each node. Cycles are ignored.source_id