20 #ifndef __CXXGRAPH_PARTITIONING_HDRF_H__
21 #define __CXXGRAPH_PARTITIONING_HDRF_H__
25 #include "Partitioning/Utility/Globals.hpp"
26 #include "Edge/Edge.hpp"
27 #include "PartitionStrategy.hpp"
31 namespace PARTITIONING
55 void HDRF<T>::performStep(Edge<T> &e, PartitionState<T> &state)
58 int P = GLOBALS.numberOfPartition;
63 Record u_record = state.getRecord(u);
64 Record v_record = state.getRecord(v);
68 while (!u_record.getLock())
71 sleep = (int)pow(sleep_time, 2);
74 while (!v_record.getLock())
77 sleep = (int)pow(sleep_time, 2);
78 if (sleep_time > GLOBALS.SLEEP_LIMIT)
80 u_record.releaseLock();
81 performStep(e, state);
90 int MIN_LOAD = state.getMinLoad();
91 int MAX_LOAD = state.getMaxLoad();
94 std::list<int> candidates;
95 double MAX_SCORE = 0.0;
97 for (
int m = 0; m < P; m++)
100 int degree_u = u_record.getDegree() + 1;
101 int degree_v = v_record.getDegree() + 1;
102 int SUM = degree_u + degree_v;
105 if (u_record.hasReplicaInPartition(m))
111 if (v_record.hasReplicaInPartition(m))
117 int load = state.getMachineLoad(m);
118 double bal = (MAX_LOAD - load);
119 bal /= (epsilon + MAX_LOAD - MIN_LOAD);
124 double SCORE_m = fu + fv + GLOBALS.lambda * bal;
127 std::cout <<
"ERRORE: SCORE_m<0" << std::endl;
128 std::cout <<
"fu: " << fu << std::endl;
129 std::cout <<
"fv: " << fv << std::endl;
130 std::cout <<
"GLOBALS.LAMBDA: " << GLOBALS.lambda << std::endl;
131 std::cout <<
"bal: " << bal << std::endl;
134 if (SCORE_m > MAX_SCORE)
138 candidates.push_back(m);
140 else if (SCORE_m == MAX_SCORE)
142 candidates.push_back(m);
147 if (candidates.empty())
149 std::cout <<
"ERROR: GreedyObjectiveFunction.performStep -> candidates.isEmpty()" << std::endl;
150 std::cout <<
"MAX_SCORE: " << MAX_SCORE << std::endl;
158 int choice = rand() % candidates.size();
164 CoordinatedPartitionState<T> &cord_state =
dynamic_cast<CoordinatedPartitionState<T> &
>(state);
166 if (!u_record.hasReplicaInPartition(machine_id))
168 u_record.addPartition(machine_id);
169 cord_state.incrementMachineLoadVertices(machine_id);
171 if (!v_record.hasReplicaInPartition(machine_id))
173 v_record.addPartition(machine_id);
174 cord_state.incrementMachineLoadVertices(machine_id);
177 catch (std::bad_cast)
181 if (!u_record.hasReplicaInPartition(machine_id))
183 u_record.addPartition(machine_id);
185 if (!v_record.hasReplicaInPartition(machine_id))
187 v_record.addPartition(machine_id);
192 state.incrementMachineLoad(machine_id, e);
195 u_record.incrementDegree();
196 v_record.incrementDegree();
199 u_record.releaseLock();
200 v_record.releaseLock();
Definition: Globals.hpp:32
Definition: PartitionState.hpp:31
Definition: PartitionStrategy.hpp:34