問題タブ [graph-traversal]

HashMap <String,ArrayList<String>>単語とその同義語を保持するためにを使用してシソーラスを構築しています（このデータ構造が必要です）。

割り当ての目的上、同義関係は推移的と見なされます。（シソーラスをグラフとして想像することができます）。私が達成しようとしているのは、このグラフをテキストファイルに印刷し、各行にコンポーネントを接続することです。つまり、同義語として一緒にプールできるすべての単語は1行にまとめる必要があります。

これは私がそれが起こることをどのように描いたかです：

各同義語と一緒に単語を印刷してから、それらの同義語をデータ構造から削除して、重複する行がないようにします。

もちろん問題は、ハッシュマップの内容を繰り返し処理している間は何も削除できないことです。

私が見逃している代替アプローチはありますか？

PS私は、タイトルが雄弁で簡潔である必要があるという理由だけで、「グラフ」のメタファーをずっと維持しています。私は、この比喩の有用性が限られていることを理解しています。

抽象的問題：約250,000ノードのグラフがあり、平均接続数は約10です。ノードの接続を見つけるのは長いプロセスです（たとえば、10秒）。ノードをデータベースに保存するのにも約10秒かかります。ノードがデータベースにすでに存在するかどうかを非常にすばやく確認できます。同時実行を許可しますが、一度に10を超える長いリクエストがない場合、グラフをトラバースして、最高のカバレッジを最も速く取得するにはどうすればよいでしょうか。

具体的な問題：ウェブサイトのユーザーページをスクレイプしようとしています。新しいユーザーを見つけるために、私は既知のユーザーから友達リストを取得しています。グラフの約10％を既にインポートしましたが、サイクルでスタックしたり、ノードが多すぎてメモリを使いすぎたりします。

私の現在の実装：

現在の実装の問題：

• すでにインポートしたクリークでスタックするため、時間が無駄になり、インポートするスレッドがアイドル状態になります。
• 彼らが指摘されるにつれて、さらに追加されます。

したがって、完全な書き直しだけでなく、わずかな改善も歓迎します。ありがとう！

まず、はい、これは私の Perl クラスの宿題プロジェクトです。私は答えを探しているわけではありません（それは甘いでしょうが）。私が理解しているように、使用するデータを整理するには、BFS と正規表現を使用する必要があります。これについて何らかの方向性が必要です。BFS を使用するにはどうすればよいですか? 大規模なスタックを使用して、スタック内の各アイテムを調べますか? 巨大なハッシュ テーブルを使用する必要がありますか? 誰かがこの問題に取り組んだことがありますか? どうやってやりましたか？方向性が必要なだけです。これはBSTに似ていますか？これは、グラフモジュールを使用せずに可能ですか? これはハッシュ値を使用して可能ですか?

開始ノードを選択してからDFSを介して続行することにより、重み付けされていない非巡回有向グラフをトラバースする特定のグラフアルゴリズムがあるかどうか知りたいです。検索されていない先行ノードがあるノードが検出された場合、開始するすべてのパスが探索されるまで、着信パスをバックトラックする必要があります。

グラフアルゴリズムのウィキペディアカテゴリを見つけましたが、ここにはアルゴリズムの小さな海があり、それらのほとんどに精通していません。

編集：例：グラフ{AB、EB、BC、BD}が与えられた場合、{A、B、E、B、C、D}としてトラバースするか、{A、B、E、C、D}として一意の順序でトラバースします。BFSやDFSとは異なり、このアルゴリズムは、最初の開始ノードのすべてのパスが使い果たされた場合に、新しい開始ノードで再開する必要がないことに注意してください。

これは、おそらく最適な解決策がない問題です。有向グラフがあり、サイクルがあるかどうかわからないとします (サイクル検出は、この問題の側面の 1 つになります)。一連の頂点 (おそらく数百万の頂点) が与えられた場合、特定のグラフのすべての一意のペア間のすべての個別のパス (重複する頂点のないパス) をカウントする必要があります。この状況にどう立ち向かうか。

これを行うための強引な方法を見てみましょう。

• グラフからすべての可能なペアを計算します。

• グラフのペアごとに、DFS を使用してソースから宛先へのすべてのパスを取得します。

• ペアがハッシュ テーブルで表されていると仮定すると、このペアに対する値としてパス カウントを入れます。
• 残りのペアについて繰り返します。

これで問題が発生する可能性があることを指摘できますか? この問題をこのように考えてみましょう。地球上のすべての都市間のすべての個別の経路を見つける計算上の課題は何ですか?また、この問題を解決しようとする場合、どこから始めればよいでしょうか?

編集:提示されたアルゴリズムの一部は、O(n!) 階乗時間で結果を生成します。これは、処理するリソースが限られている単一のマシンにとっては、やや困難な計算です。グラフ トラバーサルの問題を小さなチャンクに分割するための map-reduce テクニックを知っている人はいますか?

タイトルが少し乱雑であることは知っていますが、それをよりよく説明する方法がわかりません。

私がやろうとしていること：

テキストファイルで見つかったグラフを使用して、頂点Aから頂点Bまでの最短経路（頂点の最小量）を見つけて印刷します。

注：ダイクストラ法ではなく、幅優先探索を使用します。

私が持っているもの：

グラフにBFSを適用する実用的なアルゴリズムですが、実際に最短経路を印刷する良い方法はありません。

最短経路の頂点と、アルゴリズムを介して実行されるが最短経路ではない頂点を区別するのに苦労しています。

例：0と4の間の最短パスを見つけます。0は1,2と3に接続します。1は4に接続します。私のパスは[0,1、1ではなく[0,1,2,3,4]になります。 4]。

同じ質問をしているスレッドや、これを含むBFSのウォークスルーを見つけることができなかったので、これを実際よりもはるかに難しくしているのかどうかわかりません。

編集：興味があるかもしれない人のためのコード（私がサークルを避けているかどうかはまったくわかりませんか？）

編集2：スタックへのパスを保存する方法を変更しました。

変数とメソッドの説明：

v=原点

w=ターゲット頂点

g=グラフ

vi=vの近傍を反復処理する通常の反復子

読んでくれてありがとう！

私は、できればvalsと不変のデータ型を使用して、グラフScalaスタイルをトラバースするための適切な方法を見つけようとしています。

次のグラフを考えると、

出力を、特定のノードで開始する深さ優先走査にします。たとえば、1から始めて、たとえばを生成する必要があります1 2 3 0 4。

可変コレクションまたは変数なしでこれを行うための良い方法を理解できないようです。どんな助けでもいただければ幸いです。

信号フローベースの「プログラム」（たとえば、Simulinkに似たもの）のグラフがあると仮定します。つまり、いくつかの開始ノードといくつかの終了ノード、およびその間に多数のノードがある有向グラフがあります（循環関係がないことを願っています）

そのグラフをたどって計算順序を教えてくれる、よく知られているアルゴリズム（おそらくPythonライブラリとしても利用可能）はありますか？

例（方向は示されていません、明白であると仮定してください）：

これにより、指示/順序が表示されます。

ありがとう！

一連のプラグインを実行するアプリケーションを設計しています。プラグインの実行は、別のプラグインの実行に依存する場合と依存しない場合があります。つまり、一部の (すべてではない) プラグインは、実行を開始する前に他のプラグインが実行されることを期待しています。

依存しているプラ​​グインの前にプラグインが実行されないように、正しい実行順序を導き出す必要があります。

グラフ理論を使用してこれを解決できると思います (プラグインを頂点として、依存関係をエッジとして、何らかのトラバーサルを使用して実行順序を導出します)。

アプリケーションは Java で開発されているため、JGraphT を使用する予定です。

ケースを解決するためのヘルプまたはポインター??? Javaコード全体を期待しているわけではありません.グラフ理論（使用するアルゴリズム）に関するポインタはすべて同様に役立ちます....

ありがとう ！！！

[解決策:] @Artium は解決策につながります。このリンクは非常によく似た実装を示しています。

パスワードのキーボード実行のリストを作成または検出する方法を探しています。

必要な特殊文字の長さや数などのパスワード基準で問題を制限できます。

単純なキー実行の例は、「6yhn^YHN」または「zse4ZSE$」です。

より複雑なキー ランは、'V' や 'X' などのさまざまな形にすることができます (例: "mko0mju7MKO)MJU&")。

これの最初のアイデアは、大規模なパスワード ダンプの統計分析を行い、キー ラン オンリー パスワードの普及を確認することでしたが、パスワード強度強制ツールに積極的に応用できると思います。