私たちのアプリケーションは、多くのノードとエッジを持つ潜在的に大きなグラフを表示します。もちろん、ドットのようなものを使ってグラフをレイアウトし、画面上でうまく見えます。しかし、ユーザーはそれらを紙に印刷したいと思う。技術的にはこれを行うことができます。グラフを小さな画像に分割し、ユーザーがそれを印刷することができます。しかし、ページサイズを切り捨てることで、ノードを切り落とさず、ページ間にエッジがあるなどの保証はありません。グラフのレイアウトを変更するアルゴリズムを探しています - ノード境界がページ境界にならないようにする - ページ間のエッジを最小限に抑えるようにする 密度の高いノードの「クラスタ」を見つけて、ほとんどのエッジを横切って同じページを配置するように見えるようです他のページから他のクラスタへ誰もこの種のことをするために関連する文献/ツールを教えてもらえますか？用紙に印刷するためのグラフのレイアウト
ありがとうございました
クラスタ分析は良いスタートです。
私は、プロセスに以下の方法をお勧めします：
ページの配分を考える：コスト（再分割）= F（境界、multipagesエッジに近いノード）
まず、コスト関数を定義します
目的はこの機能を最小限に抑えることです。
は、クラスタ分析アルゴリズムを選択しました：
あなたがDBSCANに私のポストを見ていることができます（クラスタ化アルゴリズムを定義します。DBSCAN code in C# or vb.net , for Cluster Analysis およびクラスタリングに「ページ」制約を追加（ページのサイズ）
は、あなたがあなたのポイントを通過します順序によって結果が
が最小コストのものを選びました。理由は、「ページの制約」と異なること、またはあなたが許容できるコストを見つけたときに停止します。
このアルゴリズムの複雑さは、O（n！）...大きなグラフには大きな種類です。 したがって、いくつかのクラスタリングの制約を考えるか、部分近似を行うために部分検索（O2（n2）で最初にn2をテストする）を行うだけです。 受け入れ可能なコストに応じて、合理的な時間内に結果を得ることができます。