a graph-based, interpolative approach to chord progression generation

In this post, I want to share a few algorithmic methods I’ve recently been developing that use a graph-based approach to generate chord progressions. With these tools, we can build progressions stochastically or deterministically that reflect different way of relating chords to one another. For instance, we can generate progressions that minimize voice-leading distance between successive chords, maximize diversity of intervallic or pitch-class content, or maximize acoustic consonance between successive chords. These tools also allow us to construct chordal interpolations that can define the “space” between a starting and ending point in many different and interesting ways.

With the stipulation that I am neither a mathematician nor a data scientist, here’s my best shot at simply explaining graphs: A graph is a group of *vertices* (like on a triangle) that are connected by a series of *edges.* Vertices typically represent something like a person in a social network, an animal species, or (in this case) a chord. By connecting certain vertices to one another, graph edges show us how the represented objects are interrelated.

If all of this sounds like I am describing a network, you’re right. The terms are largely interchangeable, although they are typically used in different contexts for different purposes and have different terminologies. Networks feature *nodes* that are connected by *links,* and typically emphasize how things like money, data, or pathogens are passed between nodes. Graphs, with their *vertices* and *edges,* typically emphasize how things are related to one another. In my experience, though, these distinctions are not universal.

A basic graph or network with their associated terminology

Beyond simply indicating connection, edges can have features of their own that describe the nature of the relationship between the vertices they connect; we typically refer to these features as *weights.* For instance, if we have vertices representing various cities, we might connect them with edges that are weighted with the distance between each pair.
Along these lines, we can use edge weights to express the distance, cost, or energy required to “move” from one vertex to another or any other quantifiable relationship between vertices. We can define edge weights either arbitrarily on an edge-by-edge basis or else by using a function that takes two vertices as arguments and returns a weight for the edge that connects them. For instance, if we define a graph with chords as vertices, we might build functions to measure the voice-leading distance between two chords or the cardinality of their union’s set class. We could then use those functions to weight the edges connecting our chord-vertices.

A basic graph showing the voice-leading distances between closely related dyads. The edge-weights are both labeled and shown in terms of thickness.

It's also important to note that edges can be either *directed* or *undirected,* meaning that they can permit motion (or transmission, relation, etc.) either in both directions or in only one. In text, an undirected edge will be denoted with a double-sided arrow, as in ~$ a \leftrightarrow b $~, while directed edges will get a mono-directional arrow, such as ~$ a \rightarrow b $~. There may also be cases where a pair of vertices is connected not by one undirected edge, but rather by two directed edges. This manner of connection allows each edge to feature its own weight, giving more specific information about the character of moving from one vertex to another.

If we have a graph of chords, we can think of chord progressions as *paths* taken through the graph, successions of vertices that are connected by edges. In some cases, such as our voice-leading distance graph, all possible paths from a given chord ~$a$~ to ~$c$~ will add up to the same total of edge weights, but this will not always be the case. For example, in the following graph, three dyads are connected with edges that are weighted with a function ~$F$~, which takes the two chords as arguments and returns the total number of unique pitch-classes contained within both chords — that is the cardinality of the union of both chords, or ~$ F (c_1,c_2) = | c_1 \cup c_2 | $~.

As shown in the example below, there are two possible paths between ~$a$~ and ~$c$~. We can see that the total edge-weight for the first path (~$ a \leftrightarrow b \leftrightarrow c $~) is 8 pitch-classes, meaning that it “costs less” to take the second path (~$ a \leftrightarrow c $~) with a total weight of 5.

Two paths through the same graph, where the function ~$ F (c_1,c_2) $~ controls edge-weighting.

In larger chord graphs, the shortest path(s) between two chords may be both long and unintuitive, depending on the criterion used to connect vertices and the functions that determine edge weighting. Thankfully, computers offer us powerful tools for building graphs and finding paths through them.

A larger, relatively complex weighted graph with a highlighted path between two vertices. With larger graphs like this one, computers are particularly useful for determining weights and finding paths.

With this cursory background in mind, let's look at how we can use graphs to generate chord progressions.

First, we need to build a list of the chords that will be permitted within the generated progressions. Each chord will be a list of pitches, expressed numerically according to the following scheme:

- For Middle C (midi note 60), ~$ p = 0 $~. For all other pitches, ~$ p $~ gives the difference in cents between the pitch and middle C, divided by 100.
- For any pitch ~$p$~, ~$ \text{Mod}_{12} ( p ) = $~ the pitch-class of ~$p$~.
- (optionally) Non-integer pitches may be used to express microtones.

So for Middle C (C-4) ~$ p = 0, $~ for C-5 ~$ p = 12, $~ and for B-3 ~$ p = -1 $~.

