Как найти подграфы в ориентированном графе без преобразования в неориентированный граф?
У меня есть график, который имеет много подграфов. У меня есть некоторые ребра, которые соединяют два узла в обоих направлениях, то есть 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 (поиск в глубину).
Вы должны взглянуть на статью вики.