Add a stronglyConnectedComponents() function.

Add a stronglyConnectedComponents() function.

R=lrn@google.com

Committed: https://github.com/dart-lang/collection/commit/8f9500cbcf5bbc32b8b7625595a8767bc54f0cb0

[nweiz, 2016-06-15 20:23:37]

nweiz@google.com changed reviewers:
+ lrn@google.com

[Lasse Reichstein Nielsen, 2016-06-16 08:21:33]

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart
File lib/src/functions.dart (right):

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:149: /// edges from each key to the values associated
with that key.
associated with that key -> that the key maps to.
(maybe).

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:153: /// but `{"a": ["b"], "b": []}` is.
Emphasize that this isn't checked, but if it fails to be satisfied, the function
may fail. 
It means that failing to be valid might show up as a null access error instead
of a nice argument error.

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:163: var onStack = new Set/*<T>*/();
You are using linked-hash-maps and -sets. The order isn't important, so using
unlinked hash-map/-set will be more efficient.

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:179: lowLinks[vertex] = math.min(lowLinks[vertex],
lowLinks[successor]);
It annoys me to have two identical lines in separate branches, but I can't find
a better way to write it. :(

https://codereview.chromium.org/2069253002/diff/1/test/functions_test.dart
File test/functions_test.dart (right):

https://codereview.chromium.org/2069253002/diff/1/test/functions_test.dart#ne...
test/functions_test.dart:188: });
Also test with singleton graphs:  {"a":[]} and {"a":["a"]}
Maybe even two-element graphs: 
{"a":["b"],"b":["a"]} and {"a":[""],"b":["a"]}

https://codereview.chromium.org/2069253002/diff/1/test/functions_test.dart#ne...
test/functions_test.dart:235: test("always returns components in topological
order", () {
You are checking for a specific topological ordering here, there are more
possible topological orderings of the connected components of that graph. 

I don't think it's viable to specify which topological ordering is actually
picked. It depends on the iteration order of the keys and the order of the edges
for each key, both properties that are artificial wrt. the abstract graph
represented by the map. The final ordering is pretty much an accident of
implementation.

So, maybe just test that the components are correct, independent of order, and
that the result is topologically ordered, by testing that for each edge, the
component of the start vertex occurs earlier than the component of the end
vertex in the result.

That avoids testing for a specific ordering.

Alternatively, don't promise topological ordering at all. That allows you to
change the algorithm to something completely different in the future without
breaking tests. (Unless you actually need the topological ordering).

[nweiz, 2016-06-20 21:19:38]

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart
File lib/src/functions.dart (right):

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:149: /// edges from each key to the values associated
with that key.
On 2016/06/16 08:21:33, Lasse Reichstein Nielsen wrote:
> associated with that key -> that the key maps to.
> (maybe).

Done.

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:153: /// but `{"a": ["b"], "b": []}` is.
On 2016/06/16 08:21:33, Lasse Reichstein Nielsen wrote:
> Emphasize that this isn't checked, but if it fails to be satisfied, the
function
> may fail. 
> It means that failing to be valid might show up as a null access error instead
> of a nice argument error.

Done.

https://codereview.chromium.org/2069253002/diff/1/lib/src/functions.dart#newc...
lib/src/functions.dart:163: var onStack = new Set/*<T>*/();
On 2016/06/16 08:21:33, Lasse Reichstein Nielsen wrote:
> You are using linked-hash-maps and -sets. The order isn't important, so using
> unlinked hash-map/-set will be more efficient.

Done.

https://codereview.chromium.org/2069253002/diff/1/test/functions_test.dart
File test/functions_test.dart (right):

https://codereview.chromium.org/2069253002/diff/1/test/functions_test.dart#ne...
test/functions_test.dart:188: });
On 2016/06/16 08:21:33, Lasse Reichstein Nielsen wrote:
> Also test with singleton graphs:  {"a":[]} and {"a":["a"]}
> Maybe even two-element graphs: 
> {"a":["b"],"b":["a"]} and {"a":[""],"b":["a"]}
> 

Done.

