Kruskal's algorithm in Java

Question

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?

Answer 1

KruskalMSTFinder.java was not nice to read for me.

map, edgeSet and edgeList are defined as fields. They are initialized in prepareEdgeList-Method and reset in the clearAll-Method. Both are called within the findMinimumSpanningTree-Method.

So map, edgeSet and edgeList defined as local Variables would do the same job.

Now it is not Threadsafe! Thread one could clear the fields, while Thread two would like to prepare it.

Just define them as local Variables and let prepareEdgeList, prepareEdgeSet and prepareEdgeMap return a prepared map, edgeList and edgeSet.

Answer 2

Mathematics

A graph G is defined as a set of nodes or vertices V = {v1, v2...vn} and a bag of edges E = {e1, e2, ...em}. The only relation between edges and vertices is that for each edge e between vertices u and v both u and v must be members of V.

Dependencies

Mathematically, a set of vertices V is independent of the set of edges E. Two different graphs G1 and G2 can be defined across the same set of vertices based solely on the difference between two sets of edges E1 and E2.

 G1 = V, E1
 G2 = V, E2 

Nodes are necessarily properties of Edges. Edges are not properties of nodes. Edges are [ properties | fields | objects ] of a graph. The dependencies are:

 Graph <- Edges
 Graph <- Nodes
 Edge  <- Node, Node

Abstractions

The code defines a Node to hold edges. It works in the trivial case of binary trees, and in fairness a manifold of object oriented tutorials use a node object with left and right children to illustrate the wonders of object oriented programming.

For graphs in general, however, defining nodes to hold edges fights against the mathematical dependencies.

Code Review

There's a lot of code in the implementation and the author is not clear that it works. Of course testing is the way to determine if code works, but a large implementation of a simple algorithm suggests some areas for improvement.

Abstractions

Defining nodes to hold edges is driving code complexity. Instead of a graph being a compound of a simple structure holding a set of vertices and a simple structure holding a bag of edges a graph has become a list of complex Node objects.

• The node implementation hides the mathematic specification that we need to reason about the overall implementation of the algorithm.
• The graph implementation to the degree there is one doesn't expose graph semantics. It requires reasoning about graphs in terms of the implementation details of node.

The object hierarchy, instead of hiding the implementation details at the lower level of nodes and edges, exposes them at the higher level of the graph.

Redundancy

Redundancy occures in two forms, abstractions and data structures.

Abstractions

The decision to store edges at the node doesn't trump the mathematics. So the code still must deal with edges as edges and despite all the work to make nodes store edges, an edge data structure has to be maintained.

Data Structures

There are lists and arraylists, maps and hashmaps, etc. These are in addition to all the different object types. The multiplicity of data structures adds complexity and impedes reasoning in terms of the underlying mathematics of the algorithm.

Recommendations

1. Add tests to determine correctness of the implementation. Code review can uncover structural and syntactic issues, but given the abstractions it is near impossible to reason about the mathematics.

2. Consider refactoring the code to reflect the mathematical dependencies rather than building up from nodes.

3. Select a few data types: either Map or HashMap, either List or ArrayList, etc. This also means fewer object types.

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. -- Alan Perlis, Epigram 9

4. A graph as the primary data structure may offer some advantages when working with graphs.