Limbo
|
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 | |
Implementation of FM partitioning algorithm.
Only support two partitions
NodeType | indicates type of nodes in the graph |
NetWeightType | type of net weight values |
|
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.
Iterator | iterator of net array, dereference of which must be type of node |
weight | weight of nets |
first,last | begin and end iterator of net array |
|
inline |
|
inline |
|
inline |
|
inlineprotected |
|
inlineprotected |
one pass of moving nodes
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 |