私は現在、グラフ実装のパフォーマンスの問題に取り組んでいます。
使用技術
これはC++でプログラムされています。今のところ、グラフはBGLのおかげで実装されています。
グラフについて
管理されたグラフは動的で無向です。それは2種類の構造を持っています：多くの完全なサブグラフといくつかの単一のエッジです。必要な情報は、頂点のすぐ近くだけです。
問題文
当初、完全なサブグラフは小さく（約10頂点）、多数（約13k）でした。BGLの隣接リストの実装は完璧でした。しかし、今では、5000個の頂点のいくつかのサブグラフを管理するように求められています。つまり、5000x5000のエッジを意味します。時間と空間のパフォーマンスは、現在非常に劣っています。
拒否されたソリューション
私の最初の考えは、BGLによって提供される隣接行列の実装を使用することでした。ただし、動的グラフは使用できません。この制約を解決するには、2つの解決策があります。動的グラフの隣接行列の新しい実装を提供するか、静的グラフで使用可能な頂点のプールを使用します。振り返ってみると、それは良い考えではないと思います。スペースの複雑さはまだVxV/2です。
最終的な解決策と質問
したがって、ここでの最終的な解決策は、BGLを使用せず、頂点のバッグを実装して完全なサブグラフを表し（エッジは不要）、いくつかの単一エッジの頂点を直接接続します。そうすることで、最大のサブグラフのスペースの複雑さは、頂点の数である約5000に下がります。
- この最後の解決策は良いものだと思いますか？
- そうでない場合、どの実装を使用できますか？なぜ？
アップデート1
グラフの詳細：グラフには、約100kの頂点、約3つの頂点の約13kの完全なサブグラフ、およびサイズ範囲[10-5000]の約100の完全なサブグラフがあります。また、各エッジにはバンドルされたプロパティがあります。
アップデート2
私は最近、Salim Jouilliのおかげで、ノードのバッグがハイパーグラフの率直なアプローチであり、ハイパーエッジがノードのサブセットで構成されていることを学びました。
アップデート3
ソリューションの実装が完了しました。私はメモリ消費と実行時間を効果的に増やしました：6GBから24MBと50分から2分30。