XdmfPartitioner.cpp 39.6 KB
Newer Older
Kenneth Leiter's avatar
Kenneth Leiter committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*****************************************************************************/
/*                                    XDMF                                   */
/*                       eXtensible Data Model and Format                    */
/*                                                                           */
/*  Id : XdmfPartitioner.cpp                                                 */
/*                                                                           */
/*  Author:                                                                  */
/*     Kenneth Leiter                                                        */
/*     kenneth.leiter@arl.army.mil                                           */
/*     US Army Research Laboratory                                           */
/*     Aberdeen Proving Ground, MD                                           */
/*                                                                           */
/*     Copyright @ 2011 US Army Research Laboratory                          */
/*     All Rights Reserved                                                   */
/*     See Copyright.txt for details                                         */
/*                                                                           */
/*     This software is distributed WITHOUT ANY WARRANTY; without            */
/*     even the implied warranty of MERCHANTABILITY or FITNESS               */
/*     FOR A PARTICULAR PURPOSE.  See the above copyright notice             */
/*     for more information.                                                 */
/*                                                                           */
/*****************************************************************************/

24
25
26
27
#ifndef BUILD_EXE

extern "C"
{
28
#include <metis.h>
29
30
}

31
#include <iostream>
32
#include <sstream>
33
#include "XdmfAttribute.hpp"
34
35
#include "XdmfAttributeCenter.hpp"
#include "XdmfAttributeType.hpp"
36
#include "XdmfError.hpp"
37
#include "XdmfGeometry.hpp"
38
#include "XdmfGeometryType.hpp"
Kenneth Leiter's avatar
Kenneth Leiter committed
39
#include "XdmfGraph.hpp"
40
#include "XdmfGridCollection.hpp"
41
#include "XdmfGridCollectionType.hpp"
42
#include "XdmfHeavyDataWriter.hpp"
43
#include "XdmfMap.hpp"
44
#include "XdmfPartitioner.hpp"
45
#include "XdmfSet.hpp"
46
#include "XdmfSetType.hpp"
47
#include "XdmfTopology.hpp"
48
#include "XdmfTopologyType.hpp"
49
#include "XdmfUnstructuredGrid.hpp"
50

Kenneth Leiter's avatar
Kenneth Leiter committed
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//
// local methods
//
namespace {

  shared_ptr<XdmfGraph>
  addSymmetricEntries(const shared_ptr<XdmfGraph> graph)
  {
    const shared_ptr<XdmfArray> rowPointer = graph->getRowPointer();
    const shared_ptr<XdmfArray> columnIndex = graph->getColumnIndex();
    const unsigned int numberRows = graph->getNumberRows();

    std::set<std::pair<unsigned int, unsigned int> > entrySet;
    for(unsigned int i=0; i<numberRows; ++i) {
      for(unsigned int j=rowPointer->getValue<unsigned int>(i);
          j<rowPointer->getValue<unsigned int>(i+1);
          ++j) {
        const unsigned int k = columnIndex->getValue<unsigned int>(j);
        entrySet.insert(std::make_pair(i, k));
        entrySet.insert(std::make_pair(k, i));
      }
    }

    shared_ptr<XdmfGraph> toReturn = XdmfGraph::New(numberRows);
    shared_ptr<XdmfArray> toReturnRowPointer = toReturn->getRowPointer();
    shared_ptr<XdmfArray> toReturnColumnIndex = toReturn->getColumnIndex();
    shared_ptr<XdmfArray> toReturnValues = toReturn->getValues();

    unsigned int currentRow = 1;
    for(std::set<std::pair<unsigned int, unsigned int> >::const_iterator
          iter = entrySet.begin();
        iter != entrySet.end();
        ++iter) {
      const std::pair<unsigned int, unsigned int> & entry = *iter;
      const unsigned int row = entry.first;
      const unsigned int column = entry.second;
      for(unsigned int j = currentRow; j<row; ++j) {
        toReturnRowPointer->insert<unsigned int>(j,
                                                 toReturnColumnIndex->getSize());
      }

      currentRow = row + 1;
      toReturnColumnIndex->pushBack<unsigned int>(column);
      toReturnValues->pushBack<double>(1.0);
      toReturnRowPointer->insert(row+1,
                                 toReturnColumnIndex->getSize());
    }

    return toReturn;

  }

}

105
shared_ptr<XdmfPartitioner>
106
XdmfPartitioner::New()
107
{
108
  shared_ptr<XdmfPartitioner> p(new XdmfPartitioner());
109
  return p;
110
111
}

112
113
114
115
116
117
118
119
XdmfPartitioner::XdmfPartitioner()
{
}

XdmfPartitioner::~XdmfPartitioner()
{
}

120
121
void
XdmfPartitioner::ignore(const shared_ptr<const XdmfSet> set)
122
123
124
125
{
  mIgnoredSets.insert(set);
}

