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 = 0.5;// ---------->Konstanta pengendali intensitas jejak semut
		double beta = 0.5;// ----------->Konstanta pengendali visibilitas
		double rho = 0.5;// ---------->Tetapan penguapan jejak semut (penguapan pheromone)
		int m = 100;// ---------------->Banyaknya Semut
		int NC_MAX = 1000;// ---------->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;
				}
			}
		}

		//MEMPERSIAPKAN arrayList MST untuk menyimpan Spanning Tree dengan total bobot paling minimum yang didapatkan oleh semut
		//NILAI MST INI AKAN DIEVALUASI MELALUI OPERASI ELITISM DISETIAP AKHIR SIKLUS
		ArrayList<Edge>mst = null;
		double bestValue = Double.MAX_VALUE;

		/**
		 * 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];
			double[] Lk = new double[m];

			//PERSIAPKAN VARIABEL UNTUK MENYIMPAN NILAI DARI SEMUT TERBAIK
			ArrayList<Edge>mstSemutTerbaik = null;
			double valueSemutTerbaik = Double.MAX_VALUE;

			// 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;



				//INISIALISASI EDGE UNTUK MENGKONSTRUKSI MST
				ArrayList<Edge>edges = new ArrayList<Edge>();//
				//Lk
				double L_semut = 0.0;

				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 = -1;//(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;
						double bobot = adjacency[vertexAsal][vertexTujuan];
						L_semut += bobot;
						edges.add(new Edge(vertexAsal,vertexTujuan,bobot));
						nVisited++;
						System.out.print(vertexAsal + " - " + vertexTujuan + "; ");
					}
				}
				//SEMUT TELAH BERHASIL MEMBENTUK SATU SOLUSI MST
				System.out.println("L Semut: "+L_semut);
				Lk[semut]=L_semut;
				//LAKUKAN UPDATE DELTA TOU OLEH SEMUT
				if(!edges.isEmpty()){
					for(Edge edge:edges){
						deltaTou[edge.vertexAsal][edge.vertexTujuan] += (Q/L_semut);
					}
				}

				//EVALUASI NILAI SEMUT TERBAIK
				if(L_semut<valueSemutTerbaik && edges!=null){
					valueSemutTerbaik = L_semut;
					mstSemutTerbaik = edges;
				}

			}//end of for semut (masing-masing semut mencari solusi MST)

			//UPDATE TOU SEBELUM LANJUT KE SIKLUS BERIKUTNYA
			for (int i = 0; i < tou.length; i++) {
				for (int j = 0; j < tou[i].length; j++) {
					if (adjacency[i][j] > 0 && deltaTou[i][j]>0) {
						tou[i][j] = rho * tou[i][j]+deltaTou[i][j];
					} else {
						tou[i][j] = 0;
					}
				}
			}

			//OPERASI ELITISME
			//EVALUASI NILAI SEMUT TERBAIK
			if(valueSemutTerbaik<bestValue && mstSemutTerbaik!=null){
				bestValue = valueSemutTerbaik;
				mst = mstSemutTerbaik;
			}

		}//end of siklus semut

		//PRINT BEST VALUE
		System.out.println();
		System.out.println("PROSES SIKLUS ANT COLONY SELESAI...");
		System.out.println("BEST VALUE: "+bestValue);
		if(mst!=null){
			System.out.println("MST: ");
			for(Edge edge:mst){
				int i = edge.vertexAsal;
				int j = edge.vertexTujuan;
				//System.out.print(i+"-"+j+"; ");
				System.out.print(label[i][1]+" - "+label[j][1]+"; ");
			}
		}

	}

	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 (min + random.nextDouble() * (max - min));
	}

}

class Edge{
	int vertexAsal;
	int vertexTujuan;
	double bobot;

	public Edge(int vertexAsal, int vertexTujuan) {
		super();
		this.vertexAsal = vertexAsal;
		this.vertexTujuan = vertexTujuan;
	}

	public Edge(int vertexAsal, int vertexTujuan, double bobot) {
		super();
		this.vertexAsal = vertexAsal;
		this.vertexTujuan = vertexTujuan;
		this.bobot = bobot;
	}

}