1 /* ========================================================================== */
2 /* === Source/Mongoose_Coarsening.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 /**
13 * Coarsening of a graph given a previously determined matching
14 *
15 * In order to operate on extremely large graphs, a pre-processing is
16 * done to reduce the size of the graph while maintaining its overall structure.
17 * Given a matching of vertices with other vertices (e.g. heavy edge matching,
18 * random, etc.), coarsening constructs the new, coarsened graph.
19 */
20
21 #include "Mongoose_Coarsening.hpp"
22 #include "Mongoose_Debug.hpp"
23 #include "Mongoose_Internal.hpp"
24 #include "Mongoose_Logger.hpp"
25
26 namespace Mongoose
27 {
28
29 /**
30 * @brief Coarsen a Graph given a previously calculated matching
31 *
32 * Given a Graph @p G, coarsen returns a new Graph that is coarsened according
33 * to the matching given by G->matching, G->matchmap, and G->invmatchmap.
34 * G->matching must be built such that matching[a] = b+1 and matching[b] = a+1
35 * if vertices a and b are matched. G->matchmap is a mapping from fine to coarse
36 * vertices, so matchmap[a] = matchmap[b] = c if vertices a and b are matched
37 * and mapped to vertex c in the coarse graph. Likewise, G->invmatchmap is
38 * one possible inverse of G->matchmap, so invmatchmap[c] = a or
39 * invmatchmap[c] = b if a coarsened vertex c represents the matching of
40 * vertices a and b in the refined graph.
41 *
42 * @code
43 * Graph coarsened_graph = coarsen(large_graph, options);
44 * @endcode
45 *
46 * @param graph Graph to be coarsened
47 * @param options Option struct specifying if debug checks should be done
48 * @return A coarsened version of G
49 * @note Allocates memory for the coarsened graph, but frees on error.
50 */
coarsen(EdgeCutProblem * graph,const EdgeCut_Options * options)51 EdgeCutProblem *coarsen(EdgeCutProblem *graph, const EdgeCut_Options *options)
52 {
53 (void)options; // Unused variable
54
55 Logger::tic(CoarseningTiming);
56
57 Int cn = graph->cn;
58 Int *Gp = graph->p;
59 Int *Gi = graph->i;
60 double *Gx = graph->x;
61 double *Gw = graph->w;
62
63 Int *matchmap = graph->matchmap;
64 Int *invmatchmap = graph->invmatchmap;
65
66 /* Build the coarse graph */
67 EdgeCutProblem *coarseGraph = EdgeCutProblem::create(graph);
68 if (!coarseGraph)
69 return NULL;
70
71 Int *Cp = coarseGraph->p;
72 Int *Ci = coarseGraph->i;
73 double *Cx = coarseGraph->x;
74 double *Cw = coarseGraph->w;
75 double *gains = coarseGraph->vertexGains;
76 Int munch = 0;
77 double X = 0.0;
78
79 /* edge and vertex weights always appear in a coarse graph */
80 ASSERT(Cx != NULL);
81 ASSERT(Cw != NULL);
82
83 /* Hashtable stores column pointer values. */
84 Int *htable
85 = (Int *)SuiteSparse_malloc(static_cast<size_t>(cn), sizeof(Int));
86 if (!htable)
87 {
88 coarseGraph->~EdgeCutProblem();
89 return NULL;
90 }
91 for (Int i = 0; i < cn; i++)
92 htable[i] = -1;
93
94 /* For each vertex in the coarse graph. */
95 for (Int k = 0; k < cn; k++)
96 {
97 /* Load up the inverse matching */
98 Int v[3] = { -1, -1, -1 };
99 v[0] = invmatchmap[k];
100 v[1] = graph->getMatch(v[0]);
101 if (v[0] == v[1])
102 {
103 v[1] = -1;
104 }
105 else
106 {
107 v[2] = graph->getMatch(v[1]);
108 if (v[0] == v[2])
109 {
110 v[2] = -1;
111 }
112 }
113
114 Int ps = Cp[k] = munch; /* The munch start for this column */
115
116 double vertexWeight = 0.0;
117 double sumEdgeWeights = 0.0;
118 for (Int i = 0; i < 3 && v[i] != -1; i++)
119 {
120 /* Read the matched vertex and accumulate the vertex weight. */
121 Int vertex = v[i];
122 vertexWeight += (Gw) ? Gw[vertex] : 1;
123
124 for (Int p = Gp[vertex]; p < Gp[vertex + 1]; p++)
125 {
126 Int toCoarsened = matchmap[Gi[p]];
127 if (toCoarsened == k)
128 continue; /* Delete self-edges */
129
130 /* Read the edge weight and accumulate the sum of edge weights.
131 */
132 double edgeWeight = (Gx) ? Gx[p] : 1;
133 sumEdgeWeights += (Gx) ? Gx[p] : 1;
134
135 /* Check the hashtable before scattering. */
136 Int cp = htable[toCoarsened];
137 if (cp < ps) /* Hasn't been seen yet this column */
138 {
139 htable[toCoarsened] = munch;
140 Ci[munch] = toCoarsened;
141 Cx[munch] = edgeWeight;
142 munch++;
143 }
144 /* If the entry already exists & we have edge weights,
145 * sum the edge weights here. */
146 else
147 {
148 Cx[cp] += edgeWeight;
149 }
150 }
151 }
152
153 /* Save the vertex weight. */
154 Cw[k] = vertexWeight;
155
156 /* Save the sum of edge weights and initialize the gain for k. */
157 X += sumEdgeWeights;
158 gains[k] = -sumEdgeWeights;
159 }
160
161 /* Set the last column pointer */
162 Cp[cn] = munch;
163 coarseGraph->nz = munch;
164
165 /* Save the sum of edge weights on the graph. */
166 coarseGraph->X = X;
167 coarseGraph->H = 2.0 * X;
168
169 coarseGraph->worstCaseRatio = graph->worstCaseRatio;
170
171 /* Cleanup resources */
172 SuiteSparse_free(htable);
173
174 #ifndef NDEBUG
175 /* If we want to do expensive checks, make sure we didn't break
176 * the problem into multiple connected components. */
177 double W = 0.0;
178 for (Int k = 0; k < cn; k++)
179 {
180 W += Cw[k];
181 }
182 ASSERT(W == coarseGraph->W);
183 #endif
184
185 Logger::toc(CoarseningTiming);
186
187 /* Return the coarse graph */
188 return coarseGraph;
189 }
190
191 } // end namespace Mongoose
192