graphs/lib/src/shortest_path.dart

// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

import 'dart:collection';

/// Returns the shortest path from [start] to [target] given the directed
/// edges of a graph provided by [edges].
///
/// If [start] `==` [target], an empty [List] is returned and [edges] is never
/// called.
///
/// [start], [target] and all values returned by [edges] must not be `null`.
/// If asserts are enabled, an [AssertionError] is raised if these conditions
/// are not met. If asserts are not enabled, violations result in undefined
/// behavior.
///
/// If [equals] is provided, it is used to compare nodes in the graph. If
/// [equals] is omitted, the node's own [Object.==] is used instead.
///
/// Similarly, if [hashCode] is provided, it is used to produce a hash value
/// for nodes to efficiently calculate the return value. If it is omitted, the
/// key's own [Object.hashCode] is used.
///
/// If you supply one of [equals] or [hashCode], you should generally also to
/// supply the other.
List<T> shortestPath<T>(
  T start,
  T target,
  Iterable<T> Function(T) edges, {
  bool equals(T key1, T key2),
  int hashCode(T key),
}) =>
    _shortestPaths<T>(
      start,
      edges,
      target: target,
      equals: equals,
      hashCode: hashCode,
    )[target];

/// Returns a [Map] of the shortest paths from [start] to all of the nodes in
/// the directed graph defined by [edges].
///
/// All return values will contain the key [start] with an empty [List] value.
///
/// [start] and all values returned by [edges] must not be `null`.
/// If asserts are enabled, an [AssertionError] is raised if these conditions
/// are not met. If asserts are not enabled, violations result in undefined
/// behavior.
///
/// If [equals] is provided, it is used to compare nodes in the graph. If
/// [equals] is omitted, the node's own [Object.==] is used instead.
///
/// Similarly, if [hashCode] is provided, it is used to produce a hash value
/// for nodes to efficiently calculate the return value. If it is omitted, the
/// key's own [Object.hashCode] is used.
///
/// If you supply one of [equals] or [hashCode], you should generally also to
/// supply the other.
Map<T, List<T>> shortestPaths<T>(
  T start,
  Iterable<T> Function(T) edges, {
  bool equals(T key1, T key2),
  int hashCode(T key),
}) =>
    _shortestPaths<T>(
      start,
      edges,
      equals: equals,
      hashCode: hashCode,
    );

Map<T, List<T>> _shortestPaths<T>(
  T start,
  Iterable<T> Function(T) edges, {
  T target,
  bool equals(T key1, T key2),
  int hashCode(T key),
}) {
  assert(start != null, '`start` cannot be null');
  assert(edges != null, '`edges` cannot be null');

  final distances = HashMap<T, List<T>>(equals: equals, hashCode: hashCode);
  distances[start] = List(0);

  equals ??= _defaultEquals;
  if (equals(start, target)) {
    return distances;
  }

  final toVisit = ListQueue<T>()..add(start);

  List<T> bestOption;

  while (toVisit.isNotEmpty) {
    final current = toVisit.removeFirst();
    final currentPath = distances[current];
    final currentPathLength = currentPath.length;

    if (bestOption != null && (currentPathLength + 1) >= bestOption.length) {
      // Skip any existing `toVisit` items that have no chance of being
      // better than bestOption (if it exists)
      continue;
    }

    for (var edge in edges(current)) {
      assert(edge != null, '`edges` cannot return null values.');
      final existingPath = distances[edge];

      assert(existingPath == null ||
          existingPath.length <= (currentPathLength + 1));

      if (existingPath == null) {
        final newOption = List<T>(currentPathLength + 1)
          ..setRange(0, currentPathLength, currentPath)
          ..[currentPathLength] = edge;

        if (equals(edge, target)) {
          assert(bestOption == null || bestOption.length > newOption.length);
          bestOption = newOption;
        }

        distances[edge] = newOption;
        if (bestOption == null || bestOption.length > newOption.length) {
          // Only add a node to visit if it might be a better path to the
          // target node
          toVisit.add(edge);
        }
      }
    }
  }

  return distances;
}

bool _defaultEquals(a, b) => a == b;