PostGIS  2.2.7dev-r@@SVN_REVISION@@
cu_unionfind.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * Copyright 2015 Daniel Baston
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU General Public Licence. See the COPYING file.
10  *
11  **********************************************************************/
12 
13 #include "CUnit/Basic.h"
14 
15 #include "../lwunionfind.h"
16 #include "cu_tester.h"
17 
18 static void test_unionfind_create(void)
19 {
20  UNIONFIND *uf = UF_create(10);
21 
22  uint32_t expected_initial_ids[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
23  uint32_t expected_initial_sizes[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
24 
25  CU_ASSERT_EQUAL(10, uf->N);
26  CU_ASSERT_EQUAL(10, uf->num_clusters);
27  CU_ASSERT_EQUAL(0, memcmp(uf->clusters, expected_initial_ids, 10*sizeof(uint32_t)));
28  CU_ASSERT_EQUAL(0, memcmp(uf->cluster_sizes, expected_initial_sizes, 10*sizeof(uint32_t)));
29 
30  UF_destroy(uf);
31 }
32 
33 static void test_unionfind_union(void)
34 {
35  UNIONFIND *uf = UF_create(10);
36 
37  UF_union(uf, 0, 7); /* both have size = 1, so 7 becomes 0 */
38  UF_union(uf, 3, 2); /* both have size = 1, so 3 becomes 2 */
39  UF_union(uf, 8, 7); /* add 8 (smaller) to 0-7 (larger) */
40  UF_union(uf, 1, 2); /* add 1 (smaller) to 2-3 (larger) */
41 
42  uint32_t expected_final_ids[] = { 0, 2, 2, 2, 4, 5, 6, 0, 0, 9 };
43  uint32_t expected_final_sizes[] = { 3, 0, 3, 0, 1, 1, 1, 0, 0, 1 };
44 
45  CU_ASSERT_EQUAL(10, uf->N);
46  CU_ASSERT_EQUAL(6, uf->num_clusters);
47  CU_ASSERT_EQUAL(0, memcmp(uf->clusters, expected_final_ids, 10*sizeof(uint32_t)));
48  CU_ASSERT_EQUAL(0, memcmp(uf->cluster_sizes, expected_final_sizes, 10*sizeof(uint32_t)));
49 
50  UF_destroy(uf);
51 }
52 
54 {
55  uint32_t final_clusters[] = { 0, 2, 2, 2, 4, 5, 6, 0, 0, 2 };
56  uint32_t final_sizes[] = { 3, 0, 4, 0, 1, 1, 1, 0, 0, 0 };
57 
58  /* Manually create UF at desired final state */
59  UNIONFIND uf =
60  {
61  .N = 10,
62  .num_clusters = 5,
63  .clusters = final_clusters,
64  .cluster_sizes = final_sizes
65  };
66 
67  uint32_t* ids_by_cluster = UF_ordered_by_cluster(&uf);
68 
69  char encountered_cluster[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
70 
71  uint32_t i;
72  for (i = 0; i < uf.N; i++)
73  {
74  uint32_t c = final_clusters[ids_by_cluster[i]];
75  if (!encountered_cluster[c])
76  {
77  encountered_cluster[c] = 1;
78  }
79  else
80  {
81  /* If we've seen an element of this cluster before, then the
82  * current cluster must be the same as the previous cluster. */
83  uint32_t c_prev = final_clusters[ids_by_cluster[i-1]];
84  CU_ASSERT_EQUAL(c, c_prev);
85  }
86  }
87  lwfree(ids_by_cluster);
88 }
89 
91 {
92  UNIONFIND* uf = UF_create(5);
93  uint32_t i;
94 
95  uf->clusters[1] = 0;
96  uf->clusters[2] = 1;
97  uf->clusters[3] = 2;
98  uf->clusters[4] = 3;
99 
100  /* Calling "find" on a leaf should attach all nodes between the root and the
101  * leaf directly to the root. */
102  uint32_t root = UF_find(uf, 4);
103  for (i = 0; i < uf->N; i++)
104  {
105  /* Verify that all cluster references have been updated to point
106  * directly to the root. */
107  CU_ASSERT_EQUAL(root, uf->clusters[i]);
108  }
109 
110  UF_destroy(uf);
111 }
112 
113 void unionfind_suite_setup(void);
115 {
116  CU_pSuite suite = CU_add_suite("Clustering Union-Find", NULL, NULL);
121 }
static void test_unionfind_create(void)
Definition: cu_unionfind.c:18
void UF_destroy(UNIONFIND *uf)
Definition: lwunionfind.c:40
void lwfree(void *mem)
Definition: lwutil.c:214
uint32_t * clusters
Definition: lwunionfind.h:20
uint32_t * cluster_sizes
Definition: lwunionfind.h:21
uint32_t N
Definition: lwunionfind.h:23
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:48
void unionfind_suite_setup(void)
Definition: cu_unionfind.c:114
uint32_t * UF_ordered_by_cluster(UNIONFIND *uf)
Definition: lwunionfind.c:93
#define PG_ADD_TEST(suite, testfunc)
uint32_t num_clusters
Definition: lwunionfind.h:22
static void test_unionfind_union(void)
Definition: cu_unionfind.c:33
UNIONFIND * UF_create(uint32_t N)
Definition: lwunionfind.c:21
static void test_unionfind_ordered_by_cluster(void)
Definition: cu_unionfind.c:53
void UF_union(UNIONFIND *uf, uint32_t i, uint32_t j)
Definition: lwunionfind.c:65
static void test_unionfind_path_compression(void)
Definition: cu_unionfind.c:90