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