Debian Codegraph @

packages/seacas/libraries/chaco/internal/force_internal.c

raw
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 }