Блог

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

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

#java #graph #cgal

#java #График #cgal

Вопрос:

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

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

Вопрос, 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 amp;amp; 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;
}

Забавно, что второй медленнее, я не использую структуры данных, код итеративный и на месте, но интенсивное использование switch делает его чертовски медленным.

Спецификация проблемы изменилась, и теперь я должен сделать это с помощью CGAL и Java, я прочитаю все «https://github.com/CGAL/cgal-swig-bindings » чтобы узнать, как использовать CGAL в Java … но я хотел бы получить некоторую помощь по этому конкретному экземпляру кода CGAL… Существуют ли более быстрые алгоритмы, уже реализованные в CGAL?

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

Комментарии:

1. Мало того, что трудно понять, чего пытается достичь ваш второй алгоритм, но он явно глючит. Проверьте это с double x[]={1,2,3} помощью , double y[]={0,0,0} , S=2 и CONSTANT_SQUARED=4 — возвращаемое значение равно false , даже если ни одна пара точек не разделена расстоянием> 2. Счастливой отладки, Vento — научитесь писать понятный код, это увеличит ваши шансы написать хороший код.

2. Извините, я забыл написать inside в if-блоке перед switchVar. Пожалуйста, укажите на это. Кстати S , это длина массива, поэтому в вашем примере должно быть 3.

3. Второй алгоритм пытается создать связанный подграф, вершины от индекса 0 до inside содержатся в подграфе. Если узел, которого нет в моем подграфе ( unchecked индекс, от inside 1 до S ), должен быть подключен к моему подграфу (проверка диапазона, если блок), я перемещаю этот новый узел внутри моего подграфа, переключая координаты. Условия while — это просто проверка границ и способ ускорить вычисления (если inside == S - 1 мой подграф — это весь граф, поэтому граф подключен -> первый while может остановиться).

Ответ №1:

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

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

Заметный результат