Kenneth Leiter's avatar
Kenneth Leiter committed
126
127
128
129
130
131
132
133
134
135
136
void
XdmfPartitioner::partition(const shared_ptr<XdmfGraph> graphToPartition,
                           const unsigned int numberOfPartitions) const
{

  // Make sure row pointer and column index are non null
  if(!(graphToPartition->getRowPointer() &&
       graphToPartition->getColumnIndex()))
    XdmfError::message(XdmfError::FATAL,
                       "Current graph's row pointer or column index is null "
                       "in XdmfPartitioner::partition");
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
  graphToPartition->removeAttribute("Partition");

  shared_ptr<XdmfAttribute> attribute = XdmfAttribute::New();
  attribute->setName("Partition");
  attribute->setCenter(XdmfAttributeCenter::Node());
  attribute->setType(XdmfAttributeType::Scalar());
  graphToPartition->insert(attribute);

  idx_t numberVertices = graphToPartition->getNumberNodes();
  
  // Handle case where we partition onto 1 processor. Metis for some reason
  // handles this incorrectly (indices are 1 instead of zero even though 
  // correct numbering option is supplied to metis)
  if(numberOfPartitions == 1) {
    attribute->resize<idx_t>(numberVertices, 0);
    return;
  }
Kenneth Leiter's avatar
Kenneth Leiter committed
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268

  shared_ptr<XdmfArray> rowPointer = graphToPartition->getRowPointer();
  shared_ptr<XdmfArray> columnIndex = graphToPartition->getColumnIndex();

  idx_t numberConstraints = 1;

  bool releaseRowPointer = false;
  if(!rowPointer->isInitialized()) {
    rowPointer->read();
    releaseRowPointer = true;
  }
  bool releaseColumnIndex = false;
  if(!columnIndex->isInitialized()) {
    columnIndex->read();
    releaseColumnIndex = true;
  }

  shared_ptr<XdmfGraph> graph = graphToPartition;

  // Check whether graph is directed, if so we need to make it undirected
  // in order to partition with metis. From metis FAQ:
  //
  // The partitioning routines in METIS can only partition undirected graphs
  // (i.e., graphs in which for each edge (v,u) there is also an edge (u,v)).
  // For partitioning purposes, the directionality of an edge does not play
  // any role because if edge (u,v) is cut so will the edge (v,u). For this
  // reason, a directed graph can be easily partitioned by METIS by first
  // converting it into the corresponding undirected graph. That is, create
  // a graph for each directed edge (u,v) also contains the (v,u) edge as
  // well.
  const unsigned int numberRows = graphToPartition->getNumberRows();
  for(unsigned int i=0; i<numberRows; ++i) {
    for(unsigned int j=rowPointer->getValue<unsigned int>(i);
        j<rowPointer->getValue<unsigned int>(i+1);
        ++j) {
      const unsigned int k = columnIndex->getValue<unsigned int>(j);
      bool symmetric = false;
      for(unsigned int l=rowPointer->getValue<unsigned int>(k);
          l<rowPointer->getValue<unsigned int>(k+1);
          ++l) {
        const unsigned int m = columnIndex->getValue<unsigned int>(l);
        if(i == m) {
          symmetric = true;
          break;
        }
      }
      if(!symmetric) {
        graph = addSymmetricEntries(graphToPartition);
        if(releaseRowPointer) {
          rowPointer->release();
        }
        if(releaseColumnIndex) {
          columnIndex->release();
        }
        rowPointer = graph->getRowPointer();
        columnIndex = graph->getColumnIndex();
        break;
      }
    }
  }

  // copy into metis data structures
  idx_t * xadj = new idx_t[rowPointer->getSize()];
  rowPointer->getValues(0,
                        xadj,
                        rowPointer->getSize());
  if(releaseRowPointer) {
    rowPointer->release();
  }
  idx_t * adjncy = new idx_t[columnIndex->getSize()];
  columnIndex->getValues(0,
                         adjncy,
                         columnIndex->getSize());
  if(releaseColumnIndex) {
    columnIndex->release();
  }

  idx_t * vwgt = NULL; // equal vertex weights
  idx_t * vsize = NULL; // equal vertex sizes
  idx_t * adjwgt = NULL; // equal edge weights
  idx_t numParts = numberOfPartitions;
  real_t * tpwgts = NULL; // equal constraints and partition weights
  real_t * ubvec = NULL; // default load imbalance tolerance
  idx_t * options = NULL; // default options
  idx_t objval;
  idx_t * part = new idx_t[numberVertices];

  METIS_PartGraphRecursive(&numberVertices,
                           &numberConstraints,
                           xadj,
                           adjncy,
                           vwgt,
                           vsize,
                           adjwgt,
                           &numParts,
                           tpwgts,
                           ubvec,
                           options,
                           &objval,
                           part);

  delete [] xadj;
  delete [] adjncy;

  attribute->insert(0,
                    part,
                    numberVertices);

  delete [] part;

  return;
}


269
270
shared_ptr<XdmfGridCollection>
XdmfPartitioner::partition(const shared_ptr<XdmfUnstructuredGrid> gridToPartition,
271
                           const unsigned int numberOfPartitions,
272
                           const MetisScheme metisScheme,
273
                           const shared_ptr<XdmfHeavyDataWriter> heavyDataWriter) const
