Connected components on directed graphs

[Drew Conway]

I am attempting to count the number of connected components for both Graph and DiGraph objects, but am running into the Graph only restriction in the component algorithms.  From looking at the code, I cannot understand why this restriction is in place?  I do not *think* the use of single_source_shortest_path_length to count component node sets will be affected by directed graphs.

I am probably overlooking something obvious, but wanted to ask before i try to engineer [jig up] my own solution.

___________________________________

Drew Conway

Ph.D. Student

Department of Politics, New York University

drew....@nyu.edu

http://www.drewconway.com/

@drewconway

[Christopher Ellison]

Drew Conway wrote the following on 09/13/2010 05:11 PM:
> I am attempting to count the number of connected components for both
> Graph and DiGraph objects, but am running into the Graph only
> restriction in the component algorithms. From looking at the code, I
> cannot understand why this restriction is in place? I do not *think* the
> use of single_source_shortest_path_length to count component node sets
> will be affected by directed graphs.
>
> I am probably overlooking something obvious, but wanted to ask before i
> try to engineer [jig up] my own solution.
>

Have you looked at:

weakly_connected_components
strongly_connected_components

These are for directed graphs.

Chris

[Drew Conway]

I did, they still contain the restriction.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[Drew Conway]

Chris,

Sorry, I see what you mean now. Thanks for the tip!

- Drew

On Sep 13, 2010, at 8:29 PM, Christopher Ellison wrote:

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[David M. Gyurko, MD]

Hi,

Connected component and strongly/weakly connected component methods in networkx are not interchangeable. The two network theoretical concepts are different and networkx rightfully differentiates them.

The connected component problem with (multi)digraphs can be solved by
(1) creating first az undirected graph,
(2) getting the components, then
(3) creating digraphs from the edgelist of the undirected components.

Directed graph from the largest connected component (python):

ug = nx.Graph()
ug.add_edges_from(edgetable) # undirected global graph; edgetable is just a list of A->B, A->C, C->D etc.
# largest connected component
 if nx.number_connected_components(ug)>1:
    lcug = nx.connected_component_subgraphs(ug)[0]
else:
    lcug = ug
del ug
           
dg = nx.DiGraph()
dg.add_edges_from(lcug.edges()) # directed global graph from the largest connected component

IMPORTANT NOTE: G.to_directed() creates edges A->B, B->A from A-B! Don't use it if you want the undirected and directed components to be similar (only difference is the directedness).
G.subgraph() operations could work, but are slower compared to the above solution.

It is an old discussion yet the solution may help someone in the future. :)