// Copyright (c) 2017 GeometryFactory (France). // All rights reserved. // // This file is part of CGAL (www.cgal.org) // // $URL: https://github.com/CGAL/cgal/blob/v5.2/BGL/include/CGAL/boost/graph/METIS/partition_graph.h $ // $Id: partition_graph.h a84927d 2020-07-23T17:15:44+02:00 Laurent Rineau // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Mael Rouxel-Labbé #ifndef CGAL_BGL_PARTITION_GRAPH_H #define CGAL_BGL_PARTITION_GRAPH_H #include #include #include #include #include #include #include #include #include #include namespace CGAL { namespace METIS { struct Output_vertex_partition_ids { template void operator()(const TriangleMesh&, const Indices, idx_t const * const, internal_np::Param_not_found) { } template void operator()(const TriangleMesh& tm, const Indices indices, idx_t const * const npart, VertexPartitionIDPmap vertex_partition_id_map) { typename boost::graph_traits::vertex_iterator vit, ve; boost::tie(vit, ve) = vertices(tm); for(; vit!=ve; ++vit) put(vertex_partition_id_map, *vit, npart[get(indices, *vit)]); } }; struct Output_face_partition_ids { template void operator()(const TriangleMesh&, idx_t const * const, internal_np::Param_not_found) { } template void operator()(const TriangleMesh& tm, idx_t const * const epart, FacePartitionIDPmap face_partition_id_map) { typename boost::graph_traits::face_iterator fit, fe; boost::tie(fit, fe) = faces(tm); for(int i=0; fit!=fe; ++fit, ++i) put(face_partition_id_map, *fit, epart[i]); } }; template void partition_graph(const TriangleMesh& tm, int nparts, METIS_options options, // pointer to the options array const NamedParameters& np) { CGAL_precondition(CGAL::is_triangle_mesh(tm)); CGAL_precondition_msg(nparts > 1, ("Partitioning requires a number of parts > 1")); using parameters::get_parameter; typedef typename boost::graph_traits::vertex_descriptor vertex_descriptor; typedef typename boost::graph_traits::halfedge_descriptor halfedge_descriptor; typedef typename boost::graph_traits::face_iterator face_iterator; typedef typename CGAL::GetInitializedVertexIndexMap::type Indices; Indices indices = CGAL::get_initialized_vertex_index_map(tm, np); idx_t nn = static_cast(num_vertices(tm)); idx_t ne = static_cast(num_faces(tm)); idx_t d = 3; // number of nodes per element idx_t* eptr = new idx_t[ne + 1]; idx_t* eind = new idx_t[d * ne]; // fill the adjacency info face_iterator fit, fe; boost::tie(fit, fe) = faces(tm); for(int i=0, j=0; fit!=fe; ++fit, ++i) { eptr[i] = j; halfedge_descriptor h = halfedge(*fit, tm), done = h; do { vertex_descriptor v = target(h, tm); CGAL_assertion(j < d * ne); eind[j++] = static_cast(get(indices, v)); h = next(h, tm); } while (h != done); CGAL_assertion(i < ne); eptr[i + 1] = j; } // either the edgecut or the total communication volume of the dual graph’s partitioning idx_t objval; // partition info for the nodes idx_t* npart = (idx_t*) calloc(num_vertices(tm), sizeof(idx_t)); CGAL_assertion(npart != nullptr); // partition info for the elements idx_t* epart = (idx_t*) calloc(num_faces(tm), sizeof(idx_t)); CGAL_assertion(epart != nullptr); // do not support Fortran-style arrays CGAL_assertion((*options)[METIS_OPTION_NUMBERING] == -1 || // default initialization is '-1' (*options)[METIS_OPTION_NUMBERING] == 0); CGAL_assertion_code(int ret =) METIS_PartMeshNodal(&ne, &nn, eptr, eind, nullptr /* nodes weights */, nullptr /* nodes sizes */, &nparts, nullptr /* partitions weights */, *options, &objval, epart, npart); CGAL_assertion(ret == METIS_OK); Output_vertex_partition_ids vo; Output_face_partition_ids fo; vo(tm, indices, npart, get_parameter(np, internal_np::vertex_partition_id)); fo(tm, epart, get_parameter(np, internal_np::face_partition_id)); delete[] eptr; delete[] eind; std::free(npart); std::free(epart); } template void partition_graph(const TriangleMesh& tm, int nparts, const internal_np::Param_not_found, // no METIS options were passed const NamedParameters& np) { idx_t options[METIS_NOPTIONS]; METIS_SetDefaultOptions(options); return partition_graph(tm, nparts, &options, np); } /// \ingroup PkgBGLPartition /// /// computes a partition of the input triangular mesh into `nparts` parts, based on the /// mesh's nodal graph. The resulting partition is stored in the vertex and/or face /// property maps that are passed as parameters using \ref bgl_namedparameters "Named Parameters". /// /// \param tm a triangle mesh /// \param nparts the number of parts in the final partition /// \param np an optional sequence of \ref bgl_namedparameters "Named Parameters" among the ones listed below /// /// \tparam TriangleMesh is a model of the `FaceListGraph` concept. /// \tparam NamedParameters a sequence of \ref bgl_namedparameters "Named Parameters" /// /// \cgalNamedParamsBegin /// \cgalParamNBegin{vertex_index_map} /// \cgalParamDescription{a property map associating to each vertex of `tm` a unique index between `0` and `num_vertices(tm) - 1`} /// \cgalParamType{a class model of `ReadablePropertyMap` with `boost::graph_traits::%vertex_descriptor` /// as key type and `std::size_t` as value type} /// \cgalParamDefault{an automatically indexed internal map} /// \cgalParamExtra{If this parameter is not passed, internal machinery will create and initialize /// a face index property map, either using the internal property map if it exists /// or using an external map. The latter might result in - slightly - worsened performance /// in case of non-constant complexity for index access.} /// \cgalParamNEnd /// /// \cgalParamNBegin{METIS_options} /// \cgalParamDescription{a parameter used in to pass options to the METIS mesh partitioner} /// \cgalParamType{an array of size `METIS_NOPTIONS` with value type `idx_t` (an integer type defined by METIS)} /// \cgalParamDefault{an array of size `METIS_NOPTIONS` with value type `idx_t`, /// initialized using the function `METIS_SetDefaultOptions()`} /// \cgalParamExtra{The many options of METIS are not described here. Instead, users should refer /// to the documentation /// of METIS directly.} /// \cgalParamNEnd /// /// \cgalParamNBegin{vertex_partition_id_map} /// \cgalParamDescription{a property map that contains (after the function has been run) /// the ID of the subpart for each vertex of `tm`} /// \cgalParamType{a class model of `ReadWritePropertyMap` with /// `boost::graph_traits::%vertex_descriptor` as key type and /// `int` as value type} /// \cgalParamDefault{unused} /// \cgalParamNEnd /// /// \cgalParamNBegin{face_partition_id_map} /// \cgalParamDescription{a property map that contains (after the function has been run) /// the ID of the subpart for each face of `tm`} /// \cgalParamType{a class model of `ReadWritePropertyMap` with /// `boost::graph_traits::%face_descriptor` as key type and /// `int` as value type} /// \cgalParamDefault{unused} /// \cgalParamNEnd /// \cgalNamedParamsEnd /// /// \pre `tm` is a pure triangular surface mesh: there are no edges /// without at least one incident face template void partition_graph(const TriangleMesh& tm, int nparts, const NamedParameters& np) { using parameters::get_parameter; return partition_graph(tm, nparts, get_parameter(np, internal_np::METIS_options), np); } template void partition_graph(const TriangleMesh& tm, const int nparts) { return partition_graph(tm, nparts, CGAL::parameters::all_default()); } } // end namespace METIS } // end namespace CGAL #endif // CGAL_BGL_PARTITION_GRAPH_H