def NetStats(G):
    return { 'radius': nx.radius(G),
             'diameter': nx.diameter(G),
             'connected_components': nx.number_connected_components(G),
             'density' : nx.density(G),
             'shortest_path_length': nx.shortest_path_length(G),
             'clustering': nx.clustering(G)}

def strongly_connected_components():
    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

    scompgraphs = nx.strongly_connected_component_subgraphs(G)
    scomponents = sorted(nx.strongly_connected_components(G), key=len, reverse=True)
    print 'components nodes distribution:', [len(c) for c in scomponents]
    
    #plot graph of component, calculate saverage_shortest_path_length of components who has over 1 nodes
    index = 0
    print 'average_shortest_path_length of components who has over 1 nodes:'
    for tempg in scompgraphs:
        index += 1
        if len(tempg.nodes()) != 1:
            print nx.average_shortest_path_length(tempg)
            print 'diameter', nx.diameter(tempg)
            print 'radius', nx.radius(tempg)
        pylab.figure(index)
        nx.draw_networkx(tempg)
        pylab.show()

    # Components-as-nodes Graph
    cG = nx.condensation(G)
    pylab.figure('Components-as-nodes Graph')
    nx.draw_networkx(cG)
    pylab.show()    

def print_graph_info(graph):
  e = nx.eccentricity(graph)
  print 'graph with %u nodes, %u edges' % (len(graph.nodes()), len(graph.edges()))
  print 'radius: %s' %  nx.radius(graph, e) # min e
  print 'diameter: %s' % nx.diameter(graph, e) # max e
  print 'len(center): %s' % len(nx.center(graph, e)) # e == radius
  print 'len(periphery): %s' % len(nx.periphery(graph, e)) # e == diameter

def calculate(network):
    try:
        n = nx.radius(network)
    except:
        return 0
 
    return round(n, 7) 

def netstats_simple(graph):
    G = graph
    if nx.is_connected(G): 
        d = nx.diameter(G)
        r = nx.radius(G)
    else: 
        d = 'NA - graph is not connected' #should be calculatable on unconnected graph - see example code for hack
        r = 'NA - graph is not connected'
   
#using dictionary to pack values and variablesdot, eps, ps, pdf break equally
    result = {#"""single value measures"""  
              'nn': G.number_of_nodes(),
              'ne': G.number_of_edges(),
              'd': d,
              'r': r,
              'conn': nx.number_connected_components(G),
              'asp': nx.average_shortest_path_length(G), 
#              """number of the largest clique"""
              'cn': nx.graph_clique_number(G),
#              """number of maximal cliques"""
              'mcn': nx.graph_number_of_cliques(G),
#              """transitivity - """
              'tr': nx.transitivity(G),
              #cc = nx.clustering(G) """clustering coefficient"""
              'avgcc': nx.average_clustering(G) } 
#    result['d'] = nx.diameter(G)
    print result
    return result

def NetStats(G,name):
    
    s=0
    d = nx.degree(G)    
    for i in d.values():
        s = s + i
    
    n = len(G.nodes())
    m = len(G.edges())
    k = float(s)/float(n)
    #k = nx.average_node_connectivity(G)
        
    C = nx.average_clustering(G)
    l = nx.average_shortest_path_length(G)
    Cc = nx.closeness_centrality(G)
    d = nx.diameter(G) #The diameter is the maximum eccentricity.
    r = nx.radius(G) #The radius is the minimum eccentricity.


    
    output = "ESTADISITICOS_"+name
    SALIDA = open(output,"w")
    
    SALIDA.write(("Numero de nodos n = %s \n") %  n)
    SALIDA.write(("Numero de aristas m = %s \n") %  m)
    SALIDA.write(("Grado promedio <k> = %s \n") %  k)
        
    SALIDA.write(("Clustering Coeficient = %s \n") %  C)
    SALIDA.write(("Shortest Path Length = %s \n") %  l)
    #SALIDA.write(("Closeness = %s \n") %  Cc)
    SALIDA.write(("Diameter (maximum eccentricity) = %d \n") %  d)
    SALIDA.write(("Radius (minimum eccentricity) = %d \n") %  r)

