import 'package:dartterm/algorithms/union_find.dart';

class Edge<T> {
  final int src, dst;
  final T value;
  final double score; // higher score is better

  const Edge(this.src, this.dst, this.value, this.score);
}

List<Edge<T>> kruskal<T>(int nRegions, List<Edge<T>> srcEdges) {
  var edges = List.from(srcEdges); // copy so we can mutate it
  edges.sort((e0, e1) => -e0.score.compareTo(e1.score));

  List<Edge<T>> spanningEdges = [];
  var connected = UnionFind(nRegions);

  for (var i = 0; i < edges.length; i++) {
    var edge = edges[i];
    if (connected.find(edge.src) == connected.find(edge.dst)) {
      continue;
    }
    spanningEdges.add(edge);
    connected.union(edge.src, edge.dst);

    // break early if we run out of regions
    nRegions -= 1;
    if (nRegions == 1) {
      break;
    }
  }
  return spanningEdges;
}