def m_projection(graph_orig, members, prods, full_graph):
    logging.info('Projecting the graph on members')

    graph = graph_orig.subgraph(graph_orig.nodes())
    #considering only favorable edges
    graph.remove_edges_from([e for e in graph.edges(data=True) if e[2]['starRating'] < 4])
    assert set(graph) == (set(members) | set(prods))

    mg = nx.Graph()
    mg.add_nodes_from(members)

    prods_len = float(len(prods))
    last_pctg = 0
    prod_names = dict()
    for p_i, p in enumerate(prods):
        # first check whether two favorable reviews within a WINDOW is significant enough (p-value < 0.5)
        ts = [e['date'] for e in full_graph[p].values()]
        # In order for gkde to work, there should be more than one point value
        if len(ts) >= MIN_TS_LEN and min(ts) < max(ts):
            gkde = gaussian_kde(ts)
            p_value, err = dblquad(lambda u, v: gkde(u)*gkde(v), min(ts) - WINDOW/2.0, max(ts) + WINDOW/2.0,
                                   lambda v: v - WINDOW/2.0, lambda v: v + WINDOW/2.0)
            if p_value - EPS >= SIGNF_LEVEL and err < EPS:
                continue
        for m1, m2 in itertools.combinations(nx.neighbors(graph, p), 2):
            # order m1,m2 so the key (m1,m2) for prod_names works regardless of edge direction
            if m1 > m2:
                m1, m2 = m2, m1
                #assert m1 in members and m2 in members
            if abs(graph[p][m1]['date'] - graph[p][m2]['date']) < WINDOW:
                if mg.has_edge(m1, m2):
                    c = mg[m1][m2]['weight']
                else:
                    c = 0
                    prod_names[(m1, m2)] = []
                prod_names[(m1, m2)].append(p)
                mg.add_edge(m1, m2, weight=c + 1)
        pctg = int(p_i/prods_len*100)
        if pctg % 10 == 0 and pctg > last_pctg:
            last_pctg = pctg
            logging.info('%d%% Done' % pctg)

    logging.debug('Normalizing edge weights: meet/max')
    for e in mg.edges():
        u, v = e
        if mg[u][v]['weight'] <= 1:
            mg.remove_edge(u, v)
            del prod_names[(min(u, v), max(u, v))]
        else:
            norm = max(len(nx.neighbors(graph, u)), len(nx.neighbors(graph, v)))
            mg.add_edge(u, v, weight=float(mg[u][v]['weight']) / norm, denom=norm)
    # remove isolated nodes
    degrees = mg.degree()
    mg.remove_nodes_from([n for n in mg if degrees[n] == 0])
    # adding original graph metadata on nodes
    for m in mg:
        mg.node[m] = graph_orig.node[m]
    logging.debug(r'Projected Nodes = %d, Projected Edges = %d' % (mg.order(), len(mg.edges())))

    return mg, prod_names

def find_sidechains(molecule_graph):
    # Identify chiral atoms
    atoms = molecule_graph.atoms
    chiral_centres = chir.get_chiral_sets(atoms)
    # Identify sidechains (Ca-Cb-X), apart from proline and glycine.
    sidechains = {}
    # Detection of sidechains requires the multiple bonds be present in the atom graph.
    chir.multi_bonds(atoms)
    for k, v in chiral_centres.items():
        carbons = [atom for atom in v if atom.element == "C"]
        amides = [
            carbon
            for carbon in carbons
            if any([type(nb) == chir.GhostAtom and nb.element == "O" for nb in nx.neighbors(atoms, carbon)])
            and any([nb.element == "N" or nb.element == "O" for nb in nx.neighbors(atoms, carbon)])
        ]
        nbs_n = [nb for nb in v if nb.element == "N"]
        if amides and nbs_n:
            amide_bond = (k, amides[0])
            n_bond = (k, nbs_n[0])
            h_bond = (k, [h for h in nx.neighbors(atoms, k) if h.element == "H"][0])
            # Now find sidechains by cutting the Ca-C, Ca-N and Ca-H bonds
            atoms.remove_edges_from([amide_bond, n_bond, h_bond])
            sidechain_atoms = [
                atom
                for atom in [comp for comp in nx.connected_components(atoms) if k in comp][0]
                if type(atom) != chir.GhostAtom
            ]
            atoms.add_edges_from([amide_bond, n_bond, h_bond])
            if not any([k in cycle for cycle in nx.cycle_basis(atoms.subgraph(sidechain_atoms))]):
                sidechains[k] = atoms.subgraph(sidechain_atoms)
    chir.remove_ghost_atoms(atoms)
    return sidechains