274
{
275
276
277
278
279

  if(heavyDataWriter) {
    heavyDataWriter->openFile();
  }

280
  // Make sure geometry and topology are non null
281
  if(!(gridToPartition->getGeometry() && gridToPartition->getTopology()))
282
    XdmfError::message(XdmfError::FATAL,
283
284
                       "Current grid's geometry or topology is null in "
                       "XdmfPartitioner::partition");
285

286
  const shared_ptr<XdmfGeometry> geometry =
287
    gridToPartition->getGeometry();
288
  const shared_ptr<const XdmfGeometryType> geometryType =
289
    geometry->getType();
290
  const shared_ptr<XdmfTopology> topology =
291
    gridToPartition->getTopology();
292
  const shared_ptr<const XdmfTopologyType> topologyType =
293
294
    topology->getType();

295
  const unsigned int nodesPerElement = topologyType->getNodesPerElement();
296
297
298
299
300
301
302

  bool releaseTopology = false;
  if(!topology->isInitialized()) {
    topology->read();
    releaseTopology = true;
  }

Kenneth Leiter's avatar
Kenneth Leiter committed
303
304
  idx_t numElements = topology->getNumberElements();
  idx_t numNodes = geometry->getNumberPoints();
305

306
307
308
  // allocate metisConnectivity arrays
  idx_t * metisConnectivityEptr = new idx_t[numElements + 1];
  idx_t * metisConnectivityEind = new idx_t[nodesPerElement * numElements];
309

310
311
312
  metisConnectivityEptr[0] = 0;

  unsigned int metisConnectivityEptrValue = 0;
313
  unsigned int connectivityOffset = 0;
314
  idx_t * metisConnectivityPtr = metisConnectivityEind;
315
  for(int i=0; i<numElements; ++i) {
316
317
    metisConnectivityEptrValue += nodesPerElement;
    metisConnectivityEptr[i + 1] = metisConnectivityEptrValue;
318
319
320
321
322
323
324
    topology->getValues(connectivityOffset,
                        metisConnectivityPtr,
                        nodesPerElement);
    connectivityOffset += topologyType->getNodesPerElement();
    metisConnectivityPtr += nodesPerElement;
  }

325
326
327
328
329
330
331
332
333
334
  idx_t * vwgt = NULL; // equal weight
  idx_t * vsize = NULL; // equal size
  idx_t ncommon = 1; // FIXME
  idx_t nparts = numberOfPartitions;
  real_t * tpwgts = NULL;
  idx_t * options = NULL;
  idx_t objval;

  idx_t * elementsPartition = new idx_t[numElements];
  idx_t * nodesPartition = new idx_t[numNodes];
335

336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
  if(metisScheme == DUAL_GRAPH) {
    METIS_PartMeshDual(&numElements,
                       &numNodes,
                       metisConnectivityEptr,
                       metisConnectivityEind,
                       vwgt,
                       vsize,
                       &ncommon,
                       &nparts,
                       tpwgts,
                       options,
                       &objval,
                       elementsPartition,
                       nodesPartition);
  }
  else if(metisScheme == NODAL_GRAPH) {
    METIS_PartMeshNodal(&numElements,
                        &numNodes,
                        metisConnectivityEptr,
                        metisConnectivityEind,
                        vwgt,
                        vsize,
                        &nparts,
                        tpwgts,
                        options,
                        &objval,
                        elementsPartition,
                        nodesPartition);
  }
  else {
366
    XdmfError::message(XdmfError::FATAL,
367
                       "Invalid metis partitioning scheme selected in "
368
                       "XdmfPartitioner::partition");
369

370
  }
371

372
373
  delete [] metisConnectivityEptr;
  delete [] metisConnectivityEind;
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
  delete [] nodesPartition;

  // For each partition, map global to local node id
  std::vector<std::map<unsigned int, unsigned int> > globalToLocalNodeIdMap;
  // For each partition, list global element id.
  std::vector<std::vector<unsigned int> > globalElementIds;
  for(unsigned int i=0; i<numberOfPartitions; ++i) {
    std::map<unsigned int, unsigned int> nodeMap;
    globalToLocalNodeIdMap.push_back(nodeMap);
    std::vector<unsigned int> elementIds;
    globalElementIds.push_back(elementIds);
  }

  // Fill in globalNodeId for each partition
  unsigned int totalIndex = 0;
  for (int i=0; i<numElements; ++i) {
    unsigned int partitionId = elementsPartition[i];
    for (unsigned int j=0; j<topologyType->getNodesPerElement(); ++j) {
      unsigned int globalNodeId = topology->getValue<unsigned int>(totalIndex);
      if (globalToLocalNodeIdMap[partitionId].count(globalNodeId) == 0) {
        // Have not seen this node, need to add to map
        unsigned int size = globalToLocalNodeIdMap[partitionId].size();
        globalToLocalNodeIdMap[partitionId][globalNodeId] = size;
      }
      totalIndex++;
    }
    globalElementIds[partitionId].push_back(i);
  }
  delete [] elementsPartition;

  bool generateGlobalNodeIds = !gridToPartition->getAttribute("GlobalNodeId");

406
  shared_ptr<XdmfGridCollection> partitionedGrids =
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
    XdmfGridCollection::New();
  partitionedGrids->setType(XdmfGridCollectionType::Spatial());

  bool releaseGeometry = false;
  if(!geometry->isInitialized()) {
    geometry->read();
    releaseGeometry = true;
  }

  // Split geometry and topology into proper partitions
  for(unsigned int i=0; i<numberOfPartitions; ++i) {
    std::map<unsigned int, unsigned int> & currNodeMap =
      globalToLocalNodeIdMap[i];
    std::vector<unsigned int> & currElemIds = globalElementIds[i];

    if(currElemIds.size() > 0) {
      std::stringstream name;
      name << gridToPartition->getName() << "_" << i;

426
      const shared_ptr<XdmfUnstructuredGrid> partitioned =
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
        XdmfUnstructuredGrid::New();
      partitioned->setName(name.str());
      partitionedGrids->insert(partitioned);

      // Fill in geometry for this partition
      partitioned->getGeometry()->setType(geometryType);
      unsigned int numDimensions = geometryType->getDimensions();
      partitioned->getGeometry()->initialize(geometry->getArrayType(),
                                             currNodeMap.size() * numDimensions);

      for(std::map<unsigned int, unsigned int>::const_iterator iter =
            currNodeMap.begin();
          iter != currNodeMap.end();
          ++iter) {
        partitioned->getGeometry()->insert(iter->second * numDimensions,
                                           geometry,
                                           iter->first * numDimensions,
                                           numDimensions);
      }

      if(heavyDataWriter) {
        partitioned->getGeometry()->accept(heavyDataWriter);
        partitioned->getGeometry()->release();
      }

      // Fill in topology for this partition
      partitioned->getTopology()->setType(topologyType);
      partitioned->getTopology()->initialize(topology->getArrayType(),
                                             currElemIds.size() * topologyType->getNodesPerElement());
      unsigned int index = 0;
      for(std::vector<unsigned int>::const_iterator iter = currElemIds.begin();
          iter != currElemIds.end();
          ++iter) {
        // Translate these global node ids to local node ids
        for(unsigned int j=0; j<topologyType->getNodesPerElement(); ++j) {
          unsigned int globalNodeId =
            currNodeMap[topology->getValue<unsigned int>(*iter * topologyType->getNodesPerElement() + j)];
          partitioned->getTopology()->insert(index, &globalNodeId, 1);
          index++;
        }
      }

      if(heavyDataWriter) {
        partitioned->getTopology()->accept(heavyDataWriter);
        partitioned->getTopology()->release();
      }

      if (generateGlobalNodeIds) {
475
        shared_ptr<XdmfAttribute> globalNodeIds = XdmfAttribute::New();
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
        globalNodeIds->setName("GlobalNodeId");
        globalNodeIds->setType(XdmfAttributeType::GlobalId());
        globalNodeIds->setCenter(XdmfAttributeCenter::Node());
        globalNodeIds->initialize<unsigned int>(currNodeMap.size());
        for(std::map<unsigned int, unsigned int>::const_iterator iter =
              currNodeMap.begin();
            iter != currNodeMap.end();
            ++iter) {
          globalNodeIds->insert(iter->second, &iter->first, 1);
        }
        partitioned->insert(globalNodeIds);

        if(heavyDataWriter) {
          globalNodeIds->accept(heavyDataWriter);
          globalNodeIds->release();
        }
      }
    }
  }

  if(releaseGeometry) {
    gridToPartition->getGeometry()->release();
  }
  if(releaseTopology) {
    gridToPartition->getTopology()->release();
  }

  // Split attributes into proper partitions
  for(unsigned int i=0; i<gridToPartition->getNumberAttributes(); ++i) {
505

506
    const shared_ptr<XdmfAttribute> currAttribute =
507
508
509
510
511
512
513
514
515
516
517
518
      gridToPartition->getAttribute(i);
    bool releaseAttribute = false;
    if(!currAttribute->isInitialized()) {
      currAttribute->read();
      releaseAttribute = true;
    }
    unsigned int partitionId = 0;
    for(unsigned int j=0; j<numberOfPartitions; ++j) {
      std::map<unsigned int, unsigned int> & currNodeMap =
        globalToLocalNodeIdMap[j];
      std::vector<unsigned int> & currElemIds = globalElementIds[j];
      if(currElemIds.size() > 0) {
519
        const shared_ptr<XdmfUnstructuredGrid> partitioned =
520
521
          partitionedGrids->getUnstructuredGrid(partitionId);
        partitionId++;
522
        shared_ptr<XdmfAttribute> createdAttribute =
523
          shared_ptr<XdmfAttribute>();
524
525
526
527
        if(currAttribute->getCenter() == XdmfAttributeCenter::Grid()) {
          // Insert into each partition
          createdAttribute = currAttribute;
        }
528
        else if(currAttribute->getCenter() == XdmfAttributeCenter::Cell()) {
529
530
531
532
533
          createdAttribute = XdmfAttribute::New();
          createdAttribute->setName(currAttribute->getName());
          createdAttribute->setCenter(currAttribute->getCenter());
          createdAttribute->setType(currAttribute->getType());
          unsigned int index = 0;
534
          const unsigned int numberComponents =
Kenneth Leiter's avatar
Kenneth Leiter committed
535
            currAttribute->getSize() / topology->getNumberElements();
536
          createdAttribute->initialize(currAttribute->getArrayType(),
537
                                       currElemIds.size() * numberComponents);
538
539
540
541
542
543
          for(std::vector<unsigned int>::const_iterator iter =
                currElemIds.begin();
              iter != currElemIds.end();
              ++iter) {
            createdAttribute->insert(index,
                                     currAttribute,
544
545
546
                                     *iter * numberComponents,
                                     numberComponents);
            index += numberComponents;
547
548
549
550
551
552
553
          }
        }
        else if(currAttribute->getCenter() == XdmfAttributeCenter::Node()) {
          createdAttribute = XdmfAttribute::New();
          createdAttribute->setName(currAttribute->getName());
          createdAttribute->setCenter(currAttribute->getCenter());
          createdAttribute->setType(currAttribute->getType());
554
          createdAttribute->initialize(currAttribute->getArrayType(),
Kenneth Leiter's avatar
Kenneth Leiter committed
555
556
557
                                       currNodeMap.size());
          const unsigned int numberComponents =
            currAttribute->getSize() / geometry->getNumberPoints();
558
559
560
561
          for(std::map<unsigned int, unsigned int>::const_iterator iter =
                currNodeMap.begin();
              iter != currNodeMap.end();
              ++iter) {
562
            createdAttribute->insert(iter->second * numberComponents,
563
                                     currAttribute,
564
565
                                     iter->first * numberComponents,
                                     numberComponents);
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
          }
        }
        if(createdAttribute) {
          partitioned->insert(createdAttribute);
          if(heavyDataWriter) {
            if(!createdAttribute->isInitialized()) {
              createdAttribute->read();
            }
            createdAttribute->accept(heavyDataWriter);
            createdAttribute->release();
          }
        }
      }
    }
    if(releaseAttribute) {
      currAttribute->release();
    }
  }

  // Split sets into proper partitions
  for(unsigned int i=0; i<gridToPartition->getNumberSets(); ++i) {
587
    shared_ptr<XdmfSet> currSet = gridToPartition->getSet(i);
588
589
590
591
592
593
594
595
    if(mIgnoredSets.find(currSet) == mIgnoredSets.end()) {
      bool releaseSet = false;
      if(!currSet->isInitialized()) {
        currSet->read();
        releaseSet = true;
      }
      unsigned int partitionId = 0;
      for(unsigned int j=0; j<numberOfPartitions; ++j) {
596
        const std::map<unsigned int, unsigned int> & currNodeMap =
597
          globalToLocalNodeIdMap[j];
598
        const std::vector<unsigned int> & currElemIds = globalElementIds[j];
599
        if(currElemIds.size() > 0) {
600
          shared_ptr<XdmfUnstructuredGrid> partitioned =
601
602
            partitionedGrids->getUnstructuredGrid(partitionId);
          partitionId++;
603
604

          shared_ptr<XdmfSet> partitionedSet = XdmfSet::New();
605
          std::vector<unsigned int> partitionedSetIndex;
606

607
          if(currSet->getType() == XdmfSetType::Cell()) {
608
609
610
611
612
613
614
615
616
617
            for(unsigned int k=0; k<currSet->getSize(); ++k) {
              std::vector<unsigned int>::const_iterator val =
                std::find(currElemIds.begin(),
                          currElemIds.end(),
                          currSet->getValue<unsigned int>(k));
              if(val != currElemIds.end()) {
                unsigned int valToPush = val - currElemIds.begin();
                partitionedSet->pushBack(valToPush);
                partitionedSetIndex.push_back(k);
              }
618
619
            }
          }
620
621
622
623
624
625
626
627
          else if(currSet->getType() == XdmfSetType::Node()) {
            for(unsigned int k=0; k<currSet->getSize(); ++k) {
              std::map<unsigned int, unsigned int>::const_iterator val =
                currNodeMap.find(currSet->getValue<unsigned int>(k));
              if(val != currNodeMap.end()) {
                partitionedSet->pushBack(val->second);
                partitionedSetIndex.push_back(k);
              }
628
629
            }
          }
630

631
          // Only insert set if contains values
632
633
634
          if(partitionedSet->getSize() > 0) {

            for(unsigned int k=0; k<currSet->getNumberAttributes(); ++k) {
635
              const shared_ptr<XdmfAttribute> currAttribute =
636
                currSet->getAttribute(k);
637
638
639
640
641
642
643
              bool releaseAttribute = false;
              if(!currAttribute->isInitialized()) {
                currAttribute->read();
                releaseAttribute = true;
              }
              if(currAttribute->getCenter() == XdmfAttributeCenter::Node() ||
                 currAttribute->getCenter() == XdmfAttributeCenter::Cell()) {
644
                const unsigned int numberComponents =
645
                  currAttribute->getSize() / currSet->getSize();
646

647
                const shared_ptr<XdmfAttribute> partitionedAttribute =
648
649
650
651
652
                  XdmfAttribute::New();
                partitionedAttribute->setCenter(currAttribute->getCenter());
                partitionedAttribute->setName(currAttribute->getName());
                partitionedAttribute->setType(currAttribute->getType());
                partitionedAttribute->initialize(currAttribute->getArrayType(),
653
                                                 partitionedSetIndex.size() * numberComponents);
654
                for(unsigned int l=0; l<partitionedSetIndex.size(); ++l) {
655
                  partitionedAttribute->insert(l * numberComponents,
656
                                               currAttribute,
657
658
                                               partitionedSetIndex[l] * numberComponents,
                                               numberComponents);
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
                }
                partitionedSet->insert(partitionedAttribute);
                if(heavyDataWriter) {
                  partitionedAttribute->accept(heavyDataWriter);
                  partitionedAttribute->release();
                }
              }
            }
            partitioned->insert(partitionedSet);
            partitionedSet->setName(currSet->getName());
            partitionedSet->setType(currSet->getType());
            if(heavyDataWriter) {
              partitionedSet->accept(heavyDataWriter);
              partitionedSet->release();
            }
674
675
676
          }
        }
      }
677
678
679
      if(releaseSet) {
        currSet->release();
      }
680
681
682
683
    }
  }

  // Add XdmfMap to map boundary nodes between partitions
684
  std::vector<shared_ptr<XdmfAttribute> > globalNodeIds;
685
686
687
  for(unsigned int i=0;
      i<partitionedGrids->getNumberUnstructuredGrids();
      ++i) {
688
    shared_ptr<XdmfAttribute> globalNodeId =
689
      partitionedGrids->getUnstructuredGrid(i)->getAttribute("GlobalNodeId");
690
691
692
693
    if(!globalNodeId->isInitialized()) {
      globalNodeId->read();
    }
    globalNodeIds.push_back(globalNodeId);
694
695
  }

696
  std::vector<shared_ptr<XdmfMap> > maps = XdmfMap::New(globalNodeIds);
697
698
699
  for(unsigned int i=0;
      i<partitionedGrids->getNumberUnstructuredGrids();
      ++i) {
700
    shared_ptr<XdmfMap> map = maps[i];
701
702
    map->setName("Subdomain Boundary");
    partitionedGrids->getUnstructuredGrid(i)->insert(map);
703
704
705
706
707
708
709
710
    if(heavyDataWriter) {
      globalNodeIds[i]->release();
      map->accept(heavyDataWriter);
      map->release();
    }
  }

  return partitionedGrids;
711
712
}

