FMBiGainMgr< Gnl > Class Template Reference

Binary Fiduccia-Mattheyses Gain Manager. More...

#include <FMBiGainMgr.hpp>

Inheritance diagram for FMBiGainMgr< Gnl >:

Collaboration diagram for FMBiGainMgr< Gnl >:

Public Types
using	Base = FMGainMgr< Gnl, FMBiGainCalc< Gnl >, FMBiGainMgr< Gnl > >
using	GainCalc_ = FMBiGainCalc< Gnl >
using	node_t = typename Gnl::node_t

Public Member Functions
	FMBiGainMgr (const Gnl &hyprgraph)
	Construct a new FMBiGainMgr object.
	FMBiGainMgr (const Gnl &hyprgraph, std::uint8_t)
	Constructs a new FMBiGainMgr object with the given hypergraph.
auto	init (std::span< const std::uint8_t > part) -> int
	Initializes the FMBiGainMgr object with the given partition.
auto	modify_key (const node_t &w, std::uint8_t part_w, int key) -> void
	Modifies the key for the given vertex in the gain bucket of the opposite partition.
auto	update_move_v (const MoveInfoV< node_t > &move_info_v, int gain) -> void
	Updates the move information for the given vertex and gain.
auto	lock (uint8_t whichPart, const node_t &v) -> void
	Locks the vertex in the specified partition.
auto	lock_all (uint8_t from_part, const node_t &v) -> void
	Locks the vertex in the opposite partition from the specified partition.
Public Member Functions inherited from FMGainMgr< Gnl, FMBiGainCalc< Gnl >, FMBiGainMgr< Gnl > >
	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.

Additional Inherited Members
Public Attributes inherited from FMGainMgr< Gnl, FMBiGainCalc< Gnl >, FMBiGainMgr< Gnl > >
FMBiGainCalc< Gnl >	gain_calc
	Gain calculator instance.
Protected Attributes inherited from FMGainMgr< Gnl, FMBiGainCalc< Gnl >, FMBiGainMgr< Gnl > >
Dllist< std::pair< node_t, uint32_t > >	waiting_list
	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>
class FMBiGainMgr< Gnl >

Binary Fiduccia-Mattheyses Gain Manager.

The FMBiGainMgr class is a gain manager specialized for 2-way partitioning. It uses the FM (Fiduccia-Mattheyses) algorithm to compute and manage gains for moving vertices between two partitions.

Template Parameters

Gnl	The hypergraph type

Member Typedef Documentation

Base

template<typename Gnl >

using FMBiGainMgr< Gnl >::Base = FMGainMgr<Gnl, FMBiGainCalc<Gnl>, FMBiGainMgr<Gnl> >

GainCalc_

template<typename Gnl >

using FMBiGainMgr< Gnl >::GainCalc_ = FMBiGainCalc<Gnl>

node_t

template<typename Gnl >

using FMBiGainMgr< Gnl >::node_t = typename Gnl::node_t

Constructor & Destructor Documentation

FMBiGainMgr() [1/2]

template<typename Gnl >

FMBiGainMgr< Gnl >::FMBiGainMgr ( const Gnl &  hyprgraph )

inlineexplicit

Construct a new FMBiGainMgr object.

Parameters

[in]

hyprgraph

The hypergraph to be used for the FMBiGainMgr object

FMBiGainMgr() [2/2]

template<typename Gnl >

FMBiGainMgr< Gnl >::FMBiGainMgr ( const Gnl &  hyprgraph, std::uint8_t    )

inline

Constructs a new FMBiGainMgr object with the given hypergraph.

Parameters

[in]

hyprgraph

The hypergraph to be used for the FMBiGainMgr object.

Member Function Documentation

init()

template<typename Gnl >

auto FMBiGainMgr< Gnl >::init

(

std::span< const std::uint8_t >

part

)

-> int

Initializes the FMBiGainMgr object with the given partition.

Parameters

[in]

part

The partition to initialize the FMBiGainMgr object with.

Returns

int The result of the initialization.

lock()

template<typename Gnl >

auto FMBiGainMgr< Gnl >::lock ( uint8_t  whichPart, const node_t &  v  ) -> void

inline

Locks the vertex in the specified partition.

Parameters

[in]	whichPart	The partition to lock the vertex in.
[in]	v	The vertex to lock.

lock_all()

template<typename Gnl >

auto FMBiGainMgr< Gnl >::lock_all ( uint8_t  from_part, const node_t &  v  ) -> void

inline

Locks the vertex in the opposite partition from the specified partition.

Parameters

[in]	from_part	The partition that the vertex is currently in.
[in]	v	The vertex to lock.

modify_key()

template<typename Gnl >

auto FMBiGainMgr< Gnl >::modify_key ( const node_t &  w, std::uint8_t  part_w, int  key  ) -> void

inline

Modifies the key for the given vertex in the gain bucket of the opposite partition.

Parameters

[in]	w	The vertex whose key is to be modified.
[in]	part_w	The partition that the vertex belongs to.
[in]	key	The new key value to be set for the vertex.

update_move_v()

template<typename Gnl >

auto FMBiGainMgr< Gnl >::update_move_v ( const MoveInfoV< node_t > &  move_info_v, int  gain  ) -> void

inline

Updates the move information for the given vertex and gain.

Parameters

[in]	move_info_v	The move information for the vertex.
[in]	gain	The gain associated with the move.

---

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

• ckpttn/FMBiGainCalc.hpp
• ckpttn/FMBiGainMgr.hpp