A* search in Java and Ada

astar.adb

-- compile it: (small)
-- gnatmake -O2 astar.adb -bargs -largs -s
-- (normal)
-- gnatmake astar.adb
-- run in cmd (not powershell)
-- type input.txt | astar.exe
-- using powershell:
-- Invoke-command "gnatmake astar.adb && type input.txt | astar.exe"
-- or simply run:
-- build-run.bat
-- or
-- build_run.ps1
-- or
-- build_run.sh
-- to clean folder: gnatclean

with Ada.Text_IO;
with Ada.Integer_Text_IO;
with Ada.Containers;
with Ada.Strings.Hash;
with Ada.Containers.Vectors;
with graphs;

procedure astar is
	package tio renames Ada.Text_IO;
	package nio renames Ada.Integer_Text_IO;

	type Dimension is range 1 .. 10;
	subtype Risk_level is Integer range 1 .. 10;
	type Risk_Map is array(Dimension, Dimension) of Risk_level;
	type Dir is (Up, Left, Down, Right);

	type Coord is record
		x, y: Dimension;
		risk: Risk_level;
	end record;

	function "=" (c1, c2: in Coord) return Boolean is
		(c1.x = c2.x and c1.y = c2.y and c1.risk = c2.risk);

	function Cycle(c: in Coord) return Boolean is (false);

	function To_String(c: in Coord) return String is
		("((" & c.x'image & ',' & c.y'image & ") =>" & c.risk'image & ')');

	function Hash(c: in Coord) return Ada.Containers.Hash_Type is
		(Ada.Strings.Hash(To_String(c)));

	cave: Risk_Map := (others => (others => 1));

	package Move_Graph is new Graphs
		(Index_Type => Positive, Node_Type => Coord, Is_Cycle => Cycle);
	package mg renames Move_Graph;

	cave_graph: mg.Graph;

	procedure Read_Map is
		line: String(1..11);
		length: Natural;
		last: Positive;
	begin
		for I in Dimension loop
			begin
				tio.Get_Line(line, length);
			exception
				when tio.Data_Error => exit;
				when tio.End_Error => exit;
			end;
			exit when length = 0 or length > Integer(Dimension'last);
			for J in Dimension loop
				nio.Get(line(Integer(J)) & "", cave(I, J), last);
			end loop;
		end loop;
	end Read_Map;

	procedure Populate_Graph is
		edge: mg.Edge;
		co1, co2: Coord;
	begin
		for I in Dimension loop
			for J in Dimension loop
				co1 := (I, J, cave(I, J));
				mg.Add(cave_graph, co1);
				if Integer(I) - 1 >= Integer(Dimension'first) then
					co2 := (I-1, J, cave(I-1, J));
					edge := (co1, co2);
					mg.Add(cave_graph, co2);
					mg.Add(cave_graph, edge);
				end if;
				if Integer(I) + 1 <= Integer(Dimension'last) then
					co2 := (I+1, J, cave(I+1, J));
					edge := (co1, co2);
					mg.Add(cave_graph, co2);
					mg.Add(cave_graph, edge);
				end if;
				if Integer(J) - 1 >= Integer(Dimension'first) then
					co2 := (I, J-1, cave(I, J-1));
					edge := (co1, co2);
					mg.Add(cave_graph, co2);
					mg.Add(cave_graph, edge);
				end if;
				if Integer(J) + 1 <= Integer(Dimension'last) then
					co2 := (I, J+1, cave(I, J+1));
					edge := (co1, co2);
					mg.Add(cave_graph, co2);
					mg.Add(cave_graph, edge);
				end if;
			end loop;
		end loop;
	end;
	start_Node : Coord;
	end_Node : Coord;
	paths: mg.nv.Vector;

	function Zero_Cost return Integer is (0);
	function Cost(c1, c2: in Coord) return Integer is (c2.risk);
	function Distance(c1, c2: in Coord) return Integer is
		(abs(Integer(c1.x) - Integer(c2.x)) + abs(Integer(c1.y) - Integer(c2.y)));
	function Dijkstra_search is new mg.Uniform_Search
		(Cost_Type => Natural);
	function A_star is new mg.A_Star_Search
		(Cost_Type => Natural);
begin
	Read_Map;
	start_Node := (Dimension'first, Dimension'first,
	cave(Dimension'first, Dimension'first));
	end_Node := (Dimension'last, Dimension'last,
	cave(Dimension'last, Dimension'last));
	Populate_Graph;
	for I in Dimension loop
		for J in Dimension loop
			tio.Put(cave(I, J)'image);
		end loop;
		tio.New_Line;
	end loop;
	for C in cave_graph.nodes.Iterate loop
		tio.Put(To_String(mg.Nodes_vector.Element(C)) & ", ");
	end loop;
	tio.Put_Line("The total nodes are" & Integer(cave_graph.nodes.Length)'image);
	declare
		edge: mg.Edge;
	begin
		for E in cave_graph.edges.Iterate loop
			edge := mg.Edges_vector.Element(E);
			tio.Put_Line(To_String(edge.Node1) & " => " & To_String(edge.Node2));
		end loop;
	end;
	tio.Put_Line ("The total edges are" & Integer(cave_graph.edges.Length)'image);
	tio.Put_Line("A_Star_Search");
	paths := A_Star(cave_graph, start_Node, end_Node);
	declare
		total_cost: Natural := 0;
	begin
		for V in paths.Iterate loop
			tio.Put_Line(To_String(paths(V)));
			if mg.nv.To_Index(V) /= paths.First_Index then
				total_cost := total_cost + paths(V).risk;
			end if;
		end loop;
		tio.Put_Line("The total risk path is" & total_cost'image);

		total_cost := 0;
		tio.New_Line;
		tio.Put_Line("Dijkstra_search");
		paths := Dijkstra_search(cave_graph, start_Node, end_Node);
		for V in paths.Iterate loop
			tio.Put_Line(To_String(paths(V)));
			if mg.nv.To_Index(V) /= paths.First_Index then
				total_cost := total_cost + paths(V).risk;
			end if;
		end loop;
		tio.Put_Line("The total risk path is" & total_cost'image);
	end;
end astar;

AstarMain.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

/*
Compile and run:
$ javac *.java
$ java AstarMain < input.txt

or simply:
build-run-java.bat
or:
build_run_java.ps1
*/

class CoordCost implements Comparable<CoordCost>, Addable<CoordCost>, Copyable<CoordCost> {
	int value;
	public int compareTo(CoordCost other) {
		return Integer.compare(value, other.value);
	}

	CoordCost(int value) {
		this.value = value;
	}

	public void addFrom(CoordCost other) {
		this.value += other.value;
	}

	public String toString() {
		return String.format("%3d", value);
	}

	public CoordCost copy() {
		return new CoordCost(value);
	}

	static final CoordCost zeroCost = new CoordCost(0);
}

class Coord implements Cycleable, Comparable<Coord>, Costable<Coord, CoordCost> {
	int x, y;
	CoordCost risk;
	public Coord(int x, int y, CoordCost risk) {
		this.x = x;
		this.y = y;
		this.risk = risk;
	}

	public CoordCost zeroCost() { return new CoordCost(0); }
	public CoordCost cost(Coord otherVertex) {
		return otherVertex.risk;
	}
	public boolean isCycle() { return false; }

	public int compareTo(Coord other) {
		if (x == other.x && y == other.y && risk.compareTo(other.risk) == 0) {
			return 0;
		} else if (x < other.x || y < other.y || risk.compareTo(other.risk) < 0) {
			return -1;
		} else {
			return 1;
		}
	}

	public CoordCost distanceTo(Coord targetVertex) {
		return new CoordCost(
				Math.abs(x - targetVertex.x) +
				Math.abs(y - targetVertex.y));
	}

	public String toString() {
		return String.format("((%2d, %2d) => %2d)", x, y, risk.value);
	}
}

public class AstarMain {
	public static void main(String[] args) {
		var maplist = new ArrayList<ArrayList<Coord>>();
		var buf = new BufferedReader(new InputStreamReader(System.in));
		var atomicj = new AtomicInteger(1);
		var atomici = new AtomicInteger(1);
		var graph = new Graph<Coord, CoordCost>();
		try {
			while(true) {
				var s = buf.readLine();
				if (s == null || s.isEmpty()) break;
				var row = s.
					chars().
					mapToObj(c -> new Coord(
								atomici.get(),
								atomicj.getAndIncrement(),
								new CoordCost(c - '0'))).
					collect(Collectors.toCollection(ArrayList<Coord>::new));
				atomicj.set(1);
				atomici.incrementAndGet();
				maplist.add(row);
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
		for (var i = 0; i < maplist.size(); i++) {
			var row = maplist.get(i);
			for (var j = 0; j < row.size(); j++) {
				System.out.print(row.get(j).risk.value);
			}
			System.out.println();
		}

		populateGraph(graph, maplist);
		/*
		for (var node : graph.nodes.toArray(Coord[]::new)) {
			System.out.println(node);
		}
		*/

		System.out.println("edges length: " + graph.edges.size());
		var count = 1;
		for (var edge : graph.edges.toArray(Graph.Edge[]::new)) {
			System.out.printf("edge %3d %s\n", count++, edge);
		}

		System.out.println();
		var start = maplist.get(0).get(0);
		var end = maplist.get(maplist.size()-1).get(maplist.get(0).size()-1);
		var paths = graph.AStar(start, end);
		System.out.println("\ntotal path nodes: " + paths.size());
		System.out.println("AStar:");
		for (var node : paths.toArray(Coord[]::new)) {
			System.out.println(node);
		}
		var total = 0;
		for (var i = 1; i < paths.size(); i++) {
			total += paths.get(i).risk.value;
		}
		System.out.println("Total risk: " + total);
	}

	static void populateGraph(Graph<Coord, CoordCost> graph,
			ArrayList<ArrayList<Coord>> maplist)
	{
		var colsize = maplist.size();
		for (var y = 0; y < colsize; y++) {
			var rowsize = maplist.get(y).size();
			for (var x = 0; x < rowsize; x++) {
				graph.addVertex(maplist.get(y).get(x));
				if (x - 1 >= 0) {
					graph.addVertex(maplist.get(y).get(x-1));
					graph.addEdge(maplist.get(y).get(x), maplist.get(y).get(x-1));
				}
				if (x + 1 < rowsize) {
					graph.addVertex(maplist.get(y).get(x+1));
					graph.addEdge(maplist.get(y).get(x), maplist.get(y).get(x+1));
				}

				if (y - 1 >= 0) {
					graph.addVertex(maplist.get(y-1).get(x));
					graph.addEdge(maplist.get(y).get(x), maplist.get(y-1).get(x));
				}
				if (y + 1 < rowsize) {
					graph.addVertex(maplist.get(y+1).get(x));
					graph.addEdge(maplist.get(y).get(x), maplist.get(y+1).get(x));
				}
			}
		}
	}
}

build-run-java.bat

javac *.java
java AstarMain < input.txt

build-run.bat

gnatmake astar.adb
type input.txt | astar.exe

build_run.ps1

Invoke-command 'gnatmake astar.adb && type input.txt | astar.exe'

build_run.sh

gnatmake astar.adb
./astar < input.txt

build_run_java.ps1

Invoke-command "javac *.java && java AstarMain < input.txt"

build_run_java.sh

javac *.java
java AstarMain < input.txt

graph.adb

with Ada.Text_IO;
with Ada.Containers.Hashed_Maps;
with Ada.Containers.Synchronized_Queue_Interfaces;
with Ada.Containers.Unbounded_Priority_Queues;

package body graphs is
	package tio renames Ada.Text_IO;
	function "="(E1, E2: in Edge) return Boolean is
		((E1.Node1 = E2.Node1 and E1.Node2 = E2.Node2) or
		(E1.Node1 = E2.Node2 and E1.Node2 = E2.Node1));

	function Nodes(g: in Graph) return nv.Vector is (g.nodes);
	function Edges(g: in Graph) return ev.Vector is (g.edges);

	procedure Add(g: in out Graph; V: in Node_Type) is
	begin
		if g.nodes.Contains(V) then return; end if;
		g.nodes.Append(V);
	end Add;

	procedure Add(g: in out Graph; E: in Edge) is
	begin
		if g.edges.Contains(E) then return; end if;
		g.edges.Append(E);
	end Add;

	function Contains(g: in Graph; V: in Node_Type) return Boolean is
		(g.nodes.Contains(V));
	function Contains(g: in Graph; E: in Edge) return Boolean is
		(g.edges.Contains(E));
	function Contains(E: in Edge; V: in Node_Type) return Boolean is
		(V = E.Node1 or V = E.Node2);

	function Neighbors(g: in Graph; V: in Node_Type) return nv.Vector is
		acc: nv.Vector;
	begin
		for I in g.edges.First_Index .. g.edges.Last_Index loop
			if Contains(g.edges(I), V) then
				acc.Append(neighbor(g.edges(I), V));
			end if;
		end loop;
		return acc;
	end Neighbors;

	function Neighbor(E: in Edge; V: in Node_Type) return Node_Type is
	begin
		if V = E.Node1 then
			return E.Node2;
		else
			return E.Node1;
		end if;
	end Neighbor;

	procedure Trail(Vs: in nv.Vector; prompt: String := "") is
	begin
		if prompt /= "" then
			tio.Put_Line(prompt);
		end if;
		tio.Put("    ");
		for I in Vs.First_Index .. Vs.Last_Index loop
			tio.Put(To_String(Vs(I)) & ", ");
		end loop;
		tio.New_Line;
	end Trail;

	function Paths(g: in Graph; V_start, V_end: in Node_Type)
		return Paths_Vector.Vector is
		result: Paths_Vector.Vector;

		function In_Path(Goal, V: in Node_Type; state: in out nv.Vector) return Boolean is
			nextbound : nv.Vector;
			visiting : Node_Type;
		begin
			state.Append(v);
			if V = Goal then
				if not result.Contains(state) then
					result.Append(state);
				end if;
				state.Delete_Last;
				return true;
			end if;
			nextbound := Neighbors(g, V);
			for I in nextbound.First_Index .. nextbound.Last_Index loop
				visiting := nextbound(I);
				if visiting /= V and (not state.Contains(visiting) or Is_Cycle(visiting)) then
					if not In_Path(Goal, visiting, state)  then
						state.Delete_Last;
					end if;
				end if;
			end loop;
			return false;
		end In_Path;

		Unused: Boolean;
		state: nv.Vector;
	begin
		if not Contains(g, V_start) or not Contains(g, V_end) then return result; end if;
		Unused := In_Path(V_end, V_start, state);
		return result;
	end Paths;


	package Node_Maps is new Ada.Containers.Hashed_Maps
		(Element_Type => Node_Type, Key_Type => Node_Type,
		Hash => Hash, Equivalent_Keys => "=");
	package nm renames Node_Maps;

	function Traceback (V_start, V_end: in Node_Type; path : in nm.Map) return nv.Vector is
		result : nv.Vector := nv.Empty_Vector;
		current : Node_Type;
	begin
		current := V_end;
		loop
			result.Append(current);
			exit when current = V_start;
			if not path.Contains(current) then return nv.Empty_Vector; end if;
			current := path(current);
		end loop;
		result.Reverse_Elements;
		return result;
	end Traceback;

	function Breadth_Search(g: in Graph; V_start, V_end: in Node_Type)
		return nv.Vector is

		visited: nm.Map := nm.Empty_Map;
		visiting: nv.Vector := nv.Empty_Vector;
		next_visit: nv.Vector := nv.Empty_Vector;
		node, next_node: Node_Type;
		found_goal: Boolean := false;

		procedure Traverse_Path is
		begin
			visited.Include(V_start, V_start);
			visiting.Append(V_start);
			loop
				exit when Integer(visiting.Length) = 0;
				node := visiting.First_Element;
				visiting.Delete_First;
				next_visit := Neighbors(g, node);
				for N in next_visit.Iterate loop
					next_node := next_visit(N);
					if next_node = V_end then found_goal := true; end if;
					if not visited.Contains(next_node) or Is_Cycle(next_node) then
						visiting.Append(next_node);
						visited.Include(next_node, node);
					end if;
					exit when found_goal;
				end loop;
				exit when found_goal;
			end loop;
		end Traverse_Path;

	begin
		if not Contains(g, V_start) or not Contains(g, V_end) then
			return nv.Empty_Vector;
		end if;
		Traverse_Path;
		return Traceback(V_start, V_end, visited);
	end Breadth_Search;

	function Uniform_Search(g: in Graph; V_start, V_end: in Node_Type)
		return nv.Vector is

		type Node_Priority_Cost is record
			node: Node_Type;
			cost: Cost_Type;
		end record;

		function Get_Priority(el: Node_Priority_Cost) return Cost_Type is
			(el.cost);

		package Node_Priority_Interface is new Ada.Containers.Synchronized_Queue_Interfaces
			(Element_Type => Node_Priority_Cost);
		package Node_Priority is new Ada.Containers.Unbounded_Priority_Queues
			(Queue_Interfaces => Node_Priority_Interface, Queue_Priority => Cost_Type,
			Before => "<");
		package np renames Node_Priority;

		package Node_Cost is new Ada.Containers.Hashed_Maps
			(Key_Type => Node_Type, Element_Type => Cost_Type, Hash => Hash,
			Equivalent_Keys => "=");
		package nc renames Node_Cost;

		visited: nm.Map := nm.Empty_Map;
		visiting: np.Queue;
		next_visit: nv.Vector := nv.Empty_Vector;
		node, next_node: Node_Type;
		cost_so_far: nc.Map := nc.Empty_Map;
		found_goal: Boolean := false;
		new_cost : Cost_Type := Zero_Cost;
		node_cost_of_priority : Node_Priority_Cost;

	begin
		if not Contains(g, V_start) or not Contains(g, V_end) then
			return nv.Empty_Vector;
		end if;
		cost_so_far.Include(V_start, Zero_Cost);
		visited.Include(V_start, V_start);
		visiting.Enqueue((V_start, Zero_Cost));
		loop select
			visiting.Dequeue(node_cost_of_priority);
			node := node_cost_of_priority.node;
			exit when node = V_end;
			next_visit := Neighbors(g, node);
			for N in next_visit.Iterate loop
				next_node := next_visit(N);
				if cost_so_far.Contains(node) then
					new_cost := cost_so_far(node);
				end if;
				new_cost := new_cost + Cost(node, next_node);
				--tio.Put_Line("new_cost:" & new_cost'image);
				if not visited.Contains(next_node) then
					if not cost_so_far.Contains(next_node) then
						cost_so_far.Include(next_node, new_cost);
					elsif cost_so_far.Contains(next_node) and new_cost < cost_so_far(next_node) then
						cost_so_far(next_node) := new_cost;
					end if;
					visiting.Enqueue((next_node, new_cost));
					visited.Include(next_node, node);
				end if;
			end loop;
		else exit;
		end select;
		end loop;
		return Traceback(V_start, V_end, visited);
	end Uniform_Search;

	function Greedy_Best_Search(g: in Graph; V_start, V_end: in Node_Type)
		return nv.Vector is

		type Node_Priority_Cost is record
			node: Node_Type;
			cost: Cost_Type;
		end record;

		function Get_Priority(el: Node_Priority_Cost) return Cost_Type is
			(el.cost);

		package Node_Priority_Interface is new Ada.Containers.Synchronized_Queue_Interfaces
			(Element_Type => Node_Priority_Cost);
		package Node_Priority is new Ada.Containers.Unbounded_Priority_Queues
			(Queue_Interfaces => Node_Priority_Interface, Queue_Priority => Cost_Type,
			Before => "<");
		package np renames Node_Priority;

		visited: nm.Map := nm.Empty_Map;
		visiting: np.Queue;
		next_visit: nv.Vector := nv.Empty_Vector;
		node, next_node: Node_Type;
		found_goal: Boolean := false;
		new_cost : Cost_Type := Zero_Cost;
		node_cost_of_priority : Node_Priority_Cost;

	begin
		if not Contains(g, V_start) or not Contains(g, V_end) then
			return nv.Empty_Vector;
		end if;
		visited.Include(V_start, V_start);
		visiting.Enqueue((V_start, Zero_Cost));
		loop select
			visiting.Dequeue(node_cost_of_priority);
			node := node_cost_of_priority.node;
			exit when node = V_end;
			next_visit := Neighbors(g, node);
			for N in next_visit.Iterate loop
				next_node := next_visit(N);
				--tio.Put_Line("new_cost:" & new_cost'image);
				if not visited.Contains(next_node) then
					new_cost := Distance(V_end, next_node);
					visiting.Enqueue((next_node, new_cost));
					visited.Include(next_node, node);
				end if;
			end loop;
		else exit;
		end select;
		end loop;
		return Traceback(V_start, V_end, visited);
	end Greedy_Best_Search;

	function A_Star_Search(g: in Graph; V_start, V_end: in Node_Type)
		return nv.Vector is

		type Node_Priority_Cost is record
			node: Node_Type;
			cost: Cost_Type;
		end record;

		function Get_Priority(el: Node_Priority_Cost) return Cost_Type is
			(el.cost);

		package Node_Priority_Interface is new Ada.Containers.Synchronized_Queue_Interfaces
			(Element_Type => Node_Priority_Cost);
		package Node_Priority is new Ada.Containers.Unbounded_Priority_Queues
			(Queue_Interfaces => Node_Priority_Interface, Queue_Priority => Cost_Type,
			Before => "<");
		package np renames Node_Priority;

		package Node_Cost is new Ada.Containers.Hashed_Maps
			(Key_Type => Node_Type, Element_Type => Cost_Type, Hash => Hash,
			Equivalent_Keys => "=");
		package nc renames Node_Cost;

		visited: nm.Map := nm.Empty_Map;
		visiting: np.Queue;
		next_visit: nv.Vector := nv.Empty_Vector;
		node, next_node: Node_Type;
		cost_so_far: nc.Map := nc.Empty_Map;
		found_goal: Boolean := false;
		new_cost : Cost_Type := Zero_Cost;
		node_cost_of_priority : Node_Priority_Cost;
		priority : Cost_Type := Zero_Cost;

	begin
		if not Contains(g, V_start) or not Contains(g, V_end) then
			return nv.Empty_Vector;
		end if;
		cost_so_far.Include(V_start, Zero_Cost);
		visited.Include(V_start, V_start);
		visiting.Enqueue((V_start, Zero_Cost));
		loop
			exit when Integer(visiting.Current_Use) = 0;
			visiting.Dequeue(node_cost_of_priority);
			node := node_cost_of_priority.node;
			exit when node = V_end;
			next_visit := Neighbors(g, node);
			for N in next_visit.Iterate loop
				next_node := next_visit(N);
				if cost_so_far.Contains(node) then
					new_cost := cost_so_far(node);
				end if;
				new_cost := new_cost + Cost(node, next_node);
				--tio.Put_Line("next visit:" & To_String(next_node) & ", new_cost:" & Integer'image(new_cost));
				if not visited.Contains(next_node) then
					if not cost_so_far.Contains(next_node) then
						cost_so_far.Include(next_node, new_cost);
					elsif cost_so_far.Contains(next_node) and new_cost < cost_so_far(next_node) then
						cost_so_far(next_node) := new_cost;
					end if;
					priority := new_cost + Distance(V_end, next_node);
					visiting.Enqueue((next_node, priority));
					visited.Include(next_node, node);
				end if;
			end loop;
		end loop;
		return Traceback(V_start, V_end, visited);
	end A_Star_Search;
end graphs;

Graph.ads

with Ada.Containers.Vectors;
with Ada.Containers;

generic
type Node_Type is private;
type Index_Type is range <>;
with function "=" (Left, Right: in Node_Type)
return Boolean is <>;
with function Is_Cycle(V: in Node_Type)
return Boolean is <>;
with function To_String(V: in Node_Type)
return String is <>;
with function Hash(V: in Node_Type)
return Ada.Containers.Hash_Type is <>;

package Graphs is
	type Edge is record
		Node1, Node2: Node_Type;
	end record;
	function "="(E1, E2: in Edge) return Boolean;

	package Nodes_vector is new Ada.Containers.Vectors
		(Element_Type => Node_Type, Index_Type => Index_Type, "=" => "=");
	package nv renames Nodes_vector;

	package Edges_vector is new Ada.Containers.Vectors
		(Element_Type => Edge, Index_Type => Index_Type, "=" => "=");
	package ev renames Edges_vector;

	package Paths_Vector is new Ada.Containers.Vectors
		(Element_Type => nv.Vector, Index_Type => Index_Type, "=" => nv."=");

	type Graph is record
		nodes: nv.Vector;
		edges: ev.Vector;
	end record;

	function Nodes(g: in Graph) return nv.Vector;
	function Edges(g: in Graph) return ev.Vector;

	procedure Add(g: in out Graph; V: in Node_Type);
	procedure Add(g: in out Graph; E: in Edge);

	function Contains(g: in Graph; V: in Node_Type) return Boolean;
	function Contains(g: in Graph; E: in Edge) return Boolean;
	function Contains(E: in Edge; V: in Node_Type) return Boolean;

	function Neighbors(g: in Graph; V: in Node_Type) return nv.Vector;

	function Paths(g: in Graph; V_Start, V_End: in Node_Type)
		return Paths_Vector.Vector;

	generic
	type Cost_Type is private;
	with function Cost(V1, V2: in Node_Type) return Cost_Type is <>;
	with function "+"(C1, C2: in Cost_Type) return Cost_Type is <>;
	with function "<"(C1, C2: in Cost_Type) return Boolean is <>;
	with function Zero_Cost return Cost_Type is <>;
	function Uniform_Search(g: in Graph; V_Start, V_End: in Node_Type)
		return nv.Vector;

	generic
	type Cost_Type is private;
	with function Distance(Goal, Point: in Node_Type) return Cost_Type is <>;
	with function "<"(D1, D2: in Cost_Type) return Boolean is <>;
	with function Zero_Cost return Cost_Type is <>;
	function Greedy_Best_Search(g: in Graph; V_Start, V_End: in Node_Type)
		return nv.Vector;

	generic
	type Cost_Type is private;
	with function Cost(V1, V2: in Node_Type) return Cost_Type is <>;
	with function "+"(C1, C2: in Cost_Type) return Cost_Type is <>;
	with function "<"(C1, C2: in Cost_Type) return Boolean is <>;
	with function Zero_Cost return Cost_Type is <>;
	with function Distance(Goal, Point: in Node_Type) return Cost_Type is <>;
	function A_Star_Search(g: in Graph; V_Start, V_End: in Node_Type)
		return nv.Vector;

	function Breadth_Search (g: in Graph; V_Start, V_End: in Node_Type)
		return nv.Vector;

	private

	function Neighbor(E: in Edge; V: in Node_Type) return Node_Type;

	procedure Trail(Vs: nv.Vector; prompt : String := "");
end Graphs;

Graph.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

interface Cycleable {
	boolean isCycle();
}

interface Addable<C> {
	void addFrom(C other);
}

interface Copyable<C> {
	C copy();
}

interface Costable<V, C extends Comparable<C>> {
	C zeroCost();
	C cost(V otherVertex);
	C distanceTo(V targetVertex);
}

public class Graph<
	V extends Comparable<V> & Cycleable & Costable<V, C>,
	C extends Comparable<C> & Addable<C> & Copyable<C>>
{
	public class Edge {
		V node1, node2;
		public String toString() {
			return String.format("%s -> %s", node1, node2);
		}

		public Edge(V n1, V n2) {
			node1 = n1;
			node2 = n2;
		}
	}

	public ArrayList<V> nodes = new ArrayList<>();
	public ArrayList<Edge> edges = new ArrayList<>();
	HashMap<V, ArrayList<V>> internalEdges = new HashMap<>();

	public void addVertex(V v) {
		if (nodes.contains(v)) return;
		nodes.add(v);
	}

	public void addEdge(V v1, V v2) {
		if (!nodes.contains(v1)) nodes.add(v1);
		if (!nodes.contains(v2)) nodes.add(v2);
		if (internalEdges.containsKey(v1) && internalEdges.get(v1).contains(v2)) {
			return;
		}
		if (internalEdges.containsKey(v2) && internalEdges.get(v2).contains(v1)) {
			return;
		}
		var v1v2 = internalEdges.getOrDefault(v1, new ArrayList<>());
		var v2v1 = internalEdges.getOrDefault(v2, new ArrayList<>());
		v1v2.add(v2);
		v2v1.add(v1);
		internalEdges.put(v1, v1v2);
		internalEdges.put(v2, v2v1);
		var e = new Edge(v1, v2);
		edges.add(e);
	}

	public void addVertices(V[] vs) {
		for (var v : vs) {
			nodes.add(v);
		}
	}

	public boolean contains(V v) {
		return nodes.contains(v);
	}

	public boolean contains(Edge e) {
		return edges.contains(e);
	}

	public void addEdges(Edge[] es) {
		for (var e : es) {
			addEdge(e.node1, e.node2);
		}
	}

	public ArrayList<V> neighbors(V node) {
		var neighbors = new ArrayList<V>();
		for (var e : edges) {
			if (e.node1 == node) {
				neighbors.add(e.node2);
			} else if (e.node2 == node) {
				neighbors.add(e.node1);
			}
		}
		return neighbors;
	}

	public ArrayList<ArrayList<V>> paths(V start, V end) {
		if (!nodes.contains(start) || !nodes.contains(end)) {
			return null;
		}
		var state = new ArrayDeque<V>();
		ArrayList<ArrayList<V>> res = new ArrayList<>();
		inPath(end, start, state, res);
		return res;
	}

	boolean inPath(V goal, V node, ArrayDeque<V> state, ArrayList<ArrayList<V>> acc) {
		state.add(node);
		if (node == goal) {
			var thelist = state.stream().collect(Collectors.toCollection(ArrayList<V>::new));
			if (!acc.contains(thelist)) {
				acc.add(thelist);
			}
			state.removeLast();
			return true;
		}
		var nextbound = neighbors(node);
		nextbound.stream().forEach(v -> {
			if (v != node && (!state.contains(v) || v.isCycle())) {
				if (!inPath(goal, v, state, acc)) {
					state.removeLast();
				}
			} else {
				//System.out.printf("Cannot visit neighbor (%s)\n", v);
			}
		});
		return false;
	}

	class NodePriority {
		V node;
		C cost;

		NodePriority(V node, C cost) {
			this.node = node;
			this.cost = cost;
		}
	}

	ArrayList<V> traceback(V start, V end, HashMap<V, V> path) {
		var retpath = new ArrayList<V>();
		var current = end;
		while(true) {
			retpath.add(0, current);
			if (current == start) break;
			if (!path.containsKey(current)) {
				return new ArrayList<>();
			}
			current = path.get(current);
		}
		return retpath;
	}

	public ArrayList<V> AStar (V start, V end) {
		if (!nodes.contains(start) || !nodes.contains(end)) {
			return new ArrayList<>();
		}
		var visited = new HashMap<V, V>();
		var costSoFar = new HashMap<V, C>();
		var visiting = new PriorityQueue<NodePriority>(
				(n1, n2) -> n1.cost.compareTo(n2.cost));
		visited.put(start, start);
		visiting.add(new NodePriority(start, start.zeroCost()));
		C newcost = start.zeroCost();
		costSoFar.put(start, start.zeroCost());
		while (true) {
			if (visiting.size() == 0) {
				break;
			}
			var v = visiting.poll();
			if (v.node == end) {
				break;
			}
      
			var nextvisit = neighbors(v.node);
			for (var i = 0; i < nextvisit.size(); i++) {
				var nextnode = nextvisit.get(i);
				newcost = costSoFar.get(v.node).copy();
				newcost.addFrom(v.node.cost(nextnode));
				if (!costSoFar.containsKey(nextnode) || newcost.compareTo(costSoFar.get(nextnode)) < 0) {
					costSoFar.put(nextnode, newcost);
					var priority = newcost.copy();
					priority.addFrom(nextnode.distanceTo(end));
					visiting.add(new NodePriority(nextnode, priority));
					visited.put(nextnode, v.node);
				}
			}
		}
		return traceback(start, end, visited);
	}
}

input.txt

1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581