Transitive Reduction Implementation in Dart (Harry Hsu)

transitive_reduction.dart

/// Return the [Transitive Reduction] for a directed acyclic graph (DAG).
///
/// This function assumes the graph is acyclic and it doesn't check for that.
///
/// [nodes] should be a list of all nodes in the graph.
///
/// [hasPath] should return `true` when the first argument has a path to the second argument.
/// > Note: [hasPath] should return `true` when there is a **path**, not only an edge.
///
/// This function is a port of [jgrapht][] implementation of Harry Hsu's paper:
/// "An Algorithm for Finding a Minimal Equivalent Graph of a Digraph" ([doi][])
///
/// [Transitive Reduction]: https://en.wikipedia.org/wiki/Transitive_reductio
/// [jgrapht]: https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/TransitiveReduction.java
/// [doi]: https://doi.org/10.1145/321864.321866
Map<T, Set<T>> transitiveReduction<T>(List<T> nodes, bool Function(T from, T to) hasPath) {
  
  final length = nodes.length; // square matrix (#row == #col == length)
  final dimension = length * length;
  final pathMatrix = Uint8List(dimension);

  int index(int row, int col) => (row * length) + col;

  // Create the path matrix
  // "1" indicates a path and "0" indicates no path
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length; j++) {
      // don't create a path from a node to itself.
      if (i == j) continue;
      if (hasPath(nodes[i], nodes[j])) {
        pathMatrix[index(i, j)] = 1;
      }
    }
  }

  // Reduce the graph in the path matrix
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length; j++) {
      if (pathMatrix[index(i, j)] > 0) {
        for (var k = 0; k < length; k++) {
          if (pathMatrix[index(j, k)] > 0) {
            pathMatrix[index(i, k)] = 0;
          }
        }
      }
    }
  }

  // Create the reduced graph with the original nodes
  final reducedGraph = <T, Set<T>>{};
  for (var i = 0; i < length; i++) {
    final rowIndex = index(i, 0);
    final row = pathMatrix.sublist(rowIndex, rowIndex + length);
    final set = <T>{};
    for (var j = 0; j < row.length; j++) {
      if (row[j] > 0) {
        set.add(nodes[j]);
      }
    }
    reducedGraph[nodes[i]] = set;
  }

  return reducedGraph;
}

The following example shows how the function can be used:

import 'dart:collection';
import 'package:collection/collection.dart';

final graph = <String, List<String>>{
  'A': ['B', 'C', 'D', 'E', 'F', 'G'],
  'B': ['C', 'E', 'F'],
  'C': ['D'],
  'D': ['E', 'G'],
  'E': ['F'],
  'F': ['G'],
  'G': [],
};

final expectedReducedGraph = <String, Set<String>>{
  'A': {'B'},
  'B': {'C'},
  'C': {'D'},
  'D': {'E'},
  'E': {'F'},
  'F': {'G'},
  'G': {},
};

/// Returns `true` if there is a path `from` one node `to` another.
///
/// Only works with finite acyclic graphs
bool hasPath(String from, String to) {
  // breadth first search for DAG
  final queue = Queue<String>();
  final edges = graph[from]!;
  queue.addAll(edges);

  while (queue.isNotEmpty) {
    final next = queue.removeFirst();
    if (next == to) return true;
    queue.addAll(graph[next]!);
  }
  return false;
}

void main() {
  final reduced = transitiveReduction(graph.keys.toList(), hasPath);
  print(DeepCollectionEquality().equals(reduced, expectedReducedGraph)); // true
  print(reduced); // {A: {B}, B: {C}, C: {D}, D: {E}, E: {F}, F: {G}, G: {}}
}