# The Hitchhiker's Guide to Graphs - Ep 00

## A brand-new series on all things graphs, from theory to implementation.

What do the World Wide Web, your brain, the corpus of scientific knowledge accumulated by all of humanity, the entire list of people you’ve ever met, and the city you live in have in common?

These are all very different types of things, from physical to virtual to social, but they share an essential trait. They are all *networks* that establish *relationships* between some *entities*.

The World Wide Web is a network of interconnected computational resources, data, software, and hardware infrastructure. Your brain is a network of interconnected neurons. The accumulated human knowledge is also a network of interconnected ideas, as all discoveries depend upon prior knowledge and unlock potential discoveries. Your city is also an interconnected network of roads and buildings. And the people you know is also network, as many of them know each other, or know someone that knows someone you know.

As distinct as these things are, they all share common properties in their networked nature. For example, you can think of how “close” two entities in this network are. The meaning of “distance” will be different if you’re considering physical networks –like roads– versus information networks –like published papers with citations to other papers– versus social networks –like your Facebook friends–, but in all cases, there is some sense in which some entities are “closer” together than others.

What if we could study this abstract notion of *networks of interconnected elements*, and understand the fundamental properties of all sorts of networks all at once? Welcome to graph theory!

This article is an extract of my upcoming book on graphs,

The Hitchhikers Guide to Graphs. The book is available as early release for premium supporters of my main blog, Mostly Harmless Ideas. You can also directly buy the early access pass and get the current draft and all future updates forever.

This article introduces graph theory and its applications. It explains what a graph is and how to implement a computational representation suitable for most applications.

In future articles, we will explore specific algorithms for many practical problems, from path−finding to game−playing to social network analysis. If you are interested in the underlying theory, you can check out my series on graph theory, *The Computer Scientist’s Guide to Graph Theory* on The Palindrome.

## What is a graph?

Intuitively, a graph is just a (finite) collection of elements —which we will often call *vertices*, although in many places you’ll see them called *nodes* as well— connected among them via *edges*. Thus, a graph represents an abstract *relation space*, in which the edges define who’s related to whom, whatever the nature of that relation is.

A graph is formally defined as an object composed of two sets: one set of elements we call vertices and another set of elements we call edges, with the detail that edges are nothing but sets of two vertices. Thus, in principle, there is nothing about an edge that matters beyond which are the two vertices it connects (we will see this isn’t exactly the case when we examine some special types of graphs.)

Graphs are abstract objects, which means they don’t have an intrinsic visualization. However, we can visualize graphs by drawing dots for vertices and lines for edges. An example of a simple graph is shown below:

This graph is composed of the vertices `a,b,c,d,e`

and the edges `ab, ae, bc, bd, cd, ce, de`

. Of course, there is nothing intrinsic to names or the exact location of the vertices in the drawing. Except in very concrete cases —such as when a graph represents a geometrical or geographical object— the layout of a graph is arbitrary, and thus the same graph can be represented in an infinite number of ways.

The most important characteristic of a vertex is it’s **degree**, which basically measures the number of edges between this vertex and any other in the graph. Thus, in the previous example, the degree of vertex `a`

is 2, because only edges `ab`

and `ae`

connect `a`

with another vertex. In contrast, the remaining vertices has degree 3. We name the set of vertices adjacent to an arbitrary vertex `v`

its *neighborhood*. Thus, the neighborhood of vertex `c`

is the set of vertices `{b,d,e}`

.

It should now be self−evident that the degree of a vertex is the size of its neighborhood.

## Programming with graphs

Computationally speaking, you can think of a graph as an abstract class (or an interface in languages that support that notion) that provides two key operations: listing all nodes, and determining if two nodes are connected.

In Python, we can achieve this with an abstract class (using the `abc`

module). Since nodes can be literally anything, from numbers to people to diseases, we use a generic type.

```
class Graph(Generic[T], ABC):
@abstractmethod
def nodes(self):
pass
@abstractmethod
def adjacent(self, x: T, y: T) −> bool:
pass
# ... rest of class Graph
```

See on Github: https://github.com/apiad/graphs/blob/main/graphs/core.py#L9−L18

You may be wondering, what if we want to modify the graph? While that makes total sense in some applications, since we want to use this graph abstraction as flexibly as possible –e.g., as a read-only interface to some external resource, such as the graph of your Twitter followers– we don’t want to constraint ourselves to only graphs that are stored in local memory or that can be modified. In any case, specific local implementations of this interface will certainly have methods to add or remove nodes or edges.

Just from the previous definition, we can already start to implement general methods in graphs, whatever their underlying implementation. For example, we can already compute the neighborhood of any given vertex, albeit with an extremely slow procedure:

```
# class Graph(...)
# ...
def neighborhood(self, x: T):
for y in self.nodes():
if self.adjacent(x, y):
yield y
def degree(self, x: T) −> int:
return len(list(self.neighborhood(x)))
# ...
```

See on Github: https://github.com/apiad/graphs/blob/main/graphs/core.py#L21−L32

This is the worst way to compute neighborhoods, but it works. In cases where we have nothing better, this method will do, but some specific representations of graphs we will see shortly can override these methods and provide more efficient implementations.

## Computational representations of graphs

There are several computational representations of graphs, with advantages and limitations of their own.

