patternjavaMinor
Kruskal's algorithm in Java
Viewed 0 times
javakruskalalgorithm
Problem
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
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> map;
private final Set edgeSet;
private final List edgeList;
public KruskalMSTFinder() {
this.map = new HashMap<>();
this.edgeSet = new LinkedHashSet<>();
this.edgeList = new ArrayList<>();
}
@Override
public List
findMinimumSpanningTree(final List graph,
final WeightFunction weightFunction) {
try {
prepareEdgeList(
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,
* null is returned.
*
* @param graph the graph.
* @param weightFuntion the weight function over the edges of
* graph.
* @return the list of edges comprising a minimum-spanning
* tree, or null if an error occurred.
*/
public List
findMinimumSpanningTree(final List 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> map;
private final Set edgeSet;
private final List edgeList;
public KruskalMSTFinder() {
this.map = new HashMap<>();
this.edgeSet = new LinkedHashSet<>();
this.edgeList = new ArrayList<>();
}
@Override
public List
findMinimumSpanningTree(final List graph,
final WeightFunction weightFunction) {
try {
prepareEdgeList(
Solution
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.
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.
Context
StackExchange Code Review Q#75249, answer score: 3
Revisions (0)
No revisions yet.