Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The previous and initial iteration at Kruskal's algorithm in Java

Now what I did is remove the fields and let the actual Kruskal-routine create the required data structures in the local scope, which leads to thread safety.

The only file that changed is KruskalMSTFinder.java:

package net.coderodde.graph.mst.support;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import net.coderodde.graph.UndirectedGraphEdge;
import net.coderodde.graph.UndirectedGraphNode;
import net.coderodde.graph.WeightFunction;
import net.coderodde.graph.mst.MSTFinder;

public class KruskalMSTFinder implements MSTFinder {

    @Override
    public List<UndirectedGraphEdge> 
        findMinimumSpanningTree(final List<UndirectedGraphNode> graph,
                                final WeightFunction weightFunction) {
        final Map<UndirectedGraphNode, 
                  DisjointSet<UndirectedGraphNode>> map = new HashMap<>();
        final Set<UndirectedGraphEdge> edgeSet = new HashSet<>();
        final List<UndirectedGraphEdge> edgeList = new ArrayList<>();

        prepareEdgeList(graph, 
                        weightFunction,
                        map,
                        edgeSet,
                        edgeList);

        final List<UndirectedGraphEdge> minimumSpanningTree = new ArrayList<>();

        for (final UndirectedGraphEdge edge : edgeList) {
            final UndirectedGraphNode u = edge.firstNode();
            final UndirectedGraphNode v = edge.secondNode();

            DisjointSet<UndirectedGraphNode> us = map.get(u);
            DisjointSet<UndirectedGraphNode> vs = map.get(v);

            us = us.find(us);
            vs = vs.find(vs);

            if (us != vs) {
                minimumSpanningTree.add(edge);
                us.union(vs);
            }
        }

        return minimumSpanningTree;
    }

    private void 
        prepareEdgeList(final List<UndirectedGraphNode> graph,
                        final WeightFunction weightFunction,
                        final Map<UndirectedGraphNode,
                                  DisjointSet<UndirectedGraphNode>> map,
                        final Set<UndirectedGraphEdge> edgeSet,
                        final List<UndirectedGraphEdge> edgeList) {
        for (final UndirectedGraphNode node : graph) {
            map.put(node, new DisjointSet<>());

            for (final UndirectedGraphNode neighbor : node) {
                edgeSet.add(
                        new UndirectedGraphEdge(node, 
                                                neighbor, 
                                                weightFunction
                                                        .get(node, neighbor)));
            }
        }

        edgeList.addAll(edgeSet);
        Collections.<UndirectedGraphEdge>sort(edgeList);
    }
}

Anything else to improve?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.