質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.53%
グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

Q&A

解決済

1回答

1643閲覧

Fruchterman-Reingoldというグラフを描画するアルゴリズムを実装してみたが、すべてのノードが描画領域の右下に集まってしまう

igrep

総合スコア428

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

0グッド

0クリップ

投稿2021/04/12 10:00

編集2021/04/12 10:08

前提・実現したいこと

グラフの自動描画アルゴリズムをJavaScriptで実装して、SVGとして描画したい。

発生している問題・エラーメッセージ

リポジトリーに置いたHTMLをブラウザーで開いて「再配置する」というボタンをクリックすると、Fruchterman-Reingold アルゴリズムで各ノードの適切な位置を計算してくれるはずなのですが、最終的にすべてのノードが左上に集まってしまいます。

デバッガーでステップ実行すると分かるのですが、iteration毎にノードが描画領域の右下に移動してしまい、最終的にすべてのノードが描画領域における右下の角に配置され、結果次のiterationで位置を表すベクトルの各成分がNaNになってしまいます(すべてのノードが同じ位置に移動したことになるので)。

該当のソースコード

こちらが実際に Fruchterman-Reingold アルゴリズムを実装した関数です。
実際に動くHTMLはこちらにあります。要件の都合上、HTMLファイル単体で動作するように実装しておりますので、試していただける場合はダウンロードして開いてみてください。

js

1// 実際に Fruchterman-Reingold アルゴリズムを実装している関数。 2// 利用している主な型は次のとおり: 3//// Vector は x と y を数値として持つオブジェクト 4// type Vector = { x: number, y: number } 5// type NodeId = int; 6//// Node は Vector に displacement と id を加えたオブジェクト 7// type Node = { x: number, y: number, id: NodeId, displacement: Vector } 8//// NodeId をキー、 Node の実態を値として持つ連想配列 9// nodes :: Array<NodeId, Node> 10//// NodeId をキー、 NodeId に該当する Node がつながっている NodeId の配列を値とする 11// graph :: Array<NodeId, NodeId[]> 12const placeNodes = () => { 13 const rootArea = rootHeight * rootWidth; 14 const nodeCount = nodes.length; 15 const c = 1; 16 const k = c * Math.sqrt(rootArea / nodes.length); 17 18 const attraction = (distance) => { 19 return Math.pow(distance, 2) / k; 20 } 21 22 const repulsion = (distance) => { 23 return - Math.pow(k, 2) / distance; 24 } 25 26 const iterations = 50; 27 28 let t = rootWidth / 10; 29 const dt = t / iterations + 1; 30 31 for (let i = 0; i < iterations; i++) { 32 for (const node1 of nodes){ 33 node1.displacement = { x: 0, y: 0 }; 34 for (const node2 of nodes){ 35 if (node1.id !== node2.id) { 36 const dx = node1.x - node2.x; 37 const dy = node1.y - node2.y; 38 const distance = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2)); 39 const rep = repulsion(distance); 40 41 node1.displacement.x = node1.displacement.x + (dx / distance) * rep; 42 node1.displacement.y = node1.displacement.y + (dy / distance) * rep; 43 } 44 } 45 for (const node2Id of graph[node1.id]) { 46 if (node1.id !== node2Id) { 47 const node2 = nodes[node2Id]; 48 const dx = node1.x - node2.x; 49 const dy = node1.y - node2.y; 50 const distance = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2)); 51 const att = attraction(distance); 52 53 node1.displacement.x = node1.displacement.x - (dx / distance) * att; 54 node1.displacement.y = node1.displacement.y - (dy / distance) * att; 55 56 node2.displacement.x = node2.displacement.x + (dx / distance) * att; 57 node2.displacement.y = node2.displacement.y + (dy / distance) * att; 58 } 59 } 60 } 61 62 for (const node of nodes){ 63 const length = Math.sqrt(Math.pow(node.displacement.x, 2) + Math.pow(node.displacement.y, 2)); 64 node.x = node.x + (node.displacement.x / length) * Math.min(node.displacement.x, t); 65 node.y = node.y + (node.displacement.y / length) * Math.min(node.displacement.y, t); 66 67 // 中心が0ではないため、元の論文の式のとおりではなく、最も端の点と比較する 68 node.x = Math.min(rootWidth, Math.max(0, node.x)); 69 node.y = Math.min(rootHeight, Math.max(0, node.y)); 70 } 71 72 t = t - dt; 73 } 74};

試したこと

定数cやノードの数、描画領域の大きさなど、いくつかのパラメーターを調整しましたが、結果は変わりませんでした。

補足情報(FW/ツールのバージョンなど)

試したブラウザー

ブラウザー依存の問題ではないとは思いますが念の為:

  • Firefox 87.0
  • Chromium Edge ver. 89.0.774.75

どちらもWindows 64bit版です。

参考にしたページ

Fruchterman-Reingold アルゴリズムを実装する際、下記の記事とその参照している論文を参考にしました:

後者の元ネタとなった論文をダウンロードすれば、アルゴリズムの詳しい解説や、擬似コードが載っています。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

このようなアルゴリズムがあると初めて知り、勉強になりました。ありがとうございます。

参考文献にあげていただいている論文の擬似コードとその下にある

Our analogue to simulated annealing’s

temperature is limiting the maximum displacement of every vertex during an iteration, and changing that maximum displacement from iteration to iteration.

という文言を見るに、擬似コード内の

min(v.disp,t)

は、min(|v.disp|,t)の誤植と思われます。(tが十分大きければv.dispの分だけv.posが変動するため)

投稿していただいているJavascriptのコードで言うと、

javascript

1const length = Math.sqrt(Math.pow(node.displacement.x, 2) + Math.pow(node.displacement.y, 2)); 2node.x = node.x + (node.displacement.x / length) * Math.min(node.displacement.x, t); 3node.y = node.y + (node.displacement.y / length) * Math.min(node.displacement.y, t);

javascript

1const length = Math.sqrt(Math.pow(node.displacement.x, 2) + Math.pow(node.displacement.y, 2)); 2node.x = node.x + (node.displacement.x / length) * Math.min(length, t); 3node.y = node.y + (node.displacement.y / length) * Math.min(length, t);

にするとそれらしい出力が得られました。
修正後出力

論文を隅まで理解できていないので、根本な解決になっていなければ申し訳ありません。

投稿2021/04/12 10:42

編集2021/04/12 10:45
ayanamizuta

総合スコア11

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

igrep

2021/04/13 00:29

ありがとうございます!私自身ちゃんと理解出来てませんでした。確かに、修正前のままだとdisplacementが負の数だった場合、lengthもtも正の数だからかけ算で正の数になってしまいますね!だからどんどん右下に移動してしまうということがよくわかりました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.53%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問