1 /* ========================================================================== */
2 /* === Source/Mongoose_BoundaryHeap.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_BoundaryHeap.hpp"
13 #include "Mongoose_CutCost.hpp"
14 #include "Mongoose_Debug.hpp"
15 #include "Mongoose_Internal.hpp"
16 #include "Mongoose_Logger.hpp"
17
18 namespace Mongoose
19 {
20
21 //-----------------------------------------------------------------------------
22 // This function inserts the specified vertex into the graph
23 //-----------------------------------------------------------------------------
bhLoad(EdgeCutProblem * graph,const EdgeCut_Options * options)24 void bhLoad(EdgeCutProblem *graph, const EdgeCut_Options *options)
25 {
26 /* Load the boundary heaps. */
27 Int n = graph->n;
28 Int *Gp = graph->p;
29 Int *Gi = graph->i;
30 double *Gx = graph->x;
31 double *Gw = graph->w;
32 bool *partition = graph->partition;
33 double *gains = graph->vertexGains;
34 Int *externalDegree = graph->externalDegree;
35
36 /* Keep track of the cut cost. */
37 CutCost cost;
38 cost.heuCost = 0.0;
39 cost.cutCost = 0.0;
40 cost.W[0] = 0.0;
41 cost.W[1] = 0.0;
42 cost.imbalance = 0.0;
43
44 /* Compute the gains & discover if the vertex is on the boundary. */
45 for (Int k = 0; k < n; k++)
46 {
47 bool kPartition = partition[k];
48 cost.W[kPartition] += (Gw) ? Gw[k] : 1;
49
50 double gain = 0.0;
51 Int exD = 0;
52 for (Int p = Gp[k]; p < Gp[k + 1]; p++)
53 {
54 double edgeWeight = (Gx) ? Gx[p] : 1;
55 bool onSameSide = (kPartition == partition[Gi[p]]);
56 gain += (onSameSide ? -edgeWeight : edgeWeight);
57 if (!onSameSide)
58 {
59 exD++;
60 cost.cutCost += edgeWeight;
61 }
62 }
63 gains[k] = gain;
64 externalDegree[k] = exD;
65 if (exD > 0)
66 bhInsert(graph, k);
67 }
68
69 /* Save the cut cost to the graph. */
70 graph->cutCost = cost.cutCost;
71 graph->W0 = cost.W[0];
72 graph->W1 = cost.W[1];
73
74 double targetSplit = options->target_split;
75 ASSERT(targetSplit > 0);
76 ASSERT(targetSplit <= 0.5);
77
78 graph->imbalance = targetSplit - std::min(graph->W0, graph->W1) / graph->W;
79 graph->heuCost = (graph->cutCost
80 + (fabs(graph->imbalance) > options->soft_split_tolerance
81 ? fabs(graph->imbalance) * graph->H
82 : 0.0));
83 }
84
85 //-----------------------------------------------------------------------------
86 // This function inserts the specified vertex into the graph's boundary heap
87 //-----------------------------------------------------------------------------
bhInsert(EdgeCutProblem * graph,Int vertex)88 void bhInsert(EdgeCutProblem *graph, Int vertex)
89 {
90 /* Unpack structures */
91 Int vp = graph->partition[vertex];
92 Int *bhHeap = graph->bhHeap[vp];
93 Int size = graph->bhSize[vp];
94 double *gains = graph->vertexGains;
95
96 bhHeap[size] = vertex;
97 graph->BH_putIndex(vertex, size);
98
99 heapifyUp(graph, bhHeap, gains, vertex, size, gains[vertex]);
100
101 /* Save the size. */
102 graph->bhSize[vp] = size + 1;
103 }
104
105 //-----------------------------------------------------------------------------
106 // Removes the specified vertex from its heap.
107 // To do this, we swap the last element in the heap with the element we
108 // want to remove. Then we heapify up and heapify down.
109 //-----------------------------------------------------------------------------
bhRemove(EdgeCutProblem * graph,const EdgeCut_Options * options,Int vertex,double gain,bool partition,Int bhPosition)110 void bhRemove(EdgeCutProblem *graph, const EdgeCut_Options *options, Int vertex, double gain,
111 bool partition, Int bhPosition)
112 {
113 (void)options; // Unused variable
114 (void)gain; // Unused variable
115
116 double *gains = graph->vertexGains;
117 Int *bhIndex = graph->bhIndex;
118 Int *bhHeap = graph->bhHeap[partition];
119 Int size = (--graph->bhSize[partition]);
120
121 /* If we removed the last position in the heap, there's nothing to do. */
122 if (bhPosition == size)
123 {
124 bhIndex[vertex] = 0;
125 return;
126 }
127
128 /* Replace the vertex with the last element in the heap. */
129 Int v = bhHeap[bhPosition] = bhHeap[size];
130 graph->BH_putIndex(v, bhPosition);
131
132 /* Finish the delete of "vertex" from the heap. */
133 bhIndex[vertex] = 0;
134
135 /* Bubble up then bubble down with a reread of v because it may have
136 * changed during heapifyUp. */
137 heapifyUp(graph, bhHeap, gains, v, bhPosition, gains[v]);
138 v = bhHeap[bhPosition];
139 heapifyDown(graph, bhHeap, size, gains, v, bhPosition, gains[v]);
140 }
141
142 //-----------------------------------------------------------------------------
143 // Starting at a position, this function will heapify from a vertex upwards
144 //-----------------------------------------------------------------------------
heapifyUp(EdgeCutProblem * graph,Int * bhHeap,double * gains,Int vertex,Int position,double gain)145 void heapifyUp(EdgeCutProblem *graph, Int *bhHeap, double *gains, Int vertex,
146 Int position, double gain)
147 {
148 if (position == 0)
149 return;
150
151 Int posParent = graph->BH_getParent(position);
152 Int pVertex = bhHeap[posParent];
153 double pGain = gains[pVertex];
154
155 /* If we need to swap this vertex with the parent then: */
156 if (pGain < gain)
157 {
158 bhHeap[posParent] = vertex;
159 bhHeap[position] = pVertex;
160 graph->BH_putIndex(vertex, posParent);
161 graph->BH_putIndex(pVertex, position);
162 heapifyUp(graph, bhHeap, gains, vertex, posParent, gain);
163 }
164 }
165
166 //-----------------------------------------------------------------------------
167 // Starting at a position, this function will heapify from a vertex downwards
168 //-----------------------------------------------------------------------------
heapifyDown(EdgeCutProblem * graph,Int * bhHeap,Int size,double * gains,Int vertex,Int position,double gain)169 void heapifyDown(EdgeCutProblem *graph, Int *bhHeap, Int size, double *gains, Int vertex,
170 Int position, double gain)
171 {
172 if (position >= size)
173 return;
174
175 Int lp = graph->BH_getLeftChild(position);
176 Int rp = graph->BH_getRightChild(position);
177
178 Int lv = (lp < size ? bhHeap[lp] : -1);
179 Int rv = (rp < size ? bhHeap[rp] : -1);
180
181 double lg = (lv >= 0 ? gains[lv] : -INFINITY);
182 double rg = (rv >= 0 ? gains[rv] : -INFINITY);
183
184 if (gain < lg || gain < rg)
185 {
186 if (lg > rg)
187 {
188 bhHeap[position] = lv;
189 graph->BH_putIndex(lv, position);
190 bhHeap[lp] = vertex;
191 graph->BH_putIndex(vertex, lp);
192 heapifyDown(graph, bhHeap, size, gains, vertex, lp, gain);
193 }
194 else
195 {
196 bhHeap[position] = rv;
197 graph->BH_putIndex(rv, position);
198 bhHeap[rp] = vertex;
199 graph->BH_putIndex(vertex, rp);
200 heapifyDown(graph, bhHeap, size, gains, vertex, rp, gain);
201 }
202 }
203 }
204
205 } // end namespace Mongoose
206