# Weighted Graphs for Algorithmic Composition

a graph-based, interpolative approach to chord progression generation

In this post, I want to share a few algo­rith­mic meth­ods I’ve recent­ly been devel­op­ing that use a graph-based approach to gen­er­ate chord pro­gres­sions. With these tools, we can build pro­gres­sions sto­chas­ti­cal­ly or deter­min­is­ti­cal­ly that reflect dif­fer­ent way of relat­ing chords to one anoth­er. For instance, we can gen­er­ate pro­gres­sions that min­i­mize voice-lead­ing dis­tance between suc­ces­sive chords, max­i­mize diver­si­ty of inter­val­lic or pitch-class con­tent, or max­i­mize acoustic con­so­nance between suc­ces­sive chords. These tools also allow us to con­struct chordal inter­po­la­tions that can define the space” between a start­ing and end­ing point in many dif­fer­ent and inter­est­ing ways.

# An Introduction to Graphs

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

## Weighted Edges

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.

## Edge Direction

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.

## Paths Through Graphs

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.

# Building Chord Graphs in Mathematica

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

## Representing Pitches

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$.

## Representing Chords

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}}

## Constructing Graphs

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.

# Finding Shortest Paths

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.

## Building Weighted Graphs

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.