問題タブ [subgraph]

私は現在Graphを使用していますが、指定された頂点のリストによって誘導される元のグラフのサブグラフを作成する方法がありません。

Graph のアクセサを使用してそれを行うスタブを作成しましたが、

これが私のコードです：

ノート：

• 動作は文書化され$Graph->newていませんが、グラフのソースが示すように、属性はコピーされますが、頂点/エッジはコピーされません。

• CPAN にはすでに機能リクエストがあります: https://rt.cpan.org/Ticket/Display.html?id=65497

それで、他のモジュール（おそらくXS）がありますか、Graphそれともパッチを当てる必要がありますか？

エッジに値があり、ノードに値がない有向巡回グラフがあります。

グラフには開始ノードと終了ノードがあり、グラフを介してパスのセットを保持したいのですが、パス上のノードは気にせず、エッジ値のみを気にします。以下の例。

そのプロパティを保持する小さなグラフを生成するアルゴリズムはありますか?

グラフには数万のノードが含まれる場合がありますが、数百万にはなりません。ノードあたりのエッジの数は、ノードの数に対して少ないです。

保守的なヒューリスティックは大歓迎です。

例として、Oはノードで、数字は隣接するエッジの値です。

最初から最後までエッジ値が [1,2,3,4] の 2 つのパスがあるため、1 つが冗長であり、上記を

グラフは循環する可能性があるため、

より単純なグラフでは、2 番目の遷移 1 を削除して、自己エッジのみを残します。

無向かつ無加重 (またはすべてのエッジの加重が 1) の非巡回グラフ (G=VxE) があります。このグラフのノードのいくつかは sV (sV は V のサブセット) として選択されます。問題は、選択したすべてのノードをカバーするサブグラフを見つけたいということです。当然ながら、選択されていないノードをカバーすることもできます。ただし、目的のサブグラフにないノードは制限されます。これらの制限されたノードは、選択した 2 つのノード間の 1 つのパス上にある場合を除き、ソリューション サブグラフに含めるべきではありません。例：

A、B、C、D はノード、+ はエッジの包含を表します。このグラフでは、B と D が選択されたノードです。この例に必要なソリューションは次のとおりです。サブグラフは、ノード B、C、D とエッジ (B、C)、(C、D) * で構成されます。A は意図したとおりにサブグラフに含まれていないことに注意してください。このタイプのサブグラフを見つけるには、どのようなアプローチが役立ちますか? アイデアをありがとう。

*(X,Y) は、ノード X と Y の間のエッジを表します。

私はこのGraphvizグラフを持っています:

次の出力が生成されます。

ノードが次のように配置されるように、A と D の間のエッジの長さが最小化されることを期待していました。

それよりも

サブグラフ定義を削除すると、これは期待どおりに機能します。

サブグラフが導入されると、Graphviz が ABC を一番下に配置するのはなぜですか?

オートマトンとグラフ理論に関する科学プロジェクトを開始し、次のような機能をサポートするグラフライブラリを探しています。

• 有向/無向グラフ
• グラフ同型テスト（つまり、グラフg1はg2と同型ですか？）
• サブグラフ同型テスト（つまり、グラフg1はg2のサブグラフと同型ですか？）
• グラフ検索、訪問など
• おそらく、深刻な計算を行う必要があるため、非常に高速です

Boost Graph Libraryについては知っていますが、ドキュメントから理解できる限り、サブグラフのテストが不足しています。

だから、私の質問は：最高のc ++グラフライブラリはどれですか？彼らは私が必要とするすべての機能をサポートする必要はありません。既存のライブラリが私のニーズに完全に適合しない可能性は確かにあります。

ここにグラフの抜粋があります。

n 個の頂点と m 個の辺を持つ無向グラフ G と整数 k が与えられた場合、H の各頂点が次数 ≥ k を持つような G の最大誘導部分グラフ H を見つける O(m + n) アルゴリズムを与えます。このようなグラフが存在します。グラフ G = (V, E) の誘導部分グラフ F = (U, R) は、G の頂点 V の U の部分集合であり、各辺の両方の頂点が U にあるような G のすべての辺 R です。

私の最初のアイデアは次のようなものです。

まず、この節税では、次数が k 以上であるすべての頂点 S を実際に要求し、次に、他の頂点に接続されたエッジを持たない S 内の頂点を削除します。次に、洗練された S は H であり、すべての頂点の次数は >= k であり、それらの間のエッジは R です。

さらに、O(m+n) を要求するので、BFS または DFS が必要だと思います。それから私は立ち往生します。

BFS では、頂点の次数を知ることができます。しかし、v (頂点) の次数を取得すると、その親以外の他の接続された頂点はわかりません。しかし、親が次数 >= k を持っていない場合、v はまだ他とつながっている可能性があるため、v を削除することはできません。

ヒントはありますか？

編集：

@Michael J. Barberの答えによると、私はそれを実装し、ここでコードを更新しました:

誰でもコードのキーメソッドを見ることができますpublic Graph kCore(Graph g, int k)か? 私はそれを正しくしますか？O(m+n)ですか？

}

大きなグラフの k サイズのサブグラフを見つけるアルゴリズムが必要です。あなたの提案は何ですか？

注: 私のグラフは無向です。

前もって感謝します。

次のコードでいくつかのノードをグループ化したい

しかし、ドットはサブグラフを気にしません:

Python と、場合によっては networkx を使用して、異なる色のオーバーレイ サブグラフを使用してグラフを作成できるかどうか疑問に思っています。これらのサブグラフはノードのクラスターです。このようなグラフの例は、次の場所にあります。

http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200904-10_PLoSCompBio-HumanPhenotypes/200904-10_PLoSCompBio-Fig2sm.png

2 つのサブグラフを表示するコードがあります。

このコードは、次のような 2 つのサブグラフを表示します。

しかし、私はそれを次のようにしたい：

誰かが「rankdir」を修正してそれを成し遂げるのを手伝ってくれることを願っています。