JGrapht : 해밀턴 사이클 프로그램이 getEdgeWeightException을 반환합니다.

Question

동적 완성 그래프를 만들고 각 정점을 한 번 방문하여 시작 정점부터 끝까지 최단 경로를 찾아야하는 코드 조각에 대해 작업 해 왔습니다. . 몇 가지 연구를 한 후 Hamiltonian Cycle 문제의 코드를 찾아 내 코드에 추가했습니다. 코드의 조각을 실행 한 후,이 얻을 :

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) 

참고 첫 번째 줄은 생성 된 난수를 출력하는 것이, 그 후 내가 확인과 시작에서 "최단 경로 후 끝 가장자리 '가중치를 인쇄 to end "그래프가 완성되었는지 확인하기 위해 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로 변경하는 것이 었습니다.