limbo::algorithms::partition::FMMultiWay< GainCalcType > Class Template Reference

#include <FMMultiWay.h>

Classes
class	VertexMove
	a class denotes movement of vertex More...

Public Types
typedef GainCalcType	gain_calc_type
typedef gain_calc_type::value_type	gain_value_type

Public Member Functions
	FMMultiWay (gain_calc_type const &gc, int tn, signed char tp)
	constructor More...
void	set_partition (int v, signed char p)
	set vertex v to partition p More...
template<typename Iterator >
void	set_partitions (Iterator first, Iterator last)
	set partitions More...
signed char	partition (int v) const
	get partition of a vertex More...
void	operator() ()
	API to run the algorithm.

Protected Member Functions
void	run ()
	kernel function to run the algorithm
void	find_candidate (int &cv, signed char &cp, gain_value_type &max_gain) const
void	best_kth_move (int &k, gain_value_type &improve) const
void	revert_to_kth_move (int k)
void	reset ()
	reset movements and fixed flags

Protected Attributes
gain_calc_type const &	m_gain_calc
	function object to calculate gains
int	m_num_vertice
	total number of vertices
int	m_num_partitions
	total number of partitions
std::vector< signed char >	m_vPartition
	an array storing partition of each vertex
std::vector< bool >	m_vFixed
	whehter fixed during current iteration
std::vector< VertexMove >	m_vVertexMove
	record vertex movement during each iteration

Detailed Description

template<typename GainCalcType>
class limbo::algorithms::partition::FMMultiWay< GainCalcType >

Assume vertices are represented by 0, 1, ... N array. Partitions are 0, 1, ... P array. Negative partition id denotes no partition assigned.

Template Parameters

GainCalcType

a function object that calculate gains, refer to limbo::algorithms::coloring::SDPColoringCsdp::FMGainCalcType for example.

Definition at line 31 of file FMMultiWay.h.

Constructor & Destructor Documentation

template<typename GainCalcType>

limbo::algorithms::partition::FMMultiWay< GainCalcType >::FMMultiWay ( gain_calc_type const &  gc, int  tn, signed char  tp  )

inline

constructor

Parameters

gc	function object of gain calculator
tn	number of vertices
tp	number of partitions

Definition at line 57 of file FMMultiWay.h.

Member Function Documentation

template<typename GainCalcType>

void limbo::algorithms::partition::FMMultiWay< GainCalcType >::best_kth_move ( int &  k, gain_value_type &  improve  ) const

protected

find best kth movement

Parameters

k	index of movement
improve	cumulative improvement at kth movement

Definition at line 133 of file FMMultiWay.h.

template<typename GainCalcType>

void limbo::algorithms::partition::FMMultiWay< GainCalcType >::find_candidate ( int &  cv, signed char &  cp, gain_value_type &  max_gain  ) const

protected

traverse all vertices and partitions for the candidate with best gain

Parameters

cv	find vertex to move
cp	target partition
max_gain	best gain of the movement

Definition at line 109 of file FMMultiWay.h.

template<typename GainCalcType>

signed char limbo::algorithms::partition::FMMultiWay< GainCalcType >::partition ( int  v ) const

inline

get partition of a vertex

Parameters

v

vertex

Returns

partition

Definition at line 78 of file FMMultiWay.h.

template<typename GainCalcType >

void limbo::algorithms::partition::FMMultiWay< GainCalcType >::revert_to_kth_move ( int  k )

protected

revert to kth movement

Parameters

k	index of movement

Definition at line 150 of file FMMultiWay.h.

template<typename GainCalcType>

void limbo::algorithms::partition::FMMultiWay< GainCalcType >::set_partition ( int  v, signed char  p  )

inline

set vertex v to partition p

Parameters

v	vertex
p	partition

Definition at line 69 of file FMMultiWay.h.

template<typename GainCalcType>

template<typename Iterator >

void limbo::algorithms::partition::FMMultiWay< GainCalcType >::set_partitions ( Iterator  first, Iterator  last  )

inline

set partitions

Template Parameters

Iterator

iterator to the array of partitions

Parameters

first,last

begin and end iterator to the array of partitions

Definition at line 74 of file FMMultiWay.h.

---

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

• /Users/yibolin/Documents/Projects/Limbo/limbo/algorithms/partition/FMMultiWay.h