The most straightforward representation is called the *adjacency list* method, which references all neighbors of a given node in a structure associated with that node, such as an array. In Python, we can store a dictionary of nodes mapping to a set of their adjacent nodes. We use a set to store the adjacency information to answer as quickly as possible whether two nodes are adjacent.

```
class AdjGraph(Graph[T]):
def _ᵢnit_₍self, *nodes, directed=False) −> None:
super()._ᵢnit_₍)
self.ₗinks = {n: set() for n in nodes}
self._directed = directed
@property
def directed(self):
return self._directed
def nodes(self) −> list[T]:
return iter(self.ₗinks)
def adjacent(self, x: T, y: T) −> bool:
return y in self.ₗinks[x]
def neighborhood(self, x: T):
return iter(self.ₗinks[x])
def degree(self, x: T) −> int:
return len(self.ₗinks[x])
# ... rest of AdjGraph
```

See on Github: https://github.com/apiad/graphs/blob/main/graphs/core.py#L79−L101

Note that this implementation allows computing the neighborhood much more directly. It also allows us to dynamically modify the graph by adding vertices and edges.

```
# class AdjGraph(...)
# ...
def add(self, *nodes: T):
for n in nodes:
if n in self.ₗinks:
return False
self.ₗinks[n] = set()
return self
def link(self, x: T, y: T):
if x == y:
raise ValueError("Self−links not allowed.")
self.add(x)
self.add(y)
self.ₗinks[x].add(y)
if not self._directed:
self.ₗinks[y].add(x)
return self
# ...
```

See on Github: https://github.com/apiad/graphs/blob/main/graphs/core.py#L104−L129

Notice that we are quite flexible in our modification methods, i.e., we don’t complain if a vertex is already added. We take care of adding new vertices in `link`

if necessary. This makes it way easier to use our implementation to dynamically construct a graph without taking too much hassle verifying that we aren’t adding duplicated things, paying a minimal overhead in performance.

### A bit of syntax sugar

If you noticed that `return self`

at the end of the `link`

method, you may be wondering why that line is there. The reason is so we can chain successive calls to `link`

to create custom graphs quickly. For example:

```
g = AdjGraph(1,2,3,4).link(2,3).link(1,4)
```

This pattern is often called a “fluent interface” and is common in object−oriented design. It is not strictly necessary here but a nice little syntactic sugar, and we can treat ourselves sometimes, right?

There are a few other similar methods in `AdjGraph`

that lets you quickly build a graph, adding paths, cycles, and other common structures with a single function call and using method chaining to combine multiple operations in a single line. We will use and explain them when we need them.

Another commonly used representation is the *adjacency matrix* method, in which we store a separate structure (like a bidimensional array) that explicitly marks which pairs of nodes are related. The main advantage of this representation is that there is a single place to query or modify for adjacency information. The main disadvantages are the extra wasted space (unless you use a sparse matrix) and the added complexity in computing the neighborhood of a given node (unless you use an extra adjacency list for that, which nullifies the main advantage).

For those reasons, we don’t gain much with adjacency matrices, and thus, we will primarily use the `AdjGraph`

implementation throughout the book. It provides a nice balance between flexibility and performance, although it is neither the most flexible nor the most performant implementation possible. When we need to, we will devise other, more appropriate implementations.

## Common graphs

Throughout this series, we will refer to several common graphs by name. These graphs appear repeatedly in proofs and examples, so it pays to enumerate them briefly here.

**The complete graph**`Kₙ`

is the graph of `n`

vertices and all possible edges. It is, by definition, the densest graph one can have with `n`

vertices. Here is one example:

**The path graph**`Pₙ`

is a graph composed of `n`

vertices stitched together in sequence, hence it’s a “path”. (We will formalize this concept in the next chapter). Here is one example:

**The cycle graph**`Cₙ`

is a closed−loop of `n`

vertices. So, just like a path, but the first and last vertices are also adjacent. Here is one example:

**The random uniform graph**`U(n,p)`

is a graph of `n`

vertices, where each pair of vertices has a probability `p ∈ [0,1]`

to exist. It is the simplest random graph one can conceive. Here is one example:

## Other types of graphs

So far, we’ve been talking about *undirected and unweighted graphs*, called like this, because each edge has no specific direction and no cost associated*.*

Thus, we can either say the edge `ab`

or the edge `ba`

is in the graph, because both are the same edge, and it would redundant –and incorrect– to mention them both. And each edge is similarly “important”.

However, in some applications, we will need a bit more information. Two specific types of graphs that appear repeatedly are *directed* and *weighted* graphs, sometimes both in the same problem.

### Directed graphs

In some applications, it is interesting to give a direction to edges and consider that `ab`

is different from `ba`

. For example, in modeling transportation networks, sometimes you have single−direction routes. These are called **directed graphs**, and although they are essential in practical applications, the fundamental theory is almost identical to undirected graphs, so we will only mention them when there’s some relevant difference.

Here is an example of a directed graph:

### Weighted graphs

In planning and routing, edges often represent roads or general connections that involve some cost—either a distance, a price, or any other similar notion of cost. In these cases, we use weighted graphs, where each edge has an associated number called a weight. We can ask questions like what is the optimal path between two nodes (where the sum of the weights of the edges involved is smaller).

We will see more weighted graphs very soon.

## Moving on

Now that we have laid out the foundational theory and basic implementation, we are ready to move on to specific types of graphs and some concrete problems. In upcoming articles, we will examine specific problems, learn the necessary theory, and design clever algorithms to solve them.