def all_children_of(tree, A):
	""" returns all the children of A """
	front = []
	children = []
	nbrs = nx.neighbors(tree, A)
	
	for n in nbrs:		
		if n.i_time > A.i_time:
			front.append(n)
			children.append(n) 

	if len(front) < 1:
		return children
	
	while 1:
		new_front = []
		if len(front) < 1:
			return children
		for a in front:
			nbrs = nx.neighbors(tree, a)
			for n in nbrs:
				if n.i_time > a.i_time:
					new_front.append(n) 
					children.append(n)
		front = new_front

def ministro_ministro(G):
    """
    Cria um grafo de ministros conectados de acordo com a sobreposição de seu uso da legislação
    Construido a partir to grafo ministro_lei
    """
    GM = nx.Graph()
    for m in G:
        try:
            int(m)
        except ValueError:# Add only if node is a minister
            if m != "None":
                GM.add_node(m.decode('utf-8'))
#    Add edges
    for n in GM:
        for m in GM:
            if n == m: continue
            if GM.has_edge(n,m) or GM.has_edge(m,n): continue
            # Edge weight is the cardinality of the intersection each node neighbor set.
            w = len(set(nx.neighbors(G,n.encode('utf-8'))) & set(nx.neighbors(G,m.encode('utf-8')))) #encode again to allow for matches
            if w > 5:
                GM.add_edge(n,m,{'weight':w})
    # abreviate node names
    GMA = nx.Graph()
    GMA.add_weighted_edges_from([(o.replace('MIN.','').strip(),d.replace('MIN.','').strip(),di['weight']) for o,d,di in GM.edges_iter(data=True)])
    P.figure()
    nx.draw_spectral(GMA)
    nx.write_graphml(GMA,'ministro_ministro.graphml')
    nx.write_gml(GMA,'ministro_ministro.gml')
    nx.write_pajek(GMA,'ministro_ministro.pajek')
    nx.write_dot(GMA,'ministro_ministro.dot')
    return GMA

    def chooseNodesByDistributionOld(self):
#        try:
        self.nodesToChange = [] #reset from previous turns 
        #choose first node based on distribution
        
        rand = random.random()
        cumProb = 0.0
        currIndex = 0
        currNode = self.controlledNodes[currIndex]
        cumProb = cumProb+currNode[1]
        while rand>cumProb:
            currIndex = currIndex+1
            currNode = self.controlledNodes[currIndex]
            cumProb = cumProb+currNode[1]
        chosenNode = copy.deepcopy(currNode[0])
        currNode = chosenNode
        self.nodesToChange.append(chosenNode)
        #get remaining nodes from neighbors
        for i in range(self.actionLimit-1): #TODO: consider randomizing number of nodes chosen; consider prioritizing just neighbors of first node
            newNode = random.sample(nx.neighbors(self.knownGraph, currNode),1)
            while ((len(newNode)==0)):
                newNode = random.sample(nx.neighbors(self.knownGraph, currNode),1)
                if newNode in self.nodesToChange:
                    print 'why?'
            self.nodesToChange.append(newNode[0])
            currNode = newNode[0]
        for i in range(len(self.nodesToChange)):
            for j in range(i+1,len(self.nodesToChange)):
                if self.nodesToChange[i] == self.nodesToChange[j]:
                    print 'problem'
       
        return self.nodesToChange    