https://codereview.chromium.org/2069253002/diff/1/test/functions_test.dart#ne...
test/functions_test.dart:235: test("always returns components in topological
order", () {
On 2016/06/16 08:21:33, Lasse Reichstein Nielsen wrote:
> You are checking for a specific topological ordering here, there are more
> possible topological orderings of the connected components of that graph. 
> 
> I don't think it's viable to specify which topological ordering is actually
> picked. It depends on the iteration order of the keys and the order of the
edges
> for each key, both properties that are artificial wrt. the abstract graph
> represented by the map. The final ordering is pretty much an accident of
> implementation.
> 
> So, maybe just test that the components are correct, independent of order, and
> that the result is topologically ordered, by testing that for each edge, the
> component of the start vertex occurs earlier than the component of the end
> vertex in the result.
> 
> That avoids testing for a specific ordering.

It's a noble goal to try to preserve the invariant that all tests will pass for
all valid implementations of the code in question, but there's a point where
that becomes impractical. In this case, it would be a lot of effort to
automatically verify that the sets are in *a* topological order. On the other
hand, it's easy to verify by hand that a given order is topological, so if the
implementation changes it'll be easy to update this test and manually ensure
that the result is still correct.

> Alternatively, don't promise topological ordering at all. That allows you to
> change the algorithm to something completely different in the future without
> breaking tests. (Unless you actually need the topological ordering).

It is important for my use case that this be topological.

[nweiz, 2016-06-20 21:19:39]

Code review changes

[Lasse Reichstein Nielsen, 2016-06-23 14:44:03]

lgtm

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart
File lib/src/functions.dart (right):

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:106: /// Returns the [transitive closure][] of [graph].
Consider changing "Returns" to "Computes".
The line is fairly redundant with a function declared as "...
transitiveClosure(... graph)".

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:111: /// from each key to the values that the key maps
to.
Maybe even:
   with a vertex for each key and edges the vertex to the vertices it maps to.

Or not. I can't decide if it's better, but I'm trying to not mix abstraction
levels.

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:145: /// Returns the [strongly connected components][] of
[graph], in topological
Also consider Returns -> Computes.

(Because I just don't like "returns" in the first line of function
descriptions).

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:151: /// from each key to the values that the key maps
to.
Whatever you do above, do the same here.

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:152: ///
Maybe add a comment saying that the graph modulo its strongly connected
components is guaranteed to be a directed acyclic graph, so topological ordering
is possible. 
(But use words that users understand :)

https://codereview.chromium.org/2069253002/diff/20001/test/functions_test.dart
File test/functions_test.dart (right):

https://codereview.chromium.org/2069253002/diff/20001/test/functions_test.dar...
test/functions_test.dart:205: test("returns individual vertices for a tree", ()
{
At least document here that this is the expected topological ordering, and if
the ordering changes to another topological ordering, the test needs to be
updated.

[nweiz, 2016-06-23 20:51:54]

Code review changes

[nweiz, 2016-06-23 20:52:58]

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart
File lib/src/functions.dart (right):

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:106: /// Returns the [transitive closure][] of [graph].
On 2016/06/23 14:44:02, Lasse Reichstein Nielsen wrote:
> Consider changing "Returns" to "Computes".
> The line is fairly redundant with a function declared as "...
> transitiveClosure(... graph)".

I think the fact that "transitive closure" is a link is a pretty substantial
difference.

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:111: /// from each key to the values that the key maps
to.
On 2016/06/23 14:44:02, Lasse Reichstein Nielsen wrote:
> Maybe even:
>    with a vertex for each key and edges the vertex to the vertices it maps to.
> 
> Or not. I can't decide if it's better, but I'm trying to not mix abstraction
> levels.

I think that's less clear; it's still kind of mixing levels because it's
technically the keys that map to values, not the vertices.

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:145: /// Returns the [strongly connected components][] of
[graph], in topological
On 2016/06/23 14:44:02, Lasse Reichstein Nielsen wrote:
> Also consider Returns -> Computes.
> 
> (Because I just don't like "returns" in the first line of function
> descriptions).

It's not explicitly mandated, but the documentation guide includes several
function descriptions starting with "Returns":
https://www.dartlang.org/effective-dart/documentation/

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:151: /// from each key to the values that the key maps
to.
On 2016/06/23 14:44:03, Lasse Reichstein Nielsen wrote:
> Whatever you do above, do the same here.

Acknowledged.

https://codereview.chromium.org/2069253002/diff/20001/lib/src/functions.dart#...
lib/src/functions.dart:152: ///
On 2016/06/23 14:44:02, Lasse Reichstein Nielsen wrote:
> Maybe add a comment saying that the graph modulo its strongly connected
> components is guaranteed to be a directed acyclic graph, so topological
ordering
> is possible. 
> (But use words that users understand :)

I think that's more complex than most users would understand. Those who care can
pretty easily prove it to themselves.

https://codereview.chromium.org/2069253002/diff/20001/test/functions_test.dart
File test/functions_test.dart (right):

https://codereview.chromium.org/2069253002/diff/20001/test/functions_test.dar...
test/functions_test.dart:205: test("returns individual vertices for a tree", ()
{
On 2016/06/23 14:44:03, Lasse Reichstein Nielsen wrote:
> At least document here that this is the expected topological ordering, and if
> the ordering changes to another topological ordering, the test needs to be
> updated.

Done.

[nweiz, 2016-06-23 20:53:13]

Description was changed from

==========
Add a stronglyConnectedComponents() function.
==========

to

==========
Add a stronglyConnectedComponents() function.

R=lrn@google.com

Committed:
https://github.com/dart-lang/collection/commit/8f9500cbcf5bbc32b8b7625595a876...
==========

[nweiz, 2016-06-23 20:53:14]

Committed patchset #3 (id:40001) manually as
8f9500cbcf5bbc32b8b7625595a8767bc54f0cb0 (presubmit successful).