Как найти подграфы в ориентированном графе без преобразования в неориентированный граф?

У меня есть график, который имеет много подграфов. У меня есть некоторые ребра, которые соединяют два узла в обоих направлениях, то есть A ->B и B ->A. Двунаправленность важна, так как с нашей стороны недостаточно знаний о том, идет ли А к В или В идет к А, и у нас нет простого способа определить, какой из них правильный.

Я хотел бы знать, сколько существует подграфов, и вывести в Pandas DataFrame ребра в каждом подграфе. Однако NetworkX принимает только неориентированные графы в предоставленной функции connected_components_subgraph(G). Когда я конвертирую график в неориентированный граф, я могу использовать connected_components_subgraph(), чтобы получить узлы в каждом ребре, но я теряю направленность ребра.

Есть ли простой способ сделать то, что я пытаюсь достичь?

2 ответа

Решение

Может быть, вы ищете слабосвязанные компоненты?

Этот алгоритм обрабатывает ребра так, как если бы они были ненаправленными, и возвращает связанные компоненты в этом графе.

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

Вы ищете SCC графа, которые являются сильно связанными компонентами s. Их можно найти с помощью варианта DFS (поиск в глубину).

Вы должны взглянуть на статью вики.

Другие вопросы по тегам