Class MinimumSpanningTree

java.lang.Object
com.phasmidsoftware.gryphon.java.MinimumSpanningTree

public class MinimumSpanningTree extends Object
Java façade for minimum spanning tree algorithms on weighted undirected graphs.

All methods operate on a WeightedGraph<V, E> whose edges carry an attribute of type E. The edge attribute is used directly as the priority key — no separate weight extractor is needed.

Both algorithms require an undirected graph. Calling either on a directed graph throws IllegalStateException.

Prim result: Map<V, WeightedEdge<V, E>> mapping each non-source vertex to its cheapest MST edge. The start vertex is absent.

Kruskal result: List<WeightedEdge<V, E>> in non-decreasing order according to the supplied comparator.

Option 1 example (Double weights):


 WeightedGraph<Integer, Double> g = WeightedGraph.undirected();
 g.addEdge(new WeightedEdge<>(0, 1, 0.26));
 g.addEdge(new WeightedEdge<>(0, 7, 0.16));

 Map<Integer, WeightedEdge<Integer, Double>> mst = MinimumSpanningTree.prim(g, 0);
 double total = mst.values().stream().mapToDouble(WeightedEdge::attribute).sum();
 

Option 3 example (custom attribute type):


 WeightedGraph<Building, TunnelProperties> g = WeightedGraph.undirected();
 g.addEdge(new WeightedEdge<>(b1, b2, tunnelProperties));

 Map<Building, WeightedEdge<Building, TunnelProperties>> mst =
     MinimumSpanningTree.prim(g, start, Comparator.comparingInt(tp -> tp.cost));

 mst.forEach((b, e) -> System.out.println(b + ": cost=" + e.attribute().cost
                                           + " length=" + e.attribute().length));
 
  • Method Details

    • prim

      public static <V> Map<V,WeightedEdge<V,Double>> prim(WeightedGraph<V,Double> graph, V start)
      Runs Prim's algorithm on a graph whose edges carry Double weights.

      Edge attributes are compared by natural Double ordering. No configuration required.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - an undirected WeightedGraph<V, Double>.
      start - the source vertex (absent from the result).
      Returns:
      the MST as Map<V, WeightedEdge<V, Double>>.
      Throws:
      IllegalStateException - if graph is directed.
    • prim

      public static <V, E> Map<V,WeightedEdge<V,E>> prim(WeightedGraph<V,E> graph, V start, Comparator<E> comparator)
      Runs Prim's algorithm with a custom edge attribute type, ordered by the supplied Comparator.

      The edge attribute is used directly as the priority key. No weight extractor is needed.

      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      graph - an undirected WeightedGraph<V, E>.
      start - the source vertex (absent from the result).
      comparator - orders edge attributes.
      Returns:
      the MST as Map<V, WeightedEdge<V, E>>.
      Throws:
      IllegalStateException - if graph is directed.
    • kruskal

      public static <V> List<WeightedEdge<V,Double>> kruskal(WeightedGraph<V,Double> graph)
      Runs Kruskal's algorithm on a graph whose edges carry Double weights.

      Edges are sorted by natural Double ordering. The returned list is in non-decreasing weight order.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - an undirected WeightedGraph<V, Double>.
      Returns:
      the MST as List<WeightedEdge<V, Double>> in non-decreasing weight order.
      Throws:
      IllegalStateException - if graph is directed.
    • kruskal

      public static <V, E> List<WeightedEdge<V,E>> kruskal(WeightedGraph<V,E> graph, Comparator<E> comparator)
      Runs Kruskal's algorithm with a custom edge attribute type, ordered by the supplied Comparator.

      The edge attribute is used directly as the sort key. The returned list is in non-decreasing order according to comparator.

      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      graph - an undirected WeightedGraph<V, E>.
      comparator - orders edge attributes.
      Returns:
      the MST as List<WeightedEdge<V, E>> in non-decreasing order.
      Throws:
      IllegalStateException - if graph is directed.
    • boruvka

      public static <V> List<WeightedEdge<V,Double>> boruvka(WeightedGraph<V,Double> graph)
      Runs Borůvka's algorithm on a graph whose edges carry Double weights.

      Edges are compared by natural Double ordering. The returned list contains exactly N-1 edges for a connected graph of N vertices.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - an undirected WeightedGraph<V, Double>.
      Returns:
      the MST as List<WeightedEdge<V, Double>>.
      Throws:
      IllegalStateException - if graph is directed.
    • boruvka

      public static <V, E> List<WeightedEdge<V,E>> boruvka(WeightedGraph<V,E> graph, Comparator<E> comparator)
      Runs Borůvka's algorithm with a custom edge attribute type, ordered by the supplied Comparator.

      The edge attribute is used directly as the sort key. The returned list contains exactly N-1 edges for a connected graph of N vertices.

      Type Parameters:
      V - the vertex type.
      E - the edge attribute type.
      Parameters:
      graph - an undirected WeightedGraph<V, E>.
      comparator - orders edge attributes.
      Returns:
      the MST as List<WeightedEdge<V, E>>.
      Throws:
      IllegalStateException - if graph is directed.