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?