2012-10-25 3 views
1

기존의 정점 및 모서리 데이터를 연결되지 않은 두 개 이상의 그래프로 분리하고 싶습니다. (연결 및 좌표에 따라 두 그래프 분리하기

서로의 상단에 두 개의 육각형을 상상하지만,

육각 1 A (0,0,1)를 다음 정점을 가지고 다른 Z.에 거짓말 B를 : 나는 예로서 다음과주고 싶습니다 1,0,2), C (2,1,2), D (1,2,1), E (0,2,1), F (-1,2,1)이다. 연결성은 A-B, B-C, C-D, D-E, E-F, F-A와 같습니다. 그래프 1의이 부분은 모든 정점이이 레이어에 연결되어 있습니다.

Hexagon2는 다음과 같은 정점 A1 (0,0,6), B1 (1,0,7), C1 (2,1,7), D1 (1,2,8), E1 , 7), F1 (-1,2,6). 연결은 A1-B1, B1-C1, C1-D1, D1-E1, E1-F1, F1-A1입니다. 이것은 그래프 2의 일부입니다

내 데이터는 다음 형식으로되어 있습니다 : 그래프를 구성 할 수있는 꼭짓점 목록 및 가장자리 목록. 그래프 2를 없애고 그래프 1의 꼭짓점과 연결 만 알고리즘에 제공하십시오. 내 실제 데이터는 약 1000 개의 연결된 다각형을 그래프 1로, 약 100 개의 다각형을 그래프 2로 포함합니다. 그래프 2를 제거하고 싶습니다.

답변

2

설명하는 문제는 connected components과 관련됩니다.

파이썬 Networkx 모듈에는 이러한 유형의 그래프 문제를 처리하는 함수가 있습니다. 모든 컴포넌트를 반환하는 connected_components 함수를 찾고 있다면, 적절한 컴포넌트 (정점의 개수로 가능)를 선택할 수 있습니다.