// Spanning.java
// Tom Conerly and Contributors, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* A minimum spanning tree (MST) is a subset of the edges of a 
   weighted undirected graph that connects all the vertices 
   together, without any cycles and with the minimum total edge weight.

   This code uses the PrimMinimumSpanningTree or 
   KruskalMinimumSpanningTree class to find the MST (uncomment the
   one you want to try).

  The edges of the MST are used to create a new graph representing
  the tree.

  Usage:
    > compile Spanning.java
    > run Spanning
*/

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;

import org.jgrapht.alg.spanning.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.interfaces.SpanningTreeAlgorithm.*;



public class Spanning
{

  public static void main(String args[])
  {
    Graph<String, WeightedEdge> g =
                   new SimpleWeightedGraph<>(WeightedEdge.class);
    Graphs.addAllVertices(g, Arrays.asList("A","B","C","D","E"));
    Graphs.addEdge(g, "A", "B", 2);
    Graphs.addEdge(g, "A", "C", 3);
    Graphs.addEdge(g, "B", "D", 5);
    Graphs.addEdge(g, "C", "D", 2);
    Graphs.addEdge(g, "D", "E", 5);
    Graphs.addEdge(g, "A", "E", 10);

    // System.out.println("Undirected weighted graph: " + g);
    JGTUtils.displayAsDOT("Original", g);

    SpanningTreeAlgorithm<WeightedEdge> spanner = 
  //                 new PrimMinimumSpanningTree<>(g);
                     new KruskalMinimumSpanningTree<>(g);

    SpanningTreeAlgorithm.SpanningTree<WeightedEdge> tree = 
                                     spanner.getSpanningTree();

    System.out.println("Spanning Tree (" + tree.getWeight() + "):");
    Iterator<WeightedEdge> eIter = tree.iterator(); 
    while (eIter.hasNext()) {
      WeightedEdge e = eIter.next();
      System.out.println(" " + g.getEdgeSource(e) + " - " + 
                               g.getEdgeTarget(e) + 
                        " (" + g.getEdgeWeight(e) + ")");
    }


    // build a new graph uses the edges of the spanning tree
    Graph<String, WeightedEdge> gSpan =
             new SimpleWeightedGraph<>(WeightedEdge.class);
    Graphs.addAllEdges(gSpan, g, tree.getEdges());

    // System.out.println("Undirected weighted spanning tree: " + gSpan);
    JGTUtils.displayAsDOT("Spanning Tree", gSpan);

    System.out.println("Is the graph a tree? " + GraphTests.isTree(gSpan));
  }  // end of main()


}  // end of Spanning class