package alg;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeMap;
import java.util.TreeSet;

import misc.Common;
import misc.IO;

import graph.*;
import generator.GraphGenerator;

/*
------ Preprocess -------

Preprocess the graph to find positive nodes; these define the initial clusters
For each such cluster c,
	Compute the optimal spanning tree t(c) 
	score(c) := P(t) – N(t(c))

Compute distance matrix d(x,y) over all nodes
For each node c,
	Compute SH(x)

----- Main Loop ----------
Repeat
	For each node x,
		If a rooted subtree t in SH(x) has a score higher than max POS(t) then
			Merge t into a single cluster c
			Update distance matrix d
				d(x,c), d(c,x) := min over all nodes y in t: d(y,x)
			Compute the optimal spanning tree OST t(c) over c using shortest paths
			Keep OST if it has a higher score than SH (Note! no further running of OPT)
			score(c) := P(c) – N(t(c))
			compute SH(c)
		end if
	end for
Until no more mergers are possible
Return the highest score from the clusters
*/

public class BUp {
	Graph _g;
	// Related to all heuristics
	HashMap<Integer,Integer> n2c;
	HashMap<Integer, ArrayList<Integer>> c2n;
	HashMap<Integer, Double> scores;
	TreeSet<EdgeComparable> Q;
	
	// rlevant to SPT merging only
	HashMap<String, Tree> clusters;
	
	// used to recover the actual solution in the end
	HashSet<Integer> used_edges;
	
	// Control TM and SM
	public boolean useTM = true;
	public boolean useSM = true;
	public boolean resetClusters=false;
	
	// old implementations where single slack is maintained
	int cl_slack = -1;
	double slack = 0;
	int cid = 0;
	
	public BUp(Graph gr) {
		// TODO implement this transformation
		_g = gr;
		cid = _g.getn() + 1;
		n2c = new HashMap<Integer, Integer>();
		c2n = new HashMap<Integer, ArrayList<Integer>>();
		scores = new HashMap<Integer, Double>();
		clusters = new HashMap<String,Tree>();
		used_edges = new HashSet<Integer>();
	}
	
	// --------------------------SPT merging------------------------------------------------
	private Tree computeSPTtoAll(Graph gcurr, String name) {
		if(gcurr.getm()==0) return new Tree(gcurr);
		TreeSet<Integer> edges = new TreeSet<Integer>();
		APSP D = gcurr.getMetic();
		int v1 = gcurr.getNodeIndex(name), v2;
		for (v2 = 0; v2 < gcurr.getn();v2++) {
			if (v2==v1) continue;
			int n1, n2;
			for (int i=0; i < D.getSPath(v1, v2).size()-1; i++) {
				n1 = D.getSPath(v1, v2).get(i);
				n2 = D.getSPath(v1, v2).get(i+1);
				// make sure that the edge in both directions is added
				edges.add(gcurr.getEdgeIndex(n1, n2));
				edges.add(gcurr.getEdgeIndex(n2, n1));
			}
		}
		ArrayList<Integer> edge_indices = new ArrayList<Integer>();
		edge_indices.addAll(edges);
		return new Tree(gcurr.subgraph(edge_indices));
	}
	
	public Tree getOptimalSPTMerging() {	
		// add the best node
		Tree max_ost = new Tree(new Graph(_g.getMaxScoreName(),_g.getMaxScore()));
		clusters.put(_g.getMaxScoreName(), max_ost);
		double max_score = _g.getMaxScore();
		Tree curr_sh=null, curr_ost = null;
		ArrayList<String> terminals = new ArrayList<String>();
		Graph gcurr = _g;
		String curr_name = null;
		do {
			for (int i=0; i < gcurr.names.length; i++ ) {
				curr_sh = computeSPTtoAll(gcurr,gcurr.names[i]);
				curr_sh = PCST.computeOptTreeNW(curr_sh);
				if (curr_sh.getn()==1) continue;
				if (curr_sh.getNodeIndex(gcurr.names[i]) < 0) continue;
				terminals = curr_sh.getPositives();
				curr_ost = ST.computeSteiner(gcurr, terminals);
				//?????? curr_ost =  PCST.computeOptTreeNW(curr_ost);
				
				if (curr_ost.getMaxScore() > curr_ost.getScore()) continue;
				if (curr_ost.getScore() > max_score) {
					max_score = curr_ost.getScore();
					max_ost = curr_ost;
				}
			}
			if (null == max_ost) break;
			// Update clusters
			terminals = max_ost.getAllNames();
			// leave them for debugging purposes
			// for(String c: terminals) clusters.remove(c);
			curr_name = max_ost.getNames();
			clusters.put(curr_name,max_ost);
			
			// TODO: we are recomputing the cluster without allowing unnecessary
			// link nodes to leave previously formed clusters. This might make the
			// the expansion too conservative. Allow ost on the original tree?
			// - it will be messy to update clusters
			// - maybe ost on original and then collapse the surviving non-overlapping clusters
			gcurr = gcurr.collapseCluster(terminals, max_score, curr_name);
			max_ost = null;
			max_score = -1;
		} while(true);
		
		String best_cluster = gcurr.getMaxScoreName();
		return getOriginalSubGraph(clusters.get(best_cluster));
	}
	
