I have this Java implementation of Kruskal's algorithm. It solves a tiny problem instance correctly, yet I am not quite sure, whether my implementation is correct.
The code as follows:
MSTFinder.java
package net.coderodde.graph.mst;
import java.util.List;
import net.coderodde.graph.UndirectedGraphEdge;
import net.coderodde.graph.UndirectedGraphNode;
import net.coderodde.graph.WeightFunction;
public interface MSTFinder {
/**
* Computes the minimum-spanning tree and returns it in the form of a list
* of undirected edges. If an error occurred during the computation,
* <code>null</code> is returned.
*
* @param graph the graph.
* @param weightFuntion the weight function over the edges of
* <code>graph</code>.
* @return the list of edges comprising a minimum-spanning
* tree, or <code>null</code> if an error occurred.
*/
public List<UndirectedGraphEdge>
findMinimumSpanningTree(final List<UndirectedGraphNode> graph,
final WeightFunction weightFuntion);
}
KruskalMSTFinder.java
package net.coderodde.graph.mst.support;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
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 {
private final Map<UndirectedGraphNode,
DisjointSet<UndirectedGraphNode>> map;
private final Set<UndirectedGraphEdge> edgeSet;
private final List<UndirectedGraphEdge> edgeList;
public KruskalMSTFinder() {
this.map = new HashMap<>();
this.edgeSet = new LinkedHashSet<>();
this.edgeList = new ArrayList<>();
}
@Override
public List<UndirectedGraphEdge>
findMinimumSpanningTree(final List<UndirectedGraphNode> graph,
final WeightFunction weightFunction) {
try {
prepareEdgeList(graph, weightFunction);
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);
}
}
clearAll();
return minimumSpanningTree;
} catch (final Exception e) {
clearAll();
return null;
}
}
private void clearAll() {
map.clear();
edgeSet.clear();
edgeList.clear();
}
private void prepareEdgeList(final List<UndirectedGraphNode> graph,
final WeightFunction weightFunction) {
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);
}
}
DisjointSet.java
package net.coderodde.graph.mst.support;
public class DisjointSet<E> {
private DisjointSet<E> parent;
private int rank;
public DisjointSet() {
this.parent = this;
this.rank = 0;
}
public DisjointSet<E> find(final DisjointSet<E> set) {
return getRoot(set);
}
public void union(final DisjointSet<E> otherSet) {
final DisjointSet<E> otherRoot = getRoot(otherSet);
final DisjointSet<E> thisRoot = getRoot(this);
if (otherRoot == thisRoot) {
return;
}
if (otherRoot.rank < thisRoot.rank) {
otherRoot.parent = thisRoot.parent;
} else if (otherRoot.rank > thisRoot.rank) {
thisRoot.parent = otherRoot.parent;
} else {
thisRoot.parent = otherRoot.parent;
otherRoot.rank = thisRoot.rank + 1;
}
}
private DisjointSet<E> getRoot(final DisjointSet<E> set) {
if (set.parent == set) {
return set;
}
return getRoot(set.parent);
}
}
WeightFunction.java
package net.coderodde.graph;
import java.util.HashMap;
import java.util.Map;
public class WeightFunction {
private final Map<UndirectedGraphNode,
Map<UndirectedGraphNode, Double>> map;
public WeightFunction() {
this.map = new HashMap<>();
}
public void put(final UndirectedGraphNode u,
final UndirectedGraphNode v,
final double weight) {
putImpl(u, v, weight);
putImpl(v, u, weight);
}
public double get(final UndirectedGraphNode u,
final UndirectedGraphNode v) {
return map.get(u).get(v);
}
private void putImpl(final UndirectedGraphNode u,
final UndirectedGraphNode v,
final double weight) {
if (!map.containsKey(u)) {
map.put(u, new HashMap<>());
}
map.get(u).put(v, weight);
}
}
UndirectedGraphNode.java
package net.coderodde.graph;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class UndirectedGraphNode implements Iterable<UndirectedGraphNode> {
private final String id;
private final Set<UndirectedGraphNode> neighbors;
public UndirectedGraphNode(final String id) {
this.id = id;
this.neighbors = new LinkedHashSet<>();
}
public void connectTo(final UndirectedGraphNode other) {
this.neighbors.add(other);
other.neighbors.add(this);
}
public boolean isConnectedTo(final UndirectedGraphNode queryNode) {
return this.neighbors.contains(queryNode);
}
public void disconnectFrom(final UndirectedGraphNode neighbor) {
this.neighbors.remove(neighbor);
neighbor.neighbors.remove(this);
}
public boolean equals(final Object obj) {
if (!(obj instanceof UndirectedGraphNode)) {
return false;
}
return ((UndirectedGraphNode) obj).id.equals(this.id);
}
@Override
public int hashCode() {
return this.id.hashCode();
}
@Override
public Iterator<UndirectedGraphNode> iterator() {
return new NeighborIterator();
}
@Override
public String toString() {
return "[UndirectedGraphNode " + id + "]";
}
public String getId() {
return id;
}
private class NeighborIterator implements Iterator<UndirectedGraphNode> {
private final Iterator<UndirectedGraphNode> iterator =
UndirectedGraphNode.this.neighbors.iterator();
@Override
public boolean hasNext() {
return iterator.hasNext();
}
@Override
public UndirectedGraphNode next() {
return iterator.next();
}
}
}
UndirectedGraphEdge.java
package net.coderodde.graph;
public class UndirectedGraphEdge implements Comparable<UndirectedGraphEdge> {
private final UndirectedGraphNode u;
private final UndirectedGraphNode v;
private final double weight;
public UndirectedGraphEdge(final UndirectedGraphNode u,
final UndirectedGraphNode v,
final double weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
public UndirectedGraphNode firstNode() {
return u;
}
public UndirectedGraphNode secondNode() {
return v;
}
public String toString() {
return "[UndirectedGraphEdge between " + u.getId() + " and " +
v.getId() + "]";
}
public int hashCode() {
return u.hashCode() ^ v.hashCode();
}
@Override
public boolean equals(final Object obj) {
if (!(obj instanceof UndirectedGraphEdge)) {
return false;
}
final UndirectedGraphEdge edge = (UndirectedGraphEdge) obj;
if (this.u.equals(edge.u) && this.v.equals(edge.v)) {
return true;
}
return this.u.equals(edge.v) && this.v.equals(edge.u);
}
/**
* Sorts a sequence of edges into descending order by edge weight.
*
* @param o the other edge to compare against.
* @return a negative value if the input edge has larger weight,
* a positive value if the input edge has smaller weight, and
* the value zero if the two weights are equal.
*/
@Override
public int compareTo(final UndirectedGraphEdge o) {
return Double.compare(this.weight, o.weight);
}
}
Demo.java
package net.coderodde.graph;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import net.coderodde.graph.mst.MSTFinder;
import net.coderodde.graph.mst.support.KruskalMSTFinder;
public class Demo {
private static final int SIZE = 100000;
private static final float EDGE_LOAD_FACTOR = 15.0f;
public static void main(final String... args) {
final List<UndirectedGraphNode> graph = new ArrayList<>();
// This graph is from English-language Wikipedia-article on
// Kruskal's algorithm:
final UndirectedGraphNode a = new UndirectedGraphNode("A");
final UndirectedGraphNode b = new UndirectedGraphNode("B");
final UndirectedGraphNode c = new UndirectedGraphNode("C");
final UndirectedGraphNode d = new UndirectedGraphNode("D");
final UndirectedGraphNode e = new UndirectedGraphNode("E");
graph.add(a);
graph.add(b);
graph.add(c);
graph.add(d);
graph.add(e);
final WeightFunction wf = new WeightFunction();
a.connectTo(e);
a.connectTo(b);
b.connectTo(e);
e.connectTo(c);
b.connectTo(c);
c.connectTo(d);
e.connectTo(d);
wf.put(a, e, 1.0);
wf.put(a, b, 3.0);
wf.put(b, e, 4.0);
wf.put(e, c, 6.0);
wf.put(b, c, 5.0);
wf.put(c, d, 2.0);
wf.put(e, d, 7.0);
final MSTFinder finder = new KruskalMSTFinder();
final List<UndirectedGraphEdge> mst =
finder.findMinimumSpanningTree(graph, wf);
for (final UndirectedGraphEdge edge : mst) {
System.out.println(edge + " " +
wf.get(edge.firstNode(), edge.secondNode()));
}
System.out.println("MST done.");
final long seed = System.currentTimeMillis();
System.out.println("Seed: " + seed);
final Random rnd = new Random(seed);
final Pair<List<UndirectedGraphNode>, WeightFunction> data =
createRandomGraph(SIZE, EDGE_LOAD_FACTOR, rnd);
System.out.println("Graph constructed.");
final long ta = System.currentTimeMillis();
final List<UndirectedGraphEdge> tree =
finder.findMinimumSpanningTree(data.first, data.second);
System.out.println(
"Time: " + (System.currentTimeMillis() - ta) + " ms.");
}
public static final class Pair<F, S> {
public final F first;
public final S second;
public Pair(final F first, final S second) {
this.first = first;
this.second = second;
}
}
public static <E> E choose(final List<E> list, final Random rnd) {
if (list.isEmpty()) {
return null;
}
return list.get(rnd.nextInt(list.size()));
}
private static Pair<List<UndirectedGraphNode>, WeightFunction>
createRandomGraph(final int size,
final float edgeLoadFactor,
final Random rnd) {
final List<UndirectedGraphNode> graph = new ArrayList<>(size);
final WeightFunction wf = new WeightFunction();
for (int i = 0; i < size; ++i) {
graph.add(new UndirectedGraphNode("" + i));
}
int edges = (int)(Math.min(1.0f, edgeLoadFactor) * size);
while (edges > 0) {
final UndirectedGraphNode u = choose(graph, rnd);
final UndirectedGraphNode v = choose(graph, rnd);
u.connectTo(v);
wf.put(u, v, 10.0 * rnd.nextDouble() - 5.0);
--edges;
}
return new Pair(graph, wf);
}
}
So what do you think?