欠けているデータ型を求めて
- グラフはノードの集合であり、矢印（エッジ）で接続される。
- ノードとエッジにはデータを含められる。
- ソフトウェアエンジニアリングにおいて、グラフはパッケージ依存関係、インターネットのリンク、ソフトウェアの状態空間、関係データベース、連結リスト、二分木、ハッシュテーブルなど、さまざまな形で存在する。
- ビジネスロジックでも、グラフは引用の参照、交通ネットワーク、ソーシャルネットワークなどに活用される。
- ソフトウェア開発を長くしていれば、どこであれグラフに出会う可能性が高い。
グラフ利用への悩み
- グラフは有用だが、実際のコードでグラフを使うのは負担が大きい。
- ほとんどの主要な言語ではグラフを組み込み型としてサポートしておらず、標準ライブラリでもまれで、堅牢なサードパーティライブラリも多くない。
- グラフを自分で実装しなければならないことが多い。
- ソフトウェアエンジニアがグラフを使える頻度と、プログラミングエコシステムにおける支援との間にはギャップがある。
グラフ型がない理由
設計上の選択肢が多すぎる
- 有向グラフと無向グラフ、単純グラフと多重グラフ、ハイパーグラフ、ウーバーグラフなど、さまざまなグラフの種類が存在する。
- 各種類について、ノードとエッジに ID を与えるか、どのようなデータを保存するかといった決定が必要になる。
- あらゆる可能性をサポートする完璧なグラフライブラリには多くの時間が必要になる。
- グラフアルゴリズムでは性能が重要であり、特殊なケースも重要になる。
- グラフアルゴリズムを正しく実装するのは難しい。
実装上の選択肢が多すぎる
- 単純な有向グラフだけをサポートすると仮定しても、グラフを内部的に表現する方法は複数ある。
- エッジリスト、隣接リスト、隣接行列、構造体の集合など、さまざまな保存方式が存在する。
- グラフ操作によって、表現方式ごとに異なる性能特性を持つ。
- グラフの疎密に応じて、最適な内部表現は変わる。
- ノードデータ、エッジデータ、さまざまな種類のノードやエッジを実装することはさらに複雑である。
性能が重要すぎる
- 多くのグラフアルゴリズムは NP 完全問題か、それ以上に難しい。
- グラフは非常に大きな問題になり得るため、表現方式やアルゴリズム実装の詳細によって性能が大きく変わる。
- データ表現とアルゴリズムに対する多くの制御が必要になる。
一致した見解
- 多様なグラフの種類、表現、アルゴリズム、性能への敏感さ、大規模グラフで高コストなアルゴリズムを実行することなどが、グラフ支援が広く普及していない理由である。
- これは、言語が標準ライブラリでグラフをサポートしない理由を説明している。
- これは、プログラマーがサードパーティのグラフライブラリを避ける理由を説明している。
- グラフを使うのが難しいため、極端な状況でなければグラフとして考えたくない理由を説明している。
GN⁺の見解
- この記事は、なぜグラフがプログラミング言語やライブラリで基本的なデータ型として定着しなかったのかについて洞察を与えてくれる。
- グラフ理論はコンピュータサイエンスの重要分野であり、アルゴリズム、ネットワーク分析、データベースなど幅広い領域で応用されている。
- グラフを効果的に使うには、性能最適化と適切なデータ構造の選択が重要である。
- サードパーティライブラリとしては NetworkX、Boost Graph Library、Graph-tool などがあり、これらはさまざまなグラフ問題の解決に使える。
- グラフを使う際には、問題の特性に合ったグラフの種類とアルゴリズムを選ぶことが重要であり、これはシステム性能に直結する。
1件のコメント
Hacker Newsのコメント
Graphviz は独自のグラフライブラリを持っており、これは他のプロジェクトでは使われていない。このライブラリには長所と短所がある。
.NET でコーディングしているなら、小規模で機能は多くないがグラフライブラリの Arborescence を試してみてほしい。
グラフはデータ構造やデータ型ではなく、抽象化である。
プログラミング言語に組み込みのグラフデータ型がない理由について、これまで何度も質問されてきた。
中心的な障害は次のとおりだ:
この記事は、プログラミング言語でグラフ アルゴリズム がより良くサポートされていない理由という問いに、ほぼ答えている。
グラフ描画ツールも非常に残念だ。
この記事は本当に素晴らしい。
Electric Clojure は、Clojure 自身（s-式）をグラフ記述構文として使っている。
テーブル（データベース内のテーブルのような）という、もう 1 つの有用なデータ型がある。