def main():    
    universe = nx.read_graphml(sys.argv[1])
    
    beings = filter(lambda x: x[1]["type"] == "Being", universe.nodes(data=True))
    clients = filter(lambda x: x[1]["type"] == "client", universe.nodes(data=True))
    firm = filter(lambda x: x[1]["type"] == "firm", universe.nodes(data=True))        
    print len(beings)
    print len(clients)
    print len(firm)
    
    for b in beings:
        ns = nx.neighbors(universe,b[0])
        rep = ns[0]
        for n in ns[1:]:
            for nn in nx.neighbors(universe,n):
                universe.add_edge(rep,nn) #doesn't preserve directions or properties, yolo
            universe.remove_node(n)
        universe.remove_node(b[0])
        
    beings = filter(lambda x: x[1]["type"] == "Being", universe.nodes(data=True))
    clients = filter(lambda x: x[1]["type"] == "client", universe.nodes(data=True))
    firm = filter(lambda x: x[1]["type"] == "firm", universe.nodes(data=True))        
    print len(beings)
    print len(clients)
    print len(firm)
            
    nx.write_graphml(universe,"simplified-{}.graphml".format(int(time.time())))

	def hinges(self):
		""" Return a list of all detected hinge nodes """
		ret = []
		# Consider a node a /possible/ hinge if it meets two criteria:
		# - it has a degree of at least 3
		# - it is in two or more visible faces
		for node in [x for x in self.graph.nodes_iter() 
				if len(nx.neighbors(self.graph, x)) > 3]:

			neighbors = nx.neighbors(self.graph, node)
			faces = set()
			#print node
			for n in neighbors:
				f1 = self.graph[node][n]['face']
				f2 = self.graph[n][node]['face']
				if f1.visible:
					faces.add(f1)
				if f2.visible:
					faces.add(f2)

			if len(faces) < 2:
				continue
			
			#print 'sending to examine_hings'
			result,on = self._examine_hinge(node)
			if len(result) > 3:
				#pprint.pprint(on)
				#pprint.pprint(result)
				ret.append(node)
		return ret 

def cluster_graph( g, colors, current_color = 0 ):
    # Initialize colors
    degrees = []
    for n in g.nodes( ):
        degrees.append( (nx.degree(g, n ), n))

    nodeWithMaxDegree = sorted( degrees, reverse = True )[0][1]

    # Start with node with maximum degree
    current_color  += 1
    colors[ nodeWithMaxDegree ] = current_color

    numIteration = 0
    pN = nodeWithMaxDegree
    stack = [ nodeWithMaxDegree ]
    while stack:
        neighbours = nx.neighbors( g, stack.pop( ) )
        numIteration += 1
        for n in neighbours:
            if colors[n] > 0:
                continue
            # If most neightbours of n are as close to pN as the value current
            # iteration, then accept this node.
            potentialCandidates = filter(lambda x: colors[x] == 0, nx.neighbors( g, n ))
            # print( "Potential neighbours ", potentialCandidates )
            distance2pN = [ nx.shortest_path_length( g, x, pN) for x in potentialCandidates ]
            goodDist2pN = filter( lambda x: x <= numIteration, distance2pN )
            accepted = False
            if len( goodDist2pN ) > 0:
                accepted = True
                colors[ n ] = current_color 
                stack.append( n )
            # print n, ' -> ', distance2pN, ',', goodDist2pN, 'Accepted', accepted
        # print stack
    return g

