CODEWITHSUNDEEP
pythongraphnetworkx
ericmjl
ericmjl

Reputation: 14724

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

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?

Upvotes: 3

Views: 3667

Answers (2)

Aric
Aric

Reputation: 25319

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)]

Upvotes: 5

mike
mike

Reputation: 5055

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.

Upvotes: 1

Related Questions