Python NetworkX는 노드의 지시 그래프에서 루트로 서브 그래프를 찾습니다.

Question

나는 유향 그래프에서 정보를 추출하는 코드를 작성하고 있습니다. 이 그래프에는 사이클도 있습니다. 예를 들어,

이 그래프로부터

A->B->C->D 
A->E->F->A 
B->F->G 

, 전 서브 그래프 또는 입력 노드 될 노드들의리스트를 생성하고자하고, 출력은 입력 노드가 루트 인 그래프 것, 또는 입력 노드의 모든 자식 노드 (그래프 끝까지)가있는 노드 목록

예를 들어 위의 예에서 1. 입력 노드가 C이면 출력은 다음과 같습니다. D 2. 입력 노드가 B이면 출력 노드는 C, D, F, G, A가됩니다 (A와 B를 양방향으로 만드는 사이클이 있으므로) 3. 입력이 G이면 출력 공 i 또는 널입니다.

python networkx에는이 문제를 해결하는 데 사용할 수있는 기능이 있습니까?

또는이 문제를 해결하는 데 도움이되는 다른 도구가 있습니까?

Answer 1

원하는 기능은 dfs_preorder_nodes()입니다. 여기에 귀하의 데이터를 기반으로 약간의 데모입니다

는

import networkx as nx 

g = nx.DiGraph() 

g.add_edge('A', 'B') 
g.add_edge('B', 'C') 
g.add_edge('C', 'D') 

g.add_edge('A', 'E') 
g.add_edge('E', 'F') 
g.add_edge('F', 'A') 

g.add_edge('B', 'F') 
g.add_edge('F', 'G') 

print('A:', list(nx.dfs_preorder_nodes(g, 'A'))) 
print('B:', list(nx.dfs_preorder_nodes(g, 'B'))) 
print('G:', list(nx.dfs_preorder_nodes(g, 'G'))) 

출력 :

A: ['A', 'B', 'C', 'D', 'F', 'G', 'E'] 
B: ['B', 'C', 'D', 'F', 'A', 'E', 'G'] 
G: ['G'] 

출력은 시작 노드를 포함한다. 따라서 원하지 않으면 목록에서 첫 번째 요소를 제거하십시오.

dfs_preorder_nodes()은 생성기 개체를 반환합니다. 그래서 list()이라고 부르며 사용 가능한 출력을 얻습니다.

Answer 2

nx.ego_graph() 정확히 무엇을 설명합니까. @Hai 데자뷰에 의해 주어진 예제를 사용하면 : 당신이 잎까지 트리의 모든 노드를 얻을하려는 경우

g = nx.DiGraph() 

g.add_edge('A', 'B') 
g.add_edge('B', 'C') 
g.add_edge('C', 'D') 
g.add_edge('A', 'E') 
g.add_edge('E', 'F') 
g.add_edge('F', 'A') 
g.add_edge('B', 'F') 
g.add_edge('F', 'G') 

a = nx.ego_graph(g, 'A', radius=100) 
a.node 
#out: NodeView(('A', 'B', 'C', 'D', 'E', 'F', 'G')) 

list(nx.ego_graph(g, 'G', radius=100).node) 
#out: ['G'] 

radius 임의의 큰 숫자를해야합니다.