eleisinger

import music21
import os
from collections import defaultdict

HAYDN = music21.corpus.getWork('haydn')

def title(h):
    path, mvt = os.path.split(h)
    mvt, ext = os.path.splitext(mvt)
    qrt = os.path.basename(path)

eleisinger

"""Dijkstra's shortest-path algorithm. Basic implementation (intended to run in O(m * n) time)."""

from sys import argv

def dijkstra_score(G, shortest_distances, v, w):
    return shortest_distances[v] + G[v][w]

def dijkstra(G, source):
    unprocessed = set(G.keys()) # vertices whose shortest paths from source have not yet been calculated
    unprocessed.remove(source)

eleisinger

from sys import argv
from collections import defaultdict, deque

finishing_time = 0 # number of nodes processed so far; for finishing times in first pass
finishing_order = []
scc_sizes = []

def stack_DFS(graph, seen, start, pass_one=True, pass_two=False):
# pass_one tracks finishing time; pass_two counts scc sizes
    global finishing_time, finishing_order, scc_sizes

eleisinger

""" Applications of breadth-first search of (directed) graph G.
    
    Prints distances from starting vertex to all other vertices in G and prints distance from starting vertex to ending vertices.
    Tests if G is undirected.
    If G is undirected, counts connected components of G.
"""

from sys import argv
from collections import deque