무향 그래프로 변환하지 않고 유향 그래프에서 부분 그래프를 찾는 방법은 무엇입니까?

많은 하위 그래프가있는 그래프가 있습니다. A -> B와 B -> A의 두 방향으로 두 노드를 연결하는 가장자리가 있습니다. 양방향성은 A가 B로 이동하는지 또는 B가 A로 이동하는지에 대한 지식이 없기 때문에 양방향성이 중요하며 어느 것이 올바른지 쉽게 결정할 방법이 없습니다.무향 그래프로 변환하지 않고 유향 그래프에서 부분 그래프를 찾는 방법은 무엇입니까?

거기에 얼마나 많은 하위 그래프가 있는지 알고 싶습니다. 그리고 각 하위 그래프의 가장자리에 판다 데이터 프레임으로 출력하고 싶습니다. 그러나 NetworkX는 제공된 connected_components_subgraph (G) 함수에서 방향이없는 그래프 만 가져옵니다. 그래프를 무향 그래프로 변환하면 connected_components_subgraph()를 사용하여 각 모서리의 노드를 얻을 수 있지만 가장자리 방향을 잃을 수 있습니다.

달성하려는 작업을 수행하는 쉬운 방법이 있습니까?

출처

2013-09-05 ericmjl

그래프에 사이클이 있습니까? A → B (→ X) → A? – mike

예, 그래프에 사이클이 있습니다. 모든 하위 그래프에는 순환이있는 것은 아니지만 좋은 그래프가 있습니다. – ericmjl

자, 가능한 모든 하위 그래프를 갖고 싶습니까? 따라서 A -> B와 B -> A가 포함 된 그래프에서 두 개의 그래프를 만들려고합니다. 하나는 가장자리 A -> B이고 다른 하나는 가장자리 B -> A입니까? 그게 맞습니까? 그렇지 않으면 귀하의 질문을 명확히하십시오. 특히 그 마지막 문장. – mike

아마 weakly connected components을 찾고 계십니까?

이 알고리즘은 에지가 무향 인 것처럼 처리하고 연결된 그래프를 그 그래프에 반환합니다.

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

출처

2013-09-07 13:57:01 Aric

네, 맞습니다! 감사합니다. Aric, 저는 아직 그래프 이론에 초보자입니다. 그래서 제 생각을 정확하게 그래프 이론 언어로 번역 할 수 없었습니다. 고맙습니다!! – ericmjl

당신은 strongy연결구성 요소들이라는 것을, SCC 그래프의찾고 있습니다. 그들은 DFS (깊이 우선 검색)의 변형으로 발견 할 수 있습니다.

wiki 문서를 참조하십시오.

출처

2013-09-05 18:55:33 mike

이것이 내가 원하는 것을 정확히 모르겠습니다. – ericmjl

'neighbor (y)'의 요소가되도록'neighbor (x)'에'y'가있는 모든 노드'x'를 찾고 싶습니다. 그게 니가 원하는거야? – mike

무향 그래프로 변환하지 않고 유향 그래프에서 부분 그래프를 찾는 방법은 무엇입니까?

답변

관련 문제