問題タブ [directed-acyclic-graphs]

|V|のDAGが与えられた = nであり、s個のソースがあるため、各サブグラフが約k1=√|s|になるようにサブグラフを提示する必要があります。ソースとおよそk2=√|n| ノード。

DAGの高さを、あるソースからあるシンクまでの最大パス長と定義するとします。

生成されるすべてのサブグラフの高さがほぼ同じである必要があります。

（サブグラフの）ノードセットの各ペアの共通部分は空です。

添付の写真で右のパーティションの例を見ることができます（グラフの各エッジは上向きです）。

この例では、36個のノードと8個のシンク[＃10,11,12,13,20,21,22,23]があります。したがって、各サブグラフには6個のノードと2個または3個のシンクが必要です。

アルゴリズムのアイデアはありますか？

どうもありがとうございます

Taskother に依存できるオブジェクトがあるとしましょうTasks。特定のタスクのサブタスクのセットすべてを適切に熱心に/結合してロードする方法はありますか?

依存関係を DAG に保存する必要があります。(私たちは非常に細かいレベルで新しい学校のカリキュラムをマッピングしています)

Rails3を使用しています

考慮事項

• 深いよりも広い
• 非常に大きい
• ノードあたり 5 ～ 10 リンクと見積もっています。システムが成長するにつれて、これは増加します。
• 多くの読み取り、少数の書き込み
• 最も一般的なのはルックアップです。
  • 1度と2度の従属関係
  • 依存関係の検索/検証

私は SQL を知っています。NoSQL を検討します。

実装オプションの適切な比較へのポインタを探しています。

また、迅速に開始できるものに興味がありますが、後でより堅牢でスケーラブルなものに移行するのが苦痛ではありません。

igraphへのpython バインディングを使用して、有向ツリーを表します。そのグラフのあるノードから別のノードへのすべての可能なパスを見つけたいと思います。残念ながら、このタスクを実行する igraph ですぐに使用できる関数を見つけることができませんでしたか?

編集

無数のパスに関する懸念

私が話しているグラフは、実際には単一のルートを持つ有向非巡回グラフ (DAG) です。これは、カスケードのさまざまなレベルで分割または結合できる一方向のイベントのカスケードを表します。先ほど言ったように、これは単方向グラフです。また、グラフにサイクルが含まれていないことも前提です。これらの 2 つの理由により、パスの無限リストは不可能です。

私は何をしようとしていますか？

私の目標は、グラフの上部 (ルート) から特定のノードにつながるすべての可能なパスを見つけることです。

ノードがさまざまな種類のワークロードであり、エッジがワークロード間の依存関係であるグラフがあるとします。（循環依存関係が存在してはならないため、これはDAGです。）

また、作業を実行できる複数のエージェントのセットがあります。

一部のワークロードの種類は任意のエージェントに与えることができ、他の種類は特定のエージェントに与える必要があり、他の種類は特定のエージェントグループの1つのエージェントに与える必要があります。

次のようなワークロードを割り当てるにはどうすればよいですか。

• すべてのブロッキングワークロードが完了するまで、エージェントにワークロードは与えられません

• 総ワークロードグラフを完成させるには、可能な限り最短の時間が必要です。（エージェントのアイドル時間を最小限に抑えることは一般的には良いことですが、基本的な要件ではないことに注意してください。特定のエージェントが長時間アイドル状態になるシナリオがありますが、すべてのエージェントのすべてのジョブを完了するための合計時間は最小です。）

ワークロードには期間の見積もりがありますが、簡単にするために、すべてのワークロードの計算に同じ時間がかかると想定しています。（すべてのワークロードが実質的に一定時間の操作になるまで、各ワークロードを複数のシリアル依存のワークロードに分割するだけです。）

トポロジカルDAGソートを認識していますが、これにより、ノードの単一のシリアル順序が生成されます。複数のエージェントが並行して動作しており、タスクの非自明な並べ替えによって、潜在的に大規模なタイミング最適化を実行できるような関係になっています。

この結果は、全体の最小期間のガントチャートとして最適にレンダリングされます。実際、この問題を、マイルストーンをできるだけ早く完了することを目的として、チーム内のエンジニアにマイルストーンでバグチケットを割り当てることと考えると、そのアイデアが得られます。（いいえ...グラフをMS Projectにインポートしてからエクスポートするように言わないでください:)-その背後にあるアルゴリズムに興味があります！）

