How to find subgraphs in a directed graph without converting to undirected graph?

Question

I have a graph that has many subgraphs. I have some edges that connect two nodes in both directions, that is, A-->B and B-->A. The bidirectionality is important, as it represents a lack of knowledge on our part as to whether A goes to B or B goes to A, and we have no easy way of determining which is the correct one.

I'd like to know how many subgraphs there are, and output to a Pandas DataFrame the edges in each subgraph. However, NetworkX only takes in undirected graphs in the provided connected_components_subgraph(G) function. When I convert the graph to an undirected graph, I can use connected_components_subgraph() to get the nodes in each edge, but I lose edge directionality.

Is there an easy way to do what I'm trying to achieve?

Anteater

Are there cycles in your graph? Such that A --> B (--> X) --> A? – Yesima

Yes, there are cycles in the graph. Not every subgraph has a cycle, but a good number of them do. – Anteater

Okay, and you want to have all the possible subgraphs? So from a graph that contains A --> B and B --> A, you want to create two graphs: One with the edge A --> B and the other with the edge B --> A? Is that right? Else, please clarify your question. Especially that last sentence. – Yesima

Answer 1

Maybe you are looking for weakly connected components?

That algorithm treats the edges as if they were undirected and returns the connected components in that graph.

In [1]: import networkx as nx

In [2]: G = nx.DiGraph([(1,2),(2,1),(3,4)])

In [3]: for w in nx.weakly_connected_component_subgraphs(G):
   ...:     print(w.edges())
   ...:     
[(1, 2), (2, 1)]
[(3, 4)]

Galvanoscope

Yes, that is right! Many thanks Aric, I'm still a newbie to graph theory, so I wasn't able to translate my thoughts correctly into graph theory language. Thank you!! – Anteater

Thanks for that one. But one question: when I assign the output of w_c_c_s() to a variable "subg" and then iterate over that one, its content seems to be "consumed" after the iteration. Why is that?! When I execute the print-loop twice, it does not print anything on the second run. – Bowsprit

Answer 2

You are looking for SCC of the graph, that are strongy connected component s. They can be found with a variant of DFS (depth first search).

You should take a look at the wiki article.

Yesima

I'm not sure this is exactly what I'm looking for. – Anteater

You want want to find all nodes x where there is a y in neighbour(x), so that x is element of neighbour(y)? That's what you want? – Yesima