path method

List<T> path(T start, T target)

Returns the shortest path from start to target.

• Returns an empty list if target is not reachable from start.

Implementation

List<T> path(T start, T target) {
  final tree = <Set<T>>[];
  for (final connected in edges(start)) {
    if (connected == target) {
      // Return early if start is connected to target.
      return <T>[start, target];
    } else if (connected == start) {
      // Do not follow self-loops.
      continue;
    } else {
      // Store first branches of tree.
      tree.add({connected});
    }
  }

  // No path detected.
  if (tree.isEmpty) return <T>[];

  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) {
            // Shortest path found!
            return [start, ...path, vertex];
          } else {
            // Continue growing tree.
            tree.add({...path, vertex});
            length++;
          }
        }
      }
    }
    startIndex = endIndex;
  } while (endIndex < length);
  // No path detected:
  return <T>[];
}