問題タブ [graph-traversal]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
neo4j - グラフ走査における Neo4j と Apache Giraph の比較
Apache Giraph対Neo4j : これら 2 つのグラフ処理システムでは、ノード間のトラバーサル アルゴリズムはまったく異なりますか? 単一のマシン (分散されていない) に保存されたデータに対して Giraph と Neo4j を使用してソーシャル グラフをトラバースするとしたら、どちらがより優れたパフォーマンスを発揮し、なぜでしょうか?
graph - 何ホップかかりますか？
メッセージが地球上のすべての人に理論的に到達するのに必要なホップ数 (つまり 80 億) を決定した実験に関する情報を探しています。したがって、すべての受信者がメッセを X 人の連絡先に転送する場合、地球の人口に到達するには Y ホップかかることになります。Yが驚くほど低く、Xも高くなかったことだけは覚えています。
実験の名前やその他の情報を教えてください。
ありがとう
c# - C# 最小最大グラフ検索
編集 3: わかりました、コードを動作させることができましたが、たとえば 16 ノードと 11 を超える検索深度を使用している場合、大量のメモリ消費の問題に直面しています。
soemone がコードをチェックして、メモリ リークを修正する方法を教えてください。
完全なコードは次のとおりです。
algorithm - 指定された基準に従って、グラフ内の 2 つのノード間のパスを見つける - 最適化タスク
次の問題があります。私は循環的で無向の加重グラフ G=(V,E) を持っています。次のルールに従って、指定された 2 つのノード間の単純なパス (サイクルなし) を見つける必要があります。
- 各可能なパスのエッジセットで最小の重み値を見つける
- 見つかったパスから選択された最小値の中で最大の最小値を持つこのパスを選択します
たとえば、以下に示すグラフがあります。
ノード 1 からノード 8 への単純なパスを見つけることができます。次に示す 2 つのパスが考えられます。
- 1 -> 3 -> 5 -> 8、このパスの最小エッジ ウェイトは 2 です
- 1 -> 3 -> 5 -> 6 -> 7 -> 8、このパスの最小エッジ ウェイトは 283 です。
提示された基準によると、必要なパスはパス番号 2 です。これは、パス番号 1 よりも最小値が大きいためです。
1 つの重要な仮定: グラフ内のノードの数は非常に少なく、15 未満です。
Dijkstra または Bellman-Ford アルゴリズムの変更について考えましたが、課題は、ローカル基準 (最小距離) がないことです。パス全体を取得しない限り、エッジの最小の重みを見つけることができません...
私の 2 番目の考えは、Nearest-Neighbor アルゴリズムの修正を使用することでしたが、これは、いわゆる巡回セールスマン問題を解決するために使用されます。これは、私の場合とは少し異なります。
私の質問は次のとおりです。この問題を解決するには、Depth-First Algorithm を使用して 2 つの特定のノード間のすべての直接的な非巡回単純パスを取得し、次に見つかった各パスの最小重み値の最大値を選択するよりも良い方法はありますか?
そのような場合、特に再帰とグラフ内の可能な接続 (エッジ) の数のために、DFS アルゴリズムの複雑さが少し心配です。
アイデアをありがとう。
cuda - CUDA スレッド間で非常に不規則なジョブを共有する
グラフ トラバーサル (ビタビ アルゴリズム) に関連するいくつかのタスクに取り組んでいます。アクティブな状態の圧縮されたセットがあるたびに、いくつかのジョブが各状態で実行され、結果が出力アークを介して各アークの宛先状態に伝播されます。新しいアクティブな状態のセットが構築されます。問題は、出力アークの数が 2 つまたは 3 つから数千まで非常に大きく変化することです。そのため、計算スレッドは非常に非効率的にロードされます。
共有ローカル メモリ キューを介してジョブを共有しようとしています
ただし、アクティブ セットはすべての状態の 10 ～ 15% ですが、アクティブ セットが使用されていない場合 (アクティブ セット = すべての状態) よりも遅くなります。レジスタンスの圧力が大幅に上昇し、稼働率は低いですが、それについては何もできないと思います。
スレッド間でジョブを共有するためのより効果的な方法があるでしょうか? 3.0 でのワープ シャッフル操作について考えてみますが、2.x デバイスを使用する必要があります。
python - ツリー内の 2 つのノード間の (保証された一意の) パスを見つける
(おそらく) 単純なグラフ トラバーサルの質問があります。私はグラフのデータ構造として networkx を使用するグラフ初心者です。私のグラフは常に次のようになります。
ルート ノードから特定のノードへのパスを返す必要があります (例: を返す必要がありますpath(0, 11)) [0, 8, 9, 11]。
ツリーをトラバースするときにパスがどのように見えるかを追跡するために拡大および縮小するリストを渡すことで機能するソリューションがあり、最終的にターゲットノードが見つかったときに返されます。
この「パス」リストを渡す必要がないことを骨の髄まで感じています...コールスタックを使用してその情報を追跡できるはずですが、方法がわかりません...誰かが啓発できますかパスを追跡するためにスタックを使用してこの問題を再帰的に解決する方法について教えてください。