713
714
715
716
shared_ptr<XdmfUnstructuredGrid>
XdmfPartitioner::unpartition(const shared_ptr<XdmfGridCollection> gridToUnPartition) const
{

717
  const shared_ptr<XdmfUnstructuredGrid> returnValue =
718
    XdmfUnstructuredGrid::New();
719
  const shared_ptr<XdmfTopology> returnValueTopology =
720
721
722
723
    returnValue->getTopology();
  const shared_ptr<XdmfGeometry> returnValueGeometry =
    returnValue->getGeometry();

724
  const unsigned int numberUnstructuredGrids =
725
    gridToUnPartition->getNumberUnstructuredGrids();
726

727
728
729
730
  unsigned int elementOffset = 0;

  for(unsigned int i=0; i<numberUnstructuredGrids; ++i) {

731
    const shared_ptr<XdmfUnstructuredGrid> grid =
732
733
      gridToUnPartition->getUnstructuredGrid(i);

734
    const shared_ptr<XdmfAttribute> globalNodeIds =
735
736
737
      grid->getAttribute("GlobalNodeId");

    if(!globalNodeIds) {
738
      XdmfError::message(XdmfError::FATAL,
739
740
741
742
743
744
745
746
747
748
749
750
                         "Cannot find GlobalNodeId attribute in "
                         "XdmfPartitioner::unpartition");
    }

    bool releaseGlobalNodeIds = false;
    if(!globalNodeIds->isInitialized()) {
      globalNodeIds->read();
      releaseGlobalNodeIds = true;
    }

    // handle topology
    const shared_ptr<XdmfTopology> topology = grid->getTopology();
751

752
753
754
755
756
    if(i==0) {
      returnValueTopology->setType(topology->getType());
      returnValueTopology->initialize(topology->getArrayType());
    }

757
    returnValueTopology->reserve(returnValueTopology->getSize() +
758
759
760
761
762
763
764
765
766
767
                                 topology->getSize());

    bool releaseTopology = false;
    if(!topology->isInitialized()) {
      topology->read();
      releaseTopology = true;
    }

    for(unsigned int j=0; j<topology->getSize(); ++j) {
      const unsigned int localNodeId = topology->getValue<unsigned int>(j);
768
      const unsigned int globalNodeId =
769
770
771
772
773
774
775
        globalNodeIds->getValue<unsigned int>(localNodeId);
      returnValueTopology->pushBack(globalNodeId);
    }

    if(releaseTopology) {
      topology->release();
    }
776

777
778
    // handle geometry
    const shared_ptr<XdmfGeometry> geometry = grid->getGeometry();
779
    const shared_ptr<const XdmfGeometryType> geometryType =
780
781
      geometry->getType();
    const unsigned int geometryDimension = geometryType->getDimensions();
782

783
784
785
786
787
788
789
790
791
792
793
794
    if(i==0) {
      returnValueGeometry->setType(geometryType);
      returnValueGeometry->initialize(geometry->getArrayType());
    }

    bool releaseGeometry = false;
    if(!geometry->isInitialized()) {
      geometry->read();
      releaseGeometry = true;
    }

    for(unsigned int j=0; j<globalNodeIds->getSize(); ++j) {
795
      const unsigned int globalNodeId =
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
        globalNodeIds->getValue<unsigned int>(j);
      returnValueGeometry->insert(globalNodeId * geometryDimension,
                                  geometry,
                                  j * geometryDimension,
                                  geometryDimension);
    }

    if(releaseGeometry) {
      geometry->release();
    }

    // handle attributes
    for(unsigned int j=0; j<grid->getNumberAttributes(); ++j) {

      const shared_ptr<XdmfAttribute> attribute = grid->getAttribute(j);
811
      const shared_ptr<const XdmfAttributeCenter> attributeCenter =
812
        attribute->getCenter();
813

814
815
816
817
818
819
820
      bool releaseAttribute = false;
      if(!attribute->isInitialized()) {
        attribute->read();
        releaseAttribute = true;
      }

      shared_ptr<XdmfAttribute> returnValueAttribute;
821

822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
      if(i==0) {
        returnValueAttribute = XdmfAttribute::New();
        returnValueAttribute->setName(attribute->getName());
        returnValueAttribute->setCenter(attributeCenter);
        returnValueAttribute->setType(attribute->getType());
        returnValueAttribute->initialize(attribute->getArrayType());
        returnValue->insert(returnValueAttribute);
      }
      else {
        returnValueAttribute = returnValue->getAttribute(attribute->getName());
      }


      if(attributeCenter == XdmfAttributeCenter::Grid()) {
        returnValueAttribute->insert(0,
                                     attribute,
                                     0,
839
                                     attribute->getSize());
840
841
842
843
844
845
846
847
      }
      else if(attributeCenter == XdmfAttributeCenter::Cell()) {
        returnValueAttribute->insert(returnValueAttribute->getSize(),
                                     attribute,
                                     0,
                                     attribute->getSize());
      }
      else if(attributeCenter == XdmfAttributeCenter::Node()) {
848
849

        const unsigned int numberComponents =
850
          attribute->getSize() / geometry->getNumberPoints();
851

852
        for(unsigned int k=0; k<globalNodeIds->getSize(); ++k) {
853
          const unsigned int globalNodeId =
854
855
856
857
858
859
            globalNodeIds->getValue<unsigned int>(k);
          returnValueAttribute->insert(globalNodeId * numberComponents,
                                       attribute,
                                       k * numberComponents,
                                       numberComponents);
        }
860

861
      }
862

863
864
865
866
867
868
869
870
871
872
873
      if(releaseAttribute) {
        attribute->release();
      }

    }

    // handle sets
    for(unsigned int j=0; j<grid->getNumberSets(); ++j) {

      const shared_ptr<XdmfSet> set = grid->getSet(j);
      const shared_ptr<const XdmfSetType> setType = set->getType();
874

875
876
877
878
879
880
881
882
883
884
885
886
887
      bool releaseSet = false;
      if(!set->isInitialized()) {
        set->read();
        releaseSet = true;
      }

      shared_ptr<XdmfSet> returnValueSet = returnValue->getSet(set->getName());
      if(!returnValueSet) {
        returnValueSet = XdmfSet::New();
        returnValueSet->setName(set->getName());
        returnValueSet->setType(setType);
        returnValue->insert(returnValueSet);
      }
888

889
890
891
892
893
894
895
896
897
      if(setType == XdmfSetType::Cell()) {
        for(unsigned int k=0; k<set->getSize(); ++k) {
          const unsigned int localCellId = set->getValue<unsigned int>(k);
          returnValueSet->pushBack(localCellId + elementOffset);
        }
      }
      else if(setType == XdmfSetType::Node()) {
        for(unsigned int k=0; k<set->getSize(); ++k){
          const unsigned int localNodeId = set->getValue<unsigned int>(k);
898
          const unsigned int globalNodeId =
899
900
901
902
903
904
905
            globalNodeIds->getValue<unsigned int>(localNodeId);
          returnValueSet->pushBack(globalNodeId);
        }
      }

      for(unsigned int k=0; k<set->getNumberAttributes(); ++k) {
        const shared_ptr<XdmfAttribute> attribute = set->getAttribute(k);
906
        const shared_ptr<const XdmfAttributeCenter> attributeCenter =
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
          attribute->getCenter();
        const shared_ptr<const XdmfAttributeType> attributeType =
          attribute->getType();

        shared_ptr<XdmfAttribute> returnValueAttribute =
          returnValueSet->getAttribute(attribute->getName());
        if(!returnValueAttribute) {
          returnValueAttribute = XdmfAttribute::New();
          returnValueAttribute->setName(attribute->getName());
          returnValueAttribute->setCenter(attributeCenter);
          returnValueAttribute->setType(attributeType);
          returnValueSet->insert(returnValueAttribute);
        }

        if(attributeCenter == XdmfAttributeCenter::Cell() ||
           attributeCenter == XdmfAttributeCenter::Node()) {
          returnValueAttribute->insert(returnValueAttribute->getSize(),
                                       attribute,
                                       0,
                                       attribute->getSize());
        }
928

929
      }
930

931
    }
932

933
934
935
936
937
    elementOffset += topology->getNumberElements();

    if(releaseGlobalNodeIds) {
      globalNodeIds->release();
    }
938

939
940
941
942
943
944
  }

  return returnValue;

}

