問題タブ [directed-acyclic-graphs]

何千もの頂点とエッジを持つDAGがあります。

私は、最も人間に優しい/美的方法で頂点をグリッドポイントに配置できるアルゴリズムを探しています。私の勘では、最も優れたレイアウトは、エッジの長さの合計が最小のレイアウトに似ていると思います。

このようなエッジ長の最小合計レイアウトの効率的なアルゴリズム、またはこの問題に取り組むのに役立つ可能性のある他のアルゴリズムを教えていただけますか？

非常に単純なアルゴリズムからの出力の一部を次に示します。

文字が繰り返されないさまざまな量のセットでサブシーケンスを見つけることについて質問しました。解決策は、文字の各ペアの行列を作成し、各セットで発生しないものを破棄してから、有向非巡回グラフで最長パスを見つけることでした。ただし、最長パスだけが必要なわけではなく、いくつかの最長パスが必要です (たとえば、長さが 10、10、9、8、8、3、3、2、および 1 のサブシーケンスを生成する場合、最初の 5 つのサブシーケンスのみを表示します)。

したがって、最長パスだけを探しているわけではないため、ウィキペディアの記事で説明されている最長パス アルゴリズムを使用するのではなく、結果のサブシーケンスを生成するために、単純にすべてのリストを生成する単純なアルゴリズムを使用しています。可能なサブシーケンス。これにより、前の質問に対する回答の結果と同様のセットが生成されます。

問題は、生成されるサブシーケンスの量を減らしたいということです。

たとえば、次のセットがあるとします。

...私のアルゴリズムは現在、各セットで発生する次のペアを考え出します:

これは技術的には正しいですが、これらのペアのいくつかを削除したいと思います。たとえば、2常に の後に来ることに注意して1ください。A2したがって、 andのB2ペアを削除したいと思います (つまりA、andBに直接ジャンプするべきではありません2...常に最初に通過する必要があります1)。また、は常にその直後に発生するため、1以外の番号に決してジャンプしないでください。さらに、との間で常に発生することに注意してください。そのため、ペアを削除したいと思います(ここでも、にジャンプする前に常に通過する必要があります。これは、すべてのセットがこれらの 3 文字の位置を : として持っているためです)。220B3B3B03B < 0 < 3

明確にするために、現在のアルゴリズムは次のサブシーケンスを考え出します: (A簡潔にするために で始まるものだけを含めました):

...そして、 でマークされたものはすべて*排除する必要があります。

目的のサブシーケンスを生成する (正しい) ペアは次のようになります。

...そして、サブシーケンスの完全なリストは次のようになります:

言い換えれば、私はこの有向非巡回グラフから行こうとしています:

これに：

これらの不要なペア (つまり、グラフのエッジ) を取り除くには、どのようなアルゴリズム/ロジックを使用すればよいですか? それとも、そもそもペアを生成する私のロジックを変更する必要があると思いますか?

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

ここに私の問題があります：私は（空ではないがおそらく明確ではない）セットs_iのシーケンスSを持っており、各s_iについて、S内のセットs_j（i≠j）がs_iのサブセットである数を知る必要があります。

また、インクリメンタル パフォーマンスも必要です。すべてのカウントを取得したら、1 つのセット s_i を s_i のサブセットに置き換えて、カウントをインクリメンタルに更新します。

純粋に機能的なコードを使用してこれらすべてを実行すると、大きなプラスになります (私は Scala でコーディングしています)。

セットの包含は半順序付けであるため、私の問題を解決する最善の方法は、セットのハッセ図を表す DAG を作成し、エッジが包含を表し、整数値を各ノードのサイズを表す結合することであると考えました。ノードの下のサブダグに 1 を加えたものです。ただし、半順序付けからハッセ図を作成するアルゴリズムを開発しようとして数日間行き詰まりました (インクリメンタリティについては話さないでください!)。標準的な学部の資料。

ここに私のデータ構造があります:

私の DAG は、ルートのリストといくつかの半順序によって定義されます。

私はここでかなり立ち往生しています。DAG に新しい値 v を追加するために最後に思いついたのは次のとおりです。

