그래프를 배치 할 때 가장자리 중첩 최소화 기술은 무엇입니까? (가급적 GraphViz와 관련이 있음) 또한 기존의 소프트웨어가 평면형으로 그래프를 배치 할 수 있습니까?평면 그래프 레이아웃
현재 레이아웃 - 밝은 파란색 부분은 일부 피할 가장자리가 겹쳐있는 동안 http://www.evecakes.com/doodles/master.gif이
왼쪽 상단 모서리에있는 분홍색 부분은 잘 보인다.
일반 그래프의 경우, 최소 가장자리가 교차하는 그래프의 평면 레이아웃 (Crossing Number)을 결정하는 문제는 NP 하드입니다. 따라서 일부 휴리스틱 방법 (예 : Force based layout 알고리즘)이 사용됩니다.
아래 페이지는 graphviz 알고리즘을 간략히 설명하고 이점을 위해이를 사용하는 몇 가지 방법을 제안합니다. 또한 알고리즘에 대한 자세한 정보를 포함해야 PDF 파일에 대한 링크가 있습니다 : 도움이
http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html
희망을.
링크가 끊어졌습니다. –
그래프가 평평한 경우, 0 에지 크로싱 (평면 그래프의 정의이기 때문에)을 사용하여 임베딩을 생성 할 수 있습니다. - 그래프가 평면인지 여부를 결정하는 것은 선형 'O (N)'시간 [[1] (https://archive.org/details/PlanarityTestingByPathAddition) [2] (https://dl.acm.org/citation.cfm?id=321852)] 그리고 그것은 작고 (또한'O (N)')) 단계를 수행하여 임베딩을 생성합니다. 비평면 그래프의 경우, 네, 최소한의 엣지 크로싱 (edge crossing)으로 임베딩을 생성하는 것은 NP 어렵지만, 평면 임베딩/레이아웃 일 수는 없습니다. – MT0
다음 오픈 소스 Java 라이브러리에는 평면 그래프 배치에 도움이되는 몇 가지 알고리즘이 있습니다. 특히 http://open.trickl.com/trickl-graph/index.html
, 다음 클래스는 문제에 대한 분석 솔루션을 제공합니다
ChrobakPayneLayout을 (부스트 C에 따라 ++ 아론 윈저에 의해 구현) http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html
FoldFreeLayout (앵커를 기반으로 센서 네트워크의 무료 분산 로컬라이제이션 * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine 및 Seth Teller)
당신이하고자 할 수있는 일은 위와 같이 보이지는 않지만 중첩되지 않도록하는 첫 번째 "시도"와 같은 것을 사용하는 것입니다. 그런 다음 노드를보다 공평하게 배치하기 위해 force-directed 알고리즘을 적용 할 수 있습니다.
라이브러리는 방금 출시되었으므로 설명서가 부족합니다. 그러나 이론보다는 실제 코드를 제공하는 것이 유용 할 수 있습니다.
graphviz의 출력을 최적화하는 방법이나 가장자리 중첩 최소화 도구를 직접 구현하는 방법을 알고 싶습니까? –
전적으로 전하지만 후자에 관심이 있습니다. – jameszhao00
나는 더 많은 연구를했고 내 크기의 그래프를 위해 멀티 스케일 레이아웃이 유일한 옵션입니다. 그래서 지금 나는 SFDP를보고 있습니다. 중요한 SFDP 속성은 레벨이며 원하는 배율을 정의합니다. – jameszhao00