JGrapht: Hamiltonian Cycle Program retourne getEdgeWeightException

Question

J'ai travaillé sur ce morceau de code où je vais devoir créer un graphe dynamique complet et essayer de trouver le chemin le plus court du sommet de départ jusqu'à la fin en visitant chaque sommet une fois . Après quelques recherches, j'ai trouvé le code pour le problème Hamiltonian Cycle et l'ai ajouté à mon code. Après avoir exécuté le morceau de code, je reçois ceci:

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) 

Notez que la première ligne affiche le nombre aléatoire généré, après que j'imprimer les poids des bords pour le contrôle et à la fin après le « chemin le plus court de début pour finir "J'imprime (vertices.size() * (vertices.size() - 1)/2) et g.edgeSet(). size() pour vérifier si le graphe est complet.

Voici mon 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: Le seul problème que j'ai avec ce code est la méthode getedgeweight dans la méthode hamiltoniancycle

Answer 1

Pour ceux d'entre vous qui veulent connaître le problème avec mon le code est le fait que j'utilise des bords dirigés alors que cela limite la traversée. La solution était de le changer en ListenableUndirectedWeightedGraph.