From d94731971fb532c29c0fb3e9678f0727b8ae8394 Mon Sep 17 00:00:00 2001
From: bangerth <bangerth@0785d39b-7218-0410-832d-ea1e28bc413d>
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 <class DH>
+	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 <class DH>
+	static void
+	compute_king_ordering (std::vector<unsigned int>& 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 <boost/config.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/cuthill_mckee_ordering.hpp>
-#include "boost/graph/minimum_degree_ordering.hpp"
+#include <boost/graph/king_ordering.hpp>
 #include <boost/graph/properties.hpp>
 #include <boost/graph/bandwidth.hpp>
 
@@ -259,6 +259,61 @@ compute_Cuthill_McKee (std::vector<unsigned int>& new_dof_indices,
 }
 
 
+
+template <class DH>
+void
+DoFRenumbering::boost::
+king_ordering (DH&              dof_handler,
+	       const bool       reversed_numbering,
+	       const bool       use_constraints)
+{
+  std::vector<unsigned int> 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 <class DH>
+void
+DoFRenumbering::boost::
+compute_king_ordering (std::vector<unsigned int>& 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<types::Graph,types::vertex_degree_t>::type
+    graph_degree;
+
+  create_graph (dof_handler, use_constraints, graph, graph_degree);
+    
+  types::property_map<types::Graph, types::vertex_index_t>::type
+    index_map = get(::boost::vertex_index, graph);
+
+
+  std::vector<types::Vertex> 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<unsigned int> &,
 					      const DoFHandler<deal_II_dimension> &, bool, bool);
 
+template
+void
+DoFRenumbering::boost::king_ordering (DoFHandler<deal_II_dimension> &, bool, bool);
+
+template
+void
+DoFRenumbering::boost::compute_king_ordering (std::vector<unsigned int> &,
+					      const DoFHandler<deal_II_dimension> &, bool, bool);
+
+
+// non-boost functions:
 
 template
 void DoFRenumbering::Cuthill_McKee<DoFHandler<deal_II_dimension> >
-- 
2.39.5