findPathExclusive<T extends E> method

  1. @override
Path<T> findPathExclusive<T extends E>(
  1. WalkableBase<T> graph,
  2. T start,
  3. Goal<T> goal, {
  4. Tracer<T>? tracer,
})
override

Returns a path in graph from start to a node that satisfies goal.

Unlike findPath, this method does not check if the goal is initially satisfied by the start node, although it may be satisfied by the start node if it is an eventual successor of itself (i.e. a cycle in the graph).

If no path can be found, Path.notFound is returned.

A node will never be included in the path more than once, as determined by Object.== on the node, unless the source node is also a successor of itself, in which case it will be included twice (once at the beginning and once at the end), otherwise it will only be included at the start.

Tracing

May provide a tracer to capture finer-detail events during the traversal.

If omitted, no tracing is performed.

Example

final graph = Graph<int>();
graph.addEdge(1, 2);
graph.addEdge(2, 1);

final immediate = depthFirst.findPath(graph, 1, Goal.node(1));
print(immediate); // Path([1])

final cycle = depthFirst.findPathExclusive(graph, 1, Goal.node(1));
print(cycle); // Path([1, 2, 1])

Implementation

@override
Path<T> findPathExclusive<T extends E>(
  WalkableBase<T> graph,
  T start,
  Goal<T> goal, {
  Tracer<T>? tracer,
}) {
  // The frontier is a queue of nodes to visit, starting with the start node.
  final search = graph.asUnweighted();
  final parents = IndexMap<T, int>()..[start] = -1;

  // Which node we are currently visiting.
  var i = 0;

  do {
    final node = parents.entryAt(i);
    tracer?.onVisit(node.key);
    for (final successor in search.successors(node.key)) {
      if (goal.success(successor)) {
        final path = _reversePath(
          parents,
          (p) => p,
          i,
        );
        path.add(successor);
        return Path(path);
      }
      final next = parents.entryOf(successor);
      if (next.isAbsent) {
        next.setOrUpdate(i);
      }
    }
    i += 1;
  } while (i < parents.length);

  return Path.notFound;
}