問題タブ [directed-acyclic-graphs]

DBIx::Class サブクラス foo への直接的および間接的な外部キー依存関係を持つテーブルのリストを取得する最も速い方法はどれですか? DBIx::Class::Schema に基づく MySQL データベースがあります。DBIx::Class を直接使用できますか、または SQL::Translator は有向グラフを生成することによって役立ちますか?

次のクラスがあるとします。

入力 Foo の場合、出力は [ Bar, Baz ] になります。

この依存関係グラフを考えると、下から上に反復するための「良い」アプローチは何ですか?

各「サイクル」の期待される結果は次のとおりです。

ブレーンストーミング

「深さ優先検索」が機能しない理由:

アルゴリズム

私は本当に車輪の再発明をしたくありません.この問題を解決するアルゴリズムはすでにありますか、それとも「賢い」アプローチを持っている人はいますか?

私はこのDAGを持っています（二分木に似ていますが、グラフです..これには指定された名前がありますか？）：

(各番号はノードであり、ノード内の番号はたとえば、プログラムは乱数で実行する必要があります)

リストのリストとして表されます。

ノードの合計を最大化するパスを可能な限り機能的な方法で見つける必要があります。

私が検索したところ、これは projecteuler #18 と非常に似ていますが、project euler はパスの穴の合計を尋ねます。宿題では、合計だけでなくすべてのノードを見つける必要があります。私は自分の問題にいくつかの本当に良い解決策を適応させようとしましたが、うまくいきませんでした. いくつかのアドバイス？

私は、論理回路 (DAG として表すことができる) を含む研究問題に取り組んでいます。DAG の各ノードには特定の重みがあり、これは負になる場合があります。私の目的は、ノードの重みの合計が最大になるように接続されたサブグラフを見つけることです。

エッジの重みが与えられた最大重み接続サブグラフ問題は明らかに NP 困難ですが、私が望んでいるのは、有向非巡回の性質と、エッジの重みではなくノードの重みを扱っているという事実により、問題が多少簡単になることです。誰かがこの問題への攻撃を開始する方法の正しい方向に私を向けることができますか?

ありがとう

私が取り組んでいるフレームワークは、他のサービスに依存するステートフル サービスで構成され、有向非巡回グラフhttp://en.wikipedia.org/wiki/Directed_acyclic_graphを形成します

できるだけ効率的にサービスを開始したい。これは、可能であればサービスを並行して開始することを意味します。たとえば、ウィキペディアのリンクのグラフ。依存関係がないため、3、5、および 7 を同時に開始します。トポロジカル ソートを見てきましたが、それだけでは何が並列に開始できるかわかりません。次のようなサービスをグループ化するためのライブラリ/APIを探しています:

これは、最初に「a」を開始し、次に「b」、「c」、および「d」を並行して開始し、次に「e」というように開始するように指示します。

Vertices をモデル化するライブラリをいくつか見つけましたが、探しているグループ化を行うライブラリはありません。これまでのところ、有向グラフの実装をいくつか見つけましたが、寛容なライセンス (非 gpl など) が必要です。ComputeNodeOrder http://www.docjar.com/docs/api/org/eclipse/osgi/internal/resolver/ComputeNodeOrder.Digraph.html (equinox org.eclipse.osgi_3.6.2.R36x_v20110210 から)、Jgrapht ( lgpl) http://www.jgrapht.org/javadoc/、ユングhttp://jung.sourceforge.net/index.html、プレクサスhttp://plexus.codehaus.org/plexus-utils/apidocs/org/codehaus /plexus/util/dag/DAG.htmlしかし、これらのいずれか/すべてが必要なことを行うかどうかはわかりません。

キーが頂点IDであり、リストにエッジに沿ったすべてのターゲット頂点が含まれる場所としてDAGを表すことを検討しています。Dictionary(Of Integer, List(Of Integer))

この構造は後で次の目的で使用します。

9ページの有向非巡回グラフを理解するのに問題があります

http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

それを説明できる人はいますか？

したがって、基本的に次のような問題があります。文字列がたくさんあり、すべてのパスが文字列に対応するように、またはその逆になるようにDAGを構築したいと思います。ただし、文字列を任意に並べ替える自由があります。文字の順序は関係ありません。私が生成するDAGには、それに関連するコストがあります。基本的に、DAGのブランチのコストは、その子パスの長さに比例します。

たとえば、文字列BAAA、CAAA、DAAAがあり、それらを並べ替えることなくそれらを表すDAGを作成するとします。私は得る：

（）->（B、C、D）-> A-> A-> A

ここで、タプルは分岐を表します。

私の目的のためのより安価な表現は次のようになります：

（）-> A-> A-> A->（B、C、D）

問題は次のとおりです。n個の文字列が与えられた場合、対応するDAGのコストが最も低くなるように文字列を並べ替えます。ここで、コスト関数は次のとおりです。多様性を持って訪問してください。

したがって、最初の例のコストは12です。これは、トラバーサルでAを複数回訪問する必要があるためです。2番目の例のコストは6です。これは、ブランチを処理する前にAを1回だけ訪問するためです。

この問題はNP困難だと感じています。形式言語についての質問のようで、私はそのような種類のアルゴリズムに精通していないため、削減をどのように行うべきかを理解できません。完全な答え自体は必要ありませんが、誰かが関連していると思われるよく知られた問題のクラスを指摘できれば、それをいただければ幸いです。

別の投稿のこのアルゴリズムに従って、画像のDAGのクリティカルパスの計算を行っています。先生は配列を実装する必要があります。宿題のステートメントを簡略化します。これは、配列を介して実装された単純なグラフです。

これは、上の図に示すように、エッジの始点ノード、エッジの終点ノード、および頂点の各ペア間の距離を表す3つの配列v、u、およびdがある私のコードです。画像のグラフでは、プロジェクトの期間は、クリティカルパスからの距離の合計に対応する25に等しくなります。

私のコードは、このリンクの擬似コードによる距離の計算をうまく行うことができません

何が間違っているのか、またはプロジェクトの期間（クリティカルパスからの距離の合計に対応）を教えてくれるコードをどのように解決できるのでしょうか？最初の3つの頂点までの距離しか計算できません。