問題タブ [directed-acyclic-graphs]

それぞれが演算子をサブクラス化するいくつかのクラスがあります。演算子には、画像、数値、文字列など、さまざまなタイプの入力と出力がいくつかあります。各サブクラスは、計算を行うrun（）メソッドを実装します。次に、これらの演算子のコンテナを設計して、単純な演算子からより大きな演算子を作成したいと思います。コンテナは可能な限り効率的である必要があるため、スレッドを使用することを計画しています。Boostグラフライブラリで、計算を実行する順序を計算できる例を見つけました：http ://www.boost.org/doc/libs/1_49_0/libs/graph/doc/file_dependency_example.html、しかし、これを行うにはさらに良い方法があると思います。各オペレーターは、すべての入力の準備ができるまで、ブロックされた状態で待機できます。コンテナがOperatorをサブクラス化し、それらを再帰的に組み合わせることができると便利です。これは既知のデザインパターンだと思います。

DAGをJSONテキストとして表現したいと思います。誰かがこれを試したかどうか、およびJSONが実際にDAGであるかどうかの検証に関して彼らが扱った問題があるかどうか疑問に思います。

gRbaseパッケージの「dag」関数をplotと組み合わせて使用​​して、いくつかのDAGを作成しています。

「dag」ヘルプページでは、引数にこれが表示されます。

x、グラフの生成クラスを含むリスト。以下の例を参照してください。

以下の例では、次のようなものが表示されます。

その結果、このコードを実行すると、それが機能し、グラフが表示されます。

独自のリストを作成すると、次のエラーが発生するのはなぜですか？

関連する定理とアルゴリズムを追跡できるように、使用しているデータ構造の数学的形式を探しています。

次のものがあるとします。

• トピックの有向非巡回グラフ。
• 各トピックでは、トピック、一連のドキュメント内のアイテム、および一連のグループ内のアイテムの間に 1 つ以上の関係があります。
• グループは単純なセットの場合もあれば、最終的に DAG になる場合もあります。ドキュメントとトピックの関連付けの可視性を管理するために使用されます。

関連性はあるが一般的すぎるハイパーグラフに出くわしたのはつい最近のことです。このデータ構造には形式がありますか? そうでない場合、数学用語でより簡潔に説明できますか?

The Algorithm Design Manualには、関連する 2 つの節があります。

基本的に、最初の消費税の解き方は知っていますが、最初の消費税の解法をヒントに、2番目の消費税の解き方がわかりません。

算術式木の抜粋

上は算術式ツリーです。算術式が木として与えられたとします。各リーフは整数で、各内部ノードは標準の算術演算 (+、−、∗、/) の 1 つです。たとえば、式 2 + 3 ∗ 4 + (3 ∗ 4)/5 は、上の図のツリーで表されます。このような式を評価するための O(n) アルゴリズムを与えてください。ここで、ツリーには n 個のノードがあります。

わかりました、これは難しいことではありません。私の解決策は次のとおりです。

結果の式ツリーを解決するために再帰的な方法を使用するだけです。

演算式DAGの抜粋

算術式が、共通部分式が削除された DAG (有向非巡回グラフ) として与えられているとします。各リーフは整数で、各内部ノードは標準の算術演算 (+、−、∗、/) の 1 つです。たとえば、式 2 + 3 ∗ 4 + (3 ∗ 4)/5 は、上の図の DAG で表されます。このような DAG を評価するための O(n + m) アルゴリズムを与えます。ここで、DAG には n 個のノードと m 個のエッジがあります。ヒント: 望ましい効率を達成するために、ツリー ケースのアルゴリズムを変更します。

OK、説明に次のようなヒントがあります:ヒント: ツリー ケースのアルゴリズムを変更して、目的の効率を達成します。

実際、私はこのヒントにかなり混乱しています。典型的なツリー関連の場合、通常、再帰を使用して解決できます。ただし、これがグラフの場合、私の最初の直感は、BFS または DFS を使用して解決することです。DFS は実際には再帰的ですが、どうすれば BFS や DFS をツリーに関連付けることができますか?

数字でラベル付けされたエッジを持つ DAG があるとします。パスの値をラベルの積として定義します。各 (ソース、シンク) ペアについて、ソースからシンクへのすべてのパスの値の合計を見つけたいと考えています。これは動的計画法を使用して多項式時間で行うことができますが、問題を分解する方法にはまだいくつかの選択肢があります。私の場合、異なるラベル付けで繰り返し評価する必要がある 1 つの DAG があります。私の質問は、特定の DAG について、異なるラベル付けのこれらの値を繰り返し計算するための適切な戦略を事前に計算するにはどうすればよいですか? 掛け算の回数を最小化する方法など、最適な方法を見つけるアルゴリズムがあればいいのですが。しかし、これは質問するには多すぎるかもしれません。適切な分解を提供するアルゴリズムに非常に満足しています。

グラフ理論操作に適した C ライブラリはありますか? 特に、有向グラフの強連結成分を計算する必要があります。次のように、Ruby でTarjan のアルゴリズムを実装しました。

小さなグラフで動作していましたが、グラフが大きくなるにつれて、メソッドの再帰呼び出しにより「スタックレベルが深すぎます」というエラーが返され始めましたstrong_connect。C ライブラリが必要で、メイン プログラムが記述されている Ruby からアクセスする必要があると思います。

