Music, graphs, and hamiltonian cycles (2)

In the last posts, we have seen many examples of musical graphs wherein vertices are labelled with chords, and edges correspond to some relation between them. I already talked about graphs and music in older posts (see here and here), and I also talked about hamiltonian paths and cycles. In the case of chords, hamiltonian cycles give progressions through all of them following the relation between them which is used to define the edges.

The first authors to determine all hamiltonian cycles in the neo-Riemannian Tonnetz were Albini and Antonini, in a paper from the MCM (Mathematics and Computation in Music) conference:

• G. Albini, S. Antonini; “Hamiltonian Cycles in the Topological Dual of the Tonnetz”; Proceedings of the MCM 2009 Conference, CCIS 38, Springer, pp. 1-11

They determined that there are 62 distinct hamiltonian cycles, and I already mentionned that my colleague Moreno Andreatta used some of them to compose. I’m posting again a video to one of his songs below, animated by Gilles Baroin.

In this post, I would like to revisit hamiltonian cycles, and I’m also taking this post as an opportunity to showcase what can be done with Opycleid, the Python package I wrote for transformational music analysis. Opycleid was written so that potentially any group, monoid, or category of musical actions could be defined, and then used for musical analysis. Opycleid already includes the most well-known groups and monoids, and this is what we are going to use now. Let’s rediscover the work of Albini and Antonini : first, we need to import the famous neo-Riemannian PRL group.

import numpy as np
from opycleid.musicmonoids import PRL_Group

mg = PRL_Group()

The variable mg now contains an instance of the PRL group, which we can use to determine the action of some operations, or to determine the possible operation between any two major or minor chords.

mg.apply_operation("L","D_M")
## prints ['Fs_m']
mg.get_operation("D_M","A_m")
## prints ['PRL']

To find the hamiltonian cycles, we are going to use the following naïve backtracking algorithm.

all_chords = mg.get_object().get_elements()

def hamiltonian_cycles(path):
if len(path)==24:
op = mg.get_operation(path[-1],path)
if ("P" in op) or ("R" in op) or ("L" in op):
yield path
else:
last_elm = path[-1]
next_chords=[]
for op in ["P","R","L"]:
next_chords += mg.apply_operation(op,last_elm)
next_chords=set(next_chords)
for x in next_chords:
if not x in path:
for y in hamiltonian_cycles(path+[x]):
yield y

And if we run it starting from the C major chord, we’ll find exactly the 62 hamiltonian cycles of Albini and Antonini (actually, twice that number since our backtracking algorithm differentiates between orientations).

l=list(hamiltonian_cycles(["C_M"]))
print("Number of hamiltonian cycles :",len(l))
# Number of hamiltonian cycles : 124

Let’s print one for example :

print(" - ".join(l))
# C_M - A_m - F_M - F_m - Cs_M - Cs_m - A_M - Fs_m - D_M - D_m - Bb_M - Bb_m - Fs_M - Eb_m - B_M - B_m - G_M - G_m - Eb_M - C_m - Gs_M - Gs_m - E_M - E_m

Now, in the last posts, we have discussed the “Cube Dance” graph, which is the parsimonious graph for the $\mathcal{P}_{1,0}$ relation of Douthett and Steinbach. Can you already figure if this graph has hamiltonian cycles and if so, how many ?

If not, we’ll do it the same way using Opycleid. The UPL monoid is already defined, so we just have to slightly adapt our backtracking algorithm :

from opycleid.musicmonoids import UPL_Monoid

mg = UPL_Monoid()
all_chords = mg.get_object().get_elements()

def hamiltonian_cycles(path):
if len(path)==28:
op = mg.get_operation(path[-1],path)
if ("P" in op) or ("U" in op) or ("L" in op):
yield path
else:
last_elm = path[-1]
next_chords=[]
for op in ["P","U","L"]:
next_chords += mg.apply_operation(op,last_elm)
next_chords=set(next_chords)
for x in next_chords:
if not x in path:
for y in hamiltonian_cycles(path+[x]):
yield y
l=list(hamiltonian_cycles(["C_M"]))
print("Number of hamiltonian cycles :",len(l))
# Number of hamiltonian cycles : 2592

And as expected, we obtain 1296 different hamiltonian cycles. That’s a lot of possibilities for composition !

Finally, as a teaser, here is an arrangement I made (in the style of Philip Glass, some would say) for a hamiltonian cycle in a particular graph between all 36 major, minor, and major seventh chords.