Commits

Shu Zong Chen committed 6a89628

Implement feedback arc set for kahn

  • Participants
  • Parent commits 84ecb50

Comments (0)

Files changed (1)

File dependency_graph.py

 			for i in [(x, y) for x in pr for y in cr]:
 				self.vectors.add(i)
 
-	def _kahn_topological_sort(self):
+	def _kahn_topological_sort(self, fas=False):
 		"""My first topologoical sort, you will remain special in my heart"""
 		graph = self.clone()
 		L = [] # Empty list that will contain the sorted elements
 				graph.remove_vector(n,m) # remove edge e from the graph
 				if len(graph.parents_of(m)) == 0: # if m has no other incoming edges then
 					S.append(m)
+		if fas:
+			return graph.vectors
 		if graph.has_edges:
 			raise dependency_graph.CYCLIC_GRAPH("Cycle discovered during topological sort")
 		return L
 		"""Perform a topological sort as described by Kahn"""
 		return self._kahn_topological_sort()
 
+	@property
+	def kahn_feedback_arc_set(self):
+		return self._kahn_topological_sort(fas=True)
+
 	def _topological_sort(self):
 		"""I guess this one runs in linear time, and doesn't require a copy"""
 		#graph = self.clone() # and doesn't require a copy
 		"""Perform a depth-first topological sort"""
 		return self._topological_sort()
 
+	@property
+	def feedback_arc_set(self):
+		raise NotImplementedError
+
 	def __str__(self):
-		return repr(self.vectors)
+		return str(self.vectors)
 
 	class CYCLIC_GRAPH(Exception):
 		def __init__(self, value):