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 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 one can do one thing related utilizing information science. Particularly, we’ll 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’ll stroll by means of an end-to-end Python implementation of the algorithmic music composition process.

Notice: 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 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 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 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 another outgoing edge than incoming edge, at most one node (the ending node) has 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 couple of under 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 the town of Königsberg in Prussia by a complete of seven bridges. The query is whether or not there’s any approach to go to all 4 elements of the 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 not exist for this explicit downside. We are able to see why utilizing the definitions outlined beforehand: all 4 elements (nodes) of the 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 reality, as the next animation exhibits, it’s apparently doable to assemble 44 distinct Eulerian paths for this puzzle:

Eulerian paths might be derived programmatically utilizing Hierholzer’s algorithm as defined within the video under:

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 symbolize fragments of data, 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 doable 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 have now the next listing: [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85]. By inspection, we notice that, for instance, if x_i = 22 (with items 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 listing 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 doable answer to our downside as required. A Python implementation of this strategy is proven under:

from collections import defaultdict

def find_eulerian_path(numbers):
    # Initialize graph
    graph = defaultdict(listing)
    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 doable
    
    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: listing(vs) for u, vs in graph.gadgets()}
    
    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 resulting from 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)

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 get hold of a number of quick DNA fragments that have to be stitched collectively to derive viable candidates for the total DNA sequence, and this may probably be performed 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 because of the 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 under exhibits a labored instance:

An Algorithm for Producing Melodies

If we have now 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’ll stroll by means 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 might be helpful for processing audio information. Right here is how one can 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 venture administration. Set up directions might be discovered right here.

Now we’ll create a venture folder known as eulerian-melody-generator, a fundamental.py file to carry the melody-generation logic, and a digital atmosphere primarily based on Python 3.12:

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

uv add -r necessities.txt

Execute uv pip listing to confirm that the packages have been put in.

Lastly, we’ll want a SoundFont file to render the audio output in response to MIDI information. For the needs of this text, we’ll 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 fundamental.py within the eulerian-melody-generator listing.

Half 2: Melody Era Logic

Now, we’ll implement the melody era logic in fundamental.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
}

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

def generate_eulerian_kmers(okay, rely, scale_notes, seed=42):
    """
    Generate k-mers over the given scale that kind a related De Bruijn graph with a assured Eulerian path.
    """
    random.seed(seed)
    if rely < 1:
        return []

    # decide 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(rely):
        # decide a subsequent notice from the size
        next_note = random.selection(scale_notes)
        next_node = tuple(listing(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 satisfy 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, rely, scale_notes, seed+1)

    return edges


def build_debruijn_graph(kmers):
    """
    Construct a De Bruijn-style graph.
    """
    adj = defaultdict(listing)
    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 reserve it as a PNG.
    """
    # Create a directed graph
    G = nx.DiGraph()

    # Add edges from adjacency dict
    for prefix, suffixes in graph_dict.gadgets():
        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 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’ll 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 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(listing(adj) + listing(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.gadgets()}
    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 listing.
    """
    flattened = []
    for kmer in path_nodes:
        flattened.prolong(kmer)
    return flattened

Now, we’ll 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 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)
        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
        ],
        verify=True
    )

    print(f"Generated {mp3_file}")

Lastly, we’ll reveal how the melody generator can be utilized within the if identify == "fundamental" part of the fundamental.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 — might be assorted 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 typically closing 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, rely=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 fundamental.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 different to following the steps above, the creator of this text has created a Python library known as emg to attain the identical outcome, 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 under:

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 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 might 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 photographs, -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 outcome uploaded to YouTube:

The Wrap

On this article, we have now 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 apply of aleatoric music composition (alea being the Latin phrase for “cube”), through which some features 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 quite a lot of different areas, equivalent to 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 know-how continues to evolve and the world turns into more and more digitalized, Eulerian paths and associated graph‑theoretic ideas will possible discover many extra progressive purposes throughout numerous domains.