Eulerian Melodies: Graph Algorithms for Music Composition | Towards Data Science

graph-theorymusicalgorithmspythonbioinformatics

Abstraction: Graph Eulerian paths applied to algorithmic melody composition

Key points:

Eulerian path visits each edge in a graph exactly once; exists in directed graphs when at most one node has out-degree minus in-degree = 1, and all others are balanced
De Bruijn graphs model musical k-mers as directed edges (prefix → suffix overlap); finding a Eulerian path through the graph yields a melody sequence
DNA fragment assembly is the canonical bioinformatics use case of the same approach: k-mers as sequence fragments, de Bruijn graph, Eulerian path = candidate genome
Python stack: networkx (graph), midiutil + midi2audio + FluidSynth (MIDI/audio), FFmpeg (MP3/MP4 export); also packaged as pip install emg
Stochastically generated k-mers constrained to guarantee Eulerian path existence; random variations in note length and octave prevent monotonous output (aleatoric composition)
Hierholzer's algorithm solves Eulerian path via backtracking in O(E) time

Connections: Graph Theory · Algorithmic Music Composition · De Bruijn Graphs