Shu Zong Chen avatar Shu Zong Chen committed 6a89628

Implement feedback arc set for kahn

Comments (0)

Files changed (1)

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):
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.