Zoltan2
Zoltan2_GraphMetricsUtility.hpp
Go to the documentation of this file.
1 // @HEADER
2 //
3 // ***********************************************************************
4 //
5 // Zoltan2: A package of combinatorial algorithms for scientific computing
6 // Copyright 2012 Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Karen Devine (kddevin@sandia.gov)
39 // Erik Boman (egboman@sandia.gov)
40 // Siva Rajamanickam (srajama@sandia.gov)
41 //
42 // ***********************************************************************
43 //
44 // @HEADER
45 
49 #ifndef ZOLTAN2_GRAPHICMETRICVALUESUTILITY_HPP
50 #define ZOLTAN2_GRAPHICMETRICVALUESUTILITY_HPP
51 
54 
55 namespace Zoltan2{
56 
86 template <typename Adapter>
88  const RCP<const Environment> &env,
89  const RCP<const Comm<int> > &comm,
90  const RCP<const GraphModel<typename Adapter::base_adapter_t> > &graph,
91  const ArrayView<const typename Adapter::part_t> &part,
92  typename Adapter::part_t &numParts,
93  ArrayRCP<RCP<BaseClassMetrics<typename Adapter::scalar_t> > > &metrics,
94  ArrayRCP<typename Adapter::scalar_t> &globalSums)
95 {
96  env->debug(DETAILED_STATUS, "Entering globalWeightedCutsByPart");
98  // Initialize return values
99 
100  numParts = 0;
101 
102  int ewgtDim = graph->getNumWeightsPerEdge();
103 
104  int numMetrics = 1; // "edge cuts"
105  if (ewgtDim) numMetrics += ewgtDim; // "weight n"
106 
107  typedef typename Adapter::scalar_t scalar_t;
108  typedef typename Adapter::gno_t gno_t;
109  typedef typename Adapter::lno_t lno_t;
110  typedef typename Adapter::node_t node_t;
111  typedef typename Adapter::part_t part_t;
112  typedef StridedData<lno_t, scalar_t> input_t;
113 
114  typedef GraphMetrics<scalar_t> mv_t;
115  typedef Tpetra::CrsMatrix<part_t,lno_t,gno_t,node_t> sparse_matrix_type;
116  typedef Tpetra::Vector<part_t,lno_t,gno_t,node_t> vector_t;
117  typedef Tpetra::Map<lno_t, gno_t, node_t> map_type;
118  typedef Tpetra::global_size_t GST;
119  const GST INVALID = Teuchos::OrdinalTraits<GST>::invalid ();
120 
121  using Teuchos::as;
122 
123  // add some more metrics to the array
124  typedef typename ArrayRCP<RCP<BaseClassMetrics<typename Adapter::scalar_t> > >::size_type array_size_type;
125  metrics.resize( metrics.size() + numMetrics );
126  for( array_size_type n = metrics.size() - numMetrics; n < metrics.size(); ++n ) {
127  mv_t * newMetric = new mv_t; // allocate the new memory
128  env->localMemoryAssertion(__FILE__,__LINE__,1,newMetric); // check errors
129  metrics[n] = rcp( newMetric); // create the new members
130  }
131  array_size_type next = metrics.size() - numMetrics; // MDM - this is most likely temporary to preserve the format here - we are now filling a larger array so we may not have started at 0
132 
133 
135  // Figure out the global number of parts in use.
136  // Verify number of vertex weights is the same everywhere.
137 
138  lno_t localNumObj = part.size();
139  part_t localNum[2], globalNum[2];
140  localNum[0] = static_cast<part_t>(ewgtDim);
141  localNum[1] = 0;
142 
143  for (lno_t i=0; i < localNumObj; i++)
144  if (part[i] > localNum[1]) localNum[1] = part[i];
145 
146  try{
147  reduceAll<int, part_t>(*comm, Teuchos::REDUCE_MAX, 2,
148  localNum, globalNum);
149  }
151 
152  env->globalBugAssertion(__FILE__,__LINE__,
153  "inconsistent number of edge weights",
154  globalNum[0] == localNum[0], DEBUG_MODE_ASSERTION, comm);
155 
156  part_t nparts = globalNum[1] + 1;
157 
158  part_t globalSumSize = nparts * numMetrics;
159  scalar_t * sumBuf = new scalar_t [globalSumSize];
160  env->localMemoryAssertion(__FILE__, __LINE__, globalSumSize, sumBuf);
161  globalSums = arcp(sumBuf, 0, globalSumSize);
162 
164  // Calculate the local totals by part.
165 
166  scalar_t *localBuf = new scalar_t [globalSumSize];
167  env->localMemoryAssertion(__FILE__,__LINE__,globalSumSize,localBuf);
168  memset(localBuf, 0, sizeof(scalar_t) * globalSumSize);
169 
170  scalar_t *cut = localBuf; // # of cuts
171 
172  ArrayView<const gno_t> Ids;
173  ArrayView<input_t> vwgts;
174  //size_t nv =
175  graph->getVertexList(Ids, vwgts);
176 
177  ArrayView<const gno_t> edgeIds;
178  ArrayView<const lno_t> offsets;
179  ArrayView<input_t> wgts;
180  //size_t numLocalEdges =
181  graph->getEdgeList(edgeIds, offsets, wgts);
182  // **************************************************************************
183  // *************************** BUILD MAP FOR ADJS ***************************
184  // **************************************************************************
185 
186  RCP<const map_type> vertexMapG;
187 
188  // Build a list of the global vertex ids...
189  gno_t min = std::numeric_limits<gno_t>::max();
190  size_t maxcols = 0;
191  for (lno_t i = 0; i < localNumObj; ++i) {
192  if (Ids[i] < min) min = Ids[i];
193  size_t ncols = offsets[i+1] - offsets[i];
194  if (ncols > maxcols) maxcols = ncols;
195  }
196 
197  gno_t gmin;
198  Teuchos::reduceAll<int, gno_t>(*comm,Teuchos::REDUCE_MIN,1,&min,&gmin);
199 
200  //Generate Map for vertex
201  vertexMapG = rcp(new map_type(INVALID, Ids, gmin, comm));
202 
203  // **************************************************************************
204  // ************************** BUILD GRAPH FOR ADJS **************************
205  // **************************************************************************
206 
207  RCP<sparse_matrix_type> adjsMatrix;
208 
209  // Construct Tpetra::CrsGraph objects.
210  adjsMatrix = rcp (new sparse_matrix_type (vertexMapG, 0));
211 
212  Array<part_t> justOneA(maxcols, 1);
213 
214  for (lno_t localElement=0; localElement<localNumObj; ++localElement){
215  // Insert all columns for global row Ids[localElement]
216  size_t ncols = offsets[localElement+1] - offsets[localElement];
217  adjsMatrix->insertGlobalValues(Ids[localElement],
218  edgeIds(offsets[localElement], ncols),
219  justOneA(0, ncols));
220  }
221 
222  //Fill-complete adjs Graph
223  adjsMatrix->fillComplete ();
224 
225  // Compute part
226  RCP<vector_t> scaleVec = Teuchos::rcp( new vector_t(vertexMapG,false) );
227  for (lno_t localElement=0; localElement<localNumObj; ++localElement) {
228  scaleVec->replaceLocalValue(localElement,part[localElement]);
229  }
230 
231  // Postmultiply adjsMatrix by part
232  adjsMatrix->rightScale(*scaleVec);
233  Array<gno_t> Indices;
234  Array<part_t> Values;
235 
236  for (lno_t i=0; i < localNumObj; i++) {
237  const gno_t globalRow = Ids[i];
238  size_t NumEntries = adjsMatrix->getNumEntriesInGlobalRow (globalRow);
239  Indices.resize (NumEntries);
240  Values.resize (NumEntries);
241  adjsMatrix->getGlobalRowCopy (globalRow,Indices(),Values(),NumEntries);
242 
243  for (size_t j=0; j < NumEntries; j++)
244  if (part[i] != Values[j])
245  cut[part[i]]++;
246  }
247 
248  if (numMetrics > 1) {
249 
250  scalar_t *wgt = localBuf + nparts; // weight 0
251 
252  // This code assumes the solution has the part ordered the
253  // same way as the user input. (Bug 5891 is resolved.)
254  for (int edim = 0; edim < ewgtDim; edim++){
255  for (lno_t i=0; i < localNumObj; i++) {
256  const gno_t globalRow = Ids[i];
257  size_t NumEntries = adjsMatrix->getNumEntriesInGlobalRow (globalRow);
258  Indices.resize (NumEntries);
259  Values.resize (NumEntries);
260  adjsMatrix->getGlobalRowCopy (globalRow,Indices(),Values(),NumEntries);
261 
262  for (size_t j=0; j < NumEntries; j++)
263  if (part[i] != Values[j])
264  wgt[part[i]] += wgts[edim][offsets[i] + j];
265  }
266  wgt += nparts; // individual weights
267  }
268  }
269 
271  // Obtain global totals by part.
272 
273  try{
274  reduceAll<int, scalar_t>(*comm, Teuchos::REDUCE_SUM, globalSumSize,
275  localBuf, sumBuf);
276  }
278 
279  delete [] localBuf;
280 
282  // Global max and sum over all parts
283 
284  cut = sumBuf; // # of cuts
285  scalar_t max=0, sum=0;
286 
287  ArrayView<scalar_t> cutVec(cut, nparts);
288  getStridedStats<scalar_t>(cutVec, 1, 0, max, sum);
289 
290  metrics[next]->setName("edge cuts");
291  metrics[next]->setMetricValue("global maximum", max);
292  metrics[next]->setMetricValue("global sum", sum);
293 
294  next++;
295 
296  if (numMetrics > 1){
297  scalar_t *wgt = sumBuf + nparts; // weight 0
298 
299  for (int edim=0; edim < ewgtDim; edim++){
300  ArrayView<scalar_t> fromVec(wgt, nparts);
301  getStridedStats<scalar_t>(fromVec, 1, 0, max, sum);
302 
303  std::ostringstream oss;
304  oss << "weight " << edim;
305 
306  metrics[next]->setName(oss.str());
307  metrics[next]->setMetricValue("global maximum", max);
308  metrics[next]->setMetricValue("global sum", sum);
309 
310  next++;
311  wgt += nparts; // individual weights
312  }
313  }
314 
315  numParts = nparts;
316 
317  env->debug(DETAILED_STATUS, "Exiting globalWeightedCutsByPart");
318 }
319 
322 template <typename scalar_t, typename part_t>
323 void printGraphMetricsHeader(std::ostream &os, part_t targetNumParts, part_t numParts )
324 {
325  os << "Graph Metrics: (" << numParts << " parts)";
326  os << std::endl;
327  if (targetNumParts != numParts) {
328  os << "Target number of parts is: " << targetNumParts << std::endl;
329  }
331 }
332 
335 template <typename scalar_t, typename part_t>
336 void printGraphMetrics(std::ostream &os, part_t targetNumParts, part_t numParts, const ArrayView<RCP<BaseClassMetrics<scalar_t>>> &infoList)
337 {
338  printGraphMetricsHeader<scalar_t, part_t>(os, targetNumParts, numParts);
339  for (int i=0; i < infoList.size(); i++) {
340  if (infoList[i]->getName() != METRICS_UNSET_STRING) {
341  infoList[i]->printLine(os);
342  }
343  }
344  os << std::endl;
345 }
346 
349 template <typename scalar_t, typename part_t>
350 void printGraphMetrics(std::ostream &os, part_t targetNumParts, part_t numParts, RCP<BaseClassMetrics<scalar_t>> metricValue)
351 {
352  printGraphMetricsHeader<scalar_t, part_t>(os, targetNumParts, numParts);
353  metricValue->printLine(os);
354 }
355 
356 } //namespace Zoltan2
357 
358 #endif
#define INVALID(STR)
checks for logic errors
void printGraphMetrics(std::ostream &os, part_t targetNumParts, part_t numParts, const ArrayView< RCP< BaseClassMetrics< scalar_t >>> &infoList)
Print out list of graph metrics.
void globalWeightedCutsByPart(const RCP< const Environment > &env, const RCP< const Comm< int > > &comm, const RCP< const GraphModel< typename Adapter::base_adapter_t > > &graph, const ArrayView< const typename Adapter::part_t > &part, typename Adapter::part_t &numParts, ArrayRCP< RCP< BaseClassMetrics< typename Adapter::scalar_t > > > &metrics, ArrayRCP< typename Adapter::scalar_t > &globalSums)
Given the local partitioning, compute the global weighted cuts in each part.
size_t global_size_t
static void printHeader(std::ostream &os)
Print a standard header.
void printGraphMetricsHeader(std::ostream &os, part_t targetNumParts, part_t numParts)
Print out header info for graph metrics.
sub-steps, each method&#39;s entry and exit
The StridedData class manages lists of weights or coordinates.
GraphModel defines the interface required for graph models.
#define Z2_THROW_OUTSIDE_ERROR(env)
Throw an error returned from outside the Zoltan2 library.
#define METRICS_UNSET_STRING