A Class for Graphs

Previously, we started a definition of a graph class that uses our familiar dictionary-based representation. Now, we are providing a skeleton for a graph class that you will be using on the next homework. It follows the same idea as the previous graph class we introduced interactively, but it has more precisely-defined semantics.

1. Complete this graph class. (Note: Updated with more informative documentation strings.)

2. Outside the class definition, add some test code. Your tests should use every method. Your test should define and use more than one instance of the class. A simple structure would be

   1. Define graph objects.
   2. Use methods to add nodes and edges to each graph.
   3. Use methods to look at pieces of each graph.

   The following unit tests will test the whole Graph class (actually the graph object returned by make_empty_graph()). The tests are deliberately set up such that they are independent of the implementation of the Graph class (hence the make_empty_graph() function).   It assumes the following about the submitted code (all requirements are already met by the alternate starting code above):

   • There exists a function (not a method!) in the CodeSkulptor file called make_empty_graph() that returns an empty graph object. That is, place the following function at the very bottom of your Codeskulptor file (no indentation):
     

     	def make_empty_graph():
     	    return Graph()
     	

   • Any method whose code is not yet written must have a single line of code in it, which is “pass”. In Python, pass means “no operation” and having it turns an otherwise empty method body into valid Python syntax, so the code will run even though it returns an incorrect answer. The unit test below will simply fail the methods that have pass for their method body code. Methods with code will be throughly tested however.

   Test your Graph class using OwlTest

3. Make a Graph object that represents the following directed graph:

   

4. You previously wrote a function to create a complete graph. Rewrite it to use this class. That means that the function should not manipulate the explicit representation of the graph. Instead, it should create a Graph object and use its methods.

   Be sure you are able to do this. While this shouldn't be too different from the previous version, it involves a conceptual leap.

   def make_complete(n):
       nodes = range(n) # Make a list of all the nodes in the graph.
   
       # The rest of code is independent of what the nodes are.
       complete = Graph()
   
       for node in nodes:
           complete.add_node(node)
   
           neighbors = set(nodes) # Create an edge to every node
           neighbors.remove(node) # ...except itself
   
           for neighbor in neighbors:
               complete.add_edge(node, neighbor)
   
       return complete  
   

5. You previously wrote directed_random_neighbors() to create a random graph. Rewrite it to use this class.

6. Write a function is_equal_graph(graph1, graph2) that takes two graph objects. It returns whether the two graphs are equal in that they use the same node names and have corresponding edges. That is, whenever one graph has an edge from node_from to node_to, so does the other. Assume that the node names are immutable (e.g., strings).

   Hint: There is a simple way of implementing this that requires no loops.

zip()

Look at the CodeSkulptor documentation for the function zip(). We are going to work with it briefly because it can be useful on the next assignment. (You don't have to use it, but it can shorten your code.)

1. Define my_zip(list1, list2) which behaves like zip() on two lists. Defining your own version is one way to understand a function.

   Test your my_zip() function using OwlTest

2. Define multiply_lists(list1, list2). Assume the two inputs lists are the same length. It returns a list of numbers where you've multiplied the corresponding elements. Use zip().

   Test your multiply_lists() function using OwlTest

3. For comparison, define multiply_lists_nozip(list1, list2) without zip().

   Test your multiply_lists_nozip() function using OwlTest

4. Define combine_matrix_vec(matrix, vector). You are given a list of lists of numbers, i.e., a matrix, and another list of numbers, i.e., a vector. Assume all of the lists are of the same length. Return a new matrix of the same size where the ith element of the vector is multiplied by each number in the ith row of the original matrix. Use zip(). Note that this is a simpler operation that the usual multiplication of a matrix and a vector.

   Given:
   [[1 2 3]
    [2 3 4]
    [3 4 5]]
   and:
   [3 2 1]
   
   returns:
   [[3 6 9]
    [4 6 8]
    [3 4 5]]
   

   Test your combine_matrix_vec() function using OwlTest

What's Next?

These notes, along with the current assignment, are the last of the content focused on programming language constructs. For the rest of the course, we will focus on applying these constructs to artificial neural networks (ANNs).