5
\$\begingroup\$

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());
        }
    }
}
\$\endgroup\$
6
\$\begingroup\$
  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?

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.