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

EBV.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_EBV_H__
21 #define __CXXGRAPH_PARTITIONING_EBV_H__
22
23 #pragma once
24
25 #include "Partitioning/Utility/Globals.hpp"
26 #include "Edge/Edge.hpp"
27 #include "PartitionStrategy.hpp"
28 #include <unordered_map>
29 #include <chrono>
30
31 namespace CXXGRAPH
32 {
33 namespace PARTITIONING
34 {
39 template <typename T>
40 class EBV : public PartitionStrategy<T>
41 {
42 private:
43 Globals GLOBALS;
44
45 public:
46 explicit EBV(Globals &G);
47 ~EBV();
48
49 void performStep(const Edge<T> &e, PartitionState<T> &Sstate);
50 };
51 template <typename T>
52 EBV<T>::EBV(Globals &G) : GLOBALS(G)
53 {
54 //this->GLOBALS = G;
55 }
56 template <typename T>
57 EBV<T>::~EBV()
58 {
59 }
60 template <typename T>
61 void EBV<T>::performStep(const Edge<T> &e, PartitionState<T> &state)
62 {
63 GLOBALS.edgeAnalyzed++;
64
65 int P = GLOBALS.numberOfPartition;
66 double alpha = GLOBALS.param1;
67 double beta = GLOBALS.param2;
68 unsigned long long edgeCardinality = GLOBALS.edgeCardinality;
69 unsigned long long vertexCardinality = GLOBALS.vertexCardinality;
70 auto nodePair = e.getNodePair();
71 int u = nodePair.first->getId();
72 int v = nodePair.second->getId();
73
74 std::shared_ptr<Record<T>> u_record = state.getRecord(u);
75 std::shared_ptr<Record<T>> v_record = state.getRecord(v);
76
77 //*** ASK FOR LOCK
78 bool locks_taken = false;
79 while (!locks_taken)
80 {
81 srand((unsigned)time(NULL));
82 int usleep_time = 2;
83 while (!u_record->getLock())
84 {
85 std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
86 usleep_time = (int)pow(usleep_time, 2);
87 }
88 usleep_time = 2;
89 if (u != v)
90 {
91 while (!v_record->getLock())
92 {
93 std::this_thread::sleep_for(std::chrono::microseconds(usleep_time));
94 usleep_time = (int)pow(usleep_time, 2);
95
96 if (usleep_time > GLOBALS.SLEEP_LIMIT)
97 {
98 u_record->releaseLock();
99 performStep(e, state);
100 return;
101 } //TO AVOID DEADLOCK
102 }
103 }
104 locks_taken = true;
105 }
106 //*** LOCK TAKEN
107 int machine_id = -1;
108
109 //*** COMPUTE SCORES, FIND MIN SCORE, AND COMPUTE CANDIDATES PARTITIONS
110 std::map<int, double> eva;
111 auto u_partition = u_record->getPartitions();
112 auto v_partition = v_record->getPartitions();
113 auto optimalEdgesNumber = (double)edgeCardinality / (double)P;
114 auto optimalVerticesNumber = (double)vertexCardinality / (double)P;
115 for (int i = 0; i < P; i++)
116 {
117 eva[i] = 0;
118 if (u_partition.empty() || u_partition.find(i) == u_partition.end())
119 {
120 eva[i] += 1;
121 }
122 if (v_partition.empty() || v_partition.find(i) == v_partition.end())
123 {
124 eva[i] += 1;
125 }
126 eva[i] += alpha * (state.getMachineLoad(i) / optimalEdgesNumber) + beta * (state.getMachineLoadVertices(i) / optimalVerticesNumber);
127 }
128 //find min between eva
129 double min = eva.at(0);
130 machine_id = 0;
131 for (auto &it : eva)
132 {
133 if (it.second < min)
134 {
135 min = it.second;
136 machine_id = it.first;
137 }
138 }
139 try
140 {
141 CoordinatedPartitionState<T> &cord_state = dynamic_cast<CoordinatedPartitionState<T> &>(state);
142 //NEW UPDATE RECORDS RULE TO UPFDATE THE SIZE OF THE PARTITIONS EXPRESSED AS THE NUMBER OF VERTICES THEY CONTAINS
143 if (!u_record->hasReplicaInPartition(machine_id))
144 {
145 u_record->addPartition(machine_id);
146 cord_state.incrementMachineLoadVertices(machine_id);
147 }
148 if (!v_record->hasReplicaInPartition(machine_id))
149 {
150 v_record->addPartition(machine_id);
151 cord_state.incrementMachineLoadVertices(machine_id);
152 }
153 }
154 catch (const std::bad_cast &e)
155 {
156 // use employee's member functions
157 //1-UPDATE RECORDS
158 if (!u_record->hasReplicaInPartition(machine_id))
159 {
160 u_record->addPartition(machine_id);
161 }
162 if (!v_record->hasReplicaInPartition(machine_id))
163 {
164 v_record->addPartition(machine_id);
165 }
166 }
167
168 //2-UPDATE EDGES
169 state.incrementMachineLoad(machine_id, &e);
170
171 //3-UPDATE DEGREES
172 u_record->incrementDegree();
173 v_record->incrementDegree();
174
175 //*** RELEASE LOCK
176 u_record->releaseLock();
177 v_record->releaseLock();
178 return;
179 }
180 }
181 }
182
183 #endif // __CXXGRAPH_PARTITIONING_EBV_H__
CXXGRAPH::Edge
Definition: Edge.hpp:39
CXXGRAPH::PARTITIONING::EBV
A Vertex Cut Partioning Algorithm ( as described by this paper https://arxiv.org/abs/2010....
Definition: EBV.hpp:41
CXXGRAPH::PARTITIONING::Globals
Definition: Globals.hpp:32
CXXGRAPH::PARTITIONING::PartitionState
Definition: PartitionState.hpp:33
CXXGRAPH::PARTITIONING::PartitionStrategy
Definition: PartitionStrategy.hpp:34