我们从Python开源项目中，提取了以下7个代码示例，用于说明如何使用networkx.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
