MATH 3600 HW13

2849 days ago by warner

MATH 3600 - HW13

 

Team names: _____________________________

_____________________________

_____________________________

Date: ________________

 
       

Graphs

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).

class Graph(object): '''Represents a graph''' def __init__(self, vertices, edges): '''A Graph is defined by its set of vertices and its set of edges.''' self.V = set(vertices) self.E = set([]) self.Adj = {} self.add_edges(edges) print '(Initializing a graph with %d vertices and %d edges)' % (len(self.V),len(self.E)) def add_vertices(self,vertex_list): ''' This method will add the vertices in the vertex_list to the set of vertices for this graph. Since V is a set, duplicate vertices will not be added to V. ''' for v in vertex_list: self.V.add(v) self.build_Adj() def add_edges(self,edge_list): ''' This method will add a list of edges to the graph It will insure that the vertices of each edge are included in the set of vertices (and not duplicated). It will also insure that edges are added to the list of edges and not duplicated. ''' for s,t in edge_list: if (s,t) not in self.E and (t,s) not in self.E: self.V.add(s) self.V.add(t) self.E.add((s,t)) self.build_Adj() def build_Adj(self): self.Adj = {} for v in self.V: self.Adj[v] = [] for e in self.E: s,t = e self.Adj[s].append(t) self.Adj[t].append(s) def Degree(self,v): return len(self.Adj[v]) 
       
# Build a simple example V = ['A', 'B', 'C', 'D', 'E', 'F'] E = [('A','E'),('C','F'),('B','D'),('A','F'),('C','E')] G1 = Graph(V,E) print 'G1.V',G1.V print 'G1.E',G1.E print 'G1.Adj',G1.Adj print 'Degrees' for v in V: print v,G1.Degree(v) 
       
# Build a second example usig the same vertices, but more edges E2 = [('A','E'),('C','F'),('B','D'),('A','F'),('C','E'),('A','B'),('C','D')] G2 = Graph(V,E2) print 'G2.V',G2.V print 'G2.E',G2.E print 'G2.Adj',G2.Adj print 'Degrees' for v in V: print v,G2.Degree(v) 
       

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.

def Gplot(G,Vc): # G is the Graph # Vc is a dictionary with the coordinates for each vertex g = Graphics() # Create the list of coordinates # Include the vertices as red dots # Include the names of the vertices for v in G.V: # Include the edges for edge in G.E: return g 
       
Vcoord = {'A':(1,10),'B':(5,5),'C':(1,-10),'D':(5,-5),'E':(3,1),'F':(-5,1)} g1 = Gplot(G1,Vcoord) show(g1,figsize=(3,3),axes=False) 
       
# The vertices and their coordinates are the same for both G1 and G2. g2 = Gplot(G2,Vcoord) show(g2,figsize=(3,3),axes=False) 
       

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 breadth-first search and depth-first search. We will start with breadth-first search. This algorithm makes use of a queue.  So the first thing to do is to add the Queue class to our code.

A Queue Class

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.

import collections ''' This block defines a Queue class as a subclass of the collections.deque class This class inherits all the methods of the deque class and adds the methods enqueue and dequeue. Daniel D. Warner September 8, 2010 ''' class Queue(collections.deque): def enqueue(self,x): self.appendleft(x) def dequeue(self): if 0 < len(self): return self.pop() else: return None 
       

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 breadth-first search all the adjacent vertices that have not been visited are marked as visited and placed in the queue for later processing. In the depth-first 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 Breadth-First Code 

def is_connected_bf(G,v0): # G is the Graph # v0 is a specified vertex. Visited = {} for v in G.V: Visited[v] = False Q = Queue() Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() for v in G.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) for v in G.V: if not Visited[v]: # The Graph is not connected return False # The Graph is connected return True 
       
if is_connected_bf(G1,'A'): print "G1 is connected" else: print "G1 is not connected" 
       
