marrow/package/tarjan.py
def strongly_connected_components(graph: Graph) -> List:
	"""Find the strongly connected components in a graph using Tarjan's algorithm.
	
	The `graph` argument should be a dictionary mapping node names to sequences of successor nodes.
	"""
	
	assert check_argument_types()
	
	result = []
	stack = []
	low = {}
	
	def visit(node: str):
		if node in low: return
		
		num = len(low)
		low[node] = num
		stack_pos = len(stack)
		stack.append(node)
		
		for successor in graph[node]:
			visit(successor)
			low[node] = min(low[node], low[successor])
		
		if num == low[node]:
			component = tuple(stack[stack_pos:])
			del stack[stack_pos:]
			
			result.append(component)
			
			for item in component:
				low[item] = len(graph)
	
	for node in graph:
		visit(node)
	
	return result
def strongly_connected_components(graph: Graph) -> List:
	assert check_argument_types()
	
	result = []
	stack = []
	low = {}
	
	def visit(node: str):
		if node in low: return
		
		num = len(low)
		low[node] = num
		stack_pos = len(stack)
		stack.append(node)
		
		for successor in graph[node]:
			visit(successor)
			low[node] = min(low[node], low[successor])
		
		if num == low[node]:
			component = tuple(stack[stack_pos:])
			del stack[stack_pos:]
			
			result.append(component)
			
			for item in component:
				low[item] = len(graph)
	
	for node in graph:
		visit(node)
	
	return result
def strongly_connected_components ( graph : Graph ) -> List : assert check_argument_types ( ) result = [ ] stack = [ ] low = { } def visit ( node : str ) : if node in low : return num = len ( low ) low [ node ] = num stack_pos = len ( stack ) stack . append ( node ) for successor in graph [ node ] : visit ( successor ) low [ node ] = min ( low [ node ] , low [ successor ] ) if num == low [ node ] : component = tuple ( stack [ stack_pos : ] ) del stack [ stack_pos : ] result . append ( component ) for item in component : low [ item ] = len ( graph ) for node in graph : visit ( node ) return result
Find the strongly connected components in a graph using Tarjan's algorithm.
	
	The `graph` argument should be a dictionary mapping node names to sequences of successor nodes.
Find the strongly connected components in a graph using Tarjan s algorithm . The graph argument should be a dictionary mapping node names to sequences of successor nodes .