	private Tree getOriginalSubGraph(Tree tree) {
		String names[] = tree.getParsedOrderedNames().split(" ");
		ArrayList<String> terminals = new ArrayList<String>();
		for(String s: names) terminals.add(s);
		return ST.computeSteiner(_g, terminals);
	}

	// ------------------------ LM ---------------------------------------- 
	public void computeOptimalLM() {
		initClusters();
		// get edges between positive nodes
		Q = _g.getMetic().getOrderedEdges(false);
		
		// Run the algorithm
		KruskalSlack();
	}
	
	// ------------------------ LM+SM -------------------------------------
	public void computeOptimalLMSM() {
		initClusters();
		// get edges between positive nodes
		Q = _g.getMetic().getOrderedEdges(false);
		
		// Run the algorithm
		boolean improved = KruskalSlack();
		while (improved) {
			improved = false;
			if (starLookAhead()) {
				improved = KruskalSlack();
			}
		}
	}
	
	// ------------------------ LM+SM+TM ----------------------------------
	public void computeOptimalLMSMTM() {
		// get edges between positive nodes
		Q = _g.getMetic().getOrderedEdges(false);
		ModKruskal();
	}
	
	// ------------------------ GW ----------------------------------
	public void computeOptimalGW() {
		
		// make sure there are no zero edges
		for (double ew: _g.we) assert(ew>0);
		
		double decr;
		
		// phase 1: expand
		initClusters();
		BitSet activee = new BitSet(_g.getm());
		activee.set(0, activee.size(), true);
		double[] wee = Arrays.copyOf(_g.we, _g.we.length);
		
		HashMap<Integer,ArrayList<Integer>> c2e = new HashMap<Integer, ArrayList<Integer>>();
		HashSet<Integer> activec = new HashSet<Integer>();
		for(int c:c2n.keySet()) {
			if (scores.get(c) > 0) 
				activec.add(c);
		}
		
		
		
		while(c2n.size()>1 && activec.size() > 0)  {
			decr = Double.POSITIVE_INFINITY;
			for (int c:activec) decr = Math.min(decr, scores.get(c));
			for (int i=0;i < _g.getm(); i++) {
				if (!activee.get(i)) continue;
				if (activec.contains(n2c.get(_g.endv[i])) && 
					activec.contains(n2c.get(_g.getOrigin(i))))
					decr = Math.min(decr, wee[i]/2);
				else
					decr = Math.min(decr, wee[i]/2);
			}
			if (decr == Double.POSITIVE_INFINITY) break;
			// reduce all active scores by 0.5
			for(Integer c:activec) {
				assert(scores.get(c) >= decr);
				if (Math.abs(scores.get(c)-decr) <= Common.eps) scores.put(c,0.0);
				else scores.put(c,scores.get(c) - decr);
				
			}
			// reduce the cost of edges if connecting two
		    // different active -1, if one active -0.5
			for (int i=0; i < _g.getn(); i++) {
				for (int j = _g.ind[i]; j < _g.ind[i+1]; j++) {
					if (!activee.get(j)) continue; 
					if(activec.contains(n2c.get(i)) && activec.contains(n2c.get(_g.endv[j]))) {
						if (Math.abs(wee[j]-2*decr) <= Common.eps) wee[j] = 0.0;
						else wee[j] -= 2*decr;
					} else if (activec.contains(n2c.get(i)) || activec.contains(n2c.get(_g.endv[j]))){
						if (Math.abs(wee[j]-decr) <= Common.eps) wee[j] = 0.0;
						else wee[j] -= decr;
					}
				}
			}		
			// Handle 0 edges by joining corresponding clusters
			int c1, c2;
			for (int e = 0; e < _g.getm();e++){
				assert(wee[e] >= 0);
				if (activee.get(e) && wee[e] == 0) {
					c1 = n2c.get(_g.getOrigin(e));
					c2 = n2c.get(_g.endv[e]);
					// merge them if in two different clusters
					if (c1 != c2) {
						// Remap clusters
						c2n.put(cid, new ArrayList<Integer>());
						c2n.get(cid).addAll(c2n.get(c1));
						c2n.get(cid).addAll(c2n.get(c2));
						for (Integer node: c2n.get(cid)) n2c.put(node, cid);
						scores.put(cid, scores.get(c1) + scores.get(c2));
						scores.remove(c1); scores.remove(c2);
						c2n.remove(c1);
						activec.remove(c1);
						c2n.remove(c2);
						activec.remove(c2);
						activec.add(cid);
						// now add the edge to the cluster
						c2e.put(cid, new ArrayList<Integer>());
						c2e.get(cid).add(e);c2e.get(cid).add(_g.getReverseEdgeIndex(e));
						if (c2e.containsKey(c1)) {
							c2e.get(cid).addAll(c2e.get(c1));
							c2e.remove(c1);
						}
						if (c2e.containsKey(c2)) {
							c2e.get(cid).addAll(c2e.get(c2));
							c2e.remove(c2);
						}
						
						cid++;
					}
				}
				activee.set(e,wee[e] > 0);
				
			}
			
			// Handle 0 clusters -> inactive
			HashSet<Integer> todeactivate = new HashSet<Integer>();
			for(Integer c:activec) {
				assert(scores.get(c) >= 0);
				if (scores.get(c) ==0) {
					todeactivate.add(c);
				}
			}
			activec.removeAll(todeactivate);
		}
		
		// phase 2: strong pruning
		
		// run tree algo on every cluster, take the best
		// 1) update scores and cluster members
		// 2) finalize used_edges
		HashMap<Integer, ArrayList<Integer>> _c2n = new HashMap<Integer, ArrayList<Integer>>();
		HashMap<Integer, Integer> _n2c = new HashMap<Integer, Integer>();
		scores.clear();
		int _cid = 0;
		for (int c: c2n.keySet()) {
			if (c2n.get(c).size() > 1) {
				// create tree and get best subtree
				Tree optc = PCST.computeOptTreeNW( new Tree(_g.subgraph(c2e.get(c))));
				scores.put(_cid, optc.getScore());
			
				_c2n.put(_cid, new ArrayList<Integer>());
				for (int i = 0; i < optc.getn(); i++) {
					_c2n.get(_cid).add(_g.getNodeIndex(optc.names[i]));
					_n2c.put(_g.getNodeIndex(optc.names[i]), _cid);
				}
//				for (int e: c2e.get(c)) {
//					if (_c2n.get(_cid).contains(_g.getOrigin(e)) && 
//					_c2n.get(_cid).contains(_g.endv[e])) {
//						used_edges.add(e);
//					}
//				}
				if (optc.getn() > 1) {
					for (int i = 0;i < optc.getn();i++) {
						for (int j = optc.ind[i];j < optc.ind[i+1];j++) {
							int e = _g.getEdgeIndex(_g.getNodeIndex(optc.names[i]), 
									_g.getNodeIndex(optc.names[optc.endv[j]]));
							if (e < 0) {
								System.out.print("");
							}
							used_edges.add(e);
						}
					}
				}
				int added_cid = _cid;
				_cid++;
				// add pruned nodes as separate clusters
				for(int i:c2n.get(c)) {
					if(!_c2n.get(added_cid).contains(i)) {
						_c2n.put(_cid, new ArrayList<Integer>());
						_c2n.get(_cid).add(i);
						_n2c.put(i, _cid);
						scores.put(_cid, _g.wn[i]);
						_cid++;
					}
				}
			} else { // single node in cluster
				assert(c2n.get(c).size() == 1);
				int n = c2n.get(c).get(0);
				scores.put(_cid, _g.wn[n]);
				_c2n.put(_cid, c2n.get(c));
				_n2c.put(n, _cid);
			}
		}
		n2c = _n2c;
		c2n = _c2n;
	}
	
