tree: bd0cd5d60bb6c8faea5848db8fbb1717da5fccda [path history] [tgz]
  1. benchmark/
  2. example/
  3. lib/
  4. test/
  5. .gitignore
  6. analysis_options.yaml
  7. CHANGELOG.md
  8. LICENSE
  9. pubspec.yaml
  10. README.md
pkgs/graphs/README.md

CI pub package package publisher

Graph algorithms that do not specify a particular approach for representing a Graph.

Each algorithm is a top level function which takes callback arguments that provide the mechanism for traversing the graph. For example, two common approaches for representing a graph:

class AdjacencyListGraph<T> {
  Map<T, List<T>> nodes;
  // ...
}
class TreeGraph<T> {
  Node<T> root;
  // ...
}
class Node<T> {
  List<Node<T>> edges;
  T value;
}

Any representation can be adapted to the callback arguments.

  • Algorithms which need to traverse the graph take an edges callback which provides the immediate neighbors of a given node.
  • Algorithms which need to associate unique data with each node in the graph allow passing equals and/or hashCode callbacks if the unique data type does not correctly or efficiently implement operator== or get hashCode.

Algorithms that support graphs which are resolved asynchronously will have similar callbacks which return FutureOr.

import 'package:graphs/graphs.dart';

void sendMessage() {
  final network = AdjacencyListGraph();
  // ...
  final route = shortestPath(
      sender, receiver, (node) => network.nodes[node] ?? const []);
}

void resolveBuildOrder() {
  final dependencies = TreeGraph();
  // ...
  final buildOrder = topologicalSort([dependencies.root], (node) => node.edges);
}