def run(edges, show=False):
    G=nx.DiGraph()
    #G.add_weighted_edges_from([('A','B',0.5),('A','C',0.5)])
    G.add_edges_from(edges)
    if show:
        nx.draw(G, pos=nx.spring_layout(G))
        plt.show()
        nx.write_dot(G,'./graph.dot')
        # dot -n -Tpng graph.dot >graph.png
    print nx.hits(G,max_iter=10**3) #tol=1e-4)
    print nx.pagerank(G)

def realhits(G):
	rhits = {}
	hubs , auths =nx.hits(G)
	for pack in hubs:
		rhits[pack] = (int(hubs[pack]*1000000000000),  int(auths[pack]*1000000000000))

	return rhits

 def test_hits(self):
     G=self.G
     h,a=networkx.hits(G,tol=1.e-08)
     for (x,y) in zip(sorted(h.values()),self.G.h):
         assert_almost_equal(x,y,places=5)
     for (x,y) in zip(sorted(a.values()),self.G.a):
         assert_almost_equal(x,y,places=5)

    def __init__(self, all_user_check_ins, network, current_user):
        G = nx.DiGraph()
        for user in all_user_check_ins:
            for check_in in all_user_check_ins[user]:
                venue = check_in["venue_id"]
                if user not in G.nodes():
                    G.add_node(user)
                if venue not in G.nodes():
                    G.add_node(user)
                if (user, venue) not in G.edges():
                    G.add_edge(user, venue, weight=1)
                else:
                    current_weight = G.get_edge_data(user, venue)["weight"]
                    G.add_edge(user, venue, weight=current_weight + 1)
        (hub_scores, authority_scores) = nx.hits(G)
        self.authority_scores = authority_scores
        self.user = current_user
        self.user_check_ins = all_user_check_ins[current_user]
        self.network = network

        friend_count = {}
        for user in network:
            friend_count[user] = len(network[user])

        self.friend_count = friend_count

 def test_hits(self):
     G=self.G
     h,a=networkx.hits(G,tol=1.e-08)
     for n in G:
         assert_almost_equal(h[n],G.h[n],places=4)
     for n in G:
         assert_almost_equal(a[n],G.a[n],places=4)

 def test_empty(self):
     G=networkx.Graph()
     assert_equal(networkx.hits(G),({},{}))
     assert_equal(networkx.hits_numpy(G),({},{}))
     assert_equal(networkx.hits_scipy(G),({},{}))
     assert_equal(networkx.authority_matrix(G).shape,(0,0))
     assert_equal(networkx.hub_matrix(G).shape,(0,0))

def plot_hubs_and_authorities(G):
    """
    cria um bar plot
    """
    ha = nx.hits(G)
    print G,len(ha)
    hubs = {k:v for k,v in ha[0].items() if v!=0.0}
    auth = {k:v for k,v in ha[1].items() if v!=0.0}
    hubs.pop('None')
    # Sorting by value
    hubs = sorted(hubs.items(),key=lambda i:i[1],reverse=1)
    auth = sorted(auth.items(),key=lambda i:i[1],reverse=1)

    # Hubs
    fig = P.figure()
    ax = fig.add_subplot(111)
    labels = [l[0].decode('utf8') for l in hubs]
    vals = [l[1] for l in hubs]
    pos = np.arange(len(hubs))
    ax.barh(pos,vals,align='center',height=.8,)
    P.xlabel('Hub Statistic')
    P.ylabel('Ministers')
    P.yticks(pos,labels,size='small')

    # Authorities
    fig = P.figure()
    ax = fig.add_subplot(111)
    auth = auth[:25] # only the most cited laws
    labels = ['$%s$'%l[0] for l in auth]
    vals = [l[1] for l in auth]
    pos = np.arange(len(auth))
    ax.barh(pos,vals,align='center',height=.8)
    P.xlabel('Authority Statistic')
    P.ylabel('Law id')
    P.yticks(pos,labels)

