import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;

public class AntColony {

	private static Random random = new Random();

	public static void main(String[] args) {
		// LABEL VERTEX
		String[][] label = new String[8][2];
		label[0][0] = "A";
		label[0][1] = "City Market Palopo";
		label[1][0] = "B";
		label[1][1] = "Toko Baru";
		label[2][0] = "C";
		label[2][1] = "Pasar Andi Tadda Palopo";
		label[3][0] = "D";
		label[3][1] = "Opsal Plaza";
		label[4][0] = "E";
		label[4][1] = "Toko Matahari";
		label[5][0] = "F";
		label[5][1] = "Pusat Niaga Palopo";
		label[6][0] = "G";
		label[6][1] = "Mega Plaza";
		label[7][0] = "H";
		label[7][1] = "Mangga Dua";

		// MATRIKS ADJACENCY
		double[][] adjacency = { { 0, 0.5, 1.6, 1.3, 1.7, 1.7, 1.7, 2.3 }, { 0.5, 0, 1.1, 0.8, 1.2, 1.2, 1.2, 2.2 },
				{ 1.6, 1.1, 0, 0.85, 1.2, 1.2, 1.2, 2.3 }, { 1.3, 0.8, 0.85, 0, 0.55, 0.55, 0.4, 1.4 },
				{ 2.4, 1.9, 1.1, 0.55, 0, 0.11, 0.35, 1.6 }, { 2.4, 1.9, 1.1, 0.55, 0.11, 0, 0.35, 1.6 },
				{ 1.7, 1.2, 1.2, 0.4, 0.35, 0.35, 0, 1.2 }, { 2.3, 2.2, 2.3, 1.4, 1.5, 1.6, 1.2, 0 } };

		// INISIALISASI PARAMETER
		double tou_awal = 0.01;// ---->menyatakan intensitas awal pheromone (jejak semut) disetiap vertex
		int n = adjacency.length;// -->jumlah vertex
		double Q = 1;// -------------->konstanta siklus semut
		double alpha = 1;// ---------->Konstanta pengendali intensitas jejak semut
		double beta = 1;// ----------->Konstanta pengendali visibilitas
		double rho = 0.5;// ---------->Tetapan penguapan jejak semut (penguapan pheromone)
		int m = 10;// ---------------->Banyaknya Semut
		int NC_MAX = 18;// ---------->Banyaknya Siklus Semut

		/**
		 * PERSIAPAN MEMULAI SIKLUS SEMUT
		 */

		// VISIBILITAS ANTAR VERTEX (invers jarak dinotasikan dg simbol eta)
		double[][] eta = new double[n][n];
		for (int i = 0; i < eta.length; i++) {
			for (int j = 0; j < eta[i].length; j++) {
				if (adjacency[i][j] > 0) {
					eta[i][j] = 1.0 / adjacency[i][j];
				} else {
					eta[i][j] = 0;
				}
			}
		}

		// INISIALISASI MATRIX TOU. mula-mulai nilainya sama untuk setiap edge
		// yaitu sebesar tou_awal
		double[][] tou = new double[n][n];
		for (int i = 0; i < tou.length; i++) {
			for (int j = 0; j < tou[i].length; j++) {
				if (adjacency[i][j] > 0) {
					tou[i][j] = tou_awal;
				} else {
					tou[i][j] = 0;
				}
			}
		}

		/**
		 * MEMULAI SIKLUS SEMUT
		 */
		for (int nc = 1; nc <= NC_MAX; nc++) {// melakukan looping siklus sebanyak NC_MAX
			System.out.println("SIKLUS-" + nc);
			double[][] deltaTou = new double[n][n];

			// menebar semut buatan (artificial ants) ke vertex-vertex secara
			// random
			for (int semut = 0; semut < m; semut++) {
				System.out.println("-->Semut-" + (1 + semut));

				// menyediakan object stack untuk menyimpan vertex yang telah
				// dikunjungi
				// serta agar semut dapat bergerak mundur
				Stack stackVertex = new Stack();

				// memilih vertex pertama untuk dikunjungi secara acak
				int vo = randomBetweenInteger(0, (n - 1));
				stackVertex.push(vo);// menambahkan vo ke stack

				boolean[] block = new boolean[n];// membuat array block untuk menandai vertex yang sudah pernah dikunjungi
				block[vo] = true;

				int nVisited = 1;// baru ada satu vertex yang dikunjungi yaitu vertex awal (vo)
				while (!stackVertex.isEmpty() && nVisited < n) {
					int vertexAsal = (int) stackVertex.peek();

					// mencari kandidat Vertex tujuan dari semua vertex yang
					// terhubung ke vertexAsal dan belum terblock
					ArrayList<Double> kandidatVertexTujuan = new ArrayList<Double>();
					for (int j = 0; j < n; j++) {
						if (adjacency[vertexAsal][j] > 0 && block[j] == false) {
							kandidatVertexTujuan.add((double) j);
						}
					}

					if (kandidatVertexTujuan.isEmpty()) {// jika kandidatVertexTujuan KOSONG/EMPTY
						// jika tidak ditemukan kandidatVertexTujuan maka semut
						// akan bergerak mundur
						// secara struktur data gerakan mundur ini dilakukan
						// melalui operasi pop() pada stack
						stackVertex.pop();
					} else {
						// jika ditemukan kandidatVertexTujuan
						// maka hitung probabilitas ke masing-masing vertex
						// kandidat menggunakan
						// formula probabilitas semut
						// pembilang = tou_ij_pangkat_alpha +
						// eta_ij_pangkat_beta
						ArrayList<Double> pembilang = new ArrayList<Double>();
						double penyebut = 0;
						int i = vertexAsal;
						for (int k = 0; k < kandidatVertexTujuan.size(); k++) {
							int j = (int) Math.floor(kandidatVertexTujuan.get(k));
							double tou_ij_pangkat_alpha = Math.pow(tou[i][j], alpha);
							double eta_ij_pangkat_beta = Math.pow(eta[i][j], beta);
							double tou_ij_pangkat_alpha_plus_eta_ij_pangkat_beta = tou_ij_pangkat_alpha
									+ eta_ij_pangkat_beta;
							pembilang.add(tou_ij_pangkat_alpha_plus_eta_ij_pangkat_beta);
							penyebut += tou_ij_pangkat_alpha_plus_eta_ij_pangkat_beta;
						}

						// improve menggunakan roda roulette
						ArrayList<Double> probabilitasKomulatif = new ArrayList<Double>();
						double MAX_SUM_PROB_KOMULATIF = 0;

						// hitung probabilistik ke setiap vertex kandidat
						ArrayList<Double> p_ij = new ArrayList<Double>();
						for (int k = 0; k < pembilang.size(); k++) {
							double peluang = pembilang.get(k) / penyebut;
							p_ij.add(peluang);
							MAX_SUM_PROB_KOMULATIF += peluang;
							probabilitasKomulatif.add(MAX_SUM_PROB_KOMULATIF);
						}

						// bangkitkan sebuah bilangan acak r antara
						// [0..MAX_SUM_PROB_KOMULATIF] untuk memilih vertex
						// tujuan
						double r = randomBetweenDouble(0, MAX_SUM_PROB_KOMULATIF);
						int vertexTujuan = (int) Math.floor(kandidatVertexTujuan.get(kandidatVertexTujuan.size() - 1));// -1;
						for (int k = 0; k < probabilitasKomulatif.size(); k++) {
							if (r <= probabilitasKomulatif.get(k)) {
								vertexTujuan = (int) Math.floor(kandidatVertexTujuan.get(k));
								break;
							}
						}

						// semut menemuan vertex baru
						stackVertex.push(vertexTujuan);
						block[vertexTujuan] = true;
						nVisited++;
						System.out.print(vertexAsal + " - " + vertexTujuan + "; ");

					}
				}

				System.out.println();
			}

		}

	}

	private static int randomBetweenInteger(int min, int max) {
		if (min >= max) {
			throw new IllegalArgumentException("nilai variabel max harus lebih besar dari nilai variabel min");
		}
		return random.nextInt((max - min) + 1) + min;
	}

	private static double randomBetweenDouble(double min, double max) {
		if (min >= max) {
			throw new IllegalArgumentException("nilai variabel max harus lebih besar dari nilai variabel min");
		}
		return (random.nextDouble() * ((max - min) + 1)) + min;
	}

}