Java/CGAL проверить, подключен ли граф (некоторые ограничения в описании)

Question

это мой первый раз с CGAL, некоторые из вас могут спорить, почему я должен изучать CGAL из чего-то подобного, но это новый проект, который я должен (и ... да, я должен использовать CGAL и Java в сочетании):/Длинный рассказ короткий ... У меня есть только:

• Два двойных массива, представляющих координаты x и y моих вершин. Назовем их double[] x, y;.
• Оба массива имеют S случайных значений.
• Две вершины, u и w подключены, если distance(x[u], y[u], x[w], y[w]) < CONSTANT (из. I do distanceSquared(x[u], y[u], x[w], y[w]) < CONSTANT_SQUARED, поэтому я избегаю вызова sqrt()).
• x и y заполнены со значениями от 0 до UPPER_LIMIT, никакая другая информация не указана.

Вопрос, do x и y описывает связанный граф?

Сейчас у меня есть два: Алгоритмы

• Алгоритм 1:

  1. Построить смежности списка (Arraylist<Integer>[] adjLists;) для каждой вершины (только верхняя треугольная матрица изучены). Сложность O(|V|^2) (V = набор вершин).
  2. Рекурсивное исследование графа, маркировка вершин и подсчет, если посещенная вершина равна S В моем графе есть только один компонент, связанный с моим графиком. Сложность 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», чтобы узнать, как использовать CGAL внутри Java ... но я хотел бы получить некоторую помощь об этом конкретном экземпляр кода CGAL ... Существуют ли более быстрые алгоритмы, реализованные в CGAL?

Спасибо за ваше время, ребята! Счастливое кодирование!

Answer 1

Я считаю, что без метода пространственной индексации, лучшей производительности вы собираетесь достичь в худшем случае-сценария (все подключены) будет O(n*(n-1)/2).

Если вы можете позволить себе построить пространственный индекс (достаточно памяти, чтобы заплатить за повышение в скорости), вы можете рассмотреть R-tree and variants - вставки O(n) поиск по O(log2(n)): это будет получить «Outlier обнаружения путем изучения расстояния» подход для стоимости O(n*log2(n)) в наихудшем случае.

A notable result