@Test public void testRegularCase() { final Map<Object, Integer> w = new HashMap<>(); final Map<Object, Integer> h = new HashMap<>(); final MutableUndirectedGraph<String> g = new MutableUndirectedGraph<>(); Stream.of("s", "a", "b", "c", "d", "e", "f", "g").forEach(g::addNode); h.put("s", 17); h.put("a", 10); h.put("b", 13); h.put("c", 4); h.put("d", 2); h.put("e", 4); h.put("f", 1); h.put("g", 0); w.put(g.addEdge("s", "a"), 6); w.put(g.addEdge("s", "b"), 5); w.put(g.addEdge("s", "c"), 10); w.put(g.addEdge("a", "e"), 6); w.put(g.addEdge("b", "e"), 6); w.put(g.addEdge("b", "d"), 7); w.put(g.addEdge("c", "d"), 6); w.put(g.addEdge("e", "f"), 4); w.put(g.addEdge("d", "f"), 6); w.put(g.addEdge("f", "g"), 3); final AStarOutput<String> output = AStar.aStar(g, "s", "g", w::get, h::get); assertNull(output.getPrevious("s")); assertEquals("s", output.getPrevious("b")); assertEquals("b", output.getPrevious("e")); assertEquals("e", output.getPrevious("f")); assertEquals("f", output.getPrevious("g")); }
public static <NODE, EDGE> AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic) { final AStarOutput<NODE> output = initializeOutput(graph, start, heuristic); final Collection<NODE> unprocessed = new LinkedList<>(); unprocessed.add(start); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparingInt(output::getTotalEstimatedDistance)); unprocessed.remove(current); if (current.equals(goal)) { break; } for (final Map.Entry<NODE, EDGE> adjacent : graph.successorsWithEdges(current).entrySet()) { final NODE next = adjacent.getKey(); final EDGE edgeToNext = adjacent.getValue(); final int edgeToNextDistance = weighter.applyAsInt(edgeToNext); final int alternativeDistance = output.getDistanceSoFar(current) + edgeToNextDistance; if (alternativeDistance < output.getDistanceSoFar(next)) { final int newTotalEstimatedDistance = alternativeDistance + heuristic.applyAsInt(next); output.setDistanceSoFar(next, alternativeDistance); output.setPrevious(next, current); output.setTotalEstimatedDistance(next, newTotalEstimatedDistance); unprocessed.add(next); } } } return output; }
AStar { public static <NODE, EDGE> AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic) { final AStarOutput<NODE> output = initializeOutput(graph, start, heuristic); final Collection<NODE> unprocessed = new LinkedList<>(); unprocessed.add(start); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparingInt(output::getTotalEstimatedDistance)); unprocessed.remove(current); if (current.equals(goal)) { break; } for (final Map.Entry<NODE, EDGE> adjacent : graph.successorsWithEdges(current).entrySet()) { final NODE next = adjacent.getKey(); final EDGE edgeToNext = adjacent.getValue(); final int edgeToNextDistance = weighter.applyAsInt(edgeToNext); final int alternativeDistance = output.getDistanceSoFar(current) + edgeToNextDistance; if (alternativeDistance < output.getDistanceSoFar(next)) { final int newTotalEstimatedDistance = alternativeDistance + heuristic.applyAsInt(next); output.setDistanceSoFar(next, alternativeDistance); output.setPrevious(next, current); output.setTotalEstimatedDistance(next, newTotalEstimatedDistance); unprocessed.add(next); } } } return output; } }
AStar { public static <NODE, EDGE> AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic) { final AStarOutput<NODE> output = initializeOutput(graph, start, heuristic); final Collection<NODE> unprocessed = new LinkedList<>(); unprocessed.add(start); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparingInt(output::getTotalEstimatedDistance)); unprocessed.remove(current); if (current.equals(goal)) { break; } for (final Map.Entry<NODE, EDGE> adjacent : graph.successorsWithEdges(current).entrySet()) { final NODE next = adjacent.getKey(); final EDGE edgeToNext = adjacent.getValue(); final int edgeToNextDistance = weighter.applyAsInt(edgeToNext); final int alternativeDistance = output.getDistanceSoFar(current) + edgeToNextDistance; if (alternativeDistance < output.getDistanceSoFar(next)) { final int newTotalEstimatedDistance = alternativeDistance + heuristic.applyAsInt(next); output.setDistanceSoFar(next, alternativeDistance); output.setPrevious(next, current); output.setTotalEstimatedDistance(next, newTotalEstimatedDistance); unprocessed.add(next); } } } return output; }  }
AStar { public static <NODE, EDGE> AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic) { final AStarOutput<NODE> output = initializeOutput(graph, start, heuristic); final Collection<NODE> unprocessed = new LinkedList<>(); unprocessed.add(start); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparingInt(output::getTotalEstimatedDistance)); unprocessed.remove(current); if (current.equals(goal)) { break; } for (final Map.Entry<NODE, EDGE> adjacent : graph.successorsWithEdges(current).entrySet()) { final NODE next = adjacent.getKey(); final EDGE edgeToNext = adjacent.getValue(); final int edgeToNextDistance = weighter.applyAsInt(edgeToNext); final int alternativeDistance = output.getDistanceSoFar(current) + edgeToNextDistance; if (alternativeDistance < output.getDistanceSoFar(next)) { final int newTotalEstimatedDistance = alternativeDistance + heuristic.applyAsInt(next); output.setDistanceSoFar(next, alternativeDistance); output.setPrevious(next, current); output.setTotalEstimatedDistance(next, newTotalEstimatedDistance); unprocessed.add(next); } } } return output; }  static AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic); }
AStar { public static <NODE, EDGE> AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic) { final AStarOutput<NODE> output = initializeOutput(graph, start, heuristic); final Collection<NODE> unprocessed = new LinkedList<>(); unprocessed.add(start); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparingInt(output::getTotalEstimatedDistance)); unprocessed.remove(current); if (current.equals(goal)) { break; } for (final Map.Entry<NODE, EDGE> adjacent : graph.successorsWithEdges(current).entrySet()) { final NODE next = adjacent.getKey(); final EDGE edgeToNext = adjacent.getValue(); final int edgeToNextDistance = weighter.applyAsInt(edgeToNext); final int alternativeDistance = output.getDistanceSoFar(current) + edgeToNextDistance; if (alternativeDistance < output.getDistanceSoFar(next)) { final int newTotalEstimatedDistance = alternativeDistance + heuristic.applyAsInt(next); output.setDistanceSoFar(next, alternativeDistance); output.setPrevious(next, current); output.setTotalEstimatedDistance(next, newTotalEstimatedDistance); unprocessed.add(next); } } } return output; }  static AStarOutput<NODE> aStar(final Graph<NODE, EDGE> graph, final NODE start, final NODE goal, final ToIntFunction<EDGE> weighter, final ToIntFunction<NODE> heuristic);  }