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 attracting_components(G):
    """Returns a list of attracting components in `G`.

    An attracting component in a directed graph `G` is a strongly connected
    component with the property that a random walker on the graph will never
    leave the component, once it enters the component.

    The nodes in attracting components can also be thought of as recurrent
    nodes.  If a random walker enters the attractor containing the node, then
    the node will be visited infinitely often.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    attractors : list
        The list of attracting components, sorted from largest attracting
        component to smallest attracting component.

    See Also
    --------
    number_attracting_components
    is_attracting_component 
    attracting_component_subgraphs

    """
    scc = nx.strongly_connected_components(G)
    cG = nx.condensation(G, scc)
    attractors = [scc[n] for n in cG if cG.out_degree(n) == 0]
    attractors.sort(key=len,reverse=True)
    return attractors

def get_graph_compressed(graph_data):
    """
    Getting the Compressed Graph. A Compressed Graph is a DAG, after removing
    unreachable graph nodes, and getting bfs tree.
    """
    # Creating the directed graphs, for graph1.
    dgraph = nx.DiGraph(graph_data)
    if not dgraph.has_node(0):  # adding root node, on one node case.
        dgraph.add_node(0)
    # First, remove non reachable nodes, from the root.
    # assuming node 0 is the function root node.
    bfsy = nx.bfs_tree(dgraph, 0).nodes()
    if 0 not in bfsy:
        bfsy.append(0)
    for i in dgraph.nodes():
        if i not in bfsy:
            dgraph.remove_node(i)

    # Second, _collapse some vertices together...
    dgraph = _collapse(dgraph)

    # create DAG's (computing scc) from digraph before.
    compressed_graph = nx.condensation(dgraph)

    return compressed_graph.edges()

 def test_contract_scc2(self):
     # Bug found and fixed in [1687].
     G = nx.DiGraph()
     G.add_edge(1,2)
     G.add_edge(2,1)
     cG = nx.condensation(G)
     assert_true((1,2) in cG)

 def test_null_graph(self):
     G = nx.DiGraph()
     assert_equal(list(nx.strongly_connected_components(G)), [])
     assert_equal(list(nx.kosaraju_strongly_connected_components(G)), [])
     assert_equal(list(nx.strongly_connected_components_recursive(G)), [])
     assert_equal(len(nx.condensation(G)), 0)
     assert_raises(nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph())

def attracting_components(G):
    """Generates a list of attracting components in `G`.

    An attracting component in a directed graph `G` is a strongly connected
    component with the property that a random walker on the graph will never
    leave the component, once it enters the component.

    The nodes in attracting components can also be thought of as recurrent
    nodes.  If a random walker enters the attractor containing the node, then
    the node will be visited infinitely often.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    attractors : generator of sets
        A generator of sets of nodes, one for each attracting component of G.

    See Also
    --------
    number_attracting_components
    is_attracting_component 
    attracting_component_subgraphs

    """
    scc = list(nx.strongly_connected_components(G))
    cG = nx.condensation(G, scc)
    for n in cG:
        if cG.out_degree(n) == 0:
            yield scc[n]

    def _create_spatial_index(self):
        G = nx.condensation(self.G)  # convert to DAG
        index = dict()
        # Add 1 hop reachability for a DAG
        for v in G.nodes():  # for each component
            for w in G.node[v]['members']:  # for each node in the component
                if 'spatial' in self.G.node[w]:  # is 'w' a spatial node?
                    index.upsert(v, {self.region(w)})  # if yes, add block # of 'w' to v's meta

        # Add multi hop reachability
        self._do_dfs(G, index)
        # Update reachability information to each node in the component
        for v in G.nodes():  # for each component
            for w in G.node[v]['members']:  # for each node in the component
                try:
                    self.spatial_index[w] = index[v]  # set component's index entry to each vertex in it
                except KeyError:
                    pass  # ignore if index entry is not found as they don't have any spatial connections

        # free up space
        G = None
        index = None
        gc.collect(0)

        # Create region based index
        c = count()
        for v in self.G.nodes():
            if 'spatial' in self.G.node[v]:
                x = self.G.node[v]['spatial']['lng']
                y = self.G.node[v]['spatial']['lat']
                self.region_index.insert(next(c), (x, y, x, y), v)

