Topological Sorting -- CLRS Graph Example

clrs_topo_sort.py

import sys

class Graph(dict):
	def __init__(self):
		self.explored = {}
		self.finishing = []
		self.times = {}
		self.time = 0

	def add_v(self, v):
		if v not in self:
			self[v] = []
		return self[v]

	def add_e(self, v, e):
		if v in self:
			self[v].append(e)

	def dfs_loop(self, g):
		self.explored = {}
		self.time = 0

		for v in g:			
			if v not in self.explored:
				self.s = v
				self.dfs(g, v)

	def dfs(self, g, i):
		self.explored[i] = True
		self.time += 1

		print "Exploring %s" % (i)
		discovery = self.time

		for e in g[i]:
			if e not in self.explored and e in g:
				self.dfs(g, e)

		self.time += 1
		self.times[i] = (discovery, self.time)

		self.finishing.append(i) 

G = Graph()

G.add_v("undershorts")
G.add_v("pants")
G.add_v("shoes")
G.add_e("pants", "shoes")

G.add_v("belt")	
G.add_v("jacket")
G.add_e("belt", "jacket")
G.add_e("pants", "belt")

G.add_e("undershorts", "pants")
G.add_e("undershorts", "shoes")

G.add_v("socks")
G.add_e("socks", "shoes")

G.add_v("shirt")
G.add_v("tie")
G.add_e("shirt", "tie")
G.add_e("shirt", "belt")
G.add_e("tie", "jacket")

G.dfs_loop(G)

G.finishing.reverse()
for garment in G.finishing:
	print "Garment: %s %s" % (garment, G.times[garment])