945
946
#else

947
#include <cstdio>
948
#include <iostream>
949
950
#include <sstream>
#include "XdmfDomain.hpp"
Kenneth Leiter's avatar
Kenneth Leiter committed
951
#include "XdmfGraph.hpp"
952
953
#include "XdmfGridCollection.hpp"
#include "XdmfHDF5Writer.hpp"
954
#include "XdmfPartitioner.hpp"
955
956
#include "XdmfReader.hpp"
#include "XdmfWriter.hpp"
957

958
959
960
961
962
963
964
965
966
967
namespace {

  //
  // print usage
  //
  inline void
  printUsage(const char * programName)
  {

    std::cerr << "usage: " << programName << " "
968
              << "[-s metis_scheme] [-r] [-u]"
969
970
              << "<input file> <number of partitions> [output file]"
              << std::endl;
971
972
973
974
    std::cerr << "\t-s metis_scheme: 1 - Dual Graph" << std::endl;
    std::cerr << "\t-s metis_scheme: 2 - Node Graph" << std::endl;
    std::cerr << "\t-u unpartition file" << std::endl;

975
976
977
978
979
980
981
982
983
984
985
986
987
    //
    //
    //
    return;

  }

  //
  // process command line
  //
  void
  processCommandLine(std::string                  & inputFileName,
                     std::string                  & outputFileName,
Kenneth Leiter's avatar
Kenneth Leiter committed
988
                     unsigned int                 & numPartitions,
989
                     XdmfPartitioner::MetisScheme & metisScheme,
990
                     bool                         & unpartition,
Kenneth Leiter's avatar
Kenneth Leiter committed
991
                     int                            ac,
992
993
994
995
996
                     char                         * av[])
  {

    int c;
    bool errorFlag = false;
997

998
    while( (c=getopt(ac, av, "s:ur")) != -1 )
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
    switch(c){

    case 's': {
      const int value = std::atoi(optarg);
      if(value == 1) {
        metisScheme = XdmfPartitioner::DUAL_GRAPH;
      }
      else if(value == 2) {
        metisScheme = XdmfPartitioner::NODAL_GRAPH;
      }
      else {
        errorFlag = true;
      }
      break;
    }
1014
1015
1016
    case 'u':
      unpartition = true;
      break;
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
    case '?':
      errorFlag = true;
      break;
    }

    if (optind >= ac)
      errorFlag = true;
    else {
      inputFileName = av[optind];
      ++optind;
    }

1029
1030
1031
1032
1033
1034
1035
    if(!unpartition) {
      if (optind >= ac)
        errorFlag = true;
      else {
        numPartitions = atoi(av[optind]);
        ++optind;
      }
1036
1037
1038
1039
1040
1041
    }

    if (optind < ac) {
      outputFileName = av[optind];
      ++optind;
    }
1042

1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
    //
    // check errorFlag
    //
    if (errorFlag == true) {
      printUsage(av[0]);
      std::exit(EXIT_FAILURE);
    }

  }

}

