有向グラフデータを整理する良い方法は何ですか？

Question

ここに私の状況です。私は、異なる時間に追加される異なるデータセットを持つグラフを持っています。たとえば、set1には数千のノードがあり、set2は後で入り、ビジネスロジックを適用してset1からset2までのエッジを作成します（そして、set2からset2へのエッジを持たないset1の頂点を無効にします）。その後、set3、set4などが得られ、同じ処理が各セットと前のセットに適用されます。

質問、これを整理するにはどうすればよいですか？私が以前にしたことは、ノードset1-xx、set2-xxなどの名前を付けることでした。私が直面した問題は、現在のセットと以前のセットの間で分析を実行しようとしたときに、グラフ全体を通してループを実行する必要があった'setx'で始まったすべてのノードを探します。グラフが成長するにつれて長い時間がかかったので、私は 'set1'というノードを作成し、その特定のセットのすべてのノードに接続するという別の解決策を考えました。私はそれをテストしていますが、私はそこにもっと効率的なやり方があるのか​​、それともこのようなデータ構造を扱う方法で構築されているのだろうと思っていましたか？このようなデータをどうにか分割する方法はありますか？

私は一般的な解決策がアプリケーションになると思いますが、それが役に立ったら私はneo4jを使用しています（そのデータベースに対する特定のソリューションも同様に良いでしょう）。

Answer 1

レイヤードグラフと呼ばれる非常に特殊な有向グラフがあります。

データ構造の選択は、主に期待されるグラフ密度（前のセット/レイヤーからのノード数が通常、現在のセット/レイヤー内のノードに接続されている数）と、実行する必要がある操作それはほとんどの時間です。各レイヤーを数値インデックスで直接表現すること（つまり、一番外側の構造体はセット/レイヤーの配列になります）、レイヤーごとに1つの頂点の配列を使用することもできます。しかし、頂点ごとの辺のリスト（外に出て行くかどうかに応じて出て​​行くか出るかの設定）は次のいずれかです：

• リンクされた頂点識別子のリスト。グラフが非常に疎でエッジが頻繁に追加/削除される場合、これは良いことです。
• 頂点識別子のソートされた配列。グラフが非常に疎で不変の場合、これは良いことです。
• 頂点識別子によってインデックス付けされたブール値の配列。指定された頂点が現在の頂点からのエッジによってリンクされているかどうかを判定します。グラフが密であればこれは良いことです。

「頂点識別子」にはさまざまな形があります。たとえば、次のレイヤーの頂点の配列へのインデックスにすることができます。

Answer 2

2番目の解決策は、私が行うことです。setXノードを作成し、そのセットに属するすべてのノードをsetXに接続します。こうすることで、データが分割され、クエリが簡単になります。