DAGを格納するデータ構造を探していますが、エッジを追加するとサイクルが作成されるかどうかを効率的に（つまり、エッジ/頂点の数でサブリニアに）検出できます（したがって、非循環不変量を壊すことを防ぐことができます） ）。誰かがそのようなことを知っていますか？

ありがとう！

問題のグラフが DAG (有向非巡回グラフ) であると仮定しましょう。

質問: その頂点の 1 つだけに着信エッジがない場合にのみ、そのようなグラフが一意のトポロジカル ソートを持つと結論付けてよいでしょうか?

言い換えれば、一意のトポロジカル ソートを生成するために必要な (しかし十分ではない) 入ってくるエッジのない 1 つの頂点しかないのでしょうか?

次のように記述できるプログラミング言語があるとします。x=f（g（1）、h（1））この場合、有向非巡回グラフは、スプレッドシートのように計算の依存関係を示します（非再帰式を想定）。

これは単純な例ですが、DAG内でより複雑な式を「圧縮」しようとすると興味深いものになります。ここでの目標は、依存関係に基づいて再計算の数を最適化することです。

この問題に対処するために利用できるアルゴリズムと論文は何ですか？

リビジョン ハッシュ キーを持っています。.hgtags 以外のものを含む最も近いリビジョンを取得したいと思います。

たとえば、Mercurial の歴史の次の断片を考えてみましょう。

この場合、指定されたリビジョンがである場合、 .hgtags だけでなく他の何かを含む最も近いリビジョンであるため633cf1f61665、リビジョンを探しています。9451e8f187b1

与えられた場合、できるだけ少ない hg.exe 呼び出しを使用してどのよう633cf1f61665に見つけることができますか?9451e8f187b1

編集

出力を修正しました。同じブランチからのリビジョンが表示されているはずです。

EDIT2

私は自分自身を説明しようとします。2 つの概念を定義しましょう。

• 鈍い変更セット -hg tagアクションによって作成されたもの。
• 興味深い変更セット - 退屈でない変更セット。

したがって、私の質問は次のように言い換えることができます。

たとえば、指定された633cf1f61665または6cad328c622cまたは9451e8f187b1必要なリビジョンは9451e8f187b1です。

私は、私のような趣味の設計オプティマイザーにとって価値の高い DAWG API を Java で使用できるかどうかを調べていました。

DAWG は有向非巡回ワード グラフであり、単語を格納するためのメモリ効率の高いメカニズムです。

したがって、誰かが DAWG Java API について考えている場合、または LinkedHashMaps を使用して DAWG を実装することに関して考えている場合は、この質問に答えてください。

Web ページに有向非巡回グラフを表示する必要があります。既製のライブラリやソリューションを探しているわけではありません。提案、推奨事項、または正しい方向へのプッシュを探しています。

1.DAG の視覚化

ノードと関係がどのように表現されるかわかりません。実行可能なソリューションは、ツリーマップ、古き良きノードとライン、またはその2つの組み合わせです。1 つのノードが画面に複数回表示されても問題はありません。

最初からすべてのノードを画面に表示する必要はありません。ユーザーは、たとえば、ダブルクリックまたはズームによってノードを展開できます。

私はすべての提案やアドバイスを受け入れます。

2. 技術

実装に必要な機能がいくつかあります。

• ドラッグドロップ
• ズーム
• ノードとのマウス操作に関するイベント

私の見解では、2 つのオプションがあります (Flash は問題外です)。

を。HTML5 キャンバス

短所: ベクトルはなく、基本的には画像のみです。ノードでの暗黙的なマウス イベントはありません。

利点: 速度。人気; アニメーション

b. SVG

短所：ノードが多いと速度が遅くなります。

利点: ベクトル グラフィック。要素は DOM にあるため、イベントなどを行うことができます。

c. HTML5 キャンバスと SVG の組み合わせ

プログラムをテストすることになっている先生からいくつかの入力ファイルを受け取りました。タスクは、ファイルから読み取り、有向グラフを作成し、出力を印刷することです。しかし、サイクルがある場合は、プログラムを終了することになっています。

house1とhouse2という名前のファイルがいくつかあります。ファイルhouse1にはサイクルはありませんが、house2にはサイクルがあります。しかし、なぜ私のプログラムがそのサイクルを見つけられないのか理解できません。ここに私はすべてのコードを持っています、そして私がどこを見るべきかを言う助けはありがたいです:)

ノードグラフを使用して一連のデータを処理する方法を理解しようとしています。これは、ギター用のペダルがたくさんある場合のように、サウンド データを操作するアプリケーション用です。有向グラフで相互に接続された定義済みのプロシージャを持ついくつかのノードがあります。それぞれが順番にデータを処理し、1 つが完了すると、次のノードに処理を行うよう信号を送ります。アイデアは、UI を使用してこれらのノードをつなぎ合わせるというものです。

