meshPartitioning.cpp

Go to the documentation of this file.

 
/*
 * -------------------------------------------
 * Copyright (c) 2021 - 2026 Prashant K. Jha
 * -------------------------------------------
 * PeriDEM https://github.com/prashjha/PeriDEM
 *
 * Distributed under the Boost Software License, Version 1.0. (See accompanying
 * file LICENSE)
 */
 
#include "meshPartitioning.h"
#include "util/io.h"
#include <stdexcept>
#include "mesh.h"
#include "util/vecMethods.h" // declares std::chrono and defines timeDiff()
 
#include <metis.h>
#include <format>
 
void mesh::metisGraphPartition(std::string partitionMethod,
                         const std::vector<std::vector<size_t>> &nodeNeighs,
                         std::vector<size_t> &nodePartition,
                         size_t nPartitions) {
  // record time
  auto t1 = steady_clock::now();
  idx_t nvtxs = nodeNeighs.size();
  idx_t ncon = 1; // # of balancing constraints (at least 1)
  idx_t objval;
  int metis_return;
  idx_t nWeights  = 1;
  std::vector<idx_t> part(nvtxs, 0);
  std::vector<idx_t> vwgt(nvtxs * nWeights, 0);
  auto nParts = idx_t(nPartitions);
 
  // create adjacency data based on nodeNeighs
  // METIS needs xadj of length nvtxs+1 (CSR row pointers).
  std::vector<idx_t> xadj(static_cast<size_t>(nvtxs) + 1, 0);
  std::vector<idx_t> adjncy;
  for (size_t i=0; i<static_cast<size_t>(nvtxs); i++) {
    adjncy.insert(adjncy.end(), nodeNeighs[i].begin(), nodeNeighs[i].end());
    xadj[i+1] = xadj[i] + idx_t(nodeNeighs[i].size());
  }
  std::cout << std::format("adjcny size = {}, xadj[end] = {}\n",
                           adjncy.size(), xadj[nvtxs]);
 
  std::cout << "\nmetisGraphPartition():\n";
  if (partitionMethod == "metis_recursive") {
    std::cout << "  METIS_PartGraphRecursive partitions a graph into K parts\n";
    std::cout << "  using multilevel recursive bisection.\n";
 
    metis_return = METIS_PartGraphRecursive(&nvtxs, &ncon, xadj.data(),
                                       adjncy.data(), NULL, NULL,
                                       NULL, &nParts, NULL, NULL, NULL, &objval,
                                       part.data());
  } else if (partitionMethod == "metis_kway") {
    std::cout << "  METIS_PartGraphKway partitions a graph into K parts\n";
    std::cout << "  using multilevel K-way partition.\n";
 
    metis_return = METIS_PartGraphKway(&nvtxs, &ncon, xadj.data(),
                                       adjncy.data(), NULL, NULL,
                                       NULL, &nParts, NULL, NULL, NULL, &objval,
                                       part.data());
  } else {
    throw std::runtime_error(
        util::io::Msg()
        << "Argument partitionMethod = "
        << partitionMethod << " is invalid.\n"
        << "Valid values are {'metis_recursive', 'metis_kway'}.\n");
  }
 
  // record time
  auto t2 = steady_clock::now();
 
  std::cout << std::format("\n  Return code = {}\n"
                           "  Edge cuts for partition = {}\n"
                           "  Partition calculation time (ms) = {}\n",
                           metis_return, (int) objval,
                           util::methods::timeDiff(t1, t2, "microseconds"));
 
  // cast the part vector into nodePartition vector
  nodePartition.resize(0);
  nodePartition.insert(nodePartition.end(), part.begin(), part.end());
}
 
void mesh::metisGraphPartition(std::string partitionMethod,
                         mesh::Mesh *mesh_p,
                         const std::vector<std::vector<size_t>> &nodeNeighs,
                         size_t nPartitions) {
  mesh_p->d_nPart = nPartitions;
  mesh_p->d_partitionMethod = partitionMethod;
  mesh::metisGraphPartition(partitionMethod, nodeNeighs,
                          mesh_p->d_nodePartition, nPartitions);
}