Class: Graph compClust/mlx/Graph.py

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]}

Base Classes
Collection
Methods
BFS
```BFS ( self,  key )

```

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 (
self,
key1,
key2,
weight=1,
)

```
```addNode ( self,  node )

```
clear
```clear ( self )

```
```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,
)

```