From d94731971fb532c29c0fb3e9678f0727b8ae8394 Mon Sep 17 00:00:00 2001 From: bangerth Date: Wed, 5 Mar 2008 15:59:46 +0000 Subject: [PATCH] Write wrappers for the BOOST implementation of the King reordering algorithm. git-svn-id: https://svn.dealii.org/trunk@15861 0785d39b-7218-0410-832d-ea1e28bc413d --- .../deal.II/include/dofs/dof_renumbering.h | 36 +++++++++- .../deal.II/source/dofs/dof_renumbering.cc | 68 ++++++++++++++++++- 2 files changed, 102 insertions(+), 2 deletions(-) diff --git a/deal.II/deal.II/include/dofs/dof_renumbering.h b/deal.II/deal.II/include/dofs/dof_renumbering.h index 14ef002a63..8ba22cb130 100644 --- a/deal.II/deal.II/include/dofs/dof_renumbering.h +++ b/deal.II/deal.II/include/dofs/dof_renumbering.h @@ -221,7 +221,7 @@ class DoFRenumbering * the Boost Graph Library (BGL) * by Jeremy Siek and others. * - * While often slight slower to + * While often slighty slower to * compute, the algorithms using * often lead to matrices with * smaller bandwidths and sparse @@ -264,6 +264,40 @@ class DoFRenumbering const DH&, const bool reversed_numbering = false, const bool use_constraints = false); + + /** + * Renumber the degrees of + * freedom based on the BOOST + * implementation of the King + * algorithm. This often + * results in slightly larger + * (by a few percent) + * bandwidths than the + * Cuthill-McKee algorithm, + * but sparse ILUs are often + * slightly (also by a few + * percent) better + * preconditioners. + */ + template + static void + king_ordering (DH& dof_handler, + const bool reversed_numbering = false, + const bool use_constraints = false); + + /** + * Compute the renumbering + * for the King algorithm but + * do not actually renumber + * the degrees of freedom in + * the DoF handler argument. + */ + template + static void + compute_king_ordering (std::vector& new_dof_indices, + const DH&, + const bool reversed_numbering = false, + const bool use_constraints = false); }; /** diff --git a/deal.II/deal.II/source/dofs/dof_renumbering.cc b/deal.II/deal.II/source/dofs/dof_renumbering.cc index 36825e3645..1d93fd6cc5 100644 --- a/deal.II/deal.II/source/dofs/dof_renumbering.cc +++ b/deal.II/deal.II/source/dofs/dof_renumbering.cc @@ -38,7 +38,7 @@ #include #include #include -#include "boost/graph/minimum_degree_ordering.hpp" +#include #include #include @@ -259,6 +259,61 @@ compute_Cuthill_McKee (std::vector& new_dof_indices, } + +template +void +DoFRenumbering::boost:: +king_ordering (DH& dof_handler, + const bool reversed_numbering, + const bool use_constraints) +{ + std::vector renumbering(dof_handler.n_dofs(), + DH::invalid_dof_index); + compute_king_ordering(renumbering, dof_handler, reversed_numbering, + use_constraints); + + // actually perform renumbering; + // this is dimension specific and + // thus needs an own function + dof_handler.renumber_dofs (renumbering); +} + + +template +void +DoFRenumbering::boost:: +compute_king_ordering (std::vector& new_dof_indices, + const DH &dof_handler, + const bool reversed_numbering, + const bool use_constraints) +{ + types::Graph + graph(dof_handler.n_dofs()); + types::property_map::type + graph_degree; + + create_graph (dof_handler, use_constraints, graph, graph_degree); + + types::property_map::type + index_map = get(::boost::vertex_index, graph); + + + std::vector inv_perm(num_vertices(graph)); + + if (reversed_numbering == false) + ::boost::king_ordering(graph, inv_perm.rbegin()); + else + ::boost::king_ordering(graph, inv_perm.begin()); + + for (types::size_type c = 0; c != inv_perm.size(); ++c) + new_dof_indices[index_map[inv_perm[c]]] = c; + + Assert (std::find (new_dof_indices.begin(), new_dof_indices.end(), + DH::invalid_dof_index) == new_dof_indices.end(), + ExcInternalError()); +} + + @@ -1650,6 +1705,17 @@ void DoFRenumbering::boost::compute_Cuthill_McKee (std::vector &, const DoFHandler &, bool, bool); +template +void +DoFRenumbering::boost::king_ordering (DoFHandler &, bool, bool); + +template +void +DoFRenumbering::boost::compute_king_ordering (std::vector &, + const DoFHandler &, bool, bool); + + +// non-boost functions: template void DoFRenumbering::Cuthill_McKee > -- 2.39.5