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 graphKₙ 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 graphPₙ 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 graphCₙ 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 graphU(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.