PostGIS  2.4.9dev-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  ASSERT_INT_EQUAL(uf->N, 10);
27  ASSERT_INTARRAY_EQUAL(uf->clusters, expected_initial_ids, 10);
28  ASSERT_INTARRAY_EQUAL(uf->cluster_sizes, expected_initial_sizes, 10);
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  ASSERT_INT_EQUAL(uf->N, 10);
47  ASSERT_INTARRAY_EQUAL(uf->clusters, expected_final_ids, 10);
48  ASSERT_INTARRAY_EQUAL(uf->cluster_sizes, expected_final_sizes, 10);
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 
114 {
115  UNIONFIND* uf = UF_create(10);
116 
117  uf->clusters[0] = 8;
118  uf->clusters[1] = 5;
119  uf->clusters[2] = 5;
120  uf->clusters[3] = 5;
121  uf->clusters[4] = 7;
122  uf->clusters[5] = 5;
123  uf->clusters[6] = 8;
124  uf->clusters[7] = 7;
125  uf->clusters[8] = 8;
126  uf->clusters[9] = 7;
127 
128  uf->cluster_sizes[0] = 3;
129  uf->cluster_sizes[1] = 4;
130  uf->cluster_sizes[2] = 4;
131  uf->cluster_sizes[3] = 4;
132  uf->cluster_sizes[4] = 3;
133  uf->cluster_sizes[5] = 4;
134  uf->cluster_sizes[6] = 3;
135  uf->cluster_sizes[7] = 3;
136  uf->cluster_sizes[8] = 3;
137  uf->cluster_sizes[9] = 3;
138 
139  /* 5 -> 0
140  * 7 -> 1
141  * 8 -> 2
142  */
143  uint32_t expected_collapsed_ids[] = { 2, 0, 0, 0, 1, 0, 2, 1, 2, 1 };
144  uint32_t* collapsed_ids = UF_get_collapsed_cluster_ids(uf, NULL);
145 
146  ASSERT_INTARRAY_EQUAL(collapsed_ids, expected_collapsed_ids, 10);
147 
148  lwfree(collapsed_ids);
149 
150  char is_in_cluster[] = { 0, 1, 1, 1, 0, 1, 0, 0, 0, 0 };
151  uint32_t expected_collapsed_ids2[] = { 8, 0, 0, 0, 7, 0, 8, 7, 8, 7 };
152 
153  collapsed_ids = UF_get_collapsed_cluster_ids(uf, is_in_cluster);
154  int i;
155  for (i = 0; i < uf->N; i++)
156  {
157  if (is_in_cluster[i])
158  ASSERT_INT_EQUAL(expected_collapsed_ids2[i], collapsed_ids[i]);
159  }
160 
161  lwfree(collapsed_ids);
162  UF_destroy(uf);
163 }
164 
165 void unionfind_suite_setup(void);
167 {
168  CU_pSuite suite = CU_add_suite("Clustering Union-Find", NULL, NULL);
174 }
static void test_unionfind_create(void)
Definition: cu_unionfind.c:18
void UF_destroy(UNIONFIND *uf)
Definition: lwunionfind.c:53
void lwfree(void *mem)
Definition: lwutil.c:244
uint32_t * clusters
Definition: lwunionfind.h:33
uint32_t * cluster_sizes
Definition: lwunionfind.h:34
uint32_t N
Definition: lwunionfind.h:36
unsigned int uint32_t
Definition: uthash.h:78
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:61
void unionfind_suite_setup(void)
Definition: cu_unionfind.c:166
static void test_unionfind_collapse_cluster_ids(void)
Definition: cu_unionfind.c:113
uint32_t * UF_ordered_by_cluster(UNIONFIND *uf)
Definition: lwunionfind.c:112
#define PG_ADD_TEST(suite, testfunc)
#define ASSERT_INT_EQUAL(o, e)
uint32_t num_clusters
Definition: lwunionfind.h:35
static void test_unionfind_union(void)
Definition: cu_unionfind.c:33
UNIONFIND * UF_create(uint32_t N)
Definition: lwunionfind.c:34
static void test_unionfind_ordered_by_cluster(void)
Definition: cu_unionfind.c:53
#define ASSERT_INTARRAY_EQUAL(o, e, n)
void UF_union(UNIONFIND *uf, uint32_t i, uint32_t j)
Definition: lwunionfind.c:84
static void test_unionfind_path_compression(void)
Definition: cu_unionfind.c:90
uint32_t * UF_get_collapsed_cluster_ids(UNIONFIND *uf, const char *is_in_cluster)
Definition: lwunionfind.c:145