Graphs

Vertices and edges; directed, undirected and weighted graphs; degree, the handshake lemma and typical uses.

A4.1Trees and graphsA level20 min

At GCSE every data structure you met was a line or a table: a list, a two-dimensional array, a record. A lot of data does not have that shape. Roads join towns, web pages link to other pages, and the zones of BugBot's mat are joined wherever the robot can drive from one to the next. A graph is the data structure for relationships like these. This module builds everything on it: trees, traversals, and in the project a robot that plans its own route.

Vertices and edges

A graph is a set of vertices (also called nodes) joined by edges (also called arcs). In this graph, six zones of a warehouse floor are the vertices, and an edge joins two zones when there is a clear track between them. The number on each edge is the time in seconds the robot takes to drive it.

Undirected, directed and weighted

In an undirected graph an edge works both ways: if the robot can drive from A to B, it can drive from B to A. Friendships on a social network are undirected in the same way.

In a directed graph (a digraph) each edge has a direction, drawn as an arrow. Web links are directed: a page can link to another page that never links back. A one-way ramp on the mat would be a directed edge.

In a weighted graph every edge carries a number, its weight: a distance, a time or a cost. The warehouse graph is weighted; the directed graph above is not. The two properties are independent, so a graph can be directed and weighted, undirected and unweighted, or either mixture.

A graph in Python: a list of edges

The simplest way to store a graph is as a list of its edges. Each weighted edge is a tuple of its two ends and its weight. That is already enough to answer questions, such as whether a route is possible and how long it takes:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

EDGES = [("A", "B", 5), ("A", "D", 3), ("B", "C", 4), ("B", "D", 6),
         ("B", "E", 2), ("C", "F", 7), ("D", "E", 8), ("E", "F", 1)]

def weight(u, v):
    """The weight of the edge between u and v, or None if they are not joined."""
    for a, b, w in EDGES:
        if (a, b) == (u, v) or (a, b) == (v, u):     # undirected: either way round
            return w
    return None

def route_cost(route):
    total = 0
    for i in range(len(route) - 1):
        w = weight(route[i], route[i + 1])
        if w is None:
            return None                              # two stops are not joined: not a path
        total = total + w
    return total

print(route_cost(["A", "B", "E", "F"]))
print(route_cost(["A", "D", "E", "F"]))
print(route_cost(["A", "C", "F"]))

Run this in the simulator

Both routes from A to F use three edges, but the first costs 8 seconds and the second 12. In a weighted graph the shortest path is the one with the smallest total weight, not the fewest edges; module A5 finds it with Dijkstra's algorithm. The third route is not a path at all, because A and C are not joined.

Notice what weight has to do: search the whole list of edges for every single question. For a graph with thousands of edges that is slow, and the next lesson stores graphs in two better ways.

Degree and the handshake lemma

Add up the degrees in the warehouse graph: 2 + 4 + 2 + 3 + 3 + 2 = 16. There are 8 edges. That is no accident. Every edge has two ends, so it adds 1 to the degree of each end, and the degrees always add up to twice the number of edges. This is called the handshake lemma: at a party, count every handshake from both people's side and you count each one twice.

It has a neat consequence: the number of vertices with an odd degree is always even (here D and E). It also gives a quick check that a graph has been copied down correctly.

A directed graph splits degree in two. The in-degree of a vertex counts the arrows that end there, and the out-degree counts the arrows that leave it. In the directed graph above, B has in-degree 1 and out-degree 2.

Where graphs are used

Graphs appear wherever the connections matter more than anything else:

• Maps and sat-nav: junctions are vertices and roads are weighted edges (distance or time); one-way streets are directed edges.
• Computer networks: routers are vertices and links are edges weighted by delay or cost. Routing protocols find cheap paths through this graph.
• Social networks: people are vertices. Friendship is an undirected edge; following someone is a directed one.
• The web: pages are vertices and hyperlinks are directed edges. Search engines rank pages using the shape of this graph.
• Scheduling: jobs are vertices, and a directed edge from one job to another means "must finish before".
• Robot navigation: the places a robot can be are vertices and the moves between them are edges. BugBot plans routes this way in the project at the end of this module.

A graph is an abstraction. It keeps who is joined to whom, and the weights, and throws everything else away. The London Underground map is a graph, which is why its stations are not drawn where they are on a street map. You can move the vertices of a drawing anywhere you like: as long as the same pairs are joined, it is the same graph.

Task: degrees and the handshake

Five zones, A to E, are joined by the weighted, undirected edges in EDGES. Each edge is a tuple (end, other end, weight), and the weights are whole numbers of seconds. Work out the degree of every vertex from EDGES. Print one line per vertex, in alphabetical order, in the form A: degree 2. Then print three more lines: edges: and the number of edges, sum of degrees: and the total of all the degrees, and total weight: and the sum of every edge's weight. Do not type any of the numbers: work them out, so the program would still be right if EDGES changed.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

EDGES = [("A", "B", 4), ("A", "C", 7), ("B", "C", 2), ("B", "D", 5), ("C", "D", 3), ("C", "E", 6), ("D", "E", 1)]

degree = {}

Challenges

1. Count the vertices with an odd degree, and check the handshake lemma's promise that there is an even number of them.
2. Treat EDGES as directed, from the first end to the second. Print each vertex's in-degree and out-degree. What must all the in-degrees add up to?
3. Write neighbours(v) that returns the neighbours of v in alphabetical order using only EDGES. How many edges does it look at on every call?