#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(std::span<std::uint8_t> part)
Initializes the partition manager with the given partition.
auto legalize(std::span<std::uint8_t> part) -> LegalCheck -> auto
Legalizes the partition to satisfy balance constraints.
void optimize(std::span<std::uint8_t> part)
Optimizes the partition using the FM algorithm.

Public variables

int total_cost

Protected variables

const Gnl& hyprgraph
Reference to the hypergraph being partitioned.
GainMgr& gain_mgr
Gain manager for computing and managing gains.
ConstrMgr& validator
Constraint manager for validating partition constraints.
size_t num_parts
Number of partitions.

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(std::span<std::uint8_t> part)

Initializes the partition manager with the given partition.

Parameters
part in/out The partition vector to initialize.

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

Legalizes the partition to satisfy balance constraints.

Parameters
part in/out The partition to legalize.
Returns LegalCheck The result of the legality check.

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

Optimizes the partition using the FM algorithm.

Parameters
part in/out The partition to optimize.