def predict(u, v):
     cnbors = list(nx.common_neighbors(G, u, v))
     mult_val = G.degree(u) * G.degree(v)
     if mult_val == 0:
         return 0
     else:
         return len(cnbors)/ mult_val

def common_neighbors(features, G):
    nb_common_neighbors = []
    for i in range(features.shape[0]):
        a = features['From'][i]
        b = features['To'][i]
        nb_common_neighbors.append(len(sorted(nx.common_neighbors(G, a, b)))) # ajoute le nombre de voisins communs
    return nb_common_neighbors

 def predict(u, v):
     Cu = _community(G, u, community)
     Cv = _community(G, v, community)
     cnbors = list(nx.common_neighbors(G, u, v))
     neighbors = (sum(_community(G, w, community) == Cu for w in cnbors)
                  if Cu == Cv else 0)
     return len(cnbors) + neighbors

def get_edge_embeddedness(graph, pairs):
    c = Column(1, 'numerical')
    value = dict()
    for pair in pairs:
        value[pair] = len(list(nx.common_neighbors(graph, pair[0], pair[1])))
    c.value = value
    return c

 def __init__(self, preparedParameters, filePathResults, filePathAnalyseResult, topRank):
     print "Starting Analysing the results", datetime.today()
     
     absFilePath = filePathResults
     absfilePathAnalyseResult = filePathAnalyseResult #FormatingDataSets.get_abs_file_path(filePathAnalyseResult)
     fResult = open(absFilePath, 'r')
     with open(absfilePathAnalyseResult, 'w') as fnodes:
         self.success = 0
         element = 0
         for line in fResult:
             element = element+1
             FormatingDataSets.printProgressofEvents(element, topRank, "Analysing the results: ")
             cols = line.strip().replace('\n','').split('\t')
             if len(list(networkx.common_neighbors(preparedParameters.testGraph, cols[len(cols)-2] ,  cols[len(cols)-1] ))) != 0:
                 self.success = self.success + 1
                 fnodes.write(cols[len(cols)-2]  + '\t' + cols[len(cols)-1] + '\t' +  'SUCCESS \r\n')
             else:
                 fnodes.write(cols[len(cols)-2]  + '\t' + cols[len(cols)-1] + '\t' +  'FAILED \r\n')
             
             
             
             if element == topRank:
                 break 
         
         result =  float(self.success) / float(topRank) *100
         strResult = 'Final Result: \t' + str(result) + '%'
         fnodes.write(strResult)
         fnodes.write('\n#\t'+str(self.success))
         fnodes.close()
     print "Analysing the results finished", datetime.today()

 def simpleProximity(self, s, t): #s and t are the mip node IDs, NOT user/obj ids
     proximity = 0.0
     sharedWeight = 0.0
     for node in nx.common_neighbors(self.mip, s, t):
         sharedWeight = sharedWeight + self.mip[s][node]['weight'] + self.mip[t][node]['weight'] #the weight of the path connecting s and t through the current node
     proximity = sharedWeight/(self.mip.degree(s, weight = 'weight')+self.mip.degree(t, weight = 'weight')+0.000000000001)
     return proximity  

 def get_TimeofLinks(self, graph, node1, node2):
     result = []
     for node in networkx.common_neighbors(graph, node1, node2):
         for n,d in graph.nodes(data=True):
             if n == node:
                 result.append(d['time'])
     result.sort(reverse=True)
     return result

    def adamicAdarProximity(self, s, t):
        proximity = 0.0
        for node in nx.common_neighbors(self.mip, s, t):
            weights = self.mip[s][node]['weight'] + self.mip[t][node]['weight'] #the weight of the path connecting s and t through the current node
            if weights!=0: #0 essentially means no connection
#                print 'weights = '+str(weights)
#                print 'degree = '+str(self.mip.degree(node, weight = 'weight'))
                proximity = proximity + (weights*(1/(math.log(self.mip.degree(node, weight = 'weight'))+0.00000000000000000000000001))) #gives more weight to "rare" shared neighbors, adding small number to avoid dividing by zero
#                print 'proximity = '+str(proximity)
        return proximity    

 def get_BagofWords(self, graph, node1, node2):
     result = set()
     for node in networkx.common_neighbors(graph, node1, node2):
         for n,d in graph.nodes(data=True):
             if n == node:
                 for keyword in  ast.literal_eval(d['keywords']):
                     result.add(keyword)
                
     
     return result

