問題タブ [directed-acyclic-graphs]

有向非巡回グラフ のオンザフライ アニメーション用のオープン ソース ライブラリについて調べることに興味があります。

グラフのレンダリングに関する同様の質問がたくさんありますが、この特定のニーズに対応する質問を見つけることができませんでした。

特定のシナリオでは、たとえば STDIN を介して、グラフが読み取られるときにグラフのごく一部をレンダリングする必要があります。

残念ながら、Graphviz はこの特定のタスクに対応していないようです。また、私が知る限り、他の同様のライブラリにも対応していないようです。

あるいは、そのようなライブラリがないという事実を誰かが知っていれば、それは私が仕事に取り掛かる時が来たという具体的な兆候になるので、それも役に立ちます.

編集: Dyna は要件を満たしている可能性があると思います。別の日かそこらで誰もこれを見たり応答したりしない場合は、回答としてリストします。

オブジェクトの依存関係のコレクションを DAG にまとめるとしたら、どのような状況で BDD (二分決定図) などの別のデータ構造よりも望ましいでしょうか?

重み付けされた 2 つの DAG (有向非巡回グラフ) があり、それらを 1 つにマージする必要があるため、トポロジー順序を取得できます (場合によっては 2 つ以上になる可能性があります)。問題は、グラフはそれぞれ非循環的ですが、一緒に循環を形成できることです。また、グラフが大きい (100k 以上のノード、500k 以上のエッジ)。グラフをマージする賢い方法はありますか? すべてのグラフを「一度に」トラバースするアルゴリズムも同様に優れています。

編集：

「マージ」とは、サイクルが作成されない場合、両方のグラフのすべてのエッジと頂点を組み合わせることを意味します (もちろん、重みを保持します)。エッジが既に存在する場合は、より大きな重みを使用したいと考えています。

アイデアは、2 つの非巡回グラフで開始すると、後で結果を単純に「修正」するよりも利点が得られるということです (これは、NP 困難なフィードバック アーク セットを見つけることを意味するため、それを避けたいと考えていました)。

ご提案いただきありがとうございます。

あいさつOverflowers、

• データ構造は、任意の数のノードの非巡回ツリーです。
• 浅いノードは、深いノードの結果に依存します。
• 最終的な結果は、ツリーを再帰的にトラバースすることで簡単に計算できます。
• 無制限のスレッドがある場合は、各ノードに1つ以上のスレッドを割り当てます。
• 浅いノードに割り当てられたスレッドは、深いノードのスレッドが終了するのを待ちます。
• ただし、スレッドは限られています。場合によってはノードの総数より多く、場合によっては少なくなります。

そのような木を横断し、最終的に限られたスレッドで最終結果を得る方法について何か考えはありますか？

よろしく

Git の履歴は、DAG と呼ばれるデータ構造に格納されていることを知っています。私は DFS について聞いたことがあり、それが多少関連していることを知っています。

気になるのですが、git log --graphやなどのプログラムはどのようhg graphlogに歴史を描いているのでしょうか? レーンやすべてを素敵な方法で描くのはかなり複雑だといつも思っていました。

誰かがそれを示す擬似コードを書くことができますか?

注: Git または hg のコードを調べてみましたが、何が起こっているのかを理解して理解するのは非常に困難です。

そこで、C ++で有向非巡回グラフを作成しました。今度は、それをテキストファイルまたはファイルに保存したいと思います。それ、どうやったら出来るの？

PS：混乱してすみません...ファイルのフォーマット方法を尋ねるつもりです。

前もって感謝します！

そうしたいです：

1. The Ruby Way に従って DAG を表現します。
2. DAG からイメージを生成します。

ノード数は 100 以下です (多くの場合、80 パーセンタイルの場合は 10 など、はるかに少なくなります)。データを永続的に保存する必要はなく、イメージのみを保存する必要があるため、データベースについて考慮する必要はありません。

iPhoneでグラフを表示するための良いチュートリアルを提案できますか

Qtで一般的にグラフの有向グラフを視覚化するウィジェット、ライブラリはありますか? JVMを検査しながらリアルタイムでそれらを構築したいですか、それともGraphvizで入出力を行う方法ですか?

「git の歴史はただの DAG」という概念を理解するためのきれいな グラフを含む git イントロがあります。歴史を表現するために、この正確なモデルに基づいて構築された視覚的な git ブラウザーが (一見) 少ないのはなぜだろうか。

• git-cola の DAG ビュー(まだ実験的な機能のようです)
• github のネットワーク グラフ(私が探しているものにかなり近いですが、スタンドアロン ツールではありません)

これら以外のすべてのビジュアル git ブラウザー (gitk、git-gui、GitX など) は、テキスト情報を優先してグラフを狭い列に押しのけます。

主な機能として DAG ビューを持つ git リポジトリ ブラウザーはありますか? プラットフォーム、言語、スタンドアロン、GUI/CUI は関係ありません。

目前の特定の問題を解決しようとしているわけではありません。根本的なツールが git zen に到達するのに役立つことを願っています。

編集：関連するが、OPの見解では、異なる質問：

• きれいな git ブランチ グラフ

「git history DAG を生成するツール」以上のものを探しています。Web ブラウザーのように、この架空の「DAG 指向の git ブラウザー」は、履歴グラフを表示、検索、ジャンプ、およびフィルター処理できる必要があります。