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

GreedyVertexCut.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_GREEDYVERTEXCUT_H__
21 #define __CXXGRAPH_PARTITIONING_GREEDYVERTEXCUT_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 GreedyVertexCut : public PartitionStrategy<T>
40 {
41 private:
42 Globals GLOBALS;
43
44 public:
45 explicit GreedyVertexCut(Globals &G);
46 ~GreedyVertexCut();
47
48 void performStep(const Edge<T> &e, PartitionState<T> &Sstate);
49 };
50 template <typename T>
51 GreedyVertexCut<T>::GreedyVertexCut(Globals &G) : GLOBALS(G)
52 {
53 //this->GLOBALS = G;
54 }
55 template <typename T>
56 GreedyVertexCut<T>::~GreedyVertexCut()
57 {
58 }
59 template <typename T>
60 void GreedyVertexCut<T>::performStep(const Edge<T> &e, PartitionState<T> &state)
61 {
62 int P = GLOBALS.numberOfPartition;
63 auto nodePair = e.getNodePair();
64 int u = nodePair.first->getId();
65 int v = nodePair.second->getId();
66
67 std::shared_ptr<Record<T>> u_record = state.getRecord(u);
68 std::shared_ptr<Record<T>> v_record = state.getRecord(v);
69
70 //*** ASK FOR LOCK
71 bool locks_taken = false;
72 while (!locks_taken)
73 {
74 srand((unsigned)time(NULL));
75 int usleep_time = 2;
76 while (!u_record->getLock())
77 {
78 std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
79 usleep_time = (int)pow(usleep_time, 2);
80 }
81 usleep_time = 2;
82 if (u != v)
83 {
84 while (!v_record->getLock())
85 {
86 std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
87 usleep_time = (int)pow(usleep_time, 2);
88
89 if (usleep_time > GLOBALS.SLEEP_LIMIT)
90 {
91 u_record->releaseLock();
92 performStep(e, state);
93 return;
94 } //TO AVOID DEADLOCK
95 }
96 }
97 locks_taken = true;
98 }
99 //*** LOCK TAKEN
100 int machine_id = -1;
101
102 //*** COMPUTE CANDIDATES PARITIONS
103 std::vector<int> candidates;
104
105 if (u_record->getPartitions().empty() && v_record->getPartitions().empty())
106 {
107 //Find the partition with min load
108 int min_load = INT_MAX;
109 int machine_id = 0;
110 for (int i = 0; i < P; i++)
111 {
112 if (state.getMachineLoad(i) < min_load)
113 {
114 min_load = state.getMachineLoad(i);
115 machine_id = i;
116 }
117 }
118 candidates.push_back(machine_id);
119 }
120 else if (!u_record->getPartitions().empty() && v_record->getPartitions().empty())
121 {
122 //Find the partition with min load in u
123 int min_load = INT_MAX;
124 int machine_id = 0;
125 for (auto &partition : u_record->getPartitions())
126 {
127 if (state.getMachineLoad(partition) < min_load)
128 {
129 min_load = state.getMachineLoad(partition);
130 machine_id = partition;
131 }
132 }
133 candidates.push_back(machine_id);
134 }
135 else if (u_record->getPartitions().empty() && !v_record->getPartitions().empty())
136 {
137 //Find the partition with min load in v
138 int min_load = INT_MAX;
139 int machine_id = 0;
140 for (auto &partition : v_record->getPartitions())
141 {
142 if (state.getMachineLoad(partition) < min_load)
143 {
144 min_load = state.getMachineLoad(partition);
145 machine_id = partition;
146 }
147 }
148 candidates.push_back(machine_id);
149 }
150 else if (!u_record->getPartitions().empty() && !v_record->getPartitions().empty())
151 {
152 //check if have intersection
153 std::set<int> intersection;
154 std::set_intersection(u_record->getPartitions().begin(), u_record->getPartitions().end(),
155 v_record->getPartitions().begin(), v_record->getPartitions().end(),
156 std::inserter(intersection, intersection.begin()));
157 if (!intersection.empty())
158 {
159 //Find the partition with min load in the intersection of u and v
160 int min_load = INT_MAX;
161 int machine_id = 0;
162 for (auto &partition : intersection)
163 {
164 if (state.getMachineLoad(partition) < min_load)
165 {
166 min_load = state.getMachineLoad(partition);
167 machine_id = partition;
168 }
169 }
170 candidates.push_back(machine_id);
171 }
172 else
173 {
174 //Find the partition with min load in the union of u and v
175 std::set<int> part_union;
176 std::set_union(u_record->getPartitions().begin(), u_record->getPartitions().end(),
177 v_record->getPartitions().begin(), v_record->getPartitions().end(),
178 std::inserter(part_union, part_union.begin()));
179 int min_load = INT_MAX;
180 int machine_id = 0;
181 for (auto &partition : part_union)
182 {
183 if (state.getMachineLoad(partition) < min_load)
184 {
185 min_load = state.getMachineLoad(partition);
186 machine_id = partition;
187 }
188 }
189 candidates.push_back(machine_id);
190 }
191 }
192
193 //*** CHECK TO AVOID ERRORS
194 if (candidates.empty())
195 {
196 std::cout << "ERROR: GreedyObjectiveFunction.performStep -> candidates.isEmpty()" << std::endl;
197 exit(-1);
198 }
199
200 //*** PICK A RANDOM ELEMENT FROM CANDIDATES
201 /* initialize random seed: */
202 unsigned int seed = (unsigned int)time(NULL);
203 srand(seed);
204 int choice = rand_r(&seed) % candidates.size();
205 machine_id = candidates.at(choice);
206 try
207 {
208 CoordinatedPartitionState<T> &cord_state = dynamic_cast<CoordinatedPartitionState<T> &>(state);
209 //NEW UPDATE RECORDS RULE TO UPFDATE THE SIZE OF THE PARTITIONS EXPRESSED AS THE NUMBER OF VERTICES THEY CONTAINS
210 if (!u_record->hasReplicaInPartition(machine_id))
211 {
212 u_record->addPartition(machine_id);
213 cord_state.incrementMachineLoadVertices(machine_id);
214 }
215 if (!v_record->hasReplicaInPartition(machine_id))
216 {
217 v_record->addPartition(machine_id);
218 cord_state.incrementMachineLoadVertices(machine_id);
219 }
220 }
221 catch (const std::bad_cast &e)
222 {
223 // use employee's member functions
224 //1-UPDATE RECORDS
225 if (!u_record->hasReplicaInPartition(machine_id))
226 {
227 u_record->addPartition(machine_id);
228 }
229 if (!v_record->hasReplicaInPartition(machine_id))
230 {
231 v_record->addPartition(machine_id);
232 }
233 }
234
235 //2-UPDATE EDGES
236 state.incrementMachineLoad(machine_id, &e);
237
238 //3-UPDATE DEGREES
239 u_record->incrementDegree();
240 v_record->incrementDegree();
241
242 //*** RELEASE LOCK
243 u_record->releaseLock();
244 v_record->releaseLock();
245 return;
246 }
247 }
248 }
249
250 #endif // __CXXGRAPH_PARTITIONING_GREEDYVERTEXCUT_H__
CXXGRAPH::Edge
Definition: Edge.hpp:39
CXXGRAPH::PARTITIONING::Globals
Definition: Globals.hpp:32
CXXGRAPH::PARTITIONING::GreedyVertexCut
A Greedy Vertex Cut Partioning Algorithm.
Definition: GreedyVertexCut.hpp:40
CXXGRAPH::PARTITIONING::PartitionState
Definition: PartitionState.hpp:33
CXXGRAPH::PARTITIONING::PartitionStrategy
Definition: PartitionStrategy.hpp:34