Implementation of FM partitioning algorithm. More...

#include <FM.h>

Classes
class	FM_node_type
	node type for the algorithm More...
class	FM_net_type
	net type for the algorithm More...
struct	compare_type1
	compare function object More...
struct	compare_type2
	compare function object More...
class	gain_bucket_type
	gain bucket type More...

Public Types

typedef NodeType	node_type
typedef NetWeightType	net_weight_type
typedef FM_node_traits< node_type >::node_weight_type	node_weight_type

Public Member Functions
	FM ()
	constructor
	~FM ()
	destructor
bool	add_node (node_type *pNode, int initialPartition)
	add node
template<typename Iterator>
bool	add_net (net_weight_type const &weight, Iterator first, Iterator last)
	add nets
net_weight_type	cutsize () const
net_weight_type	operator() (double ratio1, double ratio2)
void	print () const
	print function
void	print_connection () const
	print connection
void	print_node () const
	print node

Protected Member Functions
net_weight_type	run (double ratio1, double ratio2)
	kernel function to run the algorithm
pair< net_weight_type, int >	single_pass (double ratio1, double ratio2, int target_cnt)
	one pass of moving nodes

Protected Attributes
unordered_map< node_type , FM_node_type >	m_hNode
	FM nodes.
vector< FM_net_type * >	m_vNet
	FM nets.
gain_bucket_type	m_gain_bucket
	gain buckets

Detailed Description

template<typename NodeType, typename NetWeightType = double>
class limbo::algorithms::partition::FM< NodeType, NetWeightType >

Implementation of FM partitioning algorithm.

Only support two partitions

Template Parameters

NodeType	indicates type of nodes in the graph
NetWeightType	type of net weight values

Definition at line 72 of file FM.h.

Member Typedef Documentation

◆ net_weight_type

template<typename NodeType, typename NetWeightType = double>

typedef NetWeightType limbo::algorithms::partition::FM< NodeType, NetWeightType >::net_weight_type

Definition at line 77 of file FM.h.

◆ node_type

template<typename NodeType, typename NetWeightType = double>

typedef NodeType limbo::algorithms::partition::FM< NodeType, NetWeightType >::node_type

Definition at line 76 of file FM.h.

◆ node_weight_type

template<typename NodeType, typename NetWeightType = double>

typedef FM_node_traits<node_type>::node_weight_type limbo::algorithms::partition::FM< NodeType, NetWeightType >::node_weight_type

Definition at line 78 of file FM.h.

Constructor & Destructor Documentation

◆ FM()

template<typename NodeType, typename NetWeightType = double>

limbo::algorithms::partition::FM< NodeType, NetWeightType >::FM ( )

inline

constructor

Definition at line 319 of file FM.h.

◆ ~FM()

template<typename NodeType, typename NetWeightType = double>

limbo::algorithms::partition::FM< NodeType, NetWeightType >::~FM ( )

inline

destructor

Definition at line 321 of file FM.h.

Member Function Documentation

◆ add_net()

template<typename NodeType, typename NetWeightType = double>

template<typename Iterator>

bool limbo::algorithms::partition::FM< NodeType, NetWeightType >::add_net	(	net_weight_type const &	weight,
		Iterator	first,
		Iterator	last )

inline

add nets

This function must be called after all nodes are inserted. If C++11 is allowed, we can extend it to variant length arguments.

Template Parameters

Iterator iterator of net array, dereference of which must be type of node

Parameters

weight	weight of nets
first,last	begin and end iterator of net array

Returns: whehter a net is successfully added

Definition at line 354 of file FM.h.

◆ add_node()

template<typename NodeType, typename NetWeightType = double>

bool limbo::algorithms::partition::FM< NodeType, NetWeightType >::add_node	(	node_type *	pNode,
		int	initialPartition )

inline

add node

Parameters

pNode	a node
initialPartition	initial partition, 0 or 1

Returns: whehter insertion is successful

Definition at line 334 of file FM.h.

◆ cutsize()

template<typename NodeType, typename NetWeightType = double>

net_weight_type limbo::algorithms::partition::FM< NodeType, NetWeightType >::cutsize ( ) const

inline

Returns: cut size of current partition

Definition at line 380 of file FM.h.

◆ operator()()

template<typename NodeType, typename NetWeightType = double>

net_weight_type limbo::algorithms::partition::FM< NodeType, NetWeightType >::operator()	(	double	ratio1,
		double	ratio2 )

inline

Top api for FM

Parameters

ratio1	minimum target ratio for partition 0 over partition 1
ratio2	maximum target ratio for partition 0 over partition 1

Returns: final cutsize after partition

Definition at line 392 of file FM.h.

◆ print()

template<typename NodeType, typename NetWeightType = double>

void limbo::algorithms::partition::FM< NodeType, NetWeightType >::print ( ) const

inline

print function

Definition at line 397 of file FM.h.

◆ print_connection()

template<typename NodeType, typename NetWeightType = double>

void limbo::algorithms::partition::FM< NodeType, NetWeightType >::print_connection ( ) const

inline

print connection

Definition at line 420 of file FM.h.

◆ print_node()

template<typename NodeType, typename NetWeightType = double>

void limbo::algorithms::partition::FM< NodeType, NetWeightType >::print_node ( ) const

inline

print node

Definition at line 440 of file FM.h.

◆ run()

template<typename NodeType, typename NetWeightType = double>

net_weight_type limbo::algorithms::partition::FM< NodeType, NetWeightType >::run	(	double	ratio1,
		double	ratio2 )

inlineprotected

kernel function to run the algorithm

Parameters

ratio1	minimum target ratio for partition 0 over partition 1
ratio2	maximum target ratio for partition 0 over partition 1

Returns: , final cut size

Definition at line 463 of file FM.h.

◆ single_pass()

template<typename NodeType, typename NetWeightType = double>

pair< net_weight_type, int > limbo::algorithms::partition::FM< NodeType, NetWeightType >::single_pass	(	double	ratio1,
		double	ratio2,
		int	target_cnt )

inlineprotected

one pass of moving nodes

Parameters

ratio1	minimum target ratio for partition 0 over partition 1
ratio2	maximum target ratio for partition 0 over partition 1
target_cnt	generalized iteration count, if it is negative, then run in trial mode

Returns: pair of best cut size and iteration count

Definition at line 496 of file FM.h.

Member Data Documentation

◆ m_gain_bucket

template<typename NodeType, typename NetWeightType = double>

gain_bucket_type limbo::algorithms::partition::FM< NodeType, NetWeightType >::m_gain_bucket

protected

gain buckets

Definition at line 693 of file FM.h.

◆ m_hNode

template<typename NodeType, typename NetWeightType = double>

unordered_map<node_type*, FM_node_type*> limbo::algorithms::partition::FM< NodeType, NetWeightType >::m_hNode

protected

FM nodes.

Definition at line 691 of file FM.h.

◆ m_vNet

template<typename NodeType, typename NetWeightType = double>

vector<FM_net_type*> limbo::algorithms::partition::FM< NodeType, NetWeightType >::m_vNet

protected

FM nets.

Definition at line 692 of file FM.h.

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

/home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/algorithms/partition/FM.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ net_weight_type

◆ node_type

◆ node_weight_type

Constructor & Destructor Documentation

◆ FM()

◆ ~FM()

Member Function Documentation

◆ add_net()

◆ add_node()

◆ cutsize()

◆ operator()()

◆ print()

◆ print_connection()

◆ print_node()

◆ run()

◆ single_pass()

Member Data Documentation

◆ m_gain_bucket

◆ m_hNode

◆ m_vNet