composers are identified to reuse motifs (i.e., attribute notice progressions or melodic fragments) throughout their works. For instance, well-known Hollywood composers equivalent to John Williams (Superman, Star Wars, Harry Potter) and Hans Zimmer (Inception, Interstellar, The Darkish Knight) deftly recycle motifs to create immediately recognizable, signature soundtracks.
On this article, we present how you can do one thing comparable utilizing knowledge science. Particularly, we are going to compose music by drawing on the graph-theoretic idea of Eulerian paths to assemble stochastically generated musical motifs into acoustically pleasing melodies. After offering an outline of theoretical ideas and a canonical use case to floor our understanding of the basics, we are going to stroll via an end-to-end Python implementation of the algorithmic music composition process.
Word: All figures within the following sections have been created by the creator of this text.
A Primer on Eulerian Paths
Suppose we’ve a graph consisting of nodes and edges. The diploma of a node in an undirected graph refers back to the variety of edges linked to that node. The in-degree and out-degree of a node in a directed graph seek advice from the variety of incoming and outgoing edges for that node, respectively. A Eulerian path is outlined as a stroll alongside the nodes and edges of a graph that begins at some node and ends at some node, and visits every edge precisely as soon as; if we begin and finish on the identical node, that is known as a Eulerian circuit.
In an undirected graph, a Eulerian path exists if and provided that zero or two nodes have an odd diploma, and all nodes with nonzero diploma are a part of a single linked element within the graph. In the meantime, in a directed graph, a Eulerian path exists if and provided that at most one node (the beginning node) has yet another outgoing edge than incoming edge, at most one node (the ending node) has yet another incoming edge than outgoing edge, all different nodes have equal incoming and outgoing edges, and all nodes with nonzero in-degree or out-degree are a part of a single linked element. The constraints associated to being a part of a single linked element be certain that all edges within the graph are reachable.
Figures 1 and a pair of beneath present graphical representations of the Seven Bridges of Königsberg and the House of Nikolaus, respectively. These are two well-known puzzles that contain discovering a Eulerian path.
In Determine 1, two islands (Kneiphof and Lomse) are linked to one another and the 2 mainland components (Altstadt and Vorstadt) of town of Königsberg in Prussia by a complete of seven bridges. The query is whether or not there may be any option to go to all 4 components of town utilizing every bridge precisely as soon as; in different phrases, we need to know whether or not a Eulerian path exists for the undirected graph proven in Determine 1. In 1736, the well-known mathematician Leonhard Euler — after whom Eulerian paths and circuits get their identify — confirmed that such a path can not exist for this explicit downside. We are able to see why utilizing the definitions outlined beforehand: all 4 components (nodes) of town of Königsberg have an odd variety of bridges (edges), i.e., it isn’t the case that zero or two nodes have an odd diploma.
In Determine 2, the target is to attract the Home of Nikolaus beginning at any of the 5 corners (nodes marked 1-5) and tracing every of the traces (edges) precisely as soon as. Right here, we see that two nodes have a level of 4, two nodes have a level of three, and one node has a level of two, so a Eulerian path should exist. In truth, as the next animation reveals, it’s apparently attainable to assemble 44 distinct Eulerian paths for this puzzle:
Eulerian paths may be derived programmatically utilizing Hierholzer’s algorithm as defined within the video beneath:
Hierholzer’s algorithm makes use of a search approach known as backtracking, which this article covers in additional element.
Eulerian Paths for Fragment Meeting
Given a set of nodes that signify fragments of data, we will use the idea of Eulerian paths to piece the fragments collectively in a significant means.
To see how this might work, allow us to begin by contemplating an issue that doesn’t require a lot area know-how: given a listing of optimistic two-digit integers, is it attainable to rearrange these integers in a sequence x1, x2, …, xn such that the tens digit of integer xi matches the items digit of integer xi+1? Suppose we’ve the next checklist: [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85]. By inspection, we notice that, for instance, if xi = 22 (with items digit 2), then xi+1 may be 23 or 25 (tens digit 2), whereas if xi = 78, then xi+1 can solely be 85. Now, if we translate the checklist of integers right into a directed graph, the place every digit is a node, and every two-digit integer is modeled as a directed edge from its tens digit to its items digit, then discovering a Eulerian path on this directed graph will give us one attainable answer to our downside as required. A Python implementation of this strategy is proven beneath:
from collections import defaultdict
def find_eulerian_path(numbers):
# Initialize graph
graph = defaultdict(checklist)
indeg = defaultdict(int)
outdeg = defaultdict(int)
for num in numbers:
a, b = divmod(num, 10) # a = tens digit, b = items digit
graph[a].append(b)
outdeg[a] += 1
indeg[b] += 1
# Discover begin node
begin = None
start_nodes = end_nodes = 0
for v in set(indeg) | set(outdeg):
outd = outdeg[v]
ind = indeg[v]
if outd - ind == 1:
start_nodes += 1
begin = v
elif ind - outd == 1:
end_nodes += 1
elif ind == outd:
proceed
else:
return None # No Eulerian path attainable
if not begin:
begin = numbers[0] // 10 # Arbitrary begin if Eulerian circuit
if not ( (start_nodes == 1 and end_nodes == 1) or (start_nodes == 0 and end_nodes == 0) ):
return None # No Eulerian path
# Use Hierholzer's algorithm
path = []
stack = [start]
local_graph = {u: checklist(vs) for u, vs in graph.objects()}
whereas stack:
u = stack[-1]
if local_graph.get(u):
v = local_graph[u].pop()
stack.append(v)
else:
path.append(stack.pop())
path.reverse() # We get the trail in reverse order as a consequence of backtracking
# Convert the trail to an answer sequence with the unique numbers
end result = []
for i in vary(len(path) - 1):
end result.append(path[i] * 10 + path[i+1])
return end result if len(end result) == len(numbers) else None
given_integer_list = [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85]
solution_sequence = find_eulerian_path(given_integer_list)
print(solution_sequence)Outcome:
[23, 34, 42, 22, 25, 57, 78, 85, 56, 67, 75, 55]DNA fragment meeting is a canonical use case of the above process within the space of bioinformatics. Basically, throughout DNA sequencing, scientists acquire a number of brief DNA fragments that have to be stitched collectively to derive viable candidates for the complete DNA sequence, and this could probably be achieved comparatively effectively utilizing the idea of a Eulerian path (see this paper for extra particulars). Every DNA fragment, generally known as a ok-mer, consists of ok letters drawn from the set { A, C, G, T } denoting the nucleotide bases that may make up a DNA molecule; e.g., ACT and CTG could be 3-mers. A so-called de Bruijn graph can now be constructed with nodes representing (ok-1)-mer prefixes (e.g., AC for ACT and CT for CTG), and directed edges denoting an overlap between the supply and vacation spot nodes (e.g., there could be an edge going from AC to CT because of the overlapping letter C). Deriving a viable candidate for the complete DNA sequence quantities to discovering a Eulerian path within the de Bruijn graph. The video beneath reveals a labored instance:
An Algorithm for Producing Melodies
If we’ve a set of fragments that signify musical motifs, we will use the strategy outlined within the earlier part to rearrange the motifs in a wise sequence by translating them to a de Bruijn graph and figuring out a Eulerian path. Within the following, we are going to stroll via an end-to-end implementation of this in Python. The code has been examined on macOS Sequoia 15.6.1.
Half 1: Set up and Challenge Setup
First, we have to set up FFmpeg and FluidSynth, two instruments which are helpful for processing audio knowledge. Right here is how you can set up each utilizing Homebrew on a Mac:
brew set up ffmpeg
brew set up fluid-synthWe will even be utilizing uv for Python undertaking administration. Set up directions may be discovered here.
Now we are going to create a undertaking folder known as eulerian-melody-generator, a principal.py file to carry the melody-generation logic, and a digital surroundings based mostly on Python 3.12:
mkdir eulerian-melody-generator
cd eulerian-melody-generator
uv init --bare
contact principal.py
uv venv --python 3.12
supply .venv/bin/activateSubsequent, we have to create a necessities.txt file with the next dependencies, and place the file within the eulerian-melody-generator listing:
matplotlib==3.10.5
midi2audio==0.1.1
midiutil==1.2.1
networkx==3.5The packages midi2audio and midiutil are wanted for audio processing, whereas matplotlib and networkx will likely be used to visualise the de Bruijn graph. We are able to now set up these packages in our digital surroundings:
uv add -r necessities.txtExecute uv pip checklist to confirm that the packages have been put in.
Lastly, we are going to want a SoundFont file to render the audio output in response to MIDI knowledge. For the needs of this text, we are going to use the file TimGM6mb.sf2, which may be discovered on this MuseScore website or downloaded straight from here. We are going to place the file subsequent to principal.py within the eulerian-melody-generator listing.
Half 2: Melody Era Logic
Now, we are going to implement the melody technology logic in principal.py. Allow us to begin by including the related import statements and defining some helpful lookup variables:
import os
import random
import subprocess
from collections import defaultdict
from midiutil import MIDIFile
from midi2audio import FluidSynth
import networkx as nx
import matplotlib.pyplot as plt
# Resolve the SoundFont path (assume that is identical as working listing)
BASE_DIR = os.path.dirname(os.path.abspath(__file__))
SOUNDFONT_PATH = os.path.abspath(os.path.be a part of(BASE_DIR, ".", "TimGM6mb.sf2"))
# 12‑notice chromatic reference
NOTE_TO_OFFSET = {
"C": 0, "C#":1, "D":2, "D#":3, "E":4,
"F":5, "F#":6, "G":7, "G#":8, "A":9,
"A#":10, "B":11
}
# Widespread pop‑pleasant interval patterns (in semitones from root)
MAJOR = [0, 2, 4, 5, 7, 9, 11]
NAT_MINOR = [0, 2, 3, 5, 7, 8, 10]
MAJOR_PENTA = [0, 2, 4, 7, 9]
MINOR_PENTA = [0, 3, 5, 7, 10]
MIXOLYDIAN = [0, 2, 4, 5, 7, 9, 10]
DORIAN = [0, 2, 3, 5, 7, 9, 10]We will even outline a few helper capabilities to create a dictionary of scales in all twelve keys:
def generate_scales_all_keys(scale_name, intervals):
"""
Construct a given scale in all 12 keys.
"""
scales = {}
chromatic = [*NOTE_TO_OFFSET] # Get dict keys
for i, root in enumerate(chromatic):
notes = [chromatic[(i + step) % 12] for step in intervals]
key_name = f"{root}-{scale_name}"
scales[key_name] = notes
return scales
def generate_scale_dict():
"""
Construct a grasp dictionary of all keys.
"""
scale_dict = {}
scale_dict.replace(generate_scales_all_keys("Main", MAJOR))
scale_dict.replace(generate_scales_all_keys("Pure-Minor", NAT_MINOR))
scale_dict.replace(generate_scales_all_keys("Main-Pentatonic", MAJOR_PENTA))
scale_dict.replace(generate_scales_all_keys("Minor-Pentatonic", MINOR_PENTA))
scale_dict.replace(generate_scales_all_keys("Mixolydian", MIXOLYDIAN))
scale_dict.replace(generate_scales_all_keys("Dorian", DORIAN))
return scale_dictSubsequent, we are going to implement capabilities to generate ok-mers and their corresponding de Bruijn graph. Word that the ok-mer technology is constrained to ensure a Eulerian path within the de Bruijn graph. We additionally use a random seed throughout ok-mer technology to make sure reproducibility:
def generate_eulerian_kmers(ok, depend, scale_notes, seed=42):
"""
Generate k-mers over the given scale that type a linked De Bruijn graph with a assured Eulerian path.
"""
random.seed(seed)
if depend < 1:
return []
# choose a random beginning (k-1)-tuple
start_node = tuple(random.alternative(scale_notes) for _ in vary(k-1))
nodes = {start_node}
edges = []
out_deg = defaultdict(int)
in_deg = defaultdict(int)
present = start_node
for _ in vary(depend):
# choose a subsequent notice from the dimensions
next_note = random.alternative(scale_notes)
next_node = tuple(checklist(present[1:]) + [next_note])
# add k-mer edge
edges.append(present + (next_note,))
nodes.add(next_node)
out_deg[current] += 1
in_deg[next_node] += 1
present = next_node # stroll continues
# Examine diploma imbalances and retry to fulfill Eulerian path diploma situation
start_candidates = [n for n in nodes if out_deg[n] - in_deg[n] > 0]
end_candidates = [n for n in nodes if in_deg[n] - out_deg[n] > 0]
if len(start_candidates) > 1 or len(end_candidates) > 1:
# For simplicity: regenerate till situation met
return generate_eulerian_kmers(ok, depend, scale_notes, seed+1)
return edges
def build_debruijn_graph(kmers):
"""
Construct a De Bruijn-style graph.
"""
adj = defaultdict(checklist)
in_deg = defaultdict(int)
out_deg = defaultdict(int)
for kmer in kmers:
prefix = tuple(kmer[:-1])
suffix = tuple(kmer[1:])
adj[prefix].append(suffix)
out_deg[prefix] += 1
in_deg[suffix] += 1
return adj, in_deg, out_degWe are going to implement a perform to visualise and save the de Bruijn graph for later use:
def generate_and_save_graph(graph_dict, output_file="debruijn_graph.png", seed=100, ok=1):
"""
Visualize graph and put it aside as a PNG.
"""
# Create a directed graph
G = nx.DiGraph()
# Add edges from adjacency dict
for prefix, suffixes in graph_dict.objects():
for suffix in suffixes:
G.add_edge(prefix, suffix)
# Structure for nodes (bigger ok means extra spacing between nodes)
pos = nx.spring_layout(G, seed=seed, ok=ok)
# Draw nodes and edges
plt.determine(figsize=(10, 8))
nx.draw_networkx_nodes(G, pos, node_size=1600, node_color="skyblue", edgecolors="black")
nx.draw_networkx_edges(
G, pos,
arrowstyle="-|>",
arrowsize=20,
edge_color="black",
connectionstyle="arc3,rad=0.1",
min_source_margin=20,
min_target_margin=20
)
nx.draw_networkx_labels(G, pos, labels={node: " ".be a part of(node) for node in G.nodes()}, font_size=10)
# Edge labels
edge_labels = { (u,v): "" for u,v in G.edges() }
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color="purple", font_size=8)
plt.axis("off")
plt.tight_layout()
plt.savefig(output_file, format="PNG", dpi=300)
plt.shut()
print(f"Graph saved to {output_file}")Subsequent, we are going to implement capabilities to derive a Eulerian path within the de Bruijn graph, and flatten the trail right into a sequence of notes. In a departure from the DNA fragment meeting strategy mentioned earlier, we won’t deduplicate the overlapping parts of the ok-mers through the flattening course of to permit for a extra aesthetically pleasing melody:
def find_eulerian_path(adj, in_deg, out_deg):
"""
Discover an Eulerian path within the De Bruijn graph.
"""
begin = None
for node in set(checklist(adj) + checklist(in_deg)):
if out_deg[node] - in_deg[node] == 1:
begin = node
break
if begin is None:
begin = subsequent(n for n in adj if adj[n])
stack = [start]
path = []
local_adj = {u: vs[:] for u, vs in adj.objects()}
whereas stack:
v = stack[-1]
if local_adj.get(v):
u = local_adj[v].pop()
stack.append(u)
else:
path.append(stack.pop())
return path[::-1]
def flatten_path(path_nodes):
"""
Flatten a listing of notice tuples right into a single checklist.
"""
flattened = []
for kmer in path_nodes:
flattened.prolong(kmer)
return flattenedNow, we are going to write some capabilities to compose and export the melody as an MP3 file. The important thing perform is compose_and_export, which provides variation to the rendering of the notes that make up the Eulerian path (e.g., totally different notice lengths and octaves) to make sure that the ensuing melody doesn’t sound too monotonous. We additionally suppress/redirect verbose output from FFmpeg and FluidSynth:
def note_with_octave_to_midi(notice, octave):
"""
Helper perform for changing a musical pitch like "C#"
in some octave into its numeric MIDI notice quantity.
"""
return 12 * (octave + 1) + NOTE_TO_OFFSET[note]
@contextlib.contextmanager
def suppress_fd_output():
"""
Redirects stdout and stderr on the OS file descriptor stage.
This catches output from C libraries like FluidSynth.
"""
with open(os.devnull, 'w') as devnull:
# Duplicate authentic file descriptors
old_stdout_fd = os.dup(1)
old_stderr_fd = os.dup(2)
strive:
# Redirect to /dev/null
os.dup2(devnull.fileno(), 1)
os.dup2(devnull.fileno(), 2)
yield
lastly:
# Restore authentic file descriptors
os.dup2(old_stdout_fd, 1)
os.dup2(old_stderr_fd, 2)
os.shut(old_stdout_fd)
os.shut(old_stderr_fd)
def compose_and_export(final_notes,
bpm=120,
midi_file="output.mid",
wav_file="temp.wav",
mp3_file="output.mp3",
soundfont_path=SOUNDFONT_PATH):
# Classical-style rhythmic motifs
rhythmic_patterns = [
[1.0, 1.0, 2.0], # quarter, quarter, half
[0.5, 0.5, 1.0, 2.0], # eighth, eighth, quarter, half
[1.5, 0.5, 1.0, 1.0], # dotted quarter, eighth, quarter, quarter
[0.5, 0.5, 0.5, 0.5, 2.0] # run of eighths, then half
]
# Construct an octave contour: ascend then descend
base_octave = 4
peak_octave = 5
contour = []
half_len = len(final_notes) // 2
for i in vary(len(final_notes)):
if i < half_len:
# Ascend regularly
contour.append(base_octave if i < half_len // 2 else peak_octave)
else:
# Descend
contour.append(peak_octave if i < (half_len + half_len // 2) else base_octave)
# Assign occasions following rhythmic patterns & contour
occasions = []
note_index = 0
whereas note_index < len(final_notes):
sample = random.alternative(rhythmic_patterns)
for dur in sample:
if note_index >= len(final_notes):
break
octave = contour[note_index]
occasions.append((final_notes[note_index], octave, dur))
note_index += 1
# Write MIDI
mf = MIDIFile(1)
monitor = 0
mf.addTempo(monitor, 0, bpm)
time = 0
for notice, octv, dur in occasions:
pitch = note_with_octave_to_midi(notice, octv)
mf.addNote(monitor, channel=0, pitch=pitch,
time=time, period=dur, quantity=100)
time += dur
with open(midi_file, "wb") as out_f:
mf.writeFile(out_f)
# Render to WAV
with suppress_fd_output():
fs = FluidSynth(sound_font=soundfont_path)
fs.midi_to_audio(midi_file, wav_file)
# Convert to MP3
subprocess.run(
[
"ffmpeg", "-y", "-hide_banner", "-loglevel", "quiet", "-i",
wav_file, mp3_file
],
examine=True
)
print(f"Generated {mp3_file}")Lastly, we are going to display how the melody generator can be utilized within the if identify == "principal" part of the principal.py. A number of parameters — the dimensions, tempo, ok-mer size, variety of ok-mers, variety of repetitions (or loops) of the Eulerian path, and the random seed — may be diversified to supply totally different melodies:
if __name__ == "__main__":
SCALE = "C-Main-Pentatonic" # Set "key-scale" e.g. "C-Mixolydian"
BPM = 200 # Beats per minute (musical tempo)
KMER_LENGTH = 4 # Size of every k-mer
NUM_KMERS = 8 # What number of k-mers to generate
NUM_REPEATS = 8 # How usually remaining notice sequence ought to repeat
RANDOM_SEED = 2 # Seed worth to breed outcomes
scale_dict = generate_scale_dict()
chosen_scale = scale_dict[SCALE]
print("Chosen scale:", chosen_scale)
kmers = generate_eulerian_kmers(ok=KMER_LENGTH, depend=NUM_KMERS, scale_notes=chosen_scale, seed=RANDOM_SEED)
adj, in_deg, out_deg = build_debruijn_graph(kmers)
generate_and_save_graph(graph_dict=adj, output_file="debruijn_graph.png", seed=20, ok=2)
path_nodes = find_eulerian_path(adj, in_deg, out_deg)
print("Eulerian path:", path_nodes)
final_notes = flatten_path(path_nodes) * NUM_REPEATS # A number of loops of the Eulerian path
mp3_file = f"{SCALE}_v{RANDOM_SEED}.mp3" # Assemble a searchable filename
compose_and_export(final_notes=final_notes, bpm=BPM, mp3_file=mp3_file)Executing uv run principal.py produces the next output:
Chosen scale: ['C', 'D', 'E', 'G', 'A']
Graph saved to debruijn_graph.png
Eulerian path: [('C', 'C', 'C'), ('C', 'C', 'E'), ('C', 'E', 'D'), ('E', 'D', 'E'), ('D', 'E', 'E'), ('E', 'E', 'A'), ('E', 'A', 'D'), ('A', 'D', 'A'), ('D', 'A', 'C')]
Generated C-Main-Pentatonic_v2.mp3As a less complicated different to following the steps above, the creator of this text has created a Python library known as emg to realize the identical end result, assuming FFmpeg and FluidSynth have already been put in (see particulars here). Set up the library with pip set up emg or uv add emg and use it as proven beneath:
from emg.generator import EulerianMelodyGenerator
# Path to your SoundFont file
sf2_path = "TimGM6mb.sf2"
# Create a generator occasion
generator = EulerianMelodyGenerator(
soundfont_path=sf2_path,
scale="C-Main-Pentatonic",
bpm=200,
kmer_length=4,
num_kmers=8,
num_repeats=8,
random_seed=2
)
# Run the complete pipeline
generator.run_generation_pipeline(
graph_png_path="debruijn_graph.png",
mp3_output_path="C-Main-Pentatonic_v2.mp3"
)(Non-compulsory) Half 3: Changing MP3 to MP4
We are able to use FFmpeg to transform the MP3 file to an MP4 file (taking the PNG export of the de Bruijn graph as cowl artwork), which may be uploaded to platforms equivalent to YouTube. The choice -loop 1 repeats the PNG picture for the entire audio size, -tune stillimage optimizes the encoding for static photos, -shortest makes certain that the video stops roughly when the audio ends, and -pix_fmt yuv420p ensures that the output pixel format is suitable with most gamers:
ffmpeg -loop 1 -i debruijn_graph.png -i C-Main-Pentatonic_v2.mp3
-c:v libx264 -tune stillimage -c:a aac -b:a 192k
-pix_fmt yuv420p -shortest C-Main-Pentatonic_v2.mp4Right here is the top end result uploaded to YouTube:
The Wrap
On this article, we’ve seen how an summary topic like graph idea can have a sensible utility within the seemingly unrelated space of algorithmic music composition. Apparently, our use of stochastically generated musical fragments to assemble the Eulerian path, and the random variations in notice size and octave, echo the follow of aleatoric music composition (alea being the Latin phrase for “cube”), by which some features of the composition and its efficiency are left to likelihood.
Past music, the ideas mentioned within the above sections have sensible knowledge science functions in a variety of different areas, equivalent to bioinformatics (e.g., DNA fragment meeting), archeology (e.g., reconstructing historical artifacts from scattered fragments at excavation websites), and logistics (e.g., optimum scheduling of parcel supply). As know-how continues to evolve and the world turns into more and more digitalized, Eulerian paths and associated graph‑theoretic ideas will seemingly discover many extra progressive functions throughout various domains.
