Kamada, Kawai のグラフ描画アルゴリズム - 私の図書館
はしがき 今回はフロイド法のところで言及したグラフ描画アルゴリズムについて書きます。 私はグラフ描画の世界に関しては何も知らない素人で、このアルゴリズムも古典的な有名どころらしきものを適当に選んだだけなのですが、このアルゴリズムが掲載されている An Algorithm for Drawing General Undirected Graphs は今日の時点で Google Scholar 調べで 1198 の記事から引用されているというとても凄い論文です。 アルゴリズム アルゴリズムはとてもシンプルなもので、グラフの各頂点の現在の描画位置を引数にとるエネルギー関数を定義し、その極小点を Newton-Raphson 法で求めるだけです。 頂点を結ぶ辺は、頂点の位置が定まった後に直線によって描画されます。 よって（入力が平面グラフであっても）辺は交差している場合があります。 エネルギー関数
http://www.cse.ohio-state.edu/~chaudhua/Temporary/wi11_888/Papers/Kamada_GraphDrawing_Letters89.pdf
Information Processing Letters 31 (1989) 7-15 North-Holland AN ALGORITHM FOR DRAWING GENERAL UNDIRECTED GRAPHS Tomihisa KAMADA and Satoru KAWAI 12 April 1989 Department of Information Science, Faculty of Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113 Japan Communicated by E.C.R. Hehner Received 4 July 1988 Revised 13 November 1988 Keywords: Graph, network structure, layout, draw
ビジュアルプログラミングシステムのためのグラフ描画アルゴリズムの改良 | CiNii Research
データ構造の表現の方法として, 辺と節からなるグラフ構造がある. このグラプ構造により表現されたデータをわかりやすく提示するために, グラフ自動描画法が研究されてきている. また現在, 並列論理型言語をグラフによって可視化するビジュアルプログラミングシステムを開発中であり, それにグラフ描画アルゴリズムを応用することを検討している. これは, 並列論理型言語での定義節をグラフの節, 論理変数を辺で表現することにより可読性の向上を図るものである. これまでに提案されているグラフ描画アルゴリズムの多くは, グラフの論理的構造を入力として, その構造の最適な配置を求めるというものであったが, ここでは, 特に人間の手によって入力された形の整っていないグラフを, 再配置の過程をアニメーションのような表現で見せることによってわかりやすさの向上を図るためのアルゴリズムの改良を提案する. あるグラフの再
)
力学モデル (グラフ描画アルゴリズム) - Wikipedia
力学モデルによる、wiki ページのネットワークの可視化。（辺はリンクを表す） 力学モデル（りきがくモデル）によるグラフ描画（力指向アルゴリズム）は、グラフを美しく描画するためのアルゴリズムの一つである。 このアルゴリズムは、グラフのノードを2次元空間や3次元空間に配置して、辺の長さをほぼ等しい長さにし、グラフの辺ができるだけ交差しないようにすることを目的にしている。 このアルゴリズムでは、グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探すことで、この目的を達成している。もっとも直截的なモデルでは、それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。 そして、その力学系の挙動をシミュレートし、弾性力や静電気力が粒子を近づけたり遠ざけたりするようすを計算する。粒子が安定な配置になり、位置が変化しなくなるま
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
グラフ描画入門 - Wolfram Mathematica
グラフ描画アルゴリズムの性能評価 | CiNii Research
