Graphs

10 minute read

Graph theory is a branch of Mathematics, first introduced in 1736 when mathematician Carl Ehler introduced Leonhard Euler to the Seven Bridges of Königsberg problem1.

The Seven Bridges of Königsberg problem is based in the former German city of Königsberg (now Kaliningrad, Russia) which lays on both sides of the Pregel River.

In the center, there were two large islands which were connected to each other and to the riverbanks by seven bridges. Carl Ehler became obsessed with finding a route to walk through each of the seven bridges without walking over any of them more than once.

Ehler reached out to Leonhard Euler, a Swiss mathematician. Euler confirmed Ehler’s hypothesis that the problem did not have a solution, and Euler’s explanation informed a new mathematical paradigm called Geometry of Position.

Euler’s new geometry paradigm stated that the location of the bridges didn’t matter. The problem, instead, can be simplified by turning each bridge into a point (node) with lines (edges) to represent links between them. This practice of using nodes and edges is now known as Graph Theory.

Seven Bridges of Königsberg

Terminology

Graph theory, like any topic, has many specific terms for aspects of a graph.

Graph Example

a directed, weighted, acyclic graph with 6 vertices and 8 edges

Wow! A lot of jargon. Lets try to understand what all of these terms mean.

Vertex

A vertex (also called a node) is a fundamental part of a graph. It can have a name (a key), it may also have additional information (the payload).

Our graph has 6 vertices:

V = {a, b, c, d, e, f}

Edge

An edge (also called an “arc”) is another fundamental part of a graph. An edge connects two vertices to show that there is a relationship between them.

Our graph has 8 edges:

E = {(a, b, 45), (a, c, 52), (a, d, 7), (b, c, 11), (b, f, 5), (d, e, 17), (e, f, 6), (f, c, 21)}

Directed or Undirected

In directed graphs, edges point from the node at one end to the node at the other end. In undirected graphs, the edges simply connect the nodes at each end.

Our example is a directed graph.

Cyclic or Acyclic

A graph is cyclic if it has a cycle, an unbroken series of nodes with no repeating nodes or edges that connects back to itself. Graphs without cycles are acyclic.

Our example is a acyclic graph.

Cyclic / Acyclic Graphs

Weighted or Unweighted

If a graph is weighted, each edge has a “weight.” The weight could, for example, represent the distance between two locations, or the cost or time it takes to travel between the locations.

Representing Graphs in Code

There are a few ways to represent graphs in the code. We’ll look at the most common three, and the basic tradeoffs.

Let’s take this graph as an example:

Representing Graphs in Code

Edge List

A list of all the edges in the graph:

graph = [[0, 1], [0, 2], [1, 2], [2, 3], [2, 4], [4, 5]]

Since node 0 has edges to nodes 1 and 2, [0, 1] and [0, 2] are in the edge list.

This is well suited to performant lookups of an edge, or listing all edges, but is slow with many other query types. For example, to find all vertices adjacent to a given vertex, every edge must be examined.

Adjacency List

A list where the index represents the node and the value at that index is a list of the node’s neighbors:

graph = [
    [1, 2],
    [0, 2],
    [0, 1, 3, 4],
    [2],
    [2, 5],
    [4]
]

Since node 2 has edges to nodes 0, 1, 3 and 4, graph[2] has the adjacency list [0, 1, 3, 4].

We could also use a dictionary where the keys represent the node and the values are the lists of neighbors.

graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 4],
    3: [2],
    4: [2, 5],
    5: [4]
}

This would be useful if the nodes were represented by strings, objects, or otherwise didn’t map cleanly to list indices.

This representation allows for constant-time lookup of adjacent vertices, which is useful in many query and pathfinding scenarios.

It is slower for edge lookups, as the whole list of vertices adjacent to u must be examined for v, in order to find edge uv.

Adjacency lists are the typical choice for general purpose use, though edge lists or adjacency matrices have their own strengths, which may match a specific use case.

Adjacency Matrix

A matrix of 0 and 1 indicating whether node x connects to node y (0 means no, 1 means yes).

graph = [
    [0, 1, 1, 0, 0, 0],
    [1, 0, 1, 0, 0, 0],
    [1, 1, 0, 1, 1, 0],
    [0, 0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

Since node 4 has edges to nodes 2 and 5, graph[4][2] and graph[4][5] have value 1.

Adjacency matrices perform strongly with edge lookups, with a constant-time lookup given a pair of vertex Id. They tend to be slow for other operations. For example, listing everything adjacent to a vertex requires checking every single vertex in the graph.

They also typically require more space than other models, especially with sparse graphs (graphs with “few” edges).

Implementation

Using dictionaries, it is easy to implement the adjacency list in Python.

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def add_neighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connected to: ' + str([x.id for x in self.connectedTo])

    def get_connections(self):
        return self.connectedTo.keys()

    def get_id(self):
        return self.id

    def get_weight(self, nbr):
        return self.connectedTo[nbr]


class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def add_vertex(self, key):
        self.numVertices = self.numVertices + 1
        new_vertex = Vertex(key)
        self.vertList[key] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self, n):
        return n in self.vertList

    def add_edge(self, f, t, weight=0):
        if f not in self.vertList:
            nv = self.add_vertex(f)
        if t not in self.vertList:
            nv = self.add_vertex(t)
        self.vertList[f].add_neighbor(self.vertList[t], weight)

    def get_vertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())
Code: pythonds

References

  1. Wikipedia, Seven Bridges of Königsberg