問題タブ [subgraph]

ノードにグラフ内の指定された位置を強制しようとしています。そうしている間、さまざまなサブグラフが適切に整列されません。このグラフを生成するコードは次のとおりです。

ノードの位置を強制して、このコードをコンパイルしました。

出力グラフは次のとおりです: http://imageshack.us/photo/my-images/826/samplebg.png/ 私が得た出力の問題は: 1. サブグラフが t=0, t- の順に表示されない5, t=10... 2. サブグラフは左揃えではありません。

次のような出力グラフが必要です: http://imageshack.us/photo/my-images/253/needed.png/

タナック君。

SQLサーバーにグラフネットワークを保存しています。グラフネットワーク（ラベル付き、無向、接続されたグラフのコレクション）は、頂点-エッジマッピングスキームに格納されます（つまり、2つのテーブルがあります。1つは頂点用、もう1つはエッジ用です）：

頂点（graphID、vertexID、vertexLabel）

エッジ（graphID、sourceVertex、destinationVertex、edgeLabel）

このネットワークで特定のサブグラフを数える簡単な方法を探しています。例：このネットワークに存在する「ABC」のインスタンスの数を調べたい：「CDABCEABCF」。JavaやC++などでこれを行う方法についていくつかのアイデアがありますが、SQLを使用してこの問題に取り組む方法がわかりません。何か案は？

少し背景：私は学生ではありません。これは私が追求したい小さなプロジェクトです。私は（メモリ内で）多くのソーシャルメディア分析を行っていますが、SQLデータベースに対してグラフをマイニングした経験はほとんどありません。

私はしばらくこれに苦労してきましたが、まっすぐな答えを見つけることができないようです. 私はgraphvizで複合サブグラフを扱っていますが、2つのサブグラフを互いに整列させるための設定の正しい組み合わせを見つけることができないようです。

同封されているのは、問題を示す簡単な例です...

これにより、Bottom サブグラフが Top サブグラフよりも大幅に広い出力が生成されます。

私が本当に欲しいのは、上と下の両方が常にまったく同じ幅であることを保証することです。さらに、ノードが多すぎて使用可能な幅に収まらない場合は、追加のノード行が生成されます。

7 つのサブグラフ クラスターを持つグラフビズ表現があります。各サブグラフには、相互接続された約 20 のノードがあります。

各サブグラフには、1 つ以上のクラスターとの 3 ～ 10 個のリンクがあります (たとえば、クラスター 1 の 1 つのノードがクラスター 2 の別のノードに移動します)。

すべてのサブグラフを円のプレゼンテーションに配置して、それらの間のリンクを簡単に追跡できるようにしたいと思います。これを達成する方法はありますか？または、少なくとも各サブグラフの位置を修正する方法はありますか?

あなたが私を助けてくれることを願っています。ありがとうございます。

すべてのカットに弱く接続されたセットがある (あるセットから別のセットへの有向パスが少なくとも 1 つある) 有向グラフで弱く接続されている DAG にまたがる最大の重みを見つけるアルゴリズムはありますか? それともNP難しい問題ですか？このトピックに関する前の質問では、接続が弱いか強いかを指定していませんでした。より正確な。

ノードのサブセットで動作する標準のトポロジカルソートアルゴリズムのバリエーションを探しています。

「依存」、「前」、「後」の 3 種類の有向辺を持つラベル付きノードのグラフを考えてみましょう。

私が望む関数は、ノードのサブセットを受け入れ、線形順序を返します。線形順序付けは、「前」および「後」の制約に従い、「依存先」を「前」の制約として扱います。線形順序付けのノードは、依存関係が含まれるように、入力ノードのスーパーセットである必要があります。

グラフの例:

X after Yは自明にY before Xに書き換えることができます

テストケース:

ボーナス ポイント:順序付けの最初と最後のノードを強制するようにアルゴリズムを構成することもできます。

次のドット ファイルで GraphViz を使用します。

それは私にそのようなものを与えます：

しかし、私はそのようなものが欲しい:

5c071a6b2c -> 968bda3251

