問題タブ [directed-graph]

私が取り組んでいるフレームワークは、他のサービスに依存するステートフル サービスで構成され、有向非巡回グラフhttp://en.wikipedia.org/wiki/Directed_acyclic_graphを形成します

できるだけ効率的にサービスを開始したい。これは、可能であればサービスを並行して開始することを意味します。たとえば、ウィキペディアのリンクのグラフ。依存関係がないため、3、5、および 7 を同時に開始します。トポロジカル ソートを見てきましたが、それだけでは何が並列に開始できるかわかりません。次のようなサービスをグループ化するためのライブラリ/APIを探しています:

これは、最初に「a」を開始し、次に「b」、「c」、および「d」を並行して開始し、次に「e」というように開始するように指示します。

Vertices をモデル化するライブラリをいくつか見つけましたが、探しているグループ化を行うライブラリはありません。これまでのところ、有向グラフの実装をいくつか見つけましたが、寛容なライセンス (非 gpl など) が必要です。ComputeNodeOrder http://www.docjar.com/docs/api/org/eclipse/osgi/internal/resolver/ComputeNodeOrder.Digraph.html (equinox org.eclipse.osgi_3.6.2.R36x_v20110210 から)、Jgrapht ( lgpl) http://www.jgrapht.org/javadoc/、ユングhttp://jung.sourceforge.net/index.html、プレクサスhttp://plexus.codehaus.org/plexus-utils/apidocs/org/codehaus /plexus/util/dag/DAG.htmlしかし、これらのいずれか/すべてが必要なことを行うかどうかはわかりません。

有向グラフの原子性と分離の保証はどこにでも記載されていますか?

特に：

1. del_vertex の途中で別のプロセス (vertices()、out_neighbours() など) にアクセスしようとした場合、別のプロセスは digraph をどのような状態で参照しますか?エッジは削除され、頂点は削除されない) または del_vertex の後 (つまり、操作が終了するまで別のプロセスがブロックされる)?
2. del_vertices に関する同じ質問。

私の理解が正しければ、ダイグラフは3つのetsテーブルを使用して実装されています。結果を一貫させるために、それらの間に追加のロックメカニズムはありますか?

要するに、単純な有向グラフにいくつの非周期的パスがあるかを数えるための高速アルゴリズムが必要です。

単純なグラフとは、自己ループや多重辺のないグラフを意味します。パスは任意のノードから開始でき、出力エッジのないノードで終了する必要があります。パス内でエッジが2回発生しない場合、パスは非循環です。

私のグラフ（経験的データセット）には20〜160のノードしかありませんが、一部のノードには多くのサイクルがあるため、パスの数が非常に多くなり、私の素朴なアプローチは、一部のグラフに対して十分に高速ではありません。私は持っています。

私が現在行っているのは、再帰関数を使用してすべての可能なエッジに沿って「降順」であり、既にアクセスしたノードを追跡します（そしてそれらを回避します）。これまでの最速のソリューションはC++で記述されており、再帰関数でstd :: bitset引数を使用して、既にアクセスされたノードを追跡します（アクセスされたノードはビット1でマークされます）。このプログラムは、サンプルデータセットで1〜2分で実行されます（コンピューターの速度によって異なります）。他のデータセットでは、実行に1日以上、または明らかにはるかに長い時間がかかります。

サンプルデータセット：http：//pastie.org/1763781 （各行はエッジペアです）

サンプルデータセットのソリューション（最初の数字は私が開始しているノード、2番目の数字はそのノードから始まるパスカウント、最後の数字は合計パスカウント）：http： //pastie.org/1763790

より複雑なアルゴリズムについてのアイデアがあれば教えてください。近似解にも興味があります（モンテカルロアプローチでパスの数を推定します）。最終的には、平均パス長も測定したいと思います。

編集：MathOverflowにも同じタイトルで投稿されています。これが規則に違反しないことを願っています。サイトは2つ以上のリンクを許可しないため、リンクできません...

これは、生成されたグラフが現在表示されているもの です。これのコードは次のとおりです。

2本の赤い線を削除すると、希望どおりに整列します。

どうすればこのように並べて、2本の赤い線を同時に持つことができますか？

PHPとMySQLで家系図を作成する必要があります。そこにオープンソースのカスタマイズ可能なhtml家系図構築ソフトウェアがないことにかなり驚いていますが、私は逸脱します。MySQLの有向グラフと家系図の保存について多くの時間を費やしてきました。すべてが私には理にかなっています。ノード（人）のあるテーブルとエッジ（関係）のあるテーブルがあります。

私が抱えている唯一の問題は、兄弟関係や祖父母関係など、必ずしも隣接しているとは限らない関係を保存するための最良の方法がわからないことです。最初は、これらの接続を解決する親（誰もが親を持っている）を目に見えない形で強制できるので、これが大したことになるとは思いませんでした。

