A Graph ADT
The connectivity of the graph is represented by a hash of key/list
pairs. i.e.
self.edges = {'A': [B, 'C'],
'B': [C, 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
If the graph is weighted, another hash is used which parallels the first
self.weights = {'A': [0.5, 0.1],
'B': [1.0, 0.2],
'C': [2.0],
'D': [1.1],
'E': [2.3],
'F': [0.3]}
|
Methods
|
|
|
|
|
|
BFS
|
BFS ( self, key )
BFS: Breadth-First Search
Returns the number of nodes visited and the order in which they were
visited.
|
|
|
BellmanFord
|
BellmanFord ( self )
|
|
|
DFS
|
DFS ( self, key )
DFS: Depth-First Search
Returns the number of nodes visited and the pre- and post-order in
which they were visited. This is implemented recursively.
|
|
|
Dijkstra
|
Dijkstra (
self,
key,
maxcost=float( 'inf' ),
)
Returns a dictionary of keys and their minimum distance from the
given key. This implementation does not use
|
|
|
FloydWarshall
|
FloydWarshall ( self )
|
|
|
Johnson
|
Johnson ( self )
|
|
|
Kruskal
|
Kruskal ( self )
|
|
|
Prim
|
Prim ( self )
|
|
|
__init__
|
__init__ ( self )
|
|
|
addEdge
|
addEdge (
self,
key1,
key2,
weight=1,
)
|
|
|
addNode
|
addNode ( self, node )
|
|
|
clear
|
clear ( self )
|
|
|
convertToAdjMatrix
|
convertToAdjMatrix ( self )
|
|
|
degree
|
degree ( self, key )
The degree is the number of edges incident to a vertex. This is
currently implemented in an inefficient manner.
|
|
|
diameter
|
diameter ( self )
The diameter of a graph is the largest distance between any two
vertices.
|
|
|
edgeExists
|
edgeExists (
self,
key1,
key2,
)
|
|
|
girth
|
girth ( self )
The girth of a graph is the length of the smallest cycle.
|
|
|
isAcyclic
|
isAcyclic ( self )
|
|
|
isBipartite
|
isBipartite ( self )
A bipartite graph can be partitioned into two sets in which the
vertices in each set have no edges between themselves.
|
|
|
isComplete
|
isComplete ( self )
A graph is complete is every vertex is connected to each other.
|
|
|
isConnected
|
isConnected ( self )
A graph is connected if there is a path to every node from a given
node. For undirected graphs, this also satisfies the test of strong
connectivity. For directed graphs, use the isStronglyConnected()
method.
|
|
|
isRegular
|
isRegular ( self )
A graph is regular is every vertex has the same degree.
|
|
|
isStronglyConnected
|
isStronglyConnected ( self )
A graph is strongly connected is there is a path to every vertex from
any other vertex. For a directed graph this can be efficiently
checked via two applications of a BFS.
|
|
|
iterator
|
iterator (
self,
key=None,
type='DFO',
)
|
|
|
maxDistance
|
maxDistance ( self, key )
|
|
|
neighbors
|
neighbors ( self, key )
|
|
|
order
|
order ( self )
Returns the order of the graph which is defined as |V|, or the number
or vertices (nodes) in the graph.
|
|
|
postorder
|
postorder ( self, key )
|
|
|
preorder
|
preorder ( self, key )
|
|
|
removeEdge
|
removeEdge (
self,
key1,
key2,
)
|
|
|
removeNode
|
removeNode ( self, key )
Remove a node with the given key from the data structure.
|
|
|
shortestPath
|
shortestPath (
self,
key1,
key2,
)
Find a single shortest path from the given start key to the given
end key. The output is a list of the keys in order along the
shortest path.
|
|
|
size
|
size ( self )
Returns the size of the graph which is defined as |E|, or the number
or edges (arcs) in the graph.
|
|
|
weight
|
weight (
self,
key1,
key2,
)
|
|