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

EdgeBalancedVertexCut.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_EDGEBALANCEDVERTEXCUT_H__
21 #define __CXXGRAPH_PARTITIONING_EDGEBALANCEDVERTEXCUT_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 EdgeBalancedVertexCut : public PartitionStrategy<T>
40 {
41 private:
42 Globals GLOBALS;
43
44 public:
45 explicit EdgeBalancedVertexCut(Globals &G);
46 ~EdgeBalancedVertexCut();
47
48 void performStep(const Edge<T> &e, PartitionState<T> &Sstate);
49 };
50 template <typename T>
51 EdgeBalancedVertexCut<T>::EdgeBalancedVertexCut(Globals &G) : GLOBALS(G)
52 {
53 //this->GLOBALS = G;
54 }
55 template <typename T>
56 EdgeBalancedVertexCut<T>::~EdgeBalancedVertexCut()
57 {
58 }
59 template <typename T>
60 void EdgeBalancedVertexCut<T>::performStep(const Edge<T> &e, PartitionState<T> &state)
61 {
62
63 int P = GLOBALS.numberOfPartition;
64 auto nodePair = e.getNodePair();
65 int u = nodePair.first->getId();
66 int v = nodePair.second->getId();
67
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
102 //*** Check which partition has the less load
103 int MIN_LOAD = state.getMachineLoad(0);
104 int machine_id = 0;
105 double MAX_SCORE = 0.0;
106
107 for (int m = 0; m < P; m++)
108 {
109 int load = state.getMachineLoad(m);
110 if ( load <= MIN_LOAD ){
111 MIN_LOAD = load;
112 machine_id = m;
113 }
114 }
115 try
116 {
117 CoordinatedPartitionState<T> &cord_state = dynamic_cast<CoordinatedPartitionState<T> &>(state);
118 //NEW UPDATE RECORDS RULE TO UPFDATE THE SIZE OF THE PARTITIONS EXPRESSED AS THE NUMBER OF VERTICES THEY CONTAINS
119 if (!u_record->hasReplicaInPartition(machine_id))
120 {
121 u_record->addPartition(machine_id);
122 cord_state.incrementMachineLoadVertices(machine_id);
123 }
124 if (!v_record->hasReplicaInPartition(machine_id))
125 {
126 v_record->addPartition(machine_id);
127 cord_state.incrementMachineLoadVertices(machine_id);
128 }
129 }
130 catch (const std::bad_cast& e)
131 {
132 // use employee's member functions
133 //1-UPDATE RECORDS
134 if (!u_record->hasReplicaInPartition(machine_id))
135 {
136 u_record->addPartition(machine_id);
137 }
138 if (!v_record->hasReplicaInPartition(machine_id))
139 {
140 v_record->addPartition(machine_id);
141 }
142 }
143
144 //2-UPDATE EDGES
145 state.incrementMachineLoad(machine_id, &e);
146
147 //3-UPDATE DEGREES
148 u_record->incrementDegree();
149 v_record->incrementDegree();
150
151 //*** RELEASE LOCK
152 u_record->releaseLock();
153 v_record->releaseLock();
154 return;
155 }
156 }
157 }
158
159 #endif // __CXXGRAPH_PARTITIONING_EDGEBALANCEDVERTEXCUT_H__
CXXGRAPH::Edge
Definition: Edge.hpp:39
CXXGRAPH::PARTITIONING::EdgeBalancedVertexCut
A Vertex Cut Partioning Algorithm that assign an edge in the partition with less load.
Definition: EdgeBalancedVertexCut.hpp:40
CXXGRAPH::PARTITIONING::Globals
Definition: Globals.hpp:32
CXXGRAPH::PARTITIONING::PartitionState
Definition: PartitionState.hpp:33
CXXGRAPH::PARTITIONING::PartitionStrategy
Definition: PartitionStrategy.hpp:34