reachabilityMatrix function

List<List<bool>> reachabilityMatrix(
  1. Adjacency graph
)

Boolean reachability matrix consistent with reachabilitySets.

matrix[i][j] is true exactly when node j is reachable from node i via one or more edges, so the diagonal is true only for nodes on a cycle. Audited: 2026-06-12 11:26 EDT

Implementation

List<List<bool>> reachabilityMatrix(Adjacency graph) {
  final int n = graph.length;
  final List<Set<int>> sets = reachabilitySets(graph);
  // Project each reachable set onto a dense row so callers can index by (i, j).
  return <List<bool>>[
    for (int i = 0; i < n; i++) <bool>[for (int j = 0; j < n; j++) sets[i].contains(j)],
  ];
}