36#define LT(p,q) ((p).dist < (q).dist)
37#define EQ(p,q) ((p).dist == (q).dist)
65#define sub(h,i) (*(Pair*)gv_stack_get((h), (i)))
76#define left(i) (2*(i))
77#define right(i) (2*(i)+1)
78#define parent(i) ((i)/2)
79#define insideHeap(h,i) ((i)<h->heapSize)
80#define greaterPriority(h,i,j) \
81 (LT(h->data[i],h->data[j]) || ((EQ(h->data[i],h->data[j])) && (rand()%2)))
83#define exchange(h,i,j) {Pair temp; \
85 h->data[i]=h->data[j]; \
120 for (
size_t i = 0; n != 0 && i < n - 1; i++) {
121 edge.left = ordering[i];
122 edge.right = ordering[i + 1];
123 edge.dist = place[ordering[i + 1]] - place[ordering[i]];
126 for (
size_t j = (n - 1) / 2; n != 0 && j !=
SIZE_MAX; j--) {
147 size_t newSize = h->
maxSize * 2;
159static int cmp(
const void *a,
const void *b,
void *context) {
162 const double *place = context;
164 if (place[*x] < place[*y]) {
167 if (place[*x] > place[*y]) {
174 gv_stack_t* pairs_stack) {
182 size_t *ordering =
gv_calloc(n,
sizeof(
size_t));
183 size_t *inv_ordering =
gv_calloc(n,
sizeof(
size_t));
185 for (
size_t i = 0; i < n; i++) {
188 gv_sort(ordering, n,
sizeof(ordering[0]),
cmp, place);
189 for (
size_t i = 0; i < n; i++) {
190 inv_ordering[ordering[i]] = i;
197 for (
size_t i = 1; i < n; i++) {
198 left[ordering[i]] = ordering[i - 1];
200 for (
size_t i = 0; n != 0 && i < n - 1; i++) {
201 right[ordering[i]] = ordering[i + 1];
212 size_t left_index = inv_ordering[
pair.left];
213 size_t right_index = inv_ordering[
pair.right];
214 if (left_index > 0) {
215 size_t neighbor = ordering[left_index - 1];
219 new_pair.right =
pair.right;
226 if (right_index < n - 1) {
227 size_t neighbor = ordering[right_index + 1];
230 new_pair.left =
pair.left;
248 for (
size_t i = 0; i <
graph[u].nedges; i++) {
249 if (
graph[u].edges[i] == v) {
269 int *degrees =
gv_calloc(n,
sizeof(
int));
271 size_t new_nedges = 2 *
top + n;
273 int *edges =
gv_calloc(new_nedges,
sizeof(
int));
274 float *weights =
gv_calloc(new_nedges,
sizeof(
float));
276 for (
size_t i = 0; i < n; i++) {
279 for (
size_t i = 0; i <
top; i++) {
281 degrees[
pair.left]++;
282 degrees[
pair.right]++;
286 for (
size_t i = 0; i < new_nedges; i++) {
291 for (
size_t i = 0; i < n; i++) {
293 new_graph[i].
ewgts = weights;
294 new_graph[i].
edges = edges;
295 assert(i <= INT_MAX);
298 weights += degrees[i];
305 while (
pop(edges_stack, &
pair)) {
306 assert(
pair.left <= INT_MAX);
307 assert(
pair.right <= INT_MAX);
316 gv_stack_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 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 void push(gv_stack_t *s, Pair x)
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)
#define exchange(h, i, j)
static void construct_graph(size_t n, gv_stack_t *edges_stack, vtx_data **New_graph)
static void find_closest_pairs(double *place, size_t n, int num_pairs, gv_stack_t *pairs_stack)
static void insert(PairHeap *h, Pair edge)
static int cmp(const void *a, const void *b, void *context)
Agraph_t * graph(char *name)
static Agedge_t * top(gv_stack_t *sp)
#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
Implementation of a dynamically expanding stack data structure.
static void stack_push(gv_stack_t *stack, void *item)
static size_t stack_size(const gv_stack_t *stack)
static void * stack_pop(gv_stack_t *stack)
static void stack_reset(gv_stack_t *stack)
static bool stack_is_empty(const gv_stack_t *stack)
size_t right
the right node in the pair
size_t left
the left node in the pair