Add a stronglyConnectedComponents() function.
R=lrn@google.com
Review URL: https://codereview.chromium.org//2069253002 .
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 90312a3..dd5bc2c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,8 @@
+## 1.9.0
+
+* Add a top-level `stronglyConnectedComponents()` function that returns the
+ strongly connected components in a directed graph.
+
## 1.8.0
* Add a top-level `mapMap()` function that works like `Iterable.map()` on a
diff --git a/lib/src/functions.dart b/lib/src/functions.dart
index 9c973b8..6e5bb0a 100644
--- a/lib/src/functions.dart
+++ b/lib/src/functions.dart
@@ -2,6 +2,9 @@
// 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:math' as math;
+import 'dart:collection';
+
import 'utils.dart';
// TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key]
@@ -104,12 +107,13 @@
///
/// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure
///
-/// This interprets [graph] as a directed graph with a vertex for each key and
-/// edges from each key to the values associated with that key.
+/// Interprets [graph] as a directed graph with a vertex for each key and edges
+/// from each key to the values that the key maps to.
///
/// Assumes that every vertex in the graph has a key to represent it, even if
-/// that vertex has no outgoing edges. For example, `{"a": ["b"]}` is not valid,
-/// but `{"a": ["b"], "b": []}` is.
+/// that vertex has no outgoing edges. This isn't checked, but if it's not
+/// satisfied, the function may crash or provide unexpected output. For example,
+/// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is.
Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/(
Map<dynamic/*=T*/, Iterable/*<T>*/> graph) {
// This uses [Warshall's algorithm][], modified not to add a vertex from each
@@ -137,3 +141,68 @@
return result;
}
+
+/// Returns the [strongly connected components][] of [graph], in topological
+/// order.
+///
+/// [strongly connected components]: https://en.wikipedia.org/wiki/Strongly_connected_component
+///
+/// Interprets [graph] as a directed graph with a vertex for each key and edges
+/// from each key to the values that the key maps to.
+///
+/// Assumes that every vertex in the graph has a key to represent it, even if
+/// that vertex has no outgoing edges. This isn't checked, but if it's not
+/// satisfied, the function may crash or provide unexpected output. For example,
+/// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is.
+List<Set/*<T>*/> stronglyConnectedComponents/*<T>*/(
+ Map<dynamic/*=T*/, Iterable/*<T>*/> graph) {
+ // This uses [Tarjan's algorithm][].
+ //
+ // [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
+ var index = 0;
+ var stack = /*<T>*/[];
+ var result = /*<Set<T>>*/[];
+
+ // The order of these doesn't matter, so we use un-linked implementations to
+ // avoid unnecessary overhead.
+ var indices = new HashMap/*<T, int>*/();
+ var lowLinks = new HashMap/*<T, int>*/();
+ var onStack = new HashSet/*<T>*/();
+
+ strongConnect(/*=T*/ vertex) {
+ indices[vertex] = index;
+ lowLinks[vertex] = index;
+ index++;
+
+ stack.add(vertex);
+ onStack.add(vertex);
+
+ for (var successor in graph[vertex]) {
+ if (!indices.containsKey(successor)) {
+ strongConnect(successor);
+ lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]);
+ } else if (onStack.contains(successor)) {
+ lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]);
+ }
+ }
+
+ if (lowLinks[vertex] == indices[vertex]) {
+ var component = new Set/*<T>*/();
+ var/*=T*/ neighbor;
+ do {
+ neighbor = stack.removeLast();
+ onStack.remove(neighbor);
+ component.add(neighbor);
+ } while (neighbor != vertex);
+ result.add(component);
+ }
+ }
+
+ for (var vertex in graph.keys) {
+ if (!indices.containsKey(vertex)) strongConnect(vertex);
+ }
+
+ // Tarjan's algorithm produces a reverse-topological sort, so we reverse it to
+ // get a normal topological sort.
+ return result.reversed.toList();
+}
diff --git a/pubspec.yaml b/pubspec.yaml
index 06c2cb7..f5c8f9f 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.8.0
+version: 1.9.0
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: https://www.github.com/dart-lang/collection
diff --git a/test/functions_test.dart b/test/functions_test.dart
index 4d928bf..ab56c3b 100644
--- a/test/functions_test.dart
+++ b/test/functions_test.dart
@@ -181,4 +181,97 @@
}));
});
});
+
+ group("stronglyConnectedComponents()", () {
+ test("returns an empty list for an empty graph", () {
+ expect(stronglyConnectedComponents({}), isEmpty);
+ });
+
+ test("returns one set for a singleton graph", () {
+ expect(stronglyConnectedComponents({"a": []}),
+ equals([new Set.from(["a"])]));
+ });
+
+ test("returns two sets for a two-element tree", () {
+ expect(stronglyConnectedComponents({"a": ["b"], "b": []}),
+ equals([new Set.from(["a"]), new Set.from(["b"])]));
+ });
+
+ test("returns one set for a two-element loop", () {
+ expect(stronglyConnectedComponents({"a": ["b"], "b": ["a"]}),
+ equals([new Set.from(["a", "b"])]));
+ });
+
+ test("returns individual vertices for a tree", () {
+ expect(stronglyConnectedComponents({
+ "foo": ["bar"],
+ "bar": ["baz", "bang"],
+ "baz": ["qux"],
+ "bang": ["zap"],
+ "qux": [],
+ "zap": []
+ }), equals([
+ // This is expected to return *a* topological ordering, but this isn't
+ // the only valid one. If the function implementation changes in the
+ // future, this test may need to be updated.
+ new Set.from(["foo"]),
+ new Set.from(["bar"]),
+ new Set.from(["bang"]),
+ new Set.from(["zap"]),
+ new Set.from(["baz"]),
+ new Set.from(["qux"])
+ ]));
+ });
+
+ test("returns a single set for a fully cyclic graph", () {
+ expect(stronglyConnectedComponents({
+ "foo": ["bar"],
+ "bar": ["baz"],
+ "baz": ["bang"],
+ "bang": ["foo"]
+ }), equals([new Set.from(["foo", "bar", "baz", "bang"])]));
+ });
+
+ test("returns separate sets for each strongly connected component", () {
+ // https://en.wikipedia.org/wiki/Strongly_connected_component#/media/File:Scc.png
+ expect(stronglyConnectedComponents({
+ "a": ["b"],
+ "b": ["c", "e", "f"],
+ "c": ["d", "g"],
+ "d": ["c", "h"],
+ "e": ["a", "f"],
+ "f": ["g"],
+ "g": ["f"],
+ "h": ["g", "d"]
+ }), equals([
+ // This is expected to return *a* topological ordering, but this isn't
+ // the only valid one. If the function implementation changes in the
+ // future, this test may need to be updated.
+ new Set.from(["a", "b", "e"]),
+ new Set.from(["c", "d", "h"]),
+ new Set.from(["f", "g"]),
+ ]));
+ });
+
+ test("always returns components in topological order", () {
+ expect(stronglyConnectedComponents({
+ "bar": ["baz", "bang"],
+ "zap": [],
+ "baz": ["qux"],
+ "qux": [],
+ "foo": ["bar"],
+ "bang": ["zap"]
+ }), equals([
+ // This is expected to return *a* topological ordering, but this isn't
+ // the only valid one. If the function implementation changes in the
+ // future, this test may need to be updated.
+ new Set.from(["foo"]),
+ new Set.from(["bar"]),
+ new Set.from(["bang"]),
+ new Set.from(["zap"]),
+ new Set.from(["baz"]),
+ new Set.from(["qux"])
+ ]));
+ });
+ });
}
