29

私が必要としているのは、純粋な数学グラフのJavaScript実装です。明確にするために、私はsigma.jsやd3.jsのようなグラフ視覚化ライブラリを意味するのではありません。

私が探しているライブラリは、次の機能を実装します。

  • 有向および無向グラフオブジェクトの作成
  • 加重および非加重のgrapsオブジェクトの作成
  • グラフへの頂点とグラフからの頂点とエッジの追加/削除
  • 頂点とエッジにラベルを追加する（つまり、追加のメタデータ）
  • 基本的なグラフ検索と、深さ優先探索、幅優先探索、ダイクストラのアルゴリズム、A*などのトラバーサルアルゴリズムの実装。

誰かがすでに存在するかどうか知っていますか？

4

8 に答える 8

23

今、ライブラリがあります：graphlib

Graphlibは、無向および有向のマルチグラフのデータ構造と、それらで使用できるアルゴリズムを提供するJavaScriptライブラリです。

実装：

  • 有向グラフと無向グラフ（A->BはB->Aを意味します）
  • マルチグラフ（A-> Bからの複数の異なる名前付きエッジ）
  • 複合グラフ（ノードは「サブグラフ」を形成する子を持つことができます）
  • ダイクストラアルゴリズム（最短経路）
  • Floyd-Warshallアルゴリズム（負の重みをサポートする最短経路）
  • プリムのアルゴリズム（最小全域木）
  • Tarjanのアルゴリズム（強く接続されたコンポーネント）
  • トポロジカルソート（有向非巡回グラフの依存関係ソート）
  • 注文前および注文後のトラバーサル（すべてのノードでのコールバック）
  • すべてのサイクルを見つけて、グラフが非巡回であるかどうかをテストします
  • 接続されているすべてのコンポーネントを検索する

NPM、バウアーとブラウザがサポートされている、MITライセンス。

于 2016-01-19T16:04:29.383 に答える
4

数か月前に、JavaScriptでさまざまなCSアルゴリズムを実装したリポジトリを作成しました。グラフを使用したアルゴリズムもいくつかあります。私はそれを拡張する予定です（スパニングツリー、ヒューリスティックアルゴリズムはおそらくクロマチックグラフ）が、それ以来、あなたを助けることができるアルゴリズムはまだ少ないと思います。

于 2013-01-23T21:30:34.400 に答える
1

StackOverflowの同様の質問の推奨事項の助けを借りて、私は同様のトピックを持ついくつかの質問を見つけました。

最初のもの、Javascript有向非巡回グラフライブラリ？（グラフの視覚化は必要ありません）、近いです。そこでnrabinowitzはdata.jsをチェックすることを提案しています。data.jsのソースをすばやく閲覧しました。それは実際にグラフを処理するためのインターフェースを提供しますが、それは非常に基本的な方法でのみです。そこにはトラバーサルアルゴリズムはありません。また、data.jsの目標は、包括的なグラフライブラリ以外のもののようです。

2つ目は、グラフ操作用のJavascriptライブラリです。これとほぼ同じ質問ですが、実際の回答はまだありません（2013-01-23 17:32）。著者c0dem4gneticはNetworkXを参照しています。これは私が必要としているものですが、残念ながらPythonでのみ実装されています。

そのようなライブラリを自分で実装するのは少し楽しみです。グラフはとてもクールです。

于 2013-01-23T15:41:58.713 に答える
1

javascriptでグラフアルゴリズムライブラリ https://github.com/devenbhooshan/graph.jsを作成しました。ライブラリはクリーンで非常にシンプルです。とても使いやすいです。プロジェクトにgraph.jsファイルを接続して、使用を開始するだけです。

于 2014-04-03T19:03:44.153 に答える
1

js-graph-algorithmsもあります。これはかなりクリーンに見え、いくつかのアルゴリズムがあります。ただし、そのAPIはかなり基本的です。

于 2018-07-29T12:30:20.253 に答える
1

Typescriptgraphlibのサポートも含む、現在維持されている減価償却の代替案は、筆跡学です。

などの拡張機能と組み合わせると、必要なすべての機能をサポートしているようgraphology-shortest-pathです。

于 2022-01-12T04:28:13.513 に答える
0

Javaライブラリにアルゴリズムがあります。JavaScriptライブラリに追加するための空きスロットを見つけようとしています。これは今は役に立ちませんが、後の視聴者にとっては役立つかもしれません。

于 2013-01-23T16:29:40.350 に答える
0

JavaScriptで実装されたTarjanの強力に接続されたコンポーネントアルゴリズムは次のとおりです。https ：//www.vacilando.org/article/javascript-implementation-tarjans-cycle-detection-algorithm

于 2022-02-17T16:38:24.063 に答える