COMP 200 Elements of Computer Science &
COMP 130 Elements of Algorithms and Computation
Spring 2012

Practice with Graphs

Python Representation of Graphs

Today, we will develop code to work with graphs. Our first task is to choose a data representation. For the time being, we will simplify the matter by not allowing node labels and edge labels. Thus, we only need to represent graphs such as the following.

A directed graph and undirected graph, respectively. A directed graph has one-way edges, while an undirected graph has bidirectional edges.

We can model both directed and undirected graphs with the following representation. A node is represented by its name. We can use numbers or strings for names. A graph is then represented by a dictionary mapping nodes to its successors, a list of nodes.

For example, to represent the directed graph above, we have

For example, whenever there is a directed edge from node A to a node B, then the dictionary maps A to a list that includes B. Furthermore, we can allow unconnected nodes. For example, there are no edges from node 2, so the dictionary maps 2 to an empty list of nodes.

Similarly, to represent the undirected graph above, we have

Our representation of an undirected graph lists each graph twice. If there is an edge from node A to node B, then the dictionary maps A to a list that includes B, and it also maps B to a list that includes A.

So, for the following graphs, give the corresponding Python dictionary representation.

Example directed graph and undirected graph, respectively, for you to encode.

Examples of Building a Graph

Rather than defining graphs “by hand”, we typically define functions that create graphs of a certain type.

Directed ring graphs

Our first example will be to define a function that creates directed ring graphs. A directed ring graph looks like a big circle, with each node pointing to the next.

A directed ring graph of 3 nodes has how many edges? Can you draw or list them?

More generally, a directed ring graph of n nodes has how many edges?

Define a function that takes n, the number of desired graph nodes, and creates a directed ring graph. The graph nodes will be named with the numbers 0…n-1. Thus, node 0 has an edge to node 1. Node 1 has an edge to node 2, etc. Node n-1 has an edge to node 0.

Complete graphs

Our next example will be to define a function that creates complete graphs. A complete graph is simply one that has all possible edges. That is, each node has an edge to each of the other nodes.

A complete graph of 3 nodes has how many edges? Can you draw or list them?

More generally, a complete graph of n nodes has how many edges?

Define a function that takes n, the number of desired graph nodes, and creates a complete graph. The graph nodes will be named with the numbers 0…n-1.

Example of Using a Graph

In later classes, we will discuss many things that you can do with graphs. The following is one simple example to get us familiar with working with the data structure.

The out-degree of a directed graph node is the number of edges from the node. Similarly, the in-degree of a node is the number of edges to that node. For example, in the following graph, the out-degree of node 1 is 1, while its in-degree is 2. Meanwhile, the out- and in-degree of node 2 are both 0.

A directed graph.

When discussing undirected graphs, there is no distinction between out- and in-degree, and we just call it the node degree.

There are various reasons why we might be interested in the (out-/in-)degree of a node, or the average degree of the entire graph. As we've already seen, the average degree of a ring graph is one, while of a complete graph is n-1. The average degree gives us an measure of how well-connected the graph is — for example, the average number of Facebook friends. It helps us determine other properties such as whether the graph is “3-colorable&4dquo;.

Before we start writing any programs, it will be useful to think about some properties of out- and in-degrees.

Describe in English how to calculate the average out-degree of the nodes in a graph.

Describe the relationship between the average out-degree of a graph's nodes and the same graph's average in-degree.

Write a program that returns the average out-degree of a graph.

Related Resources on the Web