どうやってやるの？

よろしくお願いいたします。

私は次の点を持っています：

これは私にこの画像を与えます：

しかし、私は列ごとにサブグラフを作成したいと思います（最初の列に1つ、2番目の列に2-3、最後の列に4-5）。

それを行う方法はありますか？

よろしくお願いします。

ネットロゴについて質問があります。(無向) リンクで接続されたノードのグラフ構造がいくつかあります。これらの構造の 1 つに含まれる最小のサブグラフを特定する必要があります。基本的にサブグラフとは、どのノードがすべて相互に接続されているかを意味します。したがって、5 つのノードの構造があり、ノード 1 が 2 と 3 に接続されているとします。ノード 2 から 3、1 および 4。ノード 3 から 1、2、および 5 ノード 1、2、および 3 はすべて相互接続されているため、ノード 1、2、および 3 のサブグラフを検出する必要があります。

これを行う簡単な方法はありますか、それとも基本的に計算上不可能ですか?

編集: netlogo 拡張機能 nw を使用すると、 nw:maximal-cliques メソッドを使用して必要なものを計算できることがわかりました。今は別の問題がありますが。このようにして派閥のリストのリストを埋めようとしています

lista-cliques は通常長さ 2 ですが、clique のタートルのリストであるべき最初の要素は次のようなリストです

guild = g のタートルによって作成されたグラフの長さが約 2 ～ 8 タートルである場合、長さは 300 です。nw:maximal-cliques の呼び出しは適切に行われていますか?

私が間違っていることのアイデアはありますか?

編集2:これを行うことでリストの長さを修正する方法を考え出しました

現在、リストは 300 ノードではなく、ギルド = g のノードを含むグラフ上のノードの数と同じです。

つまり、

に等しい

ノードが 1 つまたは 2 つのノードにしか接続されていないグラフが表示されるため、これも明らかに間違っています。近づいていると思いますが、nw:maximal-cliques が最大クリークのリストではなく、グラフ上のすべてのノードのリストを作成する理由がわかりません。

何か案は？

ありがとう

次のようにNeo4J（組み込み）データベースをセットアップしています：

• 参照ノードにいくつかのユーザー ノードを接続します。
• 各ユーザー ノードには、1 つ以上のプロジェクト ノードを接続できます。
• 各プロジェクト ノードには、複雑なグラフが添付されています。

複雑なグラフは、単一のトラバース パターンでトラバース可能です (それらには隠されたツリー構造があります)。

私がやりたいことは次のとおりです。

• プロジェクト ノードの下にあるすべてのノードを削除します。
• プロジェクト ノードの下に何もない場合、ユーザーの下のすべてのプロジェクト ノードを削除します
• 特定のユーザー ノードの下にあるすべてのノードを .graphML にエクスポートします (おそらく Gremlin Java API を使用しますか?)
• 別のユーザー ノードにある情報を削除せずに、特定のユーザー ノードの下にあるデータベースに .graphML ファイルをインポートして戻します。

Neo4J データベース全体をインポートおよびエクスポートするために、Gremlin GraphML リーダーを既に使用しましたが、サブグラフのインポート/エクスポートについて何かを見つけることができませんでした。

これが実際に可能である場合、Neo4J は、同時に何かをインポートしようとする 2 人のユーザーをどのように処理しますか? たとえば、ユーザー 1 は自分のセクションを user1 ノードの下にインポートし、ユーザー 2 は自分のデータをユーザー 2 ノードの下に同時にインポートします。

もう1つの可能性は、ユーザーごとにNeo4Jデータベースを使用することですが、これは実際にはあまり好ましくないオプションであり、組み込みまたはサーバーバージョンで実際に可能かどうかは非常にわかりません. 異なるポートに複数のサーバーバージョンがあることについて読んだことがありますが、ユーザーの数は定義ごとに無制限です...

どんな助けでも大歓迎です。

EDIT 1：サブグラフを扱うGeoff（org.neo4j.geoff）と呼ばれるものにも出くわしました。これがどのように機能するかについてはまったくわかりませんが、現在調査中です。