# Commits

committed 6a89628

Implement feedback arc set for kahn

• Participants
• Parent commits 84ecb50

# 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):`