Open mjtalbot opened 4 years ago
@luigi-rosso, got an implementation of this using Tarjan's algorithm going.
the nice guys here actually implemented the algorithm in a pretty portable way: (https://github.com/dart-lang/graphs - BSD license)
class TarjansDependencySorter extends DependencySorter {
HashSet<ActorComponent> _cycleNodes;
HashSet<ActorComponent> get cycleNodes => _cycleNodes;
TarjansDependencySorter() {
_perm = HashSet<ActorComponent>();
_temp = HashSet<ActorComponent>();
_cycleNodes = HashSet<ActorComponent>();
}
@override
List<ActorComponent> sort(ActorComponent root) {
_order = <ActorComponent>[];
if (visit(root)) {
return _order;
} else {
_perm.clear();
_temp.clear();
_cycleNodes.clear();
_order.clear();
// returns a list of cycles, which themselves
var cycles = stronglyConnectedComponents<ActorComponent>(
[root], (ActorComponent node) => node.dependents);
cycles.forEach((cycle) {
// looks like the algorithm places each node in
// a single item list if its not part of a cycle
if (cycle.length > 1) {
cycle.forEach((cycleMember) {
_cycleNodes.add(cycleMember);
});
}
});
// visit again, this time skip any nodes that we know are part of a cycle
visit(root, cycleNodes: _cycleNodes);
}
return _order;
}
}
feels a bit cleaner perhaps
YES! This is awesome.
I made two minor tweaks:
Renamed the test file to *_test.dart so that VSCode and the test cli find it (seems to want the file to end in _test.dart).
Test directory "test" does not appear to contain any test files.
Test files must be in that directory and end with the pattern "_test.dart".
Moved the cycles tracking out of DependencySorter completely to keep it a little cleaner/faster (no need to instance and pass cycles hash set around prematurely).
Couple of outstanding questions:
tests: Manually tested drawing the penguin using this dependency sorter. Added some tests to keep track of some scenarios I've been trying to make sure work. not sure if we want to fit tests in like this
To run the tests
pub run test test/test_dependency_sorter.dart
does the trick.Some gotchas: the order that the nodes are evaluated is not the same as in the original Dependency Sorter
Alternatives: this looks pretty promising really. looks like a an established algorithm to find all cycles: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm. Using this we could simply use the current algorithm, and if it detects cycles, find all nodes with cycles and then re run the current algorithm, skipping over any nodes that are part of a cycle. We'll of course lose a little bit