From 119ef90585452ad9adfc213e8cfbe93bd3aa1ce1 Mon Sep 17 00:00:00 2001
From: Sapan Bhatia <gwsapan@gmail.com>
Date: Wed, 3 Sep 2014 01:07:10 -0400
Subject: [PATCH] Updated graph routines for new sync

---
 planetstack/ec2_observer/toposort.py | 73 +---------------------------
 1 file changed, 1 insertion(+), 72 deletions(-)

diff --git a/planetstack/ec2_observer/toposort.py b/planetstack/ec2_observer/toposort.py
index 6d28f4a..e771325 100644
--- a/planetstack/ec2_observer/toposort.py
+++ b/planetstack/ec2_observer/toposort.py
@@ -19,20 +19,11 @@ def dfs(graph, visit):
 	for n in nodes:
 		edge_nodes|=set(graph[n])
 
-	print 'Edge nodes=',edge_nodes
-	print 'Nodes=',nodes
-
 	sinks = list(edge_nodes - set(nodes))
 	sources = list(set(nodes) - edge_nodes)
 	
-	print 'Sinks =',sinks
-	print 'Sources =',sources
-
 	nodes.extend(sinks)
 
-	for s in sinks:
-		graph[s]=[]
-
 	visited = set(sources)
 	stack = sources
 	while stack:
@@ -43,69 +34,7 @@ def dfs(graph, visit):
 				stack.append(node)
 				visited.add(node)
 
-
-# Topological sort + find connected components
-# Notes:
-# - Uses a stack instead of recursion
-# - Forfeits optimization involving tracking currently visited nodes
-
-def toposort_with_components(g, steps=None):
-	# Get set of all nodes, including those without outgoing edges
-	keys = set(g.keys())
-	values = set({})
-	for v in g.values():
-		values=values | set(v)
-	
-	all_nodes=list(keys|values)
-	if (not steps):
-		steps = all_nodes
-
-	# Final order
-	order = {}
-
-	# Index of newest component
-	cidx = 0
-
-	# DFS stack, not using recursion
-	stack = []
-
-	# Unmarked set
-	unmarked = all_nodes
-
-	# visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
-
-	while unmarked:
-		stack.insert(0,unmarked[0]) # push first unmarked
-
-		while (stack):
-			n = stack[0]
-			add = True
-			try:
-				for m in g[n]:
-					if (m in unmarked):
-						if (m not in stack):
-							add = False
-							stack.insert(0,m)
-						else:
-							# Should not happen, if so there's a loop
-							print 'Loop at %s'%m
-			except KeyError:
-				pass
-			if (add):
-				if (n in steps):
-					order.append(n)
-				item = stack.pop(0)
-				unmarked.remove(item)
-
-	noorder = list(set(steps) - set(order))
-
-	# Steps that do not have an order get pushed as
-	# separate components that run in parallel.
-	for s in noorder:
-		order['%d'%cidx] = [s]
-		cidx+=1
-
-	return order + noorder
+	return sources
 
 # Topological sort
 # Notes:
-- 
2.43.0