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?