@Test public void testSingleNode() { final MutableUndirectedGraph<String> g = new MutableUndirectedGraph<>(); g.addNode("a"); final AStarOutput<String> output = AStar.aStar(g, "a", "a", edge -> 0, node -> 0); assertEquals(0, output.getTotalEstimatedDistance("a")); assertEquals(0, output.getDistanceSoFar("a")); assertNull(output.getPrevious("a")); }
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);  }