paths method

List<List<T>> paths(
  1. T start,
  2. T target
)

Returns a list containing all paths connecting start and target.

Implementation

List<List<T>> paths(T start, T target) {
  final pathList = <List<T>>[];
  // // Retrieve vertex tree.
  // final tree = mappedTree(start);
  // if (tree.containsKey(target)) {
  //   for (final branch in tree[target]!) {
  //     pathList.add(<T>[start, ...branch]);
  //   }
  // }
  final tree = <Set<T>>[];
  for (final connected in edges(start)) {
    if (connected == target) {
      // Add to list of paths
      pathList.add([start, target]);
    } else if (connected == start) {
      // Do not follow self-loops.
      continue;
    } else {
      // Store first branches of tree.
      tree.add({connected});
    }
  }

  // There is no other path (except for self-loops from `start` to `start`).
  if (tree.isNotEmpty) {
    var startIndex = 0;
    var endIndex = 0;
    var length = tree.length;
    do {
      endIndex = tree.length;
      for (var i = startIndex; i < endIndex; ++i) {
        final path = tree[i];
        for (final vertex in edges(path.last)) {
          // Discard walks which reach the same (inner) vertex twice.
          // Note: Each path starts with [start] even though it is not
          // listed!
          if (path.contains(vertex) || path.contains(start)) {
            continue;
          } else {
            if (vertex == target) {
              // Store detected path:
              pathList.add([start, ...path, vertex]);
            } else {
              // Continue growing tree.
              tree.add({...path, vertex});
              length++;
            }
          }
        }
      }
      startIndex = endIndex;
    } while (endIndex < length);
  }
  return pathList;
}