레이어드 그래프 그리기

Layered graph drawing
Graphviz에 의해 생성된 유향 비순환 그래프의 레이어드 도면

계층형 그래프 그리기 또는 계층형 그래프 그리기란 방향 그래프의 정점이 수평 행 또는 레이어로 그려지고 가장자리가 일반적으로 [1][2][3]아래쪽을 향하게 되는 그래프 그리기 유형입니다.이 그림을 처음 개발한 [4]스기야마 코조의 이름을 따서 스기야마풍 그래프 그리기라고도 불린다.

레이어드 드로잉의 이상적인 형태는 위쪽 평면 도면입니다.이 도면에서는 모든 가장자리가 일관된 방향으로 향하고 가장자리 쌍이 교차하지 않습니다.그러나, 그래프는 종종 순환을 포함하고, 일관되지 않은 방향의 모서리 수를 최소화하는 것은 NP-hard이며, 교차의 수를 최소화하는 것도 NP-hard이기 때문에, 계층화된 그래프 그리기 시스템은 일반적으로 도면의 이러한 유형의 결점을 최소 개수의 도면을 찾는 것을 보장하지 않고 일련의 휴리스틱스를 적용합니다.흠집

레이아웃 알고리즘

계층화된 그래프 도면의 구성은 일련의 단계로 진행됩니다.

  • 입력 그래프가 아직 방향 비순환 그래프가 아닌 경우, 일련의 에지가 식별되어 반전하면 비순환 그래프가 됩니다.가능한 최소 에지 세트를 찾는 것은 NP-완전 피드백 아크 집합 문제이기 때문에 여기서는 정확한 최적화 알고리즘 [1][2][3][5][6][7]대신 탐욕 휴리스틱이 자주 사용됩니다.이 문제에 대한 정확한 해결책은 정수 [3]프로그래밍을 사용하여 공식화할 수 있습니다.반대로 반전된 에지의 수가 매우 적은 경우 고정 파라미터-트래킹 가능한 [8]알고리즘으로 이러한 에지를 찾을 수 있습니다.
  • 첫 번째 단계에서 생성된 방향 비순환 그래프의 정점은 각 가장자리가 상위 레이어에서 하위 레이어로 이동하도록 레이어에 할당됩니다.이 단계의 목표는 소수의 레이어, 다수의 레이어에 걸쳐 있는 몇 개의 엣지, 그리고 레이어에 [1][2][3]정점을 균형 있게 할당하는 것입니다.예를 들어, Mirsky의 정리에 따르면, 각 정점에서 시작하는 가장 긴 경로의 길이에 따라 정점을 계층별로 할당하면 가능한 최소 [1][3]계층 수로 할당됩니다.Coffman-Graham 알고리즘은 레이어당 정점 수에 대한 사전 설정된 제한을 가진 레이어를 찾고 그 [1][2][3]제약조건에 따르는 레이어 수를 대략적으로 최소화하기 위해 사용될 수 있다.가장 넓은 층의 폭을 최소화하는 것은 NP-hard이지만 분기 및 절단 또는 근사 휴리스틱으로 [3]해결할 수 있습니다.또는 (레이어당 정점 수에 대한 제한 없이) 에지에 의해 확장된 총 레이어 수를 최소화하는 문제는 선형 [9]프로그래밍을 사용하여 해결할 수 있다.정수 프로그래밍 절차를 사용하여 에지 길이 최소화를 레벨당 정점 [10]수에 대한 제한과 결합할 수 있습니다.
  • 여러 레이어에 걸쳐 있는 모서리는 더미 정점의 경로로 대체되므로 이 단계 이후 확장된 그래프의 각 모서리가 [1][2]도면의 인접 레이어에서 두 정점을 연결합니다.
  • 옵션 스텝으로서 기존의 2개의 정점층 사이에 엣지 콘센트레이터 정점층(또는 합류점)을 부가할 수 있으며, 이러한 엣지 [3][11][12]콘센트레이터를 통해 완전한 초당 서브그래프를 별에 의해 대체함으로써 엣지 밀도를 낮출 수 있다.
  • 각 레이어 내의 정점은 이전 [1][2][3]레이어에 연결하는 가장자리 사이의 교차 수를 줄이기 위해 정렬됩니다.심지어 이 way,[13][14]에 그렇게 다시 발견적 학습 법에 그와 같은 위치 또는 중간값은 이웃들의 previo에 입장들이 평균을 발견함으로써 결정에 각 꼭지점을 얹는 리조트 일반적이다 한번에 한층의 주문이나 가장자리가 최대crossing-free 집합을 찾는 건널목의 최소 숫자를 찾는 것은, NP완전이다.우리 level 그리고 그것이 [1][2][9][14][15]교차의 수를 개선한다면 인접한 쌍을 교환한다.또는 한 번에 하나의 레이어 내의 정점의 순서는 그 레이어와 이전 [3][16]레이어 사이의 교잡 횟수로 트래킹 가능한 고정 파라미터 알고리즘을 사용하여 선택될 수 있다.
  • 각 정점은 이전 [1][2]단계에서 계산된 순열과 일관되게 해당 레이어 내에서 좌표가 할당됩니다.이 단계에서 고려해야 할 사항으로는 불필요한 굴곡을 방지하기 위해 두 인접 라우터 사이의 선상에 더미 노드를 배치하고 인접 [3]라우터에 대해 각 정점을 중앙에 배치하는 것이 포함됩니다.Sugiyama의 원래 연구는 이 단계의 2차 프로그래밍 공식을 제안했다. Brandes와 Köpf의 이후 방법은 [3][17]선형 시간이 걸리며 에지당 최대 2개의 벤딩을 보장한다.
  • 알고리즘의 첫 번째 단계에서 반전된 가장자리가 원래 방향으로 돌아가고 더미 정점이 그래프에서 제거되고 정점과 가장자리가 그려집니다.정점과 모서리 사이의 교차를 방지하기 위해 도면의 여러 레이어에 걸쳐 있는 모서리를 [1][2][9]모서리를 따라 더미 정점에 할당된 각 위치를 통과하는 다각형 체인 또는 스플라인 곡선으로 그릴 수 있습니다.

실장

가장 단순한 형태에서 계층화된 그래프 그리기 알고리즘은 생성될 수 있는 더미 정점의 수가 많기 때문에 n개의 정점과 m개의 모서리를 가진 그래프에서 O(mn) 시간을 필요로 할 수 있습니다.그러나 알고리즘의 일부 변형에서는 더미 정점의 효과를 실제로 명시적으로 구성하지 않고 시뮬레이션할 수 있으며, 이는 거의 선형적인 시간 [18]구현으로 이어진다.

Graphviz의 "도트" 도구는 계층화된 [9]도면을 생성합니다.레이어드 그래프 그리기 알고리즘은 Microsoft Automatic Graph[19] Layout 및 [20]Tulip에도 포함되어 있습니다.

바리에이션

일반적으로 행과 가장자리의 정점이 위에서 아래로 진행되도록 그려지지만, 대신 열과 가장자리의 정점이 왼쪽에서 오른쪽으로 [21]진행되도록 계층 그래프 그리기 알고리즘을 그릴 수 있습니다.또한 동일한 알고리즘 프레임워크가 일부 시작[3][22] 노드 주위에 동심원 모양으로 그래프를 배치하는 방사형 레이아웃과 그래프의 [3][23]3차원 레이어드 도면에도 적용되었다.

긴 모서리가 많은 레이어드 그래프 도면에서는 모서리 세트를 번들로 그룹화하고 동일한 더미 [24]정점 세트를 통해 함께 라우팅함으로써 모서리 클러터를 줄일 수 있습니다.마찬가지로 연속된 레이어 쌍 간에 교차하는 가장자리가 많은 도면의 경우 최대 이분 서브그래프의 가장자리는 합류 [25]번들로 그룹화될 수 있습니다.

정점이 층으로 배열된 도면은 스기야마의 골격을 따르지 않는 알고리즘에 의해 구성될 수 있다.예를 들어, 이러한 유형의 도면이 있는 그래프에 경계 경로 [26]폭이 있다는 사실을 사용하여 h개의 레이어를 사용하여 k개의 교차도가 있는 도면을 일정 시간 내에 다항식인지 여부를 알 수 있다.

개념 격자의 레이어드 도면에서는 스기야마 프레임워크와 가법(각 정점은 집합을 나타내고 정점의 위치는 집합 내의 요소를 나타내는 벡터의 합)을 결합한 하이브리드 접근법을 사용할 수 있다.이 하이브리드 어프로치에서 알고리즘의 정점 치환과 좌표 할당 위상은 각 정점의 수평 위치가 해당 [27]정점에 대한 요소를 나타내는 스칼라의 합으로 선택되는 단일 위상으로 대체된다.계층형 그래프 그리기 방법도 힘 지향 그래프 그리기 알고리즘을 [28]위한 초기 배치를 제공하기 위해 사용되어 왔다.

레퍼런스

  1. ^ a b c d e f g h i j 를 클릭합니다Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 978-0-13-301615-4.
  2. ^ a b c d e f g h i 를 클릭합니다Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
  3. ^ a b c d e f g h i j k l m n 를 클릭합니다Healy, Patrick; Nikolov, Nikola S. (2014), "Hierarchical Graph Drawing", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 409–453.
  4. ^ 를 클릭합니다Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Methods for visual understanding of hierarchical system structures", IEEE Transactions on Systems, Man, and Cybernetics, SMC-11 (2): 109–125, doi:10.1109/TSMC.1981.4308636, MR 0611436.
  5. ^ 를 클릭합니다Berger, B.; Shor, P. (1990), "Approximation algorithms for the maximum acyclic subgraph problem", Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA'90), pp. 236–243, ISBN 9780898712513.
  6. ^ 를 클릭합니다Eades, P.; Lin, X.; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters, 47 (6): 319–323, doi:10.1016/0020-0190(93)90079-O.
  7. ^ 를 클릭합니다Eades, P.; Lin, X. (1995), "A new heuristic for the feedback arc set problem", Australian Journal of Combinatorics, 12: 15–26.
  8. ^ 를 클릭합니다Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM, 55 (5): 1, doi:10.1145/1411509.1411511.
  9. ^ a b c d 를 클릭합니다Gansner, E. R.; Koutsofios, E.; North, S. C.; Vo, K.-P. (1993), "A technique for drawing directed graphs", IEEE Transactions on Software Engineering, 19 (3): 214–230, doi:10.1109/32.221135.
  10. ^ 를 클릭합니다Healy, Patrick; Nikolov, Nikola S. (2002), "How to layer a directed acyclic graph", Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, pp. 16–30, doi:10.1007/3-540-45848-4_2, ISBN 978-3-540-43309-5, MR 1962416.
  11. ^ 를 클릭합니다Newbery, F. J. (1989), "Edge concentration: a method for clustering directed graphs", Proceedings of the 2nd International Workshop on Software Configuration Management (SCM '89), Princeton, New Jersey, USA, Association for Computing Machinery, pp. 76–85, doi:10.1145/72910.73350, ISBN 0-89791-334-5.
  12. ^ 를 클릭합니다Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2004), "Confluent layered drawings", in Pach, János (ed.), Proc. 12th Int. Symp. Graph Drawing (GD 2004), Lecture Notes in Computer Science, vol. 47 (3383 ed.), Springer-Verlag, pp. 184–194, arXiv:cs.CG/0507051, doi:10.1007/s00453-006-0159-8.
  13. ^ 를 클릭합니다Eades, Peter; Whitesides, Sue (1994), "Drawing graphs in two layers", Theoretical Computer Science, 131 (2): 361–374, doi:10.1016/0304-3975(94)90179-1.
  14. ^ a b 를 클릭합니다Eades, Peter; Wormald, Nicholas C. (1994), "Edge crossings in drawings of bipartite graphs", Algorithmica, 11 (4): 379–403, doi:10.1007/BF01187020.
  15. ^ 를 클릭합니다Mäkinen, E. (1990), "Experiments on drawing 2-level hierarchical graphs", International Journal of Computer Mathematics, 36 (3–4): 175–181, doi:10.1080/00207169008803921.
  16. ^ 를 클릭합니다Dujmović, Vida; Fernau, Henning; Kaufmann, Michael (2008), "Fixed parameter algorithms for one-sided crossing minimization revisited", Journal of Discrete Algorithms, 6 (2): 313–323, doi:10.1016/j.jda.2006.12.008, MR 2418986.
  17. ^ 를 클릭합니다Brandes, Ulrik; Köpf, Boris (2002), "Fast and simple horizontal coordinate assignment", Graph drawing (Vienna, 2001), Lecture Notes in Computer Science, vol. 2265, Berlin: Springer, pp. 31–44, doi:10.1007/3-540-45848-4_3, ISBN 978-3-540-43309-5, MR 1962417.
  18. ^ Eiglsperger, 마르쿠스;Siebenhaller, 마틴, 카우프만, 마이클(2005년),"스기야마의 알고리즘의 계층화된 그래프 그리기에 효과적인 구현"Graph도면, 12일 국제 심포지엄, 승무원 2004년, 뉴욕, 뉴욕, 미국, 9월 29-October 2,2004년, 선택된 논문 개정된, 강의 노트 컴퓨터 과학으로, vol. 3383, Springer-Verlag,를 대신하여 서명함. 155–1.66, doi:10.1007/978-3-540-31843-9_17, 아이 에스비엔 978-3-540-24528-5.
  19. ^ Nachmanson, 레프, 로버트슨, 조지, 대통령, Bongshin(2008년),"GLEE과 Graphs 그리는"(PDF), 홍, Seok-Hee에;Nishizeki, 다카오, 권, 우(eds.)Graph도면, 15일 국제 심포지엄, GD2007년, 시드니, 호주, 9월 24–26, 2007, 수정된 논문, 강의 노트 컴퓨터 과학으로, Springer-Verlag,를 대신하여 서명함. 389–394, 4875 vol.. doi:10.1007/978-3-540-77537-9_38, 아이 에스비엔 978-3-540-77536-2.
  20. ^ 를 클릭합니다Auber, David (2004), "Tulip – A Huge Graph Visualization Framework", in Jünger, Michael; Mutzel, Petra (eds.), Graph Drawing Software, Springer-Verlag, ISBN 978-3-540-00881-1.
  21. ^ 를 클릭합니다Baburin, Danil E. (2002), "Some modifications of Sugiyama approach", Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers, Lecture Notes in Computer Science, vol. 2528, Springer-Verlag, pp. 366–367, doi:10.1007/3-540-36151-0_36, ISBN 978-3-540-00158-4.
  22. ^ 를 클릭합니다Bachmaier, Christian (2007), "A radial adaptation of the Sugiyama framework for visualizing hierarchical information", IEEE Transactions on Visualization and Computer Graphics, 13 (3): 583–594, doi:10.1109/TVCG.2007.1000, PMID 17356223.
  23. ^ 를 클릭합니다Hong, Seok-Hee; Nikolov, Nikola S. (2005), "Layered drawings of directed graphs in three dimensions", Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation (APVis '05), Conferences in Research and Practice in Information Technology, vol. 45, pp. 69–74, ISBN 9781920682279.
  24. ^ Pupyrev, 세르게이, Nachmanson, 레프, 카우프만, 마이클(2011년),"가장자리 끼워 팔기와 계층화된 그래프 레이아웃을 개선하는 것", 도표 작성 18일 국제 심포지엄, GD2010년 콘스탄츠, 독일, 9월 21일부터 24일까지, 2010년에는 선택된 논문 개정된, 강의 노트 컴퓨터 과학으로, vol. 6502, Springer-Verlag, pp. 329–340, doi:10.1007/978-3-642-18469-7_30, 국제 표준 도서 번호. 978-3-642-18468-0.
  25. ^ 를 클릭합니다Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2007), "Confluent layered drawings", Algorithmica, 47 (4): 439–452, arXiv:cs/0507051, doi:10.1007/s00453-006-0159-8.
  26. ^ 를 클릭합니다Dujmović, V.; Fellows, M.R.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S. (2008), "On the parameterized complexity of layered graph drawing", Algorithmica, 52 (2): 267–292, doi:10.1007/s00453-007-9151-1.
  27. ^ 를 클릭합니다Cole, Richard (2001), "Automated layout of concept lattices using layered diagrams and additive diagrams", Proceedings of the 24th Australasian Conference on Computer Science (ACSC '01), Australian Computer Science Communications, 23 (1): 47–53, doi:10.1109/ACSC.2001.906622, ISBN 0-7695-0963-0.
  28. ^ Benno Schwikowski; Peter Uetz & Stanley Fields (2000). "A network of protein−protein interactions in yeast". Nature Biotechnology. 18 (12): 1257–1261. doi:10.1038/82360. PMID 11101803.