Java/CGAL验证图是否连接（描述中有一些限制）

这是我第一次使用CGAL，你们中的一些人可能会争论为什么我必须从类似的东西学习CGAL，但这是一个新项目，我必须（和...是的，我必须使用CGAL和Java组合）：/长话短说...我只有：Java/CGAL验证图是否连接（描述中有一些限制）

两个双数组，表示我的顶点的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，没有给出其他信息。

Question，do x and y描述了一个连通图？

现在我有两个algoritms：

算法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”以了解如何在Java中使用CGAL ....但我想要关于此特定的一些帮助CGAL代码的实例... CGAL中是否已经实现了更快的算法？

谢谢你的时代家伙！快乐的编码！

来源

2016-10-04 Vento

不仅很难理解你的第二个算法中试图实现，但显而易见的是越野车。用'double x [] = {1,2,3}'，'double y [] = {0,0,0}'，'S = 2'和'CONSTANT_SQUARED = 4'测试它，返回的值是'false '即使没有一对点之间的距离> 2。**快速调试，Vento ** - 学会编写清晰的代码，它会增加您编写好代码的机会。 –

Ups抱歉，我忘记在switchVar之前的if块中写入'++内'。 Ty指出这一点。顺便说一句'S'是数组长度，所以在你的例子中应该是3. – Vento

第二个alg尝试创建一个连接的子图，从子索引'0'到'inside'的顶点包含在子图中。如果一个不在我的子图中的节点（'未检查'索引，从'inside + 1'到'S'）应该连接到我的子图（范围检查，如果是block），我将这个新节点我的子图通过切换坐标。 while-conditions只是边界检查和使计算更快的方法（如果内部== S - 1，我的子图是整个图，所以图连接 - >第一个可以停止）。 – Vento

我相信，如果没有空间索引的方法，在最坏的情况下（所有连接）你要达到的最佳性能将是O(n*(n-1)/2)。

如果你能负担得起建立一个空间索引（有足够的内存来支付速度上的提升），你可以考虑R-tree and variants - 插入是O(n)搜索O(log2(n))：这将“通过审查的距离异常检测”得到你的方法最坏情况下的成本为O(n*log2(n))。

来源

2016-10-05 00:57:34

Java/CGAL验证图是否连接（描述中有一些限制）

回答

相关问题