Dijkstra { public static ArrayList<MapNode> bidirectional(MapGraph graph, int startnode, int endnode) throws Exception{ if (graph == null) throw new EmptyInputException("Leerer Graph uebergeben"); if (graph.getNode(startnode) == null || graph.getNode(endnode) == null || startnode == endnode) return new ArrayList<MapNode>(); HashMap<Integer,Vertex> nodes1 = new HashMap<Integer,Vertex>(); HashMap<Integer,Vertex> nodes2 = new HashMap<Integer,Vertex>(); PrQueue forward = new PrQueue(); PrQueue backward = new PrQueue(); Vertex start = new Vertex(graph.getNode(startnode),0,0); Vertex end = new Vertex(graph.getNode(endnode),0,0); nodes1.put(startnode,start); nodes2.put(endnode,end); forward.insert(start); backward.insert(end); while (forward.getSize() != 0 && backward.getSize() != 0){ boolean abort; abort = handleQueues(nodes1,forward,graph,nodes2,backward,true); if(abort) break; abort = handleQueues(nodes1,forward,graph,nodes2,backward,false); if(abort) break; } long distance = -1; Vertex meet = null; for (Vertex currentNode : nodes1.values()){ int ID = currentNode.node.getUID(); if (nodes2.containsKey(ID) == false){ continue; } if (distance == -1) { distance = nodes1.get(ID).getDist() + nodes2.get(ID).getDist(); meet = nodes1.get(ID); }else{ long newDist = nodes1.get(ID).getDist() + nodes2.get(ID).getDist(); if (distance > newDist){ distance = nodes1.get(ID).getDist() + nodes2.get(ID).getDist(); meet = nodes1.get(ID); } } } if (meet == null) return new ArrayList<MapNode>(); ArrayList<MapNode> route = new ArrayList<MapNode>(); route.add(graph.getNode(meet.node.getUID() ) ); Vertex pos = meet; while (pos.getPredecessor() != 0){ Vertex parent = nodes1.get(pos.getPredecessor()); route.add(0, graph.getNode(parent.node.getUID())); pos = parent; } pos = nodes2.get( meet.node.getUID()); while (pos.getPredecessor() != 0){ Vertex parent = nodes2.get(pos.getPredecessor()); route.add(graph.getNode(parent.node.getUID())); pos = parent; } if(debug){ logger.log("Dijkstra.biderectional","Vom Startknoten aus evaluiert: "+nodes1.values().size()); logger.log("Dijkstra.biderectional","Vom Zielknoten aus evaluiert: "+nodes2.values().size()); logger.log("Dijkstra.biderectional","Knoten auf der Route: "+route.size()); } return route; }  static long neighbourhood(HierarchyMapGraph graph, int startnode, byte level, boolean forward); static ArrayList<MapNode> bidirectional(MapGraph graph, int startnode, int endnode); static Path bidirectional(HierarchyMapGraph graph, int startnode, int endnode);  }
@Test public void testBidirectional() throws Exception { Config.fastestPathMode = false; ArrayList<MapNode> liste = null; MapGraph graph = null; String test; try { liste = Dijkstra.bidirectional(new MapGraph(new GPSCoordinate(50,-50),new GPSCoordinate(-50,50)), 5, 6); } catch (Exception e) { fail("Auf einem leeren Graohen wurde keine Exception geworfen"); } graph = randomGraph(50,0.3f,3); try { liste = Dijkstra.bidirectional(graph, 5, 100); } catch (Exception e) { fail("Bei nicht-existierendem Endknoten wurde eine Exception geworfen, statt einer leeren Liste auszugeben: "+e.getLocalizedMessage()); } if (liste.size() != 0) fail("Die Ausgabe ohne existerenden Endknoten sollte leer sein. Stattdessen gibt es so viele Elemente: "+liste.size()); graph.insertNode(10001, new GPSCoordinate(0,0)); try { liste = Dijkstra.bidirectional(graph, 5, 10001); } catch (Exception e) { fail("Bei nicht-erreichbaren Endknoten wurde eine Exception geworfen, statt einer leeren Liste auszugeben: "+e.getLocalizedMessage()); } if (liste.size() != 0) fail("Die Ausgabe sollte leer sein. Stattdessen gibt es so viele Elemente: "+liste.size()); try { liste = Dijkstra.bidirectional(graph, 5, 5); } catch (Exception e) { fail("Bei nicht-existierendem Endknoten wurde eine Exception geworfen, statt einer leeren Liste auszugeben: "+e.getLocalizedMessage()); } if (liste.size() != 0) fail("Die Ausgabe auf start=Ende sollte leer sein. Stattdessen gibt es so viele Elemente: "+liste.size()); graph = new MapGraph(new GPSCoordinate(50,-50),new GPSCoordinate(-50,50)); for(int i=1;i<9;i++) { graph.insertNode(i, new GPSCoordinate(i,i)); } graph.insertEdge(1, 2, 1, 1, StreetType.SECONDARY); graph.insertEdge(1, 3, 2, 1, StreetType.SECONDARY); graph.insertEdge(1, 4, 3, 5, StreetType.SECONDARY); graph.insertEdge(2, 3, 4, 2, StreetType.SECONDARY); graph.insertEdge(2, 4, 5, 3, StreetType.SECONDARY); graph.insertEdge(3, 5, 6, 6, StreetType.SECONDARY); graph.insertEdge(4, 6, 7, 1, StreetType.SECONDARY); graph.insertEdge(4, 5, 8, 1, StreetType.SECONDARY); graph.insertEdge(4, 7, 9, 4, StreetType.SECONDARY); graph.insertEdge(6, 7, 10, 2, StreetType.SECONDARY); graph.insertEdge(5, 7, 11, 3, StreetType.SECONDARY); graph.insertEdge(5, 8, 12, 5, StreetType.SECONDARY); graph.insertEdge(7, 8, 13, 2, StreetType.SECONDARY); Logger.getInstance().log("DijkstraTest","======"); liste = Dijkstra.bidirectional(graph, 1, 8); if (liste.size() != 6) fail("Ausgabeliste hat falsche Groesse - erwarte 6, habe: "+liste.size()); test = Pfad(liste); if (!test.equalsIgnoreCase("1-2-4-6-7-8")) fail("Die Reihenfolge der besuchten Knoten ist falsch. Erwarte: 1-2-4-6-7-8, habe: "+test); liste = Dijkstra.bidirectional(graph, 8, 1); if (liste.size() != 0) fail("Ausgabeliste hat falsche Groesse - erwarte 0, habe: "+liste.size()); graph = new MapGraph(new GPSCoordinate(50,-50),new GPSCoordinate(-50,50)); for(int i=1;i<9;i++) { graph.insertNode(i, new GPSCoordinate(i,i)); } weg(graph,1,2,1,1); weg(graph,1,3,2,1); weg(graph,1,4,3,5); weg(graph,2,3,4,2); weg(graph,2,4,5,3); weg(graph,3,5,6,6); weg(graph,4,6,7,1); weg(graph,4,5,8,1); weg(graph,4,7,9,4); weg(graph,6,7,10,2); weg(graph,5,7,11,3); weg(graph,5,8,12,5); weg(graph,7,8,13,2); liste = Dijkstra.bidirectional(graph, 1, 8); if (liste.size() != 6) fail("Ausgabeliste hat falsche Groesse - erwarte 6, habe: "+liste.size()); test = Pfad(liste); if (!test.equalsIgnoreCase("1-2-4-6-7-8")) fail("Die Reihenfolge der besuchten Knoten ist falsch. Erwarte: -1-2-4-6-7-8, habe: "+test); liste = Dijkstra.bidirectional(graph, 8, 1); if (liste.size() != 6) fail("Ausgabeliste hat falsche Groesse - erwarte 6, habe: "+liste.size()); test = Pfad(liste); if (!test.equalsIgnoreCase("8-7-6-4-2-1")) fail("Die Reihenfolge der besuchten Knoten ist falsch. Erwarte: 8-7-6-4-2-1, habe: "+test); liste = Dijkstra.bidirectional(graph, 1, 5); if (liste.size() != 4) fail("Ausgabeliste hat falsche Groesse - erwarte 3, habe: "+liste.size()); test = Pfad(liste); if (!test.equalsIgnoreCase("1-2-4-5")) fail("Die Reihenfolge der besuchten Knoten ist falsch. Erwarte: 1-4-5, habe: "+test); liste = Dijkstra.bidirectional(graph, 3, 4); if (liste.size() != 3) fail("Ausgabeliste hat falsche Groesse - erwarte 3, habe: "+liste.size()); test = Pfad(liste); if (!test.equalsIgnoreCase("3-2-4")) fail("Die Reihenfolge der besuchten Knoten ist falsch. Erwarte: 3-2-4, habe: "+test); liste = Dijkstra.bidirectional(graph, 7, 4); if (liste.size() != 3) fail("Ausgabeliste hat falsche Groesse - erwarte 3, habe: "+liste.size()); test = Pfad(liste); if (!test.equalsIgnoreCase("7-6-4")) fail("Die Reihenfolge der besuchten Knoten ist falsch. Erwarte: 7-6-4, habe: "+test); try { BelastungsTest(50,0.3f,3); BelastungsTest(100,0.3f,5); BelastungsTest(500,0.3f,5); BelastungsTest(1000,0.3f,5); BelastungsTest(5000,0.3f,5); } catch (Exception e) { fail("Es gab einen Fehler innerhalb der Belastungstests: "+e.getLocalizedMessage()); } MapGraph testGraph = null; OSMImporter osm_imp; try { osm_imp = new OSMImporter(new File("testdateien/DtestGraph.osm")); testGraph = osm_imp.getTile(osm_imp.getMapCenter(), 0); } catch (Exception e) { fail("Fehler beim Einlesen der DtestGraph: "+e.getLocalizedMessage()); } ArrayList<MapNode> myway = Dijkstra.bidirectional(testGraph, 3, 10); Logger.getInstance().log("DijkstraTest", "Die Laenge der Strecke ist: "+weglaenge(myway)); Logger.getInstance().log("DijkstraTest","Starte Gitter-Test (n=3)"); MapGraph Gittertest = GitterGraph(3); liste = Dijkstra.bidirectional(Gittertest, 1, 3*3); if (!(Pfad(liste).equals("1-2-5-6-9"))) fail("Der Algo ibt nicht auf dem Gitter die kuerzeste Route aus"); Logger.getInstance().log("DijkstraTest","Weglaenge (soll: 4): "+weglaenge(liste)); if (weglaenge(liste) != 4) fail("Der berechnete Weg ist nciht der kuerzeste!"); }
@Test public void testWeight() throws Exception { Config.fastestPathMode = true; int gr = 4; MapGraph weightGraph = GitterWeightGraph(gr); Logger.getInstance().log("DijkstraTest","Starte WeightGitter-Test (n="+gr+")"); ArrayList<MapNode> liste = Dijkstra.bidirectional(weightGraph, 1, gr*gr); Logger.getInstance().log("DijkstraTest","Weglaenge (soll: "+((2*gr)-2)*3+"): "+weglaengeStrict(liste)); Logger.getInstance().log("DijkstraTest", "WegGewicht: "+weglaenge(liste)); Logger.getInstance().log("DijkstraTest","Pfad: "+Pfad(liste)); if (weglaenge(liste) == ((2*gr)-2)*2) fail("Der berechnete Weg ist nciht der schnellste, sondern der kuerzeste"); if (weglaengeStrict(liste) != ((2*gr)-2)*3) fail("Der berechnete Weg ist nciht der schnellste. Soll:"+((2*gr)-2)*3+" Ist:"+weglaengeStrict(liste)); }