aStarSearch<V> function

Iterable<Path<V, num>> aStarSearch<V>({
  1. required Iterable<V> startVertices,
  2. required bool targetPredicate(
    1. V vertex
    ),
  3. required Iterable<V> successorsOf(
    1. V vertex
    ),
  4. required num costEstimate(
    1. V source
    ),
  5. num edgeCost(
    1. V source,
    2. V target
    )?,
  6. bool includeAlternativePaths = false,
  7. StorageStrategy<V>? vertexStrategy,
})

A-Star search algorithm.

See https://en.wikipedia.org/wiki/A*_search_algorithm.

Implementation

Iterable<Path<V, num>> aStarSearch<V>({
  required Iterable<V> startVertices,
  required bool Function(V vertex) targetPredicate,
  required Iterable<V> Function(V vertex) successorsOf,
  required num Function(V source) costEstimate,
  num Function(V source, V target)? edgeCost,
  bool includeAlternativePaths = false,
  StorageStrategy<V>? vertexStrategy,
}) sync* {
  edgeCost = edgeCost ?? constantFunction2(1);
  vertexStrategy = vertexStrategy ?? StorageStrategy.defaultStrategy();

  final states = vertexStrategy.createMap<AStarState<V>>();
  final queue = PriorityQueue<AStarState<V>>(stateCompare);
  for (final vertex in startVertices) {
    final state = AStarState<V>(vertex: vertex, estimate: costEstimate(vertex));
    states[vertex] = state;
    queue.add(state);
  }

  while (queue.isNotEmpty) {
    final sourceState = queue.removeFirst();
    if (sourceState.isObsolete) continue;
    for (final target in successorsOf(sourceState.vertex)) {
      final value = edgeCost(sourceState.vertex, target);
      GraphError.checkPositiveEdgeValue(sourceState.vertex, target, value);
      final total = sourceState.total + value;
      final targetState = states[target];
      if (targetState == null || total < targetState.total) {
        targetState?.isObsolete = true;
        final estimate = total + costEstimate(target);
        final state = AStarState<V>(
          vertex: target,
          value: value,
          total: total,
          estimate: estimate,
        );
        state.predecessors.add(sourceState);
        states[target] = state;
        queue.add(state);
      } else if (total == targetState.total) {
        targetState.predecessors.add(sourceState);
      }
    }
    if (targetPredicate(sourceState.vertex)) {
      if (includeAlternativePaths) {
        yield* createAllShortestPaths(sourceState);
      } else {
        yield createShortestPath(sourceState);
      }
    }
  }
}