# Copyright (c) 2013 Mark Dickinson | |

# | |

# Permission is hereby granted, free of charge, to any person obtaining a copy | |

# of this software and associated documentation files (the "Software"), to deal | |

# in the Software without restriction, including without limitation the rights | |

# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |

# copies of the Software, and to permit persons to whom the Software is | |

# furnished to do so, subject to the following conditions: | |

# | |

# The above copyright notice and this permission notice shall be included in | |

# all copies or substantial portions of the Software. | |

# | |

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |

# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |

# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |

# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |

# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |

# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |

# SOFTWARE. | |

def StronglyConnectedComponents(vertices, edges): | |

"""Find the strongly connected components of a directed graph. | |

Uses a non-recursive version of Gabow's linear-time algorithm [1] to find | |

all strongly connected components of a directed graph. | |

A "strongly connected component" of a directed graph is a maximal subgraph | |

such that any vertex in the subgraph is reachable from any other; any | |

directed graph can be decomposed into its strongly connected components. | |

Written by Mark Dickinson and licensed under the MIT license [2]. | |

[1] Harold N. Gabow, "Path-based depth-first search for strong and | |

biconnected components," Inf. Process. Lett. 74 (2000) 107--114. | |

[2] From code.activestate.com: http://goo.gl/X0z4C | |

Args: | |

vertices: A list of vertices. Each vertex should be hashable. | |

edges: Dictionary that maps each vertex v to a set of the vertices w | |

that are linked to v by a directed edge (v, w). | |

Returns: | |

A list of sets of vertices. | |

""" | |

identified = set() | |

stack = [] | |

index = {} | |

boundaries = [] | |

for v in vertices: | |

if v not in index: | |

to_do = [('VISIT', v)] | |

while to_do: | |

operation_type, v = to_do.pop() | |

if operation_type == 'VISIT': | |

index[v] = len(stack) | |

stack.append(v) | |

boundaries.append(index[v]) | |

to_do.append(('POSTVISIT', v)) | |

to_do.extend([('VISITEDGE', w) for w in edges[v]]) | |

elif operation_type == 'VISITEDGE': | |

if v not in index: | |

to_do.append(('VISIT', v)) | |

elif v not in identified: | |

while index[v] < boundaries[-1]: | |

boundaries.pop() | |

else: | |

# operation_type == 'POSTVISIT' | |

if boundaries[-1] == index[v]: | |

boundaries.pop() | |

scc = set(stack[index[v]:]) | |

del stack[index[v]:] | |

identified.update(scc) | |

yield scc |