
A graph is an ordered pair, G = (V,E), where V is a set of vertices and E = {{u,v}  u ε V and v ε V} is the set of Edges.
More precisely, E is a collection of subsets of V, each of size 2, and the elements of E are called edges.
We will start be defining the class of Graph objects. This class will store V and E as sets. The vertices can be any kind of immutable object. The edges in E will be ordered pairs (tuples) of vertices. Tuples have the advantage of being immutable objects. This use of immutable objects will allow us to implement the several of the methods of the Graph class using Python's extremely efficient Dictionary class.
A Graph will own the sets V and E which define it. By using the set class for V and E we eliminate the concern about multiple copies of a vertex. It is also that case that a tuple (u,v) cannot be accidentally stored more than once, but we will need to avoid accidentally storing both (u,v) and (v,u). A Graph will also own a Dictionary called Adj, which is a particularly efficient data structure for algorithms that would naturally exploit the relationships stored in the Adjacency matrix. It also provides an efficient record of the degree for each vertex. V, E, and Adj are not treated as private objects so that we can directly explore possible algorithms which use them.
In HW13 we introduced the initial version of the Graph class which was very limited while we began to explore methods to be added to the class. Methods which are both relevant to the effective use of Graphs and capable of being efficiently implemented. In that homework we developed a code for plotting a graph and two codes for determining if a graph is connected. One approach was a recursive code that used a depthfirst search. The second approach used a queue and a breadth first search. The Graph class in this homework incorporates what we learned by including methods for plotting the graph, for determining whether the graph is connected, and for creating a list of the components of the graph. These last two methods are based on the breadthfirst search algorithm, which requires that we include the code for the Queue class.
Be sure to check out this new Graph class by doing tab completion on one or more of the Graph objects that you create.

A Queue Class
The following block defines a queue class with five methods  enqueue, dequeue, peek, clear, and display. However, instead of following the Stack class approach and having this own a private deque object, this queue is a subclass of the deque class. So this queue object is a deque. One consequence is that this queue object will inherit the methods of the deque class, which includes the clear method. This can be confirmed with the tab completion in the block following the definition of the Queue class.


Minimum Weighted Spanning Tree
If we include a weight for each edge, then we can make a simple modification to the build_spanning_tree algorithm to obtain Prim's algorithm for finding a Minimum Weighted Spanning. This is a greedy algorithm that will find a spanning tree where the sum of the weights on the edges is minimized. That is, the sum of the weights on the edges of the tree found by Prim's algorithm will be less than or equal to the sum of the weights on the edges of any other spanning tree.
The essential step is to replace the queue, which stores the vertices that have been added to the component, with a priority queue, which contains the edges (prioritizedby their weights) that cross the boundary of the component. The code for Prim's algorithm contains three print statements to provide some insight into how the algorithm behaves.

A priority queue is a container where each item is inserted with a certain priority. When an item is removed, the item with the highest priority is the item that is removed. Priority queues can be implemented using a heap. A heap is a Complete Binary Tree with a partial ordering. A complete binary tree is a binary tree where the tree is filled out from top to bottom, left to right. To be a heap, the complete binary tree must satisfy the following partial ordering criteria.
The priority of the parent must always be equal to or higher than the priority of its children.
This is often referred to as the heap property. The heap property is an invariant which must be true before and after pushing or popping an item.
There is a natural embedding of a complete binary tree into an array using the functions
The following version of the Priority Queue makes the bubbleup and siftdown routines explicit, so that it is possible to extend the class to allow for changes in the priority and other features that are important for discrete event simulation.
This class has been extended to include the routines priority_of(object) and adjust(new_priority, object). These extensions are necessary for the efficient implementation of Dijkstra's algorithm.

Create a Network by adding weights to the Graph, G2. Next find the Minimum Weighted Spanning Tree using Prim's algorithm. Then display the Network and the MST.

The Prime Maze Graph
The following blocks define and display the Prime Maze Graph.


Using the Prime Maze Graph, PMG, and its weights, WPM, find the minimum weighted spanning tree using the Prim function. Using a copy of Gpm, the plot for the Prime Maze Graph, superimpose a plot of the resulting tree with the edges drawn in red.

Shortest Paths
We will start by looking at 3 algorihtms for finding the shortest path between two vertices in a network. The two networks will be G2 and PMG from the previous examples.
For G2 we will find the shortest paths from A to B, A to C, and A to D.
For PMG we will find the shortest paths from A to B, A to R, A to O, and A to W.
The first algorithm is a depthfirst, recursive, backtracking search. Once a vertex has been added to the path it is no longer available. We will use a dictionary labeled, available, rather than a linear search to see if the vertex in already in the path. After we have found one path to the last vertex, we can prune all future branches of the search tree.








The BreadthFirst Search uses a queue that stores tuples consisting of a path and the distance.
Note that if the distance between every adjacent vertex was the same then the breadthfirst search could stop as soon as it found the last vertex. However, since this isn't the case we must keep searching as long as there are candidates. It is also the case that since there are many different paths in the queue, checking for availability requires a linear search to see if the vertex is in the path.








Exercise 1: In the block below discuss the advantages and disadvantages of shortest path algorithms based on depthfirst search versus breadthfirst search.

Dijkstra's Algorithm replaces the queue with a priority queue and builds a tree of the shortest paths from the source to all the other vertices in the network. Each node in the tree records the current parent of the vertex and the distance from the source to the vertex along the shortest path to the parent. As better paths are found the parent and the distance are updated. This necessitates that the priority queue keep track of the index of each object so that the priority of that object can be adjusted.
Once the tree is constructed, finding a specific path is extremely efficient.



Exercise 2: In the block below discuss the advantages and disadvantages of the overhead in computing Dijkstra's Shortest Path Tree versus the two previous Shortest Path algorithms.

Exercise 3: In the block below discuss the similarities and differences between the Minimum Weighted Spanning Tree and Dijkstra's Shortest Path Tree.