	// ------------------------ Components --------------------------------
	
	private void initClusters() {
		// node to cluster
		n2c.clear();
		c2n.clear();
		scores.clear();
		for (int i = 0; i < _g.getn(); i++) {
			n2c.put(i, i);
			scores.put(i,_g.wn[i]);
			c2n.put(i, new ArrayList<Integer>());
			c2n.get(n2c.get(i)).add(i);
			used_edges.clear();
		}
		cid = _g.getn() + 1;;
	}
	
	// ------------------------ Components --------------------------------
	// iterates over the edges. joins if edges are good 
	private void ModKruskal() {
		// The added edges due to triangle/star lookups
		HashSet<EdgeComparable> M = new HashSet<EdgeComparable>();
		
		// The slack hashmap
		HashMap<Integer, Double> L = new HashMap<Integer, Double>();
		initClusters();
		
		// Control local vars
		Iterator<EdgeComparable> it = Q.iterator();
		EdgeComparable e,te;
		HashSet<EdgeComparable> star_edges;
		boolean restart;
		
		do {
			if (resetClusters) {
				initClusters();
				L.clear();
			}
			restart=false;
			while(it.hasNext()) {
				// if restart -> start exploring edges from the beginning
				if(restart) { 
					if (resetClusters) {
						initClusters();
						L.clear();
					}
					restart = false;
				}
				e = it.next();
				// if the edge is redundant continue
				if(n2c.get(e.n1).equals(n2c.get(e.n2))) continue;
				
				if (M.contains(e) || 
						Math.min(scores.get(n2c.get(e.n1)), 
								  scores.get(n2c.get(e.n2))) >= e.dist) {
					// this edge was not marked so check for triangles
					if (!M.contains(e) && useTM) {
						// check for triangle with central edge e
						if (null != (te = detectTriangle(e))) {
							if (!M.contains(te)) {
								M.add(te);
								restart = true;
								it = Q.iterator();
								continue;
							}
						}
					}
					double sumS = 0, sumL = 0, maxS = 0;
					double newL = 0, newS = 0;
					int c;
					ArrayList<Integer> added = new ArrayList<Integer>(); 
					ArrayList<Integer> sp = _g.getMetic().getSPath(e.n1, e.n2); 
					//System.err.print(e.n1 + "\t"  +e.n2 +  "\t" + e.dist + "\n");
					// Connect the two clusters with their shortest path
					for(int i=0; i < sp.size(); i++) {
						c = n2c.get(sp.get(i));
						if(!added.contains(c)) {
							added.add(c);
							sumS += scores.get(c);
							sumL += (L.containsKey(c))?L.get(c):0;
							maxS = (maxS < scores.get(c))?scores.get(c):maxS;
							if(i>0) { // add the edge
								assert(!used_edges.contains(_g.getEdgeIndex(sp.get(i-1), sp.get(i))));
								used_edges.add(_g.getEdgeIndex(sp.get(i-1), sp.get(i)));
								used_edges.add(_g.getEdgeIndex(sp.get(i), sp.get(i-1)));
							}
							scores.remove(c);
						}
					}
					
					// New slack and score
					newL = Math.max(0.0, sumL - sumS + e.dist + maxS);
					if (newL > 0) L.put(cid, newL); 
					newS = sumS - e.dist + newL - sumL;
					scores.put(cid, newS);
					
					// Remap clusters
					c2n.put(cid, new ArrayList<Integer>());
					for(Integer cl: added) {
						c2n.get(cid).addAll(c2n.get(cl));
						for (Integer node: c2n.get(cl)) n2c.put(node, cid);
						c2n.remove(cl);
						L.remove(cl);
					}
					cid++;
					// start considering the edges from the beginning again
					it = Q.iterator();
				}		
			}
			// Look for stars
			if (useSM) {
				if (null != (star_edges = detectStar())) {
					M.addAll(star_edges);
					it = Q.iterator();
					restart = true;
				}
			}
		}while(restart);
		
	}
	
