\$\begingroup\$
\$\endgroup\$
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?
asked Feb 1, 2015 at 7:04
lang-java