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(
const Edge<T> &e, PartitionState<T> &state)
58 int P = GLOBALS.numberOfPartition;
60 auto nodePair = e.getNodePair();
61 int u = nodePair.first->getId();
62 int v = nodePair.second->getId();
64 Record<T> &u_record = state.getRecord(u);
65 Record<T> &v_record = state.getRecord(v);
69 while (!u_record.getLock())
71 std::cout <<
"Waiting for lock on node " << u << std::endl;
73 sleep_time = (int)pow(sleep_time, 2);
75 std::cout <<
"Lock Taken for " << u << std::endl;
77 while (!v_record.getLock())
79 std::cout <<
"Waiting for lock on node " << v << std::endl;
81 sleep_time = (int)pow(sleep_time, 2);
82 if (sleep_time > GLOBALS.SLEEP_LIMIT)
84 u_record.releaseLock();
85 performStep(e, state);
90 std::cout <<
"Lock Taken for " << v << std::endl;
94 int MIN_LOAD = state.getMinLoad();
95 int MAX_LOAD = state.getMaxLoad();
98 std::vector<int> candidates;
99 double MAX_SCORE = 0.0;
101 for (
int m = 0; m < P; m++)
104 int degree_u = u_record.getDegree() + 1;
105 int degree_v = v_record.getDegree() + 1;
106 int SUM = degree_u + degree_v;
109 if (u_record.hasReplicaInPartition(m))
115 if (v_record.hasReplicaInPartition(m))
121 int load = state.getMachineLoad(m);
122 double bal = (MAX_LOAD - load);
123 bal /= (epsilon + MAX_LOAD - MIN_LOAD);
128 double SCORE_m = fu + fv + GLOBALS.lambda * bal;
131 std::cout <<
"ERRORE: SCORE_m<0" << std::endl;
132 std::cout <<
"fu: " << fu << std::endl;
133 std::cout <<
"fv: " << fv << std::endl;
134 std::cout <<
"GLOBALS.LAMBDA: " << GLOBALS.lambda << std::endl;
135 std::cout <<
"bal: " << bal << std::endl;
138 if (SCORE_m > MAX_SCORE)
142 candidates.push_back(m);
144 else if (SCORE_m == MAX_SCORE)
146 candidates.push_back(m);
151 if (candidates.empty())
153 std::cout <<
"ERROR: GreedyObjectiveFunction.performStep -> candidates.isEmpty()" << std::endl;
154 std::cout <<
"MAX_SCORE: " << MAX_SCORE << std::endl;
162 int choice = rand() % candidates.size();
163 machine_id = candidates.at(choice);
167 CoordinatedPartitionState<T> &cord_state =
dynamic_cast<CoordinatedPartitionState<T> &
>(state);
169 if (!u_record.hasReplicaInPartition(machine_id))
171 u_record.addPartition(machine_id);
172 cord_state.incrementMachineLoadVertices(machine_id);
174 if (!v_record.hasReplicaInPartition(machine_id))
176 v_record.addPartition(machine_id);
177 cord_state.incrementMachineLoadVertices(machine_id);
180 catch (std::bad_cast)
184 if (!u_record.hasReplicaInPartition(machine_id))
186 u_record.addPartition(machine_id);
188 if (!v_record.hasReplicaInPartition(machine_id))
190 v_record.addPartition(machine_id);
195 state.incrementMachineLoad(machine_id, &e);
198 u_record.incrementDegree();
199 v_record.incrementDegree();
202 u_record.releaseLock();
203 v_record.releaseLock();
Definition: Globals.hpp:32
Definition: PartitionState.hpp:33
Definition: PartitionStrategy.hpp:34