	// Checks if any node is a center of a star
	// If many return the edges of the highest scoring one

	private HashSet<EdgeComparable> detectStar() {
		double bestStar = -1;
		HashSet<EdgeComparable> res = null, es = new HashSet<EdgeComparable>();
		EdgeComparable ec;
		double s, ms;
		// compute the best score improving star
		for (int root: c2n.keySet()) {
			s = scores.get(root);
			ms = scores.get(root);
			es.clear();
			for (int c: c2n.keySet()) {
				if(root==c || scores.get(c) < scores.get(root)) continue;
				ec = getMinDistEdge(root,c);
				if (ec.dist <= scores.get(c)){
					if(scores.get(c) > ms) ms = scores.get(c);
					s += scores.get(c) - ec.dist;
					es.add(ec);
				}
			}
			if (ms >= s) continue;
			else if (s>bestStar) {
				bestStar = s;
				if (null == res) res = new HashSet<EdgeComparable>();
				res.clear();
				res.addAll(es);
			}
		}
		return res;
	}
	
	// Checks if there are triangles in which e is "central"
	// if many, return the left edge of the one of highest score
	private EdgeComparable detectTriangle(EdgeComparable e) {
		int c1 = n2c.get(e.n1);
		int c2 = n2c.get(e.n2);
		int c11, c12;
		double d,s;
		
		double bestTD = Double.MAX_VALUE;
		EdgeComparable res = null;
		for (EdgeComparable ee: Q) {
			if (e.dist == ee.dist) break;
			if (n2c.get(ee.n1)==n2c.get(ee.n2)) continue;
			c11 = n2c.get(ee.n1);
			c12 = n2c.get(ee.n2);
			if (c11 == c1) {
				// toDO DEBUG WHEN ONE OF THESE ASSERTIONS FAIL
				// FOR SOME RESAON WE ARE FINDING THE SAME EDGE
				assert(c12!=c2);
				d = _g.getMetic().getD(e.n2, ee.n2);
				s = scores.get(c12);
			} else if (c11 == c2) {
				assert(c12!=c1);
				d = _g.getMetic().getD(e.n1, ee.n2);
				s = scores.get(c12);
			} else if (c12 == c2) {
				assert(c11!=c1);
				d = _g.getMetic().getD(e.n1, ee.n1);
				s = scores.get(c11);
			} else if (c12 == c1) {
				assert(c11!=c2);
				d = _g.getMetic().getD(e.n2, ee.n1);
				s = scores.get(c11);
			} else {
				continue;
			}
			if (d <= e.dist && d + ee.dist - s <= e.dist){
				if (bestTD > d + ee.dist - s) {
					bestTD = d + ee.dist - s;
					res = ee;
				}
			}
		}
		return res;
	}
	

