Part of the From Nodes to Connections series.

In Postgres: The Graph Database You Didn’t Know You Had we covered how we can store a DAG (Directed Acyclic Graph) in a relational database. We looked at one representation of a graph data structure called an adjacency list—a table with two columns representing how nodes connect. The columns store connections from the source or “from” node to a destination or “to” node.

Using Python, a code representation would look like:

class Node:
    pass

A = Node()
B = Node()
C = Node()

adjacency_list = [
    { "source": A, "destination": B },
    { "source": A, "destination": C },
]

An adjacency list is a simple and efficient way to store graph data, but there are many more ways to represent graphs. In this article, we’ll explore one of these alternatives called the adjacency matrix.

Adjacency Matrix

An adjacency matrix is a table with a row and column for each node in the graph (or NxN matrix). To represent the edges we store a 1 in a column for a connection and a 0 for no connection. We will start out exploring how to represent DAG’s as an adjacency matrix since we covered DAG’s in the Postgres article. To store direction in an adjacency matrix the x-axis or rows represent the “from” or “source” node. The y-axis represents the connection. Using the same graph as above, the adjacency matrix would look like this:

adjacency_matrix = [
  [0, 1, 1],
  [0, 0, 0],
  [0, 0, 0]
]

What about non-DAG graphs?

For unidirected graphs, graphs where all connections are bidirectional, the setup is the same to create the adjacency matrix. The only difference is our graph has no explicit direction. If A connections to B, then B also connects to A. Let’s take our previous DAG graph, and remove the direction.

A cool property emerges from unidirected graphs. Can you spot a pattern in the table above? Draw