def computeNumberOfPathsOfLengthK(G):
    print 'Computing number of paths of length k for k=1 to number_of_nodes. This might take a while...'
    paths = set()
    for e in G.edges_iter():
        paths.add(e)
    result = {}
    result[1] = G.number_of_edges()
    newPaths = set()
    length = 2
    while len(paths) > 0:
        for path in paths:
            for neighb in nx.all_neighbors(G, path[0]):
                if neighb not in path:
                    if neighb < path[-1]:
                        newPaths.add((neighb,)+path)
                    else:
                        newPaths.add( ((neighb,)+path)[::-1] )
            for neighb in nx.all_neighbors(G, path[-1]):
                if neighb not in path:
                    if neighb < path[0]:
                        newPaths.add( (path + (neighb,))[::-1] )
                    else:
                        newPaths.add(path + (neighb,))
                    
        result[length] = len(newPaths)
        length += 1
        paths = newPaths
        newPaths = set()
    return result

def get_graph_as_bow (g, h):
    '''
    Get subgraph2vec sentences from the goven graph
    :param g: networkx graph
    :param h: WL kernel height
    :return: sentence of the format <target> <context1> <context2> ...
    '''
    for n,d in g.nodes_iter(data=True):
        for i in xrange(0, h+1):
            center = d['relabel'][i]
            neis_labels_prev_deg = []
            neis_labels_next_deg = []

            if -1 != i-1:
                neis_labels_prev_deg = [g.node[nei]['relabel'][i-1] for nei in nx.all_neighbors(g, n)] + [d['relabel'][i-1]]
            NeisLabelsSameDeg = [g.node[nei]['relabel'][i] for nei in nx.all_neighbors(g,n)]
            if not i+1 > h:
                neis_labels_next_deg = [g.node[nei]['relabel'][i+1] for nei in nx.all_neighbors(g,n)] + [d['relabel'][i+1]]


            nei_list = NeisLabelsSameDeg + neis_labels_prev_deg + neis_labels_next_deg
            try:
                nei_list.append(d['relabel'][i-1]) #prev degree subgraph from the current node
            except:
                pass
            try:
                nei_list.append(d['relabel'][i+1]) #next degree subgraph from the current node
            except:
                pass

            nei_list = ' '.join (nei_list)

            sentence = center + ' ' + nei_list
            yield sentence

	def set_graphs(self):
		self.original_graph = nx.Graph()
		dataset = open(self.dataset)
		for line in dataset.readlines():
			line = line.strip()
			col = line.split(';')
			iid = "p%s" %(int(col[0]))
			self.original_graph.add_node(iid, {'bipartite': 0})
			pid = int(col[1])
 			self.original_graph.add_node(pid, {'bipartite': 1})
			self.original_graph.add_edge(iid, pid)
		
		dataset.close()

		nodes = set(n for n,d in self.original_graph.nodes(data=True) if d['bipartite'] == 1)
		
		self.graph_training = nx.Graph()
		for node in nodes:
			for intermediate_node in list(nx.all_neighbors(self.original_graph, node)):
				for second_node in list(set(nx.all_neighbors(self.original_graph, intermediate_node)) - set([node])):
					self.graph_training.add_edge(node, second_node)		
		
		self.graph_test = self.graph_training.copy() if self.task == "missing_link_prediction" else self.get_future_link_graph()
		
		edges = set()
		
		if (self.task == "missing_link_prediction") and (self.sample_dataset != None):
			for line in [line for line in self.sample_dataset if line[2] == 1]:
				node_1, node_2 = int(line[0]), int(line[1])
				try:
					self.graph_training.remove_edge(node_1, node_2)
				except:
					print node_1, node_2
					pass

def sort_weight_by_both(G_hu, G_origin):
    vm_active_weight_hu = {}
    vm_active_weight_origin = {}
    for vm in G_hu.nodes():
        weight = 0
        for edge in nx.all_neighbors(G_hu, vm):
            weight += G_hu[vm][edge]['weight']
        vm_active_weight_hu[int(vm)] = weight
        weight = 0
        vm = int(vm)
        for edge in nx.all_neighbors(G_origin, vm):
            weight += G_origin[vm][edge]['weight']
        vm_active_weight_origin[vm] = weight
        
    
    #nodes_weight_hu = sorted(vm_active_weight_hu.iteritems(), key=lambda vm_active_weight_hu:vm_active_weight_hu[0], reverse=False)
    nodes_weight_origin = sorted(vm_active_weight_origin.iteritems(), key=lambda vm_active_weight_origin:vm_active_weight_origin[1], reverse=True)
    
    #print nodes_weight_hu
    
    nodes_weight = {}
    for node in nodes_weight_origin:
        if node[1] == 0:
            weight = 0
        else:
            #print node[0]
            weight = vm_active_weight_hu[node[0]] / node[1]
            #print vm_active_weight_hu[node[0]], node[1]
        nodes_weight[node[0]] = weight
    
    nodes = sorted(nodes_weight.iteritems(), key=lambda nodes_weight:nodes_weight[1], reverse=True)
    print nodes

    return nodes

def cluster(G, E, x, y, j, WI):
	partition = []

	while len(G.nodes()) > 0:
		vertices = set(G.nodes()) # G.nodes()

		currDegs = G.degree(G.nodes())
		root = max(currDegs.iterkeys(), key=(lambda key: currDegs[key]))
		vertices.remove(root)

		V = { 0: [ root ] }
		El = { i: {} for i in E.keys() } # E_i[l]
		expanding = True
		l = 1
		while expanding and len(vertices) > 0:

			V[l] = set() # []
			for i in El.keys():
				El[i][l] = set() # []

			# find next layer of nodes
			for v in V[l-1]:
				for u in nx.all_neighbors(G, v):
					if u in vertices:
						V[l].add(u)
						vertices.remove(u)

			# find edges from V[l] to V[l] U v[l-1]
			for v in V[l]:
				for u in nx.all_neighbors(G, v):
					if u in V[l] or u in V[l-1]:
						# add edge to E_i[l]
						i = get_index_for_weight(G[u][v][0]['weight'], y, WI)
						El[i][l].add((u,v))

			# check expansion
			expanding = False
			for i in El.keys():
				if i > j: # ensure i <= j
					continue
				# index here by l (l+1 in paper)
				new_len = len(El[i][l])
				# find the length of E_i[1] U ... U E_i[l-1]
				curr_len = len([ e for ell in xrange(1,l) for e in El[i][ell] ])

				# if for any i, new_len > (1/x) * curr_len,
				# then we're still expanding
				if new_len > (1.0 / x) * curr_len:
					expanding = True
					break
			if expanding:
				l += 1

		# create cluster
		cluster_nodes = tuple([ e for ell in xrange(l) for e in V[ell] ])

		G.remove_nodes_from(cluster_nodes)
		partition.append(cluster_nodes)

	return partition

	def get_sample(self):
		"""
		Extracts the whole sample from the graph representing the original dataset. 
		"""
		Graph = nx.Graph()
		dataset = open(self.dataset)
		for line in dataset.readlines():
			line = line.strip()
			col = line.split(';')
			iid = int(col[0])
			Graph.add_node(iid, {'bipartite': 0})
			pid = "p%s" %(int(col[1]))
			Graph.add_node(pid, {'bipartite': 1})
			Graph.add_edge(iid, pid)
		
		dataset.close()
		
		self.original_graph = Graph.copy()

		nodes = set(n for n,d in Graph.nodes(data=True) if d['bipartite'] == 1)
		
		Gt = nx.Graph()
		for node in nodes:
			for intermediate_node in list(nx.all_neighbors(Graph, node)):
				for second_node in list(nx.all_neighbors(Graph, intermediate_node)):
					Gt.add_edge(node, second_node)
		
		self.graph_training = Gt.copy()
		self.graph_test = Gt.copy() if self.task == 1 else self.get_future_links_graph()
		
		self.get_positive_examples()
		self.get_negative_examples()

 def get_graph_from_period(graph, t0,t0_):
     print "Starting generating graph from period", datetime.today()
     papers = list([n,d] for n,d in graph.nodes(data=True) if d['node_type'] == 'E' and d['time'] >= t0 and d['time'] <= t0_)
     print "Total Papers: ",  len(papers),  datetime.today()
     new_graph = networkx.Graph()
     new_graph.add_nodes_from(papers)
     autores = list([n,d] for n,d in graph.nodes(data=True) if d['node_type'] == 'N')
     new_graph.add_nodes_from(autores)
             
     element = 0
     for paper in papers:
         element = element+1
         FormatingDataSets.printProgressofEvents(element, len(papers), "Adding paper to new graph: ")
         
         authors = networkx.all_neighbors(graph, paper[0])
         for author in authors:
             new_graph.add_edge(paper[0], author)
     
     
     element = 0
     qtyautors= len(autores)
     for autor in autores:
         element = element+1
         FormatingDataSets.printProgressofEvents(element,qtyautors, "Cleaning authors from new graph: ")
         if len(list(networkx.all_neighbors(new_graph,autor[0]))) == 0:
             new_graph.remove_node(autor[0])
       
         
     
     
     print "Generating graph from period finished", datetime.today()
     
     return new_graph    

def bn(G, d1, d2):
    bns = set()
    for n in d1:
        for ne1 in nx.all_neighbors(G, n):
            if ne1 in d2:
                bns.add(n)
                bns.add(ne1)
            for ne2 in nx.all_neighbors(G, ne1):
                if ne2 in d2:
                    bns.add(ne1)
    return bns

def edge_clustering(G):
    clusteringcoeffs = {}
    for s,t in G.edges():
        c = 0
        ns = set(nx.all_neighbors(G,s))
        nt = set(nx.all_neighbors(G,t))
        commons = ns.intersection(nt)
        ds = G.degree(s)
        dt = G.degree(t)
        c = (len(commons)+1)/float(min([ds,dt]))
        clusteringcoeffs[(s,t)] = c
    return clusteringcoeffs

    def start(self, G):
        (parity, odds) = self.checkGraph(G)

        if parity != self.HALF and parity != self.FULL:
            return

        H = G.copy()

        euler_path = []
        start_node = None

        if parity == self.HALF:
            start_node = odds[0]
        elif parity == self.FULL:
            start_node = H.nodes()[0]

        euler_path.append(start_node)

        neighbors = networkx.all_neighbors(H, start_node)
        last_node = start_node
        i = 1000

        while H.number_of_edges() > 0 and i > 0:
            bridges = self.find_bridges(H)
            chosenNode = None
            neighbors = networkx.all_neighbors(H, last_node)
            wasNonBridge = False

            for node in neighbors:
                isBridge = self.isBridge(last_node, node, bridges)
                if isBridge is False:
                    chosenNode = node
                    wasNonBridge = True
                    break

            if wasNonBridge is False:
                neighbors = networkx.all_neighbors(H, last_node)
                first = None
                for node in neighbors:
                    first = node
                    break
                chosenNode = first

            euler_path.append(chosenNode)
            H.remove_edge(last_node, chosenNode)

            if H.degree(last_node) == 0:
                H.remove_node(last_node)

            last_node = chosenNode
            i -= 1
        return euler_path

	def __edge_intersection_test(self, new_edge, join):
		a, b = new_edge
		for edge in self.graph.edges_iter():
			if util.segment_intersection(edge, new_edge):
				if join and (edge[0] not in nx.all_neighbors(self.graph, a)) and (edge[1] not in nx.all_neighbors(self.graph, a)):
					proj = util.project_on_line(edge, b)
					c, d = edge
					self.graph.remove_edge(c, d)
					self.graph.add_edge(c, proj)
					self.graph.add_edge(proj, d)
					self.graph.add_edge(a, proj)
				return False
		return True

def neighbor_count_comorbid(network, alteration_type, icd_gene_clinical, cancer_info,
                            comorbid_only = False, comorb_perm = False, weighted=False):
    tumor_data_list = alteration_type.keys()
    list2 = set()
    for icd in icd_gene_clinical:
        for cancer in tumor_data_list:
            rr = [icd_gene_clinical[icd]['cancer_assoc'][cancer_icd] 
                  for cancer_icd in cancer_info 
                  if cancer in cancer_info[cancer_icd]['TCGA']]
            if len(rr)>0 and rr[0] > 1:
                list2 |= set([cancer])
    cancers = list2

    mend_disease = mendelian_code.get_mendelian_diseases(icd_gene_clinical)
    #neighbor_count_mat = scipy.zeros([len(mend_disease), len(cancers)])
    all_mend_gn = mendelian_code.get_mendelian_genes(icd_gene_clinical)
    #gn_count_mat = scipy.zeros([len(all_mend_gn), len(cancers)])

    disease_score = pd.DataFrame(scipy.zeros([len(mend_disease), len(cancers)]), index = mend_disease, columns = cancers)
    gene_score = pd.DataFrame(scipy.zeros([len(all_mend_gn), len(cancers)]), index = all_mend_gn, columns = cancers)

    gene_connection = [['']*len(cancers) for i in range(len(all_mend_gn))]
    v = zip(*tuple([(c, canc) for canc in cancers for c in cancer_info if canc in cancer_info[c]['TCGA'] ]))
    canc_tab = dict(zip(v[1],v[0]))
    BIG_COUNT = 0
    i = 0
    for (m, md) in enumerate(mend_disease):
        mend_gn = icd_gene_clinical[md]['gene_omim'].keys()
        md_score = [0]*len(cancers)
        if len(mend_gn)==0:  
            continue
        canc_gn = set()
        for (c, canc) in enumerate(cancers):
            if not canc in canc_tab: continue
            if comorbid_only and (not canc in canc_tab or icd_gene_clinical[md]['cancer_assoc'][canc_tab[canc]] < 1): continue
            i += 1
            canc_gn |= alteration_type[canc][1]
        #pdb.set_trace()            
        md_subgr = networkx.subgraph(network, set(mend_gn) | set(canc_gn))
        for gn in mend_gn:
            if gn in md_subgr:
                if not weighted:
                    gene_result = [neighbor for neighbor in networkx.all_neighbors(md_subgr,gn) 
                                    if neighbor in canc_gn]
                    BIG_COUNT += len(gene_result)
                else:
                    BIG_COUNT += sum([md_subgr[gn][neighbor]['weight']
                                      for neighbor in networkx.all_neighbors(md_subgr,gn)
                                      if neighbor in canc_gn])
    #print 'tot pair: ' + str(i) + ' tot count: ' + str(BIG_COUNT)
    return BIG_COUNT

def makeMobile( T, root, labels = 0, color = True ):
	'''

	makeMobile( T, root, labels )
	
	In: T is a tree with 'root' as root.
		labels is an integer (default 0).
		color is a boolean (default True).

	Out: T has been changed into a labeled mobile
		with root as root and the labels are...
			... all 0 if labels == 0.
			... selected deterministically if labels == 1.
			... selected randomly if labels == 2.
		If color == True, then T has been colored by treeToMobile.colorMobile.
		
	'''

	if color:

		# Initialise
		Square = dict(zip( T.nodes(), [ 'square' ] * len(T) ))
		Black = dict(zip( T.nodes(), [ 'black' ] * len(T) ))
		nx.set_node_attributes( T, 'shape', Square )
		nx.set_node_attributes( T, 'color', Black )

		# Make the root special.
		T.node[root][ 'color' ] = 'red'
		T.node[root][ 'shape' ] = 'circle'

		colorMobile( T, root )


	# Initialise all labels to zero.
	Zero = dict(zip( T.nodes(), [0] * len(T) ))
	
	nx.set_node_attributes( T, 'label', Zero )


	if labels == 1:

		for v in nx.all_neighbors( T, root ):

			labelMobileDet( T, v, root )

	elif labels == 2:

		for v in nx.all_neighbors( T, root ):

			labelMobileRand( T, v, root )

  def __is_2_clun(self, nodes_pair):
    graph = self.graph
    for node_self in nodes_pair:
      # NOTE: 2clunにのみ対応. 2pathのみ検索
      in_2_path_node_set = set()
      in_2_path_node_set.update(set(nx.all_neighbors(graph, node_self)))
      for neighbor in nx.all_neighbors(graph, node_self):
        in_2_path_node_set.update(set(nx.all_neighbors(graph, neighbor)))

      for node_target in nodes_pair:
        if node_target not in in_2_path_node_set and node_target != node_self:
          return False

    return True

def colorMobile( M, node ):
	'''

	colorMobile( M, node )

	In: M is a tree and node is a vertex in M.
		Either M.node[node][ 'shape' ] == 'circle'
		or M.node[node][ 'shape' ] == 'point'

	Out: The 'shape' attributes of all descendants of node
		have been altered, such that every second generation
		has the same 'shape' as node and the other generations
		have the "opposite" 'shape'.

		Ironically, the 'color' attribute has not been changed.

	'''

	if M.node[node][ 'shape' ] == 'point':

		shape = 'circle'

	else:

		shape = 'point'


	for v in nx.all_neighbors( M, node ):

		# If we have not already, we color v and all its descendants.
		if not M.node[v][ 'shape' ] == shape:

			M.node[v][ 'shape' ] = shape

			colorMobile( M, v )

  def search_motifs_with_n(self, n):
    graph = self.graph

    all_nodes = nx.nodes(graph)
    motif_counter = defaultdict(int)
    # 全組み合わせ探索
    for nodes_pair in list(itertools.combinations(all_nodes, n)):
      degrees_in_pair = []
      for node_self in nodes_pair:
        degree_in_pair = 0
        for node_target in nodes_pair:
          if node_self == node_target:
            continue
          if node_target in nx.all_neighbors(graph, node_self):
            degree_in_pair += 1
        degrees_in_pair.append(degree_in_pair)
     
      # 孤立ノードがあれば飛ばす
      if 0 in degrees_in_pair:
        continue
      # エッジが足りてなければ飛ばす
      if sum(degrees_in_pair) / 2 < n -1:
        continue
      # NOTE: 飛ばしきれてない. 本当は繋がってる判定が必要

      score = sum([v * v for v in degrees_in_pair])
      motif_counter[score] += 1
    return motif_counter

def walk(G, start):
    global step, maxSteps, degree_dict, path;
    
    #print type(nx.all_neighbors(G, start)) ; 

    node_dict = {} ;
    for node in nx.all_neighbors(G, start):
        #degree = str(G.degree(node)) ;
        node_dict[str(node)] = 1 ;

    step = step + 1 ;
    #if( step >= maxSteps or start == end_node ): return ;
    if( step >= maxSteps ):
        provenance_dict[",".join(path)] = 1 ;
        return ;

    stop_walk_pro = np.random.random_sample() ;
    if( stop_walk_pro <= 0.1 ): 
        walk(G, start) ; # it has the 10% rate to stop 
    else: 
        node = random.choice(node_dict.keys()) ;    
        #node = select_random(node_dict, 1)[0] ;
        path.append(node) ;
        #print "add edge %s %s" % (start, node) ;
        walk(G, node) ; 

def show_connections(G,pos,neg):
	for x in pos:
		try:
			tmp = nx.all_neighbors(G,x[0])
                        for y in tmp:
				print y

		except:
			print "Not Found"
	for y in neg:
		try:
			tmp = nx.all_neighbors(G,x[0])
                        for y in tmp:
				print y
		except:
			print "Not Found"

	def give_output_list(self, game):
		""" This returns a list of the selected nodes. The twin attack player
		finds the highest degree nodes, and for each, it selects two
		neighbors of that node and"""

		nodes = nx.nodes(game.network)

		nodes.sort(key=lambda x : nx.degree(game.network, x), reverse=True)

		selections = set()

		for node in nodes:

			adjacents = list(nx.all_neighbors(game.network, node))

			for adj_node in adjacents[:2]:

				selections.add(adj_node)
				if len(selections) == game.num_seeds:
					break

			if len(selections) == game.num_seeds:
				break

		assert len(selections) == game.num_seeds
		return list(selections)

def ramsey_R2(graph):
    r"""Approximately computes the Ramsey number `R(2;s,t)` for graph.

    Parameters
    ----------
    graph : NetworkX graph
        Undirected graph

    Returns
    -------
    max_pair : (set, set) tuple
        Maximum clique, Maximum independent set.
    """
    if not graph:
        return (set([]), set([]))

    node = next(graph.nodes_iter())
    nbrs = nx.all_neighbors(graph, node)
    nnbrs = nx.non_neighbors(graph, node)
    c_1, i_1 = ramsey_R2(graph.subgraph(nbrs))
    c_2, i_2 = ramsey_R2(graph.subgraph(nnbrs))

    c_1.add(node)
    i_2.add(node)
    return (max([c_1, c_2]), max([i_1, i_2]))