FMGainMgr< Gnl, GainCalc, Derived > Class Template Reference

Fiduccia-Mattheyses Gain Manager. More...

#include <FMGainMgr.hpp>

Public Member Functions
	FMGainMgr (const Gnl &hyprgraph, std::uint8_t num_parts)
	Constructs a new FMGainMgr object.
auto	init (std::span< const std::uint8_t > part) -> int
	Initializes the FMGainMgr with the given partition information.
auto	is_empty_togo (uint8_t to_part) const -> bool
	Checks if the gain bucket for the given partition is empty.
auto	is_empty () const -> bool
	Checks if all the gain buckets are empty.
auto	select (std::span< const std::uint8_t > part) -> std::pair< MoveInfoV< node_t >, int >
	Selects a vertex to move and computes the associated gain.
auto	select_togo (uint8_t to_part) -> std::pair< node_t, int >
	Selects a node to move to the given partition.
auto	update_move (std::span< const std::uint8_t > part, const MoveInfoV< node_t > &move_info_v) -> void
	Updates the gain information for the given set of moves.

Public Attributes
GainCalc	gain_calc
	Gain calculator instance.

Protected Attributes
Dllist< std::pair< node_t, uint32_t > >	waiting_list {std::make_pair(node_t{}, uint32_t(0))}
	Waiting list for vertices awaiting movement.
const Gnl &	hyprgraph
	Reference to the hypergraph being partitioned.
std::vector< BPQueue< node_t > >	gain_bucket
	Gain buckets for each partition (used in bucket-based gain management)
std::uint8_t	num_parts
	Number of partitions.

Detailed Description

template<typename Gnl, typename GainCalc, class Derived>
class FMGainMgr< Gnl, GainCalc, Derived >

Fiduccia-Mattheyses Gain Manager.

The FMGainMgr class is a CRTP base class for managing the gain calculation and bucket structure used in the Fiduccia-Mattheyses partitioning algorithm. It provides methods for initializing gains, selecting vertices to move, and updating gain values after moves.

Template Parameters

Gnl	The hypergraph type
GainCalc	The gain calculator type
Derived	The derived gain manager type (CRTP)

Constructor & Destructor Documentation

FMGainMgr()

template<typename Gnl , typename GainCalc , class Derived >

FMGainMgr< Gnl, GainCalc, Derived >::FMGainMgr	(	const Gnl &	hyprgraph,
		std::uint8_t	num_parts
	)

Constructs a new FMGainMgr object.

Parameters

[in]	hyprgraph	The hypergraph to manage the gains for.
[in]	num_parts	The number of partitions in the hypergraph.

Member Function Documentation

init()

template<typename Gnl , typename GainCalc , class Derived >

auto FMGainMgr< Gnl, GainCalc, Derived >::init

(

std::span< const std::uint8_t >

part

)

-> int

Initializes the FMGainMgr with the given partition information.

Parameters

[in]

part

The partition information to initialize the FMGainMgr with.

Returns

int The result of the initialization.

is_empty()

template<typename Gnl , typename GainCalc , class Derived >

auto FMGainMgr< Gnl, GainCalc, Derived >::is_empty

(

)

const -> bool

Checks if all the gain buckets are empty.

Returns

true If all the gain buckets are empty.

false If any of the gain buckets are not empty.

is_empty_togo()

template<typename Gnl , typename GainCalc , class Derived >

auto FMGainMgr< Gnl, GainCalc, Derived >::is_empty_togo ( uint8_t  to_part ) const -> bool

inline

Checks if the gain bucket for the given partition is empty.

Parameters

[in]

to_part

The partition to check.

Returns

true If the gain bucket for the given partition is empty.

false If the gain bucket for the given partition is not empty.

select()

template<typename Gnl , typename GainCalc , class Derived >

auto FMGainMgr< Gnl, GainCalc, Derived >::select

(

std::span< const std::uint8_t >

part

)

-> std::pair< MoveInfoV< node_t >, int >

Selects a vertex to move and computes the associated gain.

Evaluates candidate vertices across all partitions, applies constraint checking, and returns the best legal move with its gain value.

Parameters

[in]

part

The current partition information.

Returns

Pair containing the selected move info and the total gain

select_togo()

template<typename Gnl , typename GainCalc , class Derived >

auto FMGainMgr< Gnl, GainCalc, Derived >::select_togo

(

uint8_t

to_part

)

-> std::pair< node_t, int >

Selects a node to move to the given partition.

Parameters

[in]

to_part

The partition to select a node to move to.

Returns

std::pair<node_t, int> A pair containing the selected node and the gain of moving that node.

update_move()

template<typename Gnl , typename GainCalc , class Derived >

auto FMGainMgr< Gnl, GainCalc, Derived >::update_move	(	std::span< const std::uint8_t >	part,
		const MoveInfoV< node_t > &	move_info_v
	)		-> void

Updates the gain information for the given set of moves.

Parameters

[in]	part	The current partition information.
[in]	move_info_v	The set of moves to update the gain information for.

Member Data Documentation

gain_bucket

template<typename Gnl , typename GainCalc , class Derived >

std::vector<BPQueue<node_t> > FMGainMgr< Gnl, GainCalc, Derived >::gain_bucket

protected

Gain buckets for each partition (used in bucket-based gain management)

gain_calc

template<typename Gnl , typename GainCalc , class Derived >

GainCalc FMGainMgr< Gnl, GainCalc, Derived >::gain_calc

Gain calculator instance.

hyprgraph

template<typename Gnl , typename GainCalc , class Derived >

const Gnl& FMGainMgr< Gnl, GainCalc, Derived >::hyprgraph

protected

Reference to the hypergraph being partitioned.

num_parts

template<typename Gnl , typename GainCalc , class Derived >

std::uint8_t FMGainMgr< Gnl, GainCalc, Derived >::num_parts

protected

Number of partitions.

waiting_list

template<typename Gnl , typename GainCalc , class Derived >

Dllist<std::pair<node_t, uint32_t> > FMGainMgr< Gnl, GainCalc, Derived >::waiting_list {std::make_pair(node_t{}, uint32_t(0))}

protected

Waiting list for vertices awaiting movement.

---

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

• ckpttn/FMGainMgr.hpp