package generator;

import ilog.cplex.cppimpl.doubleArray;
import index.IntervalBounds;

import java.io.BufferedWriter;
import java.io.Externalizable;
import java.io.FileWriter;
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.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

import javax.swing.plaf.SliderUI;

import graph.Graph;
import graph.TimeGraph;
import graph.Tree;
import graph.WeightedTimeGraph;
import graph.NodeWeightedTimeGraph;

import misc.Common;
import misc.ExtToolsDriver;
import misc.IO;
import misc.Time.t_res;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.VertexFactory;
import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.generate.ScaleFreeGraphGenerator;
import org.jgrapht.graph.SimpleGraph;

import alg.BUp;

// wrapper for JGraphT
public class GraphGenerator {
	public static Graph generateScaleFree(int size) {
		ScaleFreeGraphGenerator<Integer, DefaultEdge> sf = new ScaleFreeGraphGenerator<Integer, DefaultEdge>(size);
		VertexFactory<Integer> vg = new VertexGenerator();
		org.jgrapht.Graph<Integer, DefaultEdge> gr = new SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);
		HashMap<String, Integer> hm = new HashMap<String, Integer>();
		sf.generateGraph(gr, vg, hm);
	
		return convertToGraph(gr);
	}
	
	public static Graph generateClustered(int nnodes, int cluster_size, 
									double cluster_density, double ext_density) {
		
		HashSet<String> edges = new HashSet<String>();
		Random r = new Random();
		
		// generate clusters first
		for(int c = 0; c <= (int)nnodes / cluster_size; c++) {
			int sind = c*cluster_size;
			int eind = Math.min((c+1)*cluster_size, nnodes);
			int size = eind - sind;
			
			int nedges = 0, n1, n2;
			while (nedges < cluster_density*(size*(size-1)/2)) {
				n1 = r.nextInt(size)+sind;
				n2 = r.nextInt(size)+sind;
				if (n1!=n2){
					if(!edges.contains(n1+ "," + n2)) {
						edges.add(n1+ "," + n2);
						edges.add(n2+ "," + n1);
						nedges++;
					}
				}
			}
		}
		
		// generate inter-cluster
		for(int c1 = 0; c1 <= (int)nnodes / cluster_size; c1++) {
			int sind1 = c1*cluster_size;
			int eind1 = Math.min((c1+1)*cluster_size, nnodes);
			int size1 = eind1 - sind1;
			for(int c2 = c1+1; c2 <= (int)nnodes / cluster_size; c2++) {
				int sind2 = c2*cluster_size;
				int eind2 = Math.min((c2+1)*cluster_size, nnodes);
				int size2 = eind2 - sind2;
				
				int nedges = 0, n1, n2;
				while (nedges < ext_density*size1*size2) {
					n1 = r.nextInt(size1)+sind1;
					n2 = r.nextInt(size2)+sind2;
					if (n1!=n2){
						if(!edges.contains(n1+ "," + n2)) {
							edges.add(n1+ "," + n2);
							edges.add(n2+ "," + n1);
							nedges++;
						}
					}
				}
				
			}
		}
		
		// convert the edges list to 
		String[] edges_list = new String[edges.size()*2];
		int next = 0;
		for (String ed: edges){
			edges_list[next++] = ed.split(",")[0];
			edges_list[next++] = ed.split(",")[1];
		}
		
		// nodes
		String[] nds_list = new String[nnodes];
		for (int i = 0 ; i < nnodes; i++) nds_list[i] = "" + i;
		return new Graph(edges_list,nds_list);
	}

	private static Graph convertToGraph(org.jgrapht.Graph<Integer, DefaultEdge> gr) {
		ConnectivityInspector<Integer, DefaultEdge> ce = new ConnectivityInspector<Integer, DefaultEdge>((UndirectedGraph<Integer, DefaultEdge>) gr);
		List<Set<Integer>> cc = ce.connectedSets();
		assert(cc.size() == 1):"generated graph is disconnected";
		
		int n = gr.vertexSet().size(), m = gr.edgeSet().size()*2;
		
		Graph g = new Graph(n,m);
		for (int i = 0; i < n; i++) g.names[i] = ((Integer)i).toString();
		int eptr = 0;
		for (int i = 0; i < n; i++) {
			g.ind[i+1] = g.ind[i];
			for (int j = 0 ; j < n ;j++) {
				if (gr.containsEdge(i,j)) {
					g.endv[eptr++]=j;
					g.ind[i+1]++;
				}
			}
		}
		return g;
	}
	
