MATH 3600 HW15

2840 days ago by warner

MATH 3600 - HW15


Your names: _____________________________


Date: ________________



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 depth-first 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 breadth-first 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.

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]) def plot(self,Vc): # Vc is a dictionary with the coordinates for each vertex g = Graphics() # Create the list of coordinates Vcoords = [Vc[v] for v in self.V] # Include the vertices as red dots g += point2d(Vcoords,rgbcolor=(1,0,0),size=25) # Include the names of the vertices for v in self.V: g += text(v,(1.1*Vc[v][0], 1.1*Vc[v][1])) # Include the edges for edge in self.E: u,v = edge g += line([Vc[u],Vc[v]]) return g def build_Components(self): Visited = {} for v in self.V: Visited[v] = False components = [] Q = Queue() for v0 in self.V: if not Visited[v0]: comp = [] Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() comp.append(u) for v in self.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) components.append(comp) return components def is_connected(self): Visited = {} for v in self.V: Visited[v] = False Q = Queue() for v0 in self.V: if not Visited[v0]: Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() for v in self.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) break for v in self.V: if not Visited[v]: # The Graph is not connected return False # The Graph is connected return True 

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.

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, dequeue, peek, and display. Daniel D. Warner February 26, 2012 ''' class Queue(collections.deque): def enqueue(self,x): ''' enqueue adds an item to the end of the queue.''' self.appendleft(x) def dequeue(self): ''' dequeue removes an item from the front of the queue.''' if 0 < len(self): return self.pop() else: return None def peek(self): if 0 < len(self): p = self.pop() self.append(p) return p else: return None def display(self): print self 
# Build a simple example V = ['A', 'B', 'C', 'D', 'E', 'F'] Vcoord = {'A':(1,10),'B':(5,5),'C':(1,-10),'D':(5,-5),'E':(3,1),'F':(-5,1)} E = [('A','E'),('C','F'),('B','D'),('A','F'),('C','E')] G1 = Graph(V,E) # Check out the Graph methods with tab completion G1 
print 'G1.V',G1.V print 'G1.E',G1.E print 'G1.Adj',G1.Adj g1 = G1.plot(Vcoord) show(g1,figsize=(3,3),axes=False) print 'Degrees' for v in V: print v,G1.Degree(v) print G1.build_Components() if G1.is_connected(): print 'G1 is connected' else: print 'G1 is NOT connected' 
# Build a second example using 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 g2 = G2.plot(Vcoord) show(g2,figsize=(3,3),axes=False) print 'Degrees' for v in V: print v,G2.Degree(v) print G2.build_Components() if G2.is_connected(): print 'G2 is connected' else: print 'G2 is NOT connected' 
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')] VKcoord = {'A':(4,-4),'Aa':(1,-4),'B':(4,6),'Bb':(1,6),'C':(6,2), 'D':(11,2)} Koenigsberg = Graph(Kv,Ke) print Koenigsberg.V print Koenigsberg.E print VKcoord Kg = Koenigsberg.plot(VKcoord) show(Kg,figsize=(3,3),axes=False) print 'Degrees' for v in Koenigsberg.V: print v,'\t',Koenigsberg.Degree(v) print Koenigsberg.build_Components() if Koenigsberg.is_connected(): print 'Koenigsberg is connected' else: print 'Koenigsberg is NOT connected' 


 Tree is a connected acyclic graph.  Connected means that there is a path between every pair of vertices.  Acyclic means that there are no cycles.  

It is straightforward to show by induction that if a tree has $nV$ vertices, then it has exactly $nV-1$ edges.

Both the depth-first and breadth-first algorithms for determining whether a graph is connected are actually building a tree, which, when the graph is connected, is a spanning tree of the graph. In the while loop of the is_connected method we dequeue a vertex, u, from the queue which is part of the connected component. Note that all vertices are marked as visited immediately before being enqueued. We then check to see if vertex, u, has any adjacent vertices, v, which have not been visited. If we find one we mark it as visited and enqueue it.  To build the spanning tree all we need to do at this stage is to add the edge (u,v) to the list of edges. It makes sense to give this list of edges the name, tree, since it will always be a tree. Every vertex that is selected is adjacent to a vertex that is already in the growing tree, so the tree is connected. Also since it has not been visited, adding this edge can not create a cycle.

Exercise 1:  Complete the function, build_spanning_tree, then run the following three blocks.

def build_spanning_tree(G): Visited = {} for v in G.V: Visited[v] = False tree = [] Q = Queue() for v0 in G.V: # # # # # # # # # # break return tree 
tree1 = build_spanning_tree(G1) if len(tree1)+1 != len(G1.V): print 'This graph does NOT have a spanning tree' for edge in tree1: u,v = edge g1 += line([Vcoord[u], Vcoord[v]],rgbcolor=[1,0,0]) show(g1,figsize=(3,3),axes=False) 
tree2 = build_spanning_tree(G2) for edge in tree2: u,v = edge g2 += line([Vcoord[u], Vcoord[v]],rgbcolor=[1,0,0]) show(g2,figsize=(3,3),axes=False) 
tree3 = build_spanning_tree(Koenigsberg) for edge in tree3: u,v = edge Kg += line([VKcoord[u], VKcoord[v]],rgbcolor=[1,0,0]) show(Kg,figsize=(3,3),axes=False) 

Exercise 2:  Define and display a graph with 6 vertices and 5 edges which is not a tree.

# # # # # 
# Consider the following list of edges edges = [('Mabel','Eve'),('Alice','Carol'),('Eve','Frank'),('Alice','Doug'),('Frank','Ginger'),\ ('Ursala','Howard'),('Carol','Irene'),('Frank','Jeff'),('Doug','Kathy'),('Bob','Luis'),\ ('Alice','Bob'),('Bob','Mabel'),('Ginger','Norm'),('Howard','Oprah'),('Carol','Peter'),\ ('Kathy','Queen'),('Mabel','Ursala'),('Luis','Ronald'),('Ginger','Sarah'),('Irene','Tom'),\ ('Jeff','Vince'),('Peter','Wanda'),('Oprah','Xanthia'),('Norm','Yaakov'),('Luis','Zandra')] 
G3 = Graph([],edges) print 'nV:',len(G3.V) print 'nE:',len(G3.E) print 'Is G3 connected?',G3.is_connected() 

Since G3 has 26 vertices and 25 edges and is connected, it is a tree. However, we almost always draw a tree as a rooted tree, with the root at the top and the leaves at the bottom.

Rooted Tree is a tree with a distinguished vertex called the root.  This induces an ordering relationship on the vertices, which is often referred to as a parent-child relationship.  The root represents the first generation, all the vertices directly connected to the root by an edge in the graph are the children of the root, the second generation. Similarly any vertex, other than the root, which is connected to a second generation vertex by an edge is a child of that vertex, a member of the third generation, and so forth.  Any vertex which does not have a child is called a leaf.  Thus every vertex except the root has a single parent, and any vertex which is not a leaf will have one or more children.

If a graph is a tree, then we can choose any vertex as the root. The following depth-first prefix tree walk displays the rooted tree with the explicit parent child relationship indicated by the level of indentation.

def print_tree_df(level, parent, Visited, G): print level*' ',parent Visited[parent] = True children = G.Adj[parent] for child in children: if not Visited[child]: print_tree_df(level+1,child,Visited,G) 
root = 'Alice' Visited = {} for v in G3.V: Visited[v] = False print_tree_df(0,root,Visited,G3) 

An important question to ask about this routine is what does it do if applied to an arbitrary graph.

Exercise 3:  The following two blocks display G1 and G2 with the trees constructed by the build_spanning_tree routine. Add code after each display, which will invoke the print_tree_df for the appropriate graph with 'A' as the root. Then briefly discuss whether the two trees rooted at 'A' are the same and if not why not. It may be quite helpful to review the graphic displays generated by Exercises 2 and 3 in HW13.

show(g1,figsize=(3,3),axes=False) root = 'A' Visited = {} # # # 
show(g2,figsize=(3,3),axes=False) root = 'A' Visited = {} # # # 
# # # 

Exercise 4:  A binary tree is a tree where the degree of each vertex is less than or equal to 3. Write a short code that determines whether G3 is a binary tree. 

# # # # # 

A rooted binary tree is a rooted tree in which every vertex has 0, 1, or 2 children.

Exercise 5:  With Alice as the root, the binary tree, G3, is not a rooted binary tree. Briefly explain why. Then choose a node for the root which does produce a rooted binary tree and display the indented depth-first print out of G3 with that root.

# # 
# # # # # 

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.

def Prim(G,W): # simplify edge lookup WW = copy(W) for edge in W: s,t = edge WW[(t,s)] = W[edge] nV = len(G.V) Visited = {} for v in G.V: Visited[v] = False spanning_tree = [] PQ = PriorityQueue() weight = 0 for u in G.V: Visited[u] = True for v in G.Adj[u]: w = WW[(u,v)] PQ.push(w,(u,v)) while PQ.is_not_empty() and len(spanning_tree)<(nV-1): # print PQ._pq s,t = PQ.pop() # print (s,t),WW[(s,t)] if not Visited[t]: Visited[t] = True spanning_tree.append((s,t)) weight += WW[(s,t)] # print spanning_tree,weight for v in G.Adj[t]: if not Visited[v]: w = WW[(t,v)] PQ.push(w,(t,v)) return spanning_tree,weight 

A Priority Queue Class

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

  • parent(n) = (n-1)//2
  • leftchild(n) = 2*n + 1
  • rightchild(n) = 2*n + 2

The following version of the Priority Queue makes the bubble-up and sift-down 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.

class PriorityQueue(): ''' The arguments passed to a PriorityQueue must consist of a priority and an object. It must be possible to compare priorities using the < operator. ''' def __init__(self): self._pq = [] def _parent(self,n): return (n-1)//2 def _leftchild(self,n): return 2*n + 1 def _rightchild(self,n): return 2*n + 2 def push(self, pri, obj): self._pq.append((pri,obj)) n = len(self._pq) self._bubble_up(n-1) def _bubble_up(self,c): while 0<c: c_item = self._pq[c] p = self._parent(c) p_item = self._pq[p] if c_item < p_item: self._pq[p] = c_item self._pq[c] = p_item c = p else: break def pop(self): n = len(self._pq) if 0==n: obj = None elif 1==n: pri,obj = self._pq.pop() else: pri,obj = self._pq[0] self._pq[0] = self._pq.pop() self._sift_down(0) return obj def _sift_down(self,p): n = len(self._pq) while p<n: p_item = self._pq[p] lc = self._leftchild(p) if n <= lc: break c_item = self._pq[lc] c = lc rc = self._rightchild(p) if rc < n: r_item = self._pq[rc] if r_item < c_item: c_item = r_item c = rc if p_item <= c_item: break self._pq[p] = c_item self._pq[c] = p_item p = c def is_not_empty(self): if 0 < len(self._pq): return True else: return False 
W = {('A','B'):7, ('A','E'):18, ('C','F'):21, ('D','C'):13, ('B','D'):14, ('A','F'):19, ('C','E'):16} G2plot = G2.plot(Vcoord) show(G2plot,figsize=(3,3),axes=False) tree,weight = Prim(G2,W) if len(tree)==(len(G2.V)-1): print 'Minimum Spanning Tree:',tree print 'Weight:',weight for edge in G2.E: s,t = edge if (s,t) in W: w = W[(s,t)] else: w = W[(t,s)] xs,ys = Vcoord[s] xt,yt = Vcoord[t] xw,yw = ((xs+xt)/2,1/2+(ys+yt)/2) G2plot += text(w,(1.1*xw,1.1*yw)) for edge in tree: s,t = edge xs,ys = Vcoord[s] xt,yt = Vcoord[t] G2plot += line2d([(xs,ys),(xt,yt)],rgbcolor=(1,0,0)) show(G2plot,figsize=(3,3),axes=False) else: print 'Disconnected Subtree:',tree 

Exercise 6: Briefly discuss why the edge (A,E) made it to the top of the Priority Queue, but did not end up in the MST.

# # # # 

The Prime Maze Graph

The following blocks define and display the Prime Maze Graph.

# The dictionary of edges and weights for the Prime Maze WPM = {('A', 'B'): 2, ('A', 'C'): 8, ('A', 'D'): 10, ('A', 'E'): 5,\ ('B', 'D'): 14, ('B', 'J'): 17, ('C', 'D'): 12, ('C', 'G'): 3,\ ('C', 'H'): 10, ('D', 'H'): 4, ('E', 'F'): 2, ('E', 'N'): 6,\ ('F', 'G'): 6, ('F', 'O'): 6, ('G', 'O'): 4, ('H', 'T'): 8,\ ('I', 'J'): 8, ('I', 'K'): 4, ('I', 'L'): 6, ('J', 'M'): 10,\ ('J', 'S'): 6, ('K', 'P'): 12, ('K', 'Q'): 12, ('L', 'M'): 12,\ ('L', 'Q'): 8, ('M', 'R'): 8, ('N', 'O'): 2, ('N', 'V'): 4,\ ('O', 'V'): 12, ('P', 'T'): 6, ('P', 'U'): 4, ('Q', 'R'): 10,\ ('R', 'S'): 12, ('S', 'W'): 13, ('T', 'U'): 14, ('U', 'W'): 10,\ ('V', 'W'): 2 } 
PMV = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','P','Q','R','S','T','U','V','W'] PMcoord = {'B':(-3,3),'A':(0,3),'E':(3,3)} PMcoord['J']=(-3,2); PMcoord['D']=(-1,2); PMcoord['C']=(1,2); PMcoord['F']=(2,2) PMcoord['I']=(-1,1); PMcoord['H']=(0,1); PMcoord['G']=(1,1) PMcoord['M']=(-2,0); PMcoord['L']=(-1,0); PMcoord['K']=(0,0); PMcoord['T']=(1,0); PMcoord['O']=(2,0); PMcoord['N']=(3,0) PMcoord['R']=(-2,-1); PMcoord['Q']=(-1,-1); PMcoord['P']=(0,-1); PMcoord['U']=(2,-1) PMcoord['S']=(-3,-2); PMcoord['W']=(0,-2); PMcoord['V']=(3,-2) # print PMcoord 
# Construct the Prime Maze Graph and display it PMG = Graph([],WPM.keys()) print 'Graph of the Prime Maze' Gpm = PMG.plot(PMcoord) for edge in PMG.E: s,t = edge xs,ys = PMcoord[s] xt,yt = PMcoord[t] w = WPM[edge] Gpm += text(w,((xs+xt)/2, 0.2+(ys+yt)/2)) show(Gpm,axes=False) 

Exercise 7:  Using the Prime Maze Graph, PMG, and its weights, WPM, find the minimum weighted spanning tree using the Prim function.  You should feel free to comment out the statement in the Prim function that prints the Priority Queue.  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.

# # # # # # # # # # # #