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

Question

前提・実現したいこと

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

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

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

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

該当のソースコード

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

// 実際に Fruchterman-Reingold アルゴリズムを実装している関数。
// 利用している主な型は次のとおり:
//// Vector は x と y を数値として持つオブジェクト
// type Vector = { x: number, y: number }
// type NodeId = int;
//// Node は Vector に displacement と id を加えたオブジェクト
// type Node = { x: number, y: number, id: NodeId, displacement: Vector }
//// NodeId をキー、 Node の実態を値として持つ連想配列
// nodes :: Array<NodeId, Node>
//// NodeId をキー、 NodeId に該当する Node がつながっている NodeId の配列を値とする
// graph :: Array<NodeId, NodeId[]>
const placeNodes = () => {
  const rootArea = rootHeight * rootWidth;
  const nodeCount = nodes.length;
  const c = 1;
  const k = c * Math.sqrt(rootArea / nodes.length);

  const attraction = (distance) => {
    return Math.pow(distance, 2) / k;
  }

  const repulsion = (distance) => {
    return - Math.pow(k, 2) / distance;
  }

  const iterations = 50;

  let t = rootWidth / 10;
  const dt = t / iterations + 1;

  for (let i = 0; i < iterations; i++) {
    for (const node1 of nodes){
      node1.displacement = { x: 0, y: 0 };
      for (const node2 of nodes){
        if (node1.id !== node2.id) {
          const dx = node1.x - node2.x;
          const dy = node1.y - node2.y;
          const distance = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
          const rep = repulsion(distance);

          node1.displacement.x = node1.displacement.x + (dx / distance) * rep;
          node1.displacement.y = node1.displacement.y + (dy / distance) * rep;
        }
      }
      for (const node2Id of graph[node1.id]) {
        if (node1.id !== node2Id) {
          const node2 = nodes[node2Id];
          const dx = node1.x - node2.x;
          const dy = node1.y - node2.y;
          const distance = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
          const att = attraction(distance);

          node1.displacement.x = node1.displacement.x - (dx / distance) * att;
          node1.displacement.y = node1.displacement.y - (dy / distance) * att;

          node2.displacement.x = node2.displacement.x + (dx / distance) * att;
          node2.displacement.y = node2.displacement.y + (dy / distance) * att;
        }
      }
    }

    for (const node of nodes){
      const length = Math.sqrt(Math.pow(node.displacement.x, 2) + Math.pow(node.displacement.y, 2));
      node.x = node.x + (node.displacement.x / length) * Math.min(node.displacement.x, t);
      node.y = node.y + (node.displacement.y / length) * Math.min(node.displacement.y, t);

      // 中心が0ではないため、元の論文の式のとおりではなく、最も端の点と比較する
      node.x = Math.min(rootWidth, Math.max(0, node.x));
      node.y = Math.min(rootHeight, Math.max(0, node.y));
    }

    t = t - dt;
  }
};

試したこと

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

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

試したブラウザー

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

• Firefox 87.0
• Chromium Edge ver. 89.0.774.75

どちらもWindows 64bit版です。

参考にしたページ

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

• グラフ(ネットワーク)を奇麗に描画するアルゴリズム
• Graph Drawing by Force-directed Placement (1991)

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

Answer 1

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

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

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のコードで言うと、

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

を

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

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

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

Comments

[igrep]

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