よく知られているアルゴリズム、ソフトウェアライブラリ、または一般的な問題と原則へのポインタは大歓迎です！

私は一種の1レベルのツリー構造を次のように持っています:

ここで、p は親ノード、c は子ノード、b は仮想分岐です。

1 つの親のみが1つの子ノードにのみ分岐でき、2 つの分岐は親および/または子を共有できないという制約の下で、分岐のすべての組み合わせを見つけたいと考えています。

例combo: が組み合わせのセットである場合:

それがすべてだと思います。=)

この構造の任意のツリー、つまり p:s、c:s、および b:s の数は任意です。

編集：

これはツリーではなく、二部 有向非巡回グラフです

文字列が与えられ、結果として生じるすべての文字のペアがエッジを構成します。つまり、これは文字列ABBCADです。文字列のエッジは次のとおりです。

最短経路距離はA->Dです

手元のタスクは、上記のルールを使用して文字列からメモリ内に有向非巡回グラフを構築し、ターミナルノードで終わるルートノード（この例ではAラベル）を見つめる最短パスを見つけることです。

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

タスクに適したアプローチの1つを収集するのは、深さ優先探索アルゴリズムを使用することです。

これは宿題ではありません...

DAG G では、重み付けされたエッジが負ではない場合、G の 2 つの頂点間の最大重み付けパスをどのように見つけますか?

君たちありがとう！

データ構造に対してイテレータが必要です。今のところ、データ構造が何であるかはわかりません.DAG（有向非巡回グラフ）かもしれませんが、連結リストかもしれません。だから私はそれをイテレータにラップしたいのですが、今は特定のデータ構造では考えていません。

再帰的なビジターで DAG を訪問する方法は知っていますが、反復子メソッドnext()とhasNext().

イテレーター内で、現在のノード インスタンスを作成し、すべての子に対して for ループを繰り返してから、親に戻ります。「既に訪問済み」フラグが必要です。だから私DagElementはこれらのより多くの属性を持っています:

これはきれいな解決策ではないと思います。

何かアドバイス？

これは宿題ではありません。

見た目は木のように見えますが、すべてのリーフは一意です（データベースに一意のIDがあります）。それらの上の階層はやや恣意的です。各チェックボックスには、オン、オフ、および部分的な3つの状態があります。葉はチェックすることもチェックしないこともできます。子供の状態は、親の状態を駆動する必要があります。チェックボックスをクリックすると、チェックボックスが「切り替わり」、必要な変更が上下に反映されます。部分的にチェックされている親をクリックすると、完全にチェックされるはずです。各子には、親のリストへのポインターがあります（必要に応じてこれをセットに変更できます）。各親には、アルファベット順にソートされた子のリストがあります。同時に、下の写真からわかるように、この構造は表示用に拡大したり折りたたんだりできるツリーです。

このアルゴリズムは以前に発明されたものだと確信しています。葉の数は2万枚に達しているので、実際のパフォーマンスには気を配っています。しかし、コードが短くて読みやすいという犠牲を払って、パフォーマンスの最後の一滴をアルゴから絞り出そうとはしませんでした。

原則として、（行くところがあれば）歩いて、変更する必要のあるすべての葉を特定する必要があると考えました。その後、私は歩く必要があります。葉のセットから、影響を受ける可能性のある親のセットを把握する必要があります。次に、変更する必要のある親のセットとその値にフィルターをかけます。次に、それらをセットに追加します。次に、それらのノードから立ち上がって繰り返す必要があります。値だけでなく変更する必要のある葉と他のノードのセットを取得したら、それを実行する必要があります...またはそのようなものです。マトリックスベースの表現はコストがかかりすぎます。

私はこのことを一緒にC++使用してハッキングしてMFCいますが、私の質問はほとんど言語に依存しません。ただし、アルゴリズムよりも具体的な実装をお勧めします。Python、Perl、Scalaのようないくつかの言語は、あまりにも現代的なトリックを持っているかもしれません。私は、Java、C＃（マイナスLINQ）などのより一般的なものに固執しようとします。

コード、リンク、リファレンス、質問は大歓迎です。