isInWithCost method

(bool, double) isInWithCost(
  1. WeightedWalkable<T> graph,
  2. double cost
)

Returns whether the path is valid and has a total cost of cost.

The result is a tuple of a boolean and a double, where the boolean is true if the path is valid and the cost is equal to cost, and false otherwise. The double is the actual total cost of the path, or double.infinity if the path is not valid.

A path is considered valid if it isFound and:

  • Each node in the path is a direct successor of the previous node, or
  • The path is a single node that is a direct successor of itself or
  • The path is a single node that is a root node.

and the total cost of the path is equal to cost.

If the path is notFound, this method returns false.

Note

Checking for a root node (i.e. from a single-node path) is a potentially expensive operation, as it could require checking every node in the graph. Either avoid using this method with single-node paths, or ensure that the graph implementation is optimized for this operation (e.g. has constant-time lookup for roots, such as AdjacencyListGraph or GridWalkable on a default Grid implementation).

Implementation

(bool, double) isInWithCost(WeightedWalkable<T> graph, double cost) {
  if (isNotFound) {
    return (false, double.infinity);
  }

  // Edge-case: A path to yourself.
  if (nodes.length == 1) {
    // Self-loop:
    if (graph.successors(start).any((e) => e.$1 == start)) {
      return (cost == 0.0, 0.0);
    }

    // If not, it's still possible it's a path to itself without a loop.
    // This is a potentially expensive operation, though if you're asking if
    // a node is a path to itself returning 'false' doesn't make any sense.
    return (graph.roots.contains(start) && cost == 0.0, 0.0);
  }

  var totalCost = 0.0;
  for (var i = 0; i < nodes.length - 1; i++) {
    final node = nodes[i];
    final next = nodes[i + 1];
    final moveCost =
        graph.successors(node).firstWhere((e) => e.$1 == next).$2;
    if (moveCost == double.infinity) {
      return (false, double.infinity);
    }
    totalCost += moveCost;
  }

  return (totalCost == cost, totalCost);
}