def analyze_graph(G):    
    #centralities and node metrics
    out_degrees = G.out_degree()
    in_degrees = G.in_degree()
    betweenness = nx.betweenness_centrality(G)
    eigenvector = nx.eigenvector_centrality_numpy(G)
    closeness = nx.closeness_centrality(G)
    pagerank = nx.pagerank(G)
    avg_neighbour_degree = nx.average_neighbor_degree(G)
    redundancy = bipartite.node_redundancy(G)
    load = nx.load_centrality(G)
    hits = nx.hits(G)
    vitality = nx.closeness_vitality(G)
    
    for name in G.nodes():
        G.node[name]['out_degree'] = out_degrees[name]
        G.node[name]['in_degree'] = in_degrees[name]
        G.node[name]['betweenness'] = betweenness[name]
        G.node[name]['eigenvector'] = eigenvector[name]
        G.node[name]['closeness'] = closeness[name]
        G.node[name]['pagerank'] = pagerank[name]
        G.node[name]['avg-neigh-degree'] = avg_neighbour_degree[name]
        G.node[name]['redundancy'] = redundancy[name]
        G.node[name]['load'] = load[name]
        G.node[name]['hits'] = hits[name]
        G.node[name]['vitality'] = vitality[name]
        
    #communities
    partitions = community.best_partition(G)
    for member, c in partitions.items():
        G.node[member]['community'] = c   
    
    return G

def pagerank_hits():
    conn = sqlite3.connect("zhihu.db")     
    #following_data = pd.read_sql('select user_url, followee_url from Following where followee_url in (select user_url from User where agree_num > 50000) and user_url in (select user_url from User where agree_num > 50000)', conn)        
    following_data = pd.read_sql('select user_url, followee_url from Following where followee_url in (select user_url from User where agree_num > 10000) and user_url in (select user_url from User where agree_num > 10000)', conn)        
    conn.close()
    
    G = nx.DiGraph()
    cnt = 0
    for d in following_data.iterrows():
        G.add_edge(d[1][0],d[1][1])
        cnt += 1
    print 'links number:', cnt
    pylab.figure(0)
    nx.draw_networkx(G)
    pylab.show()

    # PageRank
    pr = nx.pagerank(G)
    prsorted = sorted(pr.items(), key=lambda x: x[1], reverse=True)
    print 'pagerank top 100:\n'
    for p in prsorted[:100]:
        print p[0], p[1]
    
    # HITS
    hub, auth = nx.hits(G)
    print 'hub top 100:\n'
    for h in sorted(hub.items(), key=lambda x: x[1], reverse=True)[:100]:
        print h[0], h[1]
    print '\nauth top 100:\n'    
    for a in sorted(auth.items(), key=lambda x: x[1], reverse=True)[:100]:     
        print a[0], a[1]

def p_original(fm, q_id, pqw, pwords, dls, pj, res, k1, k2, b, avdl, N, Nd, alpha, beta, gamma):
    """
    Fa il retrieve per la singola query
    :param fm: frequency matrix
    :param q_id: query id
    :param pqw: lista di query words per questa query
    :param pwords: dizionario delle parole
    :param dls: lunghezze dei documenti
    :param pj: indice dove scrivere in res
    :param res: matrice di output
    :param k1: param per bm25
    :param k2: param per bm25
    :param b: param per bm25
    :param avdl: lunghezza media dei documenti
    :param N: numero dei documenti
    :return: niente, salva la roba su res
    """
    # ignorare questa parte, fate finta che funzioni, alla fine avete il risultato di bm25
    actual_qw = []
    indexes_of_qws = []
    for qw in pqw:
        if qw in pwords:
            actual_qw.append(qw)
            indexes_of_qws.append(pwords[qw])

    indexes_of_qws = np.array(indexes_of_qws)
    tmp = np.arange(0, fm.shape[1])
    indexes_of_qws = np.in1d(tmp, indexes_of_qws)
    red_fm = fm[:, indexes_of_qws]
    idfs = np.ones(shape=(red_fm.shape[0], red_fm.shape[1]))
    tmp2 = np.copy(red_fm)
    tmp2[tmp2 != 0] = 1
    nis = tmp2.sum(axis=0)
    Ns = np.ones(red_fm.shape[1])*N
    idfs = np.log((Ns - nis + 0.5)/(nis + 0.5))
    Ks = k1*((1-b) + b*(dls/avdl))
    tf1s = red_fm*(k1 + 1)/(np.tile(Ks, (red_fm.shape[1], 1)).T + red_fm)
    tf2s = np.ones(red_fm.shape)
    ress = np.multiply(idfs, tf1s)
    ress = ress.sum(axis=1)
    idss = np.arange(0, red_fm.shape[0])

    idss_indx = np.argsort(ress)[::-1]

    idss = idss[idss_indx]
    ress = ress[idss_indx]

    idss_N = idss[0:Nd]
    ress_N = ress[0:Nd]

    G = get_graph_N(idss_N)

    try:
        auths, hubs = nx.hits(G)
    except nx.exception.NetworkXError, e:
        auths = {str(nid): 1.0 for nid in idss_N}
        hubs = {str(nid): 1.0 for nid in idss_N}

