dof_renumbering.h

// ---------------------------------------------------------------------
//
// Copyright (C) 2003 - 2016 by the deal.II authors
//
// This file is part of the deal.II library.
//
// The deal.II library is free software; you can use it, redistribute
// it, and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// The full text of the license can be found in the file LICENSE at
// the top level of the deal.II distribution.
//
// ---------------------------------------------------------------------

#ifndef dealii__dof_renumbering_h
#define dealii__dof_renumbering_h


#include <deal.II/base/config.h>
#include <deal.II/base/exceptions.h>
#include <deal.II/base/point.h>
#include <deal.II/dofs/dof_handler.h>
#include <deal.II/hp/dof_handler.h>

#include <vector>

DEAL_II_NAMESPACE_OPEN

namespace DoFRenumbering
{
  template <class Iterator, int dim>
  struct CompareDownstream
  {
    CompareDownstream (const Tensor<1,dim> &dir)
      :
      dir(dir)
    {}
    bool operator () (const Iterator &c1, const Iterator &c2) const
    {
      const Tensor<1,dim> diff = c2->center() - c1->center();
      return (diff*dir > 0);
    }

  private:
    const Tensor<1,dim> dir;
  };


  template <int dim>
  struct ComparePointwiseDownstream
  {
    ComparePointwiseDownstream (const Tensor<1,dim> &dir)
      :
      dir(dir)
    {}
    bool operator () (const std::pair<Point<dim>,types::global_dof_index> &c1,
                      const std::pair<Point<dim>,types::global_dof_index> &c2) const
    {
      const Tensor<1,dim> diff = c2.first-c1.first;
      return (diff*dir > 0 || (diff*dir==0 && c1.second<c2.second));
    }

  private:
    const Tensor<1,dim> dir;
  };



  namespace boost
  {
    template <typename DoFHandlerType>
    void
    Cuthill_McKee (DoFHandlerType &dof_handler,
                   const bool      reversed_numbering = false,
                   const bool      use_constraints    = false);

    template <typename DoFHandlerType>
    void
    compute_Cuthill_McKee (std::vector<types::global_dof_index> &new_dof_indices,
                           const DoFHandlerType &,
                           const bool                            reversed_numbering = false,
                           const bool                            use_constraints    = false);

    template <typename DoFHandlerType>
    void
    king_ordering (DoFHandlerType &dof_handler,
                   const bool      reversed_numbering = false,
                   const bool      use_constraints    = false);

    template <typename DoFHandlerType>
    void
    compute_king_ordering (std::vector<types::global_dof_index> &new_dof_indices,
                           const DoFHandlerType &,
                           const bool                            reversed_numbering = false,
                           const bool                            use_constraints    = false);

    template <typename DoFHandlerType>
    void
    minimum_degree (DoFHandlerType &dof_handler,
                    const bool      reversed_numbering = false,
                    const bool      use_constraints    = false);

    template <typename DoFHandlerType>
    void
    compute_minimum_degree (std::vector<types::global_dof_index> &new_dof_indices,
                            const DoFHandlerType &,
                            const bool                            reversed_numbering = false,
                            const bool                            use_constraints    = false);
  }

  template <typename DoFHandlerType>
  void
  Cuthill_McKee (DoFHandlerType                             &dof_handler,
                 const bool                                  reversed_numbering = false,
                 const bool                                  use_constraints    = false,
                 const std::vector<types::global_dof_index> &starting_indices
                 = std::vector<types::global_dof_index>());

  template <typename DoFHandlerType>
  void
  compute_Cuthill_McKee (std::vector<types::global_dof_index>       &new_dof_indices,
                         const DoFHandlerType &,
                         const bool                                  reversed_numbering = false,
                         const bool                                  use_constraints    = false,
                         const std::vector<types::global_dof_index> &starting_indices
                         = std::vector<types::global_dof_index>());

  template <typename DoFHandlerType>
  void
  Cuthill_McKee (DoFHandlerType                             &dof_handler,
                 const unsigned int                          level,
                 const bool                                  reversed_numbering = false,
                 const std::vector<types::global_dof_index> &starting_indices
                 = std::vector<types::global_dof_index> ());

  template <int dim, int spacedim>
  void
  component_wise (DoFHandler<dim,spacedim>        &dof_handler,
                  const std::vector<unsigned int> &target_component
                  = std::vector<unsigned int>());


  template <int dim>
  void
  component_wise (hp::DoFHandler<dim>             &dof_handler,
                  const std::vector<unsigned int> &target_component = std::vector<unsigned int> ());

  template <typename DoFHandlerType>
  void
  component_wise (DoFHandlerType                  &dof_handler,
                  const unsigned int               level,
                  const std::vector<unsigned int> &target_component
                  = std::vector<unsigned int>());

  template <int dim, int spacedim, class ITERATOR, class ENDITERATOR>
  types::global_dof_index
  compute_component_wise (std::vector<types::global_dof_index> &new_dof_indices,
                          const ITERATOR &start,
                          const ENDITERATOR &end,
                          const std::vector<unsigned int> &target_component,
                          bool is_level_operation);

  template <int dim, int spacedim>
  void
  block_wise (DoFHandler<dim,spacedim> &dof_handler);

  template <int dim, int spacedim>
  void
  block_wise (DoFHandler<dim,spacedim> &dof_handler, const unsigned int level);

  template <int dim, int spacedim>
  void
  block_wise (hp::DoFHandler<dim,spacedim> &dof_handler);

  template <int dim, int spacedim, class ITERATOR, class ENDITERATOR>
  types::global_dof_index
  compute_block_wise (std::vector<types::global_dof_index> &new_dof_indices,
                      const ITERATOR &start,
                      const ENDITERATOR &end,
                      bool is_level_operation);

