Debian Codegraph @

packages/isorropia/test/mtx/test_simple.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 Isorropia::Epetra::create_partitioner followed by
45 // redistribution with a Isorropia::Epetra::Redistributor.
46 //
47 // For graph partitioning:
48 //
49 // The nonzeros of this matrix represent graph edges. The row
50 // or column IDs represent the graph vertices. Only square
51 // matrices will be processed with graph partitioning.
52 //
53 // Isorropia will ignore the self-edges (the nonzero diagonal entries).
54 //
55 // For hypergraph partitioning:
56 //
57 // By convention, the columns of this matrix are hyperedges, and we
58 // wish to balance the vertices, represented by the rows.
59 //
60 // If run with --v option, prints out partitioning before and after.
61 //
62 // This is what simple.mtx looks like. 25 rows, 25 cols, 105 non-zeroes.
63 //
64 // 0123456789012345678901234
65 // 0xx x 0
66 // 1xxx x 1
67 // 2 xxx x 2
68 // 3 xxx x 3
69 // 4 xx x 4
70 // 5x xx x 5
71 // 6 x xxx x 6
72 // 7 x xxx x 7
73 // 8 x xxx x 8
74 // 9 x xx x 9
75 // 0 x xx x 0
76 // 1 x xxx x 1
77 // 2 x xxx x 2
78 // 3 x xxx x 3
79 // 4 x xx x 4
80 // 5 x xx x 5
81 // 6 x xxx x 6
82 // 7 x xxx x 7
83 // 8 x xxx x 8
84 // 9 x xx x9
85 // 0 x xx 0
86 // 1 x xxx 1
87 // 2 x xxx 2
88 // 3 x xxx3
89 // 4 x xx4
90 // 0123456789012345678901234
91 //
92 // If run with --f={filename} a matrix market file other than simple.mtx
93 // will be processed.
94 //
95
96 #include <Isorropia_ConfigDefs.hpp>
97 #include <Isorropia_Epetra.hpp>
98 #include <Isorropia_EpetraPartitioner.hpp>
99 #include <Isorropia_EpetraRedistributor.hpp>
100 #include <Isorropia_EpetraCostDescriber.hpp>
101
102 #include <ispatest_lbeval_utils.hpp>
103 #include <ispatest_epetra_utils.hpp>
104
105 #ifdef HAVE_EPETRA
106 #ifdef HAVE_MPI
107 #include <Epetra_MpiComm.h>
108 #else
109 #include <Epetra_SerialComm.h>
110 #endif
111 #include <Epetra_Map.h>
112 #include <Epetra_CrsMatrix.h>
113 #include <Epetra_Vector.h>
114 #ifdef HAVE_EPETRAEXT
115 #include <EpetraExt_CrsMatrixIn.h>
116 #endif
117 #endif
118 #ifdef _MSC_VER
119 #include "winprocess.h"
120 #endif
121
122 // Only run the first test
123 //#define SHORT_TEST 1
124
125 #include <Teuchos_CommandLineProcessor.hpp>
126
127 #define GRAPH_PARTITIONING 1
128 #define HYPERGRAPH_PARTITIONING 2
129
130 #define SUPPLY_EQUAL_WEIGHTS 1
131 #define SUPPLY_UNEQUAL_WEIGHTS 2
132 #define NO_APPLICATION_SUPPLIED_WEIGHTS 3
133
134 #define EPETRA_CRSGRAPH 1
135 #define EPETRA_CRSMATRIX 2
136
137 static int tmp=0;
138 static int testTwoArgInterface = 1;
139
140 #define CHECK_FAILED() { \
141 Comm.SumAll(&fail, &tmp, 1); \
142 if (tmp){ \
143 failures++; \
144 if (!runAll) goto Report; \
145 } \
146 fail = 0; \
147 }
148
149 #define ERROREXIT(v, s) \
150 if (v){ \
151 test_type(numPartitions, partitioningType, vertexWeightType, edgeWeightType, objectType); \
152 std::cout << s << std::endl << "FAIL" << std::endl; \
153 } \
154 exit(1);
155
156 #define ERRORRETURN(v, s) \
157 if (v){ \
158 test_type(numPartitions, partitioningType, vertexWeightType, edgeWeightType, objectType); \
159 std::cout << s << std::endl << "FAIL" << std::endl; \
160 } \
161 return 1;
162
163 static 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
201 std::cout << "using Epetra_CrsMatrix interface";
202
203 if (numPartitions > 0){
204 std::cout << std::endl << " ";
205 std::cout << "NUM PARTS is " << numPartitions;
206 }
207 std::cout << std::endl;
208
209 }
210
211 static int run_test(Teuchos::RCP<Epetra_CrsMatrix> matrix,
212 bool verbose, // display the graph before & after
213 bool contract, // set global number of partitions to 1/2 num procs
214 bool extend, // set global number of partitions to 2* num procs
215 int partitioningType, // hypergraph or graph partitioning, or simple
216 int vertexWeightType, // use vertex weights?
217 int edgeWeightType, // use edge/hyperedge weights?
218 int objectType) // use isorropia's CrsMatrix or CrsGraph
219 {
220 int rc=0, fail = 0;
221 #ifdef HAVE_EPETRAEXT
222 int localProc = 0;
223 double balance1, balance2, cutn1, cutn2, cutl1, cutl2;
224 double balance3, cutn3, cutl3;
225 double cutWgt1, cutWgt2, cutWgt3;;
226 int numCuts1, numCuts2, numCuts3, valid;
227 int numPartitions = 0;
228 int keepDenseEdges = 0;
229 int numProcs = 1;
230
231 #ifdef HAVE_MPI
232 const Epetra_MpiComm &Comm = dynamic_cast<const Epetra_MpiComm &>(matrix->Comm());
233 localProc = Comm.MyPID();
234 numProcs = Comm.NumProc();
235 #else
236 const Epetra_SerialComm &Comm = dynamic_cast<const Epetra_SerialComm &>(matrix->Comm());
237 #endif
238
239 int numRows = matrix->NumGlobalRows();
240
241 if (numRows < (numProcs * 100)){
242 // If dense edges are thrown out of a small
243 // matrix, there may be nothing left.
244 keepDenseEdges = 1;
245 }
246
247 double myShareBefore = 1.0 / numProcs;
248 double myShare = myShareBefore;
249
250 if (contract && (numProcs < 2)){
251 contract = 0;
252 }
253
254 if (contract || extend){
255 if (contract){
256 numPartitions = numProcs / 2;
257 }
258 else{
259 numPartitions = numProcs * 2;
260 }
261
262 if (numPartitions > numRows)
263 numPartitions = numRows;
264
265 if (numPartitions < numProcs){
266
267 // Need each proc's share to calculate quality metric
268
269 if (localProc < numPartitions){
270 myShare = 1.0 / numPartitions;
271 }
272 else{
273 myShare = 0.0;
274 }
275 }
276 }
277
278 // Check that input matrix is valid. This test constructs an "x"
279 // with the matrix->DomainMap() and a "y" with matrix->RangeMap()
280 // and then calculates y = Ax.
281
282 valid = ispatest::test_matrix_vector_multiply(*matrix);
283
284 if (!valid){
285 ERRORRETURN((localProc==0), "Test matrix is not a valid Epetra matrix");
286 }
287
288 // Compute vertex and edge weights
289
290 Teuchos::RCP<Isorropia::Epetra::CostDescriber> costs =
291 Teuchos::rcp(new Isorropia::Epetra::CostDescriber);
292
293 Teuchos::RCP<Epetra_Vector> vptr;
294
295 Teuchos::RCP<Epetra_CrsMatrix> eptr;
296
297 Teuchos::RCP<Epetra_Vector> hyperEdgeWeights;
298
299
300 if (edgeWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS){
301
302 if (partitioningType == GRAPH_PARTITIONING){
303
304 // Create graph edge weights.
305
306 eptr = Teuchos::rcp(new Epetra_CrsMatrix(*matrix));
307
308 if (vertexWeightType == SUPPLY_EQUAL_WEIGHTS){
309 eptr->PutScalar(1.0); // set all nonzeros to 1.0
310 }
311 else{
312 int nrows = eptr->NumMyRows();
313 int maxRowSize = eptr->MaxNumEntries();
314 double *newVal = NULL;
315 if (maxRowSize > 0){
316 newVal = new double [maxRowSize];
317 for (int j=0; j<maxRowSize; j++){
318 newVal[j] = localProc + 1 + j;
319 }
320 }
321 int numEntries;
322 int *idx;
323 double *val;
324 for (int i=0; i<nrows; i++){
325 rc = eptr->ExtractMyRowView(i, numEntries, val, idx);
326 for (int j=0; j<numEntries; j++){
327 val[j] = newVal[j];
328 }
329 }
330 if (newVal) delete [] newVal;
331 }
332
333 eptr->FillComplete(matrix->DomainMap(), matrix->RangeMap());
334 eptr->OptimizeStorage();
335
336 costs->setGraphEdgeWeights(eptr);
337 }
338 else if (partitioningType == HYPERGRAPH_PARTITIONING){
339 // Create hyperedge weights. (Note that the list of hyperedges that a
340 // process provides weights for has no relation to the columns
341 // that it has non-zeroes for, or the rows that is has. Hypergraphs
342 // in general are not square. Also more than one process can provide
343 // a weight for the same edge. Zoltan combines the weights according
344 // to the value of the PHG_EDGE_WEIGHT_OPERATION parameter. The default
345 // for this parameter is to use the maximum edge weight provided by any
346 // process for a given hyperedge.)
347
348 Epetra_Map hyperEdgeMap(matrix->NumGlobalCols(), matrix->IndexBase(), Comm);
349 hyperEdgeWeights = Teuchos::rcp(new Epetra_Vector(hyperEdgeMap));
350
351 int *edgeGIDs = NULL;
352 double *weights = NULL;
353 int numHEweights = hyperEdgeMap.NumMyElements();
354
355 if (numHEweights){
356 edgeGIDs = new int [numHEweights];
357 weights = new double [numHEweights];
358
359 if (edgeWeightType == SUPPLY_EQUAL_WEIGHTS){
360 for (int i=0; i<numHEweights; i++){
361 edgeGIDs[i] = hyperEdgeMap.GID(i);
362 weights[i] = 1.0;
363 }
364 }
365 else{
366 int hiVolumeStart = matrix->NumGlobalCols() / 3;
367 int hiVolumeEnd = hiVolumeStart * 2;
368 for (int i=0; i<numHEweights; i++){
369 edgeGIDs[i] = hyperEdgeMap.GID(i);
370 if ((edgeGIDs[i] < hiVolumeStart) || (edgeGIDs[i] >= hiVolumeEnd)){
371 weights[i] = 1.0;
372 }
373 else{
374 weights[i] = 3.0;
375 }
376 }
377 }
378 hyperEdgeWeights->ReplaceGlobalValues(numHEweights, weights, edgeGIDs);
379 }
380
381 if (weights){
382 delete [] weights;
383 delete [] edgeGIDs;
384 }
385
386 costs->setHypergraphEdgeWeights(hyperEdgeWeights);
387 }
388 }
389
390 if ((vertexWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS)){
391
392 const Epetra_Map &rowmap = matrix->RowMap();
393 int nrows = rowmap.NumMyElements();
394 double *val = NULL;
395
396 if (nrows){
397 val = new double [nrows];
398
399 if (vertexWeightType == SUPPLY_EQUAL_WEIGHTS){
400 for (int i=0; i<nrows; i++){
401 val[i] = 1.0;
402 }
403 }
404 else if (vertexWeightType == SUPPLY_UNEQUAL_WEIGHTS){
405 for (int i=0; i<nrows; i++){
406 val[i] = 1.0 + ((localProc+1) / 2);
407 }
408 }
409 }
410
411 vptr = Teuchos::rcp(new Epetra_Vector(Copy, rowmap, val));
412
413 if (val) delete [] val;
414
415 costs->setVertexWeights(vptr);
416 }
417
418 // Calculate partition quality metrics before calling Zoltan
419
420 if (partitioningType == HYPERGRAPH_PARTITIONING){
421
422 rc = ispatest::compute_hypergraph_metrics(matrix->Graph(), *costs,
423 myShare, balance1, cutn1, cutl1);
424
425 if (contract){
426 // balance wrt target of balancing weight over *all* procs
427 rc = ispatest::compute_hypergraph_metrics(matrix->Graph(), *costs,
428 myShareBefore, balance3, cutn3, cutl3);
429 }
430 }
431 else{
432 rc = ispatest::compute_graph_metrics(matrix->Graph(), *costs,
433 myShare, balance1, numCuts1, cutWgt1, cutn1, cutl1);
434 if (contract){
435 // balance wrt target of balancing weight over *all* procs
436 rc = ispatest::compute_graph_metrics(matrix->Graph(), *costs,
437 myShareBefore, balance3, numCuts3, cutWgt3, cutn3, cutl3);
438 }
439 }
440
441 if (rc){
442 ERRORRETURN((localProc==0), "Error in computing partitioning metrics")
443 }
444
445 Teuchos::ParameterList params;
446
447
448 #ifdef HAVE_ISORROPIA_ZOLTAN
449
450 // Set the Zoltan parameters for this problem
451
452 Teuchos::ParameterList &sublist = params.sublist("ZOLTAN");
453
454 if (numPartitions > 0){
455 // test #Partitions < #Processes
456 std::ostringstream os;
457 os << numPartitions;
458 std::string s = os.str();
459 params.set("NUM PARTS", s);
460 }
461
462 //sublist.set("DEBUG_LEVEL", "1"); // Zoltan will print out parameters
463 //sublist.set("DEBUG_LEVEL", "5"); // proc 0 will trace Zoltan calls
464 //sublist.set("DEBUG_MEMORY", "2"); // Zoltan will trace alloc & free
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 #else
482 ERRORRETURN((localProc==0),
483 "Zoltan partitioning required but Zoltan not available.")
484 #endif
485
486 // Perform partitioning with Zoltan (if we have it)
487
488 Teuchos::RCP<Isorropia::Epetra::Partitioner> partitioner;
489
490 if ((edgeWeightType == NO_APPLICATION_SUPPLIED_WEIGHTS) &&
491 (vertexWeightType == NO_APPLICATION_SUPPLIED_WEIGHTS)){
492
493 if (testTwoArgInterface){ // explicity supply parameters
494 if (objectType == EPETRA_CRSGRAPH){
495 // Test the Epetra_CrsGraph interface of Isorropia
496 Teuchos::RCP<const Epetra_CrsGraph> graph =
497 Teuchos::rcp(new Epetra_CrsGraph(matrix->Graph()));
498 partitioner = Teuchos::rcp(new Isorropia::Epetra::Partitioner(graph, params));
499 }
500 else{
501 // Test the Epetra_CrsMatrix interface of Isorropia
502 Teuchos::RCP<const Epetra_RowMatrix> rm = matrix;
503 partitioner = Teuchos::rcp(new Isorropia::Epetra::Partitioner(rm, params));
504 }
505 testTwoArgInterface = 0;
506 }
507 else{ // let Isorropia choose default parameters
508 if (objectType == EPETRA_CRSGRAPH){
509 // Test the Epetra_CrsGraph interface of Isorropia
510 Teuchos::RCP<const Epetra_CrsGraph> graph =
511 Teuchos::rcp(new Epetra_CrsGraph(matrix->Graph()));
512 partitioner = Teuchos::rcp(new Isorropia::Epetra::Partitioner(graph));
513 }
514 else{
515 // Test the Epetra_CrsMatrix interface of Isorropia
516 Teuchos::RCP<const Epetra_RowMatrix> rm = matrix;
517 partitioner = Teuchos::rcp(new Isorropia::Epetra::Partitioner(rm));
518 }
519 testTwoArgInterface = 1; // alternate these tests
520 }
521
522 }
523 else{
524
525 if (objectType == EPETRA_CRSGRAPH){
526 // Test the Epetra_CrsGraph interface of Isorropia
527 Teuchos::RCP<const Epetra_CrsGraph> graph =
528 Teuchos::rcp(new Epetra_CrsGraph(matrix->Graph()));
529 partitioner = Teuchos::rcp(new Isorropia::Epetra::Partitioner(graph, costs, params));
530 }
531 else{
532 // Test the Epetra_CrsMatrix interface of Isorropia
533 Teuchos::RCP<const Epetra_RowMatrix> rm = matrix;
534 partitioner = Teuchos::rcp(new Isorropia::Epetra::Partitioner(rm, costs, params));
535 }
536 }
537 // Create a Redistributor based on the partitioning
538
539 Isorropia::Epetra::Redistributor rd(partitioner);
540
541 // Redistribute the matrix
542 Teuchos::RCP<Epetra_CrsMatrix> newMatrix;
543 try {
544 newMatrix = rd.redistribute(*matrix);
545 }
546 catch(...) {
547 if (numPartitions > numProcs) {// Redistribution has to fail
548 if (localProc == 0){
549 std::cout << "Too many parts for too few processors, distribution has to fail" << std::endl ;
550 }
551 return (0);
552 }
553 ERRORRETURN((localProc==0), "Error in computing partitioning metrics after rebalancing")
554 }
555
556 // Redistribute the vertex weights
557
558 if ((vertexWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS)){
559
560 Teuchos::RCP<Epetra_Vector> newvwgts = rd.redistribute(*vptr);
561 costs->setVertexWeights(newvwgts);
562 }
563
564 // Redistribute the edge weights
565
566 if (edgeWeightType != NO_APPLICATION_SUPPLIED_WEIGHTS){
567
568 if (partitioningType == GRAPH_PARTITIONING){
569 Teuchos::RCP<Epetra_CrsMatrix> newewgts = rd.redistribute(*eptr);
570 costs->setGraphEdgeWeights(newewgts);
571 }
572 }
573 if (partitioningType == HYPERGRAPH_PARTITIONING){
574 rc = ispatest::compute_hypergraph_metrics(newMatrix->Graph(), *costs,
575 myShare, balance2, cutn2, cutl2);
576 }
577 else{
578 rc = ispatest::compute_graph_metrics(newMatrix->Graph(), *costs,
579 myShare, balance2, numCuts2, cutWgt2, cutn2, cutl2);
580 }
581
582 // After partitioning, recompute the metrics
583
584 if (rc){
585 ERRORRETURN((localProc==0), "Error in computing partitioning metrics after rebalancing")
586 }
587
588 // Output information about repartitioning
589
590 if (localProc == 0){
591 test_type(numPartitions, partitioningType, vertexWeightType, edgeWeightType, objectType);
592 std::cout << std::endl;
593 }
594
595 if (verbose){
596 ispatest::show_matrix("Before load balancing", matrix->Graph(), Comm);
597 if (localProc == 0) std::cout << std::endl;
598 }
599
600
601 if (verbose){
602 ispatest::show_matrix("After load balancing", newMatrix.get()->Graph(), Comm);
603 if (localProc==0) std::cout << std::endl;
604 }
605
606 std::string why;
607
608 if (partitioningType == GRAPH_PARTITIONING){
609 fail = (cutWgt2 > cutWgt1);
610 why = "New weighted edge cuts are worse";
611
612 if (localProc == 0){
613 std::cout << "Before partitioning: Balance " << balance1 ;
614 std::cout << " cutn " << cutn1 ;
615 std::cout << " cutl " << cutl1 ;
616
617 if (contract){
618 std::cout << " (wrt balancing over " << numPartitions << " partitions)" << std::endl;
619 std::cout << "Before partitioning: Balance " << balance3 ;
620 std::cout << " cutn " << cutn3 ;
621 std::cout << " cutl " << cutl3 ;
622 std::cout << " (wrt balancing over " << numProcs << " partitions)" ;
623 }
624 std::cout << std::endl;
625
626 std::cout << " Total edge cuts: " << numCuts1;
627 std::cout << " Total weighted edge cuts: " << cutWgt1 << std::endl;
628
629
630 std::cout << "After partitioning: Balance " << balance2 ;
631 std::cout << " cutn " << cutn2 ;
632 std::cout << " cutl " << cutl2 << std::endl;
633 std::cout << " Total edge cuts: " << numCuts2;
634 std::cout << " Total weighted edge cuts: " << cutWgt2 << std::endl;
635 }
636 }
637 else{
638 fail = (cutl2 > cutl1); // Zoltan hypergraph partitioning
639 why = "New cutl is worse";
640
641 if (localProc == 0){
642 std::cout << "Before partitioning: Balance " << balance1 ;
643 std::cout << " cutn " << cutn1 ;
644 std::cout << " cutl " << cutl1 ;
645 if (contract){
646 std::cout << " (wrt balancing over " << numPartitions << " partitions)" << std::endl;
647 std::cout << "Before partitioning: Balance " << balance3 ;
648 std::cout << " cutn " << cutn3 ;
649 std::cout << " cutl " << cutl3 ;
650 std::cout << " (wrt balancing over " << numProcs << " partitions)" ;
651 }
652 std::cout << std::endl;
653 std::cout << "After partitioning: Balance " << balance2 ;
654 std::cout << " cutn " << cutn2 ;
655 std::cout << " cutl " << cutl2 << std::endl;
656 }
657 }
658 if (fail){
659 //if (localProc == 0) std::cout << "ERROR: "+why << std::endl;
660 std::cout << "ERROR: "+why << std::endl;
661 }
662
663 // Try multiplying the rebalanced matrix and its transpose by a vector,
664 // to ensure it's a valid Epetra matrix
665
666 valid = ispatest::test_matrix_vector_multiply(*newMatrix);
667
668 if (!valid){
669 std::cout << "Rebalanced matrix is not a valid Epetra matrix" << std::endl;
670 //if (localProc == 0) std::cout << "Rebalanced matrix is not a valid Epetra matrix" << std::endl;
671 fail = 1;
672 }
673 else{
674 if (localProc == 0) std::cout << "Rebalanced matrix is a valid Epetra matrix" << std::endl;
675 }
676
677 if (localProc == 0)
678 std::cout << std::endl;
679
680 #else
681 std::<< "test_simple : currently can only test "
682 << "with Epetra and EpetraExt enabled." << std::endl;
683 fail = 1;
684 #endif
685
686 return fail;
687 }
688
689 int main(int argc, char** argv) {
690
691 int rc=0, fail = 0;
692 #ifdef HAVE_EPETRAEXT
693 bool verbose = false;
694 int localProc = 0;
695
696 #ifdef HAVE_MPI
697 int numProcs;
698 MPI_Init(&argc, &argv);
699 MPI_Comm_rank(MPI_COMM_WORLD, &localProc);
700 MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
701 const Epetra_MpiComm Comm(MPI_COMM_WORLD);
702 #else
703 const Epetra_SerialComm Comm;
704 #endif
705
706 Teuchos::CommandLineProcessor clp(false,true);
707
708 // --f=fileName provides a different matrix market file for input
709 // --v will print out the partitioning (small files only)
710 // --run-all will continue to run all tests even if there is a failure
711
712 std::string *inputFile = new std::string("simple.mtx");
713 bool runAll = false;
714
715 clp.setOption( "f", inputFile,
716 "Name of input matrix market file");
717 clp.setOption( "run-all", "abort", &runAll,
718 "Don't abort if one test fails, run all of them.");
719 clp.setOption( "v", "q", &verbose,
720 "Display matrix before and after partitioning.");
721
722 Teuchos::CommandLineProcessor::EParseCommandLineReturn parse_return =
723 clp.parse(argc,argv);
724
725 if( parse_return == Teuchos::CommandLineProcessor::PARSE_HELP_PRINTED){
726 #ifdef HAVE_MPI
727 MPI_Finalize();
728 #endif
729 return 0;
730 }
731 if( parse_return != Teuchos::CommandLineProcessor::PARSE_SUCCESSFUL ) {
732 #ifdef HAVE_MPI
733 MPI_Finalize();
734 #endif
735 return 1;
736 }
737
738 const char *fname = inputFile->c_str();
739
740 // Read in the matrix market file and distribute its rows across the
741 // processes.
742 //
743 // This reader uses the default Epetra_Map for number of rows for the
744 // RowMap() and for the RangeMap(). For non-square matrices it uses
745 // the default Epetra_Map for the number of columns for the DomainMap(),
746 // otherwise it uses the RowMap().
747 //
748 // The maps can be specified with other versions of MMFtoCrsMatrix().
749
750 Epetra_CrsMatrix *matrixPtr;
751 rc = EpetraExt::MatrixMarketFileToCrsMatrix(fname, Comm, matrixPtr);
752 if (rc < 0){
753 if (localProc==0) std::cerr << "error reading input file"<< std::cout;
754 exit(1);
755 }
756
757 bool square = (matrixPtr->NumGlobalRows() == matrixPtr->NumGlobalCols());
758
759 // If matrix is square, determine if it's symmetric TODO
760
761 // Run some partitioning tests
762 // Test graph and hypergraph partitioning
763 // Test with and without application supplied weights
764 // Test the Epetra_CrsMatrix interface and also the Epetra_CrsGraph interface
765 // Do tests where the vertex or edge weights vary widely
766
767 Teuchos::RCP<Epetra_CrsMatrix> testm = Teuchos::rcp(matrixPtr);
768
769 int failures = 0;
770
771 #ifdef SHORT_TEST
772 fail = run_test(testm,
773 verbose,
774 true, // make #partitions < #processes
775 false,
776 HYPERGRAPH_PARTITIONING,
777 SUPPLY_UNEQUAL_WEIGHTS,
778 SUPPLY_EQUAL_WEIGHTS,
779 EPETRA_CRSMATRIX);
780
781 CHECK_FAILED();
782 fail = run_test(testm,
783 verbose,
784 false, // make #partitions < #processes
785 true,
786 HYPERGRAPH_PARTITIONING,
787 SUPPLY_UNEQUAL_WEIGHTS,
788 SUPPLY_EQUAL_WEIGHTS,
789 EPETRA_CRSMATRIX);
790
791 CHECK_FAILED();
792
793 goto Report;
794 #else
795
796 if (square){
797 #ifdef HAVE_ISORROPIA_ZOLTAN
798 fail = run_test(testm,
799 verbose, // draw graph before and after partitioning
800 false, // do not make #partitions < #processes
801 false,
802 GRAPH_PARTITIONING, // do graph partitioning
803 SUPPLY_EQUAL_WEIGHTS, // supply vertex weights, all the same
804 SUPPLY_EQUAL_WEIGHTS, // supply edge weights, all the same
805 EPETRA_CRSMATRIX); // use the Epetra_CrsMatrix interface
806
807 CHECK_FAILED();
808
809 fail = run_test(testm,
810 verbose, // draw graph before and after partitioning
811 false, // do not make #partitions < #processes
812 true,
813 GRAPH_PARTITIONING, // do graph partitioning
814 SUPPLY_EQUAL_WEIGHTS, // supply vertex weights, all the same
815 SUPPLY_EQUAL_WEIGHTS, // supply edge weights, all the same
816 EPETRA_CRSMATRIX); // use the Epetra_CrsMatrix interface
817
818 CHECK_FAILED();
819
820
821 fail = run_test(testm,
822 verbose,
823 false,
824 false,
825 GRAPH_PARTITIONING,
826 SUPPLY_UNEQUAL_WEIGHTS,
827 SUPPLY_EQUAL_WEIGHTS,
828 EPETRA_CRSMATRIX);
829
830 CHECK_FAILED();
831
832 fail = run_test(testm,
833 verbose,
834 true, // make #partitions < #processes
835 false,
836 GRAPH_PARTITIONING,
837 SUPPLY_EQUAL_WEIGHTS,
838 SUPPLY_EQUAL_WEIGHTS,
839 EPETRA_CRSGRAPH);
840
841 CHECK_FAILED();
842
843 fail = run_test(testm,
844 verbose,
845 false, // make #partitions < #processes
846 true,
847 GRAPH_PARTITIONING,
848 SUPPLY_EQUAL_WEIGHTS,
849 SUPPLY_EQUAL_WEIGHTS,
850 EPETRA_CRSGRAPH);
851
852 CHECK_FAILED();
853
854 fail = run_test(testm,
855 verbose,
856 false,
857 false,
858 GRAPH_PARTITIONING,
859 NO_APPLICATION_SUPPLIED_WEIGHTS,
860 NO_APPLICATION_SUPPLIED_WEIGHTS,
861 EPETRA_CRSGRAPH);
862
863 CHECK_FAILED();
864
865 #endif
866
867 } // end if square
868
869 #ifdef HAVE_ISORROPIA_ZOLTAN
870
871 fail = run_test(testm,
872 verbose,
873 false,
874 false,
875 HYPERGRAPH_PARTITIONING,
876 SUPPLY_EQUAL_WEIGHTS,
877 SUPPLY_EQUAL_WEIGHTS,
878 EPETRA_CRSMATRIX);
879
880 CHECK_FAILED();
881
882 fail = run_test(testm,
883 verbose,
884 false,
885 false,
886 HYPERGRAPH_PARTITIONING,
887 SUPPLY_EQUAL_WEIGHTS,
888 SUPPLY_UNEQUAL_WEIGHTS,
889 EPETRA_CRSGRAPH);
890
891 CHECK_FAILED();
892
893 fail = run_test(testm,
894 verbose,
895 true, // make #partitions < #processes
896 false,
897 HYPERGRAPH_PARTITIONING,
898 SUPPLY_UNEQUAL_WEIGHTS,
899 SUPPLY_EQUAL_WEIGHTS,
900 EPETRA_CRSMATRIX);
901
902 CHECK_FAILED();
903
904 fail = run_test(testm,
905 verbose,
906 false, // make #partitions < #processes
907 true,
908 HYPERGRAPH_PARTITIONING,
909 SUPPLY_UNEQUAL_WEIGHTS,
910 SUPPLY_EQUAL_WEIGHTS,
911 EPETRA_CRSMATRIX);
912
913 CHECK_FAILED();
914
915 fail = run_test(testm,
916 verbose,
917 false,
918 false,
919 HYPERGRAPH_PARTITIONING,
920 NO_APPLICATION_SUPPLIED_WEIGHTS,
921 NO_APPLICATION_SUPPLIED_WEIGHTS,
922 EPETRA_CRSGRAPH);
923
924 CHECK_FAILED();
925
926 fail = run_test(testm,
927 verbose,
928 false,
929 false,
930 HYPERGRAPH_PARTITIONING,
931 NO_APPLICATION_SUPPLIED_WEIGHTS,
932 NO_APPLICATION_SUPPLIED_WEIGHTS,
933 EPETRA_CRSMATRIX);
934
935 CHECK_FAILED();
936 #endif
937
938 // Default row weight is number of non zeros in the row
939 #endif // SHORT_TEST
940
941 #else
942 fail = 0;
943 if (localProc == 0){
944 std::cout << "Test not run because it requires EPETRA_EXT" << std::endl;
945 }
946 #endif
947
948 Report:
949
950 #ifdef HAVE_MPI
951 MPI_Finalize();
952 #endif
953
954 if (localProc == 0){
955 if (failures){
956 if (failures > 1)
957 std::cout << std::endl << failures << " FAILURES" << std::endl;
958 else
959 std::cout << std::endl << "1 FAILURE" << std::endl;
960
961 if (!runAll){
962 std::cout <<
963 "(Use option --run-all if you do not want this test to abort on failure)" << std::endl;
964 }
965
966 }
967 else
968 std::cout << std::endl << "PASS" << std::endl;
969 }
970
971 return fail;
972 }