問題タブ [directed-graph]

ウィキペディアによると、Tarjan の強連結成分アルゴリズムを Python で実装しましたが、うまくいきません。アルゴリズムは非常に短く、違いを見つけることができないため、なぜ機能しないのかわかりません。元の紙を調べてみましたが、見つかりませんでした。

これがコードです。

必要に応じて、グラフを視覚的に確認できます。ご覧のとおり、これはウィキペディアの疑似コードをかなり前向きに翻訳したものです。ただし、これは出力です。

強連結成分は 3 つではなく、1 つだけにする必要があります。質問がすべての面で正しいことを願っています。そうでない場合は申し訳ありません。いずれにせよ、ありがとうございました。

これは、tarjan のサイクル検出の実用的な C# 実装です。

アルゴリズムはここにあります: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

DepGraph は単なる Vertex のリストであることに注意してください。Vertex には、エッジを表す他の Vertex のリストがあります。また、index と lowlink は -1 に初期化されます

編集:これは機能しています...結果を誤解しただけです。

免責事項: 著者は Erlang の初心者です。

Erlang である種の最短経路アルゴリズムを実装したいと考えています。

Erlang にはグラフ データ構造の標準実装があります: http://www.erlang.org/doc/man/digraph.html

ただし、それが使用する実際のデータ構造に関する情報は見つかりませんでした。

主に私が知りたいのは：

• 頂点アクションのすべての「隣人」を取得する最悪のケースのパフォーマンスは?
• グラフから頂点をフェッチする最悪の場合のパフォーマンスは?

次の事実を含むグラフが与えられます。

cycle(X)そして、ノード から始まるサイクルがあるかどうかを決定するルール を定義するよう求められますX。

これを行う方法が本当にわかりません。ノードをトラバースして、次のノードが最初のノードになるかどうかを確認しようとしましたが、機能しないようです

免責事項：著者はErlangの初心者です。

想像してみてください。1Mノードで構成されるグラフがあり、各ノードには0〜4個の隣接ノードがあります（エッジは各ノードからそれらの隣接ノードに出ているため、グラフは方向付けられて接続されています）。

これが私のデータ構造の選択です：

グラフを保存するには、ETSテーブルに基づく有向グラフを使用します。これにより、ノードのネイバーへの高速（O（1））アクセスが可能になります。

未訪問のノードのリストには、gb_sets：take_smallestを使用します（ノードは既にソートされており、フェッチ後に同時に削除されます）。

先行のリストには、dict構造を使用します。これにより、先行を次の方法で格納できます：{Node1、Node1_predecessor}、{Node2、Node2_predecessor}。

訪問したノードのリストには、単純なリストを使用します。

問題：

1. 有向グラフ構造とUnvisited_nodes構造の両方でノードの重みを更新しようとすると、コードの読み取りと保守が非常に困難になります。2つのデータ構造で同時に更新する必要がある「フィールド」を持つ1つの「オブジェクト」を保持するのは正しい方法ではないようです。それを行う正しい方法は何ですか？
2. 同じ質問が前任者リストについてです。ノード「オブジェクト」の先行「フィールド」をどこに保存する必要がありますか？多分グラフ（有向グラフ構造）にありますか？
3. オブジェクト（ノードとエッジ）とそのフィールド（重み）ではなく、プロセスとメッセージの観点から、ダイクストラのアルゴリズム全体を再考する必要があるかもしれません。

UPD：

アントナコスの推奨に基づくコードは次のとおりです。

2 つの有向パスを持つ有向グラフがあります。

2 つのパスの類似性を判断するアルゴリズムが必要です。

この投稿では、レーベンシュタイン距離を使用しておおよその類似性を判断することについて言及しています。また、ハミング距離も同様のメトリックを使用していることに気付きました。

私の質問は：

2 つのパスが互いに平行に走っている場合、どのように処理しますか。つまり、2 つのパスに類似したノードがない場合でも、それらのパスは互いに非常に近くを同じ方向に移動するため、「類似」と見なされます。

ありがとう

私は NetworkX で有向グラフのコードに取り組んでおり、プログラミング経験が疑わしい結果である可能性が高いブロックにぶつかりました。私がやろうとしていることは次のとおりです。

有向グラフ G があり、上部に 2 つの「親ノード」があり、そこから他のすべてのノードが流れます。このネットワークをグラフ化するとき、「親 1」の子孫であるすべてのノードをある色でグラフ化し、他のすべてのノードを別の色でグラフ化したいと思います。つまり、親 1 の後継者のリストが必要です。

現在、次を使用してそれらの最初のレイヤーを簡単に取得できます。

問題は、これが私に後継者の第 1 世代しか与えないことです。できれば、後継者の後継者、後継者の後継者などを希望します。任意に、何世代が含まれているかを正確に知らなくても分析を実行してグラフを作成できると非常に便利だからです。 .

これにアプローチする方法はありますか？

SVG有向グラフにいくつかのインタラクティブ機能を追加する必要があります。

これまでのところ、表示したいグラフはドットファイルから生成され、SVGとしてレンダリングされています。そのようなSVGドキュメントに双方向性（おそらくJavascriptを使用）を追加する簡単な方法があるかどうか知りたいです。

私が必要としているのは、マウスがノードの上を通過したときにいくつかの情報を表示し、2つのノードを比較できるようにすることです。

私のモデルは自動的に生成されるので、ドットで生成されたSVGを保持し、別のJavascriptを使用して追加情報を追加したいと思います。

これを使用して周期的な有向グラフを表すことに大きな障害はありますか?

編集：

これは、おそらく必要以上に混乱を招きました。これは RPG の会話グラフで、これまでに得たものです。これをより単純な形式にリファクタリングできるかどうかを判断しようとしていました。

NPC 用に初期化:

応答オプション付きの会話の一部:

マップ内の別のダイアログにループバックできる応答の選択肢:

河川の流れの関係を表す一対の値のリストを含むデータファイルがあります。

ファイルはこの構造を持っています

私がする必要があるのは、このファイルを読み取ることです。次に、特定のノードについて、すべての UPSTREAM ノードを出力する必要があります。

上記の例で C を入力すると、E、B、A となります。

私は Linux ボックスで perl を使用しており、これを書いている相手もそうです。ありがとう。