diff options
Diffstat (limited to 'third_party/digraph.py')
-rw-r--r-- | third_party/digraph.py | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/third_party/digraph.py b/third_party/digraph.py new file mode 100644 index 000000000..4fafcbd46 --- /dev/null +++ b/third_party/digraph.py @@ -0,0 +1,67 @@ +# Copyright (c) 2013 Mark Dickinson +# +# 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 |