// ------------------------ RANDOM GENERATION ---------------------------------------
	
	// generates a random graph of n nodes and m edges
	public static Graph generateRandom(int n, int med) {
		Random r = new Random();
		HashMap<Integer,HashSet<Integer>> edges = new HashMap<Integer, HashSet<Integer>>();
		for (int i = 0 ; i < n; i++) edges.put(i, new HashSet<Integer>());
		int m;
		if (med >= n*(n-1)/4.0) m = (int) Math.floor(n*(n-1)/4.0);
		else m = med;
		assert(m >= n-1);
		
		// Create a spanning tree
		int[] edg = generateRandomTree(n);
		for (int i = 0; i < edg.length;i+=2) {
			edges.get(edg[i]).add(edg[i+1]);
			edges.get(edg[i+1]).add(edg[i]);
		}
		
		// Add Random edges
		for (int i = 0 ; i < m - edg.length / 2; i++) {
			int v1 = r.nextInt(n);
			int v2 = r.nextInt(n);
			while (edges.get(v1).contains(v2) || v1==v2) {
				v1=r.nextInt(n);
				v2=r.nextInt(n);
			}
			edges.get(v1).add(v2);
			edges.get(v2).add(v1);
		}
		
		// Fill in the data structures
		Graph g = new Graph(n, m*2);
		int eptr = 0;
		for (int i = 0; i < n; i++) {
			g.ind[i+1] = g.ind[i] + edges.get(i).size();
			g.names[i] = ((Integer)i).toString();
			for (int v: edges.get(i)) {
				g.endv[eptr++]=v;
			}
		}
		return g;
	}
	
	// returns a list of edges
	private static int[] generateRandomTree(int n) {
		Random r = new Random();
		int[] comp = new int[n];
		int[] edges = new int[(n-1)*2];
		
		
		for(int i=0; i < n;i++) comp[i]=i;
		
		for(int i = 0; i <n-1; i++) {
			// choose a random pair from different components
			int v1 = r.nextInt(n);
			int v2 = r.nextInt(n);
			while (comp[v1]==comp[v2]) {
				v1=r.nextInt(n);
				v2=r.nextInt(n);
			}
			
			// add an edge
			edges[i*2]=v1;
			edges[i*2+1]=v2;
			
			// update components
			int ov2=comp[v2];
			for (int j=0;j<n;j++) 
				if (comp[j] == ov2) 
					comp[j] = comp[v1];
		}
		return edges;
	}
	
	// generates an edge and node weighted graph
	public static Graph generateRandomWeighted(int n, int m, int max_nw, int max_ew){
		Random r = new Random();
		Graph g = generateRandom(n, m);
		Arrays.fill(g.we, -1.0);
		// weights the nodes and edges
		for (int i=0; i<n ;i++) g.wn[i] = r.nextInt(max_nw+1);
		for (int i=0; i<m*2;i++) {
			if (-1.0==g.we[i]) {
				g.we[i] = r.nextInt(max_ew+1);
				g.setWe(g.endv[i],g.getOrigin(i),g.we[i]);
			}
		}
		g.buildN2I();
		return g;
	}
	
	// generates an edge and node weighted graph
	public static Graph generateScaleFreeWeighted(int n, int max_nw, int max_ew){
		Random r = new Random();
		Graph g = generateScaleFree(n);
		Arrays.fill(g.we, -1.0);
		// weights the nodes and edges
		for (int i=0; i<n ;i++) g.wn[i] = r.nextInt(max_nw+1);
		for (int i=0; i<g.getm();i++) {
			if (-1.0==g.we[i]) {
				g.we[i] = r.nextInt(max_ew+1);
				g.setWe(g.endv[i],g.getOrigin(i),g.we[i]);
			}
		}
		g.buildN2I();
		return g;
	}
	
	// generates edge weighted sampled from U(0,ewmax)
	// and node-weighted where percent_nz are weighted ~N(ewmax,)
	public static void generateRandomWeighted(Graph g, int ewmax, int percent_nz) {
		Random r = new Random();
		for (int i=0; i<g.getn() ;i++) {
			if (percent_nz>=r.nextInt(100)) {
				g.wn[i] = (int)Math.abs(r.nextGaussian()*ewmax/10.0 + ewmax);
			} else {
				g.wn[i] = 0;
			}
		}
		Arrays.fill(g.we,-1);
		for (int i=0; i<g.getn();i++) {
			for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
				if (g.endv[j] < i) continue;
				g.we[j] = r.nextInt(ewmax) + 1.0;
				g.we[g.getEdgeIndex(g.endv[j], i)] = g.we[j];
			}
		}
	}
	
	// ------------------------ REGULAR  ---------------------------------------
	
	public static Graph generateClosedGridGraph(int n1, int n2) {
		
		if (n1 <= 2 || n2 <= 2) return null;
		Graph g = new Graph(n1*n2,n1*n2*4);
		for (int i = 0; i < n1; i++) {
			for (int j = 0; j < n2; j++) {
				g.names[n2*i+j] = i + "," + j;
				g.ind[n2*i+j+1] = g.ind[n2*i+j] + 4;
			}
		}
		g.buildN2I();
		
		for (int i = 0; i < n1; i++) {
			for (int j = 0; j < n2; j++) {
				// edges
				g.endv[4*(n2*i+j)] = g.getNodeIndex(((i==0)?(n1-1):(i-1)) + "," + j) ;
				g.endv[4*(n2*i+j)+1] = g.getNodeIndex(((i+1)%n1) + "," + j);
				g.endv[4*(n2*i+j)+2] = g.getNodeIndex(i + ","+ ((j==0)?(n2-1):(j-1)));
				g.endv[4*(n2*i+j)+3] = g.getNodeIndex(i + "," + ((j+1)%n2));
			}
		}
		
		
		
		return g;
	}
	
	
	// ------------------------ TEST INSTANCES ---------------------------------------
	
	public static Graph getTestGraph() {
		Graph g = new Graph(7,20);
		int[] _ind = {0, 4, 9, 12, 15, 17, 20, 22};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0     | 	   1       |  2     |   3    |  4  |  5     | 6   |
		int[]    _endv = {1, 2, 3, 6, 0, 3, 4, 5, 6, 0, 3, 5, 0, 1, 2, 1, 5, 1, 2, 4, 0, 1};
		double[] _we   = {1, 3, 1, 2, 1, 2, 1, 1, 4, 3, 1, 6, 1, 2, 1, 1,10, 1, 6,10, 2, 4};
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 2, 0, 3, 13, 1, 6};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0,1,2","1,0,2","2,2,2","3,1,1","4,0,0","5,1,0","6,0,3"};
		g.names = _node_names;
		
		return g;
	}
	
	
	
	public static Graph getTestGraphWithStar() {
		Graph g = new Graph(9,26);
		int[] _ind = {0, 4, 9, 14, 17, 19, 22, 24, 25, 26};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0     | 	   1       |  2           |   3    |  4  |  5     | 6   | 7| 8| 
		int[]    _endv = {1, 2, 3, 6, 0, 3, 4, 5, 6, 0, 3, 5, 7, 8, 0, 1, 2, 1, 5, 1, 2, 4, 0, 1, 2, 2};
		double[] _we   = {1, 6, 1, 2, 1, 2, 1, 1, 4, 6, 6, 6, 1, 6, 1, 2, 6, 1,10, 1, 6,10, 2, 4, 1, 6};
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 2, 0, 3, 13, 1, 6, 6, 10};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5","6","7","8"};
		g.names = _node_names;
		
		return g;
	}
	
	public static Graph getTestGraphWithStarFurtherMerge() {
		Graph g = new Graph(10,28);
		int[] _ind = {0, 4, 9, 14, 17, 19, 22, 24, 25, 27, 28};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0     | 	   1       |  2           |   3    |  4  |  5     | 6   | 7| 8   | 9| 
		int[]    _endv = {1, 2, 3, 6, 0, 3, 4, 5, 6, 0, 3, 5, 7, 8, 0, 1, 2, 1, 5, 1, 2, 4, 0, 1, 2, 2, 9, 8};
		double[] _we   = {1, 6, 1, 2, 1, 2, 1, 1, 4, 6, 6, 6, 1, 6, 1, 2, 6, 1,10, 1, 6,10, 2, 4, 1, 6,20,20};
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 2, 0, 3, 13, 1, 6, 6, 10, 21};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5","6","7","8","9"};
		g.names = _node_names;
		
		return g;
	}
	
	public static Graph getTestGraphWithNonMergeableStar() {
		Graph g = new Graph(9,26);
		int[] _ind = {0, 4, 9, 14, 17, 19, 22, 24, 25, 26};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0     | 	   1       |  2           |   3    |  4  |  5     | 6   | 7| 8| 
		int[]    _endv = {1, 2, 3, 6, 0, 3, 4, 5, 6, 0, 3, 5, 7, 8, 0, 1, 2, 1, 5, 1, 2, 4, 0, 1, 2, 2};
		double[] _we   = {1, 6, 1, 2, 1, 2, 1, 1, 4, 6, 6, 6, 1, 6, 1, 2, 6, 1,10, 1, 6,10, 2, 4, 1, 6};
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 2, 0, 3, 13, 1, 6, 3, 9};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5","6","7","8"};
		g.names = _node_names;
		
		return g;
	}
	
	public static Graph getTestGraphClusters() {
		Graph g = new Graph(10,42);
		int[] _ind = {0, 5, 10, 15, 20, 25, 31, 35, 37, 40, 42};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0         | 	   1       |  2           |   3          |  4           |  5              | 6         | 7   | 8      | 9
		int[]    _endv = { 1, 2, 3, 4, 5, 0, 2, 3, 4, 5, 0, 1, 3, 4, 5, 0, 1, 2, 4, 5, 0, 1, 2, 3, 5, 0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 6, 8, 6, 7, 9, 6, 8};
		double[] _we   = new double[42]; Arrays.fill(_we, 0);
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn = new double[10];  Arrays.fill(_wn, 0);
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5","6","7","8","9"};
		g.names = _node_names;
		
		return g;
	}
	
	public static Graph getTestGraphSignEdges() {
		Graph g = new Graph(7,22);
		int[] _ind = {0, 4, 9, 12, 15, 17, 20, 22};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0      | 	   1        |  2     |   3     |  4  |  5     | 6   |
		int[]    _endv = { 1, 2, 3, 6, 0, 3, 4, 5, 6, 0, 3, 5, 0, 1, 2, 1, 5, 1, 2, 4, 0, 1};
		double[] _we   = { 1,-3,-1, 2, 1,-2,-1,-1, 4,-3,-1, 6,-1,-2,-1,-1,10,-1, 6,10, 2, 4};
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 2, 0, 3, 13, 1, 6};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5","6"};
		g.names = _node_names;
		
		return g;
	}
	
	// this is a special star that tests the upper bounding
	public static Graph getTestGraphUBTest() {
		Graph g = new Graph(7,12);
		int[] _ind = {0, 3, 5, 6, 8, 9, 11, 12};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0    |  1  |2 |  3  |4 |  5  |6|
		int[]    _endv = { 1, 3, 5, 0, 2, 1, 0, 4, 3, 0, 6, 5};
		double[] _we   = {-8,-1,-1,-8, 5, 5,-1, 3, 3,-1, 3, 3};
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 0, 0, 0, 0, 0, 0};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5","6"};
		g.names = _node_names;
		
		return g;
	}
	
	
	public static Graph getTestGraphCliques() {
		Graph g = new Graph(7,12);
		int[] _ind = {0, 3, 8, 11, 14, 16, 18};
		g.ind= Arrays.copyOf(_ind,_ind.length);
		//				 |    0   |  1           | 2      | 3      | 4   | 5    |
		int[]    _endv = { 1, 2, 3, 0, 2, 3, 4, 5, 0, 1, 3, 0, 1, 2, 1, 5, 1, 4 };
		double[] _we   = {.5,.9,.9,.5,.9,.9,.6,.6,.9,.9,.5,.9,.9,.5,.6,.6,.6,.6 };
		g.endv = Arrays.copyOf(_endv,_endv.length);
		g.we = Arrays.copyOf(_we,_we.length);
		
		double[] _wn={0, 0, 0, 0, 0, 0, 0};
		g.wn = Arrays.copyOf(_wn,_wn.length);
		
		String[] _node_names = {"0","1","2","3","4","5"};
		g.names = _node_names;
		
		return g;
	}
	
	public static WeightedTimeGraph getGridLineSweep(int gridx, int gridy) {
		Random r = new Random();
		Graph g = generateClosedGridGraph(gridx, gridy);
		float[][] wsl = new float[gridx][g.getm()];
		for(int t = 0; t < gridx; t++) {
			for (int i =0 ; i < wsl[t].length; i++) 
				wsl[t][i] = -1*r.nextFloat();
		}
		int ei;
		for (int t=0; t < gridx; t++) {
			for (int j=0; j < gridy; j++) {
				if (j < gridy-1) {
					ei = g.getEdgeIndex(g.getNodeIndex(t + "," + j), g.getNodeIndex(t + "," + (j+1)));
					wsl[t][ei] = r.nextFloat(); 
					wsl[t][g.getReverseEdgeIndex(ei)] = wsl[t][ei];
				}
				if (t>0) {
					if (j < gridy-1) {
						ei = g.getEdgeIndex(g.getNodeIndex((t-1) + "," + j), g.getNodeIndex((t-1) + "," + (j+1)));
						wsl[t][ei] = r.nextFloat(); 
						wsl[t][g.getReverseEdgeIndex(ei)] = wsl[t][ei];
					}
					ei = g.getEdgeIndex(g.getNodeIndex((t-1) + "," + j), g.getNodeIndex(t + "," + j));
					wsl[t][ei] = r.nextFloat(); 
					wsl[t][g.getReverseEdgeIndex(ei)] = wsl[t][ei];
				}
			}
		}
		return new WeightedTimeGraph(g,wsl);
	}
	
	// sweepine line but the first two time stamps arevery weak in order to test pattern separation
	public static WeightedTimeGraph getGridLineSweepWeakMiddle(int gridx, int gridy) {
		Random r = new Random();
		Graph g = generateClosedGridGraph(gridx, gridy);
		float[][] wsl = new float[gridx][g.getm()];
		for(int t = 0; t < gridx; t++) {
			for (int i =0 ; i < wsl[t].length; i++) 
				wsl[t][i] = -1*r.nextFloat();
		}
		int ei;
		for (int t=0; t < gridx; t++) {
			float mult = 1;
			if (1==t) mult = 0.001F;
			else if (2==t) mult = 0.00001F;
			for (int j=0; j < gridy; j++) {
				if (j < gridy-1) {
					ei = g.getEdgeIndex(g.getNodeIndex(t + "," + j), g.getNodeIndex(t + "," + (j+1)));
					wsl[t][ei] = r.nextFloat()*mult; 
					wsl[t][g.getReverseEdgeIndex(ei)] = wsl[t][ei];
				}
				if (t>0) {
					if (j < gridy-1) {
						ei = g.getEdgeIndex(g.getNodeIndex((t-1) + "," + j), g.getNodeIndex((t-1) + "," + (j+1)));
						wsl[t][ei] = r.nextFloat()*mult; 
						wsl[t][g.getReverseEdgeIndex(ei)] = wsl[t][ei];
					}
					ei = g.getEdgeIndex(g.getNodeIndex((t-1) + "," + j), g.getNodeIndex(t + "," + j));
					wsl[t][ei] = r.nextFloat()*mult; 
					wsl[t][g.getReverseEdgeIndex(ei)] = wsl[t][ei];
				}
			}
		}
		return new WeightedTimeGraph(g,wsl);
	}
	
	// ------------------------ TIME GRAPH ---------------------------------------
	
	// slices is the number of time steps
	// Pneigh is the probability lift of a neighbor being set
	// Pnext is the probability lift of the same edge in time being set
	// Pseed is the uniform probability of event in any set 
	public static TimeGraph generateTimeGraphLocalized( int slices, 
			double Pn, double Pp, double Ps, 
			Graph g) {
		// pick random edges
		BitSet[] sl = new BitSet[slices];
		BitSet neighbors = new BitSet(g.getm());
		Random r = new Random();
		
		// generate slice by slice
		for (int t=0;t<slices;t++){
			sl[t] = new BitSet(g.getm());
			sl[t].clear();
			
			// set random edges based on the seed probability
			// Ps
			if (t==0){ 
				for (int i=0; i<g.getm(); i++) {
					if (r.nextDouble() <= Ps) {
						sl[t].set(i);
						sl[t].set(g.getReverseEdgeIndex(i));
					}
				}
			}
			// if last time it was set. lift based on the 
			// probability of persistence Pp
			for (int i=0; i<g.getm(); i++) {
				if (t>0) {
					// dividing for undirected graphs because there is 
					// twice the chance to set
					if(sl[t-1].get(i) && 
					    r.nextDouble() <= Pp) {
						sl[t].set(i);
						sl[t].set(g.getReverseEdgeIndex(i));
					}
				}
			}
			
			neighbors.clear();
			// if neighbors are set lift more edges according
			// to the neighbor excitation probability Pn
			for (int i=0; i<g.getm(); i++) {
				if(sl[t].get(i)) continue;
				for(int n:g.getNeighEdges(i)) {
					if ( r.nextDouble() < Pn) {
						neighbors.set(i);
						neighbors.set(g.getReverseEdgeIndex(i));
						break;
					}
				}
			}
			sl[t].or(neighbors);
		}
		
		return new TimeGraph(g, sl);
	}
	
	// slices is the number of time steps
	// Pneigh is the probability lift of a neighbor being set
	// Pnext is the probability lift of the same edge in time being set
	// Pseed is the uniform probability of event in any set 
	public static TimeGraph generateTimeNeighborhood( int slices, 
			double Pp, double Ps, 
			Graph g) {
		// pick random edges
		BitSet[] sl = new BitSet[slices];
		BitSet neighbors = new BitSet(g.getm());
		Random r = new Random();
		
		// generate slice by slice
		for (int t=0;t<slices;t++){
			sl[t] = new BitSet(g.getm());
			sl[t].clear();
			
			// set random edges based on the seed probability
			// Ps
			if (0==0){ 
				for (int i=0; i<g.getm(); i++) {
					if (r.nextDouble() <= Ps) {
						sl[t].set(i);
						sl[t].set(g.getReverseEdgeIndex(i));
					}
				}
			}
			// if last time it was set. lift based on the 
			// probability of persistence Pp
			for (int i=0; i<g.getm(); i++) {
				if (t>0) {
					// dividing for undirected graphs because there is 
					// twice the chance to set
					if(sl[t-1].get(i) && 
					    r.nextDouble() <= Pp) {
						sl[t].set(i);
						sl[t].set(g.getReverseEdgeIndex(i));
					}
				}
			}
			
			neighbors.clear();
			double Pn=0;
			// if neighbors are set lift more edges according
			// to the neighbor excitation probability Pn
			for (int i=0; i<g.getm(); i++) {
				if(sl[t].get(i)) continue;
				// count how many neighbors of this edge are on
				Pn = 0.0;
				for(int n:g.getNeighEdges(i)) { 
					if (sl[t].get(n)) Pn +=1;
				} 
				Pn = (g.getNeighEdges(i).size()==0?0:Pn/g.getNeighEdges(i).size());
				if ( r.nextDouble() < Pn) {
					neighbors.set(i);
					neighbors.set(g.getReverseEdgeIndex(i));
				}
			}
			sl[t].or(neighbors);
		}
		
		return new TimeGraph(g, sl);
	}
	
	// As simpler model to generate "slices" time stamps of graph g
	// The states form a Markov Chain such that the probability of 
	// a given edge P(e=1,t) = min(N*F1(e,t-1) + S, 1) 
	// where F1 is the fraction of e neighbors set as 1 at time t-1 
	public static TimeGraph generateTimeHMM( int slices, 
			double N, double S, 
			Graph g) {
		// pick random edges
		BitSet[] sl = new BitSet[slices];
		BitSet prev_state = new BitSet(g.getm());
		BitSet state = new BitSet(g.getm());
		Random r = new Random();
		double[] F1 = new double[g.getn()];
		double F1_edge;
		int src, dst;
		
		state.clear();
		prev_state.clear();
		
		//set the initial state
		for (int i = 0; i < g.getm(); i++) {
			if(r.nextDouble() <= S) prev_state.set(i);
		}
		
		// generate slice by slice
		for (int t=0;t<slices;t++){
			Arrays.fill(F1, 0.0);
			sl[t] = new BitSet(g.getm());
			sl[t].clear();
			
			// compute the F1 in nodes
			for (int i = 0; i < g.getn(); i++) {
				for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
					if (prev_state.get(j)) 
						F1[i]+=1.0/(g.ind[i+1]-g.ind[i]); 
				}
			}
			
			// update hidden states
			for (int i=0; i<g.getm(); i++) {
				src = g.getOrigin(i);
				dst = g.endv[i];
				F1_edge = (F1[src]*(g.ind[src+1]-g.ind[src]) + 
						   F1[dst]*(g.ind[dst+1]-g.ind[dst])) /
						   (g.ind[src+1]-g.ind[src] + g.ind[dst+1]-g.ind[dst]) +
						   0.1*(prev_state.get(i)?1.0:0.0);
				if (src<dst) {
					if(r.nextDouble() <= F1_edge*N + S) {
						state.set(i);
						state.set(g.getReverseEdgeIndex(i));
					}
				}
			}
			
			// sample edges
			double p = 0.0;
			for (int i=0; i<g.getm(); i++) {
				if (g.getOrigin(i) >= g.endv[i]) continue;
				p = (state.get(i))?1.0:0.1;
				if (r.nextDouble() <= p) {
					sl[t].set(i);
					sl[t].set(g.getReverseEdgeIndex(i));
				}
			}
			prev_state.clear();
			prev_state.or(state);
			state.clear();
		}
		
		return new TimeGraph(g, sl);
	}	
	
	public static TimeGraph generateTimeNonClustered(int slices, DynamicModel dm,
			Graph g) {
		Random r = new Random();
		BitSet[] sl = new BitSet[slices];
		for (int i = 0; i < sl.length; i++) sl[i] = new BitSet(g.getm());
		
		// sample S*g.getm() events
		int e, t, nones=0;
		while(nones*1.0/(slices*g.getm()) < dm.POne){
			
			// pick an edge
			do {
				e = r.nextInt(g.getm());
				t = r.nextInt(slices);
			} while (sl[t].get(e) || sl[t].cardinality()*1.0/g.getm() > dm.POne);
			
			sl[t].set(e);
			sl[t].set(g.getReverseEdgeIndex(e));
			nones +=2;
		}
		return new TimeGraph(g, sl);
	}
	
	public static TimeGraph generateTimeRWSampling(int slices, DynamicModel dm,
			Graph g) {
		assert(dm.PNeighbor < 1 && dm.PNextGivenCurrent < 1);
		Random r = new Random();
		BitSet[] sl = new BitSet[slices];
		for (int i = 0; i < sl.length; i++) sl[i] = new BitSet(g.getm());
		
		// sample S*g.getm() events
		int e, t, nones=0;
		while(nones*1.0/(slices*g.getm()) < dm.POne){
			// pick an edge
			do {
				e = r.nextInt(g.getm());
				t = r.nextInt(slices);
			} while (sl[t].get(e));
			
			sl[t].set(e);
			sl[t].set(g.getReverseEdgeIndex(e));
			nones +=2;
			nones += expand(e,t,1.0,dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
			if(t<sl.length-1) 
				nones += expand(e,t+1,dm.PNextGivenCurrent,dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
			if(t>0) 
				nones += expand(e,t-1,dm.PNextGivenCurrent,dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
		}
		return new TimeGraph(g, sl);
	}
	
	
	public static TimeGraph generateTimeDriftingCenters(int slices, DynamicModel dm,
			Graph g) {
		assert(dm.PNeighbor < 1 && dm.PNextGivenCurrent < 1);
		Random r = new Random();
		BitSet[] sl = new BitSet[slices];
		for (int i = 0; i < sl.length; i++) {
			sl[i] = new BitSet(g.getm());
		}
		
		// sample S*g.getm() events
		int e, st, nones=0;
		while(nones*1.0/(slices*g.getm()) < dm.POne){
			// pick an edge that is negative
			do {
				e = r.nextInt(g.getm());
				st = r.nextInt(slices);
			} while (sl[st].get(e));
			
			
			Double len = Math.max((r.nextGaussian()+1)*dm.AvgLength,0);
			int end = Math.min(st + len.intValue(),slices-1);
			
			BitSet bsprev = new BitSet(g.getm());
			BitSet bs = new BitSet(g.getm());
			bs.set(e); bs.set(g.getReverseEdgeIndex(e));
			expandGraph(e,dm.PNeighbor,g,r,bs);
			sl[st].or(bs);
			System.out.print(st + ":" + sl[st].toString() + "\n");
			
			for(int t =st+1; t <= end; t++) {
				bsprev.clear();
				bsprev.or(bs);
				bs.clear();
				
				// choose next root
				int epos = r.nextInt(bsprev.cardinality());
				int cnt = 0;
				for(int i=bsprev.nextSetBit(0); i>=0; i=bsprev.nextSetBit(i+1)){
					if (cnt==epos) {
						e = i;
						break;
					}
					cnt++; 
				}
				bs.set(e); bs.set(g.getReverseEdgeIndex(e));
				expandGraph(e,dm.PNeighbor,g,r,bs);
				sl[t].or(bs);
				
				BitSet intersect = new BitSet(g.getm());
				intersect.or(sl[t-1]);
				intersect.and(sl[t]);
				System.out.print("["+ String.format("%.3f", 
						intersect.cardinality()*1.0/(Math.min(sl[t-1].cardinality(), sl[t].cardinality())) )+"]");
				System.out.print(t + ":" + sl[t].toString() + "\n");
			}	
			System.out.print("\n");
			
			nones = 0;
			for (int t=0; t<sl.length; t++) nones += sl[t].cardinality();
		}
		return new TimeGraph(g, sl);
	}
	
	public static TimeGraph generateTimeDriftingRWSampling(int slices, DynamicModel dm,
			Graph g) {
		assert(dm.PNeighbor < 1 && dm.PNextGivenCurrent < 1);
		Random r = new Random();
		BitSet[] sl = new BitSet[slices];
		for (int i = 0; i < sl.length; i++) sl[i] = new BitSet(g.getm());
		
		// sample S*g.getm() events
		int e, t, nones=0;
		while(nones*1.0/(slices*g.getm()) < dm.POne){
			// pick an edge
			do {
				e = r.nextInt(g.getm());
				t = r.nextInt(slices);
			} while (sl[t].get(e));
			
			sl[t].set(e);
			sl[t].set(g.getReverseEdgeIndex(e));
			nones +=2;
			nones += expandGraph(e,t,1.0,dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
			int tt = t-1;
			int prevnbr = e;
			while(tt>=0 && Math.pow(dm.PNextGivenCurrent,t-tt)>=0.01) {
				int nbr = sampleSelectedNeighborEdge(g, r, sl, prevnbr, tt+1);
				if (-1==nbr) break;
				nones += expand(nbr,tt,Math.pow(dm.PNextGivenCurrent,t-tt),dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
				//nones += expandGraph(prevnbr,tt,Math.pow(dm.PNextGivenCurrent,tt-t),dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
				tt--;
				prevnbr = nbr;
			}
			for(int j = tt+1; j <=t; j++){
				if (j>tt+1) {
					BitSet intersect = new BitSet(g.getm());
					intersect.or(sl[j-1]);
					intersect.and(sl[j]);
					System.out.print("["+ String.format("%.3f", 
							intersect.cardinality()*1.0/(Math.min(sl[j-1].cardinality(), sl[j].cardinality())) )+"]");
				}
				System.out.print(j + ":" + sl[j].toString() + "\n");
			}
		
			tt = t+1;
			prevnbr = e;
			while(tt<sl.length && Math.pow(dm.PNextGivenCurrent,tt-t)>=0.01){ 
				int nbr = sampleSelectedNeighborEdge(g, r, sl, prevnbr, tt-1);
				if (-1==nbr) break;
				nones += expandGraph(nbr,tt,Math.pow(dm.PNextGivenCurrent,tt-t),dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
				//nones += expandGraph(prevnbr,tt,Math.pow(dm.PNextGivenCurrent,tt-t),dm.PNeighbor,dm.PNextGivenCurrent,sl,g,r);
				tt++;
				prevnbr = nbr;
			}
			for(int j = t+1; j <tt; j++) {
				BitSet intersect = new BitSet(g.getm());
				intersect.or(sl[j-1]);
				intersect.and(sl[j]);
				System.out.print("["+ String.format("%.3f", 
						intersect.cardinality()*1.0/(Math.min(sl[j-1].cardinality(), sl[j].cardinality())) )+"]");
				System.out.print(j + ":" + sl[j].toString() + "\n");
			}
			System.out.print("\n");
			
		}
		return new TimeGraph(g, sl);
	}
	
	private static int sampleSelectedNeighborEdge(Graph g, Random r,
			BitSet[] sl, int e, int t) {
		// choose a neighboring edge from the selected ones
		HashSet<Integer> nbrs = g.getNeighEdges(e);
		nbrs.add(e); nbrs.add(g.getReverseEdgeIndex(e));
		ArrayList<Integer> selnbrs = new ArrayList<Integer>();
		for (Integer nbr: nbrs) {
			if(sl[t].get(nbr)) selnbrs.add(nbr);
		}
		if (selnbrs.size()==0) return -1;
		int nbr = selnbrs.get(r.nextInt(selnbrs.size()));
		return nbr;
	}
	
	public static WeightedTimeGraph generateTimeRWSamplingWeighted(int t,
			DynamicModel dm, Graph g, double lambda) {
		return generateTimeRWSamplingWeighted(t,dm,g,lambda,'w');
	}
	
	// generates an edge weighted graph
	// Latest generator we used for Legato is drifting centers: call with 'c' as last parameter
	public static WeightedTimeGraph generateTimeRWSamplingWeighted(int t,
			DynamicModel dm, Graph g, double lambda, char drifting_type) {
		Random r = new Random();
		TimeGraph tg = null;
		double origPOne = dm.POne;
		dm.POne += dm.POne*0.2;
		if (drifting_type == 's') { // drifting RW
			tg = generateTimeDriftingRWSampling(t, dm, g);
		} else if (drifting_type == 'w') { // no drifting
			tg = generateTimeRWSampling(t, dm, g);
		} else if (drifting_type == 'c') {
			tg = generateTimeDriftingCenters(t, dm, g);
		}
		
		float[][] wsl = new float[tg.gett()][tg.getm()];
		for(int i = 0; i < tg.gett(); i++) {
			for(int node = 0; node < g.getn(); node++) {
				for (int j = g.ind[node]; j < g.ind[node+1]; j++) {
					if (node < g.endv[j]) {
						// Sample from Exp(lambda)
						if (!tg.slices[i].get(j)) {
							wsl[i][j] = (float)((-1.0)*Math.log(1-r.nextDouble())/(-1.0*lambda));
						} else {
							double lambdapos = lambda * 20;
							wsl[i][j] = (float) (Math.log(1-r.nextDouble())/(-1.0*lambdapos));
						}
						wsl[i][g.getEdgeIndex(g.endv[j], node)] = wsl[i][j];
					}
				}
			}
		}
		
		// Add noise in the PCCs
		int nones = 0;
		for (int tt=0; tt<tg.slices.length; tt++) nones += tg.slices[tt].cardinality();
		double erasep = (nones - origPOne*(tg.getm()*tg.gett()))/(2.0*nones);
		for (int tt=0; tt<tg.slices.length; tt++) {
			for(int i=tg.slices[tt].nextSetBit(0); i>=0; i=tg.slices[tt].nextSetBit(i+1)) {
				if (wsl[tt][i]>=0.0 && r.nextDouble() <= erasep) {
					wsl[tt][i] *= -1.0;
					wsl[tt][tg.getReverseEdgeIndex(i)] = wsl[tt][i];
					nones-=2;
				}
			}
		}
		return new WeightedTimeGraph(tg, wsl);
	}
	
	public static TimeGraph generateTimeRWSampling( int slices, 
			double N, int EC,
			Graph g) {
		assert(N < 1);
		return generateTimeRWSampling(slices,N,N,EC,g);
	}
	
	public static TimeGraph generateTimeRWSampling( int slices, 
			double N, double T, int EC,
			Graph g) {
		//assert(N < 1 && T < 1);
		Random r = new Random();
		BitSet[] sl = new BitSet[slices];
		for (int i = 0; i < sl.length; i++) sl[i] = new BitSet(g.getm());
		
		// sample S*g.getm() events
		int e, t;
		for (int i = 0; i < EC; i++) {
			// pick an edge
			do {
				e = r.nextInt(g.getm());
				t = r.nextInt(slices);
			} while (sl[t].get(e));
			sl[t].set(e);
			sl[t].set(g.getReverseEdgeIndex(e));
			expand(e,t,1.0,N,T,sl,g,r);
			if(t<sl.length-1) expand(e,t+1,1.0*T,N,T,sl,g,r);
			if(t>0) expand(e,t-1,1.0*T,N,T,sl,g,r);
		}
		return new TimeGraph(g, sl);
	}	
	
	private static int expand(int e, int t, double P, double N, double T, BitSet[] sl, Graph g, Random r) {
		int nones = 0;
		if(P<0.001) return nones;
		for (int ne:g.getNeighEdges(e)) {
			if (!sl[t].get(ne) && r.nextDouble() < P*N) {
				nones +=2;
				sl[t].set(ne); 
				sl[t].set(g.getReverseEdgeIndex(ne));
				nones += expand(ne, t, P*N, N, T, sl, g, r);
				if(t<sl.length-1) nones += expand(e,t+1,P*T,N,T,sl,g,r);
				//if(t>0) nones += expand(e,t-1,P*N*T,N,T,sl,g,r);
			}
		}
		return nones;
	}
	
	private static int expandGraph(int e, int t, double P, double N, double T, BitSet[] sl, Graph g, Random r) {
		int nones = 0;
		if(P<0.001) return nones;
		int nneighb = g.getNeighEdges(e).size();
		for (int ne:g.getNeighEdges(e)) {
			if (!sl[t].get(ne) && r.nextDouble() < P*N/nneighb) {
				nones +=2;
				sl[t].set(ne); 
				sl[t].set(g.getReverseEdgeIndex(ne));
				nones += expand(ne, t, P*N, N, T, sl, g, r);
			}
		}
		return nones;
	}
	
	private static void expandGraph(int e, double N, Graph g, Random r, BitSet sl) {
		int nneighb = g.getNeighEdges(e).size();
		for (int ne:g.getNeighEdges(e)) {
			if (!sl.get(ne) && r.nextDouble() < N/nneighb) {
				sl.set(ne); 
				sl.set(g.getReverseEdgeIndex(ne));
				expandGraph(ne, N*N, g, r, sl);
			}
		}
	}

	// Sandpile Dynamics
	public static NodeWeightedTimeGraph generateSandPileDynamics(int slices, Graph g) {
		float sl[][] = new float[slices][g.getn()];
		Random r = new Random();
		double addrate = 1.0/g.getn();
		double erate = 1.0/g.getn();
		
		// burn in
		HashSet<Integer> full = new HashSet<Integer>();
		int burninsteps = (int) (g.getn()*(1.0*g.getn()/g.getn()));
		for (int t=0; t < burninsteps; t++) {
			// check for toppling
			full.clear();
			for (int n=0; n < g.getn(); n++) {
				if (sl[0][n] >= 1.0*(g.ind[n+1]-g.ind[n])) {
					full.add(n);
				}
			}
			// if there are full nodes -> cascade
			for (Integer ind:full){
				sl[0][ind] = 0;
				for (int n = g.ind[ind]; n < g.ind[ind+1]; n++){
					sl[0][g.endv[n]] = (float)Math.min(sl[0][g.endv[n]]+1.0, 1.0*(g.ind[g.endv[n]+1]-g.ind[g.endv[n]]));
				}
			} 
			for (int i = 0; i < addrate*g.getn(); i++) { //add and evaporate
				sl[0][r.nextInt(g.getn())] += 1.0;
			}
			for (int n = 0; n < g.getn(); n++) {
				if (sl[0][n] > 0 && r.nextDouble() <= erate) sl[0][n] -= 1.0;
			}
		}
		
		// generate 
		for (int t=1; t < slices; t++) {
			sl[t] = Arrays.copyOf(sl[t-1], sl[t-1].length);
			full.clear();
			// check for toppling
			for (int n=0; n < g.getn(); n++) {
				if (sl[t][n] >= 1.0*(g.ind[n+1]-g.ind[n])) {
					full.add(n);
				}
			}
			// if there is a full node -> cascade
			for (Integer ind:full){
				sl[t][ind] = 0;
				for (int n = g.ind[ind]; n < g.ind[ind+1]; n++){
					sl[t][g.endv[n]] = (float)Math.min(sl[t][g.endv[n]]+1.0, 1.0*(g.ind[g.endv[n]+1]-g.ind[g.endv[n]]));
				}
			} 
			
			for (int i = 0; i < addrate*g.getn(); i++) { //add and evaporate
				sl[t][r.nextInt(g.getn())] += 1.0;
			}
			
			// evaporate
			for (int n = 0; n < g.getn(); n++) {
				if (sl[t][n] > 0 && r.nextDouble() <= erate) 
					sl[t][n] -= 1.0;
			}
		}
		
		return new NodeWeightedTimeGraph(g, sl);
	}
	
	// Adds 1% geometric distributed kernels with p~U(0,1). 
	// Central node is p, 1 hop away: (1-p)p, ... k-hop (1-p)^(k-1)*p
	// Add noise ~N(0,0.01)
	public static NodeWeightedTimeGraph generateNodeWeightedShortestPathDiffusion(int slices, Graph g) {
		double perc = 0.05;
		double noise_amp=0.01;
		double threshold = 3*noise_amp;
		
		
		float sl[][] = new float[slices][g.getn()];
		Random r = new Random();
		
		HashMap<Integer,Integer> level = new HashMap<Integer, Integer>();
		Queue<Integer> q = new PriorityQueue<Integer>();
		
		// add kernels
		for (int k = 0; k < (int)(slices*g.getn()*perc);k++){
			int n = r.nextInt(g.getn());
			int t = r.nextInt(slices);
			double p = r.nextDouble()*10*noise_amp; //r.nextDouble();
			char attf = 'l';
			
			q.clear();
			level.clear();
			
			q.add(n);
			level.put(n, 0);
			Integer current;
			while( (current = q.poll())!=null) {
				sl[t][current] += att(p, 0, level.get(current),attf);
				for(int d=1; att(p,d,level.get(current),attf) > threshold; d++) {
					if (t-d>=0) sl[t-d][current] += att(p, d, level.get(current),attf);
					if (t+d<slices) sl[t+d][current] += att(p, d, level.get(current),attf);
				}
				if (att(p,0,level.get(current)+1,attf) <= threshold) continue;
				for (int i= g.ind[current]; i < g.ind[current+1]; i++) {
					if(q.contains(g.endv[i]) || level.containsKey(g.endv[i])) continue;
					q.add(g.endv[i]);
					level.put(g.endv[i], level.get(current)+1);
				}
			}
		}
		// add noise
		for (int t=0; t < slices; t++) {
			for (int n=0; n < g.getn(); n++) {
				sl[t][n] += r.nextGaussian()*noise_amp;
			}
		}
		
		return new NodeWeightedTimeGraph(g, sl);
	}
	
	// Each node is a linear combination of the cluster time series
	// Each cluster time serie is generated according to a AR(p) model
	// Noise is added independently to every node
	public static NodeWeightedTimeGraph generateRandomNWSoftClusters(int slices, Graph g, double[][] clusters, 
																		 int p, double smoothing,
																		 double amp, double noise) {
		Random r = new Random();
		double[][] y = getRandomSmoothedTimeseries(slices, clusters.length, p,
				smoothing, amp, r);
		return generateNodeWeightedTimeGraph(slices, g, clusters, noise, r, y);
	}
	
	
	// Each node is a linear combination of the cluster time series
	// Each cluster time serie is generated as a sin wave with a random phaze, amp, freq
	// Noise is added independently to every node
	public static NodeWeightedTimeGraph generateSineNWClusters(int slices, Graph g, double[][] clusters, 
			 double amp, double noise) {
			Random r = new Random();
			double[][] y = getSineTimeseries(slices, clusters.length, amp, r);
			return generateNodeWeightedTimeGraph(slices, g, clusters, noise, r, y);
	}

	
	/**
	 * @param slices
	 * @param g
	 * @param clusters
	 * @param noise
	 * @param r
	 * @param y
	 * @return
	 */
	private static NodeWeightedTimeGraph generateNodeWeightedTimeGraph(
			int slices, Graph g, double[][] clusters, double noise, Random r,
			double[][] y) {
		// Generate the node values
		float sl[][] = new float[slices][clusters[0].length];
		for (int t=0; t < slices; t++) {
			for (int c = 0; c < clusters.length; c++) {
				for (int n = 0; n < clusters[c].length; n++) {
					sl[t][n] += clusters[c][n]*y[t][c];
				}
			}
		}
		
		// add noise
		for (int t=0; t < slices; t++) {
			for (int n=0; n < sl[t].length; n++) {
				sl[t][n] += r.nextGaussian()*noise;
				sl[t][n] = Math.max(sl[t][n], 0);
			}
		}
		
		return new NodeWeightedTimeGraph(g, sl);
	}

	/**
	 * @param slices number of time slices
	 * @param nseries number of serie
	 * @param smoothing_window how many values in the past to average
	 * @param smoothing the smoothing parameter alpha in SUM(y(t-k)*alpha^k), k = 0...wmoothing_window
	 * @param amp max amplitude of the serie
	 * @param r a random generator
	 * @return
	 */
	private static double[][] getRandomSmoothedTimeseries(int slices,
			int nseries, int smoothing_window, double smoothing, double amp, Random r) {
		double norm;
		double[][] y = new double[slices][nseries];
		
		// Unfold the model
		for (int t = 0; t < y.length; t++) {
			for (int c = 0; c < y[t].length; c++) {
				y[t][c] = r.nextDouble()*amp;
				// exp weighted average of the last smoothing_window values
				norm = 1;
				for (int l = smoothing_window; l > 0; l--) {
					if (t-l < 0) continue;
					y[t][c] += y[t-l][c]*Math.pow(smoothing, l);
					norm += Math.pow(smoothing, l);
				}
				y[t][c] /= norm;
			}
		}
		return y;
	}
	
	
	/**
	 * @param slices number of time slices
	 * @param nseries number of series
	 * @param smoothing_window how many values in the past to average
	 * @param smoothing the smoothing parameter alpha in SUM(y(t-k)*alpha^k), k = 0...wmoothing_window
	 * @param amp max amplitude of the series
	 * @param r a random generator
	 * @return timeseries
	 */
	private static double[][] getSineTimeseries(int slices,
			int nseries, double amp, Random r) {
		double[][] y = new double[slices][nseries];
		double[][] level_amp_phaze_freq = new double[nseries][4];
		for (int i = 0; i < nseries; i++) {
			// choose the level
			level_amp_phaze_freq[i][0] = r.nextDouble()*amp/2.0;
			// choose the amplitude
			level_amp_phaze_freq[i][1] = r.nextDouble()*level_amp_phaze_freq[i][0];
			// choose the phaze in 0:2*pi
			level_amp_phaze_freq[i][2] = r.nextDouble()*2*Math.PI;
			// choose the frequency 1 full wave = how many ts
			level_amp_phaze_freq[i][3] = 2*Math.PI/r.nextInt((int)(slices/10.0));
		}
		
		for (int i = 0; i < slices; i++) {
			for (int j = 0; j < nseries; j++) {
				y[i][j] = level_amp_phaze_freq[j][0] + 
						  level_amp_phaze_freq[j][1]*Math.sin(level_amp_phaze_freq[j][2] + 
								  i*level_amp_phaze_freq[j][3]);
			}
		}
		
		return y;
	}
	
	
	private static double att(double p, int time_hops, int graph_hops, char form) {
		double res = 0;
		switch(form) {
			case 'g': 
				res = Math.pow((1-p),time_hops+graph_hops)*p;
				break;
			case 'l': 
				if(time_hops+graph_hops > 0) 
					res = p/(0.5*time_hops+graph_hops);
				else 
					res = p;
				break;
		}
		return res;
	}
	
	// slides a window of size length on a time graph and plots distributions
	public static void exploreEdgeDistributions(TimeGraph tg, int length) {
		for (int i = length; i < tg.gett(); i++) {
			int s=0, e = i;
			
			
			// Distribution of edges
//			TreeMap<String,TreeMap<Double,Integer>> 
//				tms = new TreeMap<String,TreeMap<Double,Integer>>();
//			tms.put("edges" + (e-s+1), tg.getEdgeScoreDistribution(s,e));
//			tms.put("edgepairs" + (e-s+1), tg.getEdgePairsScoreDistribution(s,e));
//			tms.put("islands" + (e-s+1), tg.aggregateByTime(s,e).getAggNodeWeighted().getNodeDistribution());
//			ExtToolsDriver.plotHists(tms);
//			ExtToolsDriver.kill("gnuplot");
			
			
			
			TreeMap<String,TreeMap<Double,Integer>> 
			tms1 = new TreeMap<String,TreeMap<Double,Integer>>();
			 
//			// ordered connected positive components
//			tms1.put("ConnComp"+ (e-s+1), tg.aggregateByTime(s,e).getAggNodeWeighted().getNodeDistribution());
			
			// incremental TopDown using MaxST
			tg.aggregateByTime(s, e);
			tms1.put("LB"+ (e-s+1), IntervalBounds.getMaxSTClusterScores(tg));
			
//			// get Line+Star
//			BUp solver = new BUp(tg.aggregateByTime(s,e).getAggNodeWeighted());
//			solver.computeOptimalLookAheadGrow();
//			tms1.put("LineStar" + (e-s+1), solver.getClusterScores());
			
			// Line-Merge only
			tg.aggregateByTime(s,e);
			BUp solver1 = new BUp(tg.getAggNodeWeighted());
			solver1.computeOptimalLM();
			tms1.put("Line" + (e-s+1), solver1.getClusterScores());
			
			TreeMap<Double,Integer> ub_opt_structure = new TreeMap<Double, Integer>();
			tg.aggregateByTime(s, e);
			ub_opt_structure.put(IntervalBounds.getUB(tg), 1);
			tms1.put("UB" + (e-s+1), ub_opt_structure);
			
			ExtToolsDriver.plotClusts(tms1);
			ExtToolsDriver.kill("gnuplot");
		}
	}
	
	public static void main(String[] argv) throws IOException{
		
		
		WeightedTimeGraph wgr = getGridLineSweep(3, 3);
		
		
		Graph gr = generateClustered(20, 5, 0.8, 0.1);
		
		gr = getTestGraph();
		//gr = generateRandom(20, 40);
		//NodeWeightedTimeGraph ntg = generateSandPileDynamics(8000, gr);
		//NodeWeightedTimeGraph ntg = generateNodeWeightedShortestPathDiffusion(8000, gr);
		
		double[][] cl = {{1.0,1.0,0.0,0.0,0.0,0.0,1.0},
						 {0.0,0.0,1.0,0.0,1.0,1.0,0.0},
						 {1.0,1.0,1.0,1.0,0.0,0.0,0.0}};
		
		NodeWeightedTimeGraph ntg = generateRandomNWSoftClusters(8000, gr, cl, 10, 0.9, 10, 0.1);
		String dir = "/home/petko/Dropbox/paper_linkregress/data/random/";
		BufferedWriter bwn = new BufferedWriter(new FileWriter(dir + "nodes"));
		for (int i=0;i<gr.getn();i++) {
			if (gr.names[i].split(",").length==3) {
				bwn.write((Integer.parseInt(gr.names[i].split(",")[0])+1) + "," + 
					  gr.names[i].split(",")[1] + "," + 
					  gr.names[i].split(",")[2] + "\n");
			} else {
				bwn.write((Integer.parseInt(gr.names[i])+1) + "\n");
			}
		}
		bwn.close();
		BufferedWriter bwe = new BufferedWriter(new FileWriter(dir + "edges"));
		for (int i=0;i<gr.getn();i++) 
			for(int j = gr.ind[i]; j < gr.ind[i+1]; j++) 
				if (gr.names[i].split(",").length==3) {
					bwe.write((Integer.parseInt(gr.names[i].split(",")[0])+1) + "," + 
							(Integer.parseInt(gr.names[gr.endv[j]].split(",")[0])+1) + "\n");
				} else {
					bwe.write((Integer.parseInt(gr.names[i])+1) + "," + 
							(Integer.parseInt(gr.names[gr.endv[j]])+1) + "\n");
				}
		bwe.close();
//		for (int t = 0; t < ntg.gett(); t++) {
//			for (int n = 0; n < gr.getn();n++)
//				ntg.wsl[t][n] /= 1.0*(gr.ind[n+1]-gr.ind[n]);
//		}
		IO.writeMatrix(ntg.wsl, ",", dir + "timeseries");
		System.exit(0);
		
		// first probability is persist, second seed
////		Graph g = GraphGenerator.generateScaleFree(300);
//		Graph g = GraphGenerator.generateRandom(100, 190);
////		double Pn = 0.005, Pp = 0.05, Ps = 0.001; // settings
////		TimeGraph tg = generateTimeGraphLocalized(40, Pn, Pp, Ps, g);
//		double N = 0.3, S = 0.1;
		
		TimeGraph tgw = IO.readTGraphEvents(
				 "/home/petko/data/temporal/enron/events",
				 t_res.D, 1, 
				 "pete.davis@enron.com no.address@enron.com enron.announcements@enron.com ");
		DynamicModel dmw = tgw.getDynamicsModel(); 
		
		System.err.print("weeks:\n" +  dmw.toString() + "\n");
		for (int i=0; i < 10; i++ ) {
			DynamicModel dm = dmw;
			
			TimeGraph tgw_gen = GraphGenerator.generateTimeRWSampling(tgw.gett()*3, dm, tgw);
			//TimeGraph tgw_gen = GraphGenerator.generateTimeNonClustered(tgw.gett(), dmw, tgw);
			
			System.err.print("weeks_gen:\n" +  tgw_gen.getDynamicsModel().toString() + "\n");
			
//			tgw.printStringTimeFirstK(0,30, 1000);
//			System.err.print("\n");
//			tgw_gen.printStringTimeFirstK(0, 30, 1000);
		}
		
		TimeGraph tgd = IO.readTGraphEvents(
				 "/home/petko/data/temporal/enron/events",
				 t_res.W, 1, 
				 "pete.davis@enron.com no.address@enron.com enron.announcements@enron.com ");
		DynamicModel dmd = tgd.getDynamicsModel(); 
		System.err.print("days:\n" + dmd.toString());
		
		
		
		Graph g = generateRandom(100, 200);
		TimeGraph tg = generateTimeRWSampling(20, 0.7, 0.1, 100, g);
		System.err.print(tg.toStringTime());
		
		
		tg = IO.readTGraphSigAlert("/home/petko/data/temporal/sigalert_la/preprocess/"+
		"Greater_Los_Angeles.graph");
		tg.thresholdFractionLessThan(0.5);
		boolean conn = tg.isConnected();
		//exploreEdgeDistributions(tg,0);
		
		System.err.print(tg.toStringTime());
		
	}

}