def get_tree_symmetries_for_traitset(model, simconfig, cultureid, traitset, culture_count_map):
    radii = []

    symstats = stats.BalancedTreeAutomorphismStatistics(simconfig)
    subgraph_set = model.trait_universe.get_trait_graph_components(traitset)
    trait_subgraph = model.trait_universe.get_trait_forest_from_traits(traitset)
    results = symstats.calculate_graph_symmetries(trait_subgraph)

    for subgraph in subgraph_set:
        radii.append( nx.radius(subgraph))

    mean_radii = np.mean(np.asarray(radii))
    sd_radii = np.sqrt(np.var(np.asarray(radii)))
    degrees = nx.degree(trait_subgraph).values()
    mean_degree = np.mean(np.asarray(degrees))
    sd_degree = np.sqrt(np.var(np.asarray(degrees)))
    mean_orbit_mult = np.mean(np.asarray(results['orbitcounts']))
    sd_orbit_mult = np.sqrt(np.var(np.asarray(results['orbitcounts'])))
    max_orbit_mult = np.nanmax(np.asarray(results['orbitcounts']))

    r = dict(cultureid=str(cultureid), culture_count=culture_count_map[cultureid],
             orbit_multiplicities=results['orbitcounts'],
             orbit_number=results['orbits'],
             autgroupsize=results['groupsize'],
             remaining_density=results['remainingdensity'],
             mean_radii=mean_radii,
             sd_radii=sd_radii,
             mean_degree=mean_degree,
             sd_degree=sd_degree,
             mean_orbit_multiplicity=mean_orbit_mult,
             sd_orbit_multiplicity=sd_orbit_mult,
             max_orbit_multiplicity=max_orbit_mult
             )
    #log.debug("groupstats: %s", r)
    return r

    def updateGraphStats(self, graph):

        origgraph = graph
        if nx.is_connected(graph):
            random = 0
        else:
            connectedcomp = nx.connected_component_subgraphs(graph)
            graph = max(connectedcomp)

        if len(graph) > 1:
            pathlength = nx.average_shortest_path_length(graph)
        else:
            pathlength = 0

        # print graph.nodes(), len(graph), nx.is_connected(graph)

        stats = {
            "radius": nx.radius(graph),
            "density": nx.density(graph),
            "nodecount": len(graph.nodes()),
            "center": nx.center(graph),
            "avgcluscoeff": nx.average_clustering(graph),
            "nodeconnectivity": nx.node_connectivity(graph),
            "components": nx.number_connected_components(graph),
            "avgpathlength": pathlength
        }

        # print "updated graph stats", stats
        return stats

def graph_radius(graph):
    sp = nx.shortest_path_length(graph,weight='weight')
    ecc = nx.eccentricity(graph,sp=sp)
    if ecc:
        rad = nx.radius(graph,e=ecc)
    else:
        rad = 0
    return rad

def test_radius(testgraph):
    """
    Testing radius function for graphs.
    """

    a, b = testgraph
    nx_rad = nx.radius(a)
    sg_rad = sg.digraph_distance_measures.radius(b, b.order())
    assert nx_rad == sg_rad

    def get_path_lengths(self):
        if not hasattr(self,"shortest_path_lenghts") or self.shortest_path_lenghts is None:
            self.shortest_paths_lengths = nx.all_pairs_shortest_path_length(self.G)
            self.avg_shortest_path = sum([ length for sp in self.shortest_paths_lengths.values() for length in sp.values() ])/float(self.N*(self.N-1))
            self.eccentricity = nx.eccentricity(self.G,sp=self.shortest_paths_lengths)
            self.diameter = nx.diameter(self.G,e=self.eccentricity)
            self.radius = nx.radius(self.G,e=self.eccentricity)

        return self.shortest_paths_lengths

def get_graph_info(graph):
    nodes = networkx.number_of_nodes(graph)
    edges = networkx.number_of_edges(graph)
    radius = networkx.radius(graph)
    diameter = networkx.diameter(graph)
    density = networkx.density(graph)
    average_clustering = networkx.average_clustering(graph)
    average_degree = sum(graph.degree().values()) / nodes
    return nodes, edges, radius, diameter, density, average_clustering, average_degree

 def connectivity(self):
     components = list(nx.connected_component_subgraphs(self.G))
     print('Connected components number: ')
     print(len(components))
     giant = components.pop(0)
     print('Giant component radius: ')
     print(nx.radius(giant))
     print('Giant component diameter: ')
     print(nx.diameter(giant))
     center = nx.center(giant)
     print('Giant component center: ')
     for i in xrange(len(center)):
         print(self.singer_dict[int(center[i])].split('|')[0])
     inf = self.get_graph_info(giant)
     for i in xrange(len(inf)):
         print(inf[i])

