Eulerian Melodies: Graph Algorithms for Music Composition

composers are recognized to reuse motifs (i.e., attribute notice progressions or melodic fragments) throughout their works. For instance, well-known Hollywood composers comparable 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 the way to do one thing comparable utilizing information 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 summary of theoretical ideas and a canonical use case to floor our understanding of the basics, we are going to stroll by way of an end-to-end Python implementation of the algorithmic music composition process.

Observe: All figures within the following sections have been created by the creator of this text.

A Primer on Eulerian Paths

Suppose we have now a graph consisting of nodes and edges. The diploma of a node in an undirected graph refers back to the variety of edges related to that node. The in-degree and out-degree of a node in a directed graph discuss with 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 similar 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 related 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 related element. The constraints associated to being a part of a single related element be sure that all edges within the graph are reachable.

Figures 1 and a couple of beneath present graphical representations of the Seven Bridges of Königsberg and the Home of Nikolaus, respectively. These are two well-known puzzles that contain discovering a Eulerian path.

In Determine 1, two islands (Kneiphof and Lomse) are related to one another and the 2 mainland elements (Altstadt and Vorstadt) of town of Königsberg in Prussia by a complete of seven bridges. The query is whether or not there’s any method to go to all 4 elements of town utilizing every bridge precisely as soon as; in different phrases, we wish 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’t exist for this explicit downside. We will see why utilizing the definitions outlined beforehand: all 4 elements (nodes) of town of Königsberg have an odd variety of bridges (edges), i.e., it’s not 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. Actually, as the next animation exhibits, it’s apparently potential to assemble 44 distinct Eulerian paths for this puzzle:

Eulerian paths might 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 text covers in additional element.

Eulerian Paths for Fragment Meeting

Given a set of nodes that signify fragments of knowledge, we will use the idea of Eulerian paths to piece the fragments collectively in a significant approach.

To see how this might work, allow us to begin by contemplating an issue that doesn’t require a lot area know-how: given an inventory of constructive two-digit integers, is it potential to rearrange these integers in a sequence x₁, x₂, …, x_n such that the tens digit of integer x_i matches the models digit of integer x_i+1? Suppose we have now the next record: [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85]. By inspection, we notice that, for instance, if x_i = 22 (with models digit 2), then x_i+1 might be 23 or 25 (tens digit 2), whereas if x_i = 78, then x_i+1 can solely be 85. Now, if we translate the record 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 models digit, then discovering a Eulerian path on this directed graph will give us one potential resolution to our downside as required. A Python implementation of this method is proven beneath:

from collections import defaultdict

def find_eulerian_path(numbers):
    # Initialize graph
    graph = defaultdict(record)
    indeg = defaultdict(int)
    outdeg = defaultdict(int)
    
    for num in numbers:
        a, b = divmod(num, 10)  # a = tens digit, b = models 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 potential
    
    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: record(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 on account of backtracking
    
    # Convert the trail to an answer sequence with the unique numbers
    consequence = []
    for i in vary(len(path) - 1):
        consequence.append(path[i] * 10 + path[i+1])
    
    return consequence if len(consequence) == 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)

Consequence:

[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. Primarily, throughout DNA sequencing, scientists get hold of a number of brief DNA fragments that have to be stitched collectively to derive viable candidates for the complete DNA sequence, and this will probably be accomplished comparatively effectively utilizing the idea of a Eulerian path (see this paper for extra particulars). Every DNA fragment, often 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 can 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 can be an edge going from AC to CT as a result of 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 exhibits a labored instance:

An Algorithm for Producing Melodies

If we have now a set of fragments that signify musical motifs, we will use the method 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 by way of 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 Venture Setup

First, we have to set up FFmpeg and FluidSynth, two instruments which can be helpful for processing audio information. Right here is the way to set up each utilizing Homebrew on a Mac:

brew set up ffmpeg
brew set up fluid-synth

We may even be utilizing uv for Python mission administration. Set up directions might be discovered right here.

Now we are going to create a mission folder known as eulerian-melody-generator, a predominant.py file to carry the melody-generation logic, and a digital surroundings primarily based on Python 3.12:

mkdir eulerian-melody-generator
cd eulerian-melody-generator
uv init --bare
contact predominant.py
uv venv --python 3.12
supply .venv/bin/activate

Subsequent, 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.5

The packages midi2audio and midiutil are wanted for audio processing, whereas matplotlib and networkx might be used to visualise the de Bruijn graph. We will now set up these packages in our digital surroundings:

uv add -r necessities.txt

Execute uv pip record 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 information. For the needs of this text, we are going to use the file TimGM6mb.sf2, which might be discovered on this MuseScore website or downloaded immediately from right here. We are going to place the file subsequent to predominant.py within the eulerian-melody-generator listing.

Half 2: Melody Technology Logic

Now, we are going to implement the melody technology logic in predominant.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 similar as working listing)
BASE_DIR = os.path.dirname(os.path.abspath(__file__))
SOUNDFONT_PATH = os.path.abspath(os.path.be 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
}

# Standard 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 may even outline a few helper features 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_dict

Subsequent, we are going to implement features to generate ok-mers and their corresponding de Bruijn graph. Observe 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 related 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(record(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

    # Verify 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(record)
    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_deg

We are going to implement a operate 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)

    # Format 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 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 features 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 method 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(record(adj) + record(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 an inventory of notice tuples right into a single record.
    """
    flattened = []
    for kmer in path_nodes:
        flattened.prolong(kmer)
    return flattened

Now, we are going to write some features to compose and export the melody as an MP3 file. The important thing operate is compose_and_export, which provides variation to the rendering of the notes that make up the Eulerian path (e.g., completely 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 operate 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 degree.
    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)
        attempt:
            # 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 step by step
            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
        ],
        test=True
    )

    print(f"Generated {mp3_file}")

Lastly, we are going to show how the melody generator can be utilized within the if identify == "predominant" part of the predominant.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 — might be diversified to provide completely 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 typically ultimate 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 predominant.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.mp3

As an easier various to following the steps above, the creator of this text has created a Python library known as emg to realize the identical consequence, assuming FFmpeg and FluidSynth have already been put in (see particulars right 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"
)

(Elective) Half 3: Changing MP3 to MP4

We will use FFmpeg to transform the MP3 file to an MP4 file (taking the PNG export of the de Bruijn graph as cowl artwork), which might be uploaded to platforms comparable to YouTube. The choice -loop 1 repeats the PNG picture for the entire audio size, -tune stillimage optimizes the encoding for static pictures, -shortest makes certain that the video stops roughly when the audio ends, and -pix_fmt yuv420p ensures that the output pixel format is appropriate 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.mp4

Right here is the top consequence uploaded to YouTube:

The Wrap

On this article, we have now seen how an summary topic like graph principle can have a sensible software 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 observe of aleatoric music composition (alea being the Latin phrase for “cube”), wherein some points of the composition and its efficiency are left to probability.

Past music, the ideas mentioned within the above sections have sensible information science purposes in various different areas, comparable 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 probably discover many extra modern purposes throughout numerous domains.