def get_adamic_adar_score(graph, pairs):
    c = Column(1, 'numerical')
    value = dict()
    for pair in pairs:
        common_nei = nx.common_neighbors(graph, pair[0], pair[1])
        score = 0.0
        for n in common_nei:
            score += 1.0 / math.log(len(graph.neighbors(n)) + 1)
        value[pair] = score
    c.value = value
    return c

 def generateDataForCalculate(self):
     if self.trainnigGraph == None:
         self.generating_Training_Graph()
     
     _nodes = sorted(self.trainnigGraph.nodes())
     adb = Base(self.filePathTrainingGraph + ".calc.pdl")
     adb.create('pairNodes', 'common', 'time', 'domain' )
     
     for node in sorted(_nodes):
         othernodes = set(n for n in _nodes if n > node)
         for other in othernodes:
             common =  set(networkx.common_neighbors(self.trainnigGraph, node, other))
             arestas = self.trainnigGraph.edges([node, other], True)

def merge(G,edge):
    """Returns a new graph with edge merged, and the new node containing the
            information lost in the merge. The weights from common neighbors
            are added together, a la Stoer-Wagner algorithm."""            
    if G.node[edge[1]]['type'] == 'login' or G.node[edge[1]]['type'] == 'email':
        edge = edge[::-1] # If login/email is on the right, flip the order, so it's always on the left
    
    nx.set_node_attributes(G,'list',{edge[0]:G.node[edge[0]]['list']+[edge[1]]})

    J = nx.contracted_edge(G,(edge[0],edge[1]),self_loops = False)  #Contract edge without self-loop
    # Weight stuff
    N = nx.common_neighbors(G,edge[0],edge[1]) #find common nodes
    for i in N:
        J[i][edge[0]]['weight'] = G[edge[0]][i]['weight'] + G[edge[1]][i]['weight'] #modify the weight after contraction
    return J

