Practical 19: Graph Representations and Traversals

The adjacency matrix

A square grid with one row and one column per vertex, holding 1 where there is an edge.

For an undirected graph the matrix is symmetric: m[i][j] and m[j][i] are both set, which is the two lines in add_edge. A program that sets only one has built a directed graph by accident, and the symptom is that a route works in one direction and not the other.

Its strength is one question, answered instantly. "Is there an edge from A to B" is one array lookup, O(1), whatever the size of the graph.

Its weakness is everything else. It always occupies n squared cells whether they are used or not, listing a vertex's neighbours means scanning a whole row of n cells, and adding a vertex means building a bigger grid and copying.

The adjacency list

For each vertex, the list of vertices it joins. Here it is a dictionary from a name to a list of names, which is the usual Python form.

Its strength is that it stores only what exists. Nine edges give eighteen entries, two per edge, and listing a vertex's neighbours is reading its list. Adding a vertex is adding one empty list.

Its weakness is the one question the matrix answers instantly. "Is there an edge from A to B" is a scan of A's neighbours, so it costs the degree of A.

The comparison, which is the answer to MU's first bullet

V is the number of vertices, E the number of edges.

Nearly every real graph is sparse. Ten stations here have nine lines between them, not forty-five. The matrix needed 100 cells to hold 18 ones, which is 5.6 times the list's size, and that ratio grows with the graph: a million web pages with ten links each is 10 million list entries and a million million matrix cells.

The rule: matrix for a dense graph or when you ask about single edges constantly; list for everything else. A social network, a road map, a web crawl and a dependency graph are all lists.

Breadth first and depth first

The two traversals are the same program with a different container, and that is the single most useful thing to know about them.

from collections import deque


class GraphMatrix:
    """An adjacency MATRIX: a square grid of 0 and 1."""

    def __init__(self, labels):
        self.labels = list(labels)
        self.index = {name: i for i, name in enumerate(self.labels)}
        n = len(self.labels)
        self.m = [[0] * n for _ in range(n)]

    def add_edge(self, a, b):
        i, j = self.index[a], self.index[b]
        self.m[i][j] = self.m[j][i] = 1          # undirected: both cells

    def remove_edge(self, a, b):
        i, j = self.index[a], self.index[b]
        self.m[i][j] = self.m[j][i] = 0

    def has_edge(self, a, b):
        """ONE lookup, whatever the size of the graph."""
        return self.m[self.index[a]][self.index[b]] == 1

    def neighbours(self, a):
        i = self.index[a]
        return [self.labels[j] for j in range(len(self.labels)) if self.m[i][j]]

    def degree(self, a):
        return sum(self.m[self.index[a]])

    def cells(self):
        return len(self.labels) ** 2

    def show(self):
        head = "      " + " ".join(f"{x:>3}" for x in self.labels)
        print(head)
        for name, row in zip(self.labels, self.m):
            print(f"  {name:>3} " + " ".join(f"{v:>3}" for v in row))


class GraphList:
    """An adjacency LIST: for each vertex, the vertices it joins."""

    def __init__(self, labels=()):
        self.adj = {name: [] for name in labels}

    def add_vertex(self, a):
        self.adj.setdefault(a, [])

    def add_edge(self, a, b):
        self.add_vertex(a)
        self.add_vertex(b)
        if b not in self.adj[a]:
            self.adj[a].append(b)
            self.adj[b].append(a)

    def remove_edge(self, a, b):
        if b in self.adj.get(a, []):
            self.adj[a].remove(b)
            self.adj[b].remove(a)

    def remove_vertex(self, a):
        """A matrix cannot do this without rebuilding itself."""
        for other in self.adj.pop(a, []):
            self.adj[other].remove(a)

    def has_edge(self, a, b):
        """A SCAN of a's neighbours, so it costs the degree of a."""
        return b in self.adj.get(a, [])

    def neighbours(self, a):
        return list(self.adj.get(a, []))

    def degree(self, a):
        return len(self.adj.get(a, []))

    def entries(self):
        return sum(len(v) for v in self.adj.values())

    def show(self):
        for name in self.adj:
            print(f"  {name:>3} -> {', '.join(self.adj[name]) or '(none)'}")


