How to get all disconnected subgraphs?

[Peter Bočan]

Hello guys, 

I have an issue that I cant deal with by myself, so I am asking you, as experienced with this library. I have a DiGraph G, which consists of many disconnected digraphs (some of them have cycles) and I want those directed subgraphs separated and put into an array. I tried this code but it does not work, because I get from 18000 nodes of G, to 18000 subgraphs... no idea why though. 

def get_directed_component_subgraphs(G):
    """
        Find disconnected subgraphs from original graph and add them to one array
    """
    subgraphs = []
    undirected = G.to_undirected()

    for node in G.nodes():
        copy = G.subgraph(nx.shortest_path(undirected, node)).copy()
        G.remove_nodes_from(copy.nodes())
        subgraphs.append(copy)
        print len(G), '\n'

    return subgraphs

Any idea? 
Thanks. 

[Dmitry Zinoviev]

You must be looking for nx.connected_components or nx.connected_component_subgraphs (they actually do the same thing, but return either graphs themselves or node lists).

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

--

Dmitry Zinoviev, Author of "Data Science Essentials in Python" 

https://pragprog.com/book/dzpyds/data-science-essentials-in-python
Professor of Computer Science, Suffolk University, Boston, MA 02114

[Peter Bočan]

Well, I will need directed subgraph for every disconnected component that so that I can "morph" them into stars. 

Dňa piatok, 18. augusta 2017 21:59:29 UTC+2 Dmitry Zinoviev napísal(-a):

You must be looking for nx.connected_components or nx.connected_component_subgraphs (they actually do the same thing, but return either graphs themselves or node lists).

On Fri, Aug 18, 2017 at 2:07 PM, Peter Bočan <peppy...@gmail.com> wrote:

Hello guys, 

I have an issue that I cant deal with by myself, so I am asking you, as experienced with this library. I have a DiGraph G, which consists of many disconnected digraphs (some of them have cycles) and I want those directed subgraphs separated and put into an array. I tried this code but it does not work, because I get from 18000 nodes of G, to 18000 subgraphs... no idea why though. 

def get_directed_component_subgraphs(G):
    """
        Find disconnected subgraphs from original graph and add them to one array
    """
    subgraphs = []
    undirected = G.to_undirected()

    for node in G.nodes():
        copy = G.subgraph(nx.shortest_path(undirected, node)).copy()
        G.remove_nodes_from(copy.nodes())
        subgraphs.append(copy)
        print len(G), '\n'

    return subgraphs

Any idea? 
Thanks. 

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.

Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Aric Hagberg]

Perhaps you are looking for networkx.weakly_connected_component_subgraphs()?

That should get you a list of directed subgraphs (example below, no need to sort if you don't want them ordered).

Examples

--------

Generate a sorted list of weakly connected components, largest first.

>>> G = nx.path_graph(4, create_using=nx.DiGraph())

>>> nx.add_path(G, [10, 11, 12])

>>> [len(c) for c in sorted(nx.weakly_connected_component_subgraphs(G),

...                         key=len, reverse=True)]

[4, 3]

Aric

[Peter Bočan]

Yeah, that looks promising. Thanks guys ! 

Dňa sobota, 19. augusta 2017 1:17:38 UTC+2 Aric Hagberg napísal(-a):