tree method

List<Set<T>> tree(T start, [ T? target ])

Returns a tree-like structure with start as root vertex.

• Each entry of type Set<T> represents a path (the start vertex is omitted).

Implementation

List<Set<T>> tree(T start, [T? target]) {
  final result = <Set<T>>[
    for (final connected in edges(start)) {connected}
  ];

  if (result.isEmpty) return result;

  var startIndexOld = 0;
  var startIndexNew = 0;
  do {
    startIndexNew = result.length;
    for (var i = startIndexOld; i < startIndexNew; ++i) {
      final path = result[i];
      for (final vertex in edges(path.last)) {
        // Discard walks which reach the same (inner) vertex twice.
        // Each path starts with [start] even though it is not
        // listed!
        if (path.contains(vertex) || path.contains(start)) {
          continue;
        } else {
          result.add({...path, vertex});
        }
        if (vertex == target) break;
      }
    }
    startIndexOld = startIndexNew;
  } while (startIndexNew < result.length);
  return result;
}