Contents of Part I

## Introduction

In this part, I’ll show a few simple examples of graph implementation using python 3.6, and validate them with the static type checker, mypy.

*Type hints* (or *type annotations*) is a feature added to python 3 that allows programmers to include type information in their code. Type annotations should be validated by a third-party static type checker. Static types serve to provide early (“compile-time”) warnings about possible bugs; in addition, type hints often make the code easier to understand. Type hints are completely optional and have almost no impact on the run-time behavior of the program.^{1}

For basic tutorials, I suggest you look at this introduction, or at the full mypy documentation. I will briefly explain the more advanced concepts I might use.

## Dictionary Representation

Let’s start with directed graphs. We will assign each node a unique id, using integers in `range(n_nodes-1)`

.

First, let’s get out of the way the comparison of adjacency matrix vs adjacency lists. An *adjacency matrix* representation uses a 2D boolean matrix (likely represented in python as a list of lists), where cell `(i, j)`

indicates if there is an edge from `i`

to `j`

. An *adjacency lists* representation stores a collection of neighbors for each node.

Adjacency matrix uses `O(n_nodes^2)`

space and takes `O(n_nodes)`

time to iterate through the neighbors of a single node (a very common operation in graph algorithms). The corresponding costs for adjacency lists are `O(n_edges)`

and `O(n_degree)`

. Therefore, the adjacency lists approach always wins, and its advantage is especially large for sparse graphs. In fact, adjacency matrix representation should only be used in a few very specific circumstances:

- if you need to do matrix algebra on such a matrix
^{2} - if the 2D array is already supplied from outside, and it’s not worth converting it to an adjacency lists

The obvious implementation choices for adjacency lists is a list or a set. A set is usually better because it offers O(1) lookup, insertion, and removal.^{3} The adjacency sets themselves can be stored in a list or in a dictionary; a dictionary is better because it allows O(1) node removal. ^{4}

So we have our first implementation of a directed graph as a dictionary of sets:

For demonstration, I’ve added functions that convert between our graph representation and a very simple serialization format.

Of course, any additional information would have to be stored separately, for example in dictionaries indexed by `node_id`

or by tuples `(tail_id, head_id)`

.

While this is a very simple and limited implementation, it’s quite usable in simple cases.

## Digression: Graph Equality

You can skip this section if you’re not interested in graph comparisons.

Note how in the `test_serialization`

, we cannot `assert write_graph(read_graph(g)) == g`

: it will fail because the order of lines and of neighbors within each line may change after the two conversions, and also because of possible differences in whitespace. On the other hand, `assert read_graph(write_graph(g)) == g`

works.

The behavior of the equality operator with our graphs is somewhat misleading: it does not check if the two objects represent equivalent (“isomorphic” using the mathematical term) graphs. For example, `{0: {1}, 1: {}} != {0: {}, 1: {0}}`

, and yet the lhs and the rhs represent the equivalent graphs (two nodes connected by a single edge).

Our graph object is a nested structure of dictionaries and sets, with integer node ids at the bottom tier. As a result, two graph objects compare equal (using `==`

) if for each node id in one graph, the other graph has a node with the same id, and these two nodes have the same neighbor ids. This a much stricter rule than the mathematic equivalence. It is easy to confirm that this precisely the same as equivalence of *labeled* graphs, i.e. graphs where each node is tagged with an integer label.^{5}

Since we set out to represent regular graphs rather than labeled graphs, this is somewhat unfortunate.^{6} We might consider disabling the comparison operator for our graphs to prevent subtle bugs due to misunderstanding of equality, but we cannot do that because our implementation uses built-in `dict`

.

So we just have to be careful to remember what `==`

does for graphs. And luckily, for the purposes of `test_serialization`

, comparing labeled graphs is good enough: our conversion functions happen to preserve all the node ids (even though I didn’t think about this when I wrote the code).

## Using Node Values as Node Ids

Sometimes, the node values are known to be unique and hashable. It is then tempting to just use them as node ids instead of storing values separately:

This code is slightly fragile because we have to remember to modify it if the values become non-unique in the future; also, ideally we should verify that the values provided to us are actually unique.

Note: I used generic types here. Generic types use one or several parameters (*type variables*, introduced with `TypeVar`

) to represent a whole family of types. Putting generic types in the function signature is similar to declaring several overloaded functions, one for each possible value of the parameter, but with precisely the same body:

1 2 3 4 |
T = TypeVar('T') def f(x: T) -> List[T]: return [x, x] |

is roughly equivalent to

