問題タブ [cyclic-graph]

有向グラフが循環的かどうかをどのように検出できますか? 幅優先探索をしようと思ったのですが、よくわかりません。何か案は？

ここに投稿されたほとんどの質問は、最長のパスを除いてすべて解決しました。最長パスに関するウィキペディアの記事を読んだことがありますが、グラフが非循環的である場合は簡単な問題のようですが、私の場合はそうではありません。

どうすれば問題を解決できますか？可能性のあるすべてのパスをチェックして、力ずくで？どうすればそれを始められますか?

〜18000のグラフで多くの時間がかかることはわかっています。しかし、とにかくそれを開発したいのは、プロジェクトに必要なためです。テストして、実行時間がわずか 1 秒または 2 秒の小さなスケールのグラフでインストラクターに表示します。

少なくとも私は必要なすべてのタスクを実行し、それが機能するという概念実証を実行していますが、巡回グラフにはこれ以上の方法はありません。しかし、これらすべてのパスのチェックをどこから開始すればよいかわかりません...

クラス用にカタンの入植者のクローンを書いています。追加のクレジット機能の 1 つは、どのプレーヤーが最長の道路を持っているかを自動的に決定することです。考えてみたところ、深さ優先検索のわずかなバリエーションが機能するように思えますが、サイクル検出をどうするか、プレイヤーの 2 つの最初の道路ネットワークの結合を処理する方法を理解するのに苦労しています。と他のいくつかの細目。どうすればアルゴリズム的にこれを行うことができますか?

このゲームに慣れていない人のために、問題を簡潔かつ抽象的に説明しようと思います。無向巡回グラフで可能な最長パスを見つける必要があります。

この単純なクラスがあるとします：

ペアの巡回グラフを生成することは不可能です。

同様のクラスを作成するにはどうすればよいでしょうか。これは依然として不変ですが、循環グラフを生成するために何らかの方法で使用できます。

Nodeオブジェクトで表される巡回グラフのような構造があります。Nodeは、スカラー値 (葉) または n>=1 Nodes (内部ノード)のリストです。

循環参照が発生する可能性があるため、すべての子ノードの HashCode() を結合する再帰 HashCode() 関数を単純に使用することはできません。無限再帰になってしまいます。

HashCode() の部分は、フラグを立てて既にアクセスしたノードを無視することで少なくとも実行できるように見えますが、Equals() の機能する効率的なアルゴリズムを考えるのに苦労しています。

驚いたことに、これに関する有用な情報は見つかりませんでしたが、多くの賢明な人々がこれらの問題を解決するための良い方法を考えたことは確かです...そうですか?

例 (python):

A は B と同じです。これは、まったく同じグラフを表すためです。

ところで。この質問は特定の言語を対象としているわけではありませんが、Java で説明されているNodeオブジェクトに hashCode() と equals() を実装することは、実用的な良い例です。

私はこのトピックに関するいくつかの情報を検索して見つけましたが、答えは混乱するか、当てはまらないかのどちらかです。

私はこのようなものを持っています：

ここで、ファイルをロードして解析し、そこからこのデータ構造を設定します。それは不変で循環的ですが、どのようにそうすることができますか？

また、このデータ構造にデータを入力したとしましょう。rootThing.refs（3）.nameを変更するなど、変更したいのですが、どうすればよいでしょうか。

---

ここに投稿されたアイデアをありがとう。この時点で、このような永続的なデータ構造が本当に必要な場合は、既成概念にとらわれずに考え、クライアントコードがどのような質問をする必要があるかを検討することを考えています。したがって、オブジェクトやフィールドについて考えるのではなく、クエリやインデックスなどについて考えてください。まず、私は次の観点から考えてい ます。双方向のマルチマップ永続データ構造はありますか？

Gを、サイクルを含む重み付けされていない有向グラフとします。Gのすべての頂点とGのエッジのサブセットで構成され、G'を非巡回にするのに十分小さい、すべての非巡回グラフG'を検出/作成するアルゴリズムを探しています。

より形式的：目的のアルゴリズムはGを消費し、非巡回グラフSのセットを作成します。ここで、Sの各グラフG'は次の特性を満たします。

1. G'にはGのすべての頂点が含まれます。
2. G'は、G'が非巡回であるように、Gのエッジのサブセットを含みます。
3. G'のエッジの数が最大になります。つまり、プロパティ1と2を満たすG''は存在しないため、G''にはG'よりも多くのエッジが含まれ、G''は非循環です。

