| CXXGraph 0.4.0 CXXGraph is a header only, that manages the Graphs and it's algorithm in C++

HDRF.hpp
1 /***********************************************************/
2 /*** ______ ____ ______ _ ***/
3 /*** / ___\ \/ /\ \/ / ___|_ __ __ _ _ __ | |__ ***/
4 /*** | | \ / \ / | _| '__/ _` | '_ \| '_ \ ***/
5 /*** | |___ / \ / \ |_| | | | (_| | |_) | | | | ***/
6 /*** \____/_/\_\/_/\_\____|_| \__,_| .__/|_| |_| ***/
7 /*** |_| ***/
8 /***********************************************************/
9 /*** Header-Only C++ Library for Graph ***/
10 /*** Representation and Algorithms ***/
11 /***********************************************************/
12 /*** Author: ZigRazor ***/
13 /*** E-Mail: zigrazor@gmail.com ***/
14 /***********************************************************/
15 /*** Collaboration: ----------- ***/
16 /***********************************************************/
17 /*** License: MPL v2.0 ***/
18 /***********************************************************/
19
20 #ifndef __CXXGRAPH_PARTITIONING_HDRF_H__
21 #define __CXXGRAPH_PARTITIONING_HDRF_H__
22
23 #pragma once
24
25 #include "Partitioning/Utility/Globals.hpp"
26 #include "Edge/Edge.hpp"
27 #include "PartitionStrategy.hpp"
28 #include <chrono>
29
30 namespace CXXGRAPH
31 {
32 namespace PARTITIONING
33 {
38 template <typename T>
39 class HDRF : public PartitionStrategy<T>
40 {
41 private:
42 Globals GLOBALS;
43
44 public:
45 explicit HDRF(Globals &G);
46 ~HDRF();
47
48 void performStep(const Edge<T> &e, PartitionState<T> &Sstate);
49 };
50 template <typename T>
51 HDRF<T>::HDRF(Globals &G) : GLOBALS(G)
52 {
53 //this->GLOBALS = G;
54 }
55 template <typename T>
56 HDRF<T>::~HDRF()
57 {
58 }
59 template <typename T>
60 void HDRF<T>::performStep(const Edge<T> &e, PartitionState<T> &state)
61 {
62 int P = GLOBALS.numberOfPartition;
63 double lambda = GLOBALS.param1;
64 double epsilon = GLOBALS.param2;
65 auto nodePair = e.getNodePair();
66 int u = nodePair.first->getId();
67 int v = nodePair.second->getId();
68 std::shared_ptr<Record<T>> u_record = state.getRecord(u);
69 std::shared_ptr<Record<T>> v_record = state.getRecord(v);
70
71 //*** ASK FOR LOCK
72 bool locks_taken = false;
73 while (!locks_taken)
74 {
75 srand((unsigned)time(NULL));
76 int usleep_time = 2;
77 while (!u_record->getLock())
78 {
79 std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
80 usleep_time = (int)pow(usleep_time, 2);
81 }
82 usleep_time = 2;
83 if (u != v)
84 {
85 while (!v_record->getLock())
86 {
87 std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
88 usleep_time = (int)pow(usleep_time, 2);
89
90 if (usleep_time > GLOBALS.SLEEP_LIMIT)
91 {
92 u_record->releaseLock();
93 performStep(e, state);
94 return;
95 } //TO AVOID DEADLOCK
96 }
97 }
98 locks_taken = true;
99 }
100 //*** LOCK TAKEN
101 int machine_id = -1;
102
103 //*** COMPUTE MAX AND MIN LOAD
104 int MIN_LOAD = state.getMinLoad();
105 int MAX_LOAD = state.getMaxLoad();
106
107 //*** COMPUTE SCORES, FIND MIN SCORE, AND COMPUTE CANDIDATES PARITIONS
108 std::vector<int> candidates;
109 double MAX_SCORE = 0.0;
110 for (int m = 0; m < P; m++)
111 {
112
113 int degree_u = u_record->getDegree() + 1;
114 int degree_v = v_record->getDegree() + 1;
115 int SUM = degree_u + degree_v;
116 double fu = 0;
117 double fv = 0;
118 if (u_record->hasReplicaInPartition(m))
119 {
120 fu = degree_u;
121 fu /= SUM;
122 fu = 1 + (1 - fu);
123 }
124 if (v_record->hasReplicaInPartition(m))
125 {
126 fv = degree_v;
127 fv /= SUM;
128 fv = 1 + (1 - fv);
129 }
130 int load = state.getMachineLoad(m);
131 double bal = (MAX_LOAD - load);
132 bal /= (epsilon + MAX_LOAD - MIN_LOAD);
133 if (bal < 0)
134 {
135 bal = 0;
136 }
137 double SCORE_m = fu + fv + lambda * bal;
138 if (SCORE_m < 0)
139 {
140 std::cout << "ERRORE: SCORE_m<0" << std::endl;
141 std::cout << "fu: " << fu << std::endl;
142 std::cout << "fv: " << fv << std::endl;
143 std::cout << "lambda: " << lambda << std::endl;
144 std::cout << "bal: " << bal << std::endl;
145 exit(-1);
146 }
147 if (SCORE_m > MAX_SCORE)
148 {
149 MAX_SCORE = SCORE_m;
150 candidates.clear();
151 candidates.push_back(m);
152 }
153 else if (SCORE_m == MAX_SCORE)
154 {
155 candidates.push_back(m);
156 }
157 }
158 //*** CHECK TO AVOID ERRORS
159 if (candidates.empty())
160 {
161 std::cout << "ERROR: GreedyObjectiveFunction.performStep -> candidates.isEmpty()" << std::endl;
162 std::cout << "MAX_SCORE: " << MAX_SCORE << std::endl;
163 exit(-1);
164 }
165
166 //*** PICK A RANDOM ELEMENT FROM CANDIDATES
167 /* initialize random seed: */
168 unsigned int seed = (unsigned int)time(NULL);
169 srand(seed);
170 int choice = rand_r(&seed) % candidates.size();
171 machine_id = candidates.at(choice);
172 try
173 {
174 CoordinatedPartitionState<T> &cord_state = dynamic_cast<CoordinatedPartitionState<T> &>(state);
175 //NEW UPDATE RECORDS RULE TO UPFDATE THE SIZE OF THE PARTITIONS EXPRESSED AS THE NUMBER OF VERTICES THEY CONTAINS
176 if (!u_record->hasReplicaInPartition(machine_id))
177 {
178 u_record->addPartition(machine_id);
179 cord_state.incrementMachineLoadVertices(machine_id);
180 }
181 if (!v_record->hasReplicaInPartition(machine_id))
182 {
183 v_record->addPartition(machine_id);
184 cord_state.incrementMachineLoadVertices(machine_id);
185 }
186 }
187 catch (const std::bad_cast &e)
188 {
189 // use employee's member functions
190 //1-UPDATE RECORDS
191 if (!u_record->hasReplicaInPartition(machine_id))
192 {
193 u_record->addPartition(machine_id);
194 }
195 if (!v_record->hasReplicaInPartition(machine_id))
196 {
197 v_record->addPartition(machine_id);
198 }
199 }
200
201 //2-UPDATE EDGES
202 state.incrementMachineLoad(machine_id, &e);
203
204 //3-UPDATE DEGREES
205 u_record->incrementDegree();
206 v_record->incrementDegree();
207
208 //*** RELEASE LOCK
209 u_record->releaseLock();
210 v_record->releaseLock();
211 return;
212 }
213 }
214 }
215
216 #endif // __CXXGRAPH_PARTITIONING_HDRF_H__
CXXGRAPH::Edge
Definition: Edge.hpp:39
CXXGRAPH::PARTITIONING::Globals
Definition: Globals.hpp:32
CXXGRAPH::PARTITIONING::HDRF
A Vertex Cut Partioning Algorithm ( as described by this paper https://www.fabiopetroni....
Definition: HDRF.hpp:40
CXXGRAPH::PARTITIONING::PartitionState
Definition: PartitionState.hpp:33
CXXGRAPH::PARTITIONING::PartitionStrategy
Definition: PartitionStrategy.hpp:34