def graph_stats(distance_couple, net):
    distances = []
    common_neighbors = []
    jaccard = []
    adamic = []
    edge_bet = []
    edge_betweeness = nx.edge_betweenness_centrality(net)
    for couple in distance_couple:
        distances.append(couple[1])
        common_neighbors.append(len(list(nx.common_neighbors(net, couple[0][0], couple[0][1]))))
        jaccard.append(list(nx.jaccard_coefficient(net, [(couple[0][0], couple[0][1])]))[0][2])
        adamic.append(list(nx.adamic_adar_index(net, [(couple[0][0], couple[0][1])]))[0][2])
        try:
            edge_bet.append(edge_betweeness[couple[0]])
        except KeyError:
            edge_bet.append(edge_betweeness[(couple[0][1], couple[0][0])])

    r_dist = 10.0/max(distances)
    r_n = 10.0/max(common_neighbors)
    r_j = 10.0/max(jaccard)
    r_a = 10.0/max(adamic)
    r_e = 10.0/max(edge_bet)

    distances = [j * r_dist for j in distances]
    common_neighbors = [j * r_n for j in common_neighbors]
    jaccard = [j * r_j for j in jaccard]
    adamic = [j * r_a for j in adamic]
    edge_bet = [j * r_e for j in edge_bet]

    plt.loglog(common_neighbors, color='b', label='common_neighbors')
    plt.loglog(distances, color='r', label='distances')
    plt.savefig('node_similarity/stats_cm.png', format='png')
    plt.close()

    plt.loglog(jaccard, color='b', label='jaccard')
    plt.loglog(distances, color='r', label='distances')
    plt.savefig('node_similarity/stats_j.png', format='png')
    plt.close()

    plt.loglog(adamic, color='b', label='adamic')
    plt.loglog(distances, color='r', label='distances')
    plt.savefig('node_similarity/stats_aa.png', format='png')
    plt.close()

    plt.loglog(edge_bet, color='b', label='edge betwenness')
    plt.loglog(distances, color='r', label='distances')
    plt.savefig('node_similarity/stats_eb.png', format='png')
    plt.close()

 def get_TimeofLinks(self, graph, node1, node2):
     result = []
     for node in networkx.common_neighbors(graph, node1, node2):
         if node in self.times:
             if self.debugar:
                 print "already found the time for paper ", node
         else:
             if self.debugar:
                 print "rescuing time from paper: ", str(node)
             
             paper = list(d for n,d in graph.nodes(data=True) if d['node_type'] == 'E' and n == node )
             if self.debugar:
                 print paper[0]['time']
             self.times[node] = paper[0]['time']
         result.append(self.times[node])
     result.sort(reverse=True)
     return result

    def calculateStability(self):
        balanceTriangle = 0
        totalTriangles = 0
        for edge, sign in self.edgeSignDict.iteritems():
            node1 = int(float(edge.split(",")[0]))
            node2 = int(float(edge.split(",")[1]))
            commonNeigh = sorted(nx.common_neighbors(self.graph, node1, node2))

            for inode in commonNeigh:
                sign1n = self.graph.get_edge_data(node1, inode, default={"weight": 10})["weight"]
                sign2n = self.graph.get_edge_data(node2, inode, default={"weight": 10})["weight"]
                sign12 = self.graph.get_edge_data(node1, node2, default={"weight": 10})["weight"]
                mul = sign1n * sign2n * sign12

                if mul > 0 and mul < 10:
                    balanceTriangle += 1
                # if (sign1n*sign2n*sign12) != 0:
                totalTriangles += 1

        print "Balance percentage: " + str((1.0 * balanceTriangle) / totalTriangles)

 def get_ObjectsofLinks(self, graph, node1, node2):
     result = []
     for node in networkx.common_neighbors(graph, node1, node2):
         if node in self.parameter.linkObjects:
             if self.debugar:
                 print "already found the time for paper ", node
         else:
             if self.debugar:
                 print "rescuing time from paper: ", str(node)
             
             MaxAmplitude = self.parameter.t0_ - 3
             if self.debugar:
                 print 'amplitude maxima:' , MaxAmplitude
             paper = list(d for n,d in graph.nodes(data=True) if d['node_type'] == 'E' and n == node )
             if self.debugar:
                 print 'Informacoes sobre o paper:' ,paper
             if paper[0]['time'] >= MaxAmplitude:
                 self.parameter.linkObjects[node] = [paper[0]['time'], eval(paper[0]['keywords'])]
         if self.debugar:
             print 'Informacoes sobre o paper ja na memoria:' , self.parameter.linkObjects[node]
         result.append(self.parameter.linkObjects[node])
     
     return result

 def get_pair_nodes_not_linked(self, graph, file, min_papers):
     print "Starting getting pair of nodes that is not liked", datetime.today()
     results = []
     nodesinGraph =set(n for n,d in graph.nodes(data=True) if d['node_type'] == 'N')
     currentNodes = set()
     for n in nodesinGraph:
         
         papers = set(networkx.all_neighbors(graph, n))
         print papers
         if (len(papers) >= min_papers):
             currentNodes.add(n)
     
     print 'qty of authors: ', len(currentNodes)
     nodesOrdered = sorted(currentNodes)
     element = 0
     totalnodesOrdered = len(nodesOrdered)
     for node1 in nodesOrdered:
         element = element+1
         FormatingDataSets.printProgressofEvents(element, totalnodesOrdered, "Checking Node not liked: ")
         
         others =  set(n for n in nodesOrdered if n > node1)
         notLinked = set()
         for other_node in others:
             if len(set(networkx.common_neighbors(graph, node1, other_node))) == 0:
                 notLinked.add(other_node)
         results.append([node1, notLinked])
         if element % 2000 == 0:
             for item in results:
                 file.write(str(item[0]) + '\t' +  repr(item[1]) + '\n')
             results = []
             
     for item in results:
         file.write(str(item[0]) + '\t' +  repr(item[1]) + '\n')
     results = []
         
     print "getting pair of nodes that is not liked finished", datetime.today()

    def test_clustering_score(self):
        """
        Test global clustering score with generalized formula

        This is the average of the local clustering scores for each node v:

                  2 Nv        where Kv = degree
        C(v) = ----------           Nv = number of edges between
               Kv (Kv - 1)               the neighbors of v
        """
        test_data_path = os.path.join(self._fixtures_dir, "les-miserables.csv")
        results = ctd.get_summary(test_data_path)
        graph = ctd.get_graph(test_data_path)

        local_scores = []
        for v in graph.nodes():
            k = graph.degree(v)
            neighbor_links = []
            for u in nx.all_neighbors(graph, v):
                neighbor_links += [tuple(sorted((u, w))) for w in nx.common_neighbors(graph, u, v)]
            n = len(list(set(neighbor_links)))
            local_scores.append(2 * n / float(k * (k - 1))) if k > 1 else local_scores.append(0)

        self.assertAlmostEqual(results["clustering"], sum(local_scores) / float(len(local_scores)))