def hits_algo(adj_matrix,hub_score):  
    # INPUT: Initial hub_score, authorities score and adjacency matrix.
    # OUTPUT: Converged
    print "Running HITS algorithm..."
    graph = nx.to_networkx_graph(adj_matrix)
    # print graph
    nstart = dict([(i, hub_score[i]) for i in xrange(len(hub_score))])
    # print nstart
    # return nx.hits(graph)
    return nx.hits(graph,nstart=nstart)

 def test_empty(self):
     try:
         import numpy
     except ImportError:
         raise SkipTest('numpy not available.')
     G=networkx.Graph()
     assert_equal(networkx.hits(G),({},{}))
     assert_equal(networkx.hits_numpy(G),({},{}))
     assert_equal(networkx.authority_matrix(G).shape,(0,0))
     assert_equal(networkx.hub_matrix(G).shape,(0,0))

def extract_social_features(df_comments):
    socialVector = np.empty([df_comments.shape[0],8])
    index = 0
        
    graph = networkx.DiGraph()   
    
    userdict = dict()
    for _, row in df_comments.iterrows():
        userdict[row['comment_id']] = row['author']
        
    for user in set(userdict.values()):
        graph.add_node(user)
        
         
    for _, row in df_comments.iterrows():
        if not userdict.has_key(row['thread_root_id']):
            continue
        
        source = userdict[row['comment_id']]
        dest = userdict[row['thread_root_id']]
        if source == dest:
            continue
        graph.add_edge(source, dest)
    
    pageranker = networkx.pagerank(graph, alpha=0.85)
    hubs, auths = networkx.hits(graph)
    
    author_groupby = df_comments.groupby('author')
    user_age_dict = {}
    user_nr_posts_dict = {}
    for _,group in author_groupby:
        first_date = datetime.fromtimestamp(mktime(group.date.values[0]))
        last_date = datetime.fromtimestamp(mktime(group.date.values[-1]))
        diff = last_date - first_date
        days = diff.days
        user_age_dict[group.author.values[0]] = days + 1
        user_nr_posts_dict[group.author.values[0]] = len(group)
        
    for ix, row in df_comments.iterrows():            
        user = userdict[row['comment_id']]
        socialVector[ix][0] = graph.in_degree(user) #In Degree
        socialVector[ix][1] = graph.out_degree(user) #Out Degree
        socialVector[ix][2] = user_age_dict[user] #User Age
        socialVector[ix][3] = user_nr_posts_dict[user] #Nr of Posts
        socialVector[ix][4] = user_nr_posts_dict[user]/float(user_age_dict[user]) # Postrate
        socialVector[ix][5] = pageranker[user] # Pagerank
        socialVector[ix][6] = hubs[user] # Pagerank
        socialVector[ix][7] = auths[user] # Pagerank
    
        index += 1
        if index % 1000 == 0:
            print "extracted", index, "values"
        
                
    return socialVector

def getHits(G):
    print "Calculating HITS"
    ret = []
    try:
        hubs, auths = nx.hits(G)
        for pack in hubs:
            ret.append((pack, (hubs[pack], auth[pack])))

    except nx.NetworkXError:
        print "HITS failed"
    return ret

def test_hits(testgraph):
    """
    Test hits algorithm
    """

    h0, a0 = nx.hits(testgraph[0], max_iter=100)
    h1, a1 = sg.links.hits(testgraph[1], max_iter=100)

    for u in testgraph[0].nodes_iter():
        assert abs(h0[u] - h1[u]) < 1e-5
        assert abs(a0[u] - a1[u]) < 1e-5

	def __link_analysis(self): # recalculates hub and authority rate

		# insert check for existing hub? reduce computational time
		nstart = {}
		for name in nx.nodes(self.OG):
			nstart[name] = self.OG.node[name]['normweightmax']
		
		h, a = nx.hits(self.OG, max_iter = 30)
		for node in self.OG.nodes():
			self.OG.node[node]['hub'] = h[node]
			self.OG.node[node]['authority'] = a[node]

		#for WOG
		nstart2 = {}
		for name in nx.nodes(self.WOG):
			nstart2[name] = self.WOG.node[name]['normweightmax']
		
		h2, a2 = nx.hits(self.WOG, max_iter = 30)
		for node in self.WOG.nodes():
			self.WOG.node[node]['hub'] = h2[node]
			self.WOG.node[node]['authority'] = a2[node]

