#include <ckpttn/PartMgrBase.hpp>
template<typename Gnl, typename GainMgr, typename ConstrMgr>
PartMgrBase class

Fiduccia-Mattheyses Partitioning Algorithm Manager Base.

Template parameters
Gnl
GainMgr
ConstrMgr

PartMgrBase is a base class for managing the Fiduccia-Mattheyses Partitioning Algorithm. It takes three template parameters: Gnl (graph type), GainMgr (gain manager type), and ConstrMgr (constraint manager type).

In this partitioning method, the next solution $s'$ considered after solution $s$ is dervied by first applying a sequence of $t$ changes (moves) to $s$ (with $t$ dependent from $s$ and from the specific heuristic method), thus obtaining a sequence of solution $s,...,s_t$ and by successively choosing the best among these solutions.

In order to do that, heuristics refer to a measure of the gain (and balance condition) associated to any sequence of changes performed on the current solution. Moreover, the length of the sequence generated is determined by evaluting a suitably defined $stopping rule$ at each iteration.

Reference: gr. Ausiello et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Section 10.3.2.

Derived classes

template<typename Gnl, typename GainMgr, typename ConstrMgr>
class FMPartMgr
Fiduccia-Mattheyses Partitioning Algorithm Manager.

Public types

using GainCalc_ = typename GainMgr::GainCalc_
using GainMgr_ = GainMgr
using ConstrMgr_ = ConstrMgr

Constructors, destructors, conversion operators

PartMgrBase(const Gnl& hyprgraph, GainMgr& gain_mgr, ConstrMgr& constr_mgr, size_t num_parts)
Construct a new Part Mgr Base object.

Public functions

void init(gsl::span<std::uint8_t> part)
auto legalize(gsl::span<std::uint8_t> part) -> LegalCheck -> auto
void optimize(gsl::span<std::uint8_t> part)

Public variables

int total_cost

Protected variables

const Gnl& hyprgraph
GainMgr& gain_mgr
ConstrMgr& validator
size_t num_parts

Function documentation

template<typename Gnl, typename GainMgr, typename ConstrMgr>
PartMgrBase<Gnl, GainMgr, ConstrMgr>::PartMgrBase(const Gnl& hyprgraph, GainMgr& gain_mgr, ConstrMgr& constr_mgr, size_t num_parts)

Construct a new Part Mgr Base object.

Parameters
hyprgraph in
gain_mgr in/out
constr_mgr in/out
num_parts in

template<typename Gnl, typename GainMgr, typename ConstrMgr>
void PartMgrBase<Gnl, GainMgr, ConstrMgr>::init(gsl::span<std::uint8_t> part)

Parameters
part in/out

template<typename Gnl, typename GainMgr, typename ConstrMgr>
auto PartMgrBase<Gnl, GainMgr, ConstrMgr>::legalize(gsl::span<std::uint8_t> part) -> LegalCheck

Parameters
part in/out
Returns LegalCheck

template<typename Gnl, typename GainMgr, typename ConstrMgr>
void PartMgrBase<Gnl, GainMgr, ConstrMgr>::optimize(gsl::span<std::uint8_t> part)

Parameters
part in/out