I've been working on this piece of code where i'll need to create a dynamic complete graph and try to find the shortest path from the start vertex to the end by visiting each vertex once. After some research I've found the code for the Hamiltonian Cycle problem and added it to my code. After running the piece of code, I get this :
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)
Note that the first line prints the random number generated, after that i print the edges' weights for checking and at the end after the "shortest path from Start to End" I print (vertices.size() * (vertices.size() - 1) / 2) and g.edgeSet().size() to check if the graph is complete.
Here is my 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: The only problem i have with this code is the getedgeweight method in the hamiltoniancycle method