ただし、ロマンチックなパートナーなど、共通の親がいない可能性のある関係も保存できる必要があります。私が読んだことはすべて親子関係を示唆していますが、ロマンチックなパートナーは（願わくば）共通の親を共有していないため、エッジテーブルに保存する方法がわかりません。別のテーブルを使用する必要がありますか、それとも何ですか？同じテーブルにある場合、これをどのように表現しますか？なじみのない人間関係でこれをやっている限り、家族でもやったほうがいいかもしれません。

要約すると、3つの質問：

• 横方向の関係をどのように表現しますか？
• 横方向の関係に共通の親がある場合、どのように保存しますか？familyこれは、他の横方向の関係が保存されているテーブルのフラグである必要がありますか？
• 子が2つ以上離れている（祖父母）が、直接の親が利用できない親子関係を保存するにはどうすればよいですか？

どんな助けでもありがたいです、そして誰かがいくつかのjavascript / html家系図構築ソフトウェアについて何か提案があれば、それは素晴らしいでしょう。

2 つのノード間に複数のアーチを持つことができるグラフが与えられました。

例 ：

4 ノード 1->2 2->3 3->4 3->4 1->4

ノード A からノード B までの道路の数を求める最適な方法はどれですか?

この例の答えは 3 です: 1->2->3->4 ; 1->2->3->4 および 1->4

ノードとアーチの制限は 1 000 000 です

私は総当たりアルゴリズムで考えているだけです。

他のアイデアはありますか？編集：

グラフは非循環です

プログラムにフロー図描画キャンバスを埋め込みたいです。ユーザーは次のことができます。

• 「ノード」（長方形のノードで十分）と「エッジ」（直交することが望ましい）を描画して「ノード」を接続します。
• マウスを使用してノードをドラッグしてレイアウトし、長方形のサイズを変更します。
• マウスで 1 つまたは複数のノードを選択して、削除、コピー、貼り付けなどを行います。
• マウスで 1 つまたは複数のノードを選択して、定義済みのプロパティ (体積、温度、圧力など) を編集します。;
• 色の変更 (オプション)
• ファイルへの/からのデータの保存/読み取り。

描画後、プログラムは接続ロジック ( Directed graphのようなデータ構造) とプロパティを取得してさらに計算する必要があるだけです。

これを行うための無料またはオープン ソースの C++ ライブラリはありますか? (クロスプラットフォームでは必要ありません。Windows で利用できれば十分です。)

Gを、サイクルを含む重み付けされていない有向グラフとします。Gのすべての頂点とGのエッジのサブセットで構成され、G'を非巡回にするのに十分小さい、すべての非巡回グラフG'を検出/作成するアルゴリズムを探しています。

より形式的：目的のアルゴリズムはGを消費し、非巡回グラフSのセットを作成します。ここで、Sの各グラフG'は次の特性を満たします。

1. G'にはGのすべての頂点が含まれます。
2. G'は、G'が非巡回であるように、Gのエッジのサブセットを含みます。
3. G'のエッジの数が最大になります。つまり、プロパティ1と2を満たすG''は存在しないため、G''にはG'よりも多くのエッジが含まれ、G''は非循環です。

背景：元のグラフGは、要素間のペアワイズ順序をモデル化しています。グラフのサイクルが原因で、これをすべての要素の順序として利用することはできません。したがって、最大非巡回グラフG'は、ペアごとの順序関係を可能な限り尊重しようとして、この順序の可能な限り最良の近似をモデル化する必要があります。

素朴なアプローチでは、エッジの可能なすべての組み合わせを削除し、削除するたびに非周期性をチェックすることができます。この場合、時間と空間の複雑さが悪いことを意味するバリエーションの強く分岐したツリーがあります。

注：問題はスパニングツリーに関連している可能性があり、G'グラフを一種の有向スパニングツリーとして定義できます。ただし、私のシナリオでは、G'のエッジのペアが同じ開始頂点または同じ終了頂点を持つ可能性があることに注意してください。これは、文献で使用されている有向スパニングツリーのいくつかの定義と矛盾します。

編集：スパニングツリーに関連する直感的な説明、背景情報、メモを追加しました。

重複の可能性:
有向グラフでサイクルを検出するための最適なアルゴリズム

有向グラフでループを見つけるアルゴリズムを探しています。

私のグラフには、エッジではなくノードにのみラベルがあり、かなり巨大になる可能性があります。

アルゴリズムの出力は、一連のリストとしてのループである必要があります。各リストには、ループに含まれるノードのラベルが含まれている必要があります。したがって、リストの最初と最後の要素は同じである必要があります。

私が使用しているグラフには、連結成分が 1 つしかなく、強連結成分がない可能性が高いです。サイクル数は少ないと予想されます (まだ確認する必要があります)。

まさにこれまたは類似のもののための優れたアルゴリズムは大歓迎です。

どうもありがとうございました。

PS: 不明な点がある場合は、お気軽に詳細をお問い合わせください。たとえば、グラフは (これまでのところ) 1 つのノードから複数のノード (通常は 1 つ) までの一連のエッジとして保存されますが、これは無関係である必要があります。私見では。

私は有向グラフを持っています。次はサイクルですか？矢印はサイクル内で特定の方向を持っていますか?