Come posso ottenere il componente gigante di un grafico NetworkX?

non so se NetworkX di recente ottimizzato uno dei metodi per essere un generatore invece di restituire una lista, ma sto cercando un buon modo (anzi, meglio) per ottenere il GC di un grafico.Come posso ottenere il componente gigante di un grafico NetworkX?

ho un lavoro, ma in realtà inefficiente dall'aspetto, giù Snippet:

# G = nx.Graph() 
giant = sorted(nx.connected_component_subgraphs(G), key=len, reverse=True)[0]

C'è un modo più pulito?

fonte

2014-09-29 Nick T

In NetworkX 1.9, connected_components_subgraphs restituisce un iteratore (invece di un elenco ordinato). I valori forniti dall'iteratore sono not in sorted order. Quindi, per trovare la più grande, utilizzare max:

giant = max(nx.connected_component_subgraphs(G), key=len)

ordinamento è O (n log n). Il massimo è O (n).

fonte

2014-09-29 17:50:19 unutbu

Non sapevo che si potesse usare un argomento 'key' con' max', interessante ... Il metodo 'connected_component_subgraphs' è il metodo migliore da usare all'interno di NX? –

Sì. Questo è il modo [consigliato dallo sviluppatore principale del NetworkX] (http://stackoverflow.com/a/24378179/190597). – unutbu

Sarebbe possibile ordinare 'nx.connected_component_subgraphs()' per non identificare la componente più importante, ma * tutti * di loro? Ordinandolo potremmo ritrovarci con uno ** snippet inefficiente ** come indicato dall'OP. C'è qualche soluzione, soprattutto per il caso di ** reti enormi **? – FaCoffee

Come posso ottenere il componente gigante di un grafico NetworkX?

risposta

Problemi correlati