from networkit import *
from networkit.dynamic import *
from networkit.centrality import *
import operator
from ..support import MissingDependencyError
try:
	import pandas as pd
except ImportError:
	have_pandas = False
else:
	have_pandas = True
import random

def removeAndAddEdges(G, nEdges, tabu=None):
	if nEdges > G.numberOfEdges() - tabu.numberOfEdges():
		raise Error("G does not have enough edges")

	# select random edges for removal
	removed = set()
	while len(removed) < nEdges:
		(u, v) = G.randomEdge()
		if not tabu.hasEdge(u, v) and not ((u,v) in removed or (v,u) in removed):	# exclude all edges in the tabu graph
			removed.add((u, v))
	print (removed)
	# build event streams
	removeStream = []
	for (u, v) in removed:
		removeStream.append(GraphEvent(GraphEvent.EDGE_REMOVAL, u, v, 0))
	addStream = []
	for (u, v) in removed:
		addStream.append(GraphEvent(GraphEvent.EDGE_ADDITION, u, v, 1.0))

	return (removeStream, addStream)

def extractLargestComponent(G):
	"""
	Extract the subgraph of the largest connected component.

	Parameters
	----------
	G : Graph
		Input graph.
	Returns
	-------
	Graph
		Subgraph of largest component, preserving node ids of orignal graph.
	"""

	cc = properties.ConnectedComponents(G)
	cc.run()
	cSizes = cc.getComponentSizes()
	(largestCompo, size) = max(cSizes.items(), key=operator.itemgetter(1))
	compoNodes = [v for v in G.nodes() if cc.componentOfNode(v) is largestCompo]
	C = graph.Subgraph().fromNodes(G, compoNodes)
	return C


def setRandomWeights(G, mu, sigma):
	"""
	Add random weights, normal distribution with mean mu and standard deviation sigma
	"""
	for (u, v) in G.edges():
		w = random.normalvariate(mu, sigma)
		G.setWeight(u, v, w)
	return G



def test(G, T, nEdges, batchSize, epsilon, delta, size):
	if not have_pandas:
		raise MissingDependencyError("pandas")
	# find a set of nEdges to remove from G
	(removeStream, addStream) = removeAndAddEdges(G, nEdges, tabu=T)
	# remove the edges from G
	updater = dynamic.GraphUpdater(G)
	updater.update(removeStream)
	# run the algorithms on the inital graph
	apprBc = ApproxBetweenness(G, epsilon, delta)
	print("Running approx bc")
	apprBc.run()
	dynApprBc = DynApproxBetweenness(G, epsilon, delta, False)
	print("Running dyn approx bc with predecessors")
	dynApprBc.run()
	# apply the batches
	nExperiments = nEdges // batchSize
	timesApprBc = []
	timesDynApprBc = []
	for i in range(nExperiments):
		batch = addStream[i*batchSize : (i+1)*batchSize]
		# add the edges of batch to the graph
		updater.update(batch)
		# update the betweenness with the static approximated algorithm
		t = stopwatch.Timer()
		apprBc.run()
		x = t.stop()
		timesApprBc.append(x)
		print("ApprBC")
		print(x)
		# update the betweenness with the dynamic approximated algorithm
		t = stopwatch.Timer()
		dynApprBc.update(batch)
		y = t.stop()
		timesDynApprBc.append(y)
		print("Speedup DynApprBC (with preds)")
		print(x/y)

	c = pd.Series(timesApprBc)
	d = pd.Series(timesDynApprBc)
	df1 = pd.DataFrame({"Static approx bc" : c, "Dynamic approx bc" : d})
	return df1


if __name__ == "__main__":
	setNumberOfThreads(1)
	graph_name = "road_usa.metis.graph"
	#G = readGraph("/algoDaten/staudt/Graphs/Collections/DynBC/email-Enron.edgelist-t0.graph", Format.EdgeListTabZero)
	G = graphio.METISGraphReader().read("/algoDaten/staudt/Graphs/Collections/DynBC/"+graph_name)
	size = G.numberOfNodes()
	print("Number of nodes: "+str(size))
	G = extractLargestComponent(G)
	print("Took largest connected component of the graph.")
	T = graph.SpanningForest(G).generate()
	print("Computed spanning forest.")

	for i in range(11):
		batchSize = 2**i
		nEdges = batchSize * 10
		epsilon = 0.2
		delta = 0.1
		df1 = test(G, T, nEdges, batchSize, epsilon, delta, size)
		df1.to_csv("results/times_"+graph_name+"_batch_"+str(batchSize)+"NO_PREDS_epsilon="+str(epsilon)+".csv")