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).
• If a target vertex is provided the function returns as soon as a branch reaching target is added to the tree.

Implementation

List<Set<T>> tree(T start, [T? target]) {
  final result = <Set<T>>[];

  for (final connected in edges(start)) {
    result.add({connected});
    if (connected == target) {
      return result;
    }
  }

  if (result.isEmpty) return result;

  var startIndex = 0;
  var endIndex = 0;
  var length = result.length;
  do_loop:
  do {
    endIndex = result.length;
    for (var i = startIndex; i < endIndex; ++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});
          length++;
        }
        if (vertex == target) break do_loop;
      }
    }
    startIndex = endIndex;
  } while (endIndex < length);
  return result;
}