Debian Codegraph @

packages/isorropia/test/mtx/test_create_balanced_copy.cpp

raw
1 //@HEADER
2 //************************************************************************
3 //
4 // Isorropia: Partitioning and Load Balancing Package
5 // Copyright (2006) Sandia Corporation
6 //
7 //Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 //license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 //************************************************************************
38 //@HEADER
39 //
40 // Read in a matrix market file. Use isorropia to do graph
41 // or hypergraph partitioning. Compute the graph or hypergraph
42 // balance and cut metrics both before and after partitioning.
43 //
44 // This tests all variants of Isorropia::Epetra::createBalancedCopy().
45 //
46 // For graph partitioning:
47 //
48 // The nonzeros of this matrix represent graph edges. The row
49 // or column IDs represent the graph vertices. Only square
50 // matrices will be processed with graph partitioning.
51 //
52 // Isorropia will ignore the self-edges (the nonzero diagonal entries).
53 //
54 // For hypergraph partitioning:
55 //
56 // By convention, the columns of this matrix are hyperedges, and we
57 // wish to balance the vertices, represented by the rows.
58 //
59 // If run with --v option, prints out partitioning before and after.
60 //
61 // This is what simple.mtx looks like. 25 rows, 25 cols, 105 non-zeroes.
62 //
63 // 0123456789012345678901234
64 // 0xx x 0
65 // 1xxx x 1
66 // 2 xxx x 2
67 // 3 xxx x 3
68 // 4 xx x 4
69 // 5x xx x 5
70 // 6 x xxx x 6
71 // 7 x xxx x 7
72 // 8 x xxx x 8
73 // 9 x xx x 9
74 // 0 x xx x 0
75 // 1 x xxx x 1
76 // 2 x xxx x 2
77 // 3 x xxx x 3
78 // 4 x xx x 4
79 // 5 x xx x 5
80 // 6 x xxx x 6
81 // 7 x xxx x 7
82 // 8 x xxx x 8
83 // 9 x xx x9
84 // 0 x xx 0
85 // 1 x xxx 1
86 // 2 x xxx 2
87 // 3 x xxx3
88 // 4 x xx4
89 // 0123456789012345678901234
90 //
91 // If run with --f={filename} a matrix market file other than simple.mtx
92 // will be processed.
93 //
94
95 #include <Isorropia_ConfigDefs.hpp>
96 #include <Isorropia_Epetra.hpp>
97 #include <Isorropia_EpetraPartitioner.hpp>
98 #include <Isorropia_EpetraRedistributor.hpp>
99 #include <Isorropia_EpetraCostDescriber.hpp>
100
101 #include <ispatest_lbeval_utils.hpp>
102 #include <ispatest_epetra_utils.hpp>
103
104 static int tmp=0;
105 #define CHECK_FAILED() { \
106 Comm.SumAll(&fail, &tmp, 1); \
107 if (tmp){ \
108 failures++; \
109 if (!runAll) goto Report; \
110 } \
111 fail = 0; \
112 }
113
114 #ifdef HAVE_EPETRA
115 #ifdef HAVE_MPI
116 #include <Epetra_MpiComm.h>
117 #else
118 #include <Epetra_SerialComm.h>
119 #endif
120 #include <Epetra_Map.h>
121 #include <Epetra_CrsMatrix.h>
122 #include <Epetra_Vector.h>
123 #include <Epetra_Import.h>
124 #ifdef HAVE_EPETRAEXT
125 #include <EpetraExt_CrsMatrixIn.h>
126 #endif
127
128 #endif
129
130 #include <Teuchos_CommandLineProcessor.hpp>
131
132 #include <unistd.h>
133
134 //#define SHORT_TEST
135
136 #define GRAPH_PARTITIONING 1
137 #define HYPERGRAPH_PARTITIONING 2
138
139 #define SUPPLY_EQUAL_WEIGHTS 1
140 #define SUPPLY_UNEQUAL_WEIGHTS 2
141 #define NO_APPLICATION_SUPPLIED_WEIGHTS 3
142
143 #define EPETRA_CRSGRAPH 1
144 #define EPETRA_CRSMATRIX 2
145 #define EPETRA_ROWMATRIX 3
146 #define EPETRA_LINEARPROBLEM 4
147
148 #define ERROREXIT(v, s) \
149 if (v){ \
150 test_type(numPartitions, partitioningType, vertexWeightType, edgeWeightType, objectType); \
151 std::cout << s << std::endl << "FAIL" << std::endl; \
152 } \
153 exit(1);
154
155 #define ERRORRETURN(v, s) \
156 if (v){ \
157 test_type(numPartitions, partitioningType, vertexWeightType, edgeWeightType, objectType); \
158 std::cout << s << std::endl << "FAIL" << std::endl; \
159 } \
160 return 1;
161
162
163 void test_type(int numPartitions, int partitioningType, int vertexWeightType,
164 int edgeWeightType, int objectType)
165 {
166 std::cout << "TEST: ";
167 if (partitioningType == GRAPH_PARTITIONING)
168 std::cout << "graph partitioning, ";
169 else
170 std::cout << "hypergraph partitioning, ";
171
172 if (vertexWeightType == SUPPLY_EQUAL_WEIGHTS)
173 std::cout << "created equal vertex (row) weights, ";
174 else if (vertexWeightType == SUPPLY_UNEQUAL_WEIGHTS)
175 std::cout << "created unequal vertex (row) weights, ";
176 else
177 std::cout << "did not supply vertex (row) weights, ";
178
179 std::cout << std::endl << " ";
180
181 if (partitioningType == GRAPH_PARTITIONING){
182 if (edgeWeightType == SUPPLY_EQUAL_WEIGHTS)
183 std::cout << "created equal edge weights, ";
184 else if (edgeWeightType == SUPPLY_UNEQUAL_WEIGHTS)
185 std::cout << "created unequal edge weights, ";
186 else
187 std::cout << "did not supply edge weights, ";
188 }
189 else{
190 if (edgeWeightType == SUPPLY_EQUAL_WEIGHTS)
191 std::cout << "created equal hyperedge (column) weights, ";
192 else if (edgeWeightType == SUPPLY_UNEQUAL_WEIGHTS)
193 std::cout << "created unequal hyperedge (column) weights,";
194 else
195 std::cout << "did not supply hyperedge (column) weights, ";
196 }
197
198 if (objectType == EPETRA_CRSGRAPH)
199 std::cout << "using Epetra_CrsGraph interface";
200 else if (objectType == EPETRA_CRSMATRIX)
201 std::cout << "using Epetra_CrsMatrix interface";
202 else if (objectType == EPETRA_LINEARPROBLEM)
203 std::cout << "using Epetra_LinearProblem interface";
204 else if (objectType == EPETRA_ROWMATRIX)
205 std::cout << "using Epetra_RowMatrix interface";
206
207 if (numPartitions > 0){
208 std::cout << std::endl << " ";
209 std::cout << "NUM_GLOBAL_PARTS is " << numPartitions;
210 }
211 std::cout << std::endl;
212
213 }
214
215 // 8/31/09 modified this test so there are no user supplied weights, because
216 // createBalancedCopy no longer takes weights
217
218 static int run_test(Teuchos::RCP<Epetra_CrsMatrix> matrix,
219 bool verbose, // display the graph before & after
220 bool contract, // set global number of partitions to 1/2 num procs
221 int partitioningType, // hypergraph or graph partitioning, or simple
222 int vertexWeightType, // use vertex weights?
223 int edgeWeightType, // use edge/hyperedge weights?
224 int objectType) // use isorropia's CrsMatrix or CrsGraph
225 {
226 int rc=0, fail = 0;
227 #ifdef HAVE_EPETRAEXT
228 int localProc = 0;
229 double balance1, balance2, cutn1, cutn2, cutl1, cutl2;
230 double balance3, cutn3, cutl3;
231 double cutWgt1, cutWgt2, cutWgt3;
232 int numCuts1, numCuts2, numCuts3, valid;
233 int numPartitions = 0;
234 int keepDenseEdges = 0;
235 int numProcs = 1;
236
237 #ifdef HAVE_MPI
238 const Epetra_MpiComm &Comm = dynamic_cast<const Epetra_MpiComm &>(matrix->Comm());
239 localProc = Comm.MyPID();
240 numProcs = Comm.NumProc();
241 #else
242 const Epetra_SerialComm &Comm = dynamic_cast<const Epetra_SerialComm &>(matrix->Comm());
243 #endif
244
245 int numRows = matrix->NumGlobalRows();
246
247 if (numRows < (numProcs * 100)){
248 // By default Zoltan throws out dense edges, defined as those
249 // whose number of non-zeros exceeds 25% of the number of vertices.
250 //
251 // If dense edges are thrown out of a small matrix, there may be nothing left.
252 keepDenseEdges = 1;
253 }
254
255 double myShareBefore = 1.0 / numProcs;
256 double myShare = myShareBefore;
257
258 if (contract){
259 numPartitions = numProcs / 2;
260
261 if (numPartitions > numRows)
262 numPartitions = numRows;
263
264 if (numPartitions > 0){
265 if (localProc < numPartitions){
266 myShare = 1.0 / numPartitions;
267 }
268 else{
269 myShare = 0.0;
270 }
271 }
272 else{
273 contract = 0;
274 }
275 }
276
277 // If we want Zoltan's or Isorropia's default weights, then we don't
278 // need to supply a CostDescriber object to createBalancedCopy,
279 // so we get to test the API functions that don't take a CostDescriber.
280
281 bool noCosts = ((vertexWeightType == NO_APPLICATION_SUPPLIED_WEIGHTS) &&
282 (edgeWeightType == NO_APPLICATION_SUPPLIED_WEIGHTS));
283
284 // Test the interface that has no parameters, if possible
285
286 bool noParams =
287 ((partitioningType == HYPERGRAPH_PARTITIONING) && // default, so requires no params
288 (numPartitions == 0) && // >0 would require a parameter
289 (keepDenseEdges == 0)); // >0 would require a parameter
290
291 // Maps for original object
292 const Epetra_Map &sourceRowMap = matrix->RowMap();
293 const Epetra_Map &sourceRangeMap = matrix->RangeMap();
294 // const Epetra_Map &sourceColMap = matrix->ColMap();
295 const Epetra_Map &sourceDomainMap = matrix->DomainMap();
296
297 int numCols = matrix->NumGlobalCols();
298 int nMyRows = sourceRowMap.NumMyElements();
299 int base = sourceRowMap.IndexBase();
300
301 // Compute vertex and edge weights
302
303 Isorropia::Epetra::CostDescriber costs;
304
305 Teuchos::RCP<Epetra_Vector> vptr;
306
307 Teuchos::RCP<Epetra_CrsMatrix> eptr;
308
309 Teuchos::RCP<Epetra_Vector> hyperEdgeWeights;
310
311 if (edgeWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS){
312
313 if (partitioningType == GRAPH_PARTITIONING){
314
315 // Create graph edge weights.
316
317 eptr = Teuchos::rcp(new Epetra_CrsMatrix(*matrix));
318
319 if (vertexWeightType == SUPPLY_EQUAL_WEIGHTS){
320 eptr->PutScalar(1.0); // set all nonzeros to 1.0
321 }
322 else{
323 int maxRowSize = eptr->MaxNumEntries();
324 double *newVal = NULL;
325 if (maxRowSize > 0){
326 newVal = new double [maxRowSize];
327 for (int j=0; j<maxRowSize; j++){
328 newVal[j] = localProc + 1 + j;
329 }
330 }
331 int numEntries;
332 int *idx;
333 double *val;
334 for (int i=0; i<nMyRows; i++){
335 rc = eptr->ExtractMyRowView(i, numEntries, val, idx);
336 for (int j=0; j<numEntries; j++){
337 val[j] = newVal[j];
338 }
339 }
340 if (newVal) delete [] newVal;
341 }
342
343 eptr->FillComplete(sourceDomainMap, sourceRangeMap);
344
345 costs.setGraphEdgeWeights(eptr);
346 }
347 else{
348 // Create hyperedge weights. (Note that the list of hyperedges that a
349 // process provides weights for has no relation to the columns
350 // that it has non-zeroes for, or the rows that is has. Hypergraphs
351 // in general are not square. Also more than one process can provide
352 // a weight for the same edge. Zoltan combines the weights according
353 // to the value of the PHG_EDGE_WEIGHT_OPERATION parameter. The default
354 // for this parameter is to use the maximum edge weight provided by any
355 // process for a given hyperedge.)
356
357 Epetra_Map hyperEdgeMap(numCols, base, Comm);
358
359 hyperEdgeWeights = Teuchos::rcp(new Epetra_Vector(hyperEdgeMap));
360
361 int *edgeGIDs = NULL;
362 double *weights = NULL;
363 int numHEweights = hyperEdgeMap.NumMyElements();
364
365 if (numHEweights){
366 edgeGIDs = new int [numHEweights];
367 weights = new double [numHEweights];
368
369 if (edgeWeightType == SUPPLY_EQUAL_WEIGHTS){
370 for (int i=0; i<numHEweights; i++){
371 edgeGIDs[i] = hyperEdgeMap.GID(i);
372 weights[i] = 1.0;
373 }
374 }
375 else{
376 int hiVolumeStart = matrix->NumGlobalCols() / 3;
377 int hiVolumeEnd = hiVolumeStart * 2;
378 for (int i=0; i<numHEweights; i++){
379 edgeGIDs[i] = hyperEdgeMap.GID(i);
380 if ((edgeGIDs[i] < hiVolumeStart) || (edgeGIDs[i] >= hiVolumeEnd)){
381 weights[i] = 1.0;
382 }
383 else{
384 weights[i] = 3.0;
385 }
386 }
387 }
388 hyperEdgeWeights->ReplaceGlobalValues(numHEweights, weights, edgeGIDs);
389 }
390
391 if (weights){
392 delete [] weights;
393 delete [] edgeGIDs;
394 }
395
396 costs.setHypergraphEdgeWeights(hyperEdgeWeights);
397 }
398 }
399
400 bool need_importer = false;
401
402 if ((vertexWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS)){
403
404 need_importer = true; // to redistribute row weights
405
406 double *val = NULL;
407
408 if (nMyRows){
409 val = new double [nMyRows];
410
411 if (vertexWeightType == SUPPLY_EQUAL_WEIGHTS){
412 for (int i=0; i<nMyRows; i++){
413 val[i] = 1.0;
414 }
415 }
416 else if (vertexWeightType == SUPPLY_UNEQUAL_WEIGHTS){
417 for (int i=0; i<nMyRows; i++){
418 val[i] = 1.0 + ((localProc+1) / 2);
419 }
420 }
421 }
422
423 vptr = Teuchos::rcp(new Epetra_Vector(Copy, sourceRowMap, val));
424
425 if (val) delete [] val;
426
427 costs.setVertexWeights(vptr);
428 }
429
430 // Calculate partition quality metrics before calling Zoltan
431
432 if (partitioningType == GRAPH_PARTITIONING){
433 rc = ispatest::compute_graph_metrics(matrix->Graph(), costs,
434 myShare, balance1, numCuts1, cutWgt1, cutn1, cutl1);
435 if (contract){
436 // balance wrt target of balancing weight over *all* procs
437 rc = ispatest::compute_graph_metrics(matrix->Graph(), costs,
438 myShareBefore, balance3, numCuts3, cutWgt3, cutn3, cutl3);
439 }
440 }
441 else{
442 rc = ispatest::compute_hypergraph_metrics(matrix->Graph(), costs,
443 myShare, balance1, cutn1, cutl1);
444 if (contract){
445 // balance wrt target of balancing weight over *all* procs
446 rc = ispatest::compute_hypergraph_metrics(matrix->Graph(), costs,
447 myShareBefore, balance3, cutn3, cutl3);
448 }
449 }
450
451 if (rc){
452 ERROREXIT((localProc==0), "Error in computing partitioning metrics")
453 }
454
455 Teuchos::ParameterList params;
456
457 #ifdef HAVE_ISORROPIA_ZOLTAN
458
459 if (!noParams){
460
461 // We're using Zoltan for partitioning and supplying
462 // parameters, overriding defaults.
463
464 Teuchos::ParameterList &sublist = params.sublist("Zoltan");
465
466 if (partitioningType == GRAPH_PARTITIONING){
467 params.set("PARTITIONING METHOD", "GRAPH");
468 sublist.set("GRAPH_PACKAGE", "PHG");
469 }
470 else{
471 params.set("PARTITIONING METHOD", "HYPERGRAPH");
472 sublist.set("LB_APPROACH", "PARTITION");
473 sublist.set("PHG_CUT_OBJECTIVE", "CONNECTIVITY"); // "cutl"
474 }
475
476 if (keepDenseEdges){
477 // only throw out rows that have no zeroes, default is to
478 // throw out if .25 or more of the columns are non-zero
479 sublist.set("PHG_EDGE_SIZE_THRESHOLD", "1.0");
480 }
481 if (numPartitions > 0){
482 // test #Partitions < #Processes
483 std::ostringstream os;
484 os << numPartitions;
485 std::string s = os.str();
486 // sublist.set("NUM_GLOBAL_PARTS", s);
487 params.set("NUM PARTS", s);
488 }
489
490 //sublist.set("DEBUG_LEVEL", "1"); // Zoltan will print out parameters
491 //sublist.set("DEBUG_LEVEL", "5"); // proc 0 will trace Zoltan calls
492 //sublist.set("DEBUG_MEMORY", "2"); // Zoltan will trace alloc & free
493 }
494
495 #else
496 ERROREXIT((localProc==0),
497 "Zoltan partitioning required but Zoltan not available.")
498 #endif
499
500 // Function scope values
501
502 Teuchos::RCP<Epetra_Vector> newvwgts;
503 Teuchos::RCP<Epetra_CrsMatrix> newewgts;
504
505 // Function scope values required for LinearProblem
506
507 Epetra_LinearProblem *problem = NULL;
508 Epetra_Map *LHSmap = NULL;
509 Epetra_MultiVector *RHS = NULL;
510 Epetra_MultiVector *LHS = NULL;
511
512 // Reference counted pointer to balanced object
513
514 Epetra_CrsMatrix *matrixPtr=NULL;
515 Epetra_CrsGraph *graphPtr=NULL;
516 Epetra_RowMatrix *rowMatrixPtr=NULL;
517 Epetra_LinearProblem *problemPtr=NULL;
518
519 // Row map for balanced object
520 const Epetra_BlockMap *targetBlockRowMap=NULL; // for input CrsGraph
521 const Epetra_Map *targetRowMap=NULL; // for all other inputs
522
523 // Column map for balanced object
524 const Epetra_BlockMap *targetBlockColMap=NULL; // for input CrsGraph
525 const Epetra_Map *targetColMap=NULL; // for all other inputs
526
527 if (objectType == EPETRA_CRSMATRIX){
528 if (noParams && noCosts){
529 matrixPtr = Isorropia::Epetra::createBalancedCopy(*matrix);
530 }
531 else if (noCosts){
532 matrixPtr = Isorropia::Epetra::createBalancedCopy(*matrix, params);
533 }
534 targetRowMap = &(matrixPtr->RowMap());
535 targetColMap = &(matrixPtr->ColMap());
536 }
537 else if (objectType == EPETRA_CRSGRAPH){
538 const Epetra_CrsGraph graph = matrix->Graph();
539 if (noParams && noCosts){
540 graphPtr = Isorropia::Epetra::createBalancedCopy(graph);
541 }
542 else if (noCosts){
543 graphPtr = Isorropia::Epetra::createBalancedCopy(graph, params);
544 }
545 targetBlockRowMap = &(graphPtr->RowMap());
546 targetBlockColMap = &(graphPtr->ColMap());
547 }
548 else if (objectType == EPETRA_ROWMATRIX){
549 if (noParams && noCosts){
550 rowMatrixPtr = Isorropia::Epetra::createBalancedCopy(*matrix);
551 }
552 else if (noCosts){
553 rowMatrixPtr = Isorropia::Epetra::createBalancedCopy(*matrix, params);
554 }
555 targetRowMap = &(rowMatrixPtr->RowMatrixRowMap());
556 targetColMap = &(rowMatrixPtr->RowMatrixColMap());
557 }
558 else if (objectType == EPETRA_LINEARPROBLEM){
559
560 // Create a linear problem with this matrix.
561
562 LHSmap = new Epetra_Map(numCols, base, Comm);
563
564 int myRHSsize = sourceRowMap.NumMyElements();
565 int myLHSsize = LHSmap->NumMyElements();
566
567 int valSize = ((myRHSsize > myLHSsize) ? myRHSsize : myLHSsize);
568
569 double *vals = NULL;
570
571 if (valSize){
572 vals = new double [valSize];
573 }
574
575 if (valSize){
576 for (int i=0; i < valSize; i++){
577 // put my rank in my portion of LHS and my portion of RHS
578 vals[i] = localProc;
579 }
580 }
581
582 RHS = new Epetra_MultiVector(Copy, sourceRowMap, vals, 1, 1);
583
584 LHS = new Epetra_MultiVector(Copy, *LHSmap, vals, 1, 1);
585
586 if (valSize){
587 delete [] vals;
588 }
589
590 problem = new Epetra_LinearProblem(matrix.get(), LHS, RHS);
591
592 Epetra_LinearProblem lp = *problem;
593
594 if (lp.CheckInput()){
595 ERROREXIT((localProc==0), "Error creating a LinearProblem");
596 }
597 if (noParams && noCosts){
598 problemPtr = Isorropia::Epetra::createBalancedCopy(lp);
599 }
600 else if (noCosts){
601 problemPtr = Isorropia::Epetra::createBalancedCopy(lp, params);
602 }
603
604 targetRowMap = &(problemPtr->GetMatrix()->RowMatrixRowMap());
605 targetColMap = &(problemPtr->GetMatrix()->RowMatrixColMap());
606 }
607
608 // Redistribute the edge weights
609 // Comment this out since we don't redistribute columns
610
611 if (edgeWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS){
612
613 if (partitioningType == GRAPH_PARTITIONING){
614
615 Epetra_Import *importer = NULL;
616
617 if (objectType == EPETRA_CRSGRAPH){
618 newewgts = Teuchos::rcp(new Epetra_CrsMatrix(Copy, *graphPtr));
619 targetRowMap = &(newewgts->RowMap());
620 targetColMap = &(newewgts->ColMap());
621 }
622 else{
623 newewgts = Teuchos::rcp(new Epetra_CrsMatrix(Copy, *targetRowMap, *targetColMap, 0));
624 }
625
626 importer = new Epetra_Import(*targetRowMap, sourceRowMap);
627 newewgts->Import(*eptr, *importer, Insert);
628 newewgts->FillComplete(*targetColMap, *targetRowMap);
629
630 costs.setGraphEdgeWeights(newewgts);
631 }
632 }
633
634 // Redistribute the vertex weights
635
636 if ((vertexWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS)){
637
638 Epetra_Import *importer = NULL;
639
640 if (objectType == EPETRA_CRSGRAPH){
641 newvwgts = Teuchos::rcp(new Epetra_Vector(*targetBlockRowMap));
642 importer = new Epetra_Import(*targetBlockRowMap, sourceRowMap);
643 }
644 else{
645 newvwgts = Teuchos::rcp(new Epetra_Vector(*targetRowMap));
646 importer = new Epetra_Import(*targetRowMap, sourceRowMap);
647 }
648
649 newvwgts->Import(*vptr, *importer, Insert);
650 costs.setVertexWeights(newvwgts);
651 }
652
653 if (localProc == 0){
654 test_type(numPartitions, partitioningType, vertexWeightType, edgeWeightType, objectType);
655 }
656
657 if (verbose){
658
659 // Picture of problem before balancing
660
661 if (objectType == EPETRA_LINEARPROBLEM){
662
663 ispatest::show_matrix("Before load balancing", *problem, Comm);
664 }
665 else{
666 ispatest::show_matrix("Before load balancing", matrix->Graph(), Comm);
667 }
668
669 // Picture of problem after balancing
670
671 if (objectType == EPETRA_LINEARPROBLEM){
672 ispatest::show_matrix("After load balancing (x in Ax=b is not redistributed)", *problemPtr, Comm);
673 }
674 else if (objectType == EPETRA_ROWMATRIX){
675 ispatest::show_matrix("After load balancing", *rowMatrixPtr, Comm);
676 }
677 else if (objectType == EPETRA_CRSMATRIX){
678 ispatest::show_matrix("After load balancing", matrixPtr->Graph(), Comm);
679 }
680 else if (objectType == EPETRA_CRSGRAPH){
681 ispatest::show_matrix("After load balancing", *graphPtr, Comm);
682 }
683 }
684
685 // After partitioning, recompute the metrics
686
687 if (partitioningType == GRAPH_PARTITIONING){
688 if (objectType == EPETRA_LINEARPROBLEM){
689 rc = ispatest::compute_graph_metrics(*(problemPtr->GetMatrix()), costs,
690 myShare, balance2, numCuts2, cutWgt2, cutn2, cutl2);
691 }
692 else if (objectType == EPETRA_ROWMATRIX){
693 rc = ispatest::compute_graph_metrics(*rowMatrixPtr, costs,
694 myShare, balance2, numCuts2, cutWgt2, cutn2, cutl2);
695 }
696 else if (objectType == EPETRA_CRSMATRIX){
697 rc = ispatest::compute_graph_metrics(matrixPtr->Graph(), costs,
698 myShare, balance2, numCuts2, cutWgt2, cutn2, cutl2);
699 }
700 else {
701 rc = ispatest::compute_graph_metrics(*graphPtr, costs,
702 myShare, balance2, numCuts2, cutWgt2, cutn2, cutl2);
703 }
704 }
705 else{
706 if (objectType == EPETRA_LINEARPROBLEM){
707 rc = ispatest::compute_hypergraph_metrics(*(problemPtr->GetMatrix()), costs,
708 myShare, balance2, cutn2, cutl2);
709 }
710 else if (objectType == EPETRA_ROWMATRIX){
711 rc = ispatest::compute_hypergraph_metrics(*rowMatrixPtr, costs,
712 myShare, balance2, cutn2, cutl2);
713 }
714 else if (objectType == EPETRA_CRSMATRIX){
715 rc = ispatest::compute_hypergraph_metrics(matrixPtr->Graph(), costs,
716 myShare, balance2, cutn2, cutl2);
717 }
718 else{
719 rc = ispatest::compute_hypergraph_metrics(*graphPtr, costs,
720 myShare, balance2, cutn2, cutl2);
721 }
722 }
723
724 if (rc){
725 ERROREXIT((localProc==0), "Error in computing partitioning metrics")
726 }
727
728 std::string why;
729
730 if (partitioningType == GRAPH_PARTITIONING){
731 fail = (cutWgt2 > cutWgt1);
732 why = "New weighted edge cuts are worse";
733
734 if (localProc == 0){
735 std::cout << "Before partitioning: Balance " << balance1 ;
736 std::cout << " cutn " << cutn1 ;
737 std::cout << " cutl " << cutl1 ;
738
739 if (contract){
740 std::cout << " (wrt balancing over " << numPartitions << " partitions)" << std::endl;
741 std::cout << "Before partitioning: Balance " << balance3 ;
742 std::cout << " cutn " << cutn3 ;
743 std::cout << " cutl " << cutl3 ;
744 std::cout << " (wrt balancing over " << numProcs << " partitions)" ;
745 }
746 std::cout << std::endl;
747
748 std::cout << " Total edge cuts: " << numCuts1;
749 std::cout << " Total weighted edge cuts: " << cutWgt1 << std::endl;
750 std::cout << "After partitioning: Balance " << balance2 ;
751 std::cout << " cutn " << cutn2 ;
752 std::cout << " cutl " << cutl2 << std::endl;
753 std::cout << " Total edge cuts: " << numCuts2;
754 std::cout << " Total weighted edge cuts: " << cutWgt2 << std::endl;
755 }
756 }
757 else{
758 fail = (cutl2 > cutl1);
759 why = "New cutl is worse";
760
761 if (localProc == 0){
762 std::cout << "Before partitioning: Balance " << balance1 ;
763 std::cout << " cutn " << cutn1 ;
764 std::cout << " cutl " << cutl1 ;
765 if (contract){
766 std::cout << " (wrt balancing over " << numPartitions << " partitions)" << std::endl;
767 std::cout << "Before partitioning: Balance " << balance3 ;
768 std::cout << " cutn " << cutn3 ;
769 std::cout << " cutl " << cutl3 ;
770 std::cout << " (wrt balancing over " << numProcs << " partitions)" ;
771 }
772 std::cout << std::endl;
773 std::cout << "After partitioning: Balance " << balance2 ;
774 std::cout << " cutn " << cutn2 ;
775 std::cout << " cutl " << cutl2 << std::endl;
776 }
777 }
778
779 if (fail){
780 if (localProc == 0) std::cout << "ERROR: "+why << std::endl;
781 }
782
783 // Check that input matrix is valid. This test constructs an "x"
784 // with the matrix->DomainMap() and a "y" with matrix->RangeMap()
785 // and then calculates y = Ax.
786
787 if (objectType == EPETRA_LINEARPROBLEM){
788 valid = ispatest::test_matrix_vector_multiply(*problemPtr);
789 }
790 else if (objectType == EPETRA_ROWMATRIX){
791 valid = ispatest::test_row_matrix_vector_multiply(*rowMatrixPtr);
792 }
793 else if (objectType == EPETRA_CRSMATRIX){
794 valid = ispatest::test_matrix_vector_multiply(*matrixPtr);
795 }
796 else{
797 valid = ispatest::test_matrix_vector_multiply(*graphPtr);
798 }
799
800 if (!valid){
801 if (localProc == 0) std::cout << "Rebalanced matrix is not a valid Epetra matrix" << std::endl;
802 fail = 1;
803 }
804 else{
805 if (localProc == 0) std::cout << "Rebalanced matrix is a valid Epetra matrix" << std::endl;
806 }
807
808 if (localProc == 0)
809 std::cout << std::endl;
810
811
812
813 #else
814 std::cout << "test_simple main: currently can only test "
815 << "with Epetra and EpetraExt enabled." << std::endl;
816 rc = -1;
817 #endif
818
819 return fail;
820 }
821
822 int main(int argc, char** argv) {
823
824 int rc=0, fail = 0;
825 #ifdef HAVE_EPETRAEXT
826 bool verbose = false;
827 int localProc = 0;
828 // std::string *fstr;
829
830 #ifdef HAVE_MPI
831 int numProcs;
832 MPI_Init(&argc, &argv);
833 MPI_Comm_rank(MPI_COMM_WORLD, &localProc);
834 MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
835 const Epetra_MpiComm Comm(MPI_COMM_WORLD);
836 #else
837 const Epetra_SerialComm Comm;
838 #endif
839
840 Teuchos::CommandLineProcessor clp(false,true);
841
842 // --f=fileName provides a different matrix market file for input
843 // --v will print out the partitioning (small files only)
844
845 std::string *inputFile = new std::string("simple.mtx");
846 bool runAll = false;
847
848 clp.setOption( "f", inputFile,
849 "Name of input matrix market file");
850 clp.setOption( "run-all", "abort", &runAll,
851 "Don't abort if one test fails, run all of them.");
852 clp.setOption( "v", "q", &verbose,
853 "Display matrix before and after partitioning.");
854
855 Teuchos::CommandLineProcessor::EParseCommandLineReturn parse_return =
856 clp.parse(argc,argv);
857
858 if( parse_return == Teuchos::CommandLineProcessor::PARSE_HELP_PRINTED){
859 #ifdef HAVE_MPI
860 MPI_Finalize();
861 #endif
862 return 0;
863 }
864 if( parse_return != Teuchos::CommandLineProcessor::PARSE_SUCCESSFUL ) {
865 #ifdef HAVE_MPI
866 MPI_Finalize();
867 #endif
868 return 1;
869 }
870
871 const char *fname = inputFile->c_str();
872
873 // Read in the matrix market file and distribute its rows across the
874 // processes.
875 //
876 // This reader uses the default Epetra_Map for number of rows for the
877 // RowMap() and for the RangeMap(). For non-square matrices it uses
878 // the default Epetra_Map for the number of columns for the DomainMap(),
879 // otherwise it uses the RowMap().
880 //
881 // The maps can be specified with other versions of MMFtoCrsMatrix().
882
883
884 Epetra_CrsMatrix *matrixPtr;
885 rc = EpetraExt::MatrixMarketFileToCrsMatrix(fname, Comm, matrixPtr);
886 if (rc < 0){
887 if (localProc==0){
888 std::cout << "error reading input file" << std::endl << "FAIL" << std::endl;
889 }
890 exit(1);
891 }
892
893 bool square = (matrixPtr->NumGlobalRows() == matrixPtr->NumGlobalCols());
894 // If matrix is square, determine if it's symmetric TODO
895
896
897 // Run some partitioning tests
898 // Test graph and hypergraph partitioning
899 // Test with and without application supplied weights
900 // Test the Epetra_CrsMatrix interface and also the Epetra_CrsGraph interface
901 // Do tests where the vertex or edge weights vary widely
902
903 Teuchos::RCP<Epetra_CrsMatrix> testm = Teuchos::rcp(matrixPtr);
904 int failures = 0;
905
906 #ifdef SHORT_TEST
907 fail = run_test(testm,
908 verbose,
909 false, // do not test #partitions < #processes
910 NO_APPLICATION_SUPPLIED_WEIGHTS,
911 NO_APPLICATION_SUPPLIED_WEIGHTS,
912 EPETRA_CRSGRAPH);
913
914 CHECK_FAILED();
915 goto Report;
916
917 #else
918
919 if (square){
920 #ifdef HAVE_ISORROPIA_ZOLTAN
921 fail = run_test(testm, // test matrix
922 verbose, // display matrix before and after?
923 false, // do not test #partitions < #processes
924 GRAPH_PARTITIONING, // perform zoltan graph partitioning
925 NO_APPLICATION_SUPPLIED_WEIGHTS,
926 NO_APPLICATION_SUPPLIED_WEIGHTS,
927 EPETRA_LINEARPROBLEM); // use linear problem interface of isorropia
928
929 CHECK_FAILED();
930
931 fail = run_test(testm,
932 verbose, // draw graph before and after partitioning?
933 false, // do not test #partitions < #processes
934 HYPERGRAPH_PARTITIONING, // do graph partitioning
935 NO_APPLICATION_SUPPLIED_WEIGHTS,
936 NO_APPLICATION_SUPPLIED_WEIGHTS,
937 EPETRA_CRSMATRIX); // use the Epetra_CrsMatrix interface
938
939 CHECK_FAILED();
940
941 fail = run_test(testm,
942 verbose,
943 true, // test #partitions < #processes
944 GRAPH_PARTITIONING,
945 NO_APPLICATION_SUPPLIED_WEIGHTS,
946 NO_APPLICATION_SUPPLIED_WEIGHTS,
947 EPETRA_CRSMATRIX);
948
949 CHECK_FAILED();
950
951 fail = run_test(testm,
952 verbose,
953 false, // do not test #partitions < #processes
954 GRAPH_PARTITIONING,
955 NO_APPLICATION_SUPPLIED_WEIGHTS,
956 NO_APPLICATION_SUPPLIED_WEIGHTS,
957 EPETRA_LINEARPROBLEM);
958
959 CHECK_FAILED();
960
961 fail = run_test(testm,
962 verbose,
963 false, // do not test #partitions < #processes
964 GRAPH_PARTITIONING,
965 NO_APPLICATION_SUPPLIED_WEIGHTS,
966 NO_APPLICATION_SUPPLIED_WEIGHTS,
967 EPETRA_ROWMATRIX);
968
969 CHECK_FAILED();
970 #else
971 fail = 0;
972 if (localProc == 0){
973 std::cout << "Test not run because it requires EPETRA_EXT" << std::endl;
974 }
975 #endif
976
977
978
979 #ifdef HAVE_ISORROPIA_ZOLTAN
980
981 fail = run_test(testm,
982 verbose,
983 true, // test #partitions < #processes
984 HYPERGRAPH_PARTITIONING,
985 NO_APPLICATION_SUPPLIED_WEIGHTS,
986 NO_APPLICATION_SUPPLIED_WEIGHTS,
987 EPETRA_CRSGRAPH);
988
989 CHECK_FAILED();
990
991 fail = run_test(testm,
992 verbose,
993 false, // do not test #partitions < #processes
994 HYPERGRAPH_PARTITIONING,
995 NO_APPLICATION_SUPPLIED_WEIGHTS,
996 NO_APPLICATION_SUPPLIED_WEIGHTS,
997 EPETRA_ROWMATRIX);
998
999 CHECK_FAILED();
1000
1001 fail = run_test(testm,
1002 verbose,
1003 false, // do not test #partitions < #processes
1004 HYPERGRAPH_PARTITIONING,
1005 NO_APPLICATION_SUPPLIED_WEIGHTS,
1006 NO_APPLICATION_SUPPLIED_WEIGHTS,
1007 EPETRA_LINEARPROBLEM);
1008
1009 CHECK_FAILED();
1010
1011 #endif
1012 }
1013 #endif // SHORT_TEST
1014
1015 #else
1016 fail = 0;
1017 if (localProc == 0){
1018 std::cout << "Test not run because it requires EPETRA_EXT" << std::endl;
1019 }
1020 #endif
1021
1022 Report:
1023
1024 #ifdef HAVE_MPI
1025 MPI_Finalize();
1026 #endif
1027
1028 if (localProc == 0){
1029 if (failures){
1030 if (failures > 1)
1031 std::cout << std::endl << failures << " FAILURES" << std::endl;
1032 else
1033 std::cout << std::endl << "1 FAILURE" << std::endl;
1034
1035 if (!runAll){
1036 std::cout <<
1037 "(Use option --run-all if you do not want this test to abort on failure)" << std::endl;
1038 }
1039 }
1040 else
1041 std::cout << std::endl << "PASS" << std::endl;
1042 }
1043
1044 return fail;
1045 }