import sys
from pprint import pprint
def topological_sort_visit(graph, node, node_list):
if node in graph:
if graph[node]['mark'] == 2:
return
if graph[node]['mark'] == 1:
# there are cycles in our graph. don't go down this path
return
graph[node]['mark'] = 1
for child in graph[node]['children']:
topological_sort_visit(graph, child, node_list)
graph[node]['mark'] = 2
# since there are cycles, check presence before adding
if node not in node_list:
node_list.append(node)
def topological_sort(graph):
nodes = []
for key in graph.keys():
topological_sort_visit(graph, key, nodes)
return nodes
graph = {}
# The input represents a Source -> Destination mapping
for line in sys.stdin.read().strip().split('\n'):
[src, dest] = line.replace("'", "").split(':')
if src not in graph:
graph[src] = {'children': [dest], 'mark': 0}
else:
graph[src]['children'].append(dest)
sorted_list = topological_sort(graph)
pprint(sorted_list)
To embed this program on your website, copy the following code and paste it into your website's HTML: