Assignment 6

Put all your answers in one CodeSkulptor file. Put text answers in Python comments. Use Python comments to clearly mark each problem number.

Work in assigned pairs on this assignment. Submit it on OWL-Space, under Assignment 6. Only the first person listed in the pair should submit the Codeskulptor URL. Put the pair designation as posted, (NetID1, NetID2), at the top of your submission as well as in Python comments at the top of your CodeSkulptor code. Including the person's actual names too would be nice.

As with the previous assignments, your grade will partly depend on your code style.

• Docstrings — Every function should have a docstring that describes what the function does, including relating any outputs to the inputs.
• Code reuse — Wherever reasonable you should reuse functions that have been defined previously on this assignment, on a previous assignment, or in class.

Be sure to read the course policies.

Graphs, Classes, and Objects (100 points total)

1. (1 point)

   In class, you completed a dictionary-based graph class definition.

   • Copy the class and rename it as Graph1.
   • Copy the factory function and rename it as make_empty_graph1(). Also, edit it so that it uses the Graph1() constructor.
   • Also copy the factory function ane rename it as make_empty_graph2()Graph2() constructor (which will be defined in the next problem).

2. (56 points total)

   1. 17 points: add_node()
   2. 10 points: add_edge()
   3. 5 points: get_nodes()
   4. 12 points: get_node_neighbors()
   5. 12 points: get_edges()

   Complete this graph class that uses an adjacency matrix representation.

   Hint: If the graph currently has n nodes, then self.names has length n, and self.adjmatrix has n rows and n columns. So, when adding a node, self.names will get one larger, and self.adjmatrix will get one larger in both dimensions. However, adding an edge doesn't change the size of the representation, though since the add_edge(name_from, name_to) method is defined as adding a node to the graph if it doesn't already exist, the process of adding the new node will increase the size of matrix.

3. (7 points)

   Make a Graph1 object that represents the following directed graph:

   

4. (7 points)

   Make a Graph2 object that represents the directed graph on slide 13 of the Graphs/Networks overview.

5. (7 points)

   In class, you wrote directed_random_neighbors(num_nodes, num_edges) that returned a graph of the Graph class (which we've now renamed Graph1).

   Rewrite that function slightly, so that directed_random_neighbors(empty_graph, num_nodes, num_edges) takes one more argument — an empty graph that is an instance of class Graph1 or Graph2 (or, any other class with the same methods). It returns nothing, but instead mutates the given graph.

   In other words, the body of the function should no longer manipulate the graph data structure directly. Instead, it should call methods such as graph.add_node() and graph.add_edge().

   You would use this function like this:

       my_graph = make_empty_graph()
       directed_random_neighbors(my_graph, 6, 3)
   

   After the call, graph will be the same object, but now modified to be a graph with 6 nodes, each having 3 edges.

6. (22 points total)

   1. (17 points)

      Think of a social graph for a stereotypical high school. Nerds have friends who are other nerds, and jocks have friends who are other jocks. There is no friendship that crosses this social divide. This is an example of a partition. We can separate the nodes/people of the high school social graph into two smaller sets of nodes/people such that there are no edges/friends between the two sets.

      Another way to describe this example partition is to think of the nerds themselves being the partition. I.e., no nerd is friends with a non-nerd.

      Write a function is_partition(graph, nodes) that takes a graph object and a set of nodes. The graph object can be an instance of Graph1 or Graph2 (or, any other class with the same methods). It returns whether the given node set partitions the graph in the latter sense of a partition.

      Here is one way that this problem can be broken into smaller pieces. The node set forms a partition if

      • it is a subset of the graph nodes (i.e., all the given nodes are actually in the graph), and
      • no edge in the node set has an edge to or from a node not in the node set.

   2. (5 points total)

      Show the output of this function on at least three test cases:

      • (1 point) a graph and an empty node set,
      • (2 points) a graph and a non-empty partitioning node set, and
      • (2 points) a graph and a non-empty non-partitioning node set.

      You may use the graphs of problems 3 and 4, any examples from class, or any others.