Walkable<E> class abstract mixin Graphs

A collection of values, or "nodes", that can be traversed incrementally.

The nodes of the walkable collection are accessed by calling the successors method with a source vertex as an argument, which returns an Iterable of vertices that are accessible from the source node.

The Walkable declaration provides a default implementation, which can be extended or mixed-in to implement the Walkable interface. It implements every member other than successors and roots. An implementation of Walkable should provide a more efficient implementation of members of Walkable when it can do so.

Directed and Undirected Graphs

A Walkable by definition describes a directed graph, where the edges between nodes have a direction. For an undirected graph, where the edges are bidirectional, they should be represented as two directed edges in either direction.

See Walkable.undirected as an example implementation of an undirected graph.

Adapting to a WeightedWalkable

A Walkable can be adapted to a WeightedWalkable by calling the asWeighted method with a function that determines the weight of an edge between two nodes. This allows for a Walkable to be used in algorithms that require a WeightedWalkable:

final unweighted = Walkable.generate(
  successors: (node) => switch (node) {
    'a' => ['b'],
    _ => const [],
  },
  roots: () => ['a'],
);
final weighted = unweighted.asWeighted((source, target) => 1);
print(weighted.successors('a')); // [('b', 1)]

Example

Here is a sample implementation of a graph using pattern matching:

final class AbcGraph with Walkable<String> {
  @override
  Iterable<String> successors(String node) {
    return switch (node) {
      'a' => ['b', 'c'],
      'b' => ['c'],
      'c' => ['d'],
      _ => const [],
    };
  }

  @override
  Iterable<String> get roots => ['a', 'b', 'c'];
}

void main() {
  final graph = AbcGraph();
  print(graph.successors('a')); // ['b', 'c']
  print(graph.roots); // ['a', 'b', 'c']
}