	// iterates over the edges. joins if edges are good 
	private boolean KruskalSlack() {
		boolean merged = false;
		boolean merged_this_iteration = true;
		double slack_cluster_score=0;
		
		//double s1, s2;
		while (merged_this_iteration) {
			merged_this_iteration = false;
			for (EdgeComparable e: Q) {
				// redundant? i.e. connecting parts of the same cluster
				if(n2c.get(e.n1).equals(n2c.get(e.n2))) continue;
				// bad?
				if(isBad(e)) continue;
				// merge e
				
				// remember the previous score of the slack cluster if any
				if (slack > 0) {
					assert(cl_slack == n2c.get(e.n1) || cl_slack == n2c.get(e.n2)): "Merging non-slack nodes?";
					slack_cluster_score = scores.get(cl_slack);
				}
				
				double S = 0; 
				// Sum P along along SP
				int c=-1;
				ArrayList<Integer> added = new ArrayList<Integer>(); 
				ArrayList<Integer> sp = _g.getMetic().getSPath(e.n1, e.n2); 
				//System.err.print(e.n1 + "\t"  +e.n2 + "\t"  + e.dist + "\n");
				// connect the two clusters with their shortest path
				for(int i=0; i < sp.size(); i++) {
					c = n2c.get(sp.get(i));
					if(!added.contains(c)) {
						S += scores.get(c);
						scores.remove(c);
						added.add(c);
						if(i>0) {
							assert(!used_edges.contains(_g.getEdgeIndex(sp.get(i-1), sp.get(i))));
							used_edges.add(_g.getEdgeIndex(sp.get(i-1), sp.get(i)));
							S -= _g.getWe(sp.get(i-1),sp.get(i));
						}
					} else {
						assert(c==added.get(added.size()-1)):"Cluster " + c + "[" + clusterNodesToString(c) + 
														     "] appears twice on the shortest path between " + e.n1 + 
														     " and " + e.n2;
					}
				}
				
				//update slack if any
				if (slack > 0) {
					assert (S - slack_cluster_score >= 0): "Negative improvement in slack-node merging";
					slack = Math.max(slack-(S - slack_cluster_score), 0.0);
					cl_slack = cid;
				}
				
				scores.put(cid, S);
				// remap
				c2n.put(cid, new ArrayList<Integer>());
				for(Integer cl: added) {
					c2n.get(cid).addAll(c2n.get(cl));
					for (Integer node: c2n.get(cl)) n2c.put(node, cid);
					c2n.remove(cl);
				}
				
				cid++;
				merged = true;
				merged_this_iteration = true;
				break;
			}
		}
		return merged;
	}
	
