JGrapht: Hamiltonian Cycle-Programm gibt getEdgeWeightException zurück

Question

Ich habe an diesem Stück Code gearbeitet, wo ich ein dynamisches vollständiges Diagramm erstellen und versuchen muss, den kürzesten Pfad vom Start-Scheitelpunkt bis zum Ende zu finden, indem ich jeden Scheitelpunkt einmal besuche . Nach einigen Recherchen habe ich den Code für das Hamilton-Zyklus-Problem gefunden und zu meinem Code hinzugefügt. Ich das Stück Code, nach dem Laufen, erhalten diese:

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) 

Beachten Sie, dass die erste Zeile gibt die Zufallszahl generiert, nachdem das Drucken i die Gewichte Kanten zur Kontrolle und am Ende nach dem „kürzesten Weg von Anfang Um zu beenden "drucke ich (vertices.size() * (vertices.size() - 1)/2) und g.edgeSet(). size(), um zu prüfen, ob der Graph vollständig ist.

Hier ist mein Code:

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; 

    } 
    } 

EDIT: Das einzige Problem, das ich mit diesem Code haben die getedgeweight Methode in der hamiltoniancycle Methode ist

Answer 1

Für diejenigen, die mit dem Problem wissen möchte code ist die Tatsache, dass ich gerichtete Kanten verwende, während das den traverse begrenzt. Die Lösung bestand darin, es in ListenableUndirectedWeightedGraph zu ändern.