Topological Sort

topSort.py

# Constants
UNVISITED = 0
VISITED = 1
EXPLORED = 2

# Test Adjacency List Graph
# 0 -> 1 -> 2 -> 3
graph = [[1], 
         [2], 
         [3], 
         []]

def topSort(graph):
  """
  :type graph List[List[int]]
  :rtype: List[int]
  """
  # Initialize State
  state = [UNVISITED for i in range(len(graph))]

  # Topologically Sorted Order
  order = []
            
  # Start DFS from each unvisited node
  for node in range(len(graph)):
    if state[node] == UNVISITED:
      ret = subGraphHasCycle(graph,node,state,order)
      if ret:
        return [] # No Topological order exists

  # Depending on the application
  # And the direction the edges were drawn
  # You may want to reverse this order
  # Or you may want to modify the algorithm to insert them from
  # Right to Left  
  order.reverse()
  return order
        
def subGraphHasCycle(graph, node, state, order):
        
  if state[node] == VISITED:
    return True
  if state[node] == EXPLORED:
    return False
        
  state[node] = VISITED
        
  for neighbor in graph[node]:
    ret = subGraphHasCycle(graph, neighbor, state, order)
    if ret:
      return True
            
  state[node] = EXPLORED
  order.append(node)
  return False

print (topSort(graph))