Iterable Function()

in lib/src/strongly_connected_components.dart [34:78]

• 41 lines of code
• 8 McCabe index (conditional complexity)

  Iterable<T> Function(T) edges, {
  bool Function(T, T)? equals,
  int Function(T)? hashCode,
}) {
  final result = <List<T>>[];
  final lowLinks = HashMap<T, int>(equals: equals, hashCode: hashCode);
  final indexes = HashMap<T, int>(equals: equals, hashCode: hashCode);
  final onStack = HashSet<T>(equals: equals, hashCode: hashCode);

  final nonNullEquals = equals ?? _defaultEquals;

  var index = 0;
  var lastVisited = Queue<T>();

  void strongConnect(T node) {
    indexes[node] = index;
    var lowLink = lowLinks[node] = index;
    index++;
    lastVisited.addLast(node);
    onStack.add(node);
    for (final next in edges(node)) {
      if (!indexes.containsKey(next)) {
        strongConnect(next);
        lowLink = lowLinks[node] = min(lowLink, lowLinks[next]!);
      } else if (onStack.contains(next)) {
        lowLink = lowLinks[node] = min(lowLink, indexes[next]!);
      }
    }
    if (lowLinks[node] == indexes[node]) {
      final component = <T>[];
      T next;
      do {
        next = lastVisited.removeLast();
        onStack.remove(next);
        component.add(next);
      } while (!nonNullEquals(next, node));
      result.add(component);
    }
  }

  for (final node in nodes) {
    if (!indexes.containsKey(node)) strongConnect(node);
  }
  return result;
}