Representing Graphs

Python Representation of Graphs

We have seen that graphs/networks have many uses. So, we want to write programs that use graphs. However, Python, like most programming languages, does not have a notion of graphs built-in. Instead, we need to choose some combination of our other data structures to represent graphs. 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 set of nodes.

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

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

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

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

Our representation of an undirected graph mentions each edge twice. If there is an edge from node A to node B, then the dictionary maps A to a set that includes B, and it also maps B to a set 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.

Later, we will need to augment this representation to also include labels.

There are many other possible ways to represent graphs. We'll mention two here. First, note that our current representation is node-oriented in that we list all the nodes, and then for each of those, we mention all of its neighboring nodes. In fact, the edges themselves are only implicit.

Another possible representation is a set of edges, where each edge is a pair of nodes. We need to combine that with a set of nodes, since there can be nodes that aren't mentioned among the edges. For example, we could define the following.

undirected_graph = (set([0, 1, 2, 3, 4]), set([(0, 1), (0, 4), (1, 0), (1, 3), (3, 1), (3, 4), (4, 0), (4, 3)]))

Another common representation is a 2D matrix of Booleans. If there is an edge from i to j, then matrix[i][j] is true. This simply assumes that the node names are consecutive integers. Python doesn't have matrices, but we can define a matrix as a list of lists. So, for example, we can define the following.

undirected_graph = [[False, True, False, False, True], [True, False, False, True, False], [False, False, False, False, False], [False, True, False, False, True], [True, False, False, True, False]]

As you can see, all of the representations become hard to read even for small graphs.

Which representation is best depends on the algorithms that you plan to use on the data. Many algorithms are easier with some representations and harder on others.

Examples of Building a Graph

Defining graphs “by hand” like this is tedious, especially as the graphs get larger. So, 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 in the circle.

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

Let's name the nodes 0, 1, 2.
3 edges, one outgoing edge per node: 0 to 1, 1 to 2, 2 to 0.

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

n edges, one outgoing edge per node.

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.

Hint: You might want to use the “modulo” operator, %, which returns the remainder of x/y.

def makeDirectedRing(n):
    """Returns a directed ring graph of nodes 0..n-1."""
    ring = {}
    for node in range(n):
        ring[node] = set([(node+1) % n])   # Make a set of the one successor node.
    return ring

But, here's a version without using modulo.

def makeDirectedRing(n):
    """Returns a directed ring graph of nodes 0..n-1."""
    ring = {n: [0]}
    for node in range(n-1):
        ring[node] = set([(node+1)])   # Make a set of the one successor node.
    return ring

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. We can have both complete directed graphs and complete undirected graphs.

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

Let's name the nodes 0, 1, 2.

For a complete directed graph, there are six edges, two per node:
0 to 1, 0 to 2, 1 to 0, 1 to 2, 2 to 0, and 2 to 1.

For a complete undirected graph, there are three edges, i.e.,
half as many: 0-1, 0-2, and 1-2.

Note that our Python data representation doesn't distinguish between
these two.

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

Directed: n(n-1).  Undirected: n(n-1)/2.

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

Version 1:

def make_complete(n):
    """Returns a complete graph of nodes 0..n-1."""
    complete = {}
    for node in range(n):
        neighbors = range(n)             # Create an edge to every node...
        del neighbors[node]              # ...except itself.
        complete[node] = set(neighbors)  # Add the node's neighbors to the graph.
    return complete

Version 2: This avoids the slightly dangerous del. It also uses a more general process that doesn't rely on the nodes being a range of integers:

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 = {}
    for node in nodes:
        neighbors = set(nodes) # Create an edge to every node
        neighbors.remove(node) # ...except itself
        complete[node] = neighbors  # Add the nodes neighbors to the graph
    return complete

Random graph

Often, we want some sort of randomly-generated graph. Typically, we want such graphs to be random, but still maintain some particular properties. The following is one such example.

Write a function directed_random_neighbors(num_nodes, num_edges). It returns a directed graph with the given number of nodes. Each node has the given number of distinct edges chosen randomly. E.g., for node 2, we cannot choose edges (2, 5), (2, 1), and (2, 5), because two of those are not distinct.

Need a hint on how to guarantee distinctness?

Here are two possible approaches for picking the distinct edges
for a given node.  

You could re-guess neighbors in a loop until you pick something distinct.

Better, you could generate a list of all the possible neighbors, and
then choose and remove random values from this list.  The removal
guarantees that each choice is distinct.

Adding Labels to the Graph Representation

Many applications of graphs, including the ones we will focus on, use node or edge labels. We could augment our dictionary-plus-set-based representation to incorporate labels. However, the representation would get more complicated to the point of being somewhat unwieldy. Instead, we will soon use this as motivation to introduce classes and objects in Python, and then use an object-based representation of graphs.

COMP 200: Elements of Computer Science Spring 2013