For this project, we will build chords by pulling from a limited collection of pitches, which I will refer to as a *pitch space.* One benefit of this approach is that we can easily define rules to describe the kinds of chords we want and then have the computer efficiently identify all of the options within our pitch space that meet those requirements.

For now, let's limit our consideration to the octave above Middle C in 12TET pitch space, integers from ~$ p = 0 $~ to ~$ p = 12 $~.

```
pitchSpace = Range[0, 12]
// {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
```

Then we'll take only the chords of set-class (0 3 7) from this pitch collection.

```
chords = Select[
Subsets[pitchSpace, {3}],
SetClass[#] == {0, 3, 7} &
]
// {{0, 3, 7}, {0, 5, 9}, {1, 4, 8}, ... {5, 9, 12}}
```

In Mathematica, we can create a graph by specifying edges and vertices at once.

`Graph[{x⟷y, y⟷z, z⟷x, x⟷q, q⟷y}]`

A basic graph definition in Mathematica. The ⟷ symbol connecting the vertex letters in the code here are standing in for the proper undirected edge character used in the Wolfram Language. That symbol can be inputted in Mathematica by typing `ESC ue ESC`

.

Graph vertices can be any expression within Mathematica, so we can use the elements from our *chords* array:

`Graph[{chords[[1]]⟷chords[[2]]}]`

Along these lines, we can programmatically build a graph that connects each element of *chords* to every other. We will refer to this graph as `gComplete`

.

```
gComplete = Graph[
Flatten[
Table[
chords[[i]]⟷# & /@ Complement[chords, chords[[i ;; i]]],
{i, Length[chords]}
],
1]
]
```

A graph of the elements of *chords* in which each chord is connected to every other.

Or we can connect chords together randomly, as in the below example, where we define a graph `gRand`

that projects two edges out of each vertex randomly.

```
gRand = Graph[
Flatten[
Table[
chords[[i]] ⟷ # & /@ Complement[
RandomSample[chords, 2],
chords[[i ;; i]]
],
{i, Length[chords]}
],
1]
]
```

A graph of the elements of `chords`

in which 2 edges are assigned to each vertex randomly.

Mathematica also provides the function `FindShortestPath`

, which takes as arguments the graph in question as well as starting and ending vertices. The function returns a list of vertices for the shortest path between two points. For example, we can find the shortest path between the vertices `{1,4,8}`

and `{5,9,12}`

in our graph `gRand`

as follows.

```
path = FindShortestPath[gRand, {1, 4, 8}, {5, 9, 12}]
// {{1, 4, 8}, {0, 5, 9}, {3, 6, 10}, {5, 9, 12}}
```

We can then assign this shortest path to the variable `path`

and highlight it within the context of `gRand`

.

`HighlightGraph[gRand, PathGraph[path]]`

The graph `gRand`

with the shortest path between the vertices `{1,4,8}`

and `{5,9,12}`

highlighted.

When defining a graph in Mathematica, we give a list of edges in a particular order. Weights for each edge may be passed to the `Graph`

function as a separate list, as long as you take care that the order of the weights matches that of the vertices.

For example, consider the following lists `edges`

and `weights`

. In Mathematica, edges are expressed by using an edge symbol (like ⟷) to directly link the actual expressions that serve as vertices, so it is not necessary to first define a list of vertices as each edge in our list specifies two vertices and an edge between them.

```
edges = {x ⟷ y, y ⟷ z, z ⟷ x, x ⟷ w, w ⟷ y};
weights = {1, 4, 1, 3, 1};
```

In this code, the first element of `weights`

describes the edge between ~$x$~ and ~$y$~, the second describes the edge between ~$y$~ and ~$z$~, etc.

We can then use `edges`

and `weights`

to define a weighted graph `g`

:

`g = Graph[edges, EdgeWeight -> weights]`

A weighted graph `g`

with each weight shown in gray and centered on its edge. The vertices are labeled in black.

Let's say we want to find the shortest path from z to w. If we don't take edge weighting into account, the paths ~$ z \to x \to w $~ and ~$ z \to y \rightarrow w $~ would be the shortest in terms of the total number of edges traversed. If we consider weights, however, the shortest path is ~$ z \to x \to y \to w $~ with a total weight of 3, in comparison to ~$ z \to x \to w $~ with 4 and ~$ z \to x \to y \to w $~ with 5.

To verify that ~$ z \to x \to y \to w $~ is the shortest path, we can use the `FindShortestPath`

function:

```
path = FindShortestPath[g, z, w]
{z, x, y, w}
```

As before, we can then easily visualize this path:

`HighlightGraph[g, PathGraph[path]]`

The weighted graph `g`

, with the shortest path between its vertices ~$ z $~ and ~$ w $~ highlighted.