Eulerian Melodies: Graph Algorithms for Music Composition

composers are identified to reuse motifs (i.e., attribute be aware progressions or melodic fragments) throughout their works. For instance, well-known Hollywood composers similar 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 methods to do one thing related 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.

Notice: All figures within the following sections have been created by the writer 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 check 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 identical node, that is referred to 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 part 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 one more outgoing edge than incoming edge, at most one node (the ending node) has yet one more 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 part. The constraints associated to being a part of a single linked part 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 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 solution 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 title — 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’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 strains (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 actual fact, 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 referred to as backtracking, which this text covers in additional element.

Eulerian Paths for Fragment Meeting

Given a set of nodes that symbolize 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 a listing of optimistic two-digit integers, is it attainable to rearrange these integers in a sequence x₁, x₂, …, x_n such that the tens digit of integer x_i matches the items digit of integer x_i+1? Suppose we’ve the next record: [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85]. By inspection, we be aware that, for instance, if x_i = 22 (with items digit 2), then x_i+1 may 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 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(record)
    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: 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 attributable to 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. Primarily, throughout DNA sequencing, scientists acquire a number of quick DNA fragments that should be stitched collectively to derive viable candidates for the complete DNA sequence, and this could doubtlessly be executed comparatively effectively utilizing the idea of a Eulerian path (see this paper for extra particulars). Every DNA fragment, generally known as a okay-mer, consists of okay 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 (okay-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 reveals a labored instance:

An Algorithm for Producing Melodies

If we’ve a set of fragments that symbolize musical motifs, we will use the strategy outlined within the earlier part to rearrange the motifs in a smart 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 Undertaking Setup

First, we have to set up FFmpeg and FluidSynth, two instruments which are helpful for processing audio knowledge. Right here is methods to set up each utilizing Homebrew on a Mac:

brew set up ffmpeg
brew set up fluid-synth

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

Now we are going to create a challenge folder referred to as eulerian-melody-generator, a most important.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 most important.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 shall 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.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 knowledge. For the needs of this text, we are going to use the file TimGM6mb.sf2, which may be discovered on this MuseScore web site or downloaded instantly from right here. We are going to place the file subsequent to most important.py within the eulerian-melody-generator listing.

Half 2: Melody Era Logic

Now, we are going to implement the melody technology logic in most important.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‑be aware 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
}

# Common 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 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 okay-mers and their corresponding de Bruijn graph. Notice that the okay-mer technology is constrained to ensure a Eulerian path within the de Bruijn graph. We additionally use a random seed throughout okay-mer technology to make sure reproducibility:

def generate_eulerian_kmers(okay, 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 []

    # decide 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):
        # decide a subsequent be aware from the size
        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

    # Test 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(okay, 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 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, okay=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 okay means extra spacing between nodes)
    pos = nx.spring_layout(G, seed=seed, okay=okay)

    # 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="pink", 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 strategy mentioned earlier, we won’t deduplicate the overlapping parts of the okay-mers throughout 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 a listing of be aware 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 perform is compose_and_export, which provides variation to the rendering of the notes that make up the Eulerian path (e.g., totally different be aware 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(be aware, octave):
    """
    Helper perform for changing a musical pitch like "C#" 
    in some octave into its numeric MIDI be aware 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 steadily
            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)
    observe = 0
    mf.addTempo(observe, 0, bpm)
    time = 0
    for be aware, octv, dur in occasions:
        pitch = note_with_octave_to_midi(be aware, octv)
        mf.addNote(observe, 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
        ],
        verify=True
    )

    print(f"Generated {mp3_file}")

Lastly, we are going to show how the melody generator can be utilized within the if title == "most important" part of the most important.py. A number of parameters — the size, tempo, okay-mer size, variety of okay-mers, variety of repetitions (or loops) of the Eulerian path, and the random seed — may be various 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 last be aware 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(okay=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, okay=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 most important.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 a less complicated various to following the steps above, the writer of this text has created a Python library referred to as emg to attain the identical end result, 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"
)

(Optionally available) 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 similar 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 positive 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 tip end result uploaded to YouTube:

The Wrap

On this article, we’ve seen how an summary topic like graph concept 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 be aware size and octave, echo the apply of aleatoric music composition (alea being the Latin phrase for “cube”), wherein some elements of the composition and its efficiency are left to probability.

Past music, the ideas mentioned within the above sections have sensible knowledge science purposes in plenty of different areas, similar 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 expertise continues to evolve and the world turns into more and more digitalized, Eulerian paths and associated graph‑theoretic ideas will possible discover many extra modern purposes throughout various domains.