enumeratePaths function

List<List<int>> enumeratePaths(Adjacency graph, int start, int target, { int? maxDepth, })

Every simple path from start to target, each path a node-index list.

A simple path repeats no node, so cycles in graph cannot cause infinite recursion. maxDepth, when set, caps the number of EDGES in a path (a path of k nodes has k-1 edges); paths needing more edges are pruned. When start == target the single zero-edge path [[start]] is returned. Out-of- range start or target yields an empty list.

Example:

final Adjacency g = buildGraph([(0, 1), (0, 2), (1, 2)], 3);
enumeratePaths(g, 0, 2); // [[0, 2], [0, 1, 2]]

Audited: 2026-06-12 11:26 EDT

Implementation

List<List<int>> enumeratePaths(
  Adjacency graph,
  int start,
  int target, {
  int? maxDepth,
}) {
  // Guard out-of-range endpoints up front so the DFS can index graph safely.
  if (start < 0 || start >= graph.length) return <List<int>>[];
  if (target < 0 || target >= graph.length) return <List<int>>[];
  final List<List<int>> paths = <List<int>>[];
  final List<bool> onPath = List<bool>.filled(graph.length, false);
  final List<int> current = <int>[];
  _walk(graph, start, target, maxDepth, onPath, current, paths);
  return paths;
}