Java/CGALはグラフが接続されているかどうかを確認します（説明に制約があります）

Question

CGALで初めてのことですが、 （そして...はい、私はCGALとJavaを組み合わせて使用​​しなければなりません）：/長い話を短い...私は持っています：

• 私の頂点のx座標とy座標を表す2つのダブル配列。それらをdouble[] x, y;としましょう。
• 両方の配列には、ランダム値のSがあります。
• 2つの頂点uとwは、distance(x[u], y[u], x[w], y[w]) < CONSTANT（ofc。I do distanceSquared(x[u], y[u], x[w], y[w]) < CONSTANT_SQUARED）と接続されているので、sqrt（）を呼ぶのは避けてください。
• xおよびyは、0からUPPER_LIMITまでの値でランダムに入力されます。他の情報はありません。

質問、xとyは接続グラフを記述していますか？

• アルゴリズム1：：各頂点の

  1. ビルドの隣接リスト（Arraylist<Integer>[] adjLists;）（のみ上三角行列が探求）

     今私は2つのalgoritmsを持っています。複雑度O(|V|^2)（V =頂点集合）。

  2. 訪問グラフの頂点がSに等しい場合、再帰グラフの探索、頂点のマーキングとカウント、私のグラフには接続されたコンポーネントが1つしかありません。グラフが接続されています。複雑度O(|E|)（E =エッジセット）。

• アルゴリズム2：

  private static boolean algorithmGraph(double[] x, double[] y) { 
      int unchecked, inside = 0, current = 0; 
      double switchVar; 
      while (current <= inside && inside != S - 1) { 
       unchecked = inside + 1; 
       while (unchecked < S) { 
       if ((x[current] - x[unchecked]) * (x[current] - x[unchecked]) + (y[current] - y[unchecked]) * (y[current] - y[unchecked]) <= CONSTANT_SQUARED) { 
        inside++; 
        // switch x coordinates | unchecked <-> inside 
        switchVar = x[unchecked]; 
        x[unchecked] = x[inside]; 
        x[inside] = switchVar; 
        // switch y coordinates | unchecked <-> inside 
        switchVar = y[unchecked]; 
        y[unchecked] = y[inside]; 
        y[inside] = switchVar; 
       } 
       unchecked++; 
       } 
       current++; 
      } 
      return inside == S - 1; 
  } 
  

おかしい事は二番目が遅い、私はデータ構造を使用していない、コードを反復し、インプレースが、スイッチ作るの多用でありますそれは地獄のように遅くなる。

問題の仕様が変更されましたが、現在はCGALとJavaでそれを行う必要があります。「https://github.com/CGAL/cgal-swig-bindings」全体を読んでJava内でCGALを使用する方法を学習しますが、 CGALコードのインスタンス...すでに高速アルゴリズムが実装されていますか？

ありがとうございます！ハッピーコーディング！私はと考えてい

Answer 1

は、空間索引の方法なしに、あなたは最悪のケースのシナリオで達成しようとしている最高のパフォーマンスは、（すべての接続）O(n*(n-1)/2)になるだろう。

あなたが空間インデックスを構築するために余裕があれば（速度のブーストのために支払うために十分なメモリを持っている）、あなたはR-tree and variants検討すること - 挿入がO(n)検索がO(log2(n))である：これは、「距離を調べることによって、外れ値の検出」あなたを取得するアプローチ最悪のシナリオではO(n*log2(n))のコストである。

​​