def hits_example():
    n = 7
    #~ g = nx.wheel_graph(n)
    #~ pos = nx.spring_layout(g)
    g = nx.DiGraph()
    g.add_nodes_from(range(0,n))
    edge_list = [(0,1),(0,6),(0,5),(1,2),(1,6),(2,0),(2,1),(2,3),(3,4),(4,5),(4,6),(5,0),(5,3),(5,4)]
    g.add_edges_from(edge_list)
    hubs,auts = nx.hits(g)
    for n in range(0,n):
        print 'node',n
        print '  authority:',auts[n]
        print '  hubness:', hubs[n]
        print '  out:',g.successors(n)
        print '  in:',g.predecessors(n)

def get_statistics():
    """
    uses data statistics to find the most important papers in the collection.
    """
    
    
    with open(MAIN_FOLDER + "network.pkl", "r") as f:
        network = pickle.load(f)

    betweenness_dict = networkx.betweenness_centrality(network.to_undirected())
    sorted_betweenness = sorted(betweenness_dict.items(), key=operator.itemgetter(1), reverse=True)
    betweenness = [x[0] for x in sorted_betweenness[:5]]

    pagerank_dict = networkx.pagerank(network.to_undirected())
    sorted_pagerank = sorted(pagerank_dict.items(), key=operator.itemgetter(1), reverse=True)
    pagerank = [x[0] for x in sorted_pagerank[:5]]

    hits_dict = networkx.hits(network.to_undirected())
    sorted_hits = sorted(hits_dict[0].items(), key=operator.itemgetter(1), reverse=True)
    hits = [x[0] for x in sorted_hits[:5]]

    in_degree_dict = network.in_degree()
    sorted_in_degree = sorted(in_degree_dict.items(), key=operator.itemgetter(1), reverse=True)
    in_degree = [x[0] for x in sorted_in_degree[:5]]

    community_dict = []
    for k in xrange(20):
        community_dict += list(networkx.k_clique_communities(network.to_undirected(), 21 - k))
        if community_dict:
            break

    modules = []
    for index, community in enumerate(community_dict):
        modules.append([])
        for p in community:
            modules[index].append(p)

    statistics = {'in_degree': in_degree, 'betweenness': betweenness, 'hits': hits, 'pagerank': pagerank,
                  'modules': modules}

    with open(MAIN_FOLDER + "statistics.pkl", "wa") as f:
        pickle.dump(statistics, f)

    def recalculate(self):
    
    
        authorities = nx.hits(self.DG)[1]
        
        # Convert to log scale
        authorities_log = {}
        
        for user,value in authorities.items():
        
            v = value * 10**30
        
            if value > 0:
                v = math.log(v)
            else:
                v = 0
        
            authorities_log[user] = abs(int(v))
            
            
        # Normalise to 100
        authorities_norm = {}
        max_user = max(authorities_log.iteritems(), key=operator.itemgetter(1))[0]
        max_val = authorities_log[max_user]
        
        r = 100/float(max_val)
        
        for user,value in authorities_log.items():
            
            authorities_norm[user] = int(value*r)
 
        authorities_norm[max_user] = 100

        # Clear existing values
        
        sql = "UPDATE tracker_users set karma = 0"
        self.queryDB(sql, ())
        
        # Save values
        for user,karma in authorities_norm.items():
            sql = "UPDATE tracker_users SET karma = %s WHERE username = %s"
            self.queryDB(sql, (karma, user))

G.add_weighted_edges_from(links)


nx.draw_networkx(G, posNX, width = widths)
plt.pyplot.show()
plt.pyplot.savefig('flows.png')
out.close()


#nx.draw_networkx(G,pos, width = widths, alpha = .7 )
#plt.pyplot.show()
newPOS = []
for coords in iter(posIG):
    newPOS.append(posIG[coords])


betterGraph = ig.Graph(25, newLinks, directed = True)

betterGraph.es["width"] = widths

betterGraph.vs["label"] = range(25)

layout = newPOS

ig.plot(betterGraph, layout = layout, weighted =True)



hitsHubs, hitsAuths = nx.hits(G)[0].values(), nx.hits(G)[1].values()