Eulerian Melodies: Graph Algorithms for Music Composition

composers are identified to reuse motifs (i.e., attribute notice progressions or melodic fragments) throughout their works. For instance, well-known Hollywood composers reminiscent of 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 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 writer of this text.

A Primer on Eulerian Paths

Suppose we’ve got 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 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 similar 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 related 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 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 part. The constraints associated to being a part of a single related part be sure 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 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 solution to go to all 4 elements 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’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 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 potential 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 method referred to as backtracking, which this article 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 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 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’ve got 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 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 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 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 = 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 as a consequence of backtracking
    
    # Convert the trail to an answer sequence with the unique numbers
    outcome = []
    for i in vary(len(path) - 1):
        outcome.append(path[i] * 10 + path[i+1])
    
    return outcome if len(outcome) == 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. Basically, throughout DNA sequencing, scientists receive a number of brief DNA fragments that should be stitched collectively to derive viable candidates for the total DNA sequence, and this could doubtlessly be accomplished comparatively effectively utilizing the idea of a Eulerian path (see this paper for extra particulars). Every DNA fragment, referred to 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 total 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 got a set of fragments that symbolize 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 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 Mission Setup

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

brew set up ffmpeg
brew set up fluid-synth

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

Now we are going to create a challenge folder referred to as eulerian-melody-generator, a foremost.py file to carry the melody-generation logic, and a digital atmosphere based mostly on Python 3.12:

mkdir eulerian-melody-generator
cd eulerian-melody-generator
uv init --bare
contact foremost.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 atmosphere:

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 may be discovered on this MuseScore web site or downloaded immediately from here. We’ll place the file subsequent to foremost.py within the eulerian-melody-generator listing.

Half 2: Melody Era Logic

Now, we are going to implement the melody technology logic in foremost.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
}

# 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 can 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_dict

Subsequent, we are going to implement capabilities to generate okay-mers and their corresponding de Bruijn graph. Observe 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 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.selection(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.selection(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(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’ll 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, 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)

    # Format 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 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 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 is not going to deduplicate the overlapping parts of the okay-mers in the course of 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 notice tuples right into a single record.
    """
    flattened = []
    for kmer in path_nodes:
        flattened.lengthen(kmer)
    return flattened

Now, we are going to write some capabilities 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., 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 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 progressively
            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.selection(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 display how the melody generator can be utilized within the if title == "foremost" part of the foremost.py. A number of parameters — the dimensions, tempo, okay-mer size, variety of okay-mers, variety of repetitions (or loops) of the Eulerian path, and the random seed — may be diversified to provide 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 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(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 foremost.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 different to following the steps above, the writer of this text has created a Python library referred to as emg to realize the identical outcome, 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 total 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 may be uploaded to platforms reminiscent of 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 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 outcome uploaded to YouTube:

The Wrap

On this article, we’ve got seen how an summary topic like graph idea 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”), during which some points of the composition and its efficiency are left to likelihood.

Past music, the ideas mentioned within the above sections have sensible information science functions in quite a lot of different areas, reminiscent of bioinformatics (e.g., DNA fragment meeting), archeology (e.g., reconstructing historic 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 doubtless discover many extra modern functions throughout various domains.