Uniform Cost Search in Java 8

Edge.java

// Sisi
public class Edge {
	public Edge(Vertex a, Vertex b, int cost) {
		this.a = a;
		this.b = b;
		this.cost = cost;
	}

	public Vertex getA() {
		return a;
	}

	public Vertex getB() {
		return b;
	}

	public int getCost() {
		return cost;
	}

	public Edge reverse() {
		return new Edge(b, a, cost);
	}

	public boolean contains(Vertex v) {
		return a == v || b == v;
	}

	public boolean equals(Object o) {
		if (o instanceof Edge) {
			Edge e = (Edge) o;
			return e.a.equals(a) && e.b.equals(b);
		} else {
			return false;
		}
	}

	public int hashCode() {
		return a.hashCode() + 666 * b.hashCode() - cost;
	}

	protected Vertex a, b;
	protected int cost;
}

UCS.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;

// Uniform-Cost Search
public class UCS {
	public class UCSResult {
		public Edge[] getPaths() {
			return paths.clone();
		}

		public int getTotalCost() {
			return cost;
		}

		public int getTotalExpansion() {
			return expansion;
		}

		private Edge[] paths;
		private int cost;
		private int expansion;
	}

	public UCS(Vertex[] vertexes, Edge[] edges) {
		this.verts = new ArrayList<Vertex>(Arrays.asList(vertexes));
		this.edges = new ArrayList<Edge>(Arrays.asList(edges));

		// Buat graf bolak balik untuk mensimulasikan graf tanpa arah
		int size = this.edges.size();
		for (int i = 0; i < size; i++) {
			Edge reverse = this.edges.get(i).reverse();

			if (this.edges.contains(reverse) == false) {
				this.edges.add(reverse);
			}
		}

		neighboor = new HashMap<Vertex, HashSet<Edge>>();
		size = this.edges.size();

		// Buat koneksi tetangga antar simpul
		// HashSet<Edge> mengandung semua yang Edge.getA() == Vertex
		for (int i = 0; i < size; i++) {
			Edge e = this.edges.get(i);
			Vertex v = e.getA();

			// Apakah vertex benar-benar didefinisikan?
			if (verts.contains(v) == false) {
				throw new IllegalArgumentException("Vertex \"" + verts + "\" missing from verts");
			}

			HashSet<Edge> adjacent = neighboor.get(v);

			if (adjacent == null) {
				adjacent = new HashSet<Edge>();
				neighboor.put(e.getA(), adjacent);
			}

			adjacent.add(e);
		}
	}

	public UCSResult find(Vertex source, Vertex destination) {
		HashSet<Edge> connection = neighboor.get(source);

		if (connection == null) {
			throw new IllegalArgumentException("Source vertex \"" + source + "\" doesn't exist");
		}

		if (neighboor.get(destination) == null) {
			throw new IllegalArgumentException("Destination vertex \"" + destination + "\" doesn't exist");
		}

		PriorityQueue<PathCost> frontier = new PriorityQueue<PathCost>(16, UCS::comparePathCost);
		HashSet<Vertex> visited = new HashSet<Vertex>();
		int totalExpansion = 1;

		// Set frontier
		for (Edge e: connection) {
			frontier.offer(new PathCost(e, null));
		}

		visited.add(source);

		while (true) {
			// Ambil yang pertama
			PathCost pc = frontier.poll();

			if (pc == null) {
				// Gagal, tidak ada solusi
				return null;
			}

			Vertex next = pc.edge.getB();

			if (next.equals(destination)) {
				// Ditemukan solusi
				UCSResult result = new UCSResult();
				result.cost = pc.totalCost;
				result.expansion = totalExpansion;
				result.paths = pc.getPaths();

				return result;
			}

			// Jika tidak ada rekursi, lanjut
			if (visited.contains(next) == false) {
				visited.add(next);

				HashSet<Edge> adjacent = neighboor.get(next);

				if (adjacent != null) {
					// Tambahkan ke queue
					for (Edge e: adjacent) {
						// Pastikan tidak kembali ke simpul sebelumnya
						if (e.getB().equals(pc.edge.getA()) == false) {
							frontier.offer(new PathCost(e, pc));
						}
					}
				}
			}

			totalExpansion++;
			// Simpul yang tidak terhubung ke sisi selanjutnya atau
			// simpul yang siklik akan terhapus secara otomatis
		}
	}

	private class PathCost {
		PathCost(Edge edge, PathCost prev) {
			this.edge = edge;
			this.totalCost = edge.getCost();

			if (prev != null) {
				totalCost += prev.totalCost;
				previous = prev;
			}
		}

