limbo::algorithms::partition::FM< NodeType, NetWeightType > Class Template Reference

Implementation of FM partitioning algorithm. More...

#include <FM.h>

Classes
struct	compare_type1
	compare function object More...
struct	compare_type2
	compare function object More...
class	FM_net_type
	net type for the algorithm More...
class	FM_node_type
	node type for the algorithm 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 More...
template<typename Iterator >
bool	add_net (net_weight_type const &weight, Iterator first, Iterator last)
	add nets More...
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 More...
pair< net_weight_type, int >	single_pass (double ratio1, double ratio2, int target_cnt)
	one pass of moving nodes More...

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 Function Documentation

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.

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.

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.

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.

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.

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.

---

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

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