| 1 |
/* |
| 2 |
* Copyright(C) 1999-2020, 2023 National Technology & Engineering Solutions |
| 3 |
* of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with |
| 4 |
* NTESS, the U.S. Government retains certain rights in this software. |
| 5 |
* |
| 6 |
* See packages/seacas/LICENSE for details |
| 7 |
*/ |
| 8 |
|
| 9 |
#include "defs.h" |
| 10 |
#include "internal.h" |
| 11 |
#include "smalloc.h" |
| 12 |
#include "structs.h" |
| 13 |
#include <stdio.h> |
| 14 |
|
| 15 |
/* Greedily increase the number of internal vtxs in each set. */ |
| 16 |
void force_internal(struct vtx_data **graph, /* graph data structure */ |
| 17 |
int nvtxs, /* number of vertices in graph */ |
| 18 |
int using_ewgts, /* are edge weights being used? */ |
| 19 |
int *assign, /* current assignment */ |
| 20 |
double *goal, /* desired set sizes */ |
| 21 |
int nsets_tot, /* total number of sets */ |
| 22 |
int npasses_max /* number of passes to make */ |
| 23 |
) |
| 24 |
{ |
| 25 |
extern int DEBUG_TRACE; /* trace main execution path? */ |
| 26 |
extern int DEBUG_INTERNAL; /* turn on debugging code here? */ |
| 27 |
struct bidint *prev; /* back pointer for setting up lists */ |
| 28 |
struct bidint *int_list = NULL; /* internal vwgt in each set */ |
| 29 |
struct bidint *vtx_elems = NULL; /* linked lists of vtxs in each set */ |
| 30 |
struct bidint *set_list = NULL; /* headers for vtx_elems lists */ |
| 31 |
double *internal_vwgt = NULL; /* total internal vwgt in each set */ |
| 32 |
int *total_vwgt = NULL; /* total vertex weight in each set */ |
| 33 |
int *indices = NULL; /* orders sets by internal vwgt */ |
| 34 |
int *locked = NULL; /* is vertex allowed to switch sets? */ |
| 35 |
int internal; /* is a vertex internal or not? */ |
| 36 |
int *space = NULL; /* space for mergesort */ |
| 37 |
int npasses; /* number of callse to improve_internal */ |
| 38 |
int nlocked; /* number of vertices that can't move */ |
| 39 |
int set, set2; /* sets two vertices belong to */ |
| 40 |
int any_change; /* did pass improve # internal vtxs? */ |
| 41 |
int niter; /* counts calls to improve_internal */ |
| 42 |
int vwgt_max; /* largest vertex weight in graph */ |
| 43 |
int progress; /* am I improving # internal vertices? */ |
| 44 |
int error; /* out of space? */ |
| 45 |
int size; /* array spacing */ |
| 46 |
int i, j; /* loop counters */ |
| 47 |
|
| 48 |
error = 1; |
| 49 |
|
| 50 |
/* For each set, compute the total weight of internal vertices. */ |
| 51 |
|
| 52 |
if (DEBUG_TRACE > 0) { |
| 53 |
printf("<Entering force_internal>\n"); |
| 54 |
} |
| 55 |
|
| 56 |
indices = smalloc_ret(nsets_tot * sizeof(int)); |
| 57 |
internal_vwgt = smalloc_ret(nsets_tot * sizeof(double)); |
| 58 |
total_vwgt = smalloc_ret(nsets_tot * sizeof(int)); |
| 59 |
if (indices == NULL || internal_vwgt == NULL || total_vwgt == NULL) { |
| 60 |
goto skip; |
| 61 |
} |
| 62 |
|
| 63 |
for (set = 0; set < nsets_tot; set++) { |
| 64 |
total_vwgt[set] = internal_vwgt[set] = 0; |
| 65 |
indices[set] = set; |
| 66 |
} |
| 67 |
|
| 68 |
vwgt_max = 0; |
| 69 |
for (i = 1; i <= nvtxs; i++) { |
| 70 |
internal = TRUE; |
| 71 |
set = assign[i]; |
| 72 |
for (j = 1; j < graph[i]->nedges && internal; j++) { |
| 73 |
set2 = assign[graph[i]->edges[j]]; |
| 74 |
internal = (set2 == set); |
| 75 |
} |
| 76 |
|
| 77 |
total_vwgt[set] += graph[i]->vwgt; |
| 78 |
if (internal) { |
| 79 |
internal_vwgt[set] += graph[i]->vwgt; |
| 80 |
} |
| 81 |
if (graph[i]->vwgt > vwgt_max) { |
| 82 |
vwgt_max = graph[i]->vwgt; |
| 83 |
} |
| 84 |
} |
| 85 |
|
| 86 |
/* Now sort all the internal_vwgt values. */ |
| 87 |
space = smalloc_ret(nsets_tot * sizeof(int)); |
| 88 |
if (space == NULL) { |
| 89 |
goto skip; |
| 90 |
} |
| 91 |
ch_mergesort(internal_vwgt, nsets_tot, indices, space); |
| 92 |
sfree(space); |
| 93 |
space = NULL; |
| 94 |
|
| 95 |
/* Now construct a doubly linked list of sorted, internal_vwgt values. */ |
| 96 |
int_list = smalloc_ret((nsets_tot + 1) * sizeof(struct bidint)); |
| 97 |
if (int_list == NULL) { |
| 98 |
goto skip; |
| 99 |
} |
| 100 |
|
| 101 |
prev = &(int_list[nsets_tot]); |
| 102 |
prev->prev = NULL; |
| 103 |
for (i = 0; i < nsets_tot; i++) { |
| 104 |
set = indices[i]; |
| 105 |
int_list[set].prev = prev; |
| 106 |
int_list[set].val = internal_vwgt[set]; |
| 107 |
prev->next = &(int_list[set]); |
| 108 |
prev = &(int_list[set]); |
| 109 |
} |
| 110 |
prev->next = NULL; |
| 111 |
int_list[nsets_tot].val = -1; |
| 112 |
|
| 113 |
sfree(internal_vwgt); |
| 114 |
sfree(indices); |
| 115 |
internal_vwgt = NULL; |
| 116 |
indices = NULL; |
| 117 |
|
| 118 |
/* Set up convenient data structure for navigating through sets. */ |
| 119 |
set_list = smalloc_ret(nsets_tot * sizeof(struct bidint)); |
| 120 |
vtx_elems = smalloc_ret((nvtxs + 1) * sizeof(struct bidint)); |
| 121 |
if (set_list == NULL || vtx_elems == NULL) { |
| 122 |
goto skip; |
| 123 |
} |
| 124 |
|
| 125 |
for (i = 0; i < nsets_tot; i++) { |
| 126 |
set_list[i].next = NULL; |
| 127 |
} |
| 128 |
|
| 129 |
for (i = 1; i <= nvtxs; i++) { |
| 130 |
set = assign[i]; |
| 131 |
vtx_elems[i].next = set_list[set].next; |
| 132 |
if (vtx_elems[i].next != NULL) { |
| 133 |
vtx_elems[i].next->prev = &(vtx_elems[i]); |
| 134 |
} |
| 135 |
vtx_elems[i].prev = &(set_list[set]); |
| 136 |
set_list[set].next = &(vtx_elems[i]); |
| 137 |
} |
| 138 |
|
| 139 |
locked = smalloc_ret((nvtxs + 1) * sizeof(int)); |
| 140 |
if (locked == NULL) { |
| 141 |
goto skip; |
| 142 |
} |
| 143 |
|
| 144 |
nlocked = 0; |
| 145 |
size = (int)(&(int_list[1]) - &(int_list[0])); |
| 146 |
|
| 147 |
any_change = TRUE; |
| 148 |
npasses = 1; |
| 149 |
while (any_change && npasses <= npasses_max) { |
| 150 |
for (i = 1; i <= nvtxs; i++) { |
| 151 |
locked[i] = FALSE; |
| 152 |
} |
| 153 |
|
| 154 |
/* Now select top guy off the list and improve him. */ |
| 155 |
any_change = FALSE; |
| 156 |
progress = TRUE; |
| 157 |
niter = 1; |
| 158 |
while (progress) { |
| 159 |
prev = int_list[nsets_tot].next; |
| 160 |
set = ((int)(prev - int_list)) / size; |
| 161 |
|
| 162 |
if (DEBUG_INTERNAL > 0) { |
| 163 |
printf("Before iteration %d, nlocked = %d, int[%d] = %d\n", niter, nlocked, set, prev->val); |
| 164 |
} |
| 165 |
if (DEBUG_INTERNAL > 1) { |
| 166 |
check_internal(graph, nvtxs, int_list, set_list, vtx_elems, total_vwgt, assign, nsets_tot); |
| 167 |
} |
| 168 |
|
| 169 |
progress = improve_internal(graph, nvtxs, assign, goal, int_list, set_list, vtx_elems, set, |
| 170 |
locked, &nlocked, using_ewgts, vwgt_max, total_vwgt); |
| 171 |
if (progress) { |
| 172 |
any_change = TRUE; |
| 173 |
} |
| 174 |
niter++; |
| 175 |
} |
| 176 |
npasses++; |
| 177 |
} |
| 178 |
error = 0; |
| 179 |
|
| 180 |
skip: |
| 181 |
|
| 182 |
if (error) { |
| 183 |
strout("\nWARNING: No space to increase internal vertices."); |
| 184 |
strout(" NO INTERNAL VERTEX INCREASE PERFORMED.\n"); |
| 185 |
} |
| 186 |
|
| 187 |
sfree(internal_vwgt); |
| 188 |
sfree(indices); |
| 189 |
sfree(locked); |
| 190 |
sfree(total_vwgt); |
| 191 |
sfree(vtx_elems); |
| 192 |
sfree(int_list); |
| 193 |
sfree(set_list); |
| 194 |
} |