G.add_edges_from(edges)

nx.write_gml(G, "actor_to_movie_all_movies.gml")

nodes_to_remove = []
for node in G.nodes():
	if G.degree(node) == 1:
		nodes_to_remove.append(node)

G.remove_nodes_from(nodes_to_remove)

nx.write_gml(G, "actor_to_movie_common_movies.gml")

for node in G.nodes():
	for node2 in G.nodes():
		if len(list(nx.common_neighbors(G, node, node2))) > 0:
			if G.edge[node, node2] is not None:
				G.add_edge(node, node2)
				G.edge[node, node2]['weight'] = 1
			else:
				G.edge[node, node2]['weight'] += 1

movies = []
for node in G.nodes():
	if node not in top_100_actors:
		movies.append(node)

G.remove_nodes_from(movies)

nx.draw(G, with_labels=True)
plt.show()

def get_dyads():
    offset = int(request.args.get('offset'))
    network_type = str(request.args.get('network_type'))


    cur = g.db.cursor(cursor_factory=psycopg2.extras.DictCursor)

    start = datetime.datetime(2015, 6, 27, 22, 0, 0, 0)
    if offset != 0:
        start = start + datetime.timedelta(minutes=10*offset)

    end = start + datetime.timedelta(minutes=10)

    cur.execute("""
    select pd.user_a, pd.user_b, lat, lon, c_time, dff.distinct_co_occurneces as distinct_grids, dff.same_concerts_jac, dff.same_camp_score from presentation_prediction_dyads pd
    inner join derived_friend_features dff on dff.user_a = pd.user_a and dff.user_b = pd.user_b
        where c_time between %s and %s
    """, (start, end, ))

    G = pickle.load(open("friends_graph.pkl", "rb")).to_undirected()

    nodes = []
    edges = []
    points = []

    degrees = G.degree()

    nodes_added = set()

    for dyads in cur.fetchall():
        points.append({
            'user_a': dyads['user_a'],
            'user_b': dyads['user_b'],
            'lat': float(dyads['lat']),
            'lon': float(dyads['lon'])
        })

        current_nodes = [dyads['user_a'], dyads['user_b']]
        # Add all neighbors

        if network_type == 'common':
            for neighbor in nx.common_neighbors(G, dyads['user_a'], dyads['user_b']):
                if neighbor not in nodes_added:
                    nodes.append((neighbor, 'blue'))
                    nodes_added.add(neighbor)

                for node in current_nodes:
                    edges.append((node, neighbor, 1))
        elif network_type=='no-neighbors':
            pass

        else:
            for node in current_nodes:
                for neighbor in G.neighbors(node):
                    if neighbor not in nodes_added and neighbor not in current_nodes:
                        nodes.append((neighbor, 'blue'))
                        nodes_added.add(neighbor)

                    edges.append((node, neighbor, 1))


        for node in current_nodes:
            if node not in nodes_added:
                nodes.append((node, 'red'))
                nodes_added.add(node)



        edges.append((dyads['user_a'], dyads['user_b'], dyads['distinct_grids']))

    new_nodes = [{'id': x[0], 'label':x[0], 'value': degrees[x[0]], 'color': x[1] } for x in list(set(nodes))]
    new_edges = []
    ids = []
    for edge in edges:
        _id = str(hash(':'.join([str(edge[0]), str(edge[1])])))
        if not _id in ids:
            ids.append(_id)
            new_edges.append({'from': edge[0], 'to': edge[1], 'value': edge[2], 'id': _id})

    print(str(sorted(Counter(ids).items())))

    response = {
            'points': points,
            'network': {
                'nodes': new_nodes,
                'edges': new_edges
            },
            'start': start.strftime("%Y-%m-%d %H:%M:%S"),
            'end': end.strftime("%Y-%m-%d %H:%M:%S")
        }

    return jsonify(response)