	boolean isBad(EdgeComparable e) {
		double s1 =  scores.get(n2c.get(e.n1));
		if(n2c.get(e.n1) == cl_slack) s1 += slack;
		double s2 =  scores.get(n2c.get(e.n2));
		if(n2c.get(e.n2) == cl_slack) s2 += slack;	
		return  (Math.min(s1, s2) < e.dist);
	}
	
	private boolean starLookAhead() {
		assert(slack <= 0.0):"Star lookup while slack is nn zero";
		// compute the best score improving star
		int rootm = -1;
		double scorem = 0;
		double mindist = -1;
		for (int root: c2n.keySet()) {
			double s = scores.get(root);
			double max_comp_score = scores.get(root);
			for (int c: c2n.keySet()) {
				if(root==c || scores.get(c) == 0) continue;
				mindist = getMinDist(root,c);
				if (mindist <= scores.get(c)){
					if(scores.get(c) > max_comp_score) max_comp_score = scores.get(c);
					s += scores.get(c) - mindist;
				}
			}
			if (max_comp_score > s) continue;
			if (s>scorem) {
				rootm = root;
				scorem = s;
			}
		}
		// update slack and slack node
		if (rootm >=0 && scorem > 0) {
			slack = scorem - scores.get(rootm);
			cl_slack = rootm;
			return true;
		}
		return false;
	}
	
	// minimum distance between two clusters
	private double getMinDist(int c1, int c2) {
		double d = Double.POSITIVE_INFINITY;
		for (Integer n1: c2n.get(c1)) {
			for (Integer n2: c2n.get(c2)) {
				if(_g.getMetic().getD(n1, n2) < d)
					d = _g.getMetic().getD(n1, n2);
			}
		}
		return d;
	}
	
	private EdgeComparable getMinDistEdge(int c1, int c2) {
		double d = Double.POSITIVE_INFINITY;
		EdgeComparable e = null;
		for (Integer n1: c2n.get(c1)) {
			for (Integer n2: c2n.get(c2)) {
				if(_g.getMetic().getD(n1, n2) < d) {
					d = _g.getMetic().getD(n1, n2);
					e = Q.floor(new EdgeComparable(n1, n2, d));
					assert(Math.min(e.n1,e.n2) == Math.min(n1, n2) && 
							Math.max(e.n1,e.n2) == Math.max (n1, n2));
				}
			}
		}
		return e;
	}
	
	//  get solution
	
	public Graph getBestClusterGraph() {
		int c = -1;
		double ms =-1;
		for (Integer cl: scores.keySet()) {
			if (ms<scores.get(cl)){
				c = cl;
				ms = scores.get(cl);
			}
		}
		
		if (c2n.get(c).size()==1) {
			return new Graph(_g.names[c2n.get(c).get(0)], _g.wn[c2n.get(c).get(0)]);
		} else {
			Tree optc = ST.computeMST(_g.inducedSubgraph(c2n.get(c)));
			if (ms <= optc.getScore()) 
				return optc;
		}
		
		ArrayList<Integer> cledges = new ArrayList<Integer>();
		int from, to;
		for(Integer e: used_edges) {
			from = _g.getOrigin(e);
			to = _g.endv[e];
			if (from > to && used_edges.contains(_g.getReverseEdgeIndex(e))) continue;
			if (c2n.get(c).contains(from)){
				assert(c2n.get(c).contains(to)):"Edge between two different clusters found " +
												from + "-" + to + " |cluster=" + c2n.get(c).toString();
				cledges.add(e);
				cledges.add(_g.getReverseEdgeIndex(e));
			}
		}
		return _g.subgraph(cledges);
	}
	
