Are there import statement for classes called Edge, Graph, and Vertex?

Thread Starter

asilvester635

Joined Jan 26, 2017
73
I found this primMST java class source code online for the prim algorithm. It was accompanied by another class called BinaryMinHeap, which is used in the primMST class. I copied and pasted the primMST code in NetBeans, and it gave me error labels in the text editor for three classes that were used in the primMST class. They are class Edge, Graph, and Vertex.

There was another error for class List, but I fixed that by using the import statement import java.util.*;

Is there an import statement for the class called "Edge", "Graph", and "Vertex"? I've been searching google but I couldn't find anything. Below is the source code for primMST class.

Code:
package mst;

import java.util.*;

public class PrimMST {
    /**
     * Main method of Prim's algorithm.
     */
    public List<Edge<Integer>> primMST(Graph<Integer> graph){

        //binary heap + map data structure
        BinaryMinHeap<Vertex<Integer>> minHeap = new BinaryMinHeap<>();

        //map of vertex to edge which gave minimum weight to this vertex.
        Map<Vertex<Integer>,Edge<Integer>> vertexToEdge = new HashMap<>();

        //stores final result
        List<Edge<Integer>> result = new ArrayList<>();

        //insert all vertices with infinite value initially.
        for(Vertex<Integer> v : graph.getAllVertex()){
            minHeap.add(Integer.MAX_VALUE, v);
        }

        //start from any random vertex
        Vertex<Integer> startVertex = graph.getAllVertex().iterator().next();

        //for the start vertex decrease the value in heap + map to 0
        minHeap.decrease(startVertex, 0);

        //iterate till heap + map has elements in it
        while(!minHeap.empty()){
            //extract min value vertex from heap + map
            Vertex<Integer> current = minHeap.extractMin();

            //get the corresponding edge for this vertex if present and add it to final result.
            //This edge wont be present for first vertex.
            Edge<Integer> spanningTreeEdge = vertexToEdge.get(current);
            if(spanningTreeEdge != null) {
                result.add(spanningTreeEdge);
            }

            //iterate through all the adjacent vertices
            for(Edge<Integer> edge : current.getEdges()){
                Vertex<Integer> adjacent = getVertexForEdge(current, edge);
                //check if adjacent vertex exist in heap + map and weight attached with this vertex is greater than this edge weight
                if(minHeap.containsData(adjacent) && minHeap.getWeight(adjacent) > edge.getWeight()){
                    //decrease the value of adjacent vertex to this edge weight.
                    minHeap.decrease(adjacent, edge.getWeight());
                    //add vertex->edge mapping in the graph.
                    vertexToEdge.put(adjacent, edge);
                }
            }
        }
        return result;
   
    } // end of primMST

    private Vertex<Integer> getVertexForEdge(Vertex<Integer> v, Edge<Integer> e){
        return e.getVertex1().equals(v) ? e.getVertex2() : e.getVertex1();
    }

} // end of PrimMST class
 

WBahn

Joined Mar 31, 2012
29,978
Let's say that Fred wrote a bunch of code to manage a flock of geese and you downloaded it from his website. Would it make sense to ask anyone other than Fred these types of questions? Would you expect Google to be of much help in trying to find out how to use Fred's code?

Did you download the code for the Edge, Graph, and Vertex classes from the same website that you got the code for the PrimMST class from? If so, did you put it all of them in the mst package?
 
Top