Assignment added as file
Assignment 4: Graphs Assignment 4: Graphs UMaine COS 350 Assigned: 12 March 2020 Due: 27 March 2020 In this assignment, you will build a Python graph package that will support future homework assignments. The package should be named graphs.py; you should be able to use it in other programs by: import graphs or: from graphs import * This package must be object-oriented. In the remainder of this homework description, we’ll look at the classes and methods graphs.py will provide. Jupyter notebooks You will be turning in a Jupyter notebook for this assignment. I believe most of you have used Jupyter notebooks for Python devel- opment. If not, see jupyter.org and click on the “Jupyter Notebook” link under “User Interfaces”. If you need to install Jupyter, the doc- umentation guides you through the process. I recommend installing it (and Python) using Anaconda. (You should be using Python 3.5 or greater, by the way, for this class; I’m using 3.6 for the code in this document.) Develop all your code and documentation and show your tests of your code in a single Jupyter notebook; this is what you will turn in. I’ll provide a blank notebook you can start with that contains the code described below. Class Graph You will need to create a class, Graph, that is the base class for graphs. A graph is, of course, just a set of vertices and edges, but there are many different ways to implement them (edge lists, etc.), just as there are different types of graphs (digraph, weighted digraph, etc.). Dif- ferent implementations have different properties, for example, how much time it takes to find an adjacent vertex or incident edge. The Graph class won’t be directly implemented. Rather, its sub-classes will implement graphs in various ways so that the best implementa- tion can be used for the algorithm you’re working on. http://jupyter.org assignment 4: graphs umaine cos 350 2 So let’s define the Graph class: 1 ### 2 ### Graph class 3 ### 4 ### This class is meant to be specialized for whatever implementation of graphs you 5 ### want to create. 6 ### 7 8 class Graph (): Although we don’t want to necessarily instantiate this class, we’d like to be able to instantiate its subclasses all the same way unless there’s a need not to. So let’s create a default initialization function that takes two (optional) arguments, graph_desc, a Python list that describes the graph, and properties, that is meant to allow you to use when specializing this class: 9 def __init__(self,graph_desc=None,properties=None): The argument graph_desc should be a list whose first element describes the kind of graph it is and the rest describing the edges and vertices. The description of the graph should be one of ’graph’ or ’digraph’, at least, though you may want to add additional types as you write specialized subclasses. The edges and vertices are specified themselves as lists. If there’s a single element, it’s a vertex, else it’s an edge. Edge specifications are expected to have either two or three elements, with the first two being the source and destination of the edge and the (optional) third being a weight. For example, [’graph’ [’a’, ’b’], [’b’, ’c’], [’c’, ’d’], [’d’, ’b’]] would specify the graph in Fig. ??, and [’digraph’ [’a’, ’b’, 3], [’b’, ’c’, 2], [’c’, ’d’, 5], [’d’, ’b’, 1]] would specify the graph in Fig. ??. Note that [’graph’ [’a’, ’b’], [’b’, ’c’], [’c’, ’d’], [’d’, ’b’]] and [’graph’ [’a’], [’b’], [’a’, ’b’], [’b’, ’c’], [’c’, ’d’], [’d’, ’b’]] are specifications of the same graph, with the latter just directly specifying two of the vertices. a b c d Figure 1: Example graph. a b 3 c 2 d 5 1 Figure 2: Example digraph. For our implementation of the initialization function, we ignore weights and whether or not something is a digraph; you’ll need to assignment 4: graphs umaine cos 350 3 handle those aspects of things in your subclasses. First, set up the instance variables in the case of no description: 10 self.properties = properties 11 12 self.vertices = {} 13 self.edges = [] If there is a description, though, we need to put the first element (e.g., ’digraph’) onto the list of properties: 14 if graph_desc: 15 if properties == None: 16 self.properties = [graph_desc[0]] 17 else: 18 self.properties.append(graph_desc[0]) Now we need to parse the rest of the description, i.e., the edge and vertex descriptions. For this base class, we ignore any weights. We define two other instance variables as we parse: • vertices: This is a dictionary for the base class, with the keys being vertex names and the values being instances of Vertex. • edges: This is just a list of instances of class Edge. It’s here that you’ll want to make some changes about how you store vertices and edges in the subclasses; this is just a placeholder that could be useful: 19 for ele in graph_desc[1:]: 20 if ele[0] not in self.vertices.keys(): 21 self.vertices[ele[0]] = Vertex(self,ele[0]) 22 if len(ele) > 1: #then it’s a real edge description 23 if ele[1] not in self.vertices.keys(): 24 self.vertices[ele[1]] = Vertex(self,ele[1]) 25 26 # Not checking for duplicate edges here: 27 self.edges.append(Edge(self, self.vertices[ele[0]], 28 self.vertices[ele[1]])) Just for fun, let’s create some methods to get vertices, edges, etc.: 29 def find_vertex(self,name): 30 if name in self.vertices.keys(): 31 return self.vertices[name] 32 else: 33 return None assignment 4: graphs umaine cos 350 4 34 35 def add_vertex(self,name): 36 self.vertices[name] = Vertex(self,name) 37 38 def find_edge(self,v1,v2): 39 for e in self.edges: 40 if e.v1.name == v1 and e.v2.name == v2: 41 return e 42 return None 43 44 def add_edge(self,v1,v2): 45 source = self.find_vertex(v1) 46 dest = self.find_vertex(v2) 47 if source == None: 48 self.add_vertex(v1) 49 source = self.vertices[v1] 50 if dest == None: 51 self.add_vertex(v2) 52 dest = self.vertices[v2] 53 54 self.edges.append(Edge(self,source,dest)) 55 56 def incident_edges(self,v): 57 if not isinstance(v,Vertex): 58 v = self.find_vertex(v) 59 incident = [] 60 for e in self.edges: 61 if e.v1 == v or e.v2 == v: 62 incident.append(e) 63 return incident And to see what’s in a graph, we’ll create two other methods, to_list and to_gv. The first will return a list suitable for passing to the initialization function for Graph; i.e., to copy a graph g, you could do: g1 = Graph(g.to_list()) The second function will print out a graphviz “dot” representation for the graph; you could, for example, cut and paste this to a file foo.gv, then (on a Mac or Linux box, anyway) do: dot -Tpdf foo.gv > foo.pdf to get a PDF diagram of the file (e.g., like those in Fig. ?? and Fig. ??). 64 def to_list (self): assignment 4: graphs umaine cos 350 5 65 if ’digraph’ in self.properties: 66 output = [’digraph’] 67 else: 68 output = [’graph’] 69 70 for vname in self.vertices.keys(): 71 output.append([vname]) 72 73 for e in self.edges: 74 output.append([e.v1.name,e.v2.name]) 75 76 return output 77 78 def to_gv(self): 79 desc = self.to_list() 80 81 print(desc[0], " {") 82 83 if desc[0] == ’digraph’: 84 sep = " -> " 85 else: 86 sep = " -- " 87 88 for thing in desc[1:]: 89 if len(thing) == 1: # vertex 90 print(’ ’, thing[0]) 91 elif len(thing) > 2: # edge, weight exists 92 print(’ ’, thing[0], sep, thing[1], ’ ’, ’[label="’, thing[2], 93 ’"]’) 94 else: #no weight 95 print(’ ’, thing[0],sep,thing[1]) 96 print(’}’) We’ll also provide two other base classes, one for vertices and one for edges, that are used in the initialization function of Graph: 97 98 class Vertex (): 99 def __init__(graph,name): 100 self.graph = graph 101 self.name = name 102 103 104 class Edge (): 105 def __init__(graph,v1,v2): assignment 4: graphs umaine cos 350 6 106 self.graph = graph 107 self.v1 = v1 108 self.v2 = v2 Note that these are very minimal, and you’ll need to extend them for your own use. The Vertex class just holds the name of the vertex and a pointer back to the graph it’s part of, and the Edge class just holds a pointer to the graph and pointers to the two end points of the edge (expected to be instances of Vertex). Your turn Classes Now you will need to complete the package. Your graph.py package should include these classes, ultimately based on the Graph class: 1. AdjList: Implements a graph as a an adjacency list. 2. EdgeList: Implements a graph as an edge list. 3. AdjMatrix: Implements a graph as an adjacency matrix. Each of these should be able to handle undirected graphs, digraphs, and weighted or unweighted edges. Methods You should write all the methods needed to access vertices and edges in your subclasses (or use default methods, if those work). This includes the following (some of which are implemented already for the base class above): • add_vertex, delete_vertex: add/delete a vertex • add_edge, delete_edge: add/delete edge • all_vertices: return all vertices; should take an optional argu- ment to cause it to return either a list of Vertex instances or a list of names of the vertices. • all_edges: return all edges; should take an optional argument to cause it to return a list of Edge instances or a list of the form [[’a’, ’b’], [’b’, ’c], ...] • to_list: return a description of the graph in a from that could be given to Graph() or similar instantiation function. assignment 4: graphs umaine cos 350 7 • find_edge: find an edge given an Edge instance or list of the form [v1,v2] of vertex names. • find_vertex: find a vertex given its name. • incident_edges: return a list of all edges incident on a vertex • adjacent_vertices: return all vertices adjacent to another vertex • edge_cost: return cost of an edge • path_cost: return the cost of a path, where a path is a list of vertex names, e.g., [’a’, ’b’, ...] • adjacent_to: return True if v1 is adjacent to v2 • incident_to: return True if an edge is incident to a vertex. In addition, write DFT, a depth-first traversal method for the classes that, given a vertex, does a depth-first traversal and returns a spanning tree rooted at that vertex. (Note that the spanning tree is itself a graph, and should be returned as an instance of Graph or one of its subgraphs.