python类strongly_connected_component_subgraphs()的实例源码

def find_SCCs(mdp, Sneg):
    #----simply find strongly connected components----
    print 'Remaining states size', len(Sneg)
    SCC  = set()
    simple_digraph = DiGraph()
    A = dict()
    for s in mdp.nodes():
        A[s] = mdp.node[s]['act'].copy()
    for s_f in Sneg:
        if s_f not in simple_digraph:
            simple_digraph.add_node(s_f)
        for s_t in mdp.successors_iter(s_f):
            if s_t in Sneg:
                simple_digraph.add_edge(s_f,s_t)
    print "SubGraph of one Sf: %s states and %s edges" %(str(len(simple_digraph.nodes())), str(len(simple_digraph.edges())))
    sccs = strongly_connected_component_subgraphs(simple_digraph)
    for scc in sccs:
        SCC.add(frozenset(scc.nodes()))    
    return SCC, A

def __condensation(self):
        """Produces condensation of cyclic graphs."""
        subgraphs = nx.strongly_connected_component_subgraphs(self.digraph)
        for subgraph in list(subgraphs):
            if subgraph.number_of_nodes() == 1:
                continue  # not a cycle
            pre_edges = []
            suc_edges = []
            for node in subgraph:
                assert node not in self.node2cycle
                assert node in self.digraph  # no accidental copying
                self.node2cycle[node] = subgraph
                for pre_node in self.digraph.predecessors(node):
                    if not subgraph.has_node(pre_node):
                        pre_edges.append((pre_node, node))
                        self.digraph.add_edge(pre_node, subgraph)
                for suc_node in self.digraph.successors(node):
                    if not subgraph.has_node(suc_node):
                        suc_edges.append((node, suc_node))
                        self.digraph.add_edge(subgraph, suc_node)
                self.digraph.remove_node(node)
            assert subgraph not in self.cycles
            self.cycles[subgraph] = (pre_edges, suc_edges)

        cycle_order = lambda x: min(str(u) for u in x)
        for index, cycle in enumerate(sorted(self.cycles, key=cycle_order)):
            self.cycle2index[cycle] = index

    # pylint: disable=invalid-name

def get_largest_component(G, strongly=False):
    """
    Return the largest weakly or strongly connected component from a directed
    graph.

    Parameters
    ----------
    G : networkx multidigraph
    strongly : bool
        if True, return the largest strongly instead of weakly connected
        component

    Returns
    -------
    networkx multidigraph
    """

    start_time = time.time()
    original_len = len(list(G.nodes()))

    if strongly:
        # if the graph is not connected and caller did not request retain_all,
        # retain only the largest strongly connected component
        if not nx.is_strongly_connected(G):
            G = max(nx.strongly_connected_component_subgraphs(G), key=len)
            msg = ('Graph was not connected, retained only the largest strongly '
                   'connected component ({:,} of {:,} total nodes) in {:.2f} seconds')
            log(msg.format(len(list(G.nodes())), original_len, time.time()-start_time))
    else:
        # if the graph is not connected and caller did not request retain_all,
        # retain only the largest weakly connected component
        if not nx.is_weakly_connected(G):
            G = max(nx.weakly_connected_component_subgraphs(G), key=len)
            msg = ('Graph was not connected, retained only the largest weakly '
                   'connected component ({:,} of {:,} total nodes) in {:.2f} seconds')
            log(msg.format(len(list(G.nodes())), original_len, time.time()-start_time))

    return G

def filter_big_scc(g,edges_to_be_removed):
    #Given a graph g and edges to be removed
    #Return a list of big scc subgraphs (# of nodes >= 2)
    g.remove_edges_from(edges_to_be_removed)
    sub_graphs = filter(lambda scc: scc.number_of_nodes() >= 2, nx.strongly_connected_component_subgraphs(g))
    return sub_graphs

def get_big_sccs(g):
    self_loop_edges = g.selfloop_edges()
    g.remove_edges_from(g.selfloop_edges())
    num_big_sccs = 0
    edges_to_be_removed = []
    big_sccs = []
    for sub in nx.strongly_connected_component_subgraphs(g):
        number_of_nodes = sub.number_of_nodes()
        if number_of_nodes >= 2:
            # strongly connected components
            num_big_sccs += 1
            big_sccs.append(sub)
    #print(" # big sccs: %d" % (num_big_sccs))
    return big_sccs

def scc_nodes_edges(g):
    scc_nodes = set()
    scc_edges = set()
    num_big_sccs = 0
    num_nodes_biggest_scc = 0
    biggest_scc = None
    for sub in nx.strongly_connected_component_subgraphs(g):
        number_nodes = sub.number_of_nodes()
        if number_nodes >= 2:
            scc_nodes.update(sub.nodes_iter())
            scc_edges.update(sub.edges_iter())
            num_big_sccs += 1
            if num_nodes_biggest_scc < number_nodes:
                num_nodes_biggest_scc = number_nodes
                biggest_scc = sub
    nonscc_nodes = set(g.nodes()) - scc_nodes
    nonscc_edges = set(g.edges()) - scc_edges
    print num_nodes_biggest_scc
    print("num of big sccs: %d" % num_big_sccs)
    if biggest_scc == None:
        return scc_nodes,scc_nodes,nonscc_nodes,nonscc_edges
    print("# nodes in biggest scc: %d, # edges in biggest scc: %d" % (biggest_scc.number_of_nodes(),biggest_scc.number_of_edges()))
    print("# nodes,edges in scc: (%d,%d), # nodes, edges in non-scc: (%d,%d) " % (len(scc_nodes),len(scc_edges),len(nonscc_nodes),len(nonscc_edges)))
    num_of_nodes = g.number_of_nodes()
    num_of_edges = g.number_of_edges()
    print("# nodes in graph: %d, # of edges in graph: %d, percentage nodes, edges in scc: (%0.4f,%0.4f), percentage nodes, edges in non-scc: (%0.4f,%0.4f)" % (num_of_nodes,num_of_edges,len(scc_nodes)*1.0/num_of_nodes,len(scc_edges)*1.0/num_of_edges,len(nonscc_nodes)*1.0/num_of_nodes,len(nonscc_edges)*1.0/num_of_edges))
    return scc_nodes,scc_edges,nonscc_nodes,nonscc_edges

def graph_info(g):
    result = {}
    components = list(nx.strongly_connected_component_subgraphs(g))
    in_degrees = g.in_degree()
    out_degrees = g.out_degree()
    highest_in_degree_node = sorted(in_degrees, key = lambda x: in_degrees[x], reverse = True)[0]
    highest_out_degree_node = sorted(out_degrees, key = lambda x: out_degrees[x], reverse = True)[0]

    result['highest in_degree node'] = highest_in_degree_node
    result['highest out_degree_node'] = highest_out_degree_node

    result['numnber of components'] = len(components)
    result['number of nodes'] = g.number_of_nodes()
    result['number of edges'] = g.number_of_edges()
#Degree centrality
    in_degree_centrality = nx.in_degree_centrality(g)
    out_degree_centrality = nx.out_degree_centrality(g)
    result['sorted in_degree centrality'] = sorted([(el,in_degree_centrality[el]) for el in g.nodes()], key = lambda x: x[1], reverse = True)
    result['sorted out_degree centrality'] = sorted([(el,out_degree_centrality[el]) for el in g.nodes()], key = lambda x: x[1], reverse = True)

    result['closeness_centrality'] = sorted([(el,nx.closeness_centrality(g)[el]) for el in nx.closeness_centrality(g)], key = lambda x: x[1], reverse = True)
    result['highest in_degree node closeness'] = nx.closeness_centrality(g)[highest_in_degree_node]
    result['highest out_degree node closeness'] = nx.closeness_centrality(g)[highest_out_degree_node]


    result['betweenness centrality'] = sorted([(el,nx.betweenness_centrality(g)[el]) for el in nx.betweenness_centrality(g)], key = lambda x: x[1], reverse = True)
    result['highest in_degree node betweenness'] = nx.betweenness_centrality(g)[highest_in_degree_node]
    result['highest in_degree node betweenness'] = nx.betweenness_centrality(g)[highest_out_degree_node]


    largest_component = sorted (components, key = lambda x: x.number_of_nodes(), reverse = True)[0]

    result['largest strongly component percent'] = largest_component.number_of_nodes()/float(g.number_of_nodes())
    result['largest strongly component diameter'] = nx.diameter(largest_component)
    result['largest strongly component average path length'] = nx.average_shortest_path_length(largest_component)
    result['average_degree (undireceted)'] = sum(g.degree().values())/float(g.number_of_nodes())
    result['avg_cluster_coefficient (transitivity)'] = nx.transitivity(g)
    return result