Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
pqueue.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * pqueue.c
5  *
6  * This file contains functions for manipulating the bucket list
7  * representation of the gains associated with each vertex in a graph.
8  * These functions are used by the refinement algorithms
9  *
10  * Started 9/2/94
11  * George
12  *
13  * $Id: pqueue.c,v 1.1 1998/11/27 17:59:28 karypis Exp $
14  *
15  */
16 
17 #include <metis.h>
18 
19 
20 /*************************************************************************
21 * This function initializes the data structures of the priority queue
22 **************************************************************************/
23 void PQueueInit(CtrlType *ctrl, PQueueType *queue, int maxnodes, int maxgain)
24 {
25  int i, j, ncore;
26 
27  queue->nnodes = 0;
28  queue->maxnodes = maxnodes;
29 
30  queue->buckets = NULL;
31  queue->nodes = NULL;
32  queue->heap = NULL;
33  queue->locator = NULL;
34 
35  if (maxgain > PLUS_GAINSPAN || maxnodes < 500)
36  queue->type = 2;
37  else
38  queue->type = 1;
39 
40  if (queue->type == 1) {
41  queue->pgainspan = amin(PLUS_GAINSPAN, maxgain);
42  queue->ngainspan = amin(NEG_GAINSPAN, maxgain);
43 
44  j = queue->ngainspan+queue->pgainspan+1;
45 
46  ncore = 2 + (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes + (sizeof(ListNodeType *)/sizeof(idxtype))*j;
47 
48  if (WspaceAvail(ctrl) > ncore) {
49  queue->nodes = (ListNodeType *)idxwspacemalloc(ctrl, (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes);
50  queue->buckets = (ListNodeType **)idxwspacemalloc(ctrl, (sizeof(ListNodeType *)/sizeof(idxtype))*j);
51  queue->mustfree = 0;
52  }
53  else { /* Not enough memory in the wspace, allocate it */
54  queue->nodes = (ListNodeType *)idxmalloc((sizeof(ListNodeType)/sizeof(idxtype))*maxnodes, "PQueueInit: queue->nodes");
55  queue->buckets = (ListNodeType **)idxmalloc((sizeof(ListNodeType *)/sizeof(idxtype))*j, "PQueueInit: queue->buckets");
56  queue->mustfree = 1;
57  }
58 
59  for (i=0; i<maxnodes; i++)
60  queue->nodes[i].id = i;
61 
62  for (i=0; i<j; i++)
63  queue->buckets[i] = NULL;
64 
65  queue->buckets += queue->ngainspan; /* Advance buckets by the ngainspan proper indexing */
66  queue->maxgain = -queue->ngainspan;
67  }
68  else {
69  queue->heap = (KeyValueType *)idxwspacemalloc(ctrl, (sizeof(KeyValueType)/sizeof(idxtype))*maxnodes);
70  queue->locator = idxwspacemalloc(ctrl, maxnodes);
71  idxset(maxnodes, -1, queue->locator);
72  }
73 
74 }
75 
76 
77 /*************************************************************************
78 * This function resets the buckets
79 **************************************************************************/
80 void PQueueReset(PQueueType *queue)
81 {
82  int i, j;
83  queue->nnodes = 0;
84 
85  if (queue->type == 1) {
86  queue->maxgain = -queue->ngainspan;
87 
88  j = queue->ngainspan+queue->pgainspan+1;
89  queue->buckets -= queue->ngainspan;
90  for (i=0; i<j; i++)
91  queue->buckets[i] = NULL;
92  queue->buckets += queue->ngainspan;
93  }
94  else {
95  idxset(queue->maxnodes, -1, queue->locator);
96  }
97 
98 }
99 
100 
101 /*************************************************************************
102 * This function frees the buckets
103 **************************************************************************/
104 void PQueueFree(CtrlType *ctrl, PQueueType *queue)
105 {
106 
107  if (queue->type == 1) {
108  if (queue->mustfree) {
109  queue->buckets -= queue->ngainspan;
110  GKfree(&queue->nodes, &queue->buckets, LTERM);
111  }
112  else {
113  idxwspacefree(ctrl, sizeof(ListNodeType *)*(queue->ngainspan+queue->pgainspan+1)/sizeof(idxtype));
114  idxwspacefree(ctrl, sizeof(ListNodeType)*queue->maxnodes/sizeof(idxtype));
115  }
116  }
117  else {
118  idxwspacefree(ctrl, sizeof(KeyValueType)*queue->maxnodes/sizeof(idxtype));
119  idxwspacefree(ctrl, queue->maxnodes);
120  }
121 
122  queue->maxnodes = 0;
123 }
124 
125 
126 /*************************************************************************
127 * This function returns the number of nodes in the queue
128 **************************************************************************/
130 {
131  return queue->nnodes;
132 }
133 
134 
135 /*************************************************************************
136 * This function adds a node of certain gain into a partition
137 **************************************************************************/
138 int PQueueInsert(PQueueType *queue, int node, int gain)
139 {
140  int i, j, k;
141  idxtype *locator;
142  ListNodeType *newnode;
143  KeyValueType *heap;
144 
145  if (queue->type == 1) {
146  ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);
147 
148  /* Allocate and add the node */
149  queue->nnodes++;
150  newnode = queue->nodes + node;
151 
152  /* Attach this node in the doubly-linked list */
153  newnode->next = queue->buckets[gain];
154  newnode->prev = NULL;
155  if (newnode->next != NULL)
156  newnode->next->prev = newnode;
157  queue->buckets[gain] = newnode;
158 
159  if (queue->maxgain < gain)
160  queue->maxgain = gain;
161  }
162  else {
163  ASSERT(CheckHeap(queue));
164 
165  heap = queue->heap;
166  locator = queue->locator;
167 
168  ASSERT(locator[node] == -1);
169 
170  i = queue->nnodes++;
171  while (i > 0) {
172  j = (i-1)/2;
173  if (heap[j].key < gain) {
174  heap[i] = heap[j];
175  locator[heap[i].val] = i;
176  i = j;
177  }
178  else
179  break;
180  }
181  ASSERT(i >= 0);
182  heap[i].key = gain;
183  heap[i].val = node;
184  locator[node] = i;
185 
186  ASSERT(CheckHeap(queue));
187  }
188 
189  return 0;
190 }
191 
192 
193 /*************************************************************************
194 * This function deletes a node from a partition and reinserts it with
195 * an updated gain
196 **************************************************************************/
197 int PQueueDelete(PQueueType *queue, int node, int gain)
198 {
199  int i, j, newgain, oldgain;
200  idxtype *locator;
201  ListNodeType *newnode, **buckets;
202  KeyValueType *heap;
203 
204  if (queue->type == 1) {
205  ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);
206  ASSERT(queue->nnodes > 0);
207 
208  buckets = queue->buckets;
209  queue->nnodes--;
210  newnode = queue->nodes+node;
211 
212  /* Remove newnode from the doubly-linked list */
213  if (newnode->prev != NULL)
214  newnode->prev->next = newnode->next;
215  else
216  buckets[gain] = newnode->next;
217  if (newnode->next != NULL)
218  newnode->next->prev = newnode->prev;
219 
220  if (buckets[gain] == NULL && gain == queue->maxgain) {
221  if (queue->nnodes == 0)
222  queue->maxgain = -queue->ngainspan;
223  else
224  for (; buckets[queue->maxgain]==NULL; queue->maxgain--);
225  }
226  }
227  else { /* Heap Priority Queue */
228  heap = queue->heap;
229  locator = queue->locator;
230 
231  ASSERT(locator[node] != -1);
232  ASSERT(heap[locator[node]].val == node);
233 
234  ASSERT(CheckHeap(queue));
235 
236  i = locator[node];
237  locator[node] = -1;
238 
239  if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {
240  node = heap[queue->nnodes].val;
241  newgain = heap[queue->nnodes].key;
242  oldgain = heap[i].key;
243 
244  if (oldgain < newgain) { /* Filter-up */
245  while (i > 0) {
246  j = (i-1)>>1;
247  if (heap[j].key < newgain) {
248  heap[i] = heap[j];
249  locator[heap[i].val] = i;
250  i = j;
251  }
252  else
253  break;
254  }
255  }
256  else { /* Filter down */
257  while ((j=2*i+1) < queue->nnodes) {
258  if (heap[j].key > newgain) {
259  if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
260  j = j+1;
261  heap[i] = heap[j];
262  locator[heap[i].val] = i;
263  i = j;
264  }
265  else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
266  j = j+1;
267  heap[i] = heap[j];
268  locator[heap[i].val] = i;
269  i = j;
270  }
271  else
272  break;
273  }
274  }
275 
276  heap[i].key = newgain;
277  heap[i].val = node;
278  locator[node] = i;
279  }
280 
281  ASSERT(CheckHeap(queue));
282  }
283 
284  return 0;
285 }
286 
287 
288 
289 /*************************************************************************
290 * This function deletes a node from a partition and reinserts it with
291 * an updated gain
292 **************************************************************************/
293 int PQueueUpdate(PQueueType *queue, int node, int oldgain, int newgain)
294 {
295  int i, j;
296  idxtype *locator;
297  ListNodeType *newnode;
298  KeyValueType *heap;
299 
300  if (oldgain == newgain)
301  return 0;
302 
303  if (queue->type == 1) {
304  /* First delete the node and then insert it */
305  PQueueDelete(queue, node, oldgain);
306  return PQueueInsert(queue, node, newgain);
307  }
308  else { /* Heap Priority Queue */
309  heap = queue->heap;
310  locator = queue->locator;
311 
312  ASSERT(locator[node] != -1);
313  ASSERT(heap[locator[node]].val == node);
314  ASSERT(heap[locator[node]].key == oldgain);
315  ASSERT(CheckHeap(queue));
316 
317  i = locator[node];
318 
319  if (oldgain < newgain) { /* Filter-up */
320  while (i > 0) {
321  j = (i-1)>>1;
322  if (heap[j].key < newgain) {
323  heap[i] = heap[j];
324  locator[heap[i].val] = i;
325  i = j;
326  }
327  else
328  break;
329  }
330  }
331  else { /* Filter down */
332  while ((j=2*i+1) < queue->nnodes) {
333  if (heap[j].key > newgain) {
334  if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
335  j = j+1;
336  heap[i] = heap[j];
337  locator[heap[i].val] = i;
338  i = j;
339  }
340  else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
341  j = j+1;
342  heap[i] = heap[j];
343  locator[heap[i].val] = i;
344  i = j;
345  }
346  else
347  break;
348  }
349  }
350 
351  heap[i].key = newgain;
352  heap[i].val = node;
353  locator[node] = i;
354 
355  ASSERT(CheckHeap(queue));
356  }
357 
358  return 0;
359 }
360 
361 
362 
363 /*************************************************************************
364 * This function deletes a node from a partition and reinserts it with
365 * an updated gain
366 **************************************************************************/
367 void PQueueUpdateUp(PQueueType *queue, int node, int oldgain, int newgain)
368 {
369  int i, j;
370  idxtype *locator;
371  ListNodeType *newnode, **buckets;
372  KeyValueType *heap;
373 
374  if (oldgain == newgain)
375  return;
376 
377  if (queue->type == 1) {
378  ASSERT(oldgain >= -queue->ngainspan && oldgain <= queue->pgainspan);
379  ASSERT(newgain >= -queue->ngainspan && newgain <= queue->pgainspan);
380  ASSERT(queue->nnodes > 0);
381 
382  buckets = queue->buckets;
383  newnode = queue->nodes+node;
384 
385  /* First delete the node */
386  if (newnode->prev != NULL)
387  newnode->prev->next = newnode->next;
388  else
389  buckets[oldgain] = newnode->next;
390  if (newnode->next != NULL)
391  newnode->next->prev = newnode->prev;
392 
393  /* Attach this node in the doubly-linked list */
394  newnode->next = buckets[newgain];
395  newnode->prev = NULL;
396  if (newnode->next != NULL)
397  newnode->next->prev = newnode;
398  buckets[newgain] = newnode;
399 
400  if (queue->maxgain < newgain)
401  queue->maxgain = newgain;
402  }
403  else { /* Heap Priority Queue */
404  heap = queue->heap;
405  locator = queue->locator;
406 
407  ASSERT(locator[node] != -1);
408  ASSERT(heap[locator[node]].val == node);
409  ASSERT(heap[locator[node]].key == oldgain);
410  ASSERT(CheckHeap(queue));
411 
412 
413  /* Here we are just filtering up since the newgain is greater than the oldgain */
414  i = locator[node];
415  while (i > 0) {
416  j = (i-1)>>1;
417  if (heap[j].key < newgain) {
418  heap[i] = heap[j];
419  locator[heap[i].val] = i;
420  i = j;
421  }
422  else
423  break;
424  }
425 
426  heap[i].key = newgain;
427  heap[i].val = node;
428  locator[node] = i;
429 
430  ASSERT(CheckHeap(queue));
431  }
432 
433 }
434 
435 
436 /*************************************************************************
437 * This function returns the vertex with the largest gain from a partition
438 * and removes the node from the bucket list
439 **************************************************************************/
441 {
442  int vtx, i, j, gain, node;
443  idxtype *locator;
444  ListNodeType *tptr;
445  KeyValueType *heap;
446 
447  if (queue->nnodes == 0)
448  return -1;
449 
450  queue->nnodes--;
451 
452  if (queue->type == 1) {
453  tptr = queue->buckets[queue->maxgain];
454  queue->buckets[queue->maxgain] = tptr->next;
455  if (tptr->next != NULL) {
456  tptr->next->prev = NULL;
457  }
458  else {
459  if (queue->nnodes == 0) {
460  queue->maxgain = -queue->ngainspan;
461  }
462  else
463  for (; queue->buckets[queue->maxgain]==NULL; queue->maxgain--);
464  }
465 
466  return tptr->id;
467  }
468  else {
469  heap = queue->heap;
470  locator = queue->locator;
471 
472  vtx = heap[0].val;
473  locator[vtx] = -1;
474 
475  if ((i = queue->nnodes) > 0) {
476  gain = heap[i].key;
477  node = heap[i].val;
478  i = 0;
479  while ((j=2*i+1) < queue->nnodes) {
480  if (heap[j].key > gain) {
481  if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
482  j = j+1;
483  heap[i] = heap[j];
484  locator[heap[i].val] = i;
485  i = j;
486  }
487  else if (j+1 < queue->nnodes && heap[j+1].key > gain) {
488  j = j+1;
489  heap[i] = heap[j];
490  locator[heap[i].val] = i;
491  i = j;
492  }
493  else
494  break;
495  }
496 
497  heap[i].key = gain;
498  heap[i].val = node;
499  locator[node] = i;
500  }
501 
502  ASSERT(CheckHeap(queue));
503  return vtx;
504  }
505 }
506 
507 
508 /*************************************************************************
509 * This function returns the vertex with the largest gain from a partition
510 **************************************************************************/
512 {
513  int vtx;
514 
515  if (queue->nnodes == 0)
516  return -1;
517 
518  if (queue->type == 1)
519  vtx = queue->buckets[queue->maxgain]->id;
520  else
521  vtx = queue->heap[0].val;
522 
523  return vtx;
524 }
525 
526 
527 /*************************************************************************
528 * This function returns the vertex with the largest gain from a partition
529 **************************************************************************/
531 {
532  int key;
533 
534  if (queue->nnodes == 0)
535  return -1;
536 
537  if (queue->type == 1)
538  key = queue->maxgain;
539  else
540  key = queue->heap[0].key;
541 
542  return key;
543 }
544 
545 
546 
547 
548 /*************************************************************************
549 * This functions checks the consistency of the heap
550 **************************************************************************/
552 {
553  int i, j, nnodes;
554  idxtype *locator;
555  KeyValueType *heap;
556 
557  heap = queue->heap;
558  locator = queue->locator;
559  nnodes = queue->nnodes;
560 
561  if (nnodes == 0)
562  return 1;
563 
564  ASSERT(locator[heap[0].val] == 0);
565  for (i=1; i<nnodes; i++) {
566  ASSERTP(locator[heap[i].val] == i, ("%d %d %d %d\n", nnodes, i, heap[i].val, locator[heap[i].val]));
567  ASSERTP(heap[i].key <= heap[(i-1)/2].key, ("%d %d %d %d %d\n", i, (i-1)/2, nnodes, heap[i].key, heap[(i-1)/2].key));
568  }
569  for (i=1; i<nnodes; i++)
570  ASSERT(heap[i].key <= heap[0].key);
571 
572  for (j=i=0; i<queue->maxnodes; i++) {
573  if (locator[i] != -1)
574  j++;
575  }
576  ASSERTP(j == nnodes, ("%d %d\n", j, nnodes));
577 
578  return 1;
579 }
#define idxwspacefree
Definition: rename.h:165
#define PQueueUpdate
Definition: rename.h:320
int type
Definition: struct.h:55
int nnodes
Definition: struct.h:56
ListNodeType * nodes
Definition: struct.h:63
#define idxwspacemalloc
Definition: rename.h:164
idxtype key
Definition: struct.h:31
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define CheckHeap
Definition: rename.h:324
#define PQueueReset
Definition: rename.h:316
ListNodeType ** buckets
Definition: struct.h:64
int PQueueGetSize(PQueueType *queue)
Definition: pqueue.c:129
int maxnodes
Definition: struct.h:57
KeyValueType * heap
Definition: struct.h:67
#define idxset
Definition: rename.h:390
struct ListNodeType * prev
Definition: struct.h:43
#define PQueueSeeMax
Definition: rename.h:323
#define WspaceAvail
Definition: rename.h:163
int pgainspan
Definition: struct.h:61
void GKfree(void **ptr1,...)
Definition: util.c:121
#define ASSERTP(expr, msg)
Definition: macros.h:142
int maxgain
Definition: struct.h:62
int id
Definition: struct.h:42
int mustfree
Definition: struct.h:58
#define PQueueUpdateUp
Definition: rename.h:321
#define NEG_GAINSPAN
Definition: defs.h:24
struct ListNodeType ListNodeType
Definition: struct.h:46
int PQueueGetKey(PQueueType *queue)
Definition: pqueue.c:530
#define PLUS_GAINSPAN
Definition: defs.h:23
struct ListNodeType * next
Definition: struct.h:43
#define PQueueGetMax
Definition: rename.h:322
#define idxmalloc
Definition: rename.h:383
#define PQueueInsert
Definition: rename.h:318
idxtype val
Definition: struct.h:32
#define ASSERT(expr)
Definition: macros.h:130
#define PQueueDelete
Definition: rename.h:319
#define PQueueFree
Definition: rename.h:317
#define amin(a, b)
Definition: macros.h:30
idxtype * locator
Definition: struct.h:68
#define PQueueInit
Definition: rename.h:315
int ngainspan
Definition: struct.h:61