Skip to content

Instantly share code, notes, and snippets.

@MikuAuahDark

MikuAuahDark/Edge.java

Last active Mar 2, 2021
Embed
What would you like to do?
Uniform Cost Search in Java 8
// 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;
}
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;
}
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());
}
}
}
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment