たれぱんのびぼーろく

わたしの備忘録、生物学とプログラミングが多いかも

有向非循環グラフの可視化

概要

有向非循環グラフの可視化(visualization)について手法と記事のまとめ。

有向非循環グラフ

Directed Acyclic Graph

architecture

  1. topolodical sort
  2. layer assignment
  3. vertex ordering within layers
  4. median
  5. vertex positioning within layers

Sugiyama methods

黄金
(saved in local)

http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4308636

参考文献

Dagre-D3
ライブラリ

github.com

スタックオーバーフロー

stackoverflow.com

stackoverflow.com

http://www.graphviz.org/Documentation/TSE93.pdf

グラフの分類

http://www.iplab.cs.tsukuba.ac.jp/paper/noguchi_master.pdf

階層内頂点順序の決定

Vertex ordering within layers/ranks
edgeの交差を最小限にするために, 層内での頂点優先度付けを行う作業.

階層内頂点位置の決定

階層化、階層化頂点順序決定ののち、階層内での頂点位置を決めるアルゴリズムの提案.
"階層グラフ描画における頂点座標決定アルゴリズム"
https://ipsj.ixsq.nii.ac.jp/ej/index.php?action=pages_view_main&active_action=repository_action_common_download&item_id=70917&item_no=1&attribute_id=1&file_no=1&page_id=13&block_id=8

まとめ記事

"Hierarchical Drawing Algorithms"
https://cs.brown.edu/~rt/gdhandbook/chapters/hierarchical.pdf

topological sort

#

"Longest path in a directed acyclic graph (DAG)"
http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/Docs/longest-path-in-dag.pdf