force-directed graphを最適化しようとしています。これまでのところ、単純な O(n 2 ) メソッドを使用して実装しました。約 1000 ノードしか処理できませんが、これは私のニーズには少なすぎます。
このアルゴリズムに精通している方は、アルゴリズムに 2 つの主要な要素があることをご存じでしょう。クーロンの法則によるノード間の反発と、フックの法則を使用したエッジに沿ったばねのような引力です。これらの要素はどちらも、ノード間のペアワイズ計算を伴います。
Barnes-Hut アルゴリズムは、反発成分を O(n log n) にする前者に対してうまく機能します。しかし、私はスプリングコンポーネントに似たものを見つけることができませんでした. 私は次のことを検討しました：
位置に基づいてノードを重複するビンに分割し、同じビン内のノード間でのみペアワイズ計算を実行します。ただし、特にノードの初期構成はランダムであり、接続されたノードはどこにでもある可能性があるため、これはすべての場合に機能するとは限りません。ノードの生成方法を変更することはできますが、それらがすべて同じビンにない限り、依然として不正確な結果が生成されます。
エッジを別々に保存し、それらを繰り返し処理してばね力を計算します。今のところ、これは私にとって最も有望な方法のようです。
私が考えていないより良い方法はありますか？それが問題である場合、私は C# を使用しています。並列ループをスローするのが簡単だったらいいのにと思います。