Dijkstra { public static long neighbourhood(HierarchyMapGraph graph, int startnode, byte level, boolean forward) throws Exception{ if (graph == null) throw new EmptyInputException("Leerer Graph uebergeben"); if (graph.getNode(startnode) == null) throw new InvalidInputException("Ungueltige ID uebergeben"); int found = -1; final HashMap<Integer,Vertex> nodes = new HashMap<Integer,Vertex>(); final PrQueue queue = new PrQueue(); final Vertex start = new Vertex(graph.getNode(startnode),0); nodes.put(startnode, start); queue.insert(start); while (queue.getSize() != 0){ final Vertex node = queue.extractMin(); final HierarchyMapNode realNode = (HierarchyMapNode) node.node; found++; if (found == Config.H) return node.getDist(); Iterator <HierarchyMapEdge> edges = null; if (forward){ edges = realNode.getOutgoingEdgesByHierarchy(level).iterator(); }else{ edges = realNode.getIncomingEdgesByHierarchy(level).iterator(); } while (edges.hasNext()){ final HierarchyMapEdge newEdge = edges.next(); updateNeighbours(nodes, queue, newEdge, node, forward); } } return -1; }  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 testNeighbourhoodShort() throws Exception { double test = 0; boolean fehler; Config.fastestPathMode = false; fehler = false; try{ test = Dijkstra.neighbourhood(test3, 55,(byte)0, true); }catch(Exception e) { fehler = true; } if (fehler == false){ fail("Test 2: Bei Eingabe einer ungueltigen Node-ID wurde keine Exception geworfen"); } test = Dijkstra.neighbourhood(test3, 2, (byte)0,true); if (test != -1) fail("Test 3: Die vorwaerts-scuhe auf einem isolierten Knoten liefert nicht -1 sondern: "+test); test = Dijkstra.neighbourhood(test3, 2,(byte)0, false); if (test != -1) fail("Test 4: Die ruekwaerts-scuhe auf einem isolierten Knoten liefert nicht -1 sondern: "+test); test = Dijkstra.neighbourhood(test5, 5, (byte)0,true); if (test != -1) fail("Test 5: Die vorwaerts-scuhe auf einem isolierten Knoten bzql. ausgehender Knoten liefert nicht -1 sondern: "+test); test = Dijkstra.neighbourhood(test5, 2, (byte)0,false); if (test != -1) fail("Test 6: Die rueck.-scuhe auf einem isolierten Knoten bzql. eingehender Knoten liefert nicht -1 sondern: "+test); fehler = false; try{ test = Dijkstra.neighbourhood(new HierarchyMapGraph(), 5, (byte)0,true); }catch(Exception e){ fehler = true; } if (fehler == false) fail("Test 7: Der leere Graph liefert nicht -1 sondern: "+test); Config.H = 2; test = Dijkstra.neighbourhood(testGraph1, 1,(byte)0, true); if (test != 1) fail("TestGraph1: Der Algo liefert nicht 1 sondern: "+test); Config.H = 2; test = Dijkstra.neighbourhood(testGraph2, 1,(byte)0, true); if (test != 2) fail("TestGraph2: Der Algo liefert nicht 2 sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph2, 1, (byte)0,true); if (test != 3) fail("TestGraph2: Der Algo liefert nicht 3 sondern: "+test); Config.H = 5; test = Dijkstra.neighbourhood(testGraph2, 1,(byte)0, true); if (test != 10) fail("TestGraph2: Der Algo liefert nicht 10 sondern: "+test); Config.H = 6; test = Dijkstra.neighbourhood(testGraph2, 1, (byte)0,true); if (test != -1) fail("TestGraph2: Der Algo liefert nicht -1 sondern: "+test); Config.H = 3; test = Dijkstra.neighbourhood(testGraph3, 1, (byte)0,true); if (test != 1000) fail("TestGraph3: Der Algo liefert nicht 1000 sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph3, 1, (byte)0,true); if (test != -1) fail("TestGraph3: Der Algo liefert nicht -1 sondern: "+test); Config.H = 2; test = Dijkstra.neighbourhood(testGraph4, 1,(byte)0, true); if (test != 2) fail("TestGraph4: Der Algo liefert nicht 2 sondern: "+test); Config.H = 3; test = Dijkstra.neighbourhood(testGraph4, 1,(byte)0, true); if (test != 3) fail("TestGraph4: Der Algo liefert nicht 3 sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph4, 1, (byte)0,true); if (test != -1) fail("TestGraph4: Der Algo liefert nicht -1 sondern: "+test+" evtl. Knoten doppelt begangen?"); Config.H = 2; test = Dijkstra.neighbourhood(testGraph4, 2, (byte)0,false); if (test != 1) fail("TestGraph4: Der Algo(false) liefert nicht 1 sondern: "+test); Config.H = 3; test = Dijkstra.neighbourhood(testGraph4, 2,(byte)0, false); if (test != -1) fail("TestGraph4: Der Algo(false) liefert nicht -1 sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph4, 2,(byte)0, false); if (test != -1) fail("TestGraph4: Der Algo(false) liefert nicht -1 sondern: "+test+" evtl. Knoten doppelt begangen?"); }
@Test public void testNeighbourhoodFast() throws Exception { long test = 0; boolean fehler; Config.fastestPathMode = true; fehler = false; try{ test = Dijkstra.neighbourhood(test3, 55,(byte)0, true); }catch(Exception e) { fehler = true; } if (fehler == false){ fail("Test 2: Bei Eingabe einer ungueltigen Node-ID wurde keine Exception geworfen"); } test = Dijkstra.neighbourhood(test3, 2, (byte)0,true); if (test != -1) fail("Test 3: Die vorwaerts-scuhe auf einem isolierten Knoten liefert nicht -1 sondern: "+test); test = Dijkstra.neighbourhood(test3, 2,(byte)0, false); if (test != -1) fail("Test 4: Die ruekwaerts-scuhe auf einem isolierten Knoten liefert nicht -1 sondern: "+test); test = Dijkstra.neighbourhood(test5, 5, (byte)0,true); if (test != -1) fail("Test 5: Die vorwaerts-scuhe auf einem isolierten Knoten bzql. ausgehender Knoten liefert nicht -1 sondern: "+test); test = Dijkstra.neighbourhood(test5, 2, (byte)0,false); if (test != -1) fail("Test 6: Die rueck.-scuhe auf einem isolierten Knoten bzql. eingehender Knoten liefert nicht -1 sondern: "+test); fehler = false; try{ test = Dijkstra.neighbourhood(new HierarchyMapGraph(), 5, (byte)0,true); }catch(Exception e){ fehler = true; } if (fehler == false) fail("Test 7: Der leere Graph liefert nicht -1 sondern: "+test); Config.H = 2; test = Dijkstra.neighbourhood(testGraph1, 1,(byte)0, true); if (test!= 1*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph1: Der Algo liefert nicht "+1*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 2; test = Dijkstra.neighbourhood(testGraph2, 1,(byte)0, true); if (test!= 2*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph2: Der Algo liefert nicht "+2*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph2, 1, (byte)0,true); if (test!= 3*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph2: Der Algo liefert nicht "+3*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 5; test = Dijkstra.neighbourhood(testGraph2, 1,(byte)0, true); if (test!= 10*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph2: Der Algo liefert nicht "+10*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 6; test = Dijkstra.neighbourhood(testGraph2, 1, (byte)0,true); if (test != -1) fail("TestGraph2: Der Algo liefert nicht -1 sondern: "+test); Config.H = 3; test = Dijkstra.neighbourhood(testGraph3, 1, (byte)0,true); if (test!= 1000*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph3: Der Algo liefert nicht "+1000*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph3, 1, (byte)0,true); if (test != -1) fail("TestGraph3: Der Algo liefert nicht -1 sondern: "+test); Config.H = 2; test = Dijkstra.neighbourhood(testGraph4, 1,(byte)0, true); if (test!= 2*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph4: Der Algo liefert nicht "+2*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 3; test = Dijkstra.neighbourhood(testGraph4, 1,(byte)0, true); if (test!= 3*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph4: Der Algo liefert nicht "+3*Config.getSpeedFactor(StreetType.MOTORWAY)*10000+" sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph4, 1, (byte)0,true); if (test != -1) fail("TestGraph4: Der Algo liefert nicht -1 sondern: "+test+" evtl. Knoten doppelt begangen?"); Config.H = 2; test = Dijkstra.neighbourhood(testGraph4, 2, (byte)0,false); if (test!= 1*Config.getSpeedFactor(StreetType.MOTORWAY)) fail("TestGraph4: Der Algo(false) liefert nicht 1 sondern: "+test); Config.H = 3; test = Dijkstra.neighbourhood(testGraph4, 2,(byte)0, false); if (test != -1) fail("TestGraph4: Der Algo(false) liefert nicht -1 sondern: "+test); Config.H = 4; test = Dijkstra.neighbourhood(testGraph4, 2,(byte)0, false); if (test != -1) fail("TestGraph4: Der Algo(false) liefert nicht -1 sondern: "+test+" evtl. Knoten doppelt begangen?"); }