JGrapht：哈密尔顿循环程序返回getEdgeWeightException

Question

我一直在处理这段代码，我需要创建一个动态完整图并尝试通过访问每个顶点来查找从起始顶点到最终点的最短路径。经过一番研究，我发现了哈密尔顿循环问题的代码并将其添加到我的代码中。运行一段代码后，我得到这个：

run: 
6 
18.0 
19.0 
16.0 
18.0 
13.0 
20.0 
13.0 
15.0 
12.0 
18.0 
18.0 
12.0 
Exception in thread "AWT-EventQueue-0" java.lang.NullPointerException 
15.0 
15.0 
12.0 
Shortest path from START to END: 
15 
15 
at org.jgrapht.graph.AbstractBaseGraph.getEdgeWeight(AbstractBaseGraph.java:470) 
at org.jgrapht.graph.GraphDelegator.getEdgeWeight(GraphDelegator.java:292) 
at demoweightedgraph.DemoWeightedGraph.hamiltonianCycle(DemoWeightedGraph.java:147) 
at demoweightedgraph.DemoWeightedGraph.buildGraph(DemoWeightedGraph.java:98) 
at demoweightedgraph.DemoWeightedGraph.createAndShowGui(DemoWeightedGraph.java:45) 
at demoweightedgraph.DemoWeightedGraph.access$000(DemoWeightedGraph.java:34) 
at demoweightedgraph.DemoWeightedGraph$1.run(DemoWeightedGraph.java:69) 
at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:311) 
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:756) 
at java.awt.EventQueue.access$500(EventQueue.java:97) 
at java.awt.EventQueue$3.run(EventQueue.java:709) 
at java.awt.EventQueue$3.run(EventQueue.java:703) 
at java.security.AccessController.doPrivileged(Native Method) 
at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:80) 
at java.awt.EventQueue.dispatchEvent(EventQueue.java:726) 
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201) 
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116) 
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105) 
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101) 
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93) 
at java.awt.EventDispatchThread.run(EventDispatchThread.java:82) 
    BUILD SUCCESSFUL (total time: 1 second) 

注意，第一行打印生成的随机数，在这之后我打印边缘权重检查，并在“从开始的最短路径后结束结束“我打印（vertices.size（）*（vertices.size（） - 1）/ 2）和g.edgeSet（）。size（）来检查图是否完整。

这里是我的代码：

public class DemoWeightedGraph { 

    private static void createAndShowGui() { 


     JFrame frame = new JFrame("DemoGraph"); 
     frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
     frame.setSize(200,200); 
     int i = generateNumberByRange(4,6); 
     System.out.println(i); 

     ListenableGraph<String, MyEdge> g = buildGraph(i); 

     mxGraphAnalysis mga = mxGraphAnalysis.getInstance(); 


     JGraphXAdapter<String, MyEdge> graphAdapter = 
       new JGraphXAdapter<String, MyEdge>(g); 




     mxIGraphLayout layout = new mxCircleLayout(graphAdapter); 
     layout.execute(graphAdapter.getDefaultParent()); 

     frame.add(new mxGraphComponent(graphAdapter)); 

     frame.pack(); 
     //frame.setLocationByPlatform(true); 
     frame.setVisible(true); 
    } 

    public static void main(String[] args) { 
     SwingUtilities.invokeLater(new Runnable() { 
      public void run() { 
       createAndShowGui(); 
      } 
     }); 
    } 
    public static class MyEdge extends DefaultWeightedEdge { 
     @Override 
     public String toString() { 
      return String.valueOf(getWeight()); 
     } 
    } 

    public static ListenableGraph<String, MyEdge> buildGraph(int in) { 
     ListenableDirectedWeightedGraph<String, MyEdge> graph = 
      new ListenableDirectedWeightedGraph<String, MyEdge>(MyEdge.class); 

    for(int j=0;j<in;j++){ 
     graph.addVertex(String.valueOf(j)); 
    } 
    for (int i = 0; i < in; i++) { 
      for (int j = i + 1; j < in; j++) { 
       MyEdge e1 = graph.addEdge(String.valueOf(i),String.valueOf(j)); 
      graph.setEdgeWeight(e1, generateNumberByRange(10,20)); 
      System.out.println(graph.getEdgeWeight(e1)); 
      } 
     } 


     System.out.println("Shortest path from START to END:"); 

     List sp = hamiltonianCycle(graph); 
     // List shortest_path = DijkstraShortestPath.findPathBetween(graph,"1",String.valueOf(i)); 
     // for(int k=0; k< shortest_path.size(); k++){ 
     //  shortest_path.get(k); 
     // } 

     System.out.println(sp); 

     return graph; 
    } 
    public static int generateNumberByRange(int START, int END){ 
    return ThreadLocalRandom.current().nextInt(START, END + 1); 
    } 


    protected mxFibonacciHeap createPriorityQueue() 
     { 
     return new mxFibonacciHeap(); 
    } 
    public static <V, E> List<V> hamiltonianCycle(ListenableDirectedWeightedGraph<V, E> g) 
    { 
     List<V> vertices = new LinkedList<>(g.vertexSet()); 

     System.out.println((vertices.size() * (vertices.size() - 1)/2)); 
     System.out.println(g.edgeSet().size()); 



     // If the graph is not complete then return null since this algorithm 
     // requires the graph be complete 
     if ((vertices.size() * (vertices.size() - 1)/2) != g.edgeSet().size()) { 
      return null; 
     } 

     List<V> tour = new LinkedList<>(); 

     // Each iteration a new vertex will be added to the tour until all 
     // vertices have been added 
     while (tour.size() != g.vertexSet().size()) { 
      boolean firstEdge = true; 
      double minEdgeValue = 0; 
      int minVertexFound = 0; 
      int vertexConnectedTo = 0; 

      // A check will be made for the shortest edge to a vertex not within 
      // the tour and that new vertex will be added to the vertex 
      for (int i = 0; i < tour.size(); i++) { 
       V v = tour.get(i); 
       for (int j = 0; j < vertices.size(); j++) { 
        double weight = g.getEdgeWeight(g.getEdge(v, vertices.get(j))); 
        if (firstEdge || (weight < minEdgeValue)) { 
         firstEdge = false; 
         minEdgeValue = weight; 
         minVertexFound = j; 
         vertexConnectedTo = i; 
        } 
       } 
      } 
      tour.add(vertexConnectedTo, vertices.get(minVertexFound)); 
      vertices.remove(minVertexFound); 
     } 
     return tour; 

    } 
    } 

编辑：我有这个代码，唯一的问题是在hamiltoniancycle方法

Answer 1

对于那些你想知道谁的问题的getedgeweight方法我代码是我使用有向边而限制遍历的事实。解决方案是将其更改为ListenableUndirectedWeightedGraph。