Line data    Source code

       1             : // The libMesh Finite Element Library.
       2             : // Copyright (C) 2002-2025 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
       3             : 
       4             : // This library is free software; you can redistribute it and/or
       5             : // modify it under the terms of the GNU Lesser General Public
       6             : // License as published by the Free Software Foundation; either
       7             : // version 2.1 of the License, or (at your option) any later version.
       8             : 
       9             : // This library is distributed in the hope that it will be useful,
      10             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      12             : // Lesser General Public License for more details.
      13             : 
      14             : // You should have received a copy of the GNU Lesser General Public
      15             : // License along with this library; if not, write to the Free Software
      16             : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      17             : 
      18             : 
      19             : 
      20             : #ifndef LIBMESH_METIS_CSR_GRAPH_H
      21             : #define LIBMESH_METIS_CSR_GRAPH_H
      22             : 
      23             : // Local Includes
      24             : #include "libmesh/libmesh_common.h"
      25             : 
      26             : // C++ Includes
      27             : #include <vector>
      28             : #include <numeric>
      29             : 
      30             : namespace libMesh
      31             : {
      32             : 
      33             : /**
      34             :  * This utility class provides a convenient implementation for
      35             :  * building the compressed-row-storage graph required for the
      36             :  * METIS/ParMETIS graph partitioning schemes.
      37             :  *
      38             :  * \author Benjamin S. Kirk
      39             :  * \date 2013
      40             :  * \brief Compressed graph data structure used by MetisPartitioner.
      41             :  */
      42             : template <class IndexType>
      43       25961 : class METIS_CSR_Graph
      44             : {
      45             : public:
      46             :   std::vector<IndexType> offsets, vals;
      47             : 
      48             :   /**
      49             :    * Sets the number of non-zero values in the given row.  The
      50             :    * internal indexing is 1-based.
      51             :    */
      52      523264 :   void prep_n_nonzeros(const libMesh::dof_id_type row,
      53             :                        const libMesh::dof_id_type n_nonzeros_in)
      54             :   {
      55      523264 :     libmesh_assert_less (row+1, offsets.size());
      56     3065405 :     offsets[row+1] = n_nonzeros_in;
      57      523264 :   }
      58             : 
      59             :   /**
      60             :    * \returns The number of nonzeros in the requested row by
      61             :    * subtracting the offsets vector entries.
      62             :    */
      63             :   libMesh::dof_id_type n_nonzeros (const libMesh::dof_id_type row) const
      64             :   {
      65             :     libmesh_assert_less (row+1, offsets.size());
      66             :     return (offsets[row+1] - offsets[row]);
      67             :   }
      68             : 
      69             :   /**
      70             :    * Replaces the entries in the offsets vector with their partial
      71             :    * sums and resizes the val vector accordingly.
      72             :    */
      73       33961 :   void prepare_for_use()
      74             :   {
      75       29961 :     std::partial_sum (offsets.begin(), offsets.end(), offsets.begin());
      76        4000 :     libmesh_assert (!offsets.empty());
      77       33961 :     vals.resize(offsets.back());
      78             : 
      79       33961 :     if (vals.empty())
      80         256 :       vals.push_back(0);
      81       33961 :   }
      82             : 
      83             :   /**
      84             :    * \returns A writable reference to the nonzero'th entry of row.
      85             :    */
      86     2028332 :   IndexType & operator()(const libMesh::dof_id_type row,
      87             :                          const libMesh::dof_id_type nonzero)
      88             :   {
      89     2028332 :     libmesh_assert_greater (vals.size(), offsets[row]+nonzero);
      90             : 
      91    11425736 :     return vals[offsets[row]+nonzero];
      92             :   }
      93             : 
      94             :   /**
      95             :    * \returns A const reference to the nonzero'th entry of row.
      96             :    */
      97             :   const IndexType & operator()(const libMesh::dof_id_type row,
      98             :                                const libMesh::dof_id_type nonzero) const
      99             :   {
     100             :     libmesh_assert_greater (vals.size(), offsets[row]+nonzero);
     101             : 
     102             :     return vals[offsets[row]+nonzero];
     103             :   }
     104             : };
     105             : 
     106             : } // namespace libMesh
     107             : 
     108             : #endif // LIBMESH_METIS_CSR_GRAPH_H