37#define LT(p,q) ((p).dist < (q).dist)
38#define EQ(p,q) ((p).dist == (q).dist)
68#define sub(h,i) (*LIST_GET((h), (i)))
79#define left(i) (2*(i))
80#define right(i) (2*(i)+1)
81#define parent(i) ((i)/2)
82#define insideHeap(h,i) ((i)<h->heapSize)
83#define greaterPriority(h,i,j) \
84 (LT(h->data[i],h->data[j]) || ((EQ(h->data[i],h->data[j])) && (rand()%2)))
117 for (
size_t i = 0; n != 0 && i < n - 1; i++) {
118 edge.left = ordering[i];
119 edge.right = ordering[i + 1];
120 edge.dist = place[ordering[i + 1]] - place[ordering[i]];
123 for (
size_t j = (n - 1) / 2; n != 0 && j !=
SIZE_MAX; j--) {
144 size_t newSize = h->
maxSize * 2;
156static int cmp(
const void *a,
const void *b,
void *context) {
159 const double *place = context;
161 if (place[*x] < place[*y]) {
164 if (place[*x] > place[*y]) {
171 pairs_t* pairs_stack) {
179 size_t *ordering =
gv_calloc(n,
sizeof(
size_t));
180 size_t *inv_ordering =
gv_calloc(n,
sizeof(
size_t));
182 for (
size_t i = 0; i < n; i++) {
185 gv_sort(ordering, n,
sizeof(ordering[0]),
cmp, place);
186 for (
size_t i = 0; i < n; i++) {
187 inv_ordering[ordering[i]] = i;
194 for (
size_t i = 1; i < n; i++) {
195 left[ordering[i]] = ordering[i - 1];
197 for (
size_t i = 0; n != 0 && i < n - 1; i++) {
198 right[ordering[i]] = ordering[i + 1];
209 size_t left_index = inv_ordering[
pair.left];
210 size_t right_index = inv_ordering[
pair.right];
211 if (left_index > 0) {
212 size_t neighbor = ordering[left_index - 1];
216 new_pair.right =
pair.right;
223 if (right_index < n - 1) {
224 size_t neighbor = ordering[right_index + 1];
227 new_pair.left =
pair.left;
245 for (
size_t i = 0; i <
graph[u].nedges; i++) {
246 if (
graph[u].edges[i] == v) {
266 int *degrees =
gv_calloc(n,
sizeof(
int));
268 size_t new_nedges = 2 *
top + n;
270 int *edges =
gv_calloc(new_nedges,
sizeof(
int));
271 float *weights =
gv_calloc(new_nedges,
sizeof(
float));
273 for (
size_t i = 0; i < n; i++) {
276 for (
size_t i = 0; i <
top; i++) {
278 degrees[
pair.left]++;
279 degrees[
pair.right]++;
283 for (
size_t i = 0; i < new_nedges; i++) {
288 for (
size_t i = 0; i < n; i++) {
290 new_graph[i].
ewgts = weights;
291 new_graph[i].
edges = edges;
292 assert(i <= INT_MAX);
295 weights += degrees[i];
302 while (
pop(edges_stack, &
pair)) {
303 assert(
pair.left <= INT_MAX);
304 assert(
pair.right <= INT_MAX);
313 pairs_t pairs_stack = {0};
Agobj_t * copy(Agraph_t *g, Agobj_t *obj)
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
#define greaterPriority(h, i, j)
static void find_closest_pairs(double *place, size_t n, int num_pairs, pairs_t *pairs_stack)
static void initHeap(PairHeap *h, double *place, size_t *ordering, size_t n)
static void freeHeap(PairHeap *h)
void closest_pairs2graph(double *place, int n, int num_pairs, vtx_data **graph)
static bool extractMax(PairHeap *h, Pair *max)
static void add_edge(vtx_data *graph, int u, int v)
static void heapify(PairHeap *h, size_t i)
static void construct_graph(size_t n, pairs_t *edges_stack, vtx_data **New_graph)
static void insert(PairHeap *h, Pair edge)
static int cmp(const void *a, const void *b, void *context)
static gstack_t * push(gstack_t *s, Agraph_t *subg)
Agraph_t * graph(char *name)
Arithmetic helper functions.
static Agedge_t * top(edge_stack_t *sp)
type-generic dynamically expanding list
#define LIST_POP_BACK(list)
#define LIST_IS_EMPTY(list)
#define LIST_PUSH_BACK(list, item)
#define neighbor(t, i, edim, elist)
qsort with carried along context
static void gv_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
qsort with an extra state parameter, ala qsort_r
size_t right
the right node in the pair
size_t left
the left node in the pair