問題タブ [subgraph]

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

サブグラフに応じて頂点の 2 つのリストを返す方法はありますか?

私はこの出力に到達したいと思います:

ありがとうございました

問題を次の簡単な例に減らしました。

生産する

0、1、2 を同じランクに保ちながら (元の例はより大きなグラフのコンテキストにあります)、A と B のエッジを識別できるようにする必要があります。つまり、エッジがラベルと明確に一致し、ラベルが読み取れるようにします。

私が想像した1つの解決策は、によって指定されたエッジ接続でポートを使用することでした

しかし、これは生成します

他のアイデア？同じ問題でより大きなグラフを生成しているため、エッジ/ラベルを完全にアドホックに手動で配置するのが最善の解決策ではありません。

編集：生成されたより大きなグラフの（まだ単純化された）例は次のとおりです。

これにより、次が生成されます。

これは、上記の単純な例と同じエッジ/ラベルのオーバーラップの問題を示しています。

その他の注意事項:

• この問題は、同じランク サブグラフ内で双方向に接続されたノードのペアの中間にノードがある場合に発生します。これは、バグが見られる条件のサブセットである可能性があります。
• この問題は、無向グラフにも存在します。

Neo4j グラフ データベースからサブグラフを抽出したいです。入力は 2 つのノードになります。両方のノードからすべてのワンホップネイバーを見つけて、ノードの結合を形成する必要があります（クロージャーと呼びましょう）。ここで、このクロージャ (入力ノードを含むノードの結合) 内のすべての関係を取得する必要があります。javaを使用してneo4jでこの問題に「効率的に」アプローチする方法。提案してください。

問題: Q-正則無向グラフが与えられた場合、エッジ削除によって N-正則無向サブグラフを識別するアルゴリズムを探しています。N < Q (明らかに) であり、N-regular サブグラフの空間をサンプリングする必要があるため、アルゴリズムにある程度のランダム性を実装できることが重要です。

私が試したこと: これまでのところ、私の最善の方法は、ハミルトニアン サイクルを見つけて、サイクルの他のすべてのエッジを削除することでした。これは (Q-1)-regular サブグラフを適切に作成し、原則として、必要な程度の規則性に達するまで繰り返すことができます。または、ハミルトン サイクルのないグラフをうっかり作成してしまいます。ただし、このアプローチは遅く (これが私の主な問題です)、それ以外の場合は完全に不必要なハミルトン サイクルの制限に依存していることに少し問題があります。

私の質問: 誰でもハミルトン サイクル アプローチの代替案を提案できますか、それとも問題が本質的に困難であり、ハミルトン サイクル検出よりも高速な解決策はありそうもないことを教えてもらえますか? ここでいくつかのグラフ理論の概念をいじっていることはわかっていますが、それをより正式に組み立てる専門知識がないことを残念に思います。

お時間をいただきありがとうございます:)

編集: 元のネットワークの頂点の数 (= L) が偶数であることを忘れていました。L と Q の両方が奇数の場合は不可能であり、Q の制限をできるだけ少なくしたいため、通常のグラフを確実に作成できるようにするためにこの制限を設けました。2 つ目は、すべての頂点を保持したいということです (したがって、エッジの削除についてのみ言及しました)。

aノードを指すノードを表示したいb。bサブグラフにあります。次の dot graphviz コードが機能するはずです。

残念ながら、ノードaはサブグラフの外側で宣言されていますが、内側でレンダリングされますmysubgraph(Ubuntu 14.04 の graphviz 2.36.0 で観察されます)。

事前宣言などのバリアントを試しましbた。失敗。

a回避策は、別のクラスター サブグラフで宣言することです。

これによりa、内部mysubgraphに表示されなくなりますが、別のサブグラフは実際にはオプションではありません。

a実際にはサブグラフの外にある必要があります。

質問

• こんなはずじゃないの？
• 意図した外観を維持する回避策はありますか?