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

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

  • Два двойных массива, представляющие координаты X и y моих вершин. Давайте позвоним им double[] x, y;.
  • Оба массива имеют Sслучайные значения.
  • Две вершины, uи wсоединены, если distance(x[u], y[u], x[w], y[w]) < CONSTANT(ofc. I dodistanceSquared(x[u], y[u], x[w], y[w]) < CONSTANT_SQUARED, so I avoid to call 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 && 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?

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

1 ответ

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

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

    Ощутимый результат