dag.py

from random import randint
import networkx as nx

def random_dag(nodes, edges):
    """Generate a random Directed Acyclic Graph (DAG) with a given number of nodes and edges."""
    G = nx.DiGraph()
    for i in range(nodes):
        G.add_node(i)
    while edges > 0:
        a = randint(0,nodes-1)
        b=a
        while b==a:
            b = randint(0,nodes-1)
        G.add_edge(a,b)
        if nx.is_directed_acyclic_graph(G):
            edges -= 1
        else:
            # we closed a loop!
            G.remove_edge(a,b)
    return G

print('generating dag')
dag = random_dag(5000, 5000)
print('done generating dag')
vertlist = list(dag.nodes)
edgelist = list(dag.edges)

topsort.py

from itertools import chain

#         Prepare Kitchen
#             /     \
#      Mix flour   Mix wet ingredients
#               \ /
#              Combine
#               /     \
#      Put in oven   Clean kitchen
# 
# Return a valid ordering such that all upstream steps come before all downstream steps. For example:
# 
# ['Prepare kitchen', 'Mix flour', 'Mix wet ingredients', 'Combine', 'Clean kitchen', 'Put in oven']
# OR
# ['Prepare kitchen', 'Mix wet ingredients', 'Mix flour', 'Combine', 'Clean kitchen', 'Put in oven']
# OR
# ['Prepare kitchen', 'Mix wet ingredients', 'Mix flour', 'Combine', 'Put in oven', 'Clean kitchen']

vertex_list = [
    "Prepare kitchen", "Mix flour", "Mix wet ingredients", "Combine", "Put in oven", "Clean kitchen"
]
edge_list = [
    ("Prepare kitchen", "Mix wet ingredients"),
    ("Prepare kitchen", "Mix flour"),
    ("Mix flour", "Combine"),
    ("Mix wet ingredients", "Combine"),
    ("Combine", "Put in oven"),
    ("Combine", "Clean kitchen"),
]

def to_adj_list(vertlist, edgelist):
    acc = {}
    for src, dst in edgelist:
        if src not in acc:
            acc[src] = []
        acc.get(src).append(dst)
    for src in vertex_list:
        if src not in acc:
            acc[src] = []
    return acc

def topsort(vertlist, edgelist):
    output = []
    adjlist = to_adj_list(vertlist, edgelist)

    visited = set()
    def dfs(key):
        if key in visited:
            return
        visited.add(key)
        for vert in adjlist[key]:
            dfs(vert)
        output.append(key)

    for vert in vertex_list:
        dfs(vert)

    return list(reversed(output))

def topsort_slow(vertlist, edgelist):
    output = []
    adjlist = to_adj_list(vertlist, edgelist)

    all_dests = set(chain(*adjlist.values()))
    roots = set(vertlist) - all_dests

    q = roots
    while q:
        all_dests = set()
        for src in q:
            dests = adjlist.get(src, [])
            all_dests.update(dests)
            output.append(src)
        q = all_dests

    return output

import time
import dag

vertex_list = list(dag.vertlist)
edge_list = list(dag.edgelist)

st = time.time()
#print(topsort_slow(vertex_list, edge_list))
print('slow', time.time() - st)

st = time.time()
#print(topsort(vertex_list, edge_list))
print('optimized', time.time() - st)