Homework 5 : Spanning Tree Algorithms

In this project, you will implement the Prim and Kruskal algorithms for Minimum spanning trees according to the outline given in class. Some of the details of that outline are repeated here.

Representation of Graphs

A weighted graph will be represented a list of weighted edges. The WEdge class represents a weighted edge in a graph.

public class WEdge implements Comparable<WEdge>
{
    public final int weight; // weight of edge
    public final int u, v;   // endpoints of edge
    
    public WEdge(int u, int weight, int v)
    {
        this.u = Math.min(u, v); 
        this.v = Math.max(u, v);
        this.weight = weight;
    }
    @Override
    public String toString()
    {
       return String.format("(%d, %d, %d)", u, weight, v);
    }
    @Override
    public boolean equals(Object other)
    {
       if (!(other instanceof WEdge) )  return false;
       WEdge e = (WEdge)other;
       return e.u == u && e.v == v || e.u == v && e.v == u;
    }

    @Override
    public int hashCode()
    {
        int hash = 5;
        hash = 97 * hash + this.u;
        hash = 97 * hash + this.v;
        return hash;
    }   

    @Override
    public int compareTo(WEdge o)
    {
        return weight - o.weight;
    }
}
    

Format of Input File

Input files should be accessed through a JFileChooser object. Input files will contain, in order, the following bits of information:

  1. The number of vertices in the graph
  2. The number of weighted edges in the graph, say X
  3. X triples of numbers representing weighted edges, each triple having the form (u, w, v) where w is the weight of the edge and u and v are the end points (vertices) of the edge.

Here is an example of the contents of such a file:

9
15
0  2  1
1  4  2
1  6  6
0  3  6
6  3  7
6  1  8
8  4  7
7  2  2
7  8  3
3  2  2
4  1  3
8  2  4
5  6  4
5  5  8
5  7  0
    

The graph in this file has 9 vertices and 15 edges.

Requirements for Prim's Algorithm

Create a Prim class with a static method

          static List getMST(List graph, int numberVertices)          
    

that takes as parameter a list of weighted edges representing a graph, and an integer representing the number of vertices of the graph. The method returns a list of weighted edges that represents a minimum spanning tree of the graph that was passed in as parameter.

As part of your algorithm, keep an array of boolean value, indexed by the set of vertices, that indicates whether a particular vertex is in the tree being assembled by Prim's algorithm.

       boolean [] inTree = new int[numberVertices];
    

Requirements for Kruskal's algorithm

Create a class Kruskal with a static method

          static List getMST(List graph, int numberVertices)          
    

that takes as parameter a list of weighted edges representing a graph, and an integer representing the number of vertices of the graph. The method returns a list of weighted edges that represents a minimum spanning tree of the graph that was passed in as parameter.

Kruskal functions by maintaining a forest of trees that is known to be a part of a minimum spanning tree. Initially you have N trees, with each tree consisting of a single vertex. Kruskal proceeds by adding edges to the forest of trees, in such a way that each edge added combines the two trees containing the end points of the edge being added into one tree. To avoid adding a cycle, the endpoints of the edge must be in two different trees of the spanning forest. We need a data structure that can quickly tell is if trees containing the endpoints of the edge are distinct, or the same tree. Do this by using an array that assigns to each vertex a label such that all vertices in the same tree component are assigned the same label. Originally, each vertex is labeled by itself:

       int [] label = new int[numberVertices];
       for (int k = 0; k < label.length; k++)
       {
           label[k] = k;
       }
    

When you combine two trees, assign to all vertices in the combined true the minimum label of all vertices in the two trees. Thus, if e is an edge being considered for adding to the forest, you want to make sure that label[e.u], the label of one of the endpoints in the edge e, is different from label[e.v], the label of the other endpoint of the edge.

Graph Utility Methods

Write a class GraphUtils class that contains two static methods

class GraphUtils
{
    /**
     *  Opens a file and reads data describing a weighted graph.
     *  The file starts with the number of vertices in the  graph, 
     *  followed by the number of edges Y, followed by Y triples giving
     *  the an endpoint u, a weight, and another endpoint v of a weighted edge
     * @param graphEdges: Adds all WEdge objects collected from the file to this list.
     * @return the number of vertices in the graph.
     * @throws FileNotFoundException 
     */
 static int getWeightedGraphFromFile(List<eWEdge> graphEdges) throws FileNotFoundException
    {
       // Your code here

       return ?;  
    }
 /**
  * 
  * @param graphEdges
  * @return total weight of all  edges in the graph
  */
 static int totalWeight(List<eWEdge> graphEdges)
 {
      
    return ?;
 }
}

    