		public Edge[] getPaths() {
			ArrayList<Edge> edges = new ArrayList<Edge>();

			PathCost pc = this;
			while (pc != null) {
				edges.add(pc.edge);
				pc = pc.previous;
			}

			Edge[] result = new Edge[edges.size()];

			Collections.reverse(edges);
			edges.toArray(result);

			return result;
		}

		Edge edge;
		PathCost previous;
		int totalCost;
	}

	// Fungsi sorting
	static int comparePathCost(PathCost a, PathCost b) {
		return a.totalCost - b.totalCost;
	}

	private ArrayList<Vertex> verts;
	private ArrayList<Edge> edges;
	private HashMap<Vertex, HashSet<Edge>> neighboor;
}

UCSMain.java

import java.util.ArrayList;

public class UCSMain {
	public static void main(String[] args) {
		Vertex[] vertexes = new Vertex[] {
			new Vertex("Arad"),          // 0
			new Vertex("Timisoara"),     // 1
			new Vertex("Zerind"),        // 2
			new Vertex("Oradea"),        // 3
			new Vertex("Lugoj"),         // 4
			new Vertex("Drobeta"),       // 5
			new Vertex("Mehadia"),       // 6
			new Vertex("Sibiu"),         // 7
			new Vertex("Rimnicu Vilcea"),// 8
			new Vertex("Craiova"),       // 9
			new Vertex("Fagaras"),       // 10
			new Vertex("Pitesti"),       // 11
			new Vertex("Giurgiu"),       // 12
			new Vertex("Bucharest"),     // 13
			new Vertex("Neamt"),         // 14
			new Vertex("Urziceni"),      // 15
			new Vertex("Iasi"),          // 16
			new Vertex("Vaslui"),        // 17
			new Vertex("Hirsova"),       // 18
			new Vertex("Eforie")         // 19
		};
		Edge[] edges = new Edge[] {
			// Arah deklarasi ke kanan, constructor UCS
			// akan otomatis membuat sisi arah lainnya
			new Edge(vertexes[0], vertexes[1], 118),
			new Edge(vertexes[0], vertexes[2], 75),
			new Edge(vertexes[0], vertexes[7], 140),
			new Edge(vertexes[1], vertexes[4], 111),
			new Edge(vertexes[2], vertexes[3], 71),
			new Edge(vertexes[3], vertexes[7], 151),
			new Edge(vertexes[4], vertexes[6], 70),
			new Edge(vertexes[5], vertexes[9], 120),
			new Edge(vertexes[6], vertexes[5], 75),
			new Edge(vertexes[7], vertexes[8], 80),
			new Edge(vertexes[7], vertexes[10], 99),
			new Edge(vertexes[8], vertexes[9], 146),
			new Edge(vertexes[8], vertexes[11], 97),
			new Edge(vertexes[9], vertexes[11], 138),
			new Edge(vertexes[10], vertexes[13], 211),
			new Edge(vertexes[11], vertexes[13], 101),
			new Edge(vertexes[13], vertexes[12], 90),
			new Edge(vertexes[13], vertexes[15], 85),
			new Edge(vertexes[15], vertexes[17], 142),
			new Edge(vertexes[15], vertexes[18], 98),
			new Edge(vertexes[16], vertexes[14], 87),
			new Edge(vertexes[17], vertexes[16], 92),
			new Edge(vertexes[18], vertexes[19], 86)
		};

		// Test cari arah dari Arad ke Bucharest
		UCS ucs = new UCS(vertexes, edges);
		UCS.UCSResult result = ucs.find(vertexes[0], vertexes[13]);

		System.out.println("Dari Arad, Ke Bucharest:");
		if (result == null) {
			System.out.println("Tidak ditemukan");
		} else {
			ArrayList<String> paths = new ArrayList<String>();
			Edge[] edgePath = result.getPaths();

			for (Edge e: edgePath) {
				paths.add(e.getA().toString());
			}

			paths.add(edgePath[edgePath.length - 1].getB().toString());

			System.out.println(String.join(" -> ", paths));
			System.out.println("Total Cost: " + result.getTotalCost());
			System.out.println("Total Ekspansi: " + result.getTotalExpansion());
		}
	}
}

Vertex.java

// Simpul
public class Vertex {
	public Vertex(String name) {
		this.name = name;
	}

	public String toString() {
		return name;
	}

	public boolean equals(Object v) {
		if (v instanceof Vertex) {
			return ((Vertex) v).name.equals(name);
		} else {
			return false;
		}
	}

	public int hashCode() {
		return name.hashCode() * 42069;
	}

	protected String name;
}