python - real - ¿Cómo encontrar subgrafos en un gráfico dirigido sin convertir a gráfico no dirigido?

graficas con animacion python

Question

Tengo un gráfico que tiene muchos subgrafos. Tengo algunos bordes que conectan dos nodos en ambas direcciones, es decir, A -> B y B -> A. La bidireccionalidad es importante, ya que representa una falta de conocimiento por nuestra parte sobre si A va a B o B va a A, y no tenemos una manera fácil de determinar cuál es la correcta.

Me gustaría saber cuántos subgrafos hay, y enviar a un Pandas DataFrame los bordes en cada subgrafo. Sin embargo, NetworkX solo toma gráficos no dirigidos en la función proporcionada adjunta_componentes_subgraph (G). Cuando convierto el gráfico en un gráfico no dirigido, puedo usar connected_components_subgraph () para obtener los nodos en cada borde, pero pierdo la direccionalidad de los bordes.

¿Hay una manera fácil de hacer lo que estoy tratando de lograr?

Answer 1

Está buscando SCC del gráfico, que son componentes fuertemente conectados . Se pueden encontrar con una variante de DFS (primera búsqueda de profundidad).

Deberías echarle un vistazo al artículo de la wiki .

Answer 2

Tal vez estás buscando componentes débilmente conectados ?

Ese algoritmo trata los bordes como si no estuvieran dirigidos y devuelve los componentes conectados en ese gráfico.

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