JavaScriptでグラフ構造を扱う

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。

はじめに

Python でグラフ構造を扱う際には、networkx を使うのが知られていると思います。同じようにグラフ構造を JavaScript や TypeScript で扱うには、networkx が使えませんので代替となるフレームワークが必要になります。そこで本稿では、JavaScript でグラフ構造を扱うためのフレームワークについて取り上げます。

グラフ構造を扱うJavaScriptライブラリ

データ可視化のためのライブラリには、グラフ構造を扱えるものが多く、D3.js や Vis.js はかなり前から良く活用されている印象です。
比較的よく名前の聞くライブラリの特徴を挙げておきます。

D3.js:

D3.js は、データ駆動のドキュメントを作成するための強力なビジュアライゼーションライブラリで、グラフやネットワークのビジュアライゼーションに関する高度な機能もあります。

Cytoscape.js:

Cytoscape.js は、グラフ理論の分析やビジュアライゼーションのためのライブラリです。ノードとエッジのスタイルやレイアウト、インタラクティブな操作に強みがあります。

Vis.js:

Vis.js は、数学で扱う関数を表すグラフを描画するためのライブラリですが、vis-network というモジュールをインストールするこにより、簡単にグラフをビジュアル化することができるようになります。物理エンジンを有効にすると、うねうねと動くようなネットワーク図を扱うことができます。

sigma.js:

sigma.js は、WebGLを使用した大規模グラフのビジュアライゼーションを高速に描画できるライブラリです。ノードやエッジ数が膨大になるグラフデータを描画する際には有効です。

次のサイトに、ビジュアルライブラリではないグラフライブラリ graphlib, graphology, ngraph.graph の３つの比較がされております。

このなかで、最近 は、graphology に注目しておりますが、比較サイトに紹介されているとおり、次のような特徴があります。

graphology:

• graphology は、純粋なJavaScriptで書かれたグラフ理論のためのライブラリで、グラフの作成や分析に使用することができます。ただし、ビジュアライゼーションの部分は含まれておりません。
• パフォーマンス：複雑なグラフ操作を効率的に処理できるように設計されており、大規模なデータセットでも高いパフォーマンスを維持します。
• 拡張性：プラグインシステムをサポートしており、ユーザーが独自のアルゴリズムや機能を追加することができます。

graphology のサンプル実装

graphology を用いた超簡単な例題を２つほど紹介します。

グラフのimport/export

const Graph = require('graphology')

// グラフを作成
const graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addEdge('A', 'B');

// JSON にエクスポート
const json = JSON.stringify(graph.export());
console.log('グラフのJSON:', json);

// JSON をインポート
const newGraph = new Graph();
newGraph.import(JSON.parse(json));
console.log('インポートしたノード:', newGraph.nodes()); // ['A', 'B']

実行結果

グラフのJSON: {"options":{"type":"mixed","multi":false,"allowSelfLoops":true},"attributes":{},"nodes":[{"key":"A"},{"key":"B"}],"edges":[{"key":"geid_88_0","source":"A","target":"B"}]}
インポートしたノード: [ 'A', 'B' ]

graphology には、Plugin的にアルゴリズムが準備されており、PageRankについての例が以下になります。
※事前に npm install graphology-metricsを実行して該当のアルゴリズムをインストールしてから実行します。

PageRankを計算する

const Graph = require('graphology')
const metrics = require('graphology-metrics/centrality')

// グラフ作成
const graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');

// PageRank の計算
const ranks = metrics.pagerank(graph);
console.log('Pagerank:', ranks);

実行結果

Pagerank: {
  A: 0.11615558155321362,
  B: 0.2148878552074298,
  C: 0.2988109016680539,
  D: 0.3701456615713026
}

おわりに

最後に、本稿を記載するために検証した環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。

macOS: Sequoia 15.3.2 (chip: Apple M1)
node: v22.14.0
npm: 10.9.2

ご一読いただきまして有り難うございます。

（●）（●） Happy Hacking!
/""　＿＿""＼