1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
/* ========================================================================== */
/* === Source/Mongoose_Refinement.cpp ======================================= */
/* ========================================================================== */
/* -----------------------------------------------------------------------------
* Mongoose Graph Partitioning Library Copyright (C) 2017-2018,
* Scott P. Kolodziej, Nuri S. Yeralan, Timothy A. Davis, William W. Hager
* Mongoose is licensed under Version 3 of the GNU General Public License.
* Mongoose is also available under other licenses; contact authors for details.
* -------------------------------------------------------------------------- */
#include "Mongoose_Refinement.hpp"
#include "Mongoose_BoundaryHeap.hpp"
#include "Mongoose_ImproveFM.hpp"
#include "Mongoose_Internal.hpp"
#include "Mongoose_Logger.hpp"
namespace Mongoose
{
EdgeCutProblem *refine(EdgeCutProblem *graph, const EdgeCut_Options *options)
{
Logger::tic(RefinementTiming);
EdgeCutProblem *P = graph->parent;
Int cn = graph->n;
bool *cPartition = graph->partition;
double *fGains = P->vertexGains;
Int *fExternalDegree = P->externalDegree;
/* Transfer cut costs and partition details upwards. */
P->heuCost = graph->heuCost;
P->cutCost = graph->cutCost;
P->W0 = graph->W0;
P->W1 = graph->W1;
P->imbalance = graph->imbalance;
/* For each vertex in the coarse graph. */
for (Int k = 0; k < cn; k++)
{
/* Load up the inverse matching */
Int v[3] = { -1, -1, -1 };
v[0] = P->invmatchmap[k];
v[1] = P->getMatch(v[0]);
if (v[0] == v[1])
{
v[1] = -1;
}
else
{
v[2] = P->getMatch(v[1]);
if (v[0] == v[2])
{
v[2] = -1;
}
}
/* Transfer the partition choices to the fine level. */
bool cp = cPartition[k];
for (Int i = 0; i < 3 && v[i] != -1; i++)
{
Int vertex = v[i];
P->partition[vertex] = cp;
}
}
/* See if we can relax the boundary constraint and recompute gains for
* vertices on the boundary.
* NOTE: For this, we only need to go through the set of vertices that
* were on the boundary in the coarse representation. */
for (Int h = 0; h < 2; h++)
{
/* Get the appropriate heap's data. */
Int *heap = graph->bhHeap[h];
Int size = graph->bhSize[h];
/* Go through all the boundary vertices. */
for (Int hpos = 0; hpos < size; hpos++)
{
/* Get the coarse vertex from the heap. */
Int k = heap[hpos];
/* Load up the inverse matching */
Int v[3] = { -1, -1, -1 };
v[0] = P->invmatchmap[k];
v[1] = P->getMatch(v[0]);
if (v[0] == v[1])
{
v[1] = -1;
}
else
{
v[2] = P->getMatch(v[1]);
if (v[0] == v[2])
{
v[2] = -1;
}
}
/* Relax the boundary constraint. */
for (Int i = 0; i < 3 && v[i] != -1; i++)
{
Int vertex = v[i];
double gain;
Int externalDegree;
calculateGain(P, options, vertex, &gain, &externalDegree);
/* Only add relevant vertices to the boundary heap. */
if (externalDegree > 0)
{
fExternalDegree[vertex] = externalDegree;
fGains[vertex] = gain;
bhInsert(P, vertex);
}
}
}
}
/* Now that we're done with the coarse graph, we can release it. */
graph->~EdgeCutProblem();
Logger::toc(RefinementTiming);
return P;
}
} // end namespace Mongoose
|
