1 /* ========================================================================== */
2 /* === Source/Mongoose_EdgeCutProblem.cpp =================================== */
3 /* ========================================================================== */
4
5 /* -----------------------------------------------------------------------------
6 * Mongoose Graph Partitioning Library Copyright (C) 2017-2018,
7 * Scott P. Kolodziej, Nuri S. Yeralan, Timothy A. Davis, William W. Hager
8 * Mongoose is licensed under Version 3 of the GNU General Public License.
9 * Mongoose is also available under other licenses; contact authors for details.
10 * -------------------------------------------------------------------------- */
11
12 #include "Mongoose_EdgeCutProblem.hpp"
13
14 #include <algorithm>
15 #include <new>
16
17 namespace Mongoose
18 {
19
20 /* Constructor & Destructor */
EdgeCutProblem()21 EdgeCutProblem::EdgeCutProblem()
22 {
23 n = nz = 0;
24 p = NULL;
25 i = NULL;
26 x = NULL;
27 w = NULL;
28 X = 0.0;
29 W = 0.0;
30 H = 0.0;
31
32 partition = NULL;
33 vertexGains = NULL;
34 externalDegree = NULL;
35 bhIndex = NULL;
36 bhHeap[0] = bhHeap[1] = NULL;
37 bhSize[0] = bhSize[1] = 0;
38
39 heuCost = 0.0;
40 cutCost = 0.0;
41 W0 = 0.0;
42 W1 = 0.0;
43 imbalance = 0.0;
44
45 parent = NULL;
46 clevel = 0;
47 cn = 0;
48 matching = NULL;
49 matchmap = NULL;
50 invmatchmap = NULL;
51 matchtype = NULL;
52
53 markArray = NULL;
54 markValue = 1;
55 }
56
create(const Int _n,const Int _nz,Int * _p,Int * _i,double * _x,double * _w)57 EdgeCutProblem *EdgeCutProblem::create(const Int _n, const Int _nz, Int *_p,
58 Int *_i, double *_x, double *_w)
59 {
60 void *memoryLocation = SuiteSparse_malloc(1, sizeof(EdgeCutProblem));
61 if (!memoryLocation)
62 return NULL;
63
64 // Placement new
65 EdgeCutProblem *graph = new (memoryLocation) EdgeCutProblem();
66
67 graph->shallow_p = (_p != NULL);
68 graph->shallow_i = (_i != NULL);
69 graph->shallow_x = (_x != NULL);
70 graph->shallow_w = (_w != NULL);
71
72 size_t n = static_cast<size_t>(_n);
73 graph->n = _n;
74
75 size_t nz = static_cast<size_t>(_nz);
76 graph->nz = _nz;
77
78 graph->p = (graph->shallow_p)
79 ? _p
80 : (Int *)SuiteSparse_calloc(n + 1, sizeof(Int));
81 graph->i
82 = (graph->shallow_i) ? _i : (Int *)SuiteSparse_malloc(nz, sizeof(Int));
83 graph->x = _x;
84 graph->w = _w;
85 graph->X = 0.0;
86 graph->W = 0.0;
87 graph->H = 0.0;
88 if (!graph->p || !graph->i)
89 {
90 graph->~EdgeCutProblem();
91 return NULL;
92 }
93
94 graph->partition = (bool *)SuiteSparse_malloc(n, sizeof(bool));
95 graph->vertexGains = (double *)SuiteSparse_malloc(n, sizeof(double));
96 graph->externalDegree = (Int *)SuiteSparse_calloc(n, sizeof(Int));
97 graph->bhIndex = (Int *)SuiteSparse_calloc(n, sizeof(Int));
98 graph->bhHeap[0] = (Int *)SuiteSparse_malloc(n, sizeof(Int));
99 graph->bhHeap[1] = (Int *)SuiteSparse_malloc(n, sizeof(Int));
100 graph->bhSize[0] = graph->bhSize[1] = 0;
101 if (!graph->partition || !graph->vertexGains || !graph->externalDegree
102 || !graph->bhIndex || !graph->bhHeap[0] || !graph->bhHeap[1])
103 {
104 graph->~EdgeCutProblem();
105 return NULL;
106 }
107
108 graph->heuCost = 0.0;
109 graph->cutCost = 0.0;
110 graph->W0 = 0.0;
111 graph->W1 = 0.0;
112 graph->imbalance = 0.0;
113
114 graph->parent = NULL;
115 graph->clevel = 0;
116 graph->cn = 0;
117 graph->matching = (Int *)SuiteSparse_calloc(n, sizeof(Int));
118 graph->matchmap = (Int *)SuiteSparse_malloc(n, sizeof(Int));
119 graph->invmatchmap = (Int *)SuiteSparse_malloc(n, sizeof(Int));
120 graph->matchtype = (Int *)SuiteSparse_malloc(n, sizeof(Int));
121 graph->markArray = (Int *)SuiteSparse_calloc(n, sizeof(Int));
122 graph->markValue = 1;
123 graph->singleton = -1;
124 if (!graph->matching || !graph->matchmap || !graph->invmatchmap
125 || !graph->markArray || !graph->matchtype)
126 {
127 graph->~EdgeCutProblem();
128 return NULL;
129 }
130
131 graph->initialized = false;
132
133 return graph;
134 }
135
create(const Graph * _graph)136 EdgeCutProblem *EdgeCutProblem::create(const Graph *_graph)
137 {
138 EdgeCutProblem *graph = create(_graph->n, _graph->nz, _graph->p, _graph->i,
139 _graph->x, _graph->w);
140
141 return graph;
142 }
143
create(EdgeCutProblem * _parent)144 EdgeCutProblem *EdgeCutProblem::create(EdgeCutProblem *_parent)
145 {
146 EdgeCutProblem *graph = create(_parent->cn, _parent->nz);
147
148 if (!graph)
149 return NULL;
150
151 graph->x = (double *)SuiteSparse_malloc(_parent->nz, sizeof(double));
152 graph->w = (double *)SuiteSparse_malloc(_parent->cn, sizeof(double));
153
154 if (!graph->x || !graph->w)
155 {
156 graph->~EdgeCutProblem();
157 return NULL;
158 }
159
160 graph->W = _parent->W;
161 graph->parent = _parent;
162 graph->clevel = graph->parent->clevel + 1;
163
164 return graph;
165 }
166
~EdgeCutProblem()167 EdgeCutProblem::~EdgeCutProblem()
168 {
169 p = (shallow_p) ? NULL : (Int *)SuiteSparse_free(p);
170 i = (shallow_i) ? NULL : (Int *)SuiteSparse_free(i);
171 x = (shallow_x) ? NULL : (double *)SuiteSparse_free(x);
172 w = (shallow_w) ? NULL : (double *)SuiteSparse_free(w);
173
174 partition = (bool *)SuiteSparse_free(partition);
175 vertexGains = (double *)SuiteSparse_free(vertexGains);
176 externalDegree = (Int *)SuiteSparse_free(externalDegree);
177 bhIndex = (Int *)SuiteSparse_free(bhIndex);
178 bhHeap[0] = (Int *)SuiteSparse_free(bhHeap[0]);
179 bhHeap[1] = (Int *)SuiteSparse_free(bhHeap[1]);
180 matching = (Int *)SuiteSparse_free(matching);
181 matchmap = (Int *)SuiteSparse_free(matchmap);
182 invmatchmap = (Int *)SuiteSparse_free(invmatchmap);
183 matchtype = (Int *)SuiteSparse_free(matchtype);
184
185 markArray = (Int *)SuiteSparse_free(markArray);
186
187 SuiteSparse_free(this);
188 }
189
190 /* Initialize a top level graph with a a set of options. */
initialize(const EdgeCut_Options * options)191 void EdgeCutProblem::initialize(const EdgeCut_Options *options)
192 {
193 (void)options; // Unused variable
194
195 if (initialized)
196 {
197 // Graph has been previously initialized. We need to clear some extra
198 // data structures to be able to reuse it.
199
200 X = 0.0;
201 W = 0.0;
202 H = 0.0;
203
204 bhSize[0] = bhSize[1] = 0;
205
206 heuCost = 0.0;
207 cutCost = 0.0;
208 W0 = 0.0;
209 W1 = 0.0;
210 imbalance = 0.0;
211
212 clevel = 0;
213 cn = 0;
214 for (Int k = 0; k < n; k++)
215 {
216 externalDegree[k] = 0;
217 bhIndex[k] = 0;
218 matching[k] = 0;
219 }
220 singleton = -1;
221
222 clearMarkArray();
223 }
224
225 Int *Gp = p;
226 double *Gx = x;
227 double *Gw = w;
228
229 /* Compute worst-case gains, and compute X. */
230 double *gains = vertexGains;
231 double min = fabs((Gx) ? Gx[0] : 1);
232 double max = fabs((Gx) ? Gx[0] : 1);
233 for (Int k = 0; k < n; k++)
234 {
235 W += (Gw) ? Gw[k] : 1;
236 double sumEdgeWeights = 0.0;
237
238 for (Int j = Gp[k]; j < Gp[k + 1]; j++)
239 {
240 double Gxj = (Gx) ? Gx[j] : 1;
241 sumEdgeWeights += Gxj;
242
243 if (fabs(Gxj) < min)
244 {
245 min = fabs(Gxj);
246 }
247 if (fabs(Gxj) > max)
248 {
249 max = fabs(Gxj);
250 }
251 }
252
253 gains[k] = -sumEdgeWeights;
254 X += sumEdgeWeights;
255 }
256 H = 2.0 * X;
257
258 // May need to correct tolerance for very ill-conditioned problems
259 worstCaseRatio = max / (1E-9 + min);
260
261 initialized = true;
262 }
263
clearMarkArray()264 void EdgeCutProblem::clearMarkArray()
265 {
266 markValue += 1;
267 if (markValue < 0)
268 {
269 resetMarkArray();
270 }
271 }
272
clearMarkArray(Int incrementBy)273 void EdgeCutProblem::clearMarkArray(Int incrementBy)
274 {
275 markValue += incrementBy;
276 if (markValue < 0)
277 {
278 resetMarkArray();
279 }
280 }
281
resetMarkArray()282 void EdgeCutProblem::resetMarkArray()
283 {
284 markValue = 1;
285 for (Int k = 0; k < n; k++)
286 {
287 markArray[k] = 0;
288 }
289 }
290
291 } // end namespace Mongoose
292