CXXGraph  0.2.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: AGPL v3.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 
29 namespace CXXGRAPH
30 {
31  namespace PARTITIONING
32  {
33  template <typename T>
34  class HDRF : public PartitionStrategy<T>
35  {
36  private:
37  Globals GLOBALS;
38 
39  public:
40  HDRF(Globals& G);
41  ~HDRF();
42 
43  void performStep(const Edge<T> &e, PartitionState<T> &Sstate);
44  };
45  template <typename T>
46  HDRF<T>::HDRF(Globals& G) : GLOBALS(G)
47  {
48  //this->GLOBALS = G;
49  }
50  template <typename T>
51  HDRF<T>::~HDRF()
52  {
53  }
54  template <typename T>
55  void HDRF<T>::performStep(const Edge<T> &e, PartitionState<T> &state)
56  {
57 
58  int P = GLOBALS.numberOfPartition;
59  int epsilon = 1;
60  auto nodePair = e.getNodePair();
61  int u = nodePair.first->getId();
62  int v = nodePair.second->getId();
63 
64  Record<T> &u_record = state.getRecord(u);
65  Record<T> &v_record = state.getRecord(v);
66 
67  //*** ASK FOR LOCK
68  int sleep_time = 2;
69  while (!u_record.getLock())
70  {
71  std::cout << "Waiting for lock on node " << u << std::endl;
72  sleep(sleep_time);
73  sleep_time = (int)pow(sleep_time, 2);
74  }
75  std::cout << "Lock Taken for " << u << std::endl;
76  sleep_time = 2;
77  while (!v_record.getLock())
78  {
79  std::cout << "Waiting for lock on node " << v << std::endl;
80  sleep(sleep_time);
81  sleep_time = (int)pow(sleep_time, 2);
82  if (sleep_time > GLOBALS.SLEEP_LIMIT)
83  {
84  u_record.releaseLock();
85  performStep(e, state);
86  return;
87  } //TO AVOID DEADLOCK
88  }
89  //*** LOCK TAKEN
90  std::cout << "Lock Taken for " << v << std::endl;
91  int machine_id = -1;
92 
93  //*** COMPUTE MAX AND MIN LOAD
94  int MIN_LOAD = state.getMinLoad();
95  int MAX_LOAD = state.getMaxLoad();
96 
97  //*** COMPUTE SCORES, FIND MIN SCORE, AND COMPUTE CANDIDATES PARITIONS
98  std::vector<int> candidates;
99  double MAX_SCORE = 0.0;
100 
101  for (int m = 0; m < P; m++)
102  {
103 
104  int degree_u = u_record.getDegree() + 1;
105  int degree_v = v_record.getDegree() + 1;
106  int SUM = degree_u + degree_v;
107  double fu = 0;
108  double fv = 0;
109  if (u_record.hasReplicaInPartition(m))
110  {
111  fu = degree_u;
112  fu /= SUM;
113  fu = 1 + (1 - fu);
114  }
115  if (v_record.hasReplicaInPartition(m))
116  {
117  fv = degree_v;
118  fv /= SUM;
119  fv = 1 + (1 - fv);
120  }
121  int load = state.getMachineLoad(m);
122  double bal = (MAX_LOAD - load);
123  bal /= (epsilon + MAX_LOAD - MIN_LOAD);
124  if (bal < 0)
125  {
126  bal = 0;
127  }
128  double SCORE_m = fu + fv + GLOBALS.lambda * bal;
129  if (SCORE_m < 0)
130  {
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;
136  exit(-1);
137  }
138  if (SCORE_m > MAX_SCORE)
139  {
140  MAX_SCORE = SCORE_m;
141  candidates.clear();
142  candidates.push_back(m);
143  }
144  else if (SCORE_m == MAX_SCORE)
145  {
146  candidates.push_back(m);
147  }
148  }
149 
150  //*** CHECK TO AVOID ERRORS
151  if (candidates.empty())
152  {
153  std::cout << "ERROR: GreedyObjectiveFunction.performStep -> candidates.isEmpty()" << std::endl;
154  std::cout << "MAX_SCORE: " << MAX_SCORE << std::endl;
155  exit(-1);
156  }
157 
158  //*** PICK A RANDOM ELEMENT FROM CANDIDATES
159  /* initialize random seed: */
160  srand(time(NULL));
161 
162  int choice = rand() % candidates.size();
163  machine_id = candidates.at(choice);
164 
165  try
166  {
167  CoordinatedPartitionState<T> &cord_state = dynamic_cast<CoordinatedPartitionState<T> &>(state);
168  //NEW UPDATE RECORDS RULE TO UPFDATE THE SIZE OF THE PARTITIONS EXPRESSED AS THE NUMBER OF VERTICES THEY CONTAINS
169  if (!u_record.hasReplicaInPartition(machine_id))
170  {
171  u_record.addPartition(machine_id);
172  cord_state.incrementMachineLoadVertices(machine_id);
173  }
174  if (!v_record.hasReplicaInPartition(machine_id))
175  {
176  v_record.addPartition(machine_id);
177  cord_state.incrementMachineLoadVertices(machine_id);
178  }
179  }
180  catch (std::bad_cast)
181  {
182  // use employee's member functions
183  //1-UPDATE RECORDS
184  if (!u_record.hasReplicaInPartition(machine_id))
185  {
186  u_record.addPartition(machine_id);
187  }
188  if (!v_record.hasReplicaInPartition(machine_id))
189  {
190  v_record.addPartition(machine_id);
191  }
192  }
193 
194  //2-UPDATE EDGES
195  state.incrementMachineLoad(machine_id, &e);
196 
197  //3-UPDATE DEGREES
198  u_record.incrementDegree();
199  v_record.incrementDegree();
200 
201  //*** RELEASE LOCK
202  u_record.releaseLock();
203  v_record.releaseLock();
204  }
205  }
206 }
207 
208 #endif // __CXXGRAPH_PARTITIONING_HDRF_H__
Definition: Edge.hpp:39
Definition: Globals.hpp:32
Definition: HDRF.hpp:35
Definition: PartitionState.hpp:33
Definition: PartitionStrategy.hpp:34