def RW_Size(G,r = 1000,m=100):
    sampled = []
    now_node = random.choice(G.nodes())
    sampled.append(now_node)
    while True:
        next_node = random.choice(nx.neighbors(G,now_node))
        now_node = next_node
        sampled.append(now_node)
        if len(sampled) >= r:
            break
    print(1)
    lst = []
    for i in range(0,r-m):
        if i+m <= r-1:
            for j in range(i+m,r):
               # l1 = set(nx.neighbors(G,sampled[i]))
               # l2 = set(nx.neighbors(G,sampled[j]))
               # if len(list(l1 & l2)) >= 1:
                lst.append((sampled[i],sampled[j]))
                lst.append((sampled[j],sampled[i]))
    sumA = 0.0
    sumB = 0.0
    print(len(lst))
    for nodes in lst:
        sumA += float(nx.degree(G,nodes[0]))/nx.degree(G,nodes[1])
        l1 = set(nx.neighbors(G,nodes[0]))
        l2 = set(nx.neighbors(G,nodes[1]))
        count = len(list(l1&l2))
        sumB += count/(float(nx.degree(G,nodes[0]))*nx.degree(G,nodes[1]))
    return sumA/sumB

def fast_approximate_solution_two(graph):
    """
    Given a graph, construct a solution greedily using approximation methods.
    Performs bad.
    """
    new_graph = nx.Graph()
    degrees = nx.degree_centrality(graph) 
    largest = argmax(degrees)
    new_graph.add_node(largest)
    while new_graph.number_of_edges() < graph.number_of_nodes() - 1:
        degrees = {n: count_uncovered_degree(graph, new_graph, n) for n in nx.nodes(graph)}
        neighbor_list = [nx.neighbors(graph, n) for n in new_graph.nodes()]
        neighbors = set()
        for lst in neighbor_list:
            neighbors = neighbors.union(lst)
        if not neighbors:
            break
        next_largest = argmax_in(degrees, neighbors, exceptions = new_graph.nodes())
        possible_edge_ends = [n for n in nx.neighbors(graph, next_largest) 
                              if graph.has_edge(n, next_largest) 
                              and n in new_graph.nodes()]
        new_graph.add_node(next_largest)
        edge_end = argmax_in(degrees, possible_edge_ends)
        new_graph.add_edge(edge_end, next_largest)

    return new_graph

	def printroute(self):
		for src in self.nodes.iterkeys():
			print "[Neighors List] neighbor = %s" % (src)
			print nx.neighbors(self.graph, src)
			print "[Shortest Paths] - %s " % (src)
			for dst in self.nodes.iterkeys():
				if src != dst:
					print nx.shortest_path(self.graph, src, dst)

def mindeg_GSK(BG, variables_index=0, verbose=False):
    Vprime1 = [];
    Vprime2 = [];
    
    layer = nx.get_node_attributes(BG,'bipartite');
    var = [x for x in BG.nodes() if layer[x] == variables_index]
    fac = [x for x in BG.nodes() if layer[x] != variables_index]
    
    if verbose==True:
        print 'Initial variable nodes:', var;
        print 'Initial factor nodes:', fac;

    isolated_variables = [x for x in BG.nodes() if nx.degree(BG,x)==0 and layer[x]==variables_index];
    [var.remove(x) for x in isolated_variables]
    
    G = BG.copy();
    Vprime1.extend(isolated_variables);
    G.remove_nodes_from(isolated_variables)
    
    isolated_factors = [x for x in G.nodes() if nx.degree(BG,x)==0 and layer[x]!=variables_index];
    [fac.remove(x) for x in isolated_factors]
    G.remove_nodes_from(isolated_factors);

    while len(var)>0:
        if verbose==True:
            print '#var:',len(var),'#fac:', len(fac), '#nodes in depleted graph:', G.number_of_nodes(),'#original BG:',BG.number_of_nodes();

        pendant = return_mindeg_pendant(G,layer,variables_index);
        if len(pendant)==0:
            ## if not, choose randomly and do the game. 
            if verbose==True:
                print var
            m = G.number_of_nodes()*2;
            degs = G.degree();
            for e in G.edges():
                if degs[e[0]] + degs[e[1]] < m:
                    m = degs[e[0]] + degs[e[1]];
                    v = e;
            if e[0] in var:
                v = e[0];
            else:
                v = e[1];
            pendant = []
            pendant.append(v);
            pendant.extend(nx.neighbors(G,v));
            Vprime2.append(pendant[0]);
        else:
            Vprime1.append(pendant[0]);
        augmented_pendant = []
        augmented_pendant.extend(pendant);
        for n in pendant[1:]:
            augmented_pendant.extend(nx.neighbors(G,n));
        augmented_pendant = list(set(augmented_pendant));
        G.remove_nodes_from(augmented_pendant);        
        [var.remove(x) for x in augmented_pendant if x in var];
        [fac.remove(x) for x in augmented_pendant if x in fac];

    return Vprime1,Vprime2;

    def __repr__(self):

        st = str(self.rootid) + "\n"
        levels = nx.neighbors(self, self.rootid)
        st = st + "---" + "\n"
        for l in levels:
            nw = len(nx.neighbors(self, l))
            st = st + str(l) + " : " + str(nw) + "\n"
        return st

