pkgs/graphs/test/shortest_path_test.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';
import 'dart:math' show Random;

import 'package:graphs/graphs.dart';
import 'package:test/test.dart';

import 'utils/utils.dart';

void main() {
  const graph = <String, List<String>>{
    '1': ['2', '5'],
    '2': ['3'],
    '3': ['4', '5'],
    '4': ['1'],
    '5': ['8'],
    '6': ['7'],
  };

  List<String> readEdges(String key) => graph[key] ?? [];

  List<X> getXValues(X key) => graph[key.value]?.map(X.new).toList() ?? [];

  void singlePathTest(String from, String to, List<String>? expected) {
    test('$from -> $to should be $expected (mapped)', () {
      expect(
        shortestPath<X>(
          X(from),
          X(to),
          getXValues,
          equals: xEquals,
          hashCode: xHashCode,
        )?.map((x) => x.value),
        expected,
      );
    });

    test('$from -> $to should be $expected', () {
      expect(shortestPath(from, to, readEdges), expected);
    });
  }

  void pathsTest(
    String from,
    Map<String, List<String>> expected,
    List<String> nullPaths,
  ) {
    test('paths from $from (mapped)', () {
      final result = shortestPaths<X>(
        X(from),
        getXValues,
        equals: xEquals,
        hashCode: xHashCode,
      ).map((k, v) => MapEntry(k.value, v.map((x) => x.value).toList()));
      expect(result, expected);
    });

    test('paths from $from', () {
      final result = shortestPaths(from, readEdges);
      expect(result, expected);
    });

    for (var entry in expected.entries) {
      singlePathTest(from, entry.key, entry.value);
    }

    for (var entry in nullPaths) {
      singlePathTest(from, entry, null);
    }
  }

  pathsTest('1', {
    '5': ['5'],
    '3': ['2', '3'],
    '8': ['5', '8'],
    '1': [],
    '2': ['2'],
    '4': ['2', '3', '4'],
  }, [
    '6',
    '7',
  ]);

  pathsTest('6', {
    '7': ['7'],
    '6': [],
  }, [
    '1',
  ]);
  pathsTest('7', {'7': []}, ['1', '6']);

  pathsTest('42', {'42': []}, ['1', '6']);

  test('integration test', () {
    // Be deterministic in the generated graph. This test may have to be updated
    // if the behavior of `Random` changes for the provided seed.
    final rnd = Random(1);
    const size = 1000;
    final graph = HashMap<int, List<int>>();

    Iterable<int>? resultForGraph() =>
        shortestPath(0, size - 1, (e) => graph[e] ?? const []);

    void addRandomEdge() {
      final toList = graph.putIfAbsent(rnd.nextInt(size), () => <int>[]);

      final toValue = rnd.nextInt(size);
      if (!toList.contains(toValue)) {
        toList.add(toValue);
      }
    }

    Iterable<int>? result;

    // Add edges until there is a shortest path between `0` and `size - 1`
    do {
      addRandomEdge();
      result = resultForGraph();
    } while (result == null);

    expect(result, [313, 547, 91, 481, 74, 64, 439, 388, 660, 275, 999]);

    var count = 0;
    // Add edges until the shortest path between `0` and `size - 1` is 2 items
    // Adding edges should never increase the length of the shortest path.
    // Adding enough edges should reduce the length of the shortest path.
    do {
      expect(++count, lessThan(size * 5), reason: 'This loop should finish.');
      addRandomEdge();
      final previousResultLength = result!.length;
      result = resultForGraph();
      expect(result, hasLength(lessThanOrEqualTo(previousResultLength)));
    } while (result!.length > 2);

    expect(result, [275, 999]);

    count = 0;
    // Remove edges until there is no shortest path.
    // Removing edges should never reduce the length of the shortest path.
    // Removing enough edges should increase the length of the shortest path and
    // eventually eliminate any path.
    do {
      expect(++count, lessThan(size * 5), reason: 'This loop should finish.');
      final randomKey = graph.keys.elementAt(rnd.nextInt(graph.length));
      final list = graph[randomKey]!;
      expect(list, isNotEmpty);
      list.removeAt(rnd.nextInt(list.length));
      if (list.isEmpty) {
        graph.remove(randomKey);
      }
      final previousResultLength = result!.length;
      result = resultForGraph();
      if (result != null) {
        expect(result, hasLength(greaterThanOrEqualTo(previousResultLength)));
      }
    } while (result != null);
  });
}