Simple Topological sort based on Kahn(1962) algorithm

topological_sort.py

import sys, re


def find_leading_nodes(graph):
    # get list of edges pointing to anything
    used_keys = [v for k in graph for v in graph[k]]
    # return a list of nodes who are not present in 'used keys'
    return [k for k in graph if k not in used_keys]
    
def has_incoming_edges(graph, node):
    # for key in list of graph nodes
    for k in graph:
        # if node is in any list of outbound edges it has by definition an inbound edge
        if node in graph[k]:
            return True
    # if not found then node has no inbound edges
    return False

def graph_has_edges(graph):
    for k in graph:
        if len(graph[k]) > 0:
            return True
            
    return False

# simple regex to get country names and edge direction
def parse_line(line):
    result = re.search('(.*)( comes before | comes after )(.*)', line)
    if result:    
        if result.group(2) == ' comes before ':
            return result.group(1), result.group(3)
        else:
            return result.group(3), result.group(1)
            
            
def add_nodes_to_graph(nodes, graph):
    # if the leading node is already present
    if nodes[0] in graph:
        # add trailing node as edge to leading node
        graph[nodes[0]].append(nodes[1])
    else:
        # otherwise the leading node must be created and the edge added
        graph[nodes[0]] = [nodes[1]] 
    
    # if the trailing node is not already present in the list of nodes, add it
    if nodes[1] not in graph:
        graph[nodes[1]] = []
                

def topological_sort(graph):
    # start with a list of leading nodes, in an acyclic graph there will always be 
    # at least one
    nodes = find_leading_nodes(graph)
    output = []
    while (nodes):
        # remove a node from the 'stack' of nodes
        node = nodes.pop()
        # add it to the output list of nodes
        output.append(node)
        # making a copy of the list of edges coming from the node because as we check each
        # trailing edge we're going to remove the item from the list of available edges.
        for edge in list(graph[node]):
            graph[node].remove(edge)
            if not has_incoming_edges(graph, edge):
                nodes.append(edge)
                
    # if the graph still has any edges we know it was cyclic and therefore illegal
    if graph_has_edges(graph):
        return ['Illegal request file!']
    else: 
        return output
        

def main():    
    graph = {}
    
    # read input for lines
    for line in sys.stdin.readlines():
        # parse lines for nodes and add to graph
        add_nodes_to_graph(parse_line(line), graph)
    # print out formatted list of topologically sorted nodes
    print "\n".join(topological_sort(graph))
    
    
    
if __name__ == "__main__":
    main()