PartMgrBase< Gnl, GainMgr, ConstrMgr > Class Template Reference

Fiduccia-Mattheyses Partitioning Algorithm Manager Base. More...

#include <PartMgrBase.hpp>

Inheritance diagram for PartMgrBase< Gnl, GainMgr, ConstrMgr >:

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

Public Member Functions
	PartMgrBase (const Gnl &hyprgraph, GainMgr &gain_mgr, ConstrMgr &constr_mgr, size_t num_parts)
	Construct a new Part Mgr Base object.
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
	Legalizes the partition to satisfy balance constraints.
void	optimize (std::span< std::uint8_t > part)
	Optimizes the partition using the FM algorithm.

Public Attributes
int	total_cost {}

Protected Attributes
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.

Detailed Description

template<typename Gnl, typename GainMgr, typename ConstrMgr>
class PartMgrBase< Gnl, GainMgr, ConstrMgr >

Fiduccia-Mattheyses Partitioning Algorithm Manager Base.

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.

Template Parameters

Gnl
GainMgr
ConstrMgr
Derived

Member Typedef Documentation

ConstrMgr_

template<typename Gnl , typename GainMgr , typename ConstrMgr >

using PartMgrBase< Gnl, GainMgr, ConstrMgr >::ConstrMgr_ = ConstrMgr

GainCalc_

template<typename Gnl , typename GainMgr , typename ConstrMgr >

using PartMgrBase< Gnl, GainMgr, ConstrMgr >::GainCalc_ = typename GainMgr::GainCalc_

GainMgr_

template<typename Gnl , typename GainMgr , typename ConstrMgr >

using PartMgrBase< Gnl, GainMgr, ConstrMgr >::GainMgr_ = GainMgr

Constructor & Destructor Documentation

PartMgrBase()

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  )

inline

Construct a new Part Mgr Base object.

Parameters

[in]	hyprgraph
[in,out]	gain_mgr
[in,out]	constr_mgr
[in]	num_parts

Member Function Documentation

init()

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

[in,out]

part

The partition vector to initialize.

legalize()

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

[in,out]

part

The partition to legalize.

Returns

LegalCheck The result of the legality check.

optimize()

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

[in,out]

part

The partition to optimize.

Member Data Documentation

gain_mgr

template<typename Gnl , typename GainMgr , typename ConstrMgr >

GainMgr& PartMgrBase< Gnl, GainMgr, ConstrMgr >::gain_mgr

protected

Gain manager for computing and managing gains.

hyprgraph

template<typename Gnl , typename GainMgr , typename ConstrMgr >

const Gnl& PartMgrBase< Gnl, GainMgr, ConstrMgr >::hyprgraph

protected

Reference to the hypergraph being partitioned.

num_parts

template<typename Gnl , typename GainMgr , typename ConstrMgr >

size_t PartMgrBase< Gnl, GainMgr, ConstrMgr >::num_parts

protected

Number of partitions.

total_cost

template<typename Gnl , typename GainMgr , typename ConstrMgr >

int PartMgrBase< Gnl, GainMgr, ConstrMgr >::total_cost {}

validator

template<typename Gnl , typename GainMgr , typename ConstrMgr >

ConstrMgr& PartMgrBase< Gnl, GainMgr, ConstrMgr >::validator

protected

Constraint manager for validating partition constraints.

---

The documentation for this class was generated from the following file:

• ckpttn/PartMgrBase.hpp