def condensation_plus(G):
	C = nx.condensation(G)
	maps = {}
	maps = C.graph['mapping']

	num_of_c = C.number_of_nodes();
	nbunch = {}
	for num in range(0,num_of_c):
		nbunch[num] = []

	#search through and divide G.nodes() into groups
	for num in range(0,num_of_c):
		for name in G.nodes():
			if maps[name]==num:
				nbunch[num].append(name)

	G_sub = {};

	for i in range(0, num_of_c):
		G_sub[i] = G.subgraph(nbunch[i])

	result = [];
	result.append(C);
	result.append(G_sub);

	return result

 def test_contract_scc_isolate(self):
     # Bug found and fixed in [1687].
     G = nx.DiGraph()
     G.add_edge(1, 2)
     G.add_edge(2, 1)
     scc = list(nx.strongly_connected_components(G))
     cG = nx.condensation(G, scc)
     assert_equal(list(cG.nodes()), [0])
     assert_equal(list(cG.edges()), [])

 def test_condensation_mapping_and_members(self):
     G, C = self.gc[1]
     cG = nx.condensation(G)
     mapping = cG.graph['mapping']
     assert_true(all(n in G for n in mapping))
     assert_true(all(0 == cN for n, cN in mapping.items() if n in C[0]))
     assert_true(all(1 == cN for n, cN in mapping.items() if n in C[1]))
     for n, d in cG.nodes(data=True):
         assert_equal(C[n], cG.node[n]['members'])

 def test_condensation_mapping_and_members(self):
     G, C = self.gc[1]
     C = sorted(C, key=len, reverse=True)
     cG = nx.condensation(G)
     mapping = cG.graph["mapping"]
     assert_true(all(n in G for n in mapping))
     assert_true(all(0 == cN for n, cN in mapping.items() if n in C[0]))
     assert_true(all(1 == cN for n, cN in mapping.items() if n in C[1]))
     for n, d in cG.nodes(data=True):
         assert_equal(set(C[n]), cG.node[n]["members"])

 def condensation(self):
     if DEBUG_FLAG:
         print "self.dep_graph.number_of_nodes()", self.dep_graph.number_of_nodes()
     c0 = nx.condensation(self.dep_graph)
     for cnode in c0.nodes():
         stratum_atoms = c0.node[cnode]['members']
         rules = []
         for atom in stratum_atoms:
             for rule in self.head2rules[atom]:
                 rules.append(rule)
         c0.node[cnode]['stratum'] = Stratum(stratum_atoms, rules)
     return c0

def condensation_nx( G, components) :
	"""
	G : DiGraph object. the nx.DiGraph attribute is extracted from this.

	components : 	Given components C_1 .. C_k which partition the nodes of G, the
	condensation graph cG has nodes <C_1> .. <C_k> and has edge
	(<C_i>,<C_j>) iff there was an edge in G from a node in C_i to a
	node in C_j.
	"""
	cG = DiGraph()
	cG.graph = nx.condensation( G.graph, components )
	return cG

def is_semiconnected(G):
    """Return True if the graph is semiconnected, False otherwise.

    A graph is semiconnected if, and only if, for any pair of nodes, either one
    is reachable from the other, or they are mutually reachable.

    Parameters
    ----------
    G : NetworkX graph
        A directed graph.

    Returns
    -------
    semiconnected : bool
        True if the graph is semiconnected, False otherwise.

    Raises
    ------
    NetworkXNotImplemented :
        If the input graph is undirected.

    NetworkXPointlessConcept :
        If the graph is empty.

    Examples
    --------
    >>> G=nx.path_graph(4,create_using=nx.DiGraph())
    >>> print(nx.is_semiconnected(G))
    True
    >>> G=nx.DiGraph([(1, 2), (3, 2)])
    >>> print(nx.is_semiconnected(G))
    False

    See Also
    --------
    is_strongly_connected
    is_weakly_connected
    is_connected
    is_biconnected
    """
    if len(G) == 0:
        raise nx.NetworkXPointlessConcept(
            'Connectivity is undefined for the null graph.')

    if not nx.is_weakly_connected(G):
        return False

    G = nx.condensation(G)
    path = nx.topological_sort(G)
    return all(G.has_edge(u, v) for u, v in pairwise(path))

 def test_contract_scc_edge(self):
     G = nx.DiGraph()
     G.add_edge(1, 2)
     G.add_edge(2, 1)
     G.add_edge(2, 3)
     G.add_edge(3, 4)
     G.add_edge(4, 3)
     scc = list(nx.strongly_connected_components(G))
     cG = nx.condensation(G, scc)
     assert_equal(sorted(cG.nodes()), [0, 1])
     if 1 in scc[0]:
         edge = (0, 1)
     else:
         edge = (1, 0)
     assert_equal(list(cG.edges()), [edge])

def build_analog_integration_blks(component):
    # Build the original dependance graph:
    graph = VisitorFindDirectSymbolDependance.build_direct_dependancy_graph(component)

    # Also, add in the RT graphs, that aren't direct dependents of anything, so
    # that the aprpriate AnalogIntegrationBlocks are created. (This might
    # emit events, but nothing else for example)
    for rt_graph in component.rt_graphs:
        if not rt_graph in graph:
            graph.add_node(rt_graph, label=repr(rt_graph), color='grey')


    # Plot:
    do_plot = True and False
    if do_plot:
        plot_networkx_graph(graph, show=False)
        plt.show()

    # Get the strongly connected components, and the dependancies between the
    # nodes:
    scc = nx.strongly_connected_components(graph)
    cond = nx.condensation(graph, scc=scc)


    #for node, node_data in cond.nodes_iter(data=True):
    #    print node, node_data


    ordering = reversed( nx.topological_sort(cond) )
    blks = []
    for o in ordering:
        objs = set(scc[0])
        blk_deps = set()
        for obj in scc[o]:
            o_deps = set(graph.successors(obj)) - objs
            blk_deps |= o_deps

        print blk_deps
        blk_deps = blk_deps - set(scc[o])
        blk = AnalogIntegrationBlock( objs = scc[o], dependancies=blk_deps )
        blks.append(blk)



    return blks

 def test_contract_scc1(self):
     G = nx.DiGraph()
     G.add_edges_from([(1,2),(2,3),(2,11),(2,12),(3,4),(4,3),(4,5),
                       (5,6),(6,5),(6,7),(7,8),(7,9),(7,10),(8,9),
                       (9,7),(10,6),(11,2),(11,4),(11,6),(12,6),(12,11)])
     cG = nx.condensation(G)
     # nodes
     assert_true((1,) in cG)
     assert_true((2,11,12) in cG)
     assert_true((3,4) in cG)
     assert_true((5,6,7,8,9,10) in cG)
     assert_true((2,11,12) in cG[(1,)])
     # edges
     assert_true((3,4) in cG[(2,11,12)])
     assert_true((5,6,7,8,9,10) in cG[(2,11,12)])
     assert_true((5,6,7,8,9,10) in cG[(3,4)])
     # DAG
     assert_true(nx.is_directed_acyclic_graph(cG))

 def test_contract_scc1(self):
     G = nx.DiGraph()
     G.add_edges_from(
         [
             (1, 2),
             (2, 3),
             (2, 11),
             (2, 12),
             (3, 4),
             (4, 3),
             (4, 5),
             (5, 6),
             (6, 5),
             (6, 7),
             (7, 8),
             (7, 9),
             (7, 10),
             (8, 9),
             (9, 7),
             (10, 6),
             (11, 2),
             (11, 4),
             (11, 6),
             (12, 6),
             (12, 11),
         ]
     )
     scc = list(nx.strongly_connected_components(G))
     cG = nx.condensation(G, scc)
     # DAG
     assert_true(nx.is_directed_acyclic_graph(cG))
     # nodes
     assert_equal(sorted(cG.nodes()), [0, 1, 2, 3])
     # edges
     mapping = {}
     for i, component in enumerate(scc):
         for n in component:
             mapping[n] = i
     edge = (mapping[2], mapping[3])
     assert_true(cG.has_edge(*edge))
     edge = (mapping[2], mapping[5])
     assert_true(cG.has_edge(*edge))
     edge = (mapping[3], mapping[5])
     assert_true(cG.has_edge(*edge))

    def test_condensation_as_quotient(self):
        """This tests that the condensation of a graph can be viewed as the
        quotient graph under the "in the same connected component" equivalence
        relation.

        """
        # This example graph comes from the file `test_strongly_connected.py`.
        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (2, 11), (2, 12), (3, 4), (4, 3),
                          (4, 5), (5, 6), (6, 5), (6, 7), (7, 8), (7, 9),
                          (7, 10), (8, 9), (9, 7), (10, 6), (11, 2), (11, 4),
                          (11, 6), (12, 6), (12, 11)])
        scc = list(nx.strongly_connected_components(G))
        C = nx.condensation(G, scc)
        component_of = C.graph['mapping']
        # Two nodes are equivalent if they are in the same connected component.
        same_component = lambda u, v: component_of[u] == component_of[v]
        Q = nx.quotient_graph(G, same_component)
        assert_true(nx.is_isomorphic(C, Q))

def from_NXgraph(Graph, fname, verbose):
    if not fname[-4:]=='.gml':
        fname+='.gml'
    print 'Creating',fname+'..'
    
    attr = GraphTheory.attributes_components(Graph, verbose)
    NX.set_node_attributes(Graph, 'node_type', attr)
    attr = GraphTheory.attributes_interactions(Graph, verbose)
    NX.set_edge_attributes(Graph, 'edge_type', attr)
    
    sccs = NX.strongly_connected_components(Graph)
    condensation = NX.condensation(Graph, sccs)
    layout = NX.spring_layout(condensation, iterations=100, scale=1000)
    attr = {}
    
    for i,scc in enumerate(sccs):
        for node in scc:
            attr[node] = {'x':layout[i][0],'y':layout[i][1]}

    NX.set_node_attributes(Graph, 'graphics', attr)
    NX.write_gml(Graph, fname)