큰 무작위 평면 그래프 생성

Question

대형 (~ 300k 정점) 무작위 평면 그래프 (여기서는 "무작위"는 균일 분포 임)를 생성하는 가장 효율적인 방법은 무엇입니까?

Answer 1

그럼 하나의 방법은 평면 그래프 (예 : 에지 < = 3 * vertices - 6)와 비슷한 제약 조건을 만족하는 임의의 그래프를 생성하고 O (n) 시간 동안 평면인지 확인하는 것입니다. Tarjan의 평탄도 테스트 알고리즘. 평면이 아니면 다시 생성하십시오. 300K 버텍스가 얼마나 효율적인지는 확신 할 수 없지만 (또는 심지어 균일 한 확률로 그래프를 제공 할지라도).

평면 그래프를 생성하는 데 관한 몇 가지 문헌이 있는데 여기에 O (n^4) 실행 시간이 예상되는 Generating Labeled Planar Graphs 한 종이를 찾을 수 있으며 그만한 가치도 없을 수도 있습니다. 아마 거기에있는 참고 문헌은 당신이 도움이 될만한 것을 추적하는데 도움이 될 것입니다.

행운을 빈다.

Answer 2

다른 요구 사항이 없으면 무작위로 미로 생성을 검색한다고 말하고 싶습니다. 그래프의 사이클을 원하면 간단한 미로에서 무작위로 벽을 제거하십시오. 미로의 교차점은 그래프의 노드가되고 제거 된 벽은 가장자리입니다. 즉, 미로의 크기를 선택하여 노드 수를 선택할 수 있습니다.

미로는 일반적으로 한 지점에서 다른 지점까지 최대 4 개의 연결로 2 차원 그리드에서 수행되지만, 헥스 타일이나 기타 다른 미로를 수행하는 데 방해가되는 것은 없습니다.

Answer 3

제복으로 공간에 균등하게 분포 된 것을 의미하는 경우, 이것은 공간 생태/진화 시뮬레이터 용 평면 그래프를 생성하기 위해 개발 한 매우 빠른 알고리즘입니다. 그것은 예상되는 정도의 무작위 평면 그래프를 생성 할 것입니다. 평면 그래프에서 균일 한 임의의 각도를 원하면 균일 한 난수를 기반으로 예상 각도를 선택하도록 확장 할 수 있습니다.

https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py

Answer 4

은 또 다른 가능성은 임의로 평면 그래프 인 들로네 삼각를 계산 한 다음 좌표를 선택하고 것으로 이루어진다 (도 좋은 모양). http://en.wikipedia.org/wiki/Delaunay_triangulation 이러한 삼각 측량을 계산하기위한 O (n log (n)) 알고리즘이 있습니다.

Answer 5

볼츠만 샘플링을 보았습니까? Eric Fusy의 논문 "선형 시간의 평면 그래프의 균일 무작위 샘플링"을 참조하십시오. 이 논문과 구현은 그의 논문 homepage에서 사용 가능하며,이 논문에서는 몇 초 만에 100K 크기의 인스턴스를 생성 할 수 있다고합니다.