	public double getBestClusterScore(boolean doMST) {
		if (doMST) {
			return getBestClusterGraph().getScore();
		} else {
			return getBestClusterScore();
		}
	}
	
	public double getBestClusterScore() {
		int c = -1;
		double ms =-1;
		for (Integer cl: scores.keySet()) {
			if (ms<scores.get(cl)){
				c = cl;
				ms = scores.get(cl);
			}
		}
		return ms;
	}
	
	public TreeMap<Double,Integer> getClusterScores() {
		TreeMap<Double,Integer> sol = new TreeMap<Double, Integer>();
		for (Integer cl: scores.keySet()) {
			if (!sol.containsKey(scores.get(cl))) sol.put(scores.get(cl), 1);
			else sol.put(scores.get(cl), sol.get(scores.get(cl)) + 1);
		}
		return sol;
	}
	
	
	private String clusterNodesToString(int c) {
		String res = "";
		for (Integer i: n2c.keySet()) 
			if (n2c.get(i)==c)
				res += i + " ";
		return res;
	}

	public String toString() {
		String res = "Clusters:\n";
		for (String s: clusters.keySet()) res += s + "->" + clusters.get(s).toStringHuman() + "\n";
		return res;
	}
		
	
	public static void main(String[] argv) throws IOException{		
		//evaluateRandom(); 
		test();
		//evaluateILPInstances();
		
	}

	public static void evaluateRandom() {
		long start,end;
		Graph g = GraphGenerator.generateRandomWeighted(100, 120, 20, 80);
		//System.out.print(g.toString());
		BUp b = new BUp(g);
		start = System.currentTimeMillis();
		b.computeOptimalLMSM();
		Graph res_sla = b.getBestClusterGraph();
		end = System.currentTimeMillis();
		System.out.print("LookAheadGrow: " + res_sla.getScore() + "[" + ((end-start)) + "ms]\n");
		
			b = new BUp(g);
			start = System.currentTimeMillis();
			b.computeOptimalLMSMTM();
			Graph res_krus = b.getBestClusterGraph();
			end = System.currentTimeMillis();
			System.out.print("LMSMTM: " + res_krus.getScore() + "[" + ((end-start)) + "ms]\n");
		
		
//		start = System.currentTimeMillis();
//		Tree res_spt = b.getOptimalSPTMerging();
//		end = System.currentTimeMillis();
//		System.out.print("SPTGrow: " + res_spt.getScore() + "[" + ((end-start)) + "ms]\n");
//		
//		if (res_sla.getScore() < res_spt.getScore() ) {
//			System.out.print("\nSPT :" + res_spt.getParsedOrderedNames());
//			System.out.print("\nLAHG:" + res_sla.getParsedOrderedNames());
//			//System.out.print("\nKRUS:" + res_krus.getParsedOrderedNames());	
//			//System.out.print("\n" + g.toString());
//		}
	
	}
	
