# Prims algorithm implementation

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>();

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())) {
}
}

/* 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>();

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


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?