def write_graph(graph_name, g):
    radius = nx.radius(g)
    # https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.distance_measures.radius.html

    diameter = nx.diameter(g)
    # https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.distance_measures.diameter.html

    closeness = float(sum(nx.algorithms.centrality.closeness_centrality(g).values()))/size
    # https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.centrality.closeness_centrality.html#networkx.algorithms.centrality.closeness_centrality

    betweenness = float(sum(nx.algorithms.centrality.betweenness_centrality(g).values()))/size
    # https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality

    clustering = float(sum(nx.algorithms.clustering(g).values()))/size
    # https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.cluster.clustering.html#networkx.algorithms.cluster.clustering

    print "%s\t%s\t%s\t%s\t%s\t%s" % (graph_name, radius, diameter, closeness, betweenness, clustering)

    def PrintGraphStat(self):
        logging.debug("From SVNFileNetwork.PrintGraphStat")
        print "%s" % '-' * 40
        print "Graph Radius : %f" % NX.radius(self)
        print "Graph Diameter : %f" % NX.diameter(self)

        weighted = True
        closenessdict = NX.closeness_centrality(self, distance=weighted)
        print "%s" % '-' * 40
        print "All nodes in graph"

        nodeinfolist = [(node, closeness)
                        for node, closeness in closenessdict.items()]
        # sort the node infolist by closeness number
        nodeinfolist = sorted(
            nodeinfolist, key=operator.itemgetter(1), reverse=True)
        for node, closeness in nodeinfolist:
            print "\t%s : %f" % (node.name(), closeness)
        print "%s" % '-' * 40

def report_components(g):
	components = nx.connected_component_subgraphs(g)
	print "Components: %d" % len(components)
	c_data = {}
	for i in range(len(components)):
		c = components[i]
		if len(c.nodes()) > 5: # Avoid reporting on many small components
			c_data["nodes"] = len(c.nodes())
			c_data["edges"] = len(c.edges())
			c_data["avg_clustering"] = nx.average_clustering(c)
			c_data["diameter"] = nx.diameter(c)
			c_data["radius"] = nx.radius(c)
			c_data["center"] = len(nx.center(c))
			c_data["periphery"] = len(nx.periphery(c))

			print "* Component %d:" % i
			for k in c_data:
				print "--- %s: %s" % (k, c_data[k])

	return c_data

def distance_scores(season, graph):
    
    # Take largest connected component
    g = graph if nx.is_connected(graph) else max(nx.connected_component_subgraphs(graph), key=len)
    
    # Ratio of largest connected component subgraph
    conn = len(max(nx.connected_component_subgraphs(g), key=len)) / float(nx.number_of_nodes(graph))
    conn = np.round(conn, 3)
    
    # Radius, diameter
    rad = nx.radius(g)
    diam = nx.diameter(g)
    
    # Average eccentricity
    ecc = np.mean(nx.eccentricity(g).values())
    ecc = np.round(ecc, 3)
    
    # Put it all into a dataframe
    df = pd.DataFrame([[season,conn,rad,diam,ecc]], columns=['season', 'conn', 'rad', 'diam', 'ecc'])
    
    return df

    def getMetrics(self, layerid=0):
        # get some overall network metrics
        undirectedG = self.layergraphs[layerid].to_undirected()
        metrics = {}

        try:  # must be connected
            metrics['diameter'] = nx.diameter(undirectedG)
            metrics['radius'] = nx.radius(undirectedG)
            metrics['average_clustering'] = round(nx.average_clustering(undirectedG),3)
            metrics['transitivity'] = round(nx.transitivity(undirectedG),3)
            metrics['number_connected_components'] = nx.number_connected_components(undirectedG)

            import operator
            betweenness_centrality = nx.betweenness_centrality(self.layergraphs[layerid])
            metrics['betweenness_centrality'] = sorted(betweenness_centrality.iteritems(),key=operator.itemgetter(1),reverse=True)[0][0] # find node with largest betweenness centrality

            H = nx.connected_component_subgraphs(undirectedG)[0] # largest connected component
            metrics['number_of_nodes'] = len(H.nodes())
        except:
            pass

        return metrics

 def __init__(self, graph, feature_list=[]):
     self.no_feature = 39
     self.G = graph
     self.nodes = nx.number_of_nodes(self.G)
     self.edges = nx.number_of_edges(self.G)
     self.Lap = nx.normalized_laplacian_matrix(self.G)
     # ??? how to check whether comparable, addable?
     self.eigvals = numpy.linalg.eigvals(self.Lap.A).tolist()
     try:
         self.radius = nx.radius(self.G)
     except nx.exception.NetworkXError:
         self.radius = "ND"
     try:
         self.ecc_dic = nx.eccentricity(self.G)
     except nx.exception.NetworkXError:
         self.ecc_dic = {}
     self.degree_dic = nx.average_neighbor_degree(self.G)
     self.pagerank = nx.pagerank(self.G).values()
     if feature_list == []:
         self.feature_list = list(range(1, self.no_feature + 1))
     else:
         self.feature_list = feature_list
     self.feature_vector = []
     self.feature_time = []

