package graph;

import generator.GraphGenerator;

import java.util.Arrays;
import java.util.TreeSet;

import misc.Common;

public class MetricGraph {
	// contains distances d and paths sp for pairs of nodes
	public double[][] d;
	public int[][][] sp;

	Graph g;
	
	public MetricGraph(Graph _g) {
		assert(_g.isUndirected());
		g = _g;
	}
	
	public void computeFloydWarshall() {
		
		d = new double[g.getn()][g.getn()];
		String[][] SP = new String[g.getn()][g.getn()];
		for (int i=0; i < d.length; i++ ) {
			Arrays.fill(d[i],Double.MAX_VALUE);
			Arrays.fill(SP[i], "");
		}
		
		// initialize with edges
		for (int i = 0; i < g.getn(); i++) {
			for (int j=g.ind[i]; j < g.ind[i+1]; j++) {
				d[i][g.endv[j]] = g.we[j];
				SP[i][g.endv[j]] = i + Common.SEP + g.endv[j];
			}
		}
		
		// Triple loop
		for (int k=0; k<g.getn(); k++){
		    for (int i=0; i<g.getn(); i++){
		        for (int j=0; j<g.getn(); j++){
		        	if (i==j || i==k || k == j) continue;
		            if (d[i][j] > d[i][k] + d[k][j]) {
		            	d[i][j] = d[i][k] + d[k][j];
		            	SP[i][j] = SP[i][k] + SP[k][j].replaceFirst("" + k, "");
		            }
		        }
		    }
		}
		
		// now set the sp
		int maxp = 0;
		for (int i=0; i < SP.length; i++) {
			for (int j= i+1; j < SP[i].length; j++) {
				if (maxp < SP[i][j].split(Common.SEP).length) 
					maxp =  SP[i][j].split(Common.SEP).length;
			}
		}
		
		String[] s;
		sp = new int[d.length][d.length][maxp];
		for (int i=0; i < SP.length; i++) {
			for (int j= 0; j < SP[i].length; j++) {
				Arrays.fill(sp[i][j], -1);
				if(j==i) continue;
				s = SP[i][j].split(Common.SEP);
				for (int k = 0; k < s.length; k++) {
					sp[i][j][k] = Integer.parseInt(s[k]);
				}
				
			}
		}
		
	}
	
	public TreeSet<EdgeComparable> getOrderedEdges(boolean only_positive) {
		TreeSet<EdgeComparable> ec = new TreeSet<EdgeComparable>();
		for (int i=0; i < g.getn(); i++) {
			if (only_positive && g.wn[i] == 0) continue;
			for (int j= i+1; j < g.getn(); j++) {
				if (only_positive && g.wn[j] == 0) continue;
				ec.add(new EdgeComparable(i,j,d[i][j]));
			}
		}
		return ec;
	} 
	
	public String toString() {
		String result = "";
		for (int i=0; i < g.getn(); i++) {
			for (int j=0; j < g.getn(); j++) {
				if (i==j) continue;
				result += i + "\t" + j + "\t" + d[i][j] + "\t[";
				result += sp[i][j][0];
				for (int k = 1 ; k < sp[i][j].length; k++){
					if (sp[i][j][k] < 0) break;
					result += ", " + sp[i][j][k];
				}
				
				result += "]\n";
			}
		}
		return result;
	}

	public static void main(String[] argv) {
		Graph g = GraphGenerator.getTestGraph();
		APSP apsp = new APSP(g);
		apsp.computeFloydWarshall();
		System.out.print(apsp.toString());
	}
}