ライブラリに加えて、それを Ruby ライブラリで使用するための提案があれば助けになります。

私は長い間有向非巡回グラフ（DAG）に興味を持っていましたが、ウィキペディアでトポロジカルソートについて読んだ後、レイヤーの番号付けを含むアプローチについて特別な言及は見つかりませんでした（ただし、レイヤーは描画のために広く言及されています）。このアプローチでは、グラフは技術的にトポロジカルソートされませんが、すべてのノードにレイヤー（レベル）の正しい番号が含まれていることを知っているので、特定のノードが別のノードよりもトポロジカルに「大きい」かどうかを常に判断できます。一方、順序付きリストがない限り、ノードをトポロジ的に列挙することはできません（ただし、これは、ノードのレベルを比較する最終的な従来の並べ替えで実行できます）。

このアプローチにより、レベル情報の正確性を維持しながら、任意の接続を実装できます。手順は次のとおりです。

• 新しく追加されたノード（接続なし）の場合、適用されるレベルは1です。
• 2つのノード間の接続が要求され（mからnまで）、n.level> m.levelの場合、それらは単に接続されているだけであり、他のノードのレベル固定は必要ありません。
• 要求された接続（mからn）n.level <= m.levelの場合、n.levelを（m.level + 1）に変更し、nの依存関係を再帰的にチェックして、同様のレベルの増加を確認します（または、レベルが増加しない場合は増加しません）。再帰ステップでは互換性があります）。
• 再帰的に入力されたノードのリストを保持すると、循環して何らかの取り消し操作を実装する試みを検出できます（影響を受けるすべてのノードのレベルを以前の値に戻します）

既知のノードとそれらの間の接続のセットについて、level = 1を適用するすべてのノードをそれらに追加し、それらの間のすべての既知の接続を適用しようとします（ciclesを無視して元に戻します）。

最終レベルの情報では、ノードをトポロジ的に比較できるだけでなく、他の有用な情報も含まれています。例えば：

• レベル=1のすべてのノードには着信接続がありません（すべてのパスはそれらの1つから始まります）。したがって、DAG列挙はそれらから開始できます。
• 最長のパス（エッジの数）は、（最大レベル+ 1）より長くすることはできません

一部の人工データ（nノード、Node（n + 1）に接続されているすべてのNode（n））の場合、このアルゴリズムは非常に遅くなる可能性があると思います。しかし、私が試した実際のデータ（Wikipediaのカテゴリ-800,000ノード-2,000,000接続）の場合、時間はまともで（5〜10分）、レベルとサイクルの試行回数は少ない（369レベル、1000サイクルの試行）

では、この方法は新しいものですか、それともよく知られていますが、ウィキペディアやその他のリソースでは広く紹介されていませんか？それは（技術的には）一種ではないので、データ再構築と呼ばれるべきですか？

それ自体との関係を持つProjectテーブルを持つ Ruby on Rails システムに取り組んでいます(循環関係は不可能です)。このように、プロジェクトは複数の他のプロジェクトの一部になることができます。これは非常に便利であり、新しいアプリケーションのベースとなっているレガシー システムのキラー機能です。、、およびその他の単純なプロパティを使用して、すべてのプロジェクトを 1 つのページに表示する方法が必要です。各プロジェクトは、それぞれの親に関連付けて表示する必要があり (重複したエントリは問題ありません)、各プロパティ値は、ブラウザーによって他の各プロパティと揃える必要があります (常に壊れる「静的な幅」の混乱はありません)。プロジェクトは折りたたみ可能でなければなりませんが、これはソリューションには関係ないと思います。has_and_belongs_to_manynameshort_name

現在の解決策は、HTML テーブルにツリーを表示するにはどうすればよいですか? に似ています。解決策: を使用し、<table>CSS を使用して左端の列に「ツリーのような」構造を実装しますpadding-left。各プロジェクトの親プロジェクト ID を保存することにより、完全な親子関係が維持されます。これはセマンティック マークアップではないため、結果のテーブルを JavaScript で処理するのは困難です。<tr>ノードを折りたたむ場合は、子のリストを単に削除するのではなく、同じレベルにあるノードが見つかるまで、折りたたまれたノードの後に​​それぞれをトラバースする必要があります。また、いくつかのプロジェクトが複数回表示されます

そのようなデータ構造を HTML (任意のバージョン) で表現するセマンティックな方法はありますか? 私の知る限り、テーブルのリストは適切に配置されず、リストとテーブルを混在させることはできません。

既存のシステムの構造を説明するためだけに、プログラミング言語がタスクに関連していないため、rubyまたはでタグ付けしていません。ruby-on-rails

したがって、基本的に、float値のn x m配列があり、値の1行目とm行目の値の間の最短パスを見つけようとしています。(i, j)グラフのノードに{(i, j+1), (i-1, j+1), i+1, j+1)}は、端(0 < i < n-1)になく、一番下の行にないノードの子があり(j < m-1)ます。この特定の問題を適切なタイミングで解決するアルゴリズムを探しています。私の現在の考えは A* 検索を中心に展開していますが、あなたの考えを教えてください。