Graphs topic

Graph data structures, sorting, traversal, and graph algorithms & utilities.

---

Table of Contents:

• Walkables
• Graphs
• Sorting and Traversing

---

Walkables

Sector provides foundational sequential access to graph nodes, or Walkable, which is to iterable what Graph is to List, representing a collection of nodes and edges:

void example(Walkable<String> walkable) {
  for (final node in walkable.roots) {
    for (final successor in walkable.successors(node)) {
      print('$node -> $successor');
    }
  }
}

Ephemeral collections can be created without needing a concrete implementation:

// a -> b -> c
Walkable.linear(['a', 'b', 'c']);

// a -> b -> a
Walkable.circular(['a', 'b']);

//    a
//   / \
//  b - c
Walkable.star(['a', 'b', 'c']);

See also WeightedWalkable, a variant of Walkable that includes floating point edge weights, and can be derived using Walkable.asWeighted; algorithms that can operate on both types of walkables can be implemented in terms of WalkableBase (which many algorithms in this package do).

Graphs

Graphs are a collection of nodes, and edges between nodes.

Sector contains an interface and concrete implementation, Graph and AdjacencyListGraph, respectively, which is an adjacency list representation of a graph, ideal for sparse (few edges) graphs:

final graph = Graph<String>();

graph.addEdge(Edge('a', 'b'));
graph.addEdge(Edge('b', 'c'));

print(graph.roots); // ['a']
print(graph.successors('b')); // ['c']

By default, most graphs are directed, meaning an edge has an explicit source and target node. However, undirected graphs can be created by using directed: false, or by mixing-in the UndirectedGraph mixin:

final graph = Graph<String>(directed: false);

graph.addEdge(Edge('a', 'b'));

print(graph.successors('a')); // ['b']
print(graph.successors('b')); // ['a']

// ...

final class MyUndirectedGraph<E> = MyGraph<E> with UndirectedGraph<E> {}

Sorting and Traversing

A few utilities are provided for sorting and traversing graphs:

• topologicalSort for sorting a directed acyclic graph dependency order.
• stronglyConnected and for finding cycles (strong components) in a graph.
• breadthFirst for traversing a graph in breadth-first (shallower-first) order.
• depthFirst for traversing a graph in depth-first (deeper-first) order.

Classes

AdjacencyListGraph<E>

An unweighted graph suitable for sparse graphs.

Edge<E>

A graph edge connecting two nodes.

Graph<E>

A collection of nodes and edges where edges connect exactly two nodes.

GraphBase<E>

A base interface for graphs.

ScalarEvent<E>

A captured Tracer.pushScalar event.

SkipEvent<E>

A captured Tracer.onSkip event.

TraceEvent<E>

An event captured by a TraceRecorder.

Tracer<E>

A utility for capturing events during a graph traversal or pathfinding.

TraceRecorder<E>

A utility for recording events during a graph traversal or pathfinding.

VisitEvent<E>

A captured Tracer.onVisit event.

Walkable<E>

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

WalkableBase<E>

A base interface for walkable collections.

WeightedEdge<V>

A weighted graph edge connecting two nodes.

WeightedGraph<V>

A graph where edges have an associated weight, or "cost", a double value.

WeightedWalkable<E>

A collection of nodes and edges that can be traversed incrementally.

Mixins

UndirectedGraph<E>

A mixin that that adapts a Graph to be undirected.

Functions

breadthFirst<T>(WalkableBase<T> graph, {required T start, Tracer<T>? tracer}) → Iterable<T>

Visits nodes in a graph structure, shallowest nodes first, from start.

depthFirst<T>(WalkableBase<T> graph, {required T start, Tracer<T>? tracer}) → Iterable<T>

Visits nodes in a graph structure, deepest nodes first, from start.

stronglyConnected<T>(WalkableBase<T> graph, {Iterable<T>? from, Tracer<T>? tracer}) → List<List<T>>

Partitions nodes reachable in a graph into strongly connected components.

topologicalSort<T>(Iterable<T> roots, {required Iterable<T> successors(T)}) → List<T>

Returns a topological sort of the directed edges provided, if one exists.

Typedefs

Crawler<E> = Iterable<T> Function<T extends E>(WalkableBase<T> nodes, {required T start, Tracer<T>? tracer})

A function that visits nodes in a graph structure starting from start.

Exceptions / Errors

CycleException<T>

Indicates a cycle was detected in a graph expected to be acyclic.