if is_connected_bf(G2,'A'): print "G2 is connected" else: print "G2 is not connected" 
       


The Depth-First Code

def is_connected(G,u,Visited): Visited[u] = True for v in G.Adj[u]: if not Visited[v]: is_connected(G,v,Visited) def is_connected_df(G,v0): # G is the Graph # v0 is a specified vertex. Visited = {} for v in G.V: Visited[v] = False is_connected(G,v0,Visited) for v in G.V: if not Visited[v]: # The Graph is not connected return False # The Graph is connected return True 
       
if is_connected_df(G1,'A'): print "G1 is connected" else: print "G1 is not connected" 
       
if is_connected_df(G2,'A'): print "G2 is connected" else: print "G2 is not connected" 
       

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)

#g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))
            #show(g,figsize=(3,3)#g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))
            #show(g,figsize=(3,3),axes=False),axes=False)g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))

These will enable you to see the order in which the breadth-first search examines the vertices of the graph.

def is_connected_bf_g(G,v0,g): # G is the Graph # v0 is a specified vertex. # g is the Graphics object for displaying G 
       
is_connected_bf_g(G1,'A',g1) 
       
is_connected_bf_g(G2,'A',g2) 
       

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)

#g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))
            #show(g,figsize=(3,3)#g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))
            #show(g,figsize=(3,3),axes=False),axes=False)g += line([Vcoord[u],Vcoord[v]],rgbcolor=(1,0,0))

These will enable you to see the order in which the depth-first search examines the vertices of the graph.

def is_connected_g(G,u,Visited,g): Visited[u] = True def is_connected_df_g(G,v0,g): # G is the Graph # v0 is a specified vertex. # g is the Graphics object for displaying G 
       
is_connected_df_g(G1,'A',g1) 
       
is_connected_df_g(G2,'A',g2) 
       

 

Graph Theory Started Here 

The Bridges of Königsberg is old puzzle that was solved by Euler in 1735.  The city of Königsberg in Prussia (now KaliningradRussia) 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"

Koenigsberg 1652

Kv = ['A','Aa','B','Bb','C','D'] Ke = [('A','C'),('Aa','C'),('A','Aa'),('A','D'),('B','C'),('Bb','C'),('B','Bb'),('B','D'),('C','D')] print Kv print Ke Koenigsberg = Graph(Kv,Ke) 
       
VKcoord = {'A':(4,-4),'Aa':(1,-4),'B':(4,6),'Bb':(1,6),'C':(6,2), 'D':(11,2)} print VKcoord 
       
Kg = Gplot(Koenigsberg, VKcoord) show(Kg,figsize=(3,3),axes=False) 
       

An Eulerian Path is a path that crosses each edge exactly once, and aEulerian 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.

  1. "Eulerian cycle is possible"
  2. "Eulerian path is possible"
  3. "No Eulerian path is possible"

Your function should use the Degree method of the Graph class.

def Eulerian(G): 
       
print 'G1' Eulerian(G1) print '\nG2' Eulerian(G2) print '\nKoenigsberg' Eulerian(Koenigsberg) 
       

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.

def Eulerian_path(path, G, Elist, count): # if Elist, the list of edges, is empty, then print # the path and increase the count if len(Elist) == 0: # otherwise walk through E, looking for an edge # that contains the last vertex in the path else: # 1. add the other vertex from the edge to the path # 2. create a new edge list with this edge removed # 3. recursively call Eulerian_path using the # augmented path and the new (and smaller) edge list. # 4. clean up after returning from the recursive call. # In either case return the count. return count 
       
# Call Eulerian_path with a path consisting of the starting vertex, # the Graph (not needed for this approach), the list of edges, and count = 0 Eulerian_path(['A'],G2,list(G2.E),0) 
       
Eulerian_path(['B'],G2,list(G2.E),0) 
       
Eulerian_path(['A'],Koenigsberg,Ke,0)