def extended_stats(G, connectivity=False, anc=False, ecc=False, bc=False, cc=False):
    """
    Calculate extended topological stats and metrics for a graph.

    Many of these algorithms have an inherently high time complexity. Global
    topological analysis of large complex networks is extremely time consuming
    and may exhaust computer memory. Consider using function arguments to not
    run metrics that require computation of a full matrix of paths if they
    will not be needed.

    Parameters
    ----------
    G : networkx multidigraph
    connectivity : bool
        if True, calculate node and edge connectivity
    anc : bool
        if True, calculate average node connectivity
    ecc : bool
        if True, calculate shortest paths, eccentricity, and topological metrics
        that use eccentricity
    bc : bool
        if True, calculate node betweenness centrality
    cc : bool
        if True, calculate node closeness centrality

    Returns
    -------
    stats : dict
        dictionary of network measures containing the following elements (some
        only calculated/returned optionally, based on passed parameters):

          - avg_neighbor_degree
          - avg_neighbor_degree_avg
          - avg_weighted_neighbor_degree
          - avg_weighted_neighbor_degree_avg
          - degree_centrality
          - degree_centrality_avg
          - clustering_coefficient
          - clustering_coefficient_avg
          - clustering_coefficient_weighted
          - clustering_coefficient_weighted_avg
          - pagerank
          - pagerank_max_node
          - pagerank_max
          - pagerank_min_node
          - pagerank_min
          - node_connectivity
          - node_connectivity_avg
          - edge_connectivity
          - eccentricity
          - diameter
          - radius
          - center
          - periphery
          - closeness_centrality
          - closeness_centrality_avg
          - betweenness_centrality
          - betweenness_centrality_avg

    """

    stats = {}
    full_start_time = time.time()

    # create a DiGraph from the MultiDiGraph, for those metrics that require it
    G_dir = nx.DiGraph(G)

    # create an undirected Graph from the MultiDiGraph, for those metrics that
    # require it
    G_undir = nx.Graph(G)

    # get the largest strongly connected component, for those metrics that
    # require strongly connected graphs
    G_strong = get_largest_component(G, strongly=True)

    # average degree of the neighborhood of each node, and average for the graph
    avg_neighbor_degree = nx.average_neighbor_degree(G)
    stats['avg_neighbor_degree'] = avg_neighbor_degree
    stats['avg_neighbor_degree_avg'] = sum(avg_neighbor_degree.values())/len(avg_neighbor_degree)

    # average weighted degree of the neighborhood of each node, and average for
    # the graph
    avg_weighted_neighbor_degree = nx.average_neighbor_degree(G, weight='length')
    stats['avg_weighted_neighbor_degree'] = avg_weighted_neighbor_degree
    stats['avg_weighted_neighbor_degree_avg'] = sum(avg_weighted_neighbor_degree.values())/len(avg_weighted_neighbor_degree)

    # degree centrality for a node is the fraction of nodes it is connected to
    degree_centrality = nx.degree_centrality(G)
    stats['degree_centrality'] = degree_centrality
    stats['degree_centrality_avg'] = sum(degree_centrality.values())/len(degree_centrality)

    # calculate clustering coefficient for the nodes
    stats['clustering_coefficient'] = nx.clustering(G_undir)

    # average clustering coefficient for the graph
    stats['clustering_coefficient_avg'] = nx.average_clustering(G_undir)

    # calculate weighted clustering coefficient for the nodes
    stats['clustering_coefficient_weighted'] = nx.clustering(G_undir, weight='length')

#.........这里部分代码省略.........