Dependency solver with O(N^2) runtime

DependencySolver.py

#!/usr/bin/env python

# input as dependency graph
# {
#  "node1": ["dep1", "dep2"...],
#  "node2": [...],
#  ...
# }

def solve( graph ):
	nodes = list( graph.keys() )
	
	sorted_nodes = []
	
	while len( nodes ) > 0:
		to_be_removed = []
		
		for node in nodes:
			is_satisfied = True
			for requirement in graph[node]:
				if requirement not in sorted_nodes:
					is_satisfied = False
					break
			
			if is_satisfied:
				to_be_removed.append( node )
				sorted_nodes.append( node )
		
		for node in to_be_removed:
			nodes.remove( node )
		
		if len( to_be_removed ) < 1:
			return None
		
	return sorted_nodes
			


### testing
# example from http://en.wikipedia.org/wiki/Topological_sorting#Examples
# 
# example = {}
# example[2] = []
# example[9] = []
# example[10] = []
# 
# example[11] = [2,9,10]
# example[8] = [9]
# example[7] = [11, 8]
# example[5] = [11]
# example[3] = [8, 10]
# 
# print solve( example )
# prints [2, 9, 10, 11, 5, 8, 3, 7]
#