coloring.hpp

// FEAT3: Finite Element Analysis Toolbox, Version 3
// Copyright (C) 2010 by Stefan Turek & the FEAT group
// FEAT3 is released under the GNU General Public License version 3,
// see the file 'copyright.txt' in the top level directory for details.
 
#pragma once
 
// includes, FEAT
#include <kernel/base_header.hpp>
#include <kernel/util/assertion.hpp>
#include <kernel/util/memory_pool.hpp>
 
#ifdef FEAT_HAVE_CUDA
#include <kernel/util/cuda_util.hpp>
#endif
 
// includes, system
#include <vector>
#include <algorithm>
#include <numeric>
 
namespace FEAT
{
  namespace Adjacency
  {
    // forward declaration
    class Graph;
 
    class Coloring
    {
    protected:
      using IndexVector = std::vector < Index>;
 
      Index _num_colors;
 
      IndexVector _coloring;
 
    public:
 
      Coloring();
 
      Coloring(
        Index num_nodes,
        Index num_colors);
 
      Coloring(
        Index num_nodes,
        Index* coloring);
 
      Coloring(
        Index num_colors,
        const IndexVector& coloring);
 
      explicit Coloring(const Graph& graph);
 
      explicit Coloring(const Graph& graph, const Index* order);
 
      Coloring(Coloring&& other) noexcept;
 
      Coloring& operator=(Coloring&& other) noexcept;
 
      virtual ~Coloring();
 
      Coloring clone() const
      {
        if (!_coloring.empty())
          //return Coloring(Index(_coloring.size()), _coloring.data());
          return Coloring(_num_colors, _coloring);
        else
          return Coloring();
      }
 
      Graph create_partition_graph() const;
 
      Index* get_coloring()
      {
        return _coloring.data();
      }
 
      const Index* get_coloring() const
      {
        return _coloring.data();
      }
 
      Index get_num_nodes() const
      {
        return Index(_coloring.size());
      }
 
      auto size() const -> decltype(_coloring.size())
      {
        return _coloring.size();
      }
 
      Index get_max_color() const
      {
        return _num_colors - 1;
      }
 
      Index get_num_colors() const
      {
        return _num_colors;
      }
 
      bool empty() const
      {
        return _coloring.empty();
      }
 
      Index& operator[](Index i)
      {
        ASSERT(i < _coloring.size());
        return _coloring[i];
      }
 
      const Index& operator[](Index i) const
      {
        ASSERT(i < _coloring.size());
        return _coloring[i];
      }
    }; // class Coloring
 
    class ColoringDataHandler
    {
      public:
        std::vector<int*> _coloring_maps;
        std::vector<Index> _coloring_map_sizes;
 
      explicit ColoringDataHandler() = default;
 
      template<typename ColoringType_>
      ColoringDataHandler(const ColoringType_& coloring, int hint = -1)
      {
        fill_color(coloring, hint);
      }
 
      ~ColoringDataHandler()
      {
        release_color();
      }
 
      ColoringDataHandler(const ColoringDataHandler&) = delete;
 
      ColoringDataHandler& operator=(const ColoringDataHandler&) = delete;
 
 
      ColoringDataHandler(ColoringDataHandler&& other) noexcept
      {
        _coloring_maps = std::move(other._coloring_maps);
        _coloring_map_sizes = std::move(other._coloring_map_sizes);
        other._coloring_maps.clear();
        other._coloring_map_sizes.clear();
      }
 
      ColoringDataHandler& operator=(ColoringDataHandler&& other) noexcept
      {
        if(this == &other)
          return *this;
        release_color();
        _coloring_maps = std::move(other._coloring_maps);
        _coloring_map_sizes = std::move(other._coloring_map_sizes);
        other._coloring_maps.clear();
        other._coloring_map_sizes.clear();
        return *this;
      }
 
      Index get_num_colors() const
      {
        return _coloring_map_sizes.size();
      }
 
      Index get_color_size(Index k) const
      {
        return _coloring_map_sizes.at(k);
      }
 
      std::vector<Index>& get_color_sizes()
      {
        return _coloring_map_sizes;
      }
 
      const std::vector<Index>& get_color_sizes() const
      {
        return _coloring_map_sizes;
      }
 
      int* get_color_map(Index k)
      {
        return _coloring_maps.at(k);
      }
 
      const int* get_color_map(Index k) const
      {
        return _coloring_maps.at(k);
      }
 
      std::vector<int*>& get_coloring_maps()
      {
        return _coloring_maps;
      }
 
      const std::vector<int*>& get_coloring_maps() const
      {
        return _coloring_maps;
      }
 
      Index get_max_color_size() const
      {
        return Index(std::accumulate(_coloring_map_sizes.begin(), _coloring_map_sizes.end(), Index(0), [](Index a, Index b){return std::max(a,b);}));
      }
 
 
      void fill_color(const std::vector<int>& coloring, int hint = -1)
      {
        int num_colors = hint;
        if(hint < 0)
        {
          num_colors = *std::max_element(coloring.begin(), coloring.end()) + 1;
        }
        // fill tmp vector with coloring
        std::vector<std::vector<int>> tmp_vector;
        tmp_vector.resize(Index(num_colors));
        for(std::size_t i = 0; i < coloring.size(); ++i)
        {
          tmp_vector.at(std::size_t(coloring.at(i))).push_back(int(i));
        }
        _coloring_maps.resize(std::size_t(num_colors));
        _coloring_map_sizes.resize(std::size_t(num_colors));
        for(Index i = 0; i < Index(num_colors); ++i)
        {
          _coloring_maps.at(i) = MemoryPool::allocate_memory<int>(tmp_vector.at(i).size());
          MemoryPool::copy(_coloring_maps.at(i), tmp_vector.at(i).data(), tmp_vector.at(i).size());
          _coloring_map_sizes.at(i) = tmp_vector.at(i).size();
        }
 
      }
 
      void fill_color(const Coloring& coloring, int hint = -1)
      {
        int num_colors = int(coloring.get_num_colors());
        if(hint >= 0)
        {
          ASSERTM(num_colors == hint, "Hint and number of colors do not fit!");
        }
 
        // fill tmp vector with coloring
        std::vector<std::vector<int>> tmp_vector;
        tmp_vector.resize(Index(num_colors));
        for(std::size_t i = 0; i < coloring.size(); ++i)
        {
          tmp_vector.at(std::size_t(coloring[i])).push_back(int(i));
        }
        _coloring_maps.resize(std::size_t(num_colors));
        _coloring_map_sizes.resize(std::size_t(num_colors));
        for(Index i = 0; i < Index(num_colors); ++i)
        {
          _coloring_maps.at(i) = MemoryPool::allocate_memory<int>(tmp_vector.at(i).size());
          MemoryPool::copy(_coloring_maps.at(i), tmp_vector.at(i).data(), tmp_vector.at(i).size());
          _coloring_map_sizes.at(i) = Index(tmp_vector.at(i).size());
        }
      }
 
      void release_color()
      {
        for(Index i = 0; i < _coloring_maps.size(); ++i)
        {
          MemoryPool::release_memory(_coloring_maps.at(i));
        }
        _coloring_maps.clear();
        _coloring_map_sizes.clear();
      }
 
      bool initialized() const
      {
        return _coloring_maps.size() > 0u;
      }
 
      Index get_max_size() const
      {
        return std::accumulate(_coloring_map_sizes.begin(), _coloring_map_sizes.end(), Index(0), [](const Index& a, const Index& b){return std::max(a, b);});
      }
    }; // class ColoringDataHandler
  } // namespace Adjacency
} // namespace FEAT