Я смотрел и смотрел на это, и это сводит меня с ума.
Каким-то образом e = pq.poll( ); заставляет e иметь значение null во время теста для большого минимального связующего дерева. Крошечное минимальное остовное дерево работает.
Я очень благодарен за все намеки на эту проблему и на то, как решить такие проблемы, так как я чувствую, что я здесь над головой.
Спасибо за вашу помощь!
edit: кажется, моя очередь с приоритетами как-то пуста. Не могу понять, почему это хотя
: /
edit2: Я добавил класс DisjSet для дополнительной информации
public MyMiniGraph<T> generateMinimumSpanningTree()
{
int edgesAccepted = 0;
//give all nodes to a class representing disjoint sets
DisjSet<T> ds = new DisjSet<T>( theGraph.keySet() );
//set up a new graph to represent the minimum spanning tree
MyMiniGraph<T> minSpanTree = new MyMiniGraph<T>();
//initialize minSpanTree with all theGraphs nodes
Iterator<T> nodeIter = theGraph.keySet().iterator();
while(nodeIter.hasNext())
minSpanTree.addNode( nodeIter.next() );
//order all edges in theGraph in a priority queue
PriorityQueue<Edge> pq = new PriorityQueue<Edge>(allEdges);
Edge e;
// Kruskals algorithm. Accepts the smallest edges in order
// if they are not part of the same set which would cause a cycle.
while(edgesAccepted < currentSize-1)
{
e = pq.poll( );
T uset = ds.find( e.n1 );
T vset = ds.find( e.n2 );
if(uset != vset)
{
// Accept the edge
edgesAccepted++;
ds.union(uset, vset);
//if the edge is accepted, add it to minSpanTree
minSpanTree.connectNodes(e.n1, e.n2, e.cost);
}
}
return minSpanTree;
}
объявление класса и некоторые члены:
public class MyMiniGraph<T extends Comparable<? super T>> implements MiniGraph<T>
{
// The Graph containing all the nodes and their edges
private Map< T, HashSet<Edge> > theGraph = new HashMap< T, HashSet<Edge> >( );
// Keeps track of theGraphs current size
private int currentSize = 0;
// Keeps track of the current Edge quantity
private int numEdges = 0;
// TreeSet containing all edges
private TreeSet<Edge> allEdges = new TreeSet<Edge>();
// edge representing class with its associated nodes and weight
класс DisjSet:
import java.util.*;
public class DisjSet<K extends Comparable<? super K>>
{
//HashMap containing 1. K itself, 2. Ks parent. K no.2 is null if K has no parent
private HashMap<K,K> sets = new HashMap<K,K>();
public DisjSet(Set<K> s)
{
if(s.isEmpty())
throw new IllegalStateException("Empty DisjSet argument");
Iterator<K> nodes_iter = s.iterator();
while(nodes_iter.hasNext())
sets.put( nodes_iter.next(), null );
}
// recursive method to find o_nodes sets root node
public K find(K o_node)
{
if(sets.get(o_node) == null)
return o_node;
else
return find( sets.get(o_node) );
}
/**
* connects set 2 to set 1
* @param root1 root of set 1
* @param root2 root of set 2
*/
public void union( K root1, K root2)
{
sets.put(root2, root1);
}
}
Ошибка трассировки, если это поможет?:
java.lang.NullPointerException
at MyMiniGraph.generateMinimumSpanningTree(MyMiniGraph.java:274)
at MyMiniGraphTest.testGenerateMinimumSpanningTreeLarge(MyMiniGraphTest.java:401)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44)
at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15)
at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41)
at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20)
at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:76)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:50)
at org.junit.runners.ParentRunner$3.run(ParentRunner.java:193)
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:52)
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:191)
at org.junit.runners.ParentRunner.access$000(ParentRunner.java:42)
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:184)
at org.junit.runners.ParentRunner.run(ParentRunner.java:236)
at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:49)
at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)