	// TODO: setup an experiment based on this
	public static void evaluateILPInstances() throws IOException{
		Graph g;
		BUp b;
		long start, end;
		// 
		String path = "/home/petko/data/temporal/PCST_ILP_Instances/pcstp/";
		String files = "K100.10.dat  K100.2.dat  K100.4.dat  K100.6.dat  K100.8.dat " + 
					   "K100.dat  K400.10.dat  K400.2.dat  K400.4.dat  K400.6.dat " + 
					   "K400.8.dat  K400.dat K100.1.dat   K100.3.dat  K100.5.dat " + 
					   "K100.7.dat  K100.9.dat  K200.dat  K400.1.dat   K400.3.dat " +
					   "K400.5.dat  K400.7.dat  K400.9.dat " +
					   "P100.1.dat  P100.1.dat.csv  P100.2.dat  P100.3.dat  P100.4.dat " +
					   "P100.dat  P200.dat  P400.1.dat  P400.2.dat  P400.3.dat " +
					   "P400.4.dat  P400.dat";
//		files = "K400.5.dat  K400.7.dat P100.2.dat P100.dat P400.1.dat " +
//		        "P400.2.dat P400.3.dat P400.dat";
//		files = "P100.4.dat P400.3.dat";
		
		for (String fn: files.split("[ ]+")) {
			g = IO.parseILPPCST(path + fn.trim());
			start = System.currentTimeMillis();
			g.getMetic();
			end = System.currentTimeMillis();
			System.out.print("APSP:[" + ((end-start)) + "ms]\n");
			double sum = 0;
			for (int i = 0 ; i < g.getn(); i++) sum += g.wn[i];
			System.out.print("TOTAL P: " + g.getP() +  "\tN: " + g.getN() + "\n");
			System.out.print("OPT    : " + g.opt_nw + "\n");
			
			b = new BUp(g);
			start = System.currentTimeMillis();
			b.useTM = false;b.useSM = true;
			//b.computeOptimalLMSM();
			b.computeOptimalLMSMTM();
			Graph res_sla = b.getBestClusterGraph();
			end = System.currentTimeMillis();
			//System.out.print("LookAheadGrow: " + res_sla.getScore() + "=(" + res_sla.getP() + " - " +  res_sla.getN() + ") GW = " + (g.getP() - res_sla.getP() + res_sla.getN()) + "[" + ((end-start)) + "ms]\n");
			//System.out.print("LS: "  + (g.getP() - res_sla.getP() + res_sla.getN()) + "[" + ((end-start)) + "ms]\n");
			System.out.print("LS: "  + res_sla.getScore() + "[" + ((end-start)) + "ms]\n");
			
			b = new BUp(g);
			start = System.currentTimeMillis();
			b.useTM = true;b.useSM = true;
			b.computeOptimalLMSMTM(); 
			end = System.currentTimeMillis();
			Graph res_krus = b.getBestClusterGraph();
			System.out.print("LST: "  + res_krus.getScore() + "[" + ((end-start)) + "ms]\n");
			
			b = new BUp(g);
			start = System.currentTimeMillis();
			b.computeOptimalGW(); 
			Graph res_gw = b.getBestClusterGraph();
			end = System.currentTimeMillis();
			System.out.print("GW: "  + res_gw.getScore() + "[" + ((end-start)) + "ms]\n");
			
//			start = System.currentTimeMillis();
//			try {
//				Tree res_spt = b.getOptimalSPTMerging();
//				end = System.currentTimeMillis();
//				//System.out.print("SPTGrow: " + res_spt.getScore() + "=(" + res_spt.getP() + " - " +  res_spt.getN() + ")[" + ((end-start)) + "ms]\n");
//				System.out.print("SPTGrow: " +(g.getP() - res_spt.getP() + res_spt.getN())+ "[" + ((end-start)) + "ms]\n");
//			} catch (Exception e) {
//				
//			}
			
		}
	}
	
	
	public static void test() {
		long start,end;
		
		//test
		start = System.currentTimeMillis();
		
		// --   TestGraph
		Graph g = GraphGenerator.getTestGraph();
		BUp b = new BUp(g);
		b.computeOptimalLMSM();
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalLM();
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.resetClusters = false;
		b.computeOptimalLMSMTM();
		// if triangles are on it finds 19
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalGW();
		// if triangles are on it finds 19
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		// --   TestGraphStar
		g = GraphGenerator.getTestGraphWithStar();
		b = new BUp(g);
		b.computeOptimalLMSM();
		assert(22.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalLM();
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalLMSMTM();
		assert(22.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalGW();
		assert(22.00 == b.getBestClusterGraph().getScore());
		
		// --   TestGraph with non-mergeable star
		g = GraphGenerator.getTestGraphWithNonMergeableStar();
		b = new BUp(g);
		b.computeOptimalLMSM();
		assert(19.00 == b.getBestClusterGraph().getScore());
	
		b = new BUp(g);
		b.computeOptimalLM();
		assert(19.00 == b.getBestClusterGraph().getScore());
	
		b = new BUp(g);
		b.computeOptimalLMSMTM();
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalGW();
		assert(19.00 == b.getBestClusterGraph().getScore());
		
		// --   TestGraph with star + fuirther merge
		g = GraphGenerator.getTestGraphWithStarFurtherMerge();
		b = new BUp(g);
		b.computeOptimalLMSM();
		assert(23.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalLM();
		assert(21.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalLMSMTM();
		assert(23.00 == b.getBestClusterGraph().getScore());
		
		b = new BUp(g);
		b.computeOptimalGW();
		assert(23.00 == b.getBestClusterGraph().getScore());
		
		end = System.currentTimeMillis();
		System.out.print("test: " + "[" + ((end-start)) + "ms]\n");
		
	}
	
}
