topological sort

Here is a literal translation of the topological sorting methods found on Wikipedia.

	#! /usr/bin/env python
	# -*- coding: utf-8 -*-
	"""
	`Topological sort by Kahn (1962) on Wikipedia
	<http://en.wikipedia.org/wiki/Topological_sorting>`_
	L ← Empty list that will contain the sorted elements
	S ← Set of all nodes with no incoming edges
	while S is non-empty do
	remove a node n from S
	insert n into L
	for each node m with an edge e from n to m do
	remove edge e from the graph
	if m has no other incoming edges then
	insert m into S
	if graph has edges then
	return error (graph has at least one cycle)
	else
	return L (a topologically sorted order)
	"""
	class CircularDependencyError(Exception):
	def __init__(self, keys):
	self.args = keys
	self.message = self.__str__
	def __str__(self):
	return 'Not a DAG. These keys are cyclic:\n\t%s' % str(self.args)
	def topological_sort(DAG):
	"""
	Kahn ('62) topological sort.
	:param DAG: directed acyclic graph
	:type DAG: dict
	"""
	L = []
	S = [k for k, v in DAG.iteritems() if not v]
	while S:
	n = S.pop(0)
	L.append(n)
	for m in (k for k, v in DAG.iteritems() if n in v):
	# idx = DAG[m].index(n); DAG[m].pop(idx) # Python < 2.7 alternative
	DAG[m] = list(set(DAG[m]).difference([n]))
	if not DAG[m]:
	S.append(m)
	if any([bool(v) for v in DAG.itervalues()]):
	raise CircularDependencyError([k for k, v in DAG.iteritems() if v])
	return L
	if __name__ == "__main__":
	# test DAG
	DAG = {'7': [], '5': [], '3': [], '11': ['7', '5'], '8': ['7', '3'],
	'2': ['11'], '9': ['11', '8'], '10': ['11', '3']}
	print topological_sort(DAG.copy())
	# test 10->9->8 circular dependency
	notDAG = {'7': [], '5': [], '3': [], '11': ['7', '5'], '8': ['7', '3', '10'],
	'2': ['11'], '9': ['11', '8'], '10': ['11', '3', '9']}
	print topological_sort(notDAG.copy())

view raw topological_sort.py hosted with ❤ by GitHub