Added Alternative DependencySorter to deal with cycles

[mjtalbot]

Couple of outstanding questions:

• would we want to activate this straight away, right now I've not committed using this (and essentially replacing the previous Sorter)
• this will make sure we have an ordered list of ActorComponents, but its of course not alerting anything that we are missing components if there were cycles. Something else will need to be responsible for that
• the alternative sounds kinda better

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

[mjtalbot]

@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

[luigi-rosso]

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).