UIの作成にQtを使用しているため、上記の問題に使用できるものがあるかどうかを確認するためにQtのドキュメントを調べていました。そして、Qtステートマシンを見つけました。私が読むことができるものから、必要なことをしているように見えます。状態に入り、何らかの処理を行い、完了すると終了信号が与えられ、グラフの次の状態が開始されます. また、状態をネストして、既存のノードを組み合わせて新しいノードを作成できるという事実は、魅力的なアイデアのように思えます。

ただし、ステート マシンは、ウィジェットの属性を変更する (状態を変更する) ために作成されたものであり、プロシージャをラッピングするためのものではありません。たとえば、ボタンが押されると、ステート マシンが別のウィジェットの状態を変更します。たとえば、ボタンが離されると、状態が元に戻されます。

したがって、Qt、ステート マシン、またはノード グラフによる処理の経験が豊富な人であれば、ステート マシンを微調整して手順をラップするかどうかのヒントを得ることができます。または、Qt ライブラリに他に使用できるものがある場合は?

「Gradleを使用したビルドとテスト」という本にDAGの写真がありますが、私には理解できず、十分に説明されていません。

DAG画像には、他のノードを参照せずにスタンドアロンである「プロジェクト」、「依存関係」、「クリーン」、「ヘルプ」、「タスク」、「プロパティ」などのノードが含まれています。

1）有向グラフでは、ノードには参照（エッジ）が必要だと思いました。それは間違っていますか？

2）もう1つの質問は、これらのスタンドアロンノード（DAGの「プロパティ」や「ヘルプ」など）ですか？

残念ながら、その画像をこの質問にアップロードすることはできません。

同様のトピックを検索しましたが、私の理解度と理解度に対して回答が曖昧すぎて、私の質問に対して十分に具体的ではないと思います。

同様のスレッド:
ツリー (有向非巡回グラフ) の実装
DAG (有向非巡回グラフ) の表現

質問：

次の形式のデータを含むテキスト ファイルをフォーマットしました...
データセットの例:
GO:0000109#is_a: GO:0000110#is_a: GO:0000111#is_a: GO:0000112#is_a: GO:0000113#is_a: GO :0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622
GO:0000112#part_of: GO:0000442 GO:0000118#is_a:16 81
: #is_a: GO:0034967#is_a: GO:0070210#is_a: GO:0070211#is_a: GO:0070822#is_a: GO:0070823#is_a: GO:0070824
GO:0000120#is_a: GO:0000500#is_a: GO: 0005668#is_a: GO:0070860
GO:0000123#is_a: GO:0005671#is_a: GO:0043189#is_a: GO:0070461#is_a: GO:0070775#is_a: GO:0072487
GO:0000126#is_a: 4#GO: is_a: GO:0034733
GO:0000127#part_of: GO:0034734#part_of: GO:0034735
GO:0000133#is_a: GO:0031560#is_a: GO:0031561#is_a: GO:0031562#is_a: GO:0031563#part_of: GO:0031500
GO:0000137#part_of: GO:0000136

このデータから重み付けされた有向 DAG を構築しようとしています (上記は単なるスニペットです)。106kb のデータセット全体はこちら:ソース

--------------------------------------------------

行ごとに考慮して、各行のデータを次のように説明し
ます
。 : GO:0000113#is_a: GO:0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622

「#」は、行データの区切り文字/トークナイザーです。
最初の項 GO:0000109 はノード名です。
is_a: GO:xxxxxxx OR part_of: GO:xxxxxxx の次の項は、GO:0000109 に接続されているノードです。
データセットに示されているように、後続の用語の一部にも接続があります。
is_a の場合、エッジの重みは 0.8 です。
part_of の場合、エッジの重みは 0.6 です。

--------------------------------------------------

私は DAG の仕組みについて Google で検索しましたが、その概念は理解しています。ただし、それをコードに入れる方法はまだわかりません。私はJavaを使用しています。
私の理解では、グラフは一般にノードとアークで構成されています。このグラフは、接続の方向を決定するために隣接リストを必要としますか? もしそうなら、グラフと隣接リストを組み合わせて相互に通信する方法がわかりません。グラフを作成した後の次の目標は、ルート ノードから各ノードの次数を調べることです。データセットにルート ノードがあります。

説明のために、データの最初の行の接続のサンプルを以下に示します:
画像リンク

私がここで達成しようとしていることを皆さんが理解してくれることを願っています。私の問題を調べてくれてありがとう。:)