1. DAG 内の v のすべての「ルート サブセット」rs_i、つまり、rs_i のスーパーセットが v のサブセットではないような v のサブセットを見つけます。これは、グラフで検索 (BFS または DFS) を実行することによって非常に簡単に行うことができます (collect関数、おそらく最適ではないか、欠陥がある可能性さえあります）。
2. 新しいノード n_v を構築します。その子ノードは以前に見つかった rs_i です。
3. 次に、n_v をどこに付けるかを調べましょう: 与えられたルートのリストについて、v のスーパーセットを見つけます。何も見つからない場合は、ルートに n_v を追加し、ルートから n_v のサブセットを削除します。それ以外の場合は、スーパーセットの子に対してステップ 3 を再帰的に実行します。

私はまだこのアルゴリズムを完全に実装していませんが、明らかに単純な問題に対して不必要に回旋しており、最適ではないようです。利用可能な単純なアルゴリズムはありますか (Google はこれについて無知でした)。

1つのソースを持つDAGがあるとします。nソースからの完全なパスが通過するn（つまりn、すべてのシンクを支配する）ノードを見つけたいと思います。言い換えると、のすべての後続を削除するとn、すべてのパスはで終わりnます。問題は、DAGでノードが削除済みとして段階的にマークされることです。ノードが削除済みとしてマークされると、他のノードが上記のプロパティを満たし始めることができます。発生したときにこれを効率的に検出するにはどうすればよいですか？

データ構造が、各ソースで個別に単一のソースに対してアルゴリズムを実行するよりも効率的な方法で複数のソースを使用してこれを実行できる場合、ボーナスポイントが得られます。

次のDAGがあります

閉鎖表はこちら

およびも削除せずに、パスB > Dを削除する (したがって を削除する)にはどうすればよいでしょうか。A > B > DA > C > DC > D

現在、次のクエリを使用していますが、すべてのノードに親が 1 つしかない場合にのみ機能します。

pyqt でノード グラフを作成する予定です。qt が提供する抽象モデルは 1D、2D、およびツリー データに対して機能しますが、抽象クラスはノード グラフのようなものに対して機能しないようです。

特に、QAbstractModel の「親」関数は、単一の親の QModelIndex を返します。DAG では、複数の親を持つことができます。

私が見つけた 1 つのリソースは、次のブログ投稿でした。

http://invalidmagic.wordpress.com/2009/12/10/qgraphicsscene-used-as-a-qabstractitemmodel/

いくつかの有用な情報を提供しますが、モデルが複数の親の概念をどのように表しているかはわかりません。

Qt で DAG モデルを実装する方法の例と提案を探しています。

有向グラフにサイクルのインスタンスがあれば、それを与えるアルゴリズムが必要です。誰か私に方向性を教えてもらえますか？擬似コードで、またはできればRubyで？

以前に同様の質問をし、そこでの提案に従って、グラフにサイクルがあるかどうかを検出するカーンのアルゴリズムをRubyに実装しましたが、サイクルがあるかどうかだけでなく、そのようなサイクルの1つの可能なインスタンスも必要です。

カーンのアルゴリズム

上記のアルゴリズムは、グラフにサイクルがあるかどうかを示します。

しかし、それだけでなく、次のようなサイクルの例も必要です。

検査の最後に上記のコードで変数を出力するgraphと、次のようになります。

これには、必要なサイクルが含まれますが、サイクルに関係のない余分なエッジも含まれます。

'* a *サイクリックグラフ'に関連するいくつかの質問とそれぞれの関連する回答/ディスカッションがあり、それらは確かに役立ちます。しかし、「循環グラフ」に関連するものは何も見つからなかったので、ここにこの質問を投稿することにしました。

私は次のような複雑な時間的関係を持っています

• a-> b-> c（'a'には'b'を介して'c'へのパスがあります）
• b-> d-> c
• c-> e-> a（注：-ここでcにはvia eへのパスがあります）

私はこれらの関係を「絵画的」な形式で表現する必要があります。'a'、'b'、'c'などを画像として表示できると便利ですが、それは簡単です。

そのような関係をグラフで表すために利用できるJavaScript/JQueryはありますか？私はflexなどの他のテクノロジーに関する意見を受け付けていますが、最初に選択するのはJQuery/JavaScriptです。

最近のインタビューで、以下の質問をされました。

ノードとエッジのセットが与えられ、開始ノードが最終終了ノードを指します。下の図では、1 で開始し、15 で終了します。彼らの質問には、ノード 2 (または任意のノード) が開始点として与えられ、入力エッジがすべてノード 2 から到達可能ではないパス内の次のノードをどのように見つけることができますか (つまり、どうすれば 14 に到達できますか)。

どうすればこれを行うことができますか、疑似コードは問題ないはずです。