search

dart-lang / collection

The collection package for Dart contains a number of separate libraries with utility functions and classes that makes working with collections easier.
https://pub.dev/packages/collection
BSD 3-Clause "New" or "Revised" License
386 stars 87 forks source link

Add transitive reduction to the functions library #335

Closed osaxma closed 9 months ago

osaxma commented 9 months ago

This PR adds transitive reduction to the functions library.

I copied and then modified the existing transitiveClosure function to reduce the transitive connections instead of flattening them. Similarly for tests, they are the same as the transitive closure ones, but the input and expected results were swapped (where appropriate).

Contribution guidelines:
- See our [contributor guide](https://github.com/dart-lang/.github/blob/main/CONTRIBUTING.md) for general expectations for PRs. - Larger or significant changes should be discussed in an issue before creating a PR. - Contributions to our repos should follow the [Dart style guide](https://dart.dev/guides/language/effective-dart) and use `dart format`. - Most changes should add an entry to the changelog and may need to [rev the pubspec package version](https://github.com/dart-lang/sdk/wiki/External-Package-Maintenance#making-a-change). - Changes to packages require [corresponding tests](https://github.com/dart-lang/.github/blob/main/CONTRIBUTING.md#Testing). Note that many Dart repos have a weekly cadence for reviewing PRs - please allow for some latency before initial review feedback.
osaxma commented 9 months ago

I think I rushed in submitting this as it doesn't handle the simple case where a path has more than two edges (added a failing test for that).

I will re-submit another PR once I get a working version that works with any type of graphs.

osaxma commented 8 months ago

In case anyone gets here through search, here is an implementation that works with List<SomeNode>. I don't feel it's a good fit for the functions library since it does not work with cycles and it doesn't take Map<T, Iterable<T>> as graph similar to the rest of the graph functions.