findBestPathExclusive<T extends E> method

  1. @override
(Path<T>, double) findBestPathExclusive<T extends E>(
  1. WeightedWalkable<T> graph,
  2. T start,
  3. Goal<T> goal,
  4. Heuristic<T> heuristic, {
  5. Tracer<T>? tracer,
})
override

Returns an optimal path (and it's total cost) in graph from start to a node that satisfies goal.

Unlike findBestPath, 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 the path is not found, the total cost will be double.infinity.

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.

Impassable Nodes

There are two ways to represent impassable nodes in a graph:

  • Omit the node from the graph entirely, i.e. no edge leads to it;
  • Calculate the weight of the edge to the node as double.infinity.

Tracing

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

If omitted, no tracing is performed.

Example

final graph = WeightedWalkable.from({
  'a': [('b', 1.0), ('c', 2.0)],
  'b': [('c', 3.0)],
  'c': [('a', 4.0)],
});

final (path, cost) = astar.findBestPathExclusive(graph, 'a', Goal.node('d'));
print(path); // Path(['a', 'c', 'd'])
print(cost); // 6.0

Implementation

@override
(Path<T> path, double cost) findBestPathExclusive<T extends E>(
  WeightedWalkable<T> graph,
  T start,
  Goal<T> goal,
  Heuristic<T> heuristic, {
  Tracer<T>? tracer,
}) {
  final parents = IndexMap<T, (int, double)>()..[start] = (0, 0.0);

  var now = Queue<int>()..add(0);
  var later = Queue<int>();
  var flimit = heuristic.estimateTotalCost(start);
  var check = false;

  while (now.isNotEmpty) {
    var fmin = double.maxFinite;
    while (now.isNotEmpty) {
      final index = now.removeFirst();
      final entry = parents.entryAt(index);
      final node = entry.key;
      final (_, g) = entry.value;
      final f = g + heuristic.estimateTotalCost(node);
      if (f > flimit) {
        fmin = math.min(fmin, f);
        later.addLast(index);
        continue;
      }

      tracer?.onVisit(node);
      if (check && goal.success(node) && node != start) {
        final path = _reversePath(parents, (p) => p.$1, index);
        return (Path(path), g);
      }
      check = true;

      for (final (next, weight) in graph.successors(node)) {
        final gSuccessor = g + weight;
        if (gSuccessor >= double.infinity) {
          continue;
        }
        final int iSuccessor;
        switch (parents.entryOf(next)) {
          case final AbsentMapEntry<T, (int, double)> e:
            iSuccessor = e.index;
            e.setOrUpdate((index, gSuccessor));
          case final PresentMapEntry<T, (int, double)> e:
            final (_, gNext) = e.value;
            if (gSuccessor < gNext) {
              iSuccessor = e.index;
              e.setOrUpdate((index, gSuccessor));
            } else {
              // Edge-case: It's a loop back to the same node.
              if (e.key == start && goal.success(start)) {
                // We can't use the primary routine, so let's build a path
                // to the previous ("node") and then add the start node to the
                // path.
                final path = _reversePath(parents, (p) => p.$1, index);
                return (Path(path..add(start)), gSuccessor);
              }
              continue;
            }
        }
        if (!later.remove(iSuccessor)) {
          now.addLast(iSuccessor);
        }
        now.addLast(index);
      }
    }

    // Swap now & later.
    final temp = now;
    now = later;
    later = temp;
    flimit = fmin;
  }

  return (Path.notFound, double.infinity);
}