12 #ifndef LIMBO_ALGORITHMS_PARTITION_FMMULTIWAY_H
13 #define LIMBO_ALGORITHMS_PARTITION_FMMULTIWAY_H
30 template <
typename GainCalcType>
35 typedef GainCalcType gain_calc_type;
36 typedef typename gain_calc_type::value_type gain_value_type;
46 VertexMove(
int v,
int op, gain_value_type g) : vertex(v), orig_partition(op), gain(g) {}
57 FMMultiWay(gain_calc_type
const& gc,
int tn,
signed char tp)
73 template <
typename Iterator>
89 void find_candidate(
int& cv,
signed char& cp, gain_value_type& max_gain)
const;
108 template <
typename GainCalcType>
113 for (
int v = 0; v != m_num_vertice; ++v)
116 if (m_vFixed[v])
continue;
117 for (
signed char p = 0; p != m_num_partitions; ++p)
120 if (p == m_vPartition[v])
continue;
121 gain_value_type cur_gain = m_gain_calc(v, m_vPartition[v], p, m_vPartition);
122 if (cur_gain > max_gain)
132 template <
typename GainCalcType>
137 gain_value_type
sum = 0;
138 for (
int i = 0; i != m_num_vertice; ++i)
140 sum += m_vVertexMove[i].gain;
149 template <
typename GainCalcType>
152 for (
int i = m_num_vertice-1; i > k; --i)
153 m_vPartition[m_vVertexMove[i].vertex] = m_vVertexMove[i].orig_partition;
156 template <
typename GainCalcType>
159 m_vFixed.assign(m_vFixed.size(),
false);
160 m_vVertexMove.clear();
163 template <
typename GainCalcType>
166 gain_value_type improve = 0;
169 for (
int i = 0; i != m_num_vertice; ++i)
173 gain_value_type gain = 0;
174 find_candidate(v, p, gain);
178 m_vVertexMove.push_back(
VertexMove(v, m_vPartition[v], gain));
184 best_kth_move(k, improve);
185 revert_to_kth_move(k);
187 }
while (improve > 0);
signed char orig_partition
original partition
signed char partition(int v) const
get partition of a vertex
std::vector< bool > m_vFixed
whehter fixed during current iteration
void revert_to_kth_move(int k)
std::vector< signed char > m_vPartition
an array storing partition of each vertex
int m_num_vertice
total number of vertices
void operator()()
API to run the algorithm.
void set_partition(int v, signed char p)
set vertex v to partition p
gain_calc_type const & m_gain_calc
function object to calculate gains
void run()
kernel function to run the algorithm
std::vector< VertexMove > m_vVertexMove
record vertex movement during each iteration
std::iterator_traits< Iterator >::value_type sum(Iterator first, Iterator last)
get summation of an array
void best_kth_move(int &k, gain_value_type &improve) const
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
void set_partitions(Iterator first, Iterator last)
set partitions
a class denotes movement of vertex
void find_candidate(int &cv, signed char &cp, gain_value_type &max_gain) const
void reset()
reset movements and fixed flags
VertexMove(int v, int op, gain_value_type g)
constructor
int m_num_partitions
total number of partitions
FMMultiWay(gain_calc_type const &gc, int tn, signed char tp)
constructor