問題タブ [graph-theory]

Python で大きな (10^7 ノード) グラフを操作できるようにする必要があります。各ノード/エッジに対応するデータは最小限です。たとえば、少数の文字列です。メモリと速度の点で、これを行う最も効率的な方法は何ですか?

dict の dict はより柔軟で実装が簡単ですが、リストのリストの方が高速であると直感的に期待しています。リストオプションでは、データを構造とは別に保持する必要もありますが、辞書では次のようなものが許可されます。

何を提案しますか？

はい、効率の意味をもう少し明確にする必要がありました。この特定のケースでは、ランダムアクセス検索の観点からそれを意味します。

データをメモリにロードすることは大きな問題ではありません。それは一度だけ行われます。時間のかかる部分は、ノードにアクセスすることです。そのため、情報を抽出して、関心のあるメトリックを測定できます。

各ノードをクラスにすることは考えていませんでした (プロパティはすべてのノードで同じです)。私は、誰かが共有できる同様のケースで直接の経験を持っていることを望んでいました. 結局のところ、グラフは CS で最も一般的な抽象化の 1 つです。

これらのデータ構造の両方で解決できる最も一般的な問題は何ですか?

次のような本についての推奨事項もあるとよいでしょう。

• 構造を実装する
• それらを使用するアルゴリズムの推論を実装して説明する

フラット ファイルとリレーショナル データベースは、構造化データをシリアル化するメカニズムを提供します。XML は、構造化されていないツリー状のデータをシリアル化するのに優れています。

しかし、多くの問題はグラフで表現するのが最適です。たとえば、熱シミュレーション プログラムは、抵抗エッジを介して互いに接続された温度ノードで動作します。

では、グラフ構造をシリアライズする最良の方法は何でしょうか? リレーショナル データベースがオブジェクトの複雑な Web をシリアル化できるのと同じ方法で、XML がある程度それを実行できることを私は知っています。XML は通常は機能しますが、簡単に醜くなる可能性があります。

Graphviz プログラムで使用されるドット言語については知っていますが、これが最適な方法かどうかはわかりません。この質問は、おそらく学界が取り組んでいるようなものであり、これについて議論している論文への参照があれば幸いです.

いくつかの異常な特性を持つグラフ アルゴリズムを探しています。

グラフの各エッジは、「上」エッジまたは「下」エッジのいずれかです。

有効なパスは、無数の「上」の後に無数の「下」が続くか、またはその逆になります。ただし、一度しか方向を変えることはできません。

たとえば、有効なパスは A "up" B "up" C "down" E "down" F で、無効なパスは A "up" B "down" C "up" D です。

2 つのノード間の最短の有効なパスを見つけるための適切なアルゴリズムは何ですか? 等しい長さの最短経路をすべて見つけるのはどうですか?

グラフについて何も知らなくても、2 つのノード間の幅優先トラバーサルを追跡するための適切なアプローチを探しています。対 深さ優先 (パンアウトしない場合はパスを破棄できます) では、トラバーサル中にかなりの数の「開かれた」可能性がある場合があります。

以下で説明するタスクを達成するために、最適な時間効率の良いアルゴリズムを決定しようとしています。

私はレコードのセットを持っています。このレコードのセットには、このセットのレコードのペアが互いにどのように接続するかを示す接続データがあります。これは基本的に無向グラフを表し、レコードが頂点、接続データがエッジになります。

セット内のすべてのレコードには接続情報があります (つまり、孤立したレコードは存在しません。セット内の各レコードは、セット内の 1 つ以上の他のレコードに接続されます)。

セットから任意の 2 つのレコードを選択し、選択したレコード間の単純なパスをすべて表示できるようにしたいと考えています。「単純なパス」とは、パスに繰り返しレコードがないパス (つまり、有限パスのみ) を意味します。

注: 選択された 2 つのレコードは常に異なります (つまり、開始頂点と終了頂点が同じになることはありません。サイクルはありません)。

例えば：

開始レコードとして B を選択し、終了レコードとして E を選択した場合、レコード B をレコード E に接続するレコード接続を通るすべての単純なパスを見つけたいと思うでしょう。

これは一例です。実際には、数十万のレコードを含むセットがある場合があります。

ASPのWebページにグラフを描画しようとしています。APIが役立つことを願っていますが、今のところAPIを見つけることができませんでした。

グラフには、ラベル付きノードとラベルなし方向エッジが含まれています。理想的な出力は次のようになります。

誰かが助けることができるよりも事前に構築されたものを知っていますか？

私はYahooPipes（http://pipes.yahoo.com/pipes/）のインターフェースが本当に好きで、別の問題に対して同様のインターフェースを作成したいと思っています。同じ基本的なルックアンドフィールでインターフェイスを作成できるライブラリはありますか？

私は特にパイプがどのように振る舞うか、そしてそれらが単なる直線ではない方法が好きです。

編集：アプリケーションはWebベースになります。私はFlashまたはJavascriptを使用することにオープンです。

それで、私は MIT の OpenCourseWare から Discrete Math コースを受講していますが、疑問に思っています...関係とグラフの関係はわかりますが、それを「所有」するには十分ではありません。私は単純なステート マシンを SQL にも実装したので、関係とセットがどのように完全に適用されるかについてのより厳密な研究ではなく、グラフをかなりよく理解しています。すぐには理解できないものをざっと見て、もっと学んだときに戻ってくるというYeggeの一連の思考に従うべきですか？日々作成しているグラフ構造をよりよく分析できるようになりたいと思っています (面白そうです)。また、今すぐ貴重な情報を逃さないようにしたいと思っています。

（編集：さまざまな集合と関係のプロパティがグラフ理論などにどのように関連しているか、および基本的なグラフ理論が集合/関係にどのように関連しているかについて、より良いアイデアを得たいと思います。）

これについてもっと学ぶことができる良いリソースはありますか? 重要な場合に備えて、Rosen の Discrete Mathematics and Its Applications の第 5 版を使用しています。

ありがとう！

AI の本の 1 つで、よく知られている「15 パズル」を解決するために、シミュレーションやゲームでパスを見つけるための一般的なアルゴリズム (A-Star、Dijkstra) も​​使用されていることを読みました。

これらのアルゴリズムの1つを適用できるように、15パズルをノードとエッジのグラフに縮小する方法について、誰かが私にいくつかの指針を与えることができますか?

グラフの各ノードをゲームの状態として扱うとしたら、そのツリーは非常に大きくなりませんか? それとも、それはそれを行うための方法ですか？