| // Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import 'dart:collection'; |
| import 'dart:math' show min; |
| |
| /// Finds the strongly connected components of a directed graph using Tarjan's |
| /// algorithm. |
| /// |
| /// The result will be a valid reverse topological order ordering of the |
| /// strongly connected components. Components further from a root will appear in |
| /// the result before the components which they are connected to. |
| /// |
| /// Nodes within a strongly connected component have no ordering guarantees, |
| /// except that if the first value in [nodes] is a valid root, and is contained |
| /// in a cycle, it will be the last element of that cycle. |
| /// |
| /// [nodes] must contain at least a root of every tree in the graph if there are |
| /// disjoint subgraphs but it may contain all nodes in the graph if the roots |
| /// are not known. |
| /// |
| /// If [equals] is provided, it is used to compare nodes in the graph. If |
| /// [equals] is omitted, the node's own [Object.==] is used instead. |
| /// |
| /// Similarly, if [hashCode] is provided, it is used to produce a hash value |
| /// for nodes to efficiently calculate the return value. If it is omitted, the |
| /// key's own [Object.hashCode] is used. |
| /// |
| /// If you supply one of [equals] or [hashCode], you should generally also to |
| /// supply the other. |
| List<List<T>> stronglyConnectedComponents<T>( |
| Iterable<T> nodes, |
| Iterable<T> Function(T) edges, { |
| bool equals(T key1, T key2), |
| int hashCode(T key), |
| }) { |
| final result = <List<T>>[]; |
| final lowLinks = HashMap<T, int>(equals: equals, hashCode: hashCode); |
| final indexes = HashMap<T, int>(equals: equals, hashCode: hashCode); |
| final onStack = HashSet<T>(equals: equals, hashCode: hashCode); |
| |
| equals ??= _defaultEquals; |
| |
| var index = 0; |
| var lastVisited = Queue<T>(); |
| |
| void strongConnect(T node) { |
| indexes[node] = index; |
| lowLinks[node] = index; |
| index++; |
| lastVisited.addLast(node); |
| onStack.add(node); |
| // ignore: omit_local_variable_types |
| for (final T next in edges(node) ?? const []) { |
| if (!indexes.containsKey(next)) { |
| strongConnect(next); |
| lowLinks[node] = min(lowLinks[node], lowLinks[next]); |
| } else if (onStack.contains(next)) { |
| lowLinks[node] = min(lowLinks[node], indexes[next]); |
| } |
| } |
| if (lowLinks[node] == indexes[node]) { |
| final component = <T>[]; |
| T next; |
| do { |
| next = lastVisited.removeLast(); |
| onStack.remove(next); |
| component.add(next); |
| } while (!equals(next, node)); |
| result.add(component); |
| } |
| } |
| |
| for (final node in nodes) { |
| if (!indexes.containsKey(node)) strongConnect(node); |
| } |
| return result; |
| } |
| |
| bool _defaultEquals(a, b) => a == b; |