Java/CGAL verify if a graph is connected (some constraints in description)

Question

it's my first time with CGAL, some of you may argue why do I have to learn CGAL from something like that, but it's a new project that I must do (and... yes, I must use CGAL and Java combined) :/ Long story short... I only have:

• Two double arrays, representing x and y coordinates of my vertices. Let's call them double[] x, y;.
• Both arrays have S random values.
• Two vertices, u and w are connected if distance(x[u], y[u], x[w], y[w]) < CONSTANT (ofc. I do distanceSquared(x[u], y[u], x[w], y[w]) < CONSTANT_SQUARED, so I avoid to call sqrt()).
• x and y are filled randomly with values from 0 to UPPER_LIMIT, no other infos are given.

Question, do x and y describes a connected graph?

Right now I have two algoritms:

• Algorithm 1:

  1. Build adjacency list (Arraylist<Integer>[] adjLists;) for each vertex (only upper triangular matrix explored). Complexity O(|V|^2) (V = vertices set).
  2. Recursive graph exploration, vertex marking and counting, if visited vertex equals S my graph have only one connected component, my graph is connected. Complexity O(|E|) (E = edges set).

• Algorithm 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;
  }
  

Funny thing the second one is slower, I do not use data structures, the code is iterative and in-place but the heavy use of switch makes it slow as hell.

The problem spec changed and now I must do it with CGAL and Java, I'll read the whole "https://github.com/CGAL/cgal-swig-bindings" to learn how to use CGAL within Java.... but I'd like some help about this specific instance of CGAL code... Are there faster algorithms already implemented in CGAL?

Thank you for your times guys! Happy coding!

Answer 1

I believe that, without a method of spatial indexing, the best performance you are going to achieve in the worst-case-scenario (all connected) is going to be O(n*(n-1)/2).

If you can afford to build a spatial index (have enough memory to pay for the boost in speed), you may consider R-tree and variants - insertion is O(n) searching is O(log2(n)): this will get your "outlier detection by examining distances" approach for a cost of of O(n*log2(n)) in the worst-case-scenario.

A notable result