Toplogical Sort

topological_sort.py

def topological_sort_nx(files):
    graphs = nx.DiGraph()
    for file in files:
        graphs.add_node(file)

    for fileA in files:
        for fileB in files:
            if has_dependency(fileA, fileB):
                graphs.add_edge(fileB, fileA)

    # get disconnected graphs
    subgraphs = list(nx.weakly_connected_components(graphs))
    
    allResults = []
    for subgraph in subgraphs:
        results = []
        subgraph_nodes = set(subgraph)
        while len(results) != len(subgraph_nodes):
            # 𝑓𝑖𝑙𝑒 ← argmin({𝑖𝑛𝐷𝑒𝑔𝑟𝑒𝑒[ 𝑓𝑖𝑙𝑒] | 𝑓𝑖𝑙𝑒 ∈ 𝑠𝑢𝑏𝑔𝑟𝑎𝑝ℎ and 𝑓𝑖𝑙𝑒 ∉ 𝑟𝑒𝑠𝑢𝑙𝑡𝑠})
            nodes = subgraph_nodes.difference(set(results))
            file = min(
                nodes, 
                key = lambda file: graphs.in_degree(file)
            )
            results.append(file)
        allResults.append(results)
    return allResults