1055
1056
/**
 * XdmfPartitioner is a command line utility for partitioning Xdmf grids.
1057
1058
 * The XdmfPartitioner uses the metis library to partition Triangular,
 * Quadrilateral, Tetrahedral, and Hexahedral XdmfGridUnstructureds.
1059
1060
 *
 * Usage:
1061
1062
 *     XdmfPartitioner <path-of-file-to-partition> <num-partitions>
 *                     (Optional: <path-to-output-file>)
1063
1064
 *
 */
1065
int main(int argc, char* argv[])
1066
{
1067

1068
  std::string inputFileName = "";
1069
  std::string outputFileName = "";
1070
  unsigned int numPartitions = 0;
1071
  XdmfPartitioner::MetisScheme metisScheme = XdmfPartitioner::DUAL_GRAPH;
1072
  bool unpartition = false;
1073
1074

  processCommandLine(inputFileName,
Kenneth Leiter's avatar
Kenneth Leiter committed
1075
1076
1077
                     outputFileName,
                     numPartitions,
                     metisScheme,
1078
                     unpartition,
Kenneth Leiter's avatar
Kenneth Leiter committed
1079
1080
                     argc,
                     argv);
1081

1082
1083
1084
  std::cout << inputFileName << std::endl;

  FILE * refFile = fopen(inputFileName.c_str(), "r");
1085
1086
1087
1088
1089
1090
1091
1092
1093
  if (refFile) {
    // Success
    fclose(refFile);
  }
  else {
    std::cout << "Cannot open file: " << argv[1] << std::endl;
    return 1;
  }

1094
1095
1096
1097
1098
1099
  std::string meshName;
  if(outputFileName.compare("") == 0) {
    meshName = inputFileName;
  }
  else {
    meshName = outputFileName;
1100
1101
1102
  }

  if(meshName.find_last_of("/\\") != std::string::npos) {
1103
    meshName = meshName.substr(meshName.find_last_of("/\\") + 1,
1104
1105
1106
1107
1108
1109
1110
                               meshName.length());
  }

  if (meshName.rfind(".") != std::string::npos) {
    meshName = meshName.substr(0, meshName.rfind("."));
  }

1111
  if(outputFileName.compare("") == 0) {
1112
1113
1114
1115
1116
1117
1118
1119
    std::stringstream newMeshName;
    if(unpartition) {
      newMeshName << meshName << "_unpartitioned";
    }
    else {
      newMeshName << meshName << "_p" << numPartitions;
    }
    meshName = newMeshName.str();
1120
1121
  }

1122
1123
  shared_ptr<XdmfReader> reader = XdmfReader::New();
  shared_ptr<XdmfDomain> domain =
1124
    shared_dynamic_cast<XdmfDomain>(reader->read(inputFileName));
1125

1126
1127
1128
1129
1130
1131
1132
  if(unpartition) {
    if(domain->getNumberGridCollections() == 0) {
      std::cout << "No grid collections to unpartition" << std::endl;
      return 1;
    }
  }
  else {
1133
    if(domain->getNumberUnstructuredGrids() == 0 &&
Kenneth Leiter's avatar
Kenneth Leiter committed
1134
1135
1136
       domain->getNumberGridCollections() == 0 &&
       domain->getNumberGraphs() == 0) {
      std::cout << "No grids or graphs to partition" << std::endl;
1137
1138
      return 1;
    }
1139
1140
1141
1142
  }

  std::stringstream heavyFileName;
  heavyFileName << meshName << ".h5";
1143
  shared_ptr<XdmfHDF5Writer> heavyDataWriter =
1144
1145
    XdmfHDF5Writer::New(heavyFileName.str());

1146
1147
  shared_ptr<XdmfDomain> newDomain = XdmfDomain::New();

1148
  shared_ptr<XdmfPartitioner> partitioner = XdmfPartitioner::New();
1149

1150
1151
1152
1153
1154
1155
  if(unpartition) {
    shared_ptr<XdmfUnstructuredGrid> toWrite =
      partitioner->unpartition(domain->getGridCollection(0));
    newDomain->insert(toWrite);
  }
  else {
Kenneth Leiter's avatar
Kenneth Leiter committed
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
    if(domain->getNumberGraphs() == 0) {
      shared_ptr<XdmfUnstructuredGrid> gridToPartition;
      if(domain->getNumberUnstructuredGrids() == 0) {
        // repartition
        gridToPartition =
          partitioner->unpartition(domain->getGridCollection(0));
      }
      else {
        gridToPartition = domain->getUnstructuredGrid(0);
      }
      shared_ptr<XdmfGridCollection> toWrite =
        partitioner->partition(gridToPartition,
                               numPartitions,
                               metisScheme,
                               heavyDataWriter);
      newDomain->insert(toWrite);
1172
1173
    }
    else {
Kenneth Leiter's avatar
Kenneth Leiter committed
1174
1175
1176
1177
      shared_ptr<XdmfGraph> graphToPartition = domain->getGraph(0);
      partitioner->partition(graphToPartition,
                             numPartitions);
      newDomain->insert(graphToPartition);
1178
    }
1179
  }
1180
1181
1182

  std::stringstream xmlFileName;
  xmlFileName << meshName << ".xmf";
1183
1184
  shared_ptr<XdmfWriter> writer = XdmfWriter::New(xmlFileName.str(),
                                                  heavyDataWriter);
1185
1186
1187
  newDomain->accept(writer);

  std::cout << "Wrote: " << xmlFileName.str() << std::endl;
1188
}
1189

1190
#endif // BUILD_EXE