isIn method

bool isIn(
  1. WalkableBase<T> graph
)

Returns true if this is a valid path in the graph.

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.

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 isIn(WalkableBase<T> graph) {
  if (isNotFound) {
    return false;
  }

  // Edge-case: A path to yourself.
  if (nodes.length == 1) {
    // Self-loop:
    if (graph.successors(start).contains(start)) {
      return true;
    }

    // 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);
  }

  for (var i = 0; i < nodes.length - 1; i++) {
    if (!graph.successors(nodes[i]).contains(nodes[i + 1])) {
      return false;
    }
  }
  return true;
}