Java - Creating Dynamic Vertex + Edges (Dijkstra Algorithm) -
i'm trying generate vertex + edges dynamically, i'm getting errors when try compute shortest path between coordinates.
testdijkstra3.java:
package maze_drawing; import java.io.filenotfoundexception; import java.io.printwriter; import java.io.unsupportedencodingexception; import java.util.priorityqueue; import java.util.list; import java.util.arraylist; import java.util.collections; class vertex implements comparable<vertex> { public final string name; public static string facedirection; public edge[] adjacencies; public double mindistance = double.positive_infinity; public vertex previous; public vertex(string argname) { name = argname; } public string tostring() { return name; } public int compareto(vertex other) { return double.compare(mindistance, other.mindistance); } } class edge { public final vertex target; public final string direction; public edge(vertex argtarget, string argdirection){ target = argtarget; direction = argdirection; } } public class testdijkstra3 { public static void computepaths(vertex source, string facedirection) { source.mindistance = 0; double turningweight = 0; string robotdirection = facedirection; priorityqueue<vertex> vertexqueue = new priorityqueue<vertex>(); vertexqueue.add(source); while (!vertexqueue.isempty()) { vertex u = vertexqueue.poll(); // visit each edge exiting u (edge e : u.adjacencies) { vertex v = e.target; //double weight = e.weight; string direction = e.direction; //direction destination double distancethroughu = u.mindistance + 10 + turningweight; if (distancethroughu < v.mindistance) { vertexqueue.remove(v); v.mindistance = distancethroughu ; v.previous = u; robotdirection = direction; vertexqueue.add(v); } } } } public static list<vertex> getshortestpathto(vertex target) { list<vertex> path = new arraylist<vertex>(); (vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); collections.reverse(path); return path; } public static void main(string args[]) throws filenotfoundexception, unsupportedencodingexception { int startx = 0; int starty = 0; int endx = 3; int endy = 3; string facing = "n"; string start = ""+startx+""+starty; string end = ""+endx+""+endy; vertex v00 = new vertex("00"); vertex v10 = new vertex("10"); vertex v20 = new vertex("20"); vertex v30 = new vertex("30"); vertex v40 = new vertex("40"); vertex v50 = new vertex("50"); vertex v60 = new vertex("60"); vertex v01 = new vertex("01"); vertex v11 = new vertex("11"); vertex v21 = new vertex("21"); vertex v31 = new vertex("31"); vertex v41 = new vertex("41"); vertex v51 = new vertex("51"); vertex v61 = new vertex("61"); vertex v02 = new vertex("02"); vertex v12 = new vertex("12"); vertex v22 = new vertex("22"); vertex v32 = new vertex("32"); vertex v42 = new vertex("42"); vertex v52 = new vertex("52"); vertex v62 = new vertex("62"); vertex v03 = new vertex("03"); vertex v13 = new vertex("13"); vertex v23 = new vertex("23"); vertex v33 = new vertex("33"); vertex v43 = new vertex("43"); vertex v53 = new vertex("53"); vertex v63 = new vertex("63"); vertex v04 = new vertex("04"); vertex v14 = new vertex("14"); vertex v24 = new vertex("24"); vertex v34 = new vertex("34"); vertex v44 = new vertex("44"); vertex v54 = new vertex("54"); vertex v64 = new vertex("64"); vertex v05 = new vertex("05"); vertex v15 = new vertex("15"); vertex v25 = new vertex("25"); vertex v35 = new vertex("35"); vertex v45 = new vertex("45"); vertex v55 = new vertex("55"); vertex v65 = new vertex("65"); vertex v06 = new vertex("06"); vertex v16 = new vertex("16"); vertex v26 = new vertex("26"); vertex v36 = new vertex("36"); vertex v46 = new vertex("46"); vertex v56 = new vertex("56"); vertex v66 = new vertex("66"); v00.adjacencies = new edge[]{ new edge(v10, "e"), new edge(v01, "n") }; v10.adjacencies = new edge[]{ new edge(v00, "s"), new edge(v20, "e") }; v20.adjacencies = new edge[]{ new edge(v10, "w"), new edge(v21, "n"), new edge(v30, "e") }; v30.adjacencies = new edge[]{ new edge(v20, "w"), new edge(v31, "n"), new edge(v40, "e") }; v40.adjacencies = new edge[]{ new edge(v30, "w"), new edge(v50, "e") }; v50.adjacencies = new edge[]{ new edge(v40, "w"), new edge(v51, "n") }; v60.adjacencies = new edge[]{ new edge(v61, "n") }; v01.adjacencies = new edge[]{ new edge(v02, "n"), new edge(v00, "s") }; v11.adjacencies = new edge[]{ new edge(v12, "n") }; v21.adjacencies = new edge[]{ new edge(v31, "e"), new edge(v20, "s") }; v31.adjacencies = new edge[]{ new edge(v21, "w"), new edge(v30, "s") }; v41.adjacencies = new edge[]{ new edge(v51, "e"), new edge(v42, "n") }; v51.adjacencies = new edge[]{ new edge(v50, "s"), new edge(v41, "w") }; v61.adjacencies = new edge[]{ new edge(v60, "s"), new edge(v62, "n") }; v02.adjacencies = new edge[]{ new edge(v01, "s"), new edge(v03, "n") }; v12.adjacencies = new edge[]{ new edge(v11, "s"), new edge(v13, "n"), new edge(v22, "e") }; v22.adjacencies = new edge[]{ new edge(v12, "w"), new edge(v32, "e") }; v32.adjacencies = new edge[]{ new edge(v22, "w"), new edge(v42, "e") }; v42.adjacencies = new edge[]{ new edge(v32, "w"), new edge(v41, "s"), new edge(v43, "n") }; v52.adjacencies = new edge[]{ new edge(v62, "e") }; v62.adjacencies = new edge[]{ new edge(v52, "w"), new edge(v61, "s"), new edge(v63, "n") }; v03.adjacencies = new edge[]{ new edge(v13, "e"), new edge(v02, "s"), new edge(v04, "n") }; v13.adjacencies = new edge[]{ new edge(v03, "w"), new edge(v23, "e"), new edge(v12, "s") }; v23.adjacencies = new edge[]{ new edge(v13, "w"), new edge(v33, "e") }; v33.adjacencies = new edge[]{ new edge(v34, "n"), new edge(v23, "w") }; v43.adjacencies = new edge[]{ new edge(v42, "s"), new edge(v44, "n"), new edge(v53, "e") }; v53.adjacencies = new edge[]{ new edge(v43, "w") }; v63.adjacencies = new edge[]{ new edge(v62, "s"), new edge(v64, "n") }; v04.adjacencies = new edge[]{ new edge(v05, "n"), new edge(v03, "s") }; v14.adjacencies = new edge[]{ new edge(v15, "n"), new edge(v24, "e") }; v24.adjacencies = new edge[]{ new edge(v14, "w"), new edge(v25, "n") }; v34.adjacencies = new edge[]{ new edge(v33, "s"), new edge(v35, "n") }; v44.adjacencies = new edge[]{ new edge(v45, "n"), new edge(v43, "s") }; v54.adjacencies = new edge[]{ new edge(v64, "e") }; v64.adjacencies = new edge[]{ new edge(v54, "w"), new edge(v65, "n"), new edge(v63, "s") }; v05.adjacencies = new edge[]{ new edge(v06, "n"), new edge(v04, "s") }; v15.adjacencies = new edge[]{ new edge(v14, "s") }; v25.adjacencies = new edge[]{ new edge(v26, "n"), new edge(v24, "s") }; v35.adjacencies = new edge[]{ new edge(v36, "n"), new edge(v34, "s") }; v45.adjacencies = new edge[]{ new edge(v55, "e"), new edge(v44, "s") }; v55.adjacencies = new edge[]{ new edge(v45, "w") }; v65.adjacencies = new edge[]{ new edge(v64, "s"), new edge(v66, "n") }; v06.adjacencies = new edge[]{ new edge(v16, "e"), new edge(v05, "s") }; v16.adjacencies = new edge[]{ new edge(v06, "w"), new edge(v26, "e") }; v26.adjacencies = new edge[]{ new edge(v16, "w"), new edge(v25, "s") }; v36.adjacencies = new edge[]{ new edge(v35, "s"), new edge(v46, "e") }; v46.adjacencies = new edge[]{ new edge(v36, "w"), new edge(v56, "e") }; v56.adjacencies = new edge[]{ new edge(v46, "w"), new edge(v66, "e") }; v66.adjacencies = new edge[]{ new edge(v56, "w"), new edge(v65, "s") }; vertex[] vertices = { v00, v10, v20, v30, v40, v50, v60, v01, v11, v21, v31, v41, v51, v61, v02, v12, v22, v32, v42, v52, v62, v03, v13, v23, v33, v43, v53, v63, v04, v14, v24, v34, v44, v54, v64, v05, v15, v25, v35, v45, v55, v65, v06, v16, v26, v36, v46, v56, v66 }; vertex[] vertices2 = new vertex[49]; system.out.println("start"); hentmazefil mazefile = new hentmazefil(); string linecoords; vertex v[] = new vertex[67]; string rest[] = new string[67]; string wholeline[] = new string[49]; (int = 0; < 49; i++) { linecoords = mazefile.nextlinecoords(); if (linecoords != null) { v[integer.parseint(linecoords.substring(0, 2))] = new vertex(linecoords.substring(0, 2)); rest[integer.parseint(linecoords.substring(0, 2))] = new string(linecoords.substring(2, 6)); wholeline[i] = linecoords; } else { system.out.println("line = null"); // end of while loop. break; } linecoords = mazefile.nextlinecoords(); // skipping "extra lines" linux files. } //system.out.println(vertices); //system.out.println(vertices2); string line; //adding edges (int = 0; < 49; i++) { line = wholeline[i]; v[integer.parseint(line.substring(0, 2))] = new vertex(line.substring(0, 2)); rest[integer.parseint(line.substring(0, 2))] = new string(line.substring(2, 6)); if (line.charat(2) == '0') { if (line.charat(3) == '0') { if (line.charat(4) == '0') { if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n") ,new edge (v[integer.parseint(line.substring(0, 2))+10], "e"), new edge (v[integer.parseint(line.substring(0, 2))-1], "s"), new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n") ,new edge (v[integer.parseint(line.substring(0, 2))+10], "e"), new edge (v[integer.parseint(line.substring(0, 2))-1], "s")}; } } else if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n") ,new edge (v[integer.parseint(line.substring(0, 2))+10], "e"), new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n") ,new edge (v[integer.parseint(line.substring(0, 2))+10], "e")}; } } else if (line.charat(4) == '0') { if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n"), new edge (v[integer.parseint(line.substring(0, 2))-1], "s"), new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n") , new edge (v[integer.parseint(line.substring(0, 2))-1], "s")}; } } else if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n") , new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+1], "n")}; } } else if (line.charat(3) == '0') { if (line.charat(4) == '0') { if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+10], "e"), new edge (v[integer.parseint(line.substring(0, 2))-1], "s"), new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+10], "e"), new edge (v[integer.parseint(line.substring(0, 2))-1], "s")}; } } else if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+10], "e"), new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))+10], "e")}; } } else if(line.charat(4) == '0') { if (line.charat(5) == '0') { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))-1], "s"), new edge (v[integer.parseint(line.substring(0, 2))-10], "w")}; } else { v[integer.parseint(line.substring(0, 2))].adjacencies = new edge[] {new edge (v[integer.parseint(line.substring(0, 2))-1], "s")}; } } }//end of loop int z = 0; (int = 0; < 67; i++) { if (v[i] != null) { vertices2[z] = v[i]; //system.out.println(vertices2[z]); z++; } } system.out.println("v[0] = "+v[0]); (edge e :v[0].adjacencies) { system.out.println("target: "+e.target); } system.out.println("v[1] = "+v[1]); (edge e :v[1].adjacencies) { system.out.println("target: "+e.target); } system.out.println("end"); (int = 0; < 49; i++) { if (vertices[i].tostring().equals(start)) { computepaths(vertices[i], facing); } } (int = 0; < 49; i++) { if (vertices[i].tostring().equals(end)) { system.out.println("distance " + vertices[i] + ": " + vertices[i].mindistance); list<vertex> path = getshortestpathto(vertices[i]); system.out.println("path: " + path); printwriter writer = new printwriter("traversalfile.txt", "utf-8"); (int j = 0; j < path.size()-1; j++) { int directionvalue = integer.parseint(path.get(j+1).tostring())-integer.parseint(path.get(j).tostring()); if (directionvalue == 1) { system.out.println("n"); writer.println("n"); } else if (directionvalue == 10) { system.out.println("e"); writer.println("e"); } else if (directionvalue == -1) { system.out.println("s"); writer.println("s"); } else if (directionvalue == -10) { system.out.println("w"); writer.println("w"); } else { system.out.println("something went wrong"); } } writer.close(); } } } } as see, there's 2 options along code: solution, hardcoded vertex + edges (first part), working fine, , more dynamic approach, read .txt file, , should convert these readings vertex + edges. error is, when change "vertices" --> "vertices2", in end of code, should use dynamic vertex method, , error: "start v[0] = 00 target: 01 target: 10 v[1] = 01 target: 02 target: 00 end exception in thread "main" java.lang.nullpointerexception @ maze_drawing.testdijkstra3.computepaths(testdijkstra3.java:60) @ maze_drawing.testdijkstra3.main(testdijkstra3.java:341) //this @ "computepaths(vertices2[i], facing);" java result: 1"
however, if run "vertices" (as in code above), result fine:
start v[0] = 00 target: 01 target: 10 v[1] = 01 target: 02 target: 00 end distance 33: 60.0 path: [00, 01, 02, 03, 13, 23, 33] n n n e e e
for reason, there must kind of difference, between "vertices" & "vertices2". if print them in loop, get:
output: v1: 00 v2: 00 v1: 10 v2: 01 v1: 20 v2: 02 v1: 30 v2: 03 v1: 40 v2: 04 ... etc
it goes wrong here:
int z = 0; (int = 0; < 67; i++) { if (v[i] != null) { vertices2[z] = v[i]; system.out.println(vertices2[z]); z++; } } so have 2 problems: 1. can't seem figure out how change above loop, read @10 first (see "newtestmap.map" how should look), , @1. 2. still think "computepath" should work, though arrays order kinda messed in vertices2, doesn't.
can see problem ?
thanks in advance.
hentmazefil.java :
package maze_drawing; import java.io.filenotfoundexception; import java.util.scanner; public class hentmazefil { java.io.file file; string linecoords; scanner input; public hentmazefil() { file = new java.io.file("newtestmap.map"); try { input = new scanner(file); } catch (filenotfoundexception ex) { system.out.println("file dont exist"); } } public string nextlinecoords() { if (input.hasnext()) { linecoords = input.nextline(); return linecoords; } return null; } } newtestmap.map:
000011 101010 200010 300010 401010 500110 600111 010101 110111 211001 311100 410011 511100 610101 020101 120001 221010 321010 420100 521011 620100 030001 131000 231010 330110 430001 531110 630101 040101 140011 240110 340101 440101 541011 640100 050101 151101 250101 350101 451001 551110 650101 061001 161010 261100 361001 461010 561010 661100
Comments
Post a Comment