def calc_euler_tour(g, start, end):
    '''Calculates an Euler tour over the graph g from vertex start to vertex end.
    Assumes start and end are odd-degree vertices and that there are no other odd-degree
    vertices.'''
    even_g = nx.subgraph(g, g.nodes())
    if end in even_g.neighbors(start):
        # If start and end are neighbors, remove the edge
        even_g.remove_edge(start, end)
        comps = list(nx.connected_components(even_g))
        # If the graph did not split, just find the euler circuit
        if len(comps) == 1:
            trail = list(nx.eulerian_circuit(even_g, start))
            trail.append((start, end))
        elif len(comps) == 2:
            subg1 = nx.subgraph(even_g, comps[0])
            subg2 = nx.subgraph(even_g, comps[1])
            start_subg, end_subg = (subg1, subg2) if start in subg1.nodes() else (subg2, subg1)
            trail = list(nx.eulerian_circuit(start_subg, start)) + [(start, end)] + list(nx.eulerian_circuit(end_subg, end))
        else:
            raise Exception('Unknown edge case with connected components of size {0}:\n{1}'.format(len(comps), comps))
    else:
        # If they are not neighbors, we add an imaginary edge and calculate the euler circuit
        even_g.add_edge(start, end)
        circ = list(nx.eulerian_circuit(even_g, start))
        try:
            trail_start = circ.index((start, end))
        except:
            trail_start = circ.index((end, start))
        trail = circ[trail_start+1:] + circ[:trail_start]
    return trail

def km_random(g,k=5,m=3,start=None):
    """ k nodes of breath first sequence; m add and del number."""
    if start==None:
        start=g.nodes().pop()
    bfList=list(nx.bfs_edges(g,start))
    bfList.reverse()
    bfList.append((start,start))
    tempk=[]
    try:
        while bfList:
            for each in range(k):
                tempk.append(bfList.pop()[1])
            
            tg=nx.subgraph(g,tempk)
            e=del_edge(tg,m)
            g.remove_edges_from(e)

            tg=nx.subgraph(g,tempk)
            e=add_edge(tg,m)
            g.add_edges_from(e)

            tempk=[]

    except IndexError:
        print "pop finishing"

def match_story_by_sen_edge(Gs, stories, target, tau):
    existing = copy.deepcopy(stories['keywords_set'])
    match_target = copy.deepcopy(target['keywords_set'])
    node_cos = match_story(existing, match_target, 0.3)

    subgs1 = []
    for sto in match_target:
        subgs1.append(nx.subgraph(Gs, sto))
    subgs0 = []
    for sto in existing:
        subgs0.append(nx.subgraph(Gs, sto))

    matched = []
    for i in range(len(subgs1)):
        matchingGraph = subgs1[i]
        dis = []
        for cand in subgs0:
            val = compute_distance(matchingGraph, cand)
            dis.append(val)
        total = np.multiply(dis, node_cos[i])
        match_score = np.max(total)

        if match_score < tau:
            stories['keywords_set'].append(target['keywords_set'][i])
            stories['doc_set'].append(target['doc_set'][i])
            continue

        print match_score
        match_ind = np.argmax(total)
        print  match_ind, stories['doc_set'][match_ind], target['doc_set'][i]
# 		match_text = existing[match_ind]
        stories['keywords_set'][match_ind].extend(match_target[i])
        u = stories['doc_set'][match_ind].union(target['doc_set'][i])
        stories['doc_set'][match_ind] = u

 def test_subgraph_of_subgraph(self):
     SGv = nx.subgraph(self.G, range(3, 7))
     SDGv = nx.subgraph(self.DG, range(3, 7))
     SMGv = nx.subgraph(self.MG, range(3, 7))
     SMDGv = nx.subgraph(self.MDG, range(3, 7))
     for G in self.graphs + [SGv, SDGv, SMGv, SMDGv]:
         SG = nx.induced_subgraph(G, [4, 5, 6])
         assert_equal(list(SG), [4, 5, 6])
         SSG = SG.subgraph([6, 7])
         assert_equal(list(SSG), [6])
         # subgraph-subgraph chain is short-cut in base class method
         assert_is(SSG._graph, G)

 def test_subgraph(self):
     assert_equal(self.G.subgraph([0, 1, 2, 4]).adj,
                  nx.subgraph(self.G, [0, 1, 2, 4]).adj)
     assert_equal(self.DG.subgraph([0, 1, 2, 4]).adj,
                  nx.subgraph(self.DG, [0, 1, 2, 4]).adj)
     assert_equal(self.G.subgraph([0, 1, 2, 4]).adj,
                  nx.induced_subgraph(self.G, [0, 1, 2, 4]).adj)
     assert_equal(self.DG.subgraph([0, 1, 2, 4]).adj,
                  nx.induced_subgraph(self.DG, [0, 1, 2, 4]).adj)
     # subgraph-subgraph chain is allowed in function interface
     H = nx.induced_subgraph(self.G.subgraph([0, 1, 2, 4]), [0, 1, 4])
     assert_is_not(H._graph, self.G)
     assert_equal(H.adj, self.G.subgraph([0, 1, 4]).adj)

def filterGraphByRecipeID(G, Grecipes, Gingredients, recipeNodes):
	recipe_to_remove = [ n for n in Grecipes.nodes() if n not in recipeNodes]	
	searchGrecipes = nx.subgraph(Grecipes, recipeNodes)
	searchGrecipes.remove_nodes_from(recipe_to_remove)

	ingrNodes = list(set([b for n in searchGrecipes.nodes() for b in G.neighbors(n)]))
	ingr_to_remove = [ n for n in Gingredients.nodes() if n not in ingrNodes]
	searchGingredients = Gingredients

	searchG = nx.subgraph(G, recipeNodes + ingrNodes)
	searchG.remove_nodes_from(recipe_to_remove)
	searchG.remove_nodes_from(ingr_to_remove)

	return (searchG, searchGrecipes, searchGingredients)

 def plot_induced_subgraphs(self):
     plt.figure(1)
     partition = self.find_partition()[1]
     communities = [partition[v] for v in partition]
     newGraph=self.G
     for community in communities:
         nx.subgraph(newGraph, [key for key in partition if partition[key]==community])
     node_color=[float(partition[v]) for v in partition]
     labels =  {}
     for node in newGraph.nodes():
         labels[node]= newGraph.node[node].get('name', '')
     nx.draw_spring(newGraph,node_color=node_color, labels=labels)
     plt.show()
     plt.savefig("C:\\Users\\Heschoon\\Dropbox\\ULB\\Current trends of artificial intelligence\\Trends_project\\graphs\\graph_induced.pdf")

def core_substitution(graph, orig_cip_graph, new_cip_graph):
    """
    graph is the whole graph..
    subgraph is the interfaceregrion in that we will transplant
    new_cip_graph which is the interface and the new core
    """
    assert( set(orig_cip_graph.nodes()) - set(graph.nodes()) == set([]) ), 'orig_cip_graph not in graph'

    # select only the interfaces of the cips
    new_graph_interface_nodes = [n for n, d in new_cip_graph.nodes(data=True) if 'core' not in d]
    new_cip_interface_graph = nx.subgraph(new_cip_graph, new_graph_interface_nodes)

    original_graph_interface_nodes = [n for n, d in orig_cip_graph.nodes(data=True) if 'core' not in d]
    original_interface_graph = nx.subgraph(orig_cip_graph, original_graph_interface_nodes)
    # get isomorphism between interfaces, if none is found we return an empty graph

    iso = get_good_isomorphism(graph,
                               orig_cip_graph,
                               new_cip_graph,
                               original_interface_graph,
                               new_cip_interface_graph)

    if len(iso) != len(original_interface_graph):
        # print iso
        # draw.display(orig_cip_graph)
        # draw.display(new_cip_graph)
        #draw.graphlearn([orig_cip_graph, new_cip_graph],size=10)
        logger.log(5,"grammar hash collision, discovered in 'core_substution' ")
        return nx.Graph()

    # ok we got an isomorphism so lets do the merging
    graph = nx.union(graph, new_cip_graph, rename=('', '-'))

    # removing old core
    # original_graph_core_nodes = [n for n, d in orig_cip_graph.nodes(data=True) if 'core' in d]
    original_graph_core_nodes = [n for n, d in orig_cip_graph.nodes(data=True) if 'core' in d]

    for n in original_graph_core_nodes:
        graph.remove_node(str(n))

    # merge interfaces
    for k, v in iso.iteritems():
        graph.node[str(k)][
            'interface'] = True  # i am marking the interface only for the backflow probability calculation in graphlearn, this is probably deleteable because we also do this in merge, also this line is superlong Ooo
        merge(graph, str(k), '-' + str(v))
    # unionizing killed my labels so we need to relabel


    return nx.convert_node_labels_to_integers(graph)

    def remove_bridges(self, in_file_, start_id, delim_):
        reader = csv.reader(open(in_file_), delimiter=delim_)
        for line in reader:
                self.G.remove_edge(int(line[0]) - start_id,int(line[1]) - start_id)
	
	print "no of components after removing bridges: %d" % nx.number_connected_components(self.G)
	comps = nx.connected_components(self.G)
	for comp in comps:
        	print len(comp)

        bfs = self.BreadthFirstLevels(1,100)
        nbunch = [1]
        for n in bfs:
            #print(n)
            val_ = n.values()
            for set_ in val_:
                nbunch += list(set_)
        #print nbunch
        print "start creating the induced graph!"
        induced_g = nx.subgraph(self.G, nbunch)
        self.G.clear()
#        start_ = 0
#        for n_ in induced_g:
#            self.maps_[n_] = start_
#            start_ += 1
#        for n_1 in induced_g:
#            for n_2 in induced_g:
#                if n_1 in induced_g.neighbors(n_2):
#                    self.G.add_edge(maps_[n_1],maps_[n_2]) 
        self.n = nx.number_of_nodes(induced_g)
        self.G = induced_g
        print "no of node: %d and no of edges: %d in induce graph!" % (self.G.number_of_nodes(), self.G.number_of_edges())

def find_football_communities():
    """ Finds the communities produced for the football network, uses compare
    methods to graph
    """
    fgraph = CD.football_graph()
    known = CD.football_known_c()
    temp7 = known[7]
    temp8 = known[8]
    temp9 = known[9]
    known[7] = temp8
    known[8] = temp9
    known[9] = temp7

    center_g = nx.Graph()
    center_g.add_nodes_from(range(12))
    centers = nx.circular_layout(center_g, scale = 10)
            
    pos = {}
    subgraphs = [nx.subgraph(fgraph, c) for c in known]
    count = -1
    for g in subgraphs:
        count += 1
        (off_x, off_y) = centers[count]
        pos_local = nx.circular_layout(g, scale=2.)
        for n, place in pos_local.iteritems():
            pos[n] = place + np.array([off_x, off_y])
    
    compare_methods(fgraph,
                    'football_',
                    param=[1., 1., 5./115., 4, 0, .7, 20],
                    known=known,
                    pos=pos,
                    color_map={76:1, 11:2, 7:3, 102:4, 104:5, 47:6, 98:7,
                               96:8, 23:9, 94:10, 27:0},
                    data_path="FootballGames/football_metis")

def vis_coauthor_communities(graph, source, i, prefix, options, radius, overlap):
    """ Finds the communities produced by different methods for the astro
    citation network
    """    
    interest = CD.get_ball(graph, options[source][i], radius)
    print "Displaying and computing for a subset of ", len(interest), " nodes."
    sgraph = nx.subgraph(graph, interest)
    
    cleaned = {}
    for key in options.keys():
        """ for generating sub community structure
        """
        if key == source:
            # split the overarching with the substructure
            cleaned[source] = [options[source][i]]
            options['Parallel Subcommunities'] = options[source][:i]
            options['Parallel Subcommunities'].extend(options[source][i+1:])
            key = 'Parallel Subcommunities'
        
        filtered = [filter(lambda n: n in interest, c) for c in options[key]]
        filtered = filter(lambda c: len(c) > 0, filtered)
        cleaned[key] = filtered
        cleaned[key] = CD.clean_of_duplicate_c(cleaned[key], overlap=overlap)

    compare_methods(sgraph, prefix, options=cleaned)

def compute_global_utility(graph):
    """
    Return an index that quantifies how big the size of adopter
    clusters is in the entire population of consumers. We call this
    index 'Global utility' in our article.

    This index computes the cluster-size-weighted average of adopter
    clusters divided by the total number of consumers

    So it goes from 0 to 1 and it's always increasing.
    """
    N = len(graph.nodes())
    adopters = get_adopters(graph)
    
    clusters = nx.subgraph(graph, adopters)
    cluster_sizes = [len(c) for c in nx.connected_components(clusters) if len(c) > 1]
    if cluster_sizes:
        # The weight of each cluster depends on its size
        weights = np.array(cluster_sizes) / N
        # Compute the weighted average
        weigthed_average = np.average(cluster_sizes, weights=weights)
        # Since the index needs to go between 0 and 1, we need to divide between N
        # again
        utility = weigthed_average / N
        return utility
    else:
        return 0

def dyad_census(pg, debug=0, debuglog=0):
    """
    dyad_census() calculates the number of null, asymmetric, and
    mutual edges between all pairs of nodes in a directed graph.
    """
    if not networkx.is_directed_acyclic_graph(pg):
        logging.error('pyp_network.dyad_census() requires a directed graph as input!')
        return 0
    else:
        census = {}
        census['null'] = 0
        census['asymmetric'] = 0
        census['mutual'] = 0
        tg = networkx.subgraph(pg, pg.nodes())
        for u in pg.nodes_iter():
            tg.delete_node(u)
            for v in tg.nodes_iter():
                if not pg.has_neighbor(u,v):
                    census['null'] = census['null'] + 1
                elif u in pg.predecessors(v) and v in pg.successors(u):
                    census['mutual'] = census['mutual'] + 1
                    if debug:
                        print 'Nodes %s and %s link to one another!' % ( u, v )
                    if debuglog:
                        logging.error('Nodes %s and %s link to one another!',u, v)
                elif u in pg.predecessors(v) and v not in pg.successors(u):
                    census['asymmetric'] = census['asymmetric'] + 1
                elif u not in pg.predecessors(v) and v in pg.successors(u):
                    census['asymmetric'] = census['asymmetric'] + 1
                else:
                    pass
        del(tg)
        return census

def mean_geodesic(pg, debug=0):
    """
    mean_geodesic() calculates the mean geodesic (shortest) distance
    between two vertices in a network.
    """
    length_sum = 0
    if networkx.is_directed_acyclic_graph(pg):
        n_pairs_with_paths = 0
    else:
        n_pairs_with_paths = ( pg.order() * ( pg.order() + 1 ) ) / 2
    tg = networkx.subgraph(pg, pg.nodes())
    for u in pg.nodes_iter():
        tg.delete_node(u)
        for v in tg.nodes_iter():
            try:
                length = networkx.shortest_path_length(pg,u,v)
                if length > 0:
                    length_sum = length_sum + length
                    if networkx.is_directed_acyclic_graph(pg):
                        n_pairs_with_paths = n_pairs_with_paths + 1
            except networkx.exception.NetworkXError:
                pass
    try:
        geodesic = float(length_sum) / float(n_pairs_with_paths)
    except:
        geodesic = -999.
    if debug:
        print 'length_sum:\t', length_sum
        print 'n_pairs_with_paths:\t', n_pairs_with_paths
    return geodesic

def bound_branch(G, k ,q_nodes, is_use_cores=False, select_method='rand'):
    '''
    wrapper of branch and bound method
    '''
    ts = time.time()
    global optimal
    optimal = set()
    k_neighbors = k_hop_nbrs_n(G, k, q_nodes)
    sub = set(q_nodes)
    sub.update(k_neighbors)
    g = nx.subgraph(G, sub)

    if is_use_cores:
        cores = nx.core_number(g)
    else:
        cores = None

    # print('subgraph ', g.nodes())
    print('minimum degree of subgraph', minimum_degree(g))
    print('k neighbors', len(k_neighbors))
    BB(g, k, q_nodes, set(), cores, select_method)
    print('the solution is', optimal)

    te = time.time()

    texe = round(te-ts, 2) # the execution time

    return texe

def upper_bound(G, k, H):
    '''
    the upper bound of size of k-plex of H in G
    '''
    # upper_bound_by_deg = min([nx.degree(G, node) for node in H]) + k
    # upper_bound_by_deg = 100

    subg = nx.subgraph(G, H)
    validate_neighbors = {node for node in neighbors(G, H) if len(set(G.neighbors(node)).intersection(H)) >= len(H)+1-k}

    strict_nodes = [node for node in H if len(subg[node]) == len(H)-k]
    if len(strict_nodes) > 0:
        avaliable_nodes = {node for node in G.neighbors(strict_nodes[0]) if node not in H}
        for i in range(1, len(strict_nodes)):
            avaliable_nodes.intersection_update({node for node in G.neighbors(strict_nodes[i]) if node not in H})
        avaliable_nodes.intersection_update(validate_neighbors)

        return len(H)+len(avaliable_nodes)
    else:
        min_d = float('inf')
        for node in H:
            nbrs = neighbors(G, [node])
            nbrs.intersection_update(validate_neighbors)
            num_non_nbrs = k-1-(subg.number_of_nodes() - nx.degree(subg, node))
            min_d = min(min_d, len(nbrs)+num_non_nbrs)
        return min_d

def subgraph_from_pathways(pathways, g):
    """
    returns a topological annotated graph containing given pathways
    """
    nodes = []
    if type(pathways) == list:
        for p in pathways:
            nodes += nodes_from_pathway(p, g)
    elif type(pathways) == str:
        nodes += nodes_from_pathway(pathways, g)
        
    h = nx.subgraph(g, nodes)

    remove_edges = []
    if type(pathways) == list:
        for p in pathways:
            for e in h.edges():
                if not p in h.get_edge_data(*e)['pathways']:
                    remove_edges.append(e)
    elif type(pathways) == str:
        for e in h.edges():
            if not pathways in h.get_edge_data(*e)['pathways']:
                remove_edges.append(e)
                
    for r in remove_edges:
        h.remove_edge(*r)

    return topological_annotate(h)

def init():
    global projectname
    global version_aray
    global pos
    global x
    global y
    global size_array
    global numframes
    global sg
    for i in range(6):
        data_directory = projectname + "_history/" + projectname + version_array[i] + "/" + projectname
        [g, lines] = creategraph.readfile(data_directory)
        if i == 0:
            sg = creategraph.refine(g, 45)
            [pos, x, y] = creategraph.coordinate(sg)
            size = creategraph.point_sizes(sg, lines)
            zeros = np.array([0] * len(size))
            print 'len(size) = ', len(size)
            print 'zeros = ', zeros
            size_array.append(zeros)
            size_array.append(size)
        else:
            # create the graph induced by nodes from sg
            subg = nx.subgraph(g, nx.nodes(sg))
            print subg, sg
            if nx.number_of_nodes(subg) != nx.number_of_nodes(sg):
                print 'panic at 34' 
            else: #                            v  this seems to be a error, but not
                size = creategraph.point_sizes(sg, lines)
                size_array.append(size)


    x = np.array(x)
    y = np.array(y)
    size_array = np.array(size_array)

def step3_balance_number(G,node):
	right=0
	wrong=0
	total=0
	cate_num=dict() #the number 16 cases
	ins=find_in_nodes(G,node)
	outs=find_out_nodes(G,node)
	sub_nodes=ins+outs
	subG=nx.subgraph(G,sub_nodes)
	for in_node in ins:
		c_outs=find_in_nodes(subG,in_node)
		for out_node in c_outs:
			if out_node in outs:
				total=total+1
				#node-->out_node-->mid_node-->in_node-->node
				flag1=(G[node][out_node]['weight']==-1)
				flag2=(G[out_node][in_node]['weight']==-1)
				flag3=(G[in_node][node]['weight']==-1)
				key=str(1000+flag1*100+flag2*10+flag3)
				
				if cate_num.has_key(key):
					cate_num[key]=cate_num[key]+1
				else:
					cate_num[key]=1

				if((flag1+flag2+flag3)%2==0):
					right=right+1
				else:
					wrong=wrong+1
	return (right,total,cate_num)

def filter_relevant_ids(graph):
    """
        Dado el grafo de mis followed y sus followed,
        extraemos los 100 nodos más relevantes 
    """
    graph = nx.read_gpickle('graph.gpickle')
    my_followed = list(set([x[0] for x in graph.edges()]))
    graph = nx.subgraph(graph, my_followed)

    def get_nfollowed(nid):
        return len(graph.successors(nid))

    def get_nfollowers(nid):
        return len(graph.predecessors(nid))

    import pandas as pd
    df = pd.DataFrame()
    df['nodeid'] = my_followed
    df['nfollowed'] = df['nodeid'].apply(get_nfollowed)
    df['nfollowers'] = df['nodeid'].apply(get_nfollowers)

    relevant = df[(df.nfollowed > 40) & (df.nfollowers > 40)]

    relevantids = list(relevant.nodeid.values)
    with open('layer0.pickle','wb') as f:
        pickle.dump(relevantids, f)

    return relevantids