
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.
This initial version of the Graph class will be very limited while we 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.
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 addition to the __init__ method this preliminary definition of the Graph class includes four methods: add_vertices, add_edges, build_Adj, and Degree.
The vertices are the keys to the Adj dictionary and for each vertex the value is the list of vertices that it is adjacent to (that is, the vertices to which it is connected to with a single edge).



Exercise 1: Complete the function, Gplot, which generates a plot of a graph given the Graph and a dictionary containing the coordinates (an ordered pair) for each vertex.



Once you have Exercise 1 working correctly you should easily see that the graph G1 has two components. One component consists of the vertices B and D. The other consists of the vertices A, C, E, and F. You should also easily see that G2 is a connected Graph.
After we have created a Graph from the defining lists of vertices and edges, one of the first questions is whether the graph is connected. There are two algorithmic approaches to answering this question. They are breadthfirst search and depthfirst search. We will start with breadthfirst search. This algorithm makes use of a queue. So the first thing to do is to add the Queue class to our code.
The following block defines a queue class with two methods  enqueue and dequeue. 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. This can be confirmed with the tab completion in the block following the definition of the Queue class.

Both the algorithms for answering the "is this graph connected?" utilize the same general strategy. First create a dictionary, Visited, for all the vertices and initialize it to show that none of the vertices have been visited. Then pick an arbitrary vertex, mark it as visited, and inspect all the vertices that it is adjacent to. In the breadthfirst search all the adjacent vertices that have not been visited are marked as visited and placed in the queue for later processing. In the depthfirst search when a vertex is selected it is marked as visited and we start a loop over its adjacent vertices. However instead of postponing the examination of the vertices which had not been visited until we have looked at all the children, we recursively examine the vertices as soon as we find an appropriate one. The process is finished when either the queue is empty or the top most loop has been completed. Then if all vertices have been visited the graph is connected and the function returns True, otherwise it is not connected and the function returns False.
The BreadthFirst Code



The DepthFirst Code



Exercise 2: Copy the code from the routine is_connected_bf(G,v0). Change the name to is_connected_bf_g(G,v0,g) and include a Graphics object, g, that contains a plot of the Graph being examined as a third argument. In the code where a vertex is about to be added to the queue include the following two lines of code where g is the Graphics object.
g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))
show(g,figsize=(3,3),axes=False)
These will enable you to see the order in which the breadthfirst search examines the vertices of the graph.



Exercise 3: Copy the code from the routine is_connected_df(G,v0). Change the name to is_connected_df_g(G,v0,g) and include a Graphics object, g, that contains a plot of the Graph being examined as a third argument. In the code where a vertex is about to be examined recursively include the following two lines of code where g is the Graphics object.
g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))
show(g,figsize=(3,3),axes=False)
These will enable you to see the order in which the depthfirst search examines the vertices of the graph.



The Bridges of Königsberg is old puzzle that was solved by Euler in 1735. The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges. Euler reduced the problem to the graph problem where each land mass was represented by a vertex and each bridge was represented by an edge. The following block defines and displays the related graph. 'A' and 'Aa' denote the same land mass as do 'B' and 'Bb"



An Eulerian Path is a path that crosses each edge exactly once, and an Eulerian Cycle is an Eulerian Path that ends up where it started.
The first observation is that a graph must be connected in order to have an Eulerian path. Then the key idea in finding an Eulerian path is that for any vertex in the path except possibly the first and last vertices, we have to come to the vertex on one edge and leave on a different edge. Thus we see that the degree of any interior vertex on the path must be even. Consequently, for an Eulerian cycle all the vertices must be of even degree, and for an Eulerian path all the vertices must be of even degree except the first and last vertices of the path.
Exercise 4: Write a function that given a graph analyzes the graph and the degrees of each node and prints one of the following 3 strings.
Your function should use the Degree method of the Graph class.


Exercise 5: Write a (recursive) Backtrack Routine that given a graph and a starting vertex attempts to find all Eulerian paths that start at that vertex.





