Representing Graphs

Practice with Graphs

These exercises are meant to give you more practice with graphs and sets, both conceptually and in code. As such, they should help you prepare for the current assignment.

As a running example, we will use one of the directed graphs from the previous class exercises.

• directed_graph = {0: set([1,4]), 1: set([3]), 2: set([]), 3: set([0,1,4]), 4: set([0,3])}
  

Of course, the previous class provided additional examples, including programs that would generate additional examples. You should also use those when testing today's programs.

Exercises

First, let's consider some graph representation issues.

• Write a function graph_nodes(graph) that returns a set of all the nodes in the given graph. For example, graph_nodes(directed_graph) should return set([0, 1, 2, 3, 4]).

  Note that the same code should work for both directed and undirected graphs.

  Test your graph_nodes function using OwlTest

• Write a function graph_edges(graph) that returns a set of all the edges in the given directed graph. For example, graph_edges(directed_graph) should return set([(0,1), (0,4), (1,3), (3,0), (3,1), (3,4), (4,0), (4,3)]).

  Note that if this function is given an undirected graph, the returned set should include each edge twice, once in each direction.

  Test your graph_edges function using OwlTest

Before the next exercises, let's introduce some definitions. A directed graph node's out-degree is the number of edges pointing out of that node. A directed graph node's in-degree is the number of edges pointing into that node. For example, the out-degree of our example directed graph's node 3 is 3, and its in-degree is 2. For undirected graphs, we instead similarly define the node degree, instead of differentiating between the out- and in-degrees.

• Write a function outdegree(graph, node) that returns the out-degree for the given node in the given directed graph.

  From the previous discussion, outdegree(directed_graph, 3) should return 3.

  Test your outdegree function using OwlTest

• Write a function avg_outdegree(graph) that returns the average out-degree in the graph, i.e., the average of the out-degrees of all the nodes in the graph.

  Use the previous function, along with the function you wrote earlier in the course to compute an average.

  Test your avg_outdegree function using OwlTest

• Write a function indegree(graph, node) that returns the in-degree for the given node in the given directed graph.

  From the previous discussion, indegree(directed_graph, 3) should return 2.

  Test your indegree function using OwlTest

• Write a function avg_indegree(graph) that returns the average in-degree in the graph, i.e., the average of the in-degrees of all the nodes in the graph.

  Use the previous function, along with the function you wrote earlier in the course to compute an average.

  Test your avg_indegree function using OwlTest

• What is the relationship between the average out- and in-degrees of the given sample directed graph? What is the relationship on other sample graphs?

  They are equal to each other.
  

  Can you argue/prove that this relationship always holds?

  The average out-degree is, by definition,
       ( (out-degree node 0) + ... + (out-degree node n-1) ) / #nodes
  Let's think about that sum in the numerator.  It simply totals to the
  number of edges in the graph.  After all, every directed edge has to
  go out of some node, so each edge is counted somewhere in that sum.
  Thus, the formula simplifies to
       #edges / #nodes
  
  The average in-degree is, by definition,
       ( (in-degree node 0) + ... + (in-degree node n-1) ) / #nodes
  By similar reasoning, in that each directed edge has to go into some
  node, this also simplifies to
       #edges / #nodes
  
  Thus, they are the same.
  

• Hopefully, the thinking encouraged by the previous problem has led you to an insight about the average out- and in-degrees. (This insight is provided in the hidden solution above.) Can you now define versions of avg_outdegree(graph) and avg_indegree(graph) that are simpler than your previous ones?

• Does the same relationship hold between the median out- and in-degrees? What about the standard deviation of the out- and in-degrees?

  In short, not in general.
  

Next, we want to test if two sets are equal, i.e., have the same elements. Of course, this is really easy with == or !=. But, let's pretend that our local CodeSkulptor implementor has accidentally broken the built-in set-equality operations. Alas, you have witnessed that such mistakes happen. Of course, that's just an excuse for you to think about how you can use the remaining set operations.

• Define the function equal_sets1(set1, set2) that returns the appropriate Boolean. The only set operations you can use are issubset() and issuperset(). You are not allowed to convert the sets into any other data structure.

  Test your equal_sets1 function using OwlTest

• Define the function equal_sets2(set1, set2) that returns the appropriate Boolean. The only set operations you can use are add(), remove(), discard(), pop(), copy(), in, and not in. You are not allowed to convert the sets into any other data structure. Hint: You might want to define some helper function and also use the idea of the previous version.

  Test your equal_sets2 function using OwlTest