# dependency-graph

committed 6a89628

Implement feedback arc set for kahn

# 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.