# three-letter codes, so that the matrix fits on a page:
# CST Chhatrapati Shivaji Terminus, BYC Byculla, DDR Dadar, KUR Kurla,
# THN Thane, BAN Bandra, AND Andheri, BOR Borivali, PNV Panvel, VSH Vashi
STATIONS = ["CST", "BYC", "DDR", "KUR", "THN", "BAN",
            "AND", "BOR", "PNV", "VSH"]
EDGES = [("CST", "BYC"), ("BYC", "DDR"), ("DDR", "KUR"),
         ("KUR", "THN"), ("DDR", "BAN"), ("BAN", "AND"),
         ("AND", "BOR"), ("KUR", "AND"),
         ("PNV", "VSH")]

def bfs(g, start, trace=False):
    """Breadth first: a QUEUE. Visits everything at distance 1, then 2, ..."""
    seen = {start}
    order = []
    q = deque([start])
    if trace:
        print(f"    {'take':<6}{'new neighbours':<22}queue after")
    while q:
        here = q.popleft()
        order.append(here)
        added = []
        for n in g.neighbours(here):
            if n not in seen:
                seen.add(n)
                q.append(n)
                added.append(n)
        if trace:
            print(f"    {here:<6}{', '.join(added) or '-':<22}{list(q)}")
    return order


def dfs_iterative(g, start, trace=False):
    """Depth first: the same code with a STACK instead of a queue."""
    seen = {start}
    order = []
    stack = [start]
    if trace:
        print(f"    {'take':<6}{'new neighbours':<22}stack after")
    while stack:
        here = stack.pop()
        order.append(here)
        added = []
        for n in g.neighbours(here):
            if n not in seen:
                seen.add(n)
                stack.append(n)
                added.append(n)
        if trace:
            print(f"    {here:<6}{', '.join(added) or '-':<22}{stack}")
    return order


def dfs_recursive(g, start, seen=None, order=None):
    if seen is None:
        seen, order = {start}, []
    order.append(start)
    for n in g.neighbours(start):
        if n not in seen:
            seen.add(n)
            dfs_recursive(g, n, seen, order)
    return order


def components(g, labels):
    """Every part of the graph that is joined up."""
    seen, out = set(), []
    for v in labels:
        if v not in seen:
            part = bfs(g, v)
            seen.update(part)
            out.append(part)
    return out


def shortest_path(g, start, goal):
    """BFS again, remembering where each vertex was reached FROM.
    On an unweighted graph this gives the fewest hops."""
    if start == goal:
        return [start]
    came_from = {start: None}
    q = deque([start])
    while q:
        here = q.popleft()
        for n in g.neighbours(here):
            if n in came_from:
                continue
            came_from[n] = here
            if n == goal:
                path = [goal]
                while came_from[path[-1]] is not None:
                    path.append(came_from[path[-1]])
                return list(reversed(path))
            q.append(n)
    return None


g = GraphList(STATIONS)
for a, b in EDGES:
    g.add_edge(a, b)

print("breadth first from CST, step by step")
order = bfs(g, "CST", trace=True)
print("  visited:", order)

print()
print("depth first from CST, the SAME code with a stack")
order2 = dfs_iterative(g, "CST", trace=True)
print("  visited:", order2)

print()
print("depth first again, recursively:", dfs_recursive(g, "CST"))
print("  the recursive and iterative walks differ, and both are correct DFS:")
print("  the stack reverses the order the neighbours are pushed in.")

print()
print("the graph is not all joined up")
for part in components(g, STATIONS):
    print("  a component:", part)
print("  two components, so no route exists between them at all")

print()
print("fewest hops, which is what BFS gives on an unweighted graph")
for a, b in (("CST", "BOR"), ("CST", "THN"), ("BYC", "AND"), ("CST", "PNV")):
    p = shortest_path(g, a, b)
    if p is None:
        print(f"  {a} to {b}: no route")
    else:
        print(f"  {a} to {b}: {' -> '.join(p)}  ({len(p) - 1} hops)")