One method is to gather the graph information from a file, and the other is to compute the total weight of a list of edges.

The main program

Put all code in a single project. To test your method, use the following main program.


import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author gcm
 */
public class MinSpanningTrees 
{   
    public static void main(String[] args) throws FileNotFoundException 
    {
        List<WEdge> graphEdges = new LinkedList<>();
        int numberVertices = GraphUtils.getWeightedGraphFromFile(graphEdges);
        
        System.out.println("The edges of the graph are: \n" + graphEdges);        
        
        List%ltWEdge> spanningTreeEdges  = Prim.getMST(graphEdges, numberVertices);
        
        System.out.printf("The edges of the Prim MST are: \n%s\n", spanningTreeEdges);
        System.out.printf("The weight of the MST is %d\n", 
                                     GraphUtils.totalWeight(spanningTreeEdges));    
        
        System.out.println("The edges of the graph are: \n" + graphEdges);  
        
        List<WEdge> spanningTreeEdges2  = Kruskal.getMST(graphEdges, numberVertices);
        
        System.out.printf("The edges of the Kruskal MST are: \n%s\n", 
                                    spanningTreeEdges2);
        System.out.printf("The weight of the MST is %d\n", 
                                     GraphUtils.totalWeight(spanningTreeEdges2));  
        
    }
}

    
Sample Interaction
z

Here is an example run of the program with the previously given file is

The edges of the graph are: 
[(0, 2, 1), (1, 4, 2), (1, 6, 6), (0, 3, 6), (6, 3, 7), (6, 1, 8), (7, 4, 8), (2, 2, 7), (3, 8, 7), (2, 2, 3), (3, 1, 4), (4, 2, 8), (4, 6, 5), (5, 5, 8), (0, 7, 5)]
The edges of the Prim MST are: 
[(0, 2, 1), (0, 3, 6), (6, 1, 8), (4, 2, 8), (3, 1, 4), (2, 2, 3), (2, 2, 7), (5, 5, 8)]
The weight of the MST is 18
The edges of the graph are: 
[(0, 2, 1), (1, 4, 2), (1, 6, 6), (0, 3, 6), (6, 3, 7), (6, 1, 8), (7, 4, 8), (2, 2, 7), (3, 8, 7), (2, 2, 3), (3, 1, 4), (4, 2, 8), (4, 6, 5), (5, 5, 8), (0, 7, 5)]
Sorted edges
 [(6, 1, 8), (3, 1, 4), (0, 2, 1), (2, 2, 7), (2, 2, 3), (4, 2, 8), (0, 3, 6), (6, 3, 7), (1, 4, 2), (7, 4, 8), (5, 5, 8), (1, 6, 6), (4, 6, 5), (0, 7, 5), (3, 8, 7)]
Added (6, 1, 8)
labels are [0, 1, 2, 3, 4, 5, 6, 7, 6]
Added (3, 1, 4)
labels are [0, 1, 2, 3, 3, 5, 6, 7, 6]
Added (0, 2, 1)
labels are [0, 0, 2, 3, 3, 5, 6, 7, 6]
Added (2, 2, 7)
labels are [0, 0, 2, 3, 3, 5, 6, 2, 6]
Added (2, 2, 3)
labels are [0, 0, 2, 2, 2, 5, 6, 2, 6]
Added (4, 2, 8)
labels are [0, 0, 2, 2, 2, 5, 2, 2, 2]
Added (0, 3, 6)
labels are [0, 0, 0, 0, 0, 5, 0, 0, 0]
The edges of the Kruskal MST are: 
[(6, 1, 8), (3, 1, 4), (0, 2, 1), (2, 2, 7), (2, 2, 3), (4, 2, 8), (0, 3, 6), (5, 5, 8)]
The weight of the MST is 18
    

Notice that the program opens the input file, reads it, and then builds and print a list of the edges in the graph. It then calls the Prim method to get a minimum spanning tree . The edges of the MST are then printed. Next, the Kruskal method is then called. This method displays each edge as it is added, and also displays the array showing the current labels on all vertices.

Due Date:

Tuesday of Week 10.