1 2 3 4 5 6 7 8 9 |
@overload def f(x: int) -> List[int]: return [x, x] @overload def f(x: str) -> List[str]: return [x, x] # and so on... |

Except that by “several” I mean infinitely many, since parameter (type variable) `T`

in this example can represent any of the infinitely many types that may be defined in the program.

A generic class, marked as such by deriving it from `Generic[T]`

is similar to a generic function, except that the overloading happens based on the constructor arguments. Once the concrete type for each type variable is determined for a given class instance, it stays the same for all attributes and methods of that instance. If the constructor arguments are insufficient for mypy to figure out the concrete types, then mypy asks the user to add type annotation. In our case, `x = Node(1)`

would be fine because mypy can figure out that the concrete type of `T`

here is `int`

.^{7} `x = Node()`

won’t tell mypy anything about `T`

, so mypy requires type annotation, e.g. `x: Node[int] = Node()`

or `x = Node[int]()`

.

## Node Class

If we want the code to be safer, or if node values are not actually unique and hashable, and yet we still prefer to store node values together with the graph rather than elsewhere, we can just wrap node values inside a class (we can rely on the default user-defined class equality, which compares different instances as not equal):

With nodes as custom class objects, we can customize their behavior with methods. The only obvious addition I thought of is `__repr__`

, which helps debugging. Be careful not to override `__eq__`

method, since the whole point of `class Node`

is to ensure different nodes never compare equal (so that they are kept separate in the dictionary).

Note how both `read_graph`

and `write_graph`

functions became more complex. This is because we no longer store node ids in the graph object, instead referring directly to the `Node`

objects. This only works in a live graph; in the serialized format, we still need to use node ids. As a result, `read_graph`

and `write_graph`

need to create a mapping between `Node`

objects and node ids.^{8}

Also note that the test became much more complex. `read_graph(write_graph(g)) == g`

no longer holds because at the bottom of the nested collections that we use to represent the graph, we now have `Node`

objects with identity-based equality rather than integers or strings with value-based comparison. Since a `Node`

object will never compare equal to any other `Node`

object, two different graphs won’t be equal.^{9} If we want to check even the simplistic “labeled graph” equality, we need to write our own function; and that’s what I chose to do.

The function `labeled_graph_eq`

verifies whether two graphs are equal when viewed as labeled graphs, with the node labels given by the `value`

attribute. Unlike in the previous examples, we cannot assume that labels are unique (that’s the main reason why we wrapped node values in a class to begin with). Handling non-unique labels is a bit tricky, and `labeled_graph_eq`

mainly serves to help in unit tests, where we can make labels unique. Therefore, I decided to keep things simple and raise `NotImplementedError`

when non-unique labels are detected. ^{10}

## Set Representation

Now that we have a custom class to represent nodes, we can even store the adjacency sets inside them. In that case, graph is no longer a dictionary, but just a set of nodes. Unfortunately, as we make this change, we will break our existing code such as `write_graph`

and `labeled_graph_eq`

:

I think this is a (very minor) improvement over the previous version because a node object is now sufficient to find all its neighbors (the graph is no longer needed). As a result, some graph functions (e.g., a BFS traversal) will need one less argument. Related to that, `Node.__str__`

/ `Node.__repr__`

also have more information at their disposal (e.g., they could now report the node degree).

Note the instance attribute type annotation for `adj`

inside `class Node`

. This is telling mypy that `Node`

objects have an instance attribute `adj`

of the indicated type. This is necessary because mypy cannot infer the type of `adj`

based on the assignment of an empty set (without this annotation, mypy will assume that `adj`

has type `Set[Any]`

, which effectively disables part of the type checking).

Also, I had to use a string `'Set[Node[T]]'`

because class objects are not visible to python runtime in the body of their own class definition, and python runtime executes all type annotations. This problem is solved by using a forward reference, which is just a string that contains the definition you originally wanted to use.

## Limitations

To recap, we considered several simple graph implementations:

– Graph is a dictionary with nodes as keys, and adjacency sets as values

(1) Nodes are integer ids (node values stored separately)

(2) Nodes are user-provided values (which have to be hashable and unique)

(3) Nodes are instances of a custom class, which wraps user-provided values

– Graph is a set of nodes

(4) Nodes are instances of a custom class which contains values and adjacency sets

In simple cases, these approaches work fine.

But let’s try to add a new feature to our graph.

Many graph algorithms need to iterate through the incoming edges of a given

node. In order to do this efficiently, we will keep track of the adjacent

nodes in the reverse direction.^{11}

With implementations (1), (2), (3) we could change values of the dictionary

