Graphviz 13.1.3~dev.20250829.0113
Loading...
Searching...
No Matches
closest.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <assert.h>
12#include <limits.h>
13#include <neatogen/kkutils.h>
14#include <neatogen/closest.h>
15#include <stdbool.h>
16#include <stdint.h>
17#include <stdlib.h>
18#include <util/alloc.h>
19#include <util/gv_math.h>
20#include <util/list.h>
21#include <util/sort.h>
22
23/*****************************************
24** This module contains functions that **
25** given a 1-D layout construct a graph **
26** where close nodes in this layout are **
27** adjacent **
28*****************************************/
29
30typedef struct {
31 /* this structure represents two nodes in the 1-D layout */
32 size_t left;
33 size_t right;
34 double dist; /* distance between the nodes in the layout */
35} Pair;
36
37#define LT(p,q) ((p).dist < (q).dist)
38#define EQ(p,q) ((p).dist == (q).dist)
39
40typedef LIST(Pair *) pairs_t;
41
42static void push(pairs_t *s, Pair x) {
43
44 // copy the item to save it on the stack
45 Pair *copy = gv_alloc(sizeof(x));
46 *copy = x;
47
49}
50
51static bool pop(pairs_t *s, Pair *x) {
52
53 // is the stack empty?
54 if (LIST_IS_EMPTY(s)) {
55 return false;
56 }
57
58 // remove the top and pass it back to the caller
60 *x = *top;
61
62 // discard the previously saved copy
63 free(top);
64
65 return true;
66}
67
68#define sub(h,i) (*LIST_GET((h), (i)))
69
70/* An auxulliary data structure (a heap) for
71 * finding the closest pair in the layout
72 */
73typedef struct {
75 size_t heapSize;
76 size_t maxSize;
77} PairHeap;
78
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)))
85
86static void heapify(PairHeap *h, size_t i) {
87 size_t largest;
88 while (1) {
89 size_t l = left(i);
90 size_t r = right(i);
91 if (insideHeap(h, l) && greaterPriority(h, l, i))
92 largest = l;
93 else
94 largest = i;
95 if (insideHeap(h, r) && greaterPriority(h, r, largest))
96 largest = r;
97 if (largest == i)
98 break;
99
100 SWAP(&h->data[largest], &h->data[i]);
101 i = largest;
102 }
103}
104
105static void freeHeap(PairHeap * h)
106{
107 free(h->data);
108}
109
110static void initHeap(PairHeap *h, double *place, size_t *ordering, size_t n) {
111 Pair edge;
112
113 h->heapSize = n == 0 ? 0 : (n - 1);
114 h->maxSize = h->heapSize;
115 h->data = gv_calloc(h->maxSize, sizeof(Pair));
116
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]];
121 h->data[i] = edge;
122 }
123 for (size_t j = (n - 1) / 2; n != 0 && j != SIZE_MAX; j--) {
124 heapify(h, j);
125 }
126}
127
128static bool extractMax(PairHeap * h, Pair * max)
129{
130 if (h->heapSize == 0)
131 return false;
132
133 *max = h->data[0];
134 h->data[0] = h->data[h->heapSize - 1];
135 h->heapSize--;
136 heapify(h, 0);
137 return true;
138}
139
140static void insert(PairHeap * h, Pair edge)
141{
142 size_t i = h->heapSize;
143 if (h->heapSize == h->maxSize) {
144 size_t newSize = h->maxSize * 2;
145 h->data = gv_recalloc(h->data, h->maxSize, newSize, sizeof(Pair));
146 h->maxSize = newSize;
147 }
148 h->heapSize++;
149 h->data[i] = edge;
150 while (i > 0 && greaterPriority(h, i, parent(i))) {
151 SWAP(&h->data[i], &h->data[parent(i)]);
152 i = parent(i);
153 }
154}
155
156static int cmp(const void *a, const void *b, void *context) {
157 const size_t *x = a;
158 const size_t *y = b;
159 const double *place = context;
160
161 if (place[*x] < place[*y]) {
162 return -1;
163 }
164 if (place[*x] > place[*y]) {
165 return 1;
166 }
167 return 0;
168}
169
170static void find_closest_pairs(double *place, size_t n, int num_pairs,
171 pairs_t* pairs_stack) {
172 /* Fill the stack 'pairs_stack' with 'num_pairs' closest pairs int the 1-D layout 'place' */
174 size_t *left = gv_calloc(n, sizeof(size_t));
175 size_t *right = gv_calloc(n, sizeof(size_t));
176 Pair pair = {0}, new_pair;
177
178 /* Order the nodes according to their place */
179 size_t *ordering = gv_calloc(n, sizeof(size_t));
180 size_t *inv_ordering = gv_calloc(n, sizeof(size_t));
181
182 for (size_t i = 0; i < n; i++) {
183 ordering[i] = i;
184 }
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;
188 }
189
190 /* Initialize heap with all consecutive pairs */
191 initHeap(&heap, place, ordering, n);
192
193 /* store the leftmost and rightmost neighbors of each node that were entered into heap */
194 for (size_t i = 1; i < n; i++) {
195 left[ordering[i]] = ordering[i - 1];
196 }
197 for (size_t i = 0; n != 0 && i < n - 1; i++) {
198 right[ordering[i]] = ordering[i + 1];
199 }
200
201 /* extract the 'num_pairs' closest pairs */
202 for (int i = 0; i < num_pairs; i++) {
203
204 if (!extractMax(&heap, &pair)) {
205 break; /* not enough pairs */
206 }
207 push(pairs_stack, pair);
208 /* insert to heap "descendant" pairs */
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];
213 if (inv_ordering[right[neighbor]] < right_index) {
214 /* we have a new pair */
215 new_pair.left = neighbor;
216 new_pair.right = pair.right;
217 new_pair.dist = place[pair.right] - place[neighbor];
218 insert(&heap, new_pair);
219 right[neighbor] = pair.right;
220 left[pair.right] = neighbor;
221 }
222 }
223 if (right_index < n - 1) {
224 size_t neighbor = ordering[right_index + 1];
225 if (inv_ordering[left[neighbor]] > left_index) {
226 /* we have a new pair */
227 new_pair.left = pair.left;
228 new_pair.right = neighbor;
229 new_pair.dist = place[neighbor] - place[pair.left];
230 insert(&heap, new_pair);
231 left[neighbor] = pair.left;
232 right[pair.left] = neighbor;
233 }
234 }
235 }
236 free(left);
237 free(right);
238 free(ordering);
239 free(inv_ordering);
240 freeHeap(&heap);
241}
242
243static void add_edge(vtx_data * graph, int u, int v)
244{
245 for (size_t i = 0; i < graph[u].nedges; i++) {
246 if (graph[u].edges[i] == v) {
247 /* edge already exist */
248 return;
249 }
250 }
251 /* add the edge */
252 graph[u].edges[graph[u].nedges++] = v;
253 graph[v].edges[graph[v].nedges++] = u;
254 if (graph[0].ewgts != NULL) {
255 graph[u].ewgts[0]--;
256 graph[v].ewgts[0]--;
257 }
258}
259
260static void construct_graph(size_t n, pairs_t *edges_stack,
261 vtx_data **New_graph) {
262 /* construct an unweighted graph using the edges 'edges_stack' */
263 vtx_data *new_graph;
264
265 /* first compute new degrees and nedges; */
266 int *degrees = gv_calloc(n, sizeof(int));
267 size_t top = LIST_SIZE(edges_stack);
268 size_t new_nedges = 2 * top + n;
269 Pair pair;
270 int *edges = gv_calloc(new_nedges, sizeof(int));
271 float *weights = gv_calloc(new_nedges, sizeof(float));
272
273 for (size_t i = 0; i < n; i++) {
274 degrees[i] = 1; /* save place for the self loop */
275 }
276 for (size_t i = 0; i < top; i++) {
277 pair = sub(edges_stack, i);
278 degrees[pair.left]++;
279 degrees[pair.right]++;
280 }
281
282 /* copy graph into new_graph: */
283 for (size_t i = 0; i < new_nedges; i++) {
284 weights[i] = 1.0;
285 }
286
287 *New_graph = new_graph = gv_calloc(n, sizeof(vtx_data));
288 for (size_t i = 0; i < n; i++) {
289 new_graph[i].nedges = 1;
290 new_graph[i].ewgts = weights;
291 new_graph[i].edges = edges;
292 assert(i <= INT_MAX);
293 *edges = (int)i; // self loop for Lap
294 *weights = 0; /* self loop weight for Lap */
295 weights += degrees[i];
296 edges += degrees[i]; /* reserve space for possible more edges */
297 }
298
299 free(degrees);
300
301 /* add all edges from stack */
302 while (pop(edges_stack, &pair)) {
303 assert(pair.left <= INT_MAX);
304 assert(pair.right <= INT_MAX);
305 add_edge(new_graph, (int)pair.left, (int)pair.right);
306 }
307}
308
309void
310closest_pairs2graph(double *place, int n, int num_pairs, vtx_data ** graph)
311{
312 /* build a graph with with edges between the 'num_pairs' closest pairs in the 1-D space: 'place' */
313 pairs_t pairs_stack = {0};
314 assert(n >= 0);
315 find_closest_pairs(place, (size_t)n, num_pairs, &pairs_stack);
316 construct_graph((size_t)n, &pairs_stack, graph);
317 LIST_FREE(&pairs_stack);
318}
Agobj_t * copy(Agraph_t *g, Agobj_t *obj)
Definition actions.c:145
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define greaterPriority(h, i, j)
Definition closest.c:83
static void find_closest_pairs(double *place, size_t n, int num_pairs, pairs_t *pairs_stack)
Definition closest.c:170
static void initHeap(PairHeap *h, double *place, size_t *ordering, size_t n)
Definition closest.c:110
static void freeHeap(PairHeap *h)
Definition closest.c:105
void closest_pairs2graph(double *place, int n, int num_pairs, vtx_data **graph)
Definition closest.c:310
#define left(i)
Definition closest.c:79
#define parent(i)
Definition closest.c:81
static bool extractMax(PairHeap *h, Pair *max)
Definition closest.c:128
static void add_edge(vtx_data *graph, int u, int v)
Definition closest.c:243
static void heapify(PairHeap *h, size_t i)
Definition closest.c:86
#define right(i)
Definition closest.c:80
static void construct_graph(size_t n, pairs_t *edges_stack, vtx_data **New_graph)
Definition closest.c:260
#define insideHeap(h, i)
Definition closest.c:82
static void insert(PairHeap *h, Pair edge)
Definition closest.c:140
#define sub(h, i)
Definition closest.c:68
static int cmp(const void *a, const void *b, void *context)
Definition closest.c:156
static Agnode_t * pop(void)
Definition ccomps.c:220
void free(void *)
edge
Definition gmlparse.y:244
#define SIZE_MAX
Definition gmlscan.c:347
static gstack_t * push(gstack_t *s, Agraph_t *subg)
Definition grammar.c:1655
node NULL
Definition grammar.y:181
Agraph_t * graph(char *name)
Definition gv.cpp:30
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:131
static Agedge_t * top(edge_stack_t *sp)
Definition tred.c:73
type-generic dynamically expanding list
#define LIST(type)
Definition list.h:55
#define LIST_SIZE(list)
Definition list.h:80
#define LIST_FREE(list)
Definition list.h:379
#define LIST_POP_BACK(list)
Definition list.h:416
#define LIST_IS_EMPTY(list)
Definition list.h:90
#define LIST_PUSH_BACK(list, item)
Definition list.h:393
#define neighbor(t, i, edim, elist)
Definition make_map.h:41
static int num_pairs
Definition pca.c:20
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
Definition sort.h:24
size_t maxSize
Definition closest.c:76
size_t heapSize
Definition closest.c:75
Pair * data
Definition closest.c:74
Definition closest.c:30
size_t right
the right node in the pair
Definition closest.c:33
double dist
Definition closest.c:34
size_t left
the left node in the pair
Definition closest.c:32
float * ewgts
Definition sparsegraph.h:36
unsigned nedges
unsigned * edges
Definition grammar.c:90