cycleWalk method

List<String> cycleWalk(List<String> group)

A shortest closed walk through group starting at its first member, following only edges that exist. The last element points back to the first.

Sorting a group alphabetically and drawing arrows between neighbours used to claim imports that no file declares; a developer following those arrows to decide which import to cut opened the wrong file. In a group of two or more, a walk back to any member always exists.

Implementation

List<String> cycleWalk(List<String> group) {
  if (group.isEmpty) return const [];
  final members = group.toSet();
  final start = group.first;

  final parent = <String, String>{};
  final queue = <String>[start];
  var head = 0;
  while (head < queue.length) {
    final node = queue[head++];
    final targets = (edges[node] ?? const <String>{}).toList()..sort();
    for (final next in targets) {
      if (!members.contains(next)) continue;
      if (next == start) {
        final walk = <String>[];
        for (String? at = node; at != null; at = parent[at]) {
          walk.add(at);
        }
        return walk.reversed.toList();
      }
      if (parent.containsKey(next)) continue;
      parent[next] = node;
      queue.add(next);
    }
  }
  return [start];
}