to `namedtuple`

s with forward and reverse adjacency sets. When adding or

deleting edges, we now need to update the reverse adjacency set; since we

can’t add a method to builtin `dict`

, we will define a global functions to do

that.^{12}

One problem is that we’re breaking the API of our graph: we’ll need to

replace `graph[node]`

with `graph[node].forward`

, `graph[v].add(w)`

with

`add_edge(graph, v, w)`

, and `graph[v].remove(w)`

with `remove_edge(graph, v,`

.

w)

Also, we cannot disable `dict`

methods, so if

`graph[v].add(w)`

is used by accident, we will end up with a corrupt graph. Luckily, most

such errors will probably be caught by the type checker; but still leaving

many useless or potentially dangerous methods exposed is unattractive.

With implementation (4), we seem to have more flexibility since we could put

reverse adjacency data inside the node instances. It does buy us some

reduction in code breakage: we can keep the API for simple iterations

unchanged, so only graph mutations need to be rewritten. But it comes at a

cost: we no longer can rely on the type checker to catch bugs such as

`graph[v].adj.add(w)`

without the matching `graph[w].reverse_adj.add(v)`

. In

fact, those errors won’t even cause an immediate runtime exception; they will

instead corrupt the graph object — a far more dangerous bug.

In summary, here are the problems with our current implementations:

- API often breaks as we add new features
- We cannot disable methods of bultin classes, so we expose many methods

that are not part of public API. Some of them may be dangerous (e.g.,

dictionary item assignment when we no longer want it to be used) - We cannot add new methods to builtin classes, so any functions that work

on the graph need to be global (even in python, it’s often better to organize

related functions together under a class).

If these concerns are relevant to us, for example if we are likely to enhance

the graph functionality over time, we should wrap the graph data structure in

a class. We’ll do so in part II.

## Series Contents

Part I – Representing graphs as dictionaries or sets

Part II – Representing graphs as classes

Part III – Implementing graph traversal

Part IV – Trees and binary trees

- Some type hints take the form of inheritance, and so may create a meaningful subclass relationship in runtime.
- And in that case, you really should be using numpy, pandas, or scipy to benefit from fast C implementation of such operations
- Sets have ~50% memory overhead compared to lists; in the unlikely case that memory is a bottleneck, and you don’t mind slower lookup time, you could use lists. Also, we’re talking about regular graphs, where there is no meaningful order for neighbors; of course, if such order is relevant, a list or ordered set would be appropriate.
- The ~50% memory overhead of
`dict`

vs`list`

is even less of a concern here because nodes usually occupy only a fraction of the space taken by edges. - In the previous example, the two dictionaries represented different labeled graphs: one of them had an edge from a node labeled 0 to a node labeled 1; the other had an edge from a node labeled 1 to a node labeled 0. Labeled graph comparison is much more strict than graph comparison. For example, take a graph with n nodes represented as
`{i: {i+1} for i in range(n-1)}`

. If we arbitrarily reshuffle its node ids, we would get different labeled graphs but equivalent graphs if we ignore the labels. There are n! ways to shuffle n numbers, so in this case, n! labeled graphs correspond to a single regular graph. - If you’re thinking about implementing a function that checks whether two graph objects represent equivalent unlabeled graphs, there’s bad news. A simple approach (try all permutations of node ids) has exponential complexity; it’s unknown whether a polynomial-time algorithm exists for the general case; and efficient heuristic algorithms are quite complex.
`1`

is an int and the first constructor argument is`Optional[T]`

; the only types that satisfy these constraints are superclasses of`int`

, and mypy infers`int`

(it is optimal in this case to infer the narrowest possible type, since it allows the variable to be used in as many contexts as possible.- We could have automatically generated a
`node_id`

attribute for each`Node`

object; but it’s not worth it because, while that would simplify`write_graph`

function, it would make all the other graph functions slightly more complex. - Unless we somehow make the two graphs share
`Node`

objects; this is definitely not a safe design, and anyway it’s not something that we can easily do in`read_graph`

. - Similarly, the function as written requires labels (that is,
`T`

) to be hashable; it’s slightly more troublesome to relax that restriction, and it’s good enough for unit tests. - That would reduce the cost of iteration

through the incoming edges from`O(n_edges)`

to`O(in_degree)`

, in exchange

for a constant-factor run-time and memory cost. - I don’t think this implementation is attractive, so I didn’t

include it here; but you can view in on

[github](https://github.com/pkch/graphtypes/blob/master/dictgraph_reverse_nodegeneric.py).