print()
print("and why DFS is the wrong tool for that question")
path = dfs_recursive(g, "CST")
print("  a depth-first walk from CST visits", path)
print("  BOR is reached, but not by the shortest route: DFS follows one branch")
print("  to its end before trying another, so the path it finds may be long.")

The difference is the queue against the stack

Put the two loops side by side:

here = q.popleft()      # breadth first: a QUEUE, first in first out
here = stack.pop()      # depth first:   a STACK, last in first out

Everything else is identical. And the behaviour that follows is exactly what the two disciplines mean:

• Breadth first takes the oldest waiting vertex, so it finishes everything one hop away before

it looks at anything two hops away. It spreads out in rings.

• Depth first takes the newest, so it follows one branch as far as it goes before coming back.

It plunges.

Read the two traces. BFS from CST visits CST, BYC, DDR, then KUR and BAN together, which are both three hops out. DFS visits CST, BYC, DDR, then dives BAN, AND, BOR to the end of that branch, and only then comes back for KUR and THN.

Three things the run shows

The recursive and iterative depth-first walks differ. Recursive gives CST, BYC, DDR, KUR, THN, AND, BAN, BOR; the stack version gives CST, BYC, DDR, BAN, AND, BOR, KUR, THN. Both are correct depth-first traversals, and the reason they differ is that a stack reverses the order the neighbours were pushed in, so the stack version takes the last neighbour first. An examiner asking for "the" DFS order should say which; if not, say which convention you used.

seen is checked when a vertex is pushed, not when it is taken. That is why no vertex appears twice in the queue or the stack. Marking on removal instead lets a vertex be queued several times before it is first taken, which still gives the right answer and wastes memory; on a graph with cycles, forgetting to mark at all never terminates.

The graph has two components. CST's component has eight stations and Panvel and Vashi are a separate pair, so there is no route between them at all. Finding the components is BFS from every vertex not yet seen, which is what components does, and it is the standard way to answer "is this graph connected".

The shortest path, and why it has to be BFS

shortest_path is BFS with one addition: a dictionary remembering which vertex each one was reached from. When the goal is reached, following those back gives the path.

It gives the fewest hops, and the reason is the ring behaviour: BFS reaches every vertex at distance 1 before any at distance 2, so the first time it reaches the goal it has come by a shortest route. Depth-first search has no such property, and the last lines of the run make the point: a depth-first walk from CST does reach BOR, but by whatever branch it happened to dive down.

This is only true on an unweighted graph. Add distances to the edges and the fewest hops is no longer the shortest journey, and the answer becomes Dijkstra's algorithm, which is BFS with a priority queue instead of a plain queue, taking the nearest unvisited vertex rather than the oldest. That is the priority queue of [Practical 18 continued: Heaps and Priority Queues], and the connection is worth stating: Dijkstra is BFS with the heap swapped in for the queue, exactly as DFS is BFS with a stack swapped in.

MU's application: a social network

MU names route mapping and social networks; the routes are above and this is the other.

from collections import deque


class GraphMatrix:
    """An adjacency MATRIX: a square grid of 0 and 1."""

    def __init__(self, labels):
        self.labels = list(labels)
        self.index = {name: i for i, name in enumerate(self.labels)}
        n = len(self.labels)
        self.m = [[0] * n for _ in range(n)]

    def add_edge(self, a, b):
        i, j = self.index[a], self.index[b]
        self.m[i][j] = self.m[j][i] = 1          # undirected: both cells

    def remove_edge(self, a, b):
        i, j = self.index[a], self.index[b]
        self.m[i][j] = self.m[j][i] = 0

    def has_edge(self, a, b):
        """ONE lookup, whatever the size of the graph."""
        return self.m[self.index[a]][self.index[b]] == 1

    def neighbours(self, a):
        i = self.index[a]
        return [self.labels[j] for j in range(len(self.labels)) if self.m[i][j]]

    def degree(self, a):
        return sum(self.m[self.index[a]])

    def cells(self):
        return len(self.labels) ** 2

    def show(self):
        head = "      " + " ".join(f"{x:>3}" for x in self.labels)
        print(head)
        for name, row in zip(self.labels, self.m):
            print(f"  {name:>3} " + " ".join(f"{v:>3}" for v in row))


class GraphList:
    """An adjacency LIST: for each vertex, the vertices it joins."""

    def __init__(self, labels=()):
        self.adj = {name: [] for name in labels}

    def add_vertex(self, a):
        self.adj.setdefault(a, [])

    def add_edge(self, a, b):
        self.add_vertex(a)
        self.add_vertex(b)
        if b not in self.adj[a]:
            self.adj[a].append(b)
            self.adj[b].append(a)

    def remove_edge(self, a, b):
        if b in self.adj.get(a, []):
            self.adj[a].remove(b)
            self.adj[b].remove(a)

    def remove_vertex(self, a):
        """A matrix cannot do this without rebuilding itself."""
        for other in self.adj.pop(a, []):
            self.adj[other].remove(a)

    def has_edge(self, a, b):
        """A SCAN of a's neighbours, so it costs the degree of a."""
        return b in self.adj.get(a, [])

    def neighbours(self, a):
        return list(self.adj.get(a, []))

    def degree(self, a):
        return len(self.adj.get(a, []))

    def entries(self):
        return sum(len(v) for v in self.adj.values())

    def show(self):
        for name in self.adj:
            print(f"  {name:>3} -> {', '.join(self.adj[name]) or '(none)'}")


# three-letter codes, so that the matrix fits on a page:
# CST Chhatrapati Shivaji Terminus, BYC Byculla, DDR Dadar, KUR Kurla,
# THN Thane, BAN Bandra, AND Andheri, BOR Borivali, PNV Panvel, VSH Vashi
STATIONS = ["CST", "BYC", "DDR", "KUR", "THN", "BAN",
            "AND", "BOR", "PNV", "VSH"]
FRIENDSHIPS = [("Aarti", "Bhavesh"), ("Aarti", "Chetna"),
               ("Bhavesh", "Devang"), ("Chetna", "Devang"),
               ("Chetna", "Esha"), ("Devang", "Farhan"),
               ("Esha", "Farhan"), ("Farhan", "Gauri"),
               ("Hemant", "Ishita")]
PEOPLE = ["Aarti", "Bhavesh", "Chetna", "Devang", "Esha",
          "Farhan", "Gauri", "Hemant", "Ishita"]


def distances(g, start):
    """Every vertex, and how many hops away it is. BFS, counting levels."""
    far = {start: 0}
    q = deque([start])
    while q:
        here = q.popleft()
        for n in g.neighbours(here):
            if n not in far:
                far[n] = far[here] + 1
                q.append(n)
    return far


net = GraphList(PEOPLE)
for a, b in FRIENDSHIPS:
    net.add_edge(a, b)

print("a small social network")
net.show()

print()
me = "Aarti"
far = distances(net, me)
print(f"how far everybody is from {me}")
by_level = {}
for who, d in far.items():
    by_level.setdefault(d, []).append(who)
for d in sorted(by_level):
    label = {0: "herself", 1: "friends", 2: "friends of friends"}.get(
        d, f"{d} hops away")
    print(f"  {d} hop(s), {label:<20}{', '.join(sorted(by_level[d]))}")
unreachable = [p for p in PEOPLE if p not in far]
print(f"  not connected at all         {', '.join(unreachable)}")

print()
print(f"people to suggest to {me}: at distance 2, so friends of friends")
print("  and not already friends")
suggestions = sorted(w for w, d in far.items() if d == 2)
print("  suggestions:", suggestions)
for who in suggestions:
    shared = sorted(set(net.neighbours(who)) & set(net.neighbours(me)))
    print(f"    {who:<9} through {', '.join(shared)}")

print()
print("mutual friends of any two people")
for a, b in (("Aarti", "Devang"), ("Bhavesh", "Chetna"), ("Aarti", "Gauri")):
    shared = sorted(set(net.neighbours(a)) & set(net.neighbours(b)))
    print(f"  {a} and {b}: {', '.join(shared) or 'none'}")

print()
print("the degree of each person, which is how many friends they have")
for who in sorted(PEOPLE, key=lambda p: (-net.degree(p), p)):
    print(f"  {who:<9}{net.degree(who)}")
print("  the sum of all the degrees is", sum(net.degree(p) for p in PEOPLE),
      "which is twice the", len(FRIENDSHIPS), "friendships.")
print("  That is the handshaking lemma, and it is a useful check on any")
print("  adjacency list: the entries must come to twice the edges.")

Distance is the whole idea

A breadth-first search from one person, counting levels, gives everything a social network shows you:

People to suggest are exactly those at distance 2. Distance 1 is already a friend, and distance 3 is too far to be interesting; distance 2 means you have a friend in common and are not yet connected, which is precisely what "people you may know" means. And the program says through whom, by intersecting the two neighbour sets, which is what a real network shows beside the suggestion.

Mutual friends are a set intersection, one line, because an adjacency list gives a vertex's neighbours directly. That operation is why a social network is stored as an adjacency list and not as a matrix: a matrix would need a scan of two whole rows.

Hemant and Ishita are unreachable. They are a separate component, so no number of hops connects them to Aarti. A network with several components is the normal state of affairs, and a program that assumes the graph is connected reports a distance of infinity as a bug.

And the handshaking lemma checks the data. Nine friendships, degrees summing to 18. If a friendship had been added in one direction only the sum would be odd, which is impossible in an undirected graph, and the check would catch it.

Where graphs are used

The last row is worth a moment: a garbage collector is a graph traversal over the objects in memory, starting from the variables in scope, and anything not reached is freed. Every program a student writes is already using one.

The cost of the traversals

V vertices, E edges, on an adjacency list.

O(V + E) is the figure to remember, and it is the reason the adjacency list wins: the same traversal on a matrix is O(V squared), which for a sparse graph is enormously worse.

Procedure

1. Write both representations and run the program. Check three cells of the matrix against three

lines of the adjacency list by hand.

1. Set only m[i][j] in add_edge and confirm that the matrix is no longer symmetric and that a

route works one way only.

1. Add a station to the list in O(1). Then work out what adding one to the matrix would take.
2. Write the traversals. Follow both traces on paper and confirm the ring against the dive.
3. Swap q.popleft() for q.pop() in the BFS and confirm you have written a DFS.
4. Remove the if n not in seen test and run it on the graph, which has cycles. The program never

ends; stop it with Ctrl+C.

1. Write the social network. Add a friendship between Aarti and Hemant and confirm the two

components become one and that everybody now has a distance.

Result

A graph of ten vertices and nine edges was represented as an adjacency matrix and as an adjacency list, and the two were shown to give the same neighbours for every vertex. The matrix occupied 100 cells to hold 18 ones, 5.6 times the list's 18 entries, on a graph that is sparse. Breadth-first and depth-first search were implemented as the same loop with a queue and with a stack, and their traces printed: breadth first visited the vertices in rings and depth first followed one branch to its end. The graph was found to have two components, so that some pairs have no route. Shortest paths by fewest hops were produced by breadth-first search with a record of where each vertex was reached from. The same structure was used as a social network, where the people to suggest were exactly those at distance 2, mutual friends were a set intersection, and the degrees were checked to sum to twice the number of friendships.

Where marks are lost

• Setting only one cell of the matrix for an undirected edge. The matrix must be symmetric.
• Saying the matrix is better because a lookup is O(1) without saying it costs O(V squared) in

space. Both halves are the answer.

• BFS with a stack, or DFS with a queue. The container is the definition.
• Not marking a vertex as seen, which never terminates on a graph with a cycle.
• Marking on removal instead of on insertion, which queues vertices several times.
• Claiming DFS finds the shortest path. Only BFS does, and only on an unweighted graph.
• Assuming the graph is connected. Find the components, or say that you assumed it.
• Using BFS on a weighted graph and calling the answer the shortest path. That needs Dijkstra.
• Not printing the queue or the stack. It is the working, and it is what distinguishes the two

algorithms on paper.

• Forgetting that a vertex's own list must not contain itself unless the graph really has a

self-loop.

For the journal

Write the aim, MU's own wording, and the graph drawn as a picture with its ten vertices and nine edges. Then the matrix and the adjacency list of that same graph, side by side, with the cell count against the entry count. Then both traversals with their step tables showing the queue and the stack, because those two tables are what an examiner marks, and one sentence saying that the only difference in the program is which end the next vertex comes from. Then the components, the shortest paths, and the social network with the levels from one person and the suggestions at distance 2. Close with the handshaking check: degrees 18, edges 9. The conclusion: a graph is vertices and edges, an adjacency list costs O(V + E) where a matrix costs O(V squared), and breadth first and depth first are one algorithm with a queue or a stack in it.

Quick revision

• A graph is vertices and edges. Degree is how many edges touch a vertex. A component is a piece

that is joined up.

• Handshaking lemma: the degrees sum to twice the number of edges. Use it to check your data.
• Adjacency matrix: O(V squared) space always, O(1) edge test, O(V) to list neighbours, symmetric

for an undirected graph.

• Adjacency list: O(V + E) space, O(degree) edge test, O(degree) to list neighbours, O(1) to add a

vertex. Right for nearly every real graph, because nearly every real graph is sparse.

• BFS uses a queue and visits in rings. DFS uses a stack, or recursion, and follows one

branch to its end. They are the same program otherwise.

• Mark a vertex as seen when it is pushed, not when it is taken. Without marking at all, a

graph with a cycle never terminates.

• BFS finds the path with the fewest hops, because it reaches everything at distance k before

anything at k + 1. DFS does not.

• On a weighted graph the shortest path needs Dijkstra, which is BFS with a priority queue

instead of a queue.

• Both traversals are O(V + E) on a list and O(V squared) on a matrix.
• Components: BFS or DFS from every vertex not yet seen. One traversal in total, O(V + E).
• A social network's suggestions are the vertices at distance 2; mutual friends are a set

intersection of two neighbour lists.

• A tree is a connected graph with no cycle. Level-order is BFS and pre-order is DFS.

Questions you should be able to answer

1. Give the space cost of each representation and say which suits a sparse graph. A matrix is O(V squared) whatever the number of edges; a list is O(V + E). A sparse graph, which is nearly every real one, suits the list. Here ten vertices and nine edges needed 100 matrix cells against 18 list entries.

2. What must be true of an adjacency matrix for an undirected graph? It must be symmetric: m[i][j] and m[j][i] are both set for every edge.

3. What is the only difference between BFS and DFS in a program? Whether the next vertex is taken from the front of a queue or the top of a stack. Everything else is identical.

4. Which finds the shortest path, and under what condition? Breadth-first search, and only on an unweighted graph. It reaches everything at distance k before anything at distance k + 1, so the first time it reaches the goal it has come the shortest way.

5. Why must a vertex be marked as seen when it is pushed rather than when it is taken? Because otherwise it can be pushed several times before it is first taken, which wastes memory. Without marking at all, a graph with a cycle is traversed for ever.

6. What is a component, and how are the components found? A maximal part of the graph that is joined up. Run a traversal from every vertex that has not yet been seen; each run is one component. In total it costs O(V + E).

7. What is the cost of a full traversal on each representation? O(V + E) on an adjacency list and O(V squared) on a matrix, because the matrix makes you scan a whole row per vertex.

8. In a social network, which people should be suggested to somebody, and why? Those at distance 2: they have a friend in common and are not already friends. Distance 1 is already a friend and distance 3 has nothing in common.

9. State the handshaking lemma and say what it is good for. The sum of all the degrees is twice the number of edges, because every edge adds 1 to each of its ends. It is a free check on an adjacency list: an odd sum means an edge was added in one direction only.

10. What is the relation between BFS, DFS and Dijkstra's algorithm? All three are the same traversal with a different container: a queue gives breadth first, a stack gives depth first, and a priority queue keyed on distance gives Dijkstra, which is the shortest path on a weighted graph.