package misc;

import index.IntervalBounds;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;
import java.io.Writer;
import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import javax.swing.plaf.SliderUI;

import alg.BUp;

import misc.Time.t_res;

import graph.Graph;
import graph.LabeledGraph;
import graph.NodeWeightedTimeGraph;
import graph.TimeGraph;
import graph.Tree;
import graph.WeightedTimeGraph;
import generator.GraphGenerator;

public class IO {
	
	// parses the ILP format
	// first row is  : #graphs
	// second row is : #nodes #edges #nnznodes #solution?
	// #nnznodes lines of node ids
	// #nnznodes lines of node weights
	// #edges lines of edges: node1 node2 weight
	public static Graph readNWEWGraph(String fn) throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		String line = br.readLine();
		line = br.readLine();
		int n = Integer.parseInt(line.split("[ ]+")[0]);
		int m = Integer.parseInt(line.split("[ ]+")[1]);
		int nnzn = Integer.parseInt(line.split("[ ]+")[2]);
		double score = Double.parseDouble(line.split("[ ]+")[3]);
		
		Graph g = new Graph(n, m*2);
		for (int i=0; i<nnzn; i++) {
			line = br.readLine();
			g.names[i] = line.trim();
		}
		g.buildN2I();
		for (int i=0; i<nnzn; i++) {
			line = br.readLine();
			g.wn[i] = Double.parseDouble(line.trim());
		}
		
		// collect edges
		HashMap<String,Double> edges = new HashMap<String, Double>();
		for (int i=0; i<m; i++) {
			line = br.readLine();
			edges.put(line.split(" ")[0] + Common.SEP + line.split(" ")[1], Double.parseDouble(line.split(" ")[2]));
		}
		assert((line = br.readLine()) == null);
		
		// write edges
		int n1, n2;
		int eidx = 0;
		g.ind[0]=0;
		for (int i=0; i < n; i++) {
			g.ind[i+1]=g.ind[i];
			for (String k: edges.keySet()) {
				n1 = g.getNodeIndex(k.split(Common.SEP)[0]);
				n2 = g.getNodeIndex(k.split(Common.SEP)[1]);
				if (n1 == i) {
					g.endv[eidx] = n2;
					g.we[eidx] = edges.get(k);
					g.ind[i+1]++;
					eidx++;
				} else if (n2 == i) {
					g.endv[eidx] = n1;
					g.we[eidx] = edges.get(k);
					g.ind[i+1]++;
					eidx++;
				}
			}
		}
		return g;
	}
	
	
	// parses the ILP format
	// first row is  : #graphs
	// second row is : #nodes #edges #nnznodes #solution?
	// #nnznodes lines of node ids
	// #nnznodes lines of node weights
	// #edges lines of edges: node1 node2 weight
	public static Graph parseILPPCST(String fn) throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		String line = br.readLine();
		line = br.readLine();
		int n = Integer.parseInt(line.split("[ ]+")[0]);
		int m = Integer.parseInt(line.split("[ ]+")[1]);
		int nnzn = Integer.parseInt(line.split("[ ]+")[2]);
		double score = Double.parseDouble(line.split("[ ]+")[3]);
		
		Graph g = new Graph(n, m*2);
		
		int[][] nw = new int[nnzn][2];
		for (int i=0; i<nnzn; i++) {
			line = br.readLine();
			nw[i][0] = Integer.parseInt(line.trim()) -1;
		}
		for (int i=0; i<nnzn; i++) {
			line = br.readLine();
			nw[i][1] = Integer.parseInt(line.trim());
		}
		Arrays.fill(g.wn,0);
		for(int i=0; i<nnzn; i++) {
			g.wn[nw[i][0]] = nw[i][1]; 
		}
		for (int i=0; i< n; i++) {
			g.names[i] = "" + (i+1);
		}
		
		// collect edges
		HashMap<String,Integer> edges = new HashMap<String, Integer>();
		for (int i=0; i<m; i++) {
			line = br.readLine();
			edges.put(line.split(" ")[0] + Common.SEP + line.split(" ")[1], Integer.parseInt(line.split(" ")[2]));
		}
		
		assert((line = br.readLine()) == null);
		
		// write edges
		int n1, n2;
		int eidx = 0;
		g.ind[0]=0;
		for (int i=0; i < n; i++) {
			g.ind[i+1]=g.ind[i];
			for (String k: edges.keySet()) {
				n1 = Integer.parseInt(k.split(Common.SEP)[0]);
				n2 = Integer.parseInt(k.split(Common.SEP)[1]);
				if (n1 == i+1) {
					g.endv[eidx] = n2-1;
					g.we[eidx] = edges.get(k);
					g.ind[i+1]++;
					eidx++;
				} else if (n2 == i+1) {
					g.endv[eidx] = n1-1;
					g.we[eidx] = edges.get(k);
					g.ind[i+1]++;
					eidx++;
				}
			}
		}
		g.opt_nw = g.getP() - score;
		//System.out.print("Read: " + fn + "\nSCORE: " + score + "\n");
		return g;
	}
	
	
	public static void writeGraph(String fn) throws IOException {
		
	}
	
	public static void writeGraphMetis(String fn, Graph g) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write(g.getn() + " " + g.getm()/2 + " 1\n");
		for (int i=0;i < g.getn(); i++) {
			int c = 0;
			for (int j=g.ind[i]; j < g.ind[i+1]; j++) {
				if (j>g.ind[i]) bw.write(" ");
				bw.write((g.endv[j]+1) + " " + ((int)g.we[j]));
			}
			bw.write("\n");
		}
		bw.close();
	}
	
	public static ArrayList<String> readPartitioningMetis(String fn) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fn));
		ArrayList<String> res = new ArrayList<String>();
		String line;
		while (null != (line = br.readLine())) {
			res.add(line);
		}
		br.close();
		return res;
	}
	
	public static void writeHyperGraphHMetis(String fn, Graph g, String format) throws IOException {
		// format is the same as the input to shmetis
		// <empty> no weights
		// 1 - weights on the hyperedges (sum the edge weights in our case)
		// 10 - weights on nodes
		// 11 - weights on both
		ArrayList<Integer> edges = g.obtainUndirectedEdges();
		assert(edges.size()==g.getm()/2);
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write(g.getn() + " " +  g.getm()/2 +  " " +  format + "\n");
		for (int i=0;i < g.getn(); i++) {
			String line = "";
			if (format.equals("11") || format.equals("1")) { // weighted edges
				// sum the weights on the edges adjacent to the node
				int sum = 0;
				for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
					sum += (int)g.we[j];
				}
				line = sum + " ";
			}
			for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
				int idx = edges.indexOf((i > g.endv[j])?g.getReverseEdgeIndex(j):j);
				assert(idx >=0);
				line += (idx+1) + " ";
			}
			if (!line.trim().equals("")) bw.write(line.trim() + "\n");
		}
		if (format.equals("11") || format.equals("10")) { // weights on the nodes (edges in our case)
			for (int i = 0; i < edges.size(); i++) {
				bw.write((int)g.we[edges.get(i)] + "\n");
			}
		}
		bw.close();
	}
	
	public static HashMap<Integer, Integer> readPartitioningHMetis(String fn, Graph g) throws IOException {
		ArrayList<Integer> edges = g.obtainUndirectedEdges();
		BufferedReader br = new BufferedReader(new FileReader(fn));
		HashMap<Integer,Integer> res = new HashMap<Integer,Integer>();
		String line;
		int cnt = 0;
		while (null != (line = br.readLine())) {
			res.put(edges.get(cnt),Integer.parseInt(line.trim()));
			cnt++;
		}
		br.close();
		return res;
	}
	
	public static NodeWeightedTimeGraph readGraphNodeListEdgeListTimes(String efn, 
						String ntimesfn, String sep) throws IOException{
		Graph g = readGraphNodeListEdgeList(efn,sep);
		System.err.print("Created Graph Structure\n");
		ArrayList<float[]> lines = new ArrayList<float[]>();
		BufferedReader vbr = new BufferedReader(new FileReader(ntimesfn));
		String line = null;
		String[] linespl = null;
		while((line = vbr.readLine() )!=null) {
			linespl = line.split(sep);
			lines.add(new float[linespl.length]);
			assert(linespl.length == g.getn());
			for (int i = 0; i < g.getn(); i++) {
				lines.get(lines.size()-1)[i] = 
					Float.parseFloat(linespl[i]);
			}
			System.err.print("read timestamps " +  lines.size() + "\n");
		}
		vbr.close();
		float[][] nodeVals = new float [lines.size()][g.getn()];
		for (int i = 0; i < lines.size(); i++) nodeVals[i] = lines.get(i);
		return new NodeWeightedTimeGraph(g, nodeVals); 
	}
	
	// Expects ordered edges in both directions
	// 0-based
	public static Graph readGraphNodeListEdgeList(String efn, 
			String sep) throws IOException{
		BufferedReader ebr = new BufferedReader(new FileReader(efn));
		ArrayList<String> lines = new ArrayList<String>();
		String line = null;
		int maxnode=-1;
		while((line = ebr.readLine() )!=null) {
			lines.add(line);
			maxnode = Math.max(maxnode, Integer.parseInt(line.split(sep)[0]));
			maxnode = Math.max(maxnode, Integer.parseInt(line.split(sep)[1]));
		}
		ebr.close();
		Graph g = new Graph(maxnode+1, lines.size());
		int nidx = 0, ecnt = 0, from, to;
		for (int i =0 ; i < lines.size(); i++) {
			from = Integer.parseInt(lines.get(i).split(sep)[0]);
			to = Integer.parseInt(lines.get(i).split(sep)[1]);
			if(nidx<from) {
				g.ind[nidx+1] = g.ind[nidx] + ecnt;
				ecnt=0; 
				nidx++;
				assert(nidx <= from);
				while (nidx < from) {
					g.ind[nidx+1] = g.ind[nidx] + ecnt;
					nidx++;
					ecnt = 0;
				}
			}
			g.endv[i] = to;
			ecnt++;
		}
		g.ind[g.getn()] = lines.size();
		for (int i=0; i < g.getn();i++) g.names[i] = "" + i;
		assert(g.isUndirected());
		g.buildN2I();
		return g;
	}
	
	
	/*	Reads an edge list graph
		First line is: HEADER <tab> n <tab> m
		Expects 1) edges in both direction and 
		        2) edges are sorted by source 
	*/ 
	
	public static Graph readGraphEdgeList(String fn) throws IOException {
		return readGraphEdgeList(fn,true);
	}
	
	public static Graph readGraphEdgeList(String fn, boolean largestcomponent) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fn));
		String line = br.readLine();
		if(!line.split(Common.SEP)[0].equals("HEADER")){
			System.err.print("Unable to find HEADER in the graph file " + fn + "\n" +
					"First line(SEP= " +Common.SEP+ "):\n" + line + "\n");
		}
		
		int n = Integer.parseInt(line.split(Common.SEP)[1]);
		int m = Integer.parseInt(line.split(Common.SEP)[2]);
		
		// creating the structures to create the graph with
		String[] nodes = new String[n];
		HashSet<String> nds = new HashSet<String>();
		String[] edges = new String[m*2]; // edges
		String[] sline;
		HashMap<String, Double> ew = new HashMap<String, Double>();
		
		int cnt = 0;
		while((line = br.readLine()) != null) {
			sline = line.split(Common.SEP);
			if (sline[0].trim().equals("")) {
				System.err.print(line);
			}
			
			nds.add(sline[0].trim());
			nds.add(sline[1].trim());
			edges[2*cnt] = sline[0].trim();
			edges[2*cnt+1] = sline[1].trim();
			HashMap<Integer,Double> em = new HashMap<Integer, Double>();
			if (sline.length == 3) {
				ew.put(edges[2*cnt] + Common.SEP + edges[2*cnt+1], 
						Double.parseDouble(sline[2]));
			} else {
				ew.put(edges[2*cnt] + Common.SEP + edges[2*cnt+1], 1.0);
			}
			cnt++;
		}
		br.close();
		
		cnt = 0;
		for(String node:nds) {nodes[cnt] = node;cnt++;}
		Graph g = new Graph(edges, nodes);
		if (largestcomponent) g = g.getLargestConnectedComponent();
		
		for (int i=0; i < g.getn(); i++) {
			for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
				if (ew.containsKey(g.names[i] +Common.SEP + g.names[g.endv[j]])){
					g.we[j] = ew.get(g.names[i] +Common.SEP + g.names[g.endv[j]]);
				} 
			}
		}
		g.aggVolumesInWn();
		g.buildN2I();
		return g;
	}
	
	public static LabeledGraph readGraphEdgeListNodeLabeled(String fn, String fnlabs, int minf, HashSet<String> remove) 
						throws IOException {
		Graph g = readGraphEdgeList(fn);
		g.buildN2I();
		String[] labs = new String[g.getn()];
		Arrays.fill(labs, "");
		BufferedReader br = new BufferedReader(new FileReader(fnlabs));
		String line;
		String[] sline;
		HashMap<String, Integer> freq = new HashMap<String, Integer>();
		while((line = br.readLine()) != null) {
			sline = line.split("\t");
			Integer node = g.n2i.get(sline[0]);
			if (null == node) continue;
			for (int i=1; i < sline.length; i++) {
				if(remove.contains(sline[i])) continue;
				if (!freq.containsKey(sline[i])) freq.put(sline[i], 0);
				freq.put(sline[i], freq.get(sline[i])+1);
				labs[node] += (labs[node].equals("")?"":Common.SEP) + sline[i];
			}
		}
		for (int j = 0; j < labs.length; j++) {
			sline = labs[j].split(Common.SEP);
			int cnt = 0; labs[j] = "";
			for (int i=1; i < sline.length; i++) {
				if(freq.get(sline[i]) < minf) continue;
				labs[j] += (labs[j].equals("")?"":Common.SEP) + sline[i];
			}
		}
		
		return new LabeledGraph(g, labs);
	}
	
	public static void writeGraphEdgeList(String fn, Graph g) throws IOException {
		// write Header
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write("HEADER\t" + g.getn() + "\t" + g.getm() + "\n");
		for (int i=0; i < g.getn(); i++) {
			for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
				bw.write(g.names[i] + "\t" + g.names[g.endv[j]] + 
						 "\t" + g.we[j] + "\n");
			}	
		}
		bw.close();
	}
	
	public static void writeGraphEdgeListIndices(String fn, Graph g) throws IOException {
		// write Header
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		//bw.write("HEADER\t" + g.getn() + "\t" + g.getm() + "\n");
		for (int i=0; i < g.getn(); i++) {
			for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
				bw.write(i + "\t" + g.endv[j] + 
						 "\t" + g.we[j] + "\n");
			}	
		}
		bw.close();
	}
	
	public static void writeGraph(String fn, Graph g) throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write("" + g.names[0]); for (int i=1; i < g.getn(); i++) bw.write("," + g.names[i]); bw.write("\n");
		bw.write("" + g.wn[0]); for (int i=1; i < g.getn(); i++) bw.write("," + g.wn[i]); bw.write("\n");
		bw.write("" + g.ind[0]); for (int i=1; i < g.getn()+1; i++) bw.write("," + g.ind[i]); bw.write("\n");
		if (g.getm() > 0) {
			bw.write(g.getm() + "\n");
			bw.write("" + g.endv[0]); for (int i=1; i < g.getm(); i++) bw.write("," + g.endv[i]); bw.write("\n");
			bw.write("" + g.we[0]); for (int i=1; i < g.getm(); i++) bw.write("," + g.we[i]); bw.write("\n");
		}	
		bw.close();
	}
	
	public static void writeTGraph(String fn, TimeGraph tg) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write("" + tg.names[0]); for (int i=1; i < tg.getn(); i++) bw.write("," + tg.names[i]); bw.write("\n");
		bw.write("" + tg.wn[0]); for (int i=1; i < tg.getn(); i++) bw.write("," + tg.wn[i]); bw.write("\n");
		bw.write("" + tg.ind[0]); for (int i=1; i < tg.getn()+1; i++) bw.write("," + tg.ind[i]); bw.write("\n");
		if (tg.getm() > 0) {
			bw.write(tg.getm() + "\n");
			bw.write("" + tg.endv[0]); for (int i=1; i < tg.getm(); i++) bw.write("," + tg.endv[i]); bw.write("\n");
			bw.write("" + tg.we[0]); for (int i=1; i < tg.getm(); i++) bw.write("," + tg.we[i]); bw.write("\n");
			
			if (tg.gett() > 0) bw.write(tg.gett() + "\n");
			
			for (int t = 0; t < tg.gett(); t++) {
				boolean first = true;
				for (int i=0; i < tg.getm(); i++){ 
					if(tg.slices[t].get(i)) {
						if (!first) {
							bw.write("," + i);
						} else {
							bw.write("" + i); first = false;
						}
					} 
				}
				bw.write("\n");
			}
		}	
		bw.close();
	}
	
	public static void writeTGraphWeighted(String fn, WeightedTimeGraph tg) throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write("" + tg.names[0]); for (int i=1; i < tg.getn(); i++) bw.write("," + tg.names[i]); bw.write("\n");
		bw.write("" + tg.wn[0]); for (int i=1; i < tg.getn(); i++) bw.write("," + tg.wn[i]); bw.write("\n");
		bw.write("" + tg.ind[0]); for (int i=1; i < tg.getn()+1; i++) bw.write("," + tg.ind[i]); bw.write("\n");
		if (tg.getm() > 0) {
			bw.write(tg.getm() + "\n");
			bw.write("" + tg.endv[0]); for (int i=1; i < tg.getm(); i++) bw.write("," + tg.endv[i]); bw.write("\n");
			bw.write("" + tg.we[0]); for (int i=1; i < tg.getm(); i++) bw.write("," + tg.we[i]); bw.write("\n");
			
			if (tg.gett() > 0) bw.write(tg.gett() + "\n");
			
			for (int t = 0; t < tg.gett(); t++) {
				bw.write("" + tg.wsl[t][0]);
				for (int i=1; i < tg.getm(); i++){ 
					bw.write("," + tg.wsl[t][i]);
				}
				bw.write("\n");
			}
		}	
		bw.close();
		
	}
	
	public static void writeTGraphQuadruples(String fn, TimeGraph tg) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (int t = 0; t < tg.gett(); t++) {
			for (int s = 0; s < tg.getn(); s++) {
				for (int j = tg.ind[s]; j < tg.ind[s+1]; j++) {
					if (s < tg.endv[j]) {
						bw.write(s + "," + tg.endv[j] + "," + t + "," +(tg.slices[t].get(j)?"1":"-1") + "\n");
					}
				}
			}
		}
		bw.close();
	}
	
	private static void writeTGraphQuadruples(String fn, TimeGraph tg,
			float[][] pv) throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (int t = 0; t < tg.gett(); t++) {
			for (int s = 0; s < tg.getn(); s++) {
				for (int j = tg.ind[s]; j < tg.ind[s+1]; j++) {
					if (s < tg.endv[j]) {
						bw.write(s + "," + tg.endv[j] + "," + t + "," +pv[t][j] + "\n");
					}
				}
			}
		}
		bw.close();
		
	}
	
	public static void writeTGraphWeightedQuadruples(String fn,
			WeightedTimeGraph wtg) throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (int t = 0; t < wtg.gett(); t++) {
			for (int s = 0; s < wtg.getn(); s++) {
				for (int j = wtg.ind[s]; j < wtg.ind[s+1]; j++) {
					if (s < wtg.endv[j]) {
						bw.write(wtg.names[s] + "," + wtg.names[wtg.endv[j]] + "," + t + "," + wtg.wsl[t][j] + "\n");
					}
				}
			}
		}
		bw.close();
	}
	
	public static void writeTGraphQuadruplesLogOdds(String fn, TimeGraph tg) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (int t = 0; t < tg.gett(); t++) {
			for (int s = 0; s < tg.getn(); s++) {
				for (int j = tg.ind[s]; j < tg.ind[s+1]; j++) {
					
					if (s < tg.endv[j]) {
						bw.write(s + "," + tg.endv[j] + "," + t + "," + 
								((tg.nodescores[s][t] + tg.nodescores[tg.endv[j]][t])/2.0) + "\n");
					}
				}
			}
		}
		bw.close();
	}
	
	// outputs two files fn.graph and fn.data
	// if addHeaders, the files are prepended by HEADERS to be later
	// used by readNWGraph
	public static void writeNodeWeightedTGraphQuadruples(String fn,
			NodeWeightedTimeGraph ntg, boolean addHeaders) throws IOException {
		// graph
		BufferedWriter bwg = new BufferedWriter(new FileWriter(fn + ".graph"));
		if (addHeaders) {
			bwg.write("HEADER," + ntg.getn() + "," + ntg.getm() + "\n");
		}
		for (int i=0; i < ntg.getn(); i++) {
			for (int j = ntg.ind[i] ; j < ntg.ind[i+1]; j++) {
				bwg.write(ntg.names[i] + "," + ntg.names[ntg.endv[j]] + "," + ntg.we[j] + "\n");
			}
		}	
		bwg.close();
		
		// Timeseries
		BufferedWriter bwd = new BufferedWriter(new FileWriter(fn + ".data"));
		if (addHeaders) {
			bwd.write("HEADER," + ntg.gett() + "\n");
		}
		for (int t = 0; t < ntg.gett(); t++) {
			for (int s = 0; s < ntg.getn(); s++) {
				bwd.write(ntg.names[s] + "," + t + "," + ntg.wsl[t][s] + "\n");
			}
		}
		bwd.close();
	}
	
	public static Graph readGraph(String fn) throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		Graph g = null;
		String line = null;
		String[] sline = null;
		
		line = br.readLine(); sline = line.split(",");
		String[] names = new String[sline.length]; for (int i=0; i < names.length; i++) names[i] = sline[i];
		
		line = br.readLine(); sline = line.split(",");
		double[] wn = new double[sline.length]; 
		for (int i=0; i < wn.length; i++) {
			if ("-Infinity".equals(sline[i])) wn[i] = Double.NEGATIVE_INFINITY;
			else if ("Infinity".equals(sline[i])) wn[i] = Double.POSITIVE_INFINITY;
			else wn[i] = Double.parseDouble(sline[i]);
		}
		
		line = br.readLine(); sline = line.split(",");
		int[] ind = new int[sline.length]; for (int i=0; i < ind.length; i++) ind[i] = Integer.parseInt(sline[i]);
		
		line = br.readLine(); 
		int m = Integer.parseInt(line);
		
		if (m > 0) {
			line = br.readLine(); sline = line.split(",");
			int[] endv = new int[sline.length]; for (int i=0; i < endv.length; i++) endv[i] = Integer.parseInt(sline[i]);
			
			line = br.readLine(); sline = line.split(",");
			double[] we = new double[sline.length]; 
			for (int i=0; i < we.length; i++) {
				if ("-Infinity".equals(sline[i])) we[i] = Double.NEGATIVE_INFINITY;
				else if ("Infinity".equals(sline[i])) we[i] = Double.POSITIVE_INFINITY;
				else we[i] = Double.parseDouble(sline[i]);
			}

			g = new Graph(wn.length, we.length);
			g.ind = ind; g.names = names; g.wn = wn; g.we = we; g.endv = endv;
		} else {
			g = new Graph(wn.length, 0);
			g.ind = ind; g.names = names; g.wn = wn;
		}
		br.close();
		return g;
		
	}
	
	// expects that the input is sorted by time 
	public static WeightedTimeGraph readTGraphQuadruplesWeighted(String fn) 
	              throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		int n=0 , m = 0, t = 0; 
		HashMap<String, HashMap<String,ArrayList<Double>>> gr = 
			new HashMap<String, HashMap<String,ArrayList<Double>>>();
		String line = null;
		String n1, n2;
		double val;
		String prevline = "";
		while((line = br.readLine()) != null) {
			if(line.equals(prevline)) continue;
			n1 = line.split(",")[0];
			n2 = line.split(",")[1];
			val = Double.parseDouble(line.split(",")[3]);
			t = Math.max(t, Integer.parseInt(line.split(",")[2]));
			// add n1's edge
			if (!gr.containsKey(n1)) {
				gr.put(n1, new HashMap<String, ArrayList<Double>>()); n++;
			}
			if (!gr.get(n1).containsKey(n2)) { 
				gr.get(n1).put(n2, new ArrayList<Double>());m++;
			}
			gr.get(n1).get(n2).add(val);
			if (gr.get(n1).get(n2).size() != t+1){
				System.err.print(line );
			}
			// add n2's edge
			if (!gr.containsKey(n2)) {
				gr.put(n2, new HashMap<String, ArrayList<Double>>()); n++;
			}
			if (!gr.get(n2).containsKey(n1)) { 
				gr.get(n2).put(n1, new ArrayList<Double>());m++;
			}
			gr.get(n2).get(n1).add(val);
			assert (gr.get(n2).get(n1).size() == t+1);
			prevline = line;
		}
		
		// create graph
		int idx = 0;
		HashMap<String,Integer> nid = new HashMap<String, Integer>();
		Graph g = new Graph(n,m);
		// set = nodes
		for (String node: gr.keySet()) {
			if (!nid.containsKey(node)) nid.put(node, idx++);
			g.names[nid.get(node)] = node;
			g.ind[nid.get(node)+1] = g.ind[nid.get(node)] + gr.get(node).size();
		}
		// set edges
		idx = 0;
		for (String from: gr.keySet()) {
			for (String to: gr.get(from).keySet()){
				g.endv[idx++] = nid.get(to);
			}
		}
		// set time slices
		float[][] slices = new float[t+1][g.getm()];
		idx = 0;
		for (String from: gr.keySet()) {
			for (String to: gr.get(from).keySet()){
				for (int i= 0; i < gr.get(from).get(to).size();i++) {
					slices[i][idx] = gr.get(from).get(to).get(i).floatValue();
				}
				idx++;
			}
		}
	
		WeightedTimeGraph tg = new WeightedTimeGraph(g, slices);
		br.close();
		return tg;
	}
	
	// expects that the input is sorted by time 
	public static WeightedTimeGraph readTGraphQuadruplesPvalues(String fn, float mu) 
	              throws IOException{
		if (mu <= 0) return readTGraphQuadruplesWeighted(fn);
		BufferedReader br = new BufferedReader(new FileReader(fn));
		int n=0 , m = 0, t = 0; 
		HashMap<String, HashMap<String,ArrayList<Double>>> gr = 
			new HashMap<String, HashMap<String,ArrayList<Double>>>();
		String line = null;
		String n1, n2;
		Double val;
		String prevline = "";
		int linen = 1;
		while((line = br.readLine()) != null) {
			if(line.equals(prevline)) continue;
			n1 = line.split(",")[0];
			n2 = line.split(",")[1];
			val = Double.parseDouble(line.split(",")[3]);
			if (val.isNaN()) {
				System.err.print("Not a number encountered when reading file at line " + linen);
				System.exit(-1);
			}
			t = Math.max(t, Integer.parseInt(line.split(",")[2]));
			// add n1's edge
			if (!gr.containsKey(n1)) {
				gr.put(n1, new HashMap<String, ArrayList<Double>>()); n++;
			}
			if (!gr.get(n1).containsKey(n2)) { 
				gr.get(n1).put(n2, new ArrayList<Double>());m++;
			}
			gr.get(n1).get(n2).add(val);
			if (gr.get(n1).get(n2).size() != t+1){
				System.err.print(line );
			}
			// add n2's edge
			if (!gr.containsKey(n2)) {
				gr.put(n2, new HashMap<String, ArrayList<Double>>()); n++;
			}
			if (!gr.get(n2).containsKey(n1)) { 
				gr.get(n2).put(n1, new ArrayList<Double>());m++;
			}
			gr.get(n2).get(n1).add(val);
			assert (gr.get(n2).get(n1).size() == t+1);
			prevline = line;
			linen++;
		}
		
		// create graph
		int idx = 0;
		HashMap<String,Integer> nid = new HashMap<String, Integer>();
		Graph g = new Graph(n,m);
		// set = nodes
		for (String node: gr.keySet()) {
			if (!nid.containsKey(node)) nid.put(node, idx++);
			g.names[nid.get(node)] = node;
			g.ind[nid.get(node)+1] = g.ind[nid.get(node)] + gr.get(node).size();
		}
		// set edges
		idx = 0;
		for (String from: gr.keySet()) {
			for (String to: gr.get(from).keySet()){
				g.endv[idx++] = nid.get(to);
			}
		}
		// set time slices
		float[][] slices = new float[t+1][g.getm()];
		idx = 0;
		for (String from: gr.keySet()) {
			for (String to: gr.get(from).keySet()){
				for (int i= 0; i < gr.get(from).get(to).size();i++) {
					slices[i][idx] = gr.get(from).get(to).get(i).floatValue();
					slices[i][idx] = (float)(-Math.log(slices[i][idx]/mu)/Math.log(2));
				}
				idx++;
			}
		}
	
		WeightedTimeGraph tg = new WeightedTimeGraph(g, slices);
		br.close();
		return tg;
	}
	
	
	// expects that the input is sorted by time 
	public static TimeGraph readTGraphQuadruples(String fn) 
	              throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		int n=0 , m = 0, t = 0; 
		HashMap<String, HashMap<String,ArrayList<Double>>> gr = 
			new HashMap<String, HashMap<String,ArrayList<Double>>>();
		String line = null;
		String n1, n2;
		double val;
		String prevline = "";
		while((line = br.readLine()) != null) {
			if(line.equals(prevline)) continue;
			n1 = line.split(",")[0];
			n2 = line.split(",")[1];
			val = Double.parseDouble(line.split(",")[3]);
			t = Math.max(t, Integer.parseInt(line.split(",")[2]));
			// add n1's edge
			if (!gr.containsKey(n1)) {
				gr.put(n1, new HashMap<String, ArrayList<Double>>()); n++;
			}
			if (!gr.get(n1).containsKey(n2)) { 
				gr.get(n1).put(n2, new ArrayList<Double>());m++;
			}
			gr.get(n1).get(n2).add(val);
			if (gr.get(n1).get(n2).size() != t+1){
				System.err.print(line );
			}
			// add n2's edge
			if (!gr.containsKey(n2)) {
				gr.put(n2, new HashMap<String, ArrayList<Double>>()); n++;
			}
			if (!gr.get(n2).containsKey(n1)) { 
				gr.get(n2).put(n1, new ArrayList<Double>());m++;
			}
			gr.get(n2).get(n1).add(val);
			assert (gr.get(n2).get(n1).size() == t+1);
			prevline = line;
		}
		
		// create graph
		int idx = 0;
		HashMap<String,Integer> nid = new HashMap<String, Integer>();
		Graph g = new Graph(n,m);
		// set = nodes
		for (String node: gr.keySet()) {
			if (!nid.containsKey(node)) nid.put(node, idx++);
			g.names[nid.get(node)] = node;
			g.ind[nid.get(node)+1] = g.ind[nid.get(node)] + gr.get(node).size();
		}
		// set edges
		idx = 0;
		for (String from: gr.keySet()) {
			for (String to: gr.get(from).keySet()){
				g.endv[idx++] = nid.get(to);
			}
		}
		// set time slices
		BitSet[] slices = new BitSet[t+1];
		for (int i = 0; i <= t; i++) slices[i] = new BitSet(t);
		idx = 0;
		for (String from: gr.keySet()) {
			for (String to: gr.get(from).keySet()){
				for (int i= 0; i < gr.get(from).get(to).size();i++) {
					if (gr.get(from).get(to).get(i) > 0) {
						slices[i].set(idx);
					}
				}
				idx++;
			}
		}
	
		TimeGraph tg = new TimeGraph(g, slices);
		br.close();
		return tg;
	}
	
	public static HashMap<String, String> readHashMap(String nlfn) {
		HashMap<String, String> res = null; 
		try {
			res = new HashMap<String, String>();	
			BufferedReader br = new BufferedReader(new FileReader(nlfn));
			String line = null;
			
			while((line = br.readLine())!=null) {
				res.put(line.split(",")[0], line.split(",")[1]);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return res;
	}
	
	public static HashMap<String, String> readNodeHighways(String nlfn) {
		HashMap<String, String> res = null; 
		try {
			res = new HashMap<String, String>();	
			BufferedReader br = new BufferedReader(new FileReader(nlfn));
			String line = null;
			
			while((line = br.readLine())!=null) {
				res.put(line.split(",")[0], line.split(",")[1] + line.split(",")[2] + "-" +  line.split(",")[4]);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return res;
	}
	
	public static TimeGraph readTGraph(String fn) throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		TimeGraph tg = null; 
		Graph g = null;
		String line = null;
		String[] sline = null;
		
		line = br.readLine(); sline = line.split(",");
		String[] names = new String[sline.length]; for (int i=0; i < names.length; i++) names[i] = sline[i];
		
		line = br.readLine(); sline = line.split(",");
		double[] wn = new double[sline.length]; 
		for (int i=0; i < wn.length; i++) {
			if ("-Infinity".equals(sline[i])) wn[i] = Double.NEGATIVE_INFINITY;
			else if ("Infinity".equals(sline[i])) wn[i] = Double.POSITIVE_INFINITY;
			else wn[i] = Double.parseDouble(sline[i]);
		}
		
		line = br.readLine(); sline = line.split(",");
		int[] ind = new int[sline.length]; for (int i=0; i < ind.length; i++) ind[i] = Integer.parseInt(sline[i]);
		
		line = br.readLine(); 
		int m = Integer.parseInt(line);
		
		if (m > 0) {
			line = br.readLine(); sline = line.split(",");
			int[] endv = new int[sline.length]; for (int i=0; i < endv.length; i++) endv[i] = Integer.parseInt(sline[i]);
			
			line = br.readLine(); sline = line.split(",");
			double[] we = new double[sline.length]; 
			for (int i=0; i < we.length; i++) {
				if ("-Infinity".equals(sline[i])) we[i] = Double.NEGATIVE_INFINITY;
				else if ("Infinity".equals(sline[i])) we[i] = Double.POSITIVE_INFINITY;
				else we[i] = Double.parseDouble(sline[i]);
			}
			
			line = br.readLine(); 
			int t = Integer.parseInt(line);
			BitSet[] slices = new BitSet[t]; 
			
			for (int tt = 0; tt < t; tt++) {
				slices[tt] = new BitSet(m);
				line = br.readLine(); 
				if("".equals(line)) continue;
				sline = line.split(",");
				for (int i=0; i < sline.length; i++) slices[tt].set(Integer.parseInt(sline[i]));
			}
			
			g = new Graph(wn.length, we.length);
			g.ind = ind; g.names = names; g.wn = wn; g.we = we; g.endv = endv;
			
			tg = new TimeGraph(g, slices);
		} else {
			g = new Graph(wn.length, 0);
			g.ind = ind; g.names = names; g.wn = wn;
			BitSet[] slices = null;
			tg = new TimeGraph(tg, slices);
		}
		br.close();
		return tg;
	}
	
	public static HashMap<Integer,HashMap<Integer,Double>> loadNodeUBs(String fn, WeightedTimeGraph tg) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fn));
		HashMap<Integer,HashMap<Integer,Double>> nubs = new HashMap<Integer,HashMap<Integer,Double>>();
		String line = null;
		int i, t;
		double d;
		while ((line = br.readLine())!=null) {
			t = Integer.parseInt(line.split(",")[1]);
			d = Double.parseDouble(line.split(",")[2]);
			if (!nubs.containsKey(t)) nubs.put(t,new HashMap<Integer,Double>());
        	nubs.get(t).put(tg.getNodeIndex(line.split(",")[0]),d);
		}
		return nubs;
	}
	
	public static WeightedTimeGraph readTGraphWeighted(String fn) throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(fn));
		WeightedTimeGraph tg = null; 
		Graph g = null;
		String line = null;
		String[] sline = null;
		
		line = br.readLine(); sline = line.split(",");
		String[] names = new String[sline.length]; for (int i=0; i < names.length; i++) names[i] = sline[i];
		
		line = br.readLine(); sline = line.split(",");
		double[] wn = new double[sline.length]; 
		for (int i=0; i < wn.length; i++) {
			if ("-Infinity".equals(sline[i])) wn[i] = Double.NEGATIVE_INFINITY;
			else if ("Infinity".equals(sline[i])) wn[i] = Double.POSITIVE_INFINITY;
			else wn[i] = Double.parseDouble(sline[i]);
		}
		
		line = br.readLine(); sline = line.split(",");
		int[] ind = new int[sline.length]; for (int i=0; i < ind.length; i++) ind[i] = Integer.parseInt(sline[i]);
		
		line = br.readLine(); 
		int m = Integer.parseInt(line);
		
		if (m > 0) {
			line = br.readLine(); sline = line.split(",");
			int[] endv = new int[sline.length]; 
			for (int i=0; i < endv.length; i++) endv[i] = Integer.parseInt(sline[i]);
			
			line = br.readLine(); sline = line.split(",");
			double[] we = new double[sline.length]; 
			for (int i=0; i < we.length; i++) {
				if ("-Infinity".equals(sline[i])) we[i] = Double.NEGATIVE_INFINITY;
				else if ("Infinity".equals(sline[i])) we[i] = Double.POSITIVE_INFINITY;
				else we[i] = Double.parseDouble(sline[i]);
			}
			
			line = br.readLine(); 
			int t = Integer.parseInt(line);
			float[][] slices = new float[t][m]; 
			
			for (int tt = 0; tt < t; tt++) {
				line = br.readLine(); 
				sline = line.split(",");
				assert(sline.length == m);
				for (int i=0; i < sline.length; i++) 
					slices[tt][i] = Float.parseFloat(sline[i]);
			}
			
			g = new Graph(wn.length, we.length);
			g.ind = ind; g.names = names; g.wn = wn; g.we = we; g.endv = endv;
			
			tg = new WeightedTimeGraph(g, slices);
		} else {
			g = new Graph(wn.length, 0);
			g.ind = ind; g.names = names; g.wn = wn;
			float[][] slices = null;
			tg = new WeightedTimeGraph(tg, slices);
		}
		br.close();
		return tg;
	}
	
	
	public static TimeGraph readTGraphTwitter(String fn) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fn));
		String line = br.readLine();
		int n = Integer.parseInt(line.split(",")[0]);
		int m = Integer.parseInt(line.split(",")[1]);
		int t = Integer.parseInt(line.split(",")[2]);
		
		// create the graph
		String[] nodes = new String[n];
		HashSet<String> nds = new HashSet<String>();
		String[] edges = new String[m*4]; // edges
		String[] sline;
		HashMap<String,HashMap<Integer, Double>> ehistory = 
			new HashMap<String, HashMap<Integer,Double>>();
		int cnt = 0;
		while((line = br.readLine()) != null) {
			sline = line.split(",");
			if (sline[0].trim().equals("")) {
				System.err.print(line);
			}
			nds.add(sline[0].trim());
			nds.add(sline[1].trim());
			edges[4*cnt] = sline[0];
			edges[4*cnt+1] = sline[1];
			edges[4*cnt+2] = sline[1];
			edges[4*cnt+3] = sline[0];
			HashMap<Integer,Double> em = new HashMap<Integer, Double>();
			for (int i=2; i < sline.length; i++) {
				em.put(Integer.parseInt(sline[i].split(":")[0]), 
					   Double.parseDouble(sline[i].split(":")[1]));
			}
			ehistory.put(sline[0] + Common.SEP + sline[1], em);
			cnt++;
		}
		br.close();
		
		cnt = 0;
		for(String node:nds) {nodes[cnt] = node;cnt++;}
		Graph g = new Graph(edges, nodes);
		g = g.getLargestConnectedComponent();
		
		HashMap<Integer, HashMap<Integer,Double>> vals = new HashMap<Integer, HashMap<Integer,Double>>();
		for (int i=0; i < g.getn(); i++) {
			for (int j = g.ind[i]; j < g.ind[i+1]; j++) {
				if (i < g.endv[j]) {
					if (ehistory.containsKey(g.names[i] +Common.SEP + g.names[g.endv[j]])){
						vals.put(j, ehistory.get(g.names[i] +Common.SEP + g.names[g.endv[j]]));
					} else {
						vals.put(j, ehistory.get( g.names[g.endv[j]] + Common.SEP + g.names[i]));
					}
				}
			}
		}
		
		
		TimeGraph tg = new TimeGraph(g, vals,t);
		return tg;
		
	}
	
	
	
	public static TimeGraph readTGraphPems(String grfn, String tsfn) 
		throws IOException {
		BufferedReader brg = new BufferedReader(new FileReader(grfn));
		BufferedReader brt = new BufferedReader(new FileReader(tsfn));
		
		String line = brg.readLine();
		int n = Integer.parseInt(line.split(",")[0]);
		int m = Integer.parseInt(line.split(",")[1]);
	
		// create the graph
		String[] nodes = new String[n];
		HashSet<String> nds = new HashSet<String>();
		String[] edges = new String[m*2]; // edges
		HashMap<String,Double> edgedist = new HashMap<String, Double>(); 
		String[] sline;
		int cnt = 0;
		while((line = brg.readLine()) != null) {
			sline = line.split(",");
			if (sline[0].trim().equals("")) {
				System.err.print(line);
			}
			nds.add(sline[0].trim());
			nds.add(sline[1].trim());
			edges[2*cnt] = sline[0];
			edges[2*cnt+1] = sline[1];
			edgedist.put(sline[0] + Common.SEP + sline[1], Double.parseDouble(sline[2]));
			edgedist.put(sline[1] + Common.SEP + sline[0], Double.parseDouble(sline[2]));
			cnt++;
		}
		brg.close();
		
		cnt = 0;
		for(String node:nds) {nodes[cnt] = node;cnt++;}
		Graph g = new Graph(edges, nodes);
		// set the edge lengths
		for (int i = 0; i < g.getn(); i++) {
			for (int j = g.ind[i] ; j < g.ind[i+1]; j++) {
				g.we[j] = edgedist.get(g.names[i] + Common.SEP + g.names[g.endv(j)]);
			}
		}
		g = g.getLargestConnectedComponent();
		
		HashMap<String, Integer> nodespos = new HashMap<String, Integer>();
		for(int i=0; i < g.names.length; i++) 
			nodespos.put(g.names[i],i);
		
		// Now build the Time Graph
		int pos;
		line = brt.readLine();
		double[][] nodetimes = new double[g.getn()][Integer.parseInt(line)];
		while((line = brt.readLine()) != null) {
			sline = line.split(",");
			if (!nodespos.containsKey(sline[0])) continue;
			if (sline.length == 1) { 
				Arrays.fill(nodetimes[nodespos.get(sline[0])],-1);
			} else {
				pos = nodespos.get(sline[0]);
				assert (sline.length - 1 == nodetimes[pos].length);
				for (int i = 0 ; i < sline.length-1; i++) {
					nodetimes[pos][i] = Double.parseDouble(sline[i+1]);
				}
			}
		}
		
		// first impute nodes for which there is no information
		// every node that does not have reading should have only two bounding
		// nodes with readings along the same highway (use them to average reading)
		HashSet<Integer> comp = new HashSet<Integer>();
		HashSet<Integer> toprocess = new HashSet<Integer>();
		HashSet<Integer> nonempty = new HashSet<Integer>();
		int curr = -1;
		for (String name: nodespos.keySet()) {
			pos = nodespos.get(name);
			if(nodetimes[pos][0] == -1) {
				// find the connected component of no value nodes including pos
				// and the bounding nodes with values
				comp.clear();
				toprocess.clear(); toprocess.add(pos);
				nonempty.clear();
				while (!toprocess.isEmpty()) {
					curr = toprocess.iterator().next();
					comp.add(curr);
					toprocess.remove(curr);
					for (int i=g.ind[curr]; i < g.ind[curr+1]; i++) {
						// do not consider edges connecting Highways
						if (edgedist.get(g.names[curr] + Common.SEP + g.names[g.endv[i]]) < 0) 
							continue;
						int neigh = g.endv[i];
						if (nodetimes[neigh][0] == -1 && 
							!toprocess.contains(neigh) && !comp.contains(neigh)) {
							toprocess.add(neigh);
						} else if (nodetimes[neigh][0] != -1) {
							nonempty.add(neigh);
						} 
					}
				}
				assert(nonempty.size()<=2);
				// now impute the values in comp based on nonempty
				for(int i =0; i < nodetimes[0].length; i++) {
					double val = 0;
					for (int ne: nonempty) {
						val += nodetimes[ne][i];
					}
					val /= nonempty.size();
					for (int nd: comp) nodetimes[nd][i] = val; 
				}
			}
		}	
		// create time 
		TimeGraph tg = new TimeGraph(g, nodetimes);
		return tg;
	}
	
	
	public static TimeGraph readTGraphSigAlert(String fn) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fn));
		
		String line = br.readLine();
		int n = Integer.parseInt(line.split("\t")[0]);
		int m = Integer.parseInt(line.split("\t")[1]);
	
		// create the graph
		String[] nodes = new String[n];
		HashSet<String> nds = new HashSet<String>();
		String[] edges = new String[m*2]; // edges
		String[] edge_ev = new String[m];
		String[] sline;
		long s=Long.MAX_VALUE, e=0;
		long avgsamples = 0;; 
		int cnt = 0;
		while((line = br.readLine()) != null) {
			sline = line.split("\t");
			nds.add(sline[0]);
			nds.add(sline[1]);
			edges[2*cnt] = sline[0];
			edges[2*cnt+1] = sline[1];
			for(int i = 2; i < sline.length; i++) { 
				if(i==2) edge_ev[cnt] = sline[i];
				else edge_ev[cnt] += "\t" + sline[i];
				if(Long.parseLong(sline[i].split(":")[0]) < s) 
					s = Long.parseLong(sline[i].split(":")[0]);
				if(Long.parseLong(sline[i].split(":")[0]) > e) 
					e = Long.parseLong(sline[i].split(":")[0]);	
			}
			avgsamples += sline.length;
			cnt++;
		}
		avgsamples = (int)(avgsamples*1.0/cnt);
		
		cnt = 0;
		for(String node:nds) {nodes[cnt] = node;cnt++;}
		Graph g = new Graph(edges, nodes);
		//g = g.getLCC();
		
		// Now build the Time Graph
		int[][] vals = new int[(int)avgsamples][m]; 
		for (int j=0 ; j < m; j++) {
			int[] arr = Common.estNPoints(s,e,(int)avgsamples,edge_ev[j]);
			int eidx = g.getEdgeIndex(g.getNodeIndex(edges[2*j]),
									  g.getNodeIndex(edges[2*j + 1]));
			for (int i=0; i < avgsamples; i++) {
				vals[i][eidx] = arr[i];
			}
		}
		
		// create time 
		
		TimeGraph tg = new TimeGraph(g, vals);
		return tg;
	}
	
	public static TimeGraph readTGraphEvents(String fn, Time.t_res resolution,
			 double thresholdGT) throws IOException {
		return readTGraphEvents(fn, resolution, thresholdGT, null);
	}
	
	
	// reads in format node1 node2 time
	public static TimeGraph readTGraphEvents(String fn, Time.t_res resolution,
											 double thresholdGT, String remove_nodes) throws IOException {
		HashSet<String> filter = new HashSet<String>(); 
		if (null != remove_nodes || remove_nodes != "") {
			String[] fs = remove_nodes.split(" ");
			for(String s:fs) filter.add(s);
		}
		
		BufferedReader br = new BufferedReader(new FileReader(fn));
		
		String line = br.readLine();
		int n = Integer.parseInt(line.split(" ")[0]);
		int m = Integer.parseInt(line.split(" ")[1]);
	
		// create the graph
		String[] nodes = new String[n];
		HashSet<String> nds = new HashSet<String>();
		String[] edges = new String[m*2]; // edges
		String[] sline;
		long s=Long.MAX_VALUE, e=0;
		long avgsamples = 0, ts; 
		int cnt = 0;
		HashMap<String,TreeSet<Long>> evts = new HashMap<String, TreeSet<Long>>();
		while((line = br.readLine()) != null) {
			sline = line.split(" ");
			if (filter.contains(sline[0]) || filter.contains(sline[1])) 
				continue;
			nds.add(sline[0]);
			nds.add(sline[1]);
			String key = sline[0] + Common.SEP + sline[1];
			edges[2*cnt] = sline[0];
			edges[2*cnt+1] = sline[1];
			evts.put(key, new TreeSet<Long>());
			for(int i = 2; i < sline.length; i++) {
				ts = Long.parseLong(sline[i]);
				evts.get(key).add(ts);
				// collecting the stats
				s = Math.min(s, ts);
				e = Math.max(e, ts);	
			}
			avgsamples += evts.size() + 2;
			cnt++;
		}
		avgsamples = (int)(avgsamples*1.0/cnt);
		
		cnt = 0;
		for(String node:nds) {nodes[cnt] = node;cnt++;}
		
		//resizes edges and nodes based on filtered keep only non-null
		n = 0; while(null!=nodes[n]) n++;
		nodes = Arrays.copyOf(nodes, n);
		m = 0; while(null!=edges[m]) m++;
		edges = Arrays.copyOf(edges, m);
		
		Graph g = new Graph(edges, nodes);
		g = g.getLargestConnectedComponent();
		
		long[] pivots = Time.discretizeInterval(s, e, resolution);
		
		// Now build the Time Graph
		int[][] vals = new int[pivots.length-1][g.getm()];
		//Arrays.fill(vals, 0);
		for (int j=0 ; j < g.getm(); j++) {
			int pos = 0;
			for(Long l: evts.get(g.names[g.getOrigin(j)] + Common.SEP + g.names[g.endv[j]])) {
				while(pos < pivots.length && pivots[pos+1] < l) pos++;
				vals[pos][j]++;
			}
		}
		
		// create time 
		TimeGraph tg = new TimeGraph(g, vals);
		tg.pivots = pivots;
		tg.thresholdGTValue((int)thresholdGT);
		//System.err.print(tg.toStringTimeFirstK(500));
		return tg;
	}
	
	// LATEST GRAPH READERS EXPECTING HEADERS
	
	// Reads a graph file fng with HEADER	n	m
	// and format n1	n2	dist
	// And a time file fnt with HEADER	t 
	// and format n1	time	value
	public static NodeWeightedTimeGraph readNWGraph(String fng, String fnt) 
		throws IOException {
		Graph gr = IO.readGraphEdgeList(fng);
		gr.buildN2I();
		float[][] w = readTimeNodeWeights(gr,fnt);
		return new NodeWeightedTimeGraph(gr,w);
	}
	
	// And a time file fnt with HEADER	t 
	// and format n1	time	value
	private static float[][] readTimeNodeWeights(Graph gr, String fnt) 
		throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fnt));
		String line = br.readLine();
		if (line == null) {
			System.err.print("Empty node weights file");
			return null;
		}
		if (!line.split(Common.SEP)[0].equals("HEADER")) {
			System.err.print("No header in node weights file \nfirst row:\n");
			System.err.print(line + "\n");
			return null;
		}
		int ts = Integer.parseInt(line.split(Common.SEP)[1]);
		float[][] res = new float[ts][gr.getn()];
		while ((line = br.readLine()) != null) {
			res[Integer.parseInt(line.split(Common.SEP)[1])]
			   [gr.getNodeIndex(line.split(Common.SEP)[0])] =
				Float.parseFloat(line.split(Common.SEP)[2]);
		}
		return res;
	}

	// Reads a graph file fng with HEADER	n	m
	// and format n1	n2	dist
	// And a time file fnt with HEADER	t 
	// and format n1	n2	time	value
	public static WeightedTimeGraph readEWGraph(String fng, String fnt) 
		throws IOException {
		Graph gr = IO.readGraphEdgeList(fng);
		gr.buildN2I();
		float[][] w = readEdgeWeights(gr,fnt);
		return new WeightedTimeGraph(gr,w);
	}
	
	// And a time file fnt with HEADER	t 
	// and format n1	n2	time	value
	private static float[][] readEdgeWeights(Graph gr, String fnt) 
	throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(fnt));
		String line = br.readLine();
		if (line == null) {
			System.err.print("Empty edge weights file");
			return null;
		}
		if (!line.split(Common.SEP)[0].equals("HEADER")) {
			System.err.print("No header in edge weights file \nfirst row:\n");
			System.err.print(line + "\n");
			return null;
		}
		int ts = Integer.parseInt(line.split(Common.SEP)[1]);
		float[][] res = new float[ts][gr.getm()];
		while ((line = br.readLine()) != null) {
			int edgeidx = gr.getEdgeIndex(
					        gr.getNodeIndex(line.split(Common.SEP)[0]),
					        gr.getNodeIndex(line.split(Common.SEP)[1])
					      );
			
			res[Integer.parseInt(line.split(Common.SEP)[2])][edgeidx] =
				Float.parseFloat(line.split(Common.SEP)[3]);
			res[Integer.parseInt(line.split(Common.SEP)[2])][gr.getReverseEdgeIndex(edgeidx)] =
				Float.parseFloat(line.split(Common.SEP)[3]);
		}
		return res;
	}


	public static void writeScatterXYLabels(TreeMap<Double,Double> h, String X, String Y, String fn) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		bw.write(X + "\n");
		bw.write(Y + "\n");
		for (double i:h.keySet()) {
			bw.write(i + " " + h.get(i) + "\n");
		}	
		bw.close();
	}
	
	public static void writeHist(TreeMap<Double,Integer> h, String fn) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (double i:h.keySet()) {
			bw.write(i + " " + h.get(i) + "\n");
		}	
		bw.close();
	}
	
	public static void writeHistNormalize(TreeMap<Double,Integer> h, String fn) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		int cnt = 0;
		for (double i:h.keySet()) cnt += h.get(i);
		for (double i:h.keySet()) {
			bw.write(i + " " + h.get(i)*1.0/cnt + "\n");
		}	
		bw.close();
	}
	
	public static void writeValues(TreeMap<Double, Integer> t, String fn) 
	throws IOException {
		// TODO Auto-generated method stub
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (Double d: t.keySet()) 
			if (d  > 0.0)
				for(int i=0;i<t.get(d);i++)
					bw.write(d + "\n");
		bw.close();
	}
	
	public static void writeVector(double[] ds, String fn) 
	throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (int i=0; i< ds.length; i++) 
			bw.write(i + " " + ds[i] + "\n");
		bw.close();
	}
	
	public static void writeDist(ComparableLabeledValue[] tm, String fn) 
	throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (int i = 0 ; i < tm.length; i++) 
			bw.write(i + " " + tm[i].v + "\n");
		bw.close();
	}
	
	public static void writeStrings(ArrayList<String> b, String fn) 
	throws IOException {
		// TODO Auto-generated method stub
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (String s: b) bw.write(s + "\n");
		bw.close();	
	}
	
	public static void writeStrings(String[] b, String fn) 
	throws IOException {
		// TODO Auto-generated method stub
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (String s: b) bw.write(s + "\n");
		bw.close();	
	}
	
	public static void writeIntervals(HashSet<String> prunedUbAl, String fn) 
		throws IOException {
			int max=Integer.MIN_VALUE, min=Integer.MAX_VALUE;
			for (String s: prunedUbAl) {
				min = Math.min(min,Integer.parseInt(s.split("-")[0]));
				max = Math.max(max,Integer.parseInt(s.split("-")[1]));
			}
			BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
			for (String s: prunedUbAl) {
				int from = Integer.parseInt(s.split("-")[0]);
				int to = Integer.parseInt(s.split("-")[1]);
				bw.write( from + " " + (to-from - 1.0*(from-min)/(max-min)) + " " + 
						  (to-from) + " 0\n");
			}
			bw.close();	
	}
	
	public static void writeCurves(String[] x, String[] curve_names,
			double[][] y, String xlab, String ylab, String name) throws IOException {
		writeCurves(x, curve_names, y, xlab, ylab, name, false);
	}
	
	public static void writeCurves(String[] x, String[] curve_names,
			double[][] y, String xlab, String ylab, String name, boolean normalize) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(name));
		bw.write(xlab + "\n");
		bw.write(ylab + "\n");
		// names of the curves
		for (int i = 0; i < curve_names.length-1; i++) 
			bw.write(curve_names[i]  + "\t");
		bw.write(curve_names[curve_names.length-1]  + "\n");
		// values
		for (int i = 0 ; i < y.length; i++) {
			if(normalize) {
				double sum = 0;
				for (int j = 0 ; j < y[i].length; j++) sum+=y[i][j];
				bw.write(x[i]);
				for (int j = 0 ; j < y[i].length; j++) 
					bw.write("\t" + y[i][j]/sum);
				bw.write("\n");
			} else {
				bw.write(x[i]);
				for (int j = 0 ; j < y[i].length; j++) 
					bw.write("\t" + y[i][j]);
				bw.write("\n");
			}
		}
		bw.close();
	}
	
	public static void writeSingleCurve(String[] x, double[] y, String name) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(name));
		// values
		for (int i = 0 ; i < y.length; i++) {
			bw.write(x[i] + "\t" + y[i] + "\n");
		}
		bw.close();
	}
	
	public static void write2DScatter(TreeMap<String,Integer> h, String fn) throws IOException {
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for (String i:h.keySet()) {
			bw.write(i.split(Common.SEP)[0] + " " + i.split(Common.SEP)[1] + " " + h.get(i) + "\n");
		}	
		bw.close();
	}
	
	public static void writeMatrix(double[][] matrix, double norm, 
								   double threshold, String fn, int yupto) 
								   throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for(int sz=0; sz <= Math.min(matrix.length-1, yupto-1); sz++) {
			for (int j=0; j < matrix.length; j++) {
				bw.write(((Double.isInfinite(matrix[sz][j]) || 
						 (threshold >= matrix[sz][j]/norm))?threshold:matrix[sz][j]/norm) + " ");
			}
			bw.write("\n");
		}
		bw.close();
	}
	
	public static void writeMatrix(int[][] matrix, String sep,
									String fn) throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for(int t = 0; t < matrix.length; t++) {
			bw.write("" + matrix[t][0]);
			for (int j=1; j < matrix[t].length; j++) {
				bw.write(sep + matrix[t][j]);
			}
			bw.write("\n");
		}
		bw.close();
	}
	
	public static void writeMatrix(float[][] matrix, String sep,
			String fn) throws IOException{
		BufferedWriter bw = new BufferedWriter(new FileWriter(fn));
		for(int t = 0; t < matrix.length; t++) {
			bw.write("" + matrix[t][0]);
			for (int j=1; j < matrix[t].length; j++) {
				bw.write(sep + matrix[t][j]);
			}
			bw.write("\n");
		}
		bw.close();
	}	
	
	public static void writeILPInput(Graph g, String fn) throws IOException{
		Writer datFile = null;
    	datFile = new OutputStreamWriter(new FileOutputStream(fn), "UTF-8");
    	datFile.write("tuples = {\n");
    	// write edges one way only
    	for (int i=0; i < g.getn(); i++) {
    		for (int j = g.ind[i]; j< g.ind[i+1];j++){
    			if (i < g.endv[j]) {
    				datFile.write("  <" + i + " " + g.endv[j] + " " + g.we[j] + ">,\n");
    			}
    		}
    	}
    	datFile.write("};\n");
    	datFile.write("n=" + g.getn() + ";\n");
    	datFile.close();
	}
	
	public static void write(String s, String fn) throws IOException{
		Writer datFile = null;
    	datFile = new OutputStreamWriter(new FileOutputStream(fn), "UTF-8");
    	datFile.write(s);
    	datFile.close();
	}
	
	public static TimeGraph getEnronGraph(Time.t_res tres, int freq_gt) {
		TimeGraph tg = null;
		try {
			tg = IO.readTGraphEvents(
					Common.DATA_DIR + "enron/events",
				 tres, freq_gt, 
				 "pete.davis@enron.com no.address@enron.com enron.announcements@enron.com ");
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
		return tg;
	}
	
	public static TimeGraph getPeMSGraph(double perc_avg) {
		TimeGraph tg = null;
		double nz;
		try {
			tg = readTGraphPems(Common.DATA_DIR + "PeMS/d07_stations_2010_08_18.graph", 
			   Common.DATA_DIR + "PeMS/d07_text_station_5min_2011_04.txt.timeseries");
			nz = tg.scoreEdgesLTSpeed(perc_avg);
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
		System.err.print(tg.getDynamicsModel().toString() + "\n");
		return tg;
	}
	

	public static TimeGraph getTwitterGraph(String fn, double val) {
		TimeGraph tg = null;
		try {
			tg = readTGraphTwitter(fn);
			double d = tg.thresholdSparseGTValue(val);
			System.err.print("Retaining: " + d + "\n");
			
	//		System.err.print(tg.getDynamicsModel());
	//		tg.printStringTimeFirstK(0, 100, 1000);
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
		return tg;
	}
	
	public static void main(String[] argv) throws IOException, InterruptedException {	
		
		
		Graph gr = null;
		//gr = IO.readGraphEdgeList("/home/petko/data/Biology/sgadata_costanzo2009.udir.absepsilonscore.txt");
		
		gr = IO.readGraphEdgeList("/home/petko/data/seine/01_facebook/preprocessed/graph");
		HashSet<Integer> hs = gr.getBFSNodes(gr.getNodeIndex("5423"), 10000);
		BufferedWriter bw = new BufferedWriter(new FileWriter("/home/petko/data/seine/01_facebook/preprocessed/10000"));
		for (Integer i: hs) {
			bw.write(gr.names[i] + "\n");
		}
		bw.close();
		
		
//		TimeGraph tgEnron = getEnronGraph(t_res.D, 1);
//		float[][] pv = tgEnron.getEdgePvalues();
//		IO.writeTGraphQuadruples("/home/petko/data/temporal/enron/graph_pval_days", 
//									tgEnron, pv);
		
//		TimeGraph tgEnron = getEnronGraph(t_res.W, 1);
//		float[][] pv = tgEnron.getEdgePvalues();
//		IO.writeTGraphQuadruples("/home/petko/data/temporal/enron/graph_pval_weeks", 
//									tgEnron, pv);
//		System.exit(0);
		
		
		
//		String tfn = "/home/petko/test/times",
//			   efn = "/home/petko/test/edges",
//			   cfn = "/home/petko/test/ccsizes";
		String tfn = "/home/petko/data/temporal/MapQuest/weka/source/time_osm_decentr_zo.2.3",
		   efn = "/home/petko/data/temporal/MapQuest/weka/source/sortededges",
		   cfn = "/home/petko/data/temporal/MapQuest/weka/sourceccsizes";
		NodeWeightedTimeGraph nwtg = 
			readGraphNodeListEdgeListTimes(efn,tfn,",");
		System.err.print("created graph\n");
		//int[][] ccs = nwtg.getRootedConnectedComponents(0.1, 1.0);
		//writeMatrix(ccs,",",cfn);
		nwtg.printEvolutionOfPositiveComponents(0.1, 1.0, 0.8, 1, 
				"/home/petko/data/temporal/MapQuest/weka/ccedges.2.3", 
				"/home/petko/data/temporal/MapQuest/weka/ccnodes.2.3");
		
		System.err.print("done\n");
		System.exit(0);
		TimeGraph tg = null;
		
//		HashSet<String> remove = new HashSet<String>();
//		remove.add("GO:0008150"); remove.add("GO:0005575"); remove.add("GO:0003674");
//		LabeledGraph lg = readGraphEdgeListNodeLabeled(Common.GSEARCH_DATA_DIR + "/function_prediction/celegans/edges", 
//													   Common.GSEARCH_DATA_DIR + "/function_prediction/celegans/pin_nodes_proc.txt", 20 , remove);
//		
//		
//		// Test the reading and writing of graphs
//		Graph g = GraphGenerator.generateRandomWeighted(100, 1000, 10, 30);
//		writeGraphEdgeList(Common.GSEARCH_DATA_DIR + "test100", g);
//		Graph g1 = readGraphEdgeList(Common.GSEARCH_DATA_DIR + "test100");
//		
//		assert(g.getn() == g1.getn() && g.getm() == g1.getm());
//		for(int i=0; i < 20; i++) {
//			String v1 = g.names[Common.rand.nextInt(g.getn())];
//			int degree = g.ind[g.n2i.get(v1)+1] - g.ind[g.n2i.get(v1)];
//			if (degree == 0) continue;
//			String v2 = g.names[g.endv[
//			                           g.ind[g.n2i.get(v1)] + 
//			                           Common.rand.nextInt(degree-1)
//			                          ]
//			                   ];
//			if (!v1.equals(v2)) {
//				assert(g1.getEdgeIndex(g1.n2i.get(v1), g1.n2i.get(v2)) >= 0);
//			}
//		}
		
		
		tg = IO.getEnronGraph(t_res.D,0);
		//writeEdgeValuesSparse()
//		tg = IO.getEnronGraph( t_res.W,0);
//		
//		tg = getTwitterGraph("/home/petko/data/temporal/twitter/music/music.rt.graph.lcc.timegraph.final",
//									  0.0004);
		
		tg = getPeMSGraph(0.4);
		
		tg = readTGraphEvents(Common.DATA_DIR + "enron/events",t_res.D,0);
		int s = tg.getTimeAt(979891200);
		int e = tg.getTimeAt(987145200);
		
		s = 467; e = 468;
		
		tg.printStringTime(s,e);
		tg.aggregateByTime(s,e);
		System.err.print("" + tg.getScore() + "\tP:" + tg.getP() + "\tN:" + tg.getN() + "\n");
		BitSet edges = new BitSet(tg.getm());
		IntervalBounds.topDownLBFast(tg,edges);
		double d = tg.getScore(edges);
		System.err.print(d);
		
//		tg = readTGraphSigAlert("/home/petko/data/temporal/sigalert_la/preprocess/"+
//				"Greater_Los_Angeles.graph");
//		tg.thresholdFractionLessThan(0.5);
//		System.err.print(tg.toStringTimeFirstK(300));
//		
//		//Graph g = parseILPPCST("/home/petko/data/temporal/PCST_ILP_Instances/pcstp/K100.10.dat");
//		//g.toString();
//		int n = 400, m = 300, t = 100;
//		double Pn = 0.005, Pp = 0.05, Ps = 0.001; // settings
//		//Graph gbase = GraphGenerator.getTestGraphWithStarFurtherMerge();
//		//Graph gbase = GraphGenerator.generateScaleFree(n);
//		Graph gbase = GraphGenerator.generateRandom(n,(int)(1.2*n));
//		tg = GraphGenerator.generateTimeGraphLocalized(t, Pn, Pp, Ps, gbase);
//		System.err.print(tg.toStringTime());
//		Graph g = tg.aggregateByTime(0,tg.gett()-1);
//		for (int i = 0 ; i < g.getm(); i++) g.we[i] += tg.gett();
//		writeGraphMetis("/home/petko/Downloads/g10.13.60", g);
//		
//		// Runtime
//		Runtime run = Runtime.getRuntime() ;
//		Process pr = run.exec("/home/petko/bin/metis-4.0/pmetis /home/petko/Downloads/g10.13.60 2") ;
//		pr.waitFor();
//		
//		ArrayList<String> p = readPartitioningMetis("/home/petko/Downloads/g10.13.60.part.2");
//		
//		g = GraphGenerator.getTestGraphWithStarFurtherMerge();
//		writeHyperGraphHMetis("/home/petko/Downloads/hg", g, "11");
//		// Runtime
//		Runtime hrun = Runtime.getRuntime() ;
//		Process hpr = hrun.exec("/home/petko/bin/hmetis-1.5-linux/shmetis /home/petko/Downloads/hg 3 5") ;
//		hpr.waitFor();
//		
//		HashMap<Inprivate static void writeTGraphQuadruples(String string, TimeGraph tgEnron,
//		System.err.print(pp.keySet().toString());
		
	}


	


	
	
}