  template <int dim>
  void
  hierarchical (DoFHandler<dim> &dof_handler);

  template <typename DoFHandlerType>
  void
  cell_wise (DoFHandlerType &dof_handler,
             const std::vector<typename DoFHandlerType::active_cell_iterator> &cell_order);

  template <typename DoFHandlerType>
  void
  compute_cell_wise
  (std::vector<types::global_dof_index>                             &renumbering,
   std::vector<types::global_dof_index>                             &inverse_renumbering,
   const DoFHandlerType                                             &dof_handler,
   const std::vector<typename DoFHandlerType::active_cell_iterator> &cell_order);

  template <typename DoFHandlerType>
  void
  cell_wise (DoFHandlerType                                                  &dof_handler,
             const unsigned int                                               level,
             const std::vector<typename DoFHandlerType::level_cell_iterator> &cell_order);

  template <typename DoFHandlerType>
  void
  compute_cell_wise
  (std::vector<types::global_dof_index>                            &renumbering,
   std::vector<types::global_dof_index>                            &inverse_renumbering,
   const DoFHandlerType                                            &dof_handler,
   const unsigned int                                               level,
   const std::vector<typename DoFHandlerType::level_cell_iterator> &cell_order);

  template <typename DoFHandlerType>
  void
  downstream (DoFHandlerType                               &dof_handler,
              const Point<DoFHandlerType::space_dimension> &direction,
              const bool                                    dof_wise_renumbering = false);


  template <typename DoFHandlerType>
  void
  downstream (DoFHandlerType                               &dof_handler,
              const unsigned int                            level,
              const Point<DoFHandlerType::space_dimension> &direction,
              const bool                                    dof_wise_renumbering = false);

  template <typename DoFHandlerType>
  void
  compute_downstream (std::vector<types::global_dof_index>         &new_dof_indices,
                      std::vector<types::global_dof_index>         &reverse,
                      const DoFHandlerType                         &dof_handler,
                      const Point<DoFHandlerType::space_dimension> &direction,
                      const bool                                    dof_wise_renumbering);

  template <typename DoFHandlerType>
  void
  compute_downstream (std::vector<types::global_dof_index>         &new_dof_indices,
                      std::vector<types::global_dof_index>         &reverse,
                      const DoFHandlerType                         &dof_handler,
                      const unsigned int                            level,
                      const Point<DoFHandlerType::space_dimension> &direction,
                      const bool                                    dof_wise_renumbering);

  template <typename DoFHandlerType>
  void
  clockwise_dg (DoFHandlerType                               &dof_handler,
                const Point<DoFHandlerType::space_dimension> &center,
                const bool                                    counter = false);

  template <typename DoFHandlerType>
  void
  clockwise_dg (DoFHandlerType                               &dof_handler,
                const unsigned int                            level,
                const Point<DoFHandlerType::space_dimension> &center,
                const bool                                    counter = false);

  template <typename DoFHandlerType>
  void
  compute_clockwise_dg (std::vector<types::global_dof_index>         &new_dof_indices,
                        const DoFHandlerType                         &dof_handler,
                        const Point<DoFHandlerType::space_dimension> &center,
                        const bool                                    counter);

  template <typename DoFHandlerType>
  void
  sort_selected_dofs_back (DoFHandlerType          &dof_handler,
                           const std::vector<bool> &selected_dofs);

  template <typename DoFHandlerType>
  void
  sort_selected_dofs_back (DoFHandlerType          &dof_handler,
                           const std::vector<bool> &selected_dofs,
                           const unsigned int       level);

  template <typename DoFHandlerType>
  void
  compute_sort_selected_dofs_back (std::vector<types::global_dof_index> &new_dof_indices,
                                   const DoFHandlerType                 &dof_handler,
                                   const std::vector<bool>              &selected_dofs);

  template <typename DoFHandlerType>
  void
  compute_sort_selected_dofs_back (std::vector<types::global_dof_index> &new_dof_indices,
                                   const DoFHandlerType                 &dof_handler,
                                   const std::vector<bool>              &selected_dofs,
                                   const unsigned int                    level);

  template <typename DoFHandlerType>
  void
  random (DoFHandlerType &dof_handler);

  template <typename DoFHandlerType>
  void
  compute_random (std::vector<types::global_dof_index> &new_dof_indices,
                  const DoFHandlerType &dof_handler);

  template <typename DoFHandlerType>
  void
  subdomain_wise (DoFHandlerType &dof_handler);

  template <typename DoFHandlerType>
  void
  compute_subdomain_wise (std::vector<types::global_dof_index> &new_dof_indices,
                          const DoFHandlerType                 &dof_handler);

  DeclException0 (ExcRenumberingIncomplete);
  DeclException0 (ExcInvalidComponentOrder);
  DeclException0 (ExcNotDGFEM);
}

/* ------------------------- inline functions -------------- */

#ifndef DOXYGEN
namespace DoFRenumbering
{
  template <typename DoFHandlerType>
  void
  inline
  downstream (DoFHandlerType                               &dof,
              const Point<DoFHandlerType::space_dimension> &direction,
              const bool                                    dof_wise_renumbering)
  {
    std::vector<types::global_dof_index> renumbering(dof.n_dofs());
    std::vector<types::global_dof_index> reverse(dof.n_dofs());
    compute_downstream(renumbering, reverse, dof, direction,
                       dof_wise_renumbering);

    dof.renumber_dofs(renumbering);
  }
}
#endif


DEAL_II_NAMESPACE_CLOSE

#endif