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 = 1000;// ---------------->Banyaknya Semut
		int NC_MAX = 1000;// ---------->Banyaknya Siklus Semut
		double probBacktracking = 0.7;//>Peluang Backtracking

		/**
		 * 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) {

					//MEMBANGKITKAN BILANGAN ACAK pBack UNTUK MENENTUKAN GERAKAN MAJU ATAU MUNDUR
					double pBack = randomBetweenDouble(0.0, 1.0);

					if(pBack<probBacktracking&&stackVertex.size()>1&&stackVertex.size()<(n-1)){
						//MUNDUR
						stackVertex.pop();
					}else{
						//MAJU
						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.print("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;
	}

}