背景：元のグラフGは、要素間のペアワイズ順序をモデル化しています。グラフのサイクルが原因で、これをすべての要素の順序として利用することはできません。したがって、最大非巡回グラフG'は、ペアごとの順序関係を可能な限り尊重しようとして、この順序の可能な限り最良の近似をモデル化する必要があります。

素朴なアプローチでは、エッジの可能なすべての組み合わせを削除し、削除するたびに非周期性をチェックすることができます。この場合、時間と空間の複雑さが悪いことを意味するバリエーションの強く分岐したツリーがあります。

注：問題はスパニングツリーに関連している可能性があり、G'グラフを一種の有向スパニングツリーとして定義できます。ただし、私のシナリオでは、G'のエッジのペアが同じ開始頂点または同じ終了頂点を持つ可能性があることに注意してください。これは、文献で使用されている有向スパニングツリーのいくつかの定義と矛盾します。

編集：スパニングツリーに関連する直感的な説明、背景情報、メモを追加しました。

有向巡回グラフが与えられた場合、入力グラフを表すさまざまな DAG/ツリーを取得するにはどうすればよいですか? 実際には、指定された回路 (有向および巡回) グラフからさまざまなツリーを抽出したいと考えています。

とを使用して作成した閉路グラフがdosyncありref-setます。これを渡すと、予想どおりにがprintln得られます。これjava.lang.StackOverflowErrorは、無限にネストされた構造を効果的に印刷しようとしているためです。

私がそうすると、構造を横断してすべてを印刷しようとしない(str my-ref)ように見えるものが作成されることがわかりました。これにより、当面の問題は解決されますが、自分が何に注意を払っている場合にのみ役立ちます。 vertex@23f7d873m画面に印刷します。ある種のカスタムテキスト（おそらくを含む）として、そして他の非参照のものを通常どおり(println my-graph)に印刷するように呼び出すことができるようにしたいと思います。refstr

現在、構造体の各要素を独自に印刷し、の印刷を完全にスキップするカスタム印刷関数がありrefます。（見ることvertex@23f7d873は実際にはあまり有用ではないことがわかります）。これは使いにくく、REPLでのカジュアルな検査の妨げになります。また、swank.core/breakデバッグ中にEmacsの検査官が検査を行うのを妨げます。

1つの詳細は、実際には、私が通常印刷しようとしている他のいくつかのものも含むrefaの値です。defstruct

だから私はどの道を進むべきか疑問に思っています。私はこれらのオプションを見ます：

1. プロトコルを理解して私のed構造にextend-type適用し、遭遇したときに正しく機能するようにします。これには、構造体のフィールドごとの検査と、構造体に関しては特別な場合が必要ですが、少なくとも、構造体を含むものではなく、構造体に問題を特定します。CharSequencedefstructrefref
2. CharSequenceに遭遇したときにプロトコルをオーバーライドする方法を理解しますref。これにより、さらにローカライズされた動作が可能になり、構造体の内部にない場合でも、REPLで循環参照を表示できます。これは私の好みのオプションです。
3. toString私がするとき、あるレベルで呼ばれると私が信じる何かをする方法を理解してくださいprintln。私はこのオプションについて最も無知です。他のものについてもかなり無知ですが、私は読んJoy of Clojureでいて、今はすべて刺激を受けています。

同様に、この解決策は、循環参照を印刷しようとするときに通常はバーフする他のすべてのものに適用する必要がprintあります。pprintどのような戦略を採用する必要がありますか？

ご入力いただきありがとうございます。

Prolog でサイクルを使用して (実行時に) 有向グラフを作成する必要がありますが、それを表現する方法がわかりません。私の要件は、一定時間内に 1 つの頂点からその隣の頂点に到達する必要があるということです。

それをツリーとして表現することは可能ですか?例えば:

t(left_son,V,right_son)

しかし、どのようにサイクルを解決するのですか?

エッジのリストを作成できます。

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

あるいは単に

[a->[b],b->[c],c->[a,d],d->[]]

しかし、線形時間を消費する隣人を検索しているときに、リストで関数「メンバー」を呼び出さないようにするにはどうすればよいですか?

ご協力いただきありがとうございます