Prims algorithm implementation

Question

Review this code regarding optimization, cleanup, and best practices.

final class EdgePrims<T> {
    private final T source, target;
    private final int distance;

    public EdgePrims(T node1, T node2, int distance) {
        this.source = node1;
        this.target = node2;
        this.distance = distance;
    }

    public T getSource() {
        return source;
    }

    public T getTarget() {
        return target;
    }

    public int getDistance() {
        return distance;
    }

    @Override
    public String toString() {
        return " first vertex " + source + " to vertex " + target + " with distance: " + distance;
    }
}


final class GraphPrims<T> implements Iterable<T> {

    private final Map<T, Map<T, Integer>> graph;

    public GraphPrims() {
        graph = new HashMap<T, Map<T, Integer>>();
    }

    public void addEgde(T vertex1, T vertex2, int distance) {
        if (vertex1 == null) {
            throw new NullPointerException("The vertex 1 cannot be null");
        } 
        if (vertex2 == null) {
            throw new NullPointerException("The vertex 2 cannot be null");
        }

        if (!graph.containsKey(vertex1))  {
            graph.put(vertex1, new HashMap<T, Integer>());
        }
        if (!graph.containsKey(vertex2))  {
            graph.put(vertex2, new HashMap<T, Integer>());
        }
        graph.get(vertex1).put(vertex2, distance);
        graph.get(vertex2).put(vertex1, distance);
    }

    public Set<T> getVertices() {
        return Collections.unmodifiableSet(graph.keySet()); // QQ: should this be replaced by DEEP COPy ?
    }

    public Map<T, Integer> getEdges(T source) {
        if (source == null) {
            throw new NullPointerException("The source cannot be null.");
        }
        return Collections.unmodifiableMap(graph.get(source));
    }

    public void removeEdges(T vertex1, T vertex2) {
        if (vertex1 == null) {
            throw new NullPointerException("The vertex 1 cannot be null");
        } 
        if (vertex2 == null) {
            throw new NullPointerException("The vertex 2 cannot be null");
        }
        if (!graph.containsKey(vertex1)) {
            throw new NoSuchElementException("vertex " + vertex1  + " does not exist.");
        }
        if (!graph.containsKey(vertex2)) {
            throw new NoSuchElementException("vertex " + vertex2  + " does not exist.");
        }
        graph.get(vertex1).remove(vertex2);
        graph.get(vertex2).remove(vertex1);
    }

    @Override
    public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }
}



public class Prims<T> {

    public static Comparator<EdgePrims> edgeComparator = new Comparator<EdgePrims>() {
        @Override
        public int compare(EdgePrims edge1, EdgePrims edge2) {
            return edge1.getDistance() - edge2.getDistance();
        }
    };

    /**
     * Uses prim's algo to calculate a MST for a connected graph.
     * A non-connected graph will lead to unpredictable result.
     * 
     * @param graph a connected graph.
     * @return a list of edges that constitute the MST
     */
    public static <T> List<EdgePrims<T>> getMinSpanTree(GraphPrims<T> graph) {
        Queue<EdgePrims<T>> edgesAvailable = new PriorityQueue<EdgePrims<T>>(10, edgeComparator);
        List<EdgePrims<T>> listMinEdges = new ArrayList<EdgePrims<T>>();
        Set<T> unvisitedVertices = new HashSet<T>();
        unvisitedVertices.addAll(graph.getVertices());

        T sourceVertex = unvisitedVertices.iterator().next();
        unvisitedVertices.remove(sourceVertex);

        while (!unvisitedVertices.isEmpty()) {
            /* populate all edges for the current vertex */

            for (Entry<T, Integer> e : graph.getEdges(sourceVertex).entrySet()) {

                /* dont add a duplicate edge */
                if (unvisitedVertices.contains(e.getKey())) {
                    edgesAvailable.add(new EdgePrims(sourceVertex, e.getKey(), (Integer) e.getValue()));
                }
            }

            /* fetch the edge with least distance */
            EdgePrims<T> minEdge = edgesAvailable.poll();
            /* if the target is already visited then move to next edge */
            while (!unvisitedVertices.contains(minEdge.getTarget())) {
                minEdge = edgesAvailable.poll();
            }

            listMinEdges.add(minEdge); // this list will contain unique targetvertices.

            sourceVertex = minEdge.getTarget(); // get the next vertex.
            unvisitedVertices.remove(sourceVertex);
        }

        return listMinEdges;
    }  

    public static void main(String[] args) {
        GraphPrims<Character> graphPrims = new GraphPrims<Character>();

        graphPrims.addEgde('A', 'B', 10);
        graphPrims.addEgde('A', 'C', 15);
        graphPrims.addEgde('C', 'B', 50);
        graphPrims.addEgde('C', 'D', 20);
        graphPrims.addEgde('B', 'D', 80);
        graphPrims.addEgde('B', 'F', 80); 
       // graphPrims.addEgde('x', 'y', 700); 

        for (EdgePrims<Character> edge : getMinSpanTree(graphPrims)) {
            System.out.println(edge.toString());
        }
    }
}

Answer 1

1. public EdgePrims(T node1, T node2, int distance) - What are node1 and node2? From reading the source one can see they are source and target node - so they should be named accordingly. The names of the parameters of a function are an important piece of documentation and should convey their meaning.

2. You have created a link between your data structures (GraphPrims, EdgePrims) and an algorithm which seems weird as they have only in common that Prim's is a graph algorithm - meaning you need a graph to run it on but the graph doesn't need the algorithm. I'm pretty sure I could implement Dijkstra's algorithm and run it on a graph of yours.

   The problem is that this creates a barrier in your mind for the re-usability of the classes. Also it reads odd if I write

   class Dijkstras 
   {
       public static <T> List<EdgePrims<T>> getShortestPath(GraphPrims<T> graph, EdgePrims<T> from, EdgePrims<T> to)
       { ... }
   }
   

3. Why do you initialize edgesAvailable with a default initial capacity of 10? According to the Java documentation the default initial capacity is 11. Why is 10 any better?