def explore(u, pre):
    pre.append(u)
    
    if len(nx.neighbors(G,u)) == 0:
        Leafs[u]=set(pre)
        return

    for v in nx.neighbors(G, u):
        explore(v, pre[:])

def Welsh_Powell(g,nome):
    '''
    Função: Resolver o sudoku, é gerado um arquivo com a resolução
            a resolução também é mostrada no programa
    Parametros: g, grafo de incompatibilidade do sudoku
    Retorno: -
    '''
    #Todos os vértices tem o mesmo grau
    #Atribui uma lista de possíveis "cores" para cada vértice
    ci = []
    for no_atual in range(81):
        #verifica se o no não tem valor
        if g.node[no_atual] == 0:
            g.node[no_atual] = []
            #Lista de vértices não resolvidos
            ci.append(no_atual)
            #recupera o valor que os vizinhos possuem
            valores_vertice = [g.node[v] for v in nx.neighbors(g,no_atual)]
            #Coloca como possível valor do no os valores que não estão presentes em seus 
            #vizinhos
            for possivel_valor in range(1,10):
                if possivel_valor not in valores_vertice:
                    g.node[no_atual].append(possivel_valor)
    
    #Enquanto houver mais de um elemento por nó
    while len(ci):
        #Escolhe um no que não tem seu valor definido
        for v in ci:
            #Escolhe um no que tem só uma possibilidade
            if len(g.node[v]) == 1:
                no_retirado = g.node[v][0]
                g.node[v] = g.node[v][0]                
                ci.remove(v)
                #Remove o valor do no que tinha só uma possibilidade dos vizinhos
                for i in nx.neighbors(g,v):
                    if i in ci and no_retirado in g.node[i]:
                        g.node[i].remove(no_retirado)
    resposta = []        
    for i in range(81):
        resposta.append(g.node[i])
    gravar = int(raw_input('Para guardar a resposta em arquivo digite:\n1 - Sim\n2 - Não\n'))
    #Grafa a resposta em arquivo
    if gravar:
        arq_resposta = open(nome,"w")
        for i in range(81):
            if (i+1) % 9 == 0:
                arq_resposta.write(str(resposta[i])+'\n')
            else:
                arq_resposta.write(str(resposta[i])+" ")
        arq_resposta.close()
    print '\nResposta: '
    #Mostra a resposta no console
    for i in range(81):
        print g.node[i],
        if (i+1) % 9 == 0:
            print 

def mhrw_sampling(network, desired_order): 
    ''' MHRV algorithm '''
    
    # variables here
    g = nx.Graph()
    order = 0
    go_more = True
    
    # Try to get the first node that is not isolated 
    trycount = 0
    found_node = False

    while trycount < 10 and not found_node:
        v = random.choice(network.nodes())
        neighbors = nx.neighbors(network, v)
        if not neighbors: 
            trycount += 1
        else: 
            found_node = True

    # if didnt find the node, just return
    if not found_node:       
        return False, g, 0
    
    # now, with the first node, we start our graph
    g.add_node(v)

    while order < desired_order and go_more:
        
        # If don't find more neighboors, but almost have the order
        neighbors = nx.neighbors(network, v)
        if not neighbors:
            if order < 0.9*desired_order:
                return False, g, order
            else:
                return True, g, order

        # If find neighboors keep going
        for i in range(len(neighbors)): 
            g.add_edge(v, neighbors[i])   

        order_new = g.order()
        # If we are too big now (more than 30%), lets try again
        if order_new > 1.3*desired_order:
            return False, g, order

        # or If we reach the order we want 
        if order_new >= desired_order:
            go_more = False
         
        # If nothing happened, keep going...
        v = random.choice(neighbors) 
        order = order_new

    return True, g, order

def coefficient(node_i,node_j,G):
    '''
        paper : <<Defining and identifying communities in networks>>
    '''
    neighbors_i = set(nx.neighbors(G, node_i))
    neighbors_j = set(nx.neighbors(G, node_j))
    common = len(set(neighbors_i & neighbors_j))
    min_k = min(len(neighbors_i),len(neighbors_j))-1
    if(min_k == 0):
        return 1
    else:
        return common / min_k

    def run3(self,cs,ct,cutoff=1):

        ns = nx.neighbors(self.L.Gt,cs)
        nt = nx.neighbors(self.L.Gt,ct)
        print ns
        print nt
        path=[]
        for s in ns:
            for t in nt:
                p=nx.dijkstra_path(self.L.Gt,s,t)
                if not cs in p and not ct in p:
                    path.append(p)
        return path

def CC2(G,node):
    n_list = nx.neighbors(G,node)
    degree = len(n_list)
    if degree <= 1:
        return 0
    tri = 0
    count = 0
    for i in range(0,degree-1):
        n2_list = nx.neighbors(G,n_list[i])
        for j in range(i+1,degree):
            count += 1
            if n_list[j] in n2_list:
                tri += 1
    return float(tri)/count

def updateNeighbors(s2,s1,L1,L2,P1,P2,G):    
    L1.append(s1)
    L2.remove(s1)
    L2.append(s2)
    L1.remove(s2)
    
    
    if not hasOutsideNeighbor(s1,P1,G) :
        L1.remove(s1)

    if not hasOutsideNeighbor(s2,P2,G) :
        L2.remove(s2)
    
    N1 = nx.neighbors(G,s1)
    N2 = nx.neighbors(G,s2)

    for node1 in N1 :
        if node1 in P1:
            #print "Nodes",node1,"and",s1,"in the same partition"
            if hasOutsideNeighbor(node1,P1,G) :
                #print "Node", node1, "has a neighbor outside from",P1
                if node1 not in L1 :
                    L1.append(node1)
                    #print "L1 : ajout de", node1
            else :
                if node1 in L1 :
                    L1.remove(node1)
                #print "L1 : suppression de", node1
        else:
            #print "Nodes",node1,"and",s1,"not in the same partition"
            if not hasOutsideNeighbor(node1,P1,G) and node1 in L1:
                L1.remove(node1)
                #print "L1 : suppression de", node1
                
    for node2 in N2 : 
        if node2 in P2 :
            #print "Nodes",node2,"and",s2,"in the same partition"
            if hasOutsideNeighbor(node2,P2,G) :
                #print "Node", node2, "has a neighbor outside from",P2
                if node2 not in L2 :
                    L2.append(node2)
                    #print "L2 : ajout de", node2
            else :
                if node2 in L2 :
                    L2.remove(node2)
                #print "L2 : suppression de", node2
        else:
            #print "Nodes",node2,"and",s2,"not in the same partition"
            if not hasOutsideNeighbor(node2,P2,G) and node2 in L2:
                L2.remove(node2)