minimum spanning tree in dart using kruskall's algorithm and disjoint set union

mst.dart

/// Represents a weighted graph edge, connecting vertices [v1] and [v2].
class Edge {
  final int v1, v2;
  int weight;

  @override
  String toString() => '${v1},${v2};${weight}';

  Edge(this.v1, this.v2, this.weight);
}

/// Computes a Minimum Spanning Tree for an undirected edge-weighted graph, given a list of edges and count of vertices.
///
/// When edge weights are not unique, the [result] is one of potentially multiple solutions.
///
/// Uses [Kruskall's algortihm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) with [Disjoint Set Union](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).
///
/// Adapted to Dart from https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html
class MST {

  static int _findSet(int v, List<int> parent) {
    // follow chain of parents from given vertex v up to root of set
    // root represents set to which v belongs and may be v itself
    // path compression: every vertex visited on way to root is part of same set,
    //   so improve execution time by updating parents to point closer to root
    while(parent[v] != v) {
      parent[v] = parent[parent[v]];
      v = parent[v];
    }
    return v;
  }

  static void _zero(List<int> list) {
    final int n = list.length;
    for (int i = 0; i < n; i++) {
      list[i] = 0;
    }
  }

  late final int _numVerts;
  late final List<int> _parent, _rank;
  late final List<Edge> _edges;

  List<Edge> result = [];
  int cost = 0;

  void _makeSet(int v) {
    // adds vertex v into a new set containing only itself (as root), and initializes rank
    _parent[v] = v;
    _rank[v] = 0;
  }

  void _init() {
    // prepare for compute
    _zero(_parent);
    _zero(_rank);
    result.clear();
    cost = 0;
    for (int i = 0; i < _numVerts; i++) {
      _makeSet(i);
    }
    _edges.sort((a, b) => a.weight.compareTo(b.weight));
  }

  /// Compute the minimum spanning tree, storing participating edges in [result].
  void compute() {
    _init();
    int a, b, c;
    for (Edge e in _edges) {
      a = _findSet(e.v1, _parent);
      b = _findSet(e.v2, _parent);
      // if a and b have different roots (not a cycle), then edge belongs in result
      if (a != b) {
        cost += e.weight;
        result.add(e);
        // unionSets
        //   replace set containing a and set containing b with their union
        //   use rank to minimize tree height by keeping smaller trees within larger ones
        if (_rank[a] < _rank[b]) {
          // swap so a is always higher rank
          c = a;
          a = b;
          b = c;
        }
        _parent[b] = a;
        if (_rank[a] == _rank[b]) {
          _rank[a]++;
        }
      }
    }
  }

  /// Negate the weights of every edge.
  ///
  /// Can be used to find a maximum spanning tree by letting [compute] find the 'most negative' weights.
  void invertWeights() {
    for (Edge e in _edges) {
      e.weight *= -1;
    }
  }

  /// Prepare a data structure to compute the minimum spanning tree given a count of vertices and a list of edges.
  ///
  /// Use [compute] to find the tree, and access it from [result].
  /// Find a maximum spanning tree by calling [invertWeights] before [compute].
  MST(this._numVerts, this._edges) {
    _parent = List<int>.filled(_numVerts, 0, growable: false);
    _rank = List<int>.filled(_numVerts, 0, growable: false);
  }
}

void main() {
  /*
          5
      (3)---(2)       6 vertices    9 edges: v1,v2;weight
    9/ | \   | \8
  (4)  |1 \3 |3 (5)   0  3          0,1;2  1,2;3  2,3;5
    4\ |   \ | /7     1  4          0,3;1  1,3;3  2,5;8
      (0)---(1)       2  5          0,4;4  1,5;7  3,4;9
          2
  */
  List<Edge> edges = [
    Edge(0, 1, 2),
    Edge(0, 3, 1),
    Edge(0, 4, 4),
    Edge(1, 2, 3),
    Edge(1, 3, 3),
    Edge(1, 5, 7),
    Edge(2, 3, 5),
    Edge(2, 5, 8),
    Edge(3, 4, 9)
  ];

  print('regular - minimum');
  MST m = MST(6, edges);
  m.compute();
  print(m.result);
  print('cost: ${m.cost}');
  /*

      (3)   (2)
       |     |
  (4)  |1    |3 (5)
    4\ |     | /7
      (0)---(1)
          2

  [0,3;1, 0,1;2, 1,2;3, 0,4;4, 1,5;7]
  cost: 17
  */

  print('inverted - maximum');
  m.invertWeights();
  m.compute();
  print(m.result);
  print('cost: ${m.cost}');
  /*
          5
      (3)---(2)
    9/         \8
  (4)           (5)
    4\         /7
      (0)   (1)

  [3,4;-9, 2,5;-8, 1,5;-7, 2,3;-5, 0,4;-4]
  cost: -33
  */
}