import sys
import random
import math
import numpy as np

current_G_path = 'current_G.txt'

def Gnp_Random_Graph(n, p, seed=None):
    '''
    Return a random graph G{n,p}.
    
    Parameters
    ----------
    n : int
        The fixed number of nodes.
    p : float
        Probability for an edge of the (n)(n-1)/2 edges that can be formed.
    seed : int, optional
        Seed for random number generator (default=None).
    
    This is an O(n^2) algorithm. For sparse graphs (small p) see SpaseRandomGraphGen.
    '''    
    if not seed is None:
        random.seed(seed)

    G=[] # Initialize the graph with 0 edges
    for u in xrange(n):
        for v in xrange(u+1,n):
            if random.random() < p:
                G.append([u,v])
    return G


""" preferential attachment model
    para:
        m0: the number of nodes in the initial graph
        expected_connections: the expected edges for new added nodes
        t: the number of new added nodes
    return: a scale-free network generated by PAM
"""
def preferential_attachment_gen(init_graph, expected_connections, t):
    #----Initial graph with m0 nodes with degrees at least 1----#
    if init_graph == []:
        print "error: the original graph is null!"

    node_degrees = {}
    for [node_a, node_b] in init_graph:
        add_to_dict(node_degrees, node_a, 1)
        add_to_dict(node_degrees, node_b, 1)
    if len(node_degrees) < expected_connections:
        print "error: the expected connections for a new added node is too large!"  
    node_num = len(node_degrees)
    #-----------------------------------------------------------#
    #----the first ingredient:the growth element----#
    for i in xrange(1, t+1):
        node_vi = node_num + 1 #---add a new node vi---#
        degree_of_vi = 0
        #---the second ingredient:the preferential attachment element---#
        while degree_of_vi != expected_connections:
            list = []
            for j in xrange(1, node_num+1):
                if j in node_degrees:
                    for counts in xrange(0, node_degrees[j]):
                        list.append(j)
            #---connect vi to a random node vj with probability---#
            node_vj = random.choice(list)
            while [node_vi, node_vj] in init_graph:
               node_vj = random.choice(list)
            init_graph.append([node_vi, node_vj])
            degree_of_vi += 1
        node_num += 1
        add_to_dict(node_degrees, node_vi, degree_of_vi)
    return init_graph
#-------------------------------------------------------------------#



def Floyd(input_list, node, is_directed):
	if(node <= 0):
		print "node_num should be larger than 0\n"
		return [];
	graph_matrix = [[] for i in range(0,node)]
	for i in range(0,node):
		for j in range(0,node):
			graph_matrix[i].append(float("inf"))
	for i in range(0,node):
		graph_matrix[i][i] = 0

	for i in input_list:
		#i[3] for wreight
		if i[0] > node or i[1] > node or i[0] < 0 or i[1] < 0:
			print "Input_list should be corresponding to node_num. Out of range. \n"
			return [];
		graph_matrix[i[0] - 1][i[1] - 1] = 1
		if is_directed == 0:
			graph_matrix[i[1] - 1][i[0] - 1] = 1
	
	
	for i in range(0,node):
		for j in range(0,node):
			for k in range(0,node):
				tmp = graph_matrix[j][i] + graph_matrix[i][k];
				if tmp < graph_matrix[j][k]:
					graph_matrix[j][k] = tmp
	
#	print graph_matrix
	return graph_matrix


def AveragePathLength(input_list, node, is_directed):
	graph_matrix = Floyd(input_list, node, is_directed)
	if graph_matrix == []:
		return;
	total = 0
	valid_node = node
	invalid_list = []
	for i in range(0,node):
		if i in invalid_list:
			pass
		if is_directed == 0:
			count = 0
			for j in range(0,node):
				if graph_matrix[i][j] == float("inf"):
					count += 1
			if count == node - 1:
				invalid_list.append(i)
				valid_node -= 1
		else:
			count1 = 0
			count2 = 0
			for j in range(0,node):
				if graph_matrix[i][j] == float("inf"):
					count1 += 1
				if graph_matrix[j][i] == float("inf"):
					count2 += 1
			if count1 == node - 1 and count2 == node -1:
				invalid_list.append(i)
				valid_node -= 1

#	print invalid_list
	if is_directed == 0:
		for i in range(0,node):
			if i in invalid_list:
				pass
			else:
				for j in range(i+1,node):
					if j in invalid_list:
						pass
					else:
						tmp = graph_matrix[i][j]
						if tmp != float("inf"):
							total += tmp
		if valid_node > 1:
			apl = float(total)*2/(node*(node-1))
		else:
			apl = 0
	
	else:
		for i in range(0,node):
			if i in invalid_list:
				pass
			else:
				for j in range(0,node):
					if j in invalid_list:
						pass
					else:
						tmp = graph_matrix[i][j]
						if tmp == float("inf"):
							pass
						else:
							total += tmp
		if valid_node > 1:
			apl = float(total)/(node*(node-1))
		else:
			apl = 0
#	print apl
	return apl

def Diameter(input_list, node, is_directed):
	diameter = 0
	graph_matrix = Floyd(input_list, node, is_directed)
	if graph_matrix == []:
		return;
	if is_directed == 0:
		for i in range(0,node):
			for j in range(i+1,node):
				tmp = graph_matrix[i][j]
				if tmp > diameter and tmp != float("inf"):
					diameter = graph_matrix[i][j]
	else:
		for i in range(0,node):
			for j in range(0,node):
				tmp = graph_matrix[i][j]
				if tmp > diameter and tmp != float("inf"):
					diameter = tmp
#	print diameter
	return diameter

def LoadGraph(fpath):
	graph = []
	f = open(fpath)
	lines = f.readlines()
	for line in lines:
		graph.append([int(line.split(' ')[0]), int(line.split(' ')[1].split('\n')[0])])
	
	return graph


def BuildUp(graph, tnodeN):
	G = {}
	G['edges'] = []
	G['nodes'] = []
	nodeN = 0
	nodes = {}
	for edge in graph:
		if not edge[0] in nodes:
			nodes[edge[0]] = nodeN
			nodeN += 1
		if not edge[1] in nodes:
			nodes[edge[1]] = nodeN
			nodeN += 1
	
	for key in nodes.keys():
		G['nodes'].append(key)

	for i in range(len(nodes), tnodeN):
		G['nodes'].append(i)

	for edge in graph:
		G['edges'].append([nodes[edge[0]], nodes[edge[1]]])
	
	return G


def FormatOutput(G, nodeN):
	graph = BuildUp(G, nodeN)
	strline = ''

	for i in range(0, len(graph['nodes'])):
		strline += str(i)
		if i < len(graph['nodes']) - 1:
			strline += ','
	strline += '||'
	
	for i in range(0, len(graph['edges'])):
		strline += str(graph['edges'][i][0]) + ' ' + str(graph['edges'][i][1])
		if i < len(graph['edges']) - 1:
			strline += ','
	
	print strline

def WriteCurrentGraph(graph):
	f = open(current_G_path, 'w')
	for edge in graph:
		f.write("%d %d\n"%(int(edge[0]), int(edge[1])))
	f.close()

def GetNodeN(graph):
	nodes = {}
	nodeN = 0
	maxnode = 0
	for edge in graph:
		if not edge[0] in nodes:
			if int(edge[0]) > maxnode:
				maxnode = int(edge[0])
			nodes[edge[0]] = nodeN
			nodeN += 1
		if not edge[1] in nodes:
			if int(edge[1]) > maxnode:
				maxnode = int(edge[1])
			nodes[edge[1]] = nodeN
			nodeN += 1
	return maxnode

if __name__ == '__main__':
	graph = Gnp_Random_Graph(int(sys.argv[1]), float(sys.argv[2]))
	WriteCurrentGraph(graph)
	FormatOutput(graph, int(sys.argv[1]))
'''
	if sys.argv[1] == 'r':
		graph = Gnp_Random_Graph(int(sys.argv[2]), float(sys.argv[3]))
		WriteCurrentGraph(graph)
		FormatOutput(graph, int(sys.argv[2]))
		
	elif sys.argv[1] == 'p':
		init_G = LoadGraph(current_G_path) 
		graph = preferential_attachment_gen(init_G, int(sys.argv[2]), int(sys.argv[3]))
		WriteCurrentGraph(graph)
		FormatOutput(graph, int(sys.argv[2]))
	
	elif sys.argv[1] == 'a':
		graph = LoadGraph(current_G_path)
		nodeN = GetNodeN(graph)
		apl = AveragePathLength(graph, nodeN, 0)
		diameter = Diameter(graph, nodeN, 0)
		print "%f||%d"%(apl, diameter)
'''
