1 /*
2 File generate.h
3 */
4 
5 /***************************************************************************
6                           generate.h  -  description
7                              -------------------
8     begin                : 2002
9     copyright            : (C) 2002 by Lalescu Liviu
10     email                : Please see https://lalescu.ro/liviu/ for details about contacting Liviu Lalescu (in particular, you can find here the e-mail address)
11  ***************************************************************************/
12 
13 /***************************************************************************
14  *                                                                         *
15  *   This program is free software: you can redistribute it and/or modify  *
16  *   it under the terms of the GNU Affero General Public License as        *
17  *   published by the Free Software Foundation, either version 3 of the    *
18  *   License, or (at your option) any later version.                       *
19  *                                                                         *
20  ***************************************************************************/
21 
22 #ifndef GENERATE_H
23 #define GENERATE_H
24 
25 #include "timetable_defs.h"
26 #include "solution.h"
27 #include "matrix.h"
28 
29 #include <QObject>
30 
31 #include <QTextStream>
32 
33 #include <QList>
34 #include <QSet>
35 
36 //#include <QMutex>
37 #include <QSemaphore>
38 #include <mutex>
39 //#include <semaphore>
40 //#include <condition_variable>
41 
42 class Activity;
43 
44 class QWidget;
45 
46 /**
47 This class incorporates the routines for time and space allocation of activities
48 */
49 class Generate: public QObject{
50 	Q_OBJECT
51 
52 public:
53 	//QMutex myMutex;
54 	std::mutex myMutex;
55 
56 	int nThread; //for multiple generation, otherwise it is 0.
57 
58 	QSemaphore semaphorePlacedActivity;
59 	//std::binary_semaphore semaphorePlacedActivity;
60 	//std::condition_variable cvForPlacedActivity;
61 	bool placedActivityProcessed;
62 
63 private:
64 	bool foundGoodSwap;
65 	Matrix1D<int> permutation;
66 	//
67 	//The following variables are here to accelerate the generation (so that they are not allocated more times during the generation).
68 	Matrix1D<int> buildings;
69 	Matrix1D<int> activities;
70 	Matrix1D<int> rooms;
71 	Matrix1D<int> activitiesx2;
72 	Matrix1D<int> roomsx2;
73 	Matrix2D<int> weekBuildings;
74 	Matrix2D<int> weekActivities;
75 	Matrix2D<int> weekRooms;
76 	Matrix1D<int> aminoCnt;
77 	Matrix1D<int> aminsCnt;
78 	Matrix1D<bool> possibleToEmptySlot;
79 	//
80 	Matrix1D<bool> occupiedDay;
81 	Matrix1D<bool> canEmptyDay;
82 	Matrix1D<int> _nConflActivities;
83 	Matrix1D<QList<int>> _activitiesForDay;
84 	Matrix1D<int> _minWrong;
85 	Matrix1D<int> _nWrong;
86 	Matrix1D<int> _minIndexAct;
87 	Matrix1D<bool> occupiedIntervalDay;
88 	Matrix1D<bool> canEmptyIntervalDay;
89 	Matrix1D<QList<int>> _activitiesForIntervalDay;
90 	Matrix1D<int> sbgDayNHoursWithTag;
91 	Matrix1D<bool> possibleToEmptyDay;
92 	Matrix1D<int> tchDayNHoursWithTag;
93 	//
94 	Matrix1D<bool> canEmptyTerm;
95 	Matrix1D<QList<int>> termActivities;
96 	//
97 	Matrix1D<bool> swappedActivities;
98 	Matrix1D<int> restoreActIndex;
99 	Matrix1D<int> restoreTime;
100 	Matrix1D<int> restoreRoom;
101 	Matrix1D<QList<int>> restoreRealRoomsList;
102 	Matrix1D<int> invPermutation;
103 	//
104 	Matrix2D<double> nMinDaysBrokenL;
105 	Matrix2D<int> selectedRoomL;
106 	Matrix2D<int> permL;
107 	Matrix2D<QList<int>> conflActivitiesL;
108 	Matrix2D<int> nConflActivitiesL;
109 	Matrix2D<int> roomSlotsL;
110 	Matrix2D<QList<int>> realRoomsListL;
111 	//
112 	Matrix1D<int> slotActivity;
113 	//
114 	int currentLevel;
115 	//
116 	QSet<int> conflActivitiesSet;
117 	//
118 	int nRestore;
119 	int limitcallsrandomswap;
120 	int level_limit;
121 	int ncallsrandomswap;
122 	//
123 	//if level==0, choose best position with the lowest number of conflicting activities
124 	QList<int> conflActivitiesTimeSlot;
125 	int timeSlot;
126 	int roomSlot;
127 	QList<int> realRoomsSlot;
128 	//
129 	Matrix2D<int> triedRemovals;
130 	//
131 	bool impossibleActivity;
132 	//
133 	////////tabu list of tried removals (circular)
134 	int tabu_size;
135 	int crt_tabu_index;
136 	Matrix1D<int> tabu_activities;
137 	Matrix1D<int> tabu_times;
138 	////////////
139 	Matrix3D<int> teachersTimetable;
140 	Matrix3D<int> subgroupsTimetable;
141 	Matrix3D<int> roomsTimetable;
142 	//
143 	Matrix3D<int> newTeachersTimetable;
144 	Matrix3D<int> newSubgroupsTimetable;
145 	Matrix2D<int> newTeachersDayNHours;
146 	Matrix2D<int> newTeachersDayNGaps;
147 	Matrix2D<int> newSubgroupsDayNHours;
148 	Matrix2D<int> newSubgroupsDayNGaps;
149 	Matrix2D<int> newSubgroupsDayNFirstGaps;
150 
151 	Matrix2D<int> newTeachersDayNFirstGaps;
152 	Matrix2D<int> newTeachersRealDayNHours;
153 	Matrix2D<int> newTeachersRealDayNGaps;
154 	Matrix2D<int> newSubgroupsRealDayNHours;
155 	Matrix2D<int> newSubgroupsRealDayNGaps;
156 	Matrix2D<int> newSubgroupsRealDayNFirstGaps;
157 
158 	//
159 	Matrix3D<int> oldTeachersTimetable;
160 	Matrix3D<int> oldSubgroupsTimetable;
161 	Matrix2D<int> oldTeachersDayNHours;
162 	Matrix2D<int> oldTeachersDayNGaps;
163 	Matrix2D<int> oldSubgroupsDayNHours;
164 	Matrix2D<int> oldSubgroupsDayNGaps;
165 	Matrix2D<int> oldSubgroupsDayNFirstGaps;
166 
167 	Matrix2D<int> oldTeachersDayNFirstGaps;
168 	Matrix2D<int> oldTeachersRealDayNHours;
169 	Matrix2D<int> oldTeachersRealDayNGaps;
170 	Matrix2D<int> oldSubgroupsRealDayNHours;
171 	Matrix2D<int> oldSubgroupsRealDayNGaps;
172 	Matrix2D<int> oldSubgroupsRealDayNFirstGaps;
173 
174 	//
175 	Matrix2D<int> tchTimetable;
176 	Matrix1D<int> tchDayNHours;
177 	Matrix1D<int> tchDayNGaps;
178 
179 	Matrix2D<int> sbgTimetable;
180 	Matrix1D<int> sbgDayNHours;
181 	Matrix1D<int> sbgDayNGaps;
182 	Matrix1D<int> sbgDayNFirstGaps;
183 
184 	Matrix1D<int> tchDayNFirstGaps;
185 	Matrix1D<int> tchRealDayNHours;
186 	Matrix1D<int> tchRealDayNGaps;
187 	Matrix1D<int> sbgRealDayNHours;
188 	Matrix1D<int> sbgRealDayNGaps;
189 	Matrix1D<int> sbgRealDayNFirstGaps;
190 
191 	//
192 	Matrix2D<QList<int>> teacherActivitiesOfTheDay;
193 	Matrix2D<QList<int>> subgroupActivitiesOfTheDay;
194 
195 	//used at level 0
196 	Matrix1D<int> l0nWrong;
197 	Matrix1D<int> l0minWrong;
198 	Matrix1D<int> l0minIndexAct;
199 
200 	//2011-09-25
201 	Matrix1D<QSet<int>> slotSetOfActivities;
202 	Matrix1D<bool> slotCanEmpty;
203 
204 	Matrix1D<QSet<int>> activitiesAtTime;
205 	////////////
206 
207 	int nRealRooms;
208 	int nSets;
209 	int NIL_NODE;
210 
211 	Matrix1D<QList<int>> adj;
212 	//static Matrix1D<int> dist;
213 	Matrix1D<bool> visited;
214 	Matrix1D<int> semiRandomPermutation; //the semi-random permutation of U (the points on the left, the real rooms)
215 	Matrix1D<int> pairNode;
216 	Matrix1D<int> nConflictingActivitiesBipartiteMatching;
217 	Matrix1D<QSet<int>> conflictingActivitiesBipartiteMatching; //only used at level 0
218 
219 	Solution* tmpGlobalSolutionCompareLevel0;
220 
221 	bool compareConflictsIncreasing(int a, int b);
222 	bool compareConflictsIncreasingAtLevel0(int a, int b);
223 
224 	//2019-09-15 - for virtual rooms, choosing randomly the real rooms.
225 	/*bool breadthFirstSearch();
226 	bool depthFirstSearch(int u);
227 	int hopcroftKarp();*/
228 
229 	bool depthFirstSearch(int u);
230 	int maximumBipartiteMatching();
231 
232 	//a probabilistic function to say if we can skip a constraint based on its percentage weight
233 	bool skipRandom(double weightPercentage);
234 
235 	//for sorting slots in ascending order of potential conflicts
236 	bool compareFunctionGenerate(int i, int j);
237 
238 public:
239 	MRG32k3a rng;
240 
241 	bool isRunning;
242 
243 	int maxActivitiesPlaced;
244 	Solution highestStageSolution;
245 
246 	Generate();
247 	~Generate();
248 
249 	inline void addAiToNewTimetable(int ai, const Activity* act, int d, int h);
250 	inline void removeAiFromNewTimetable(int ai, const Activity* act, int d, int h);
251 
252 	inline void getTchTimetable(int tch, const QList<int>& conflActivities);
253 	inline void getSbgTimetable(int sbg, const QList<int>& conflActivities);
254 
255 	inline void removeAi2FromTchTimetable(int ai2);
256 	inline void removeAi2FromSbgTimetable(int ai2);
257 
258 	inline void updateTeachersNHoursGaps(int ai, int d);
259 	inline void updateSubgroupsNHoursGaps(int ai, int d);
260 
261 	inline void updateTeachersNHoursGapsRealDay(int ai, int real_d);
262 	inline void updateSubgroupsNHoursGapsRealDay(int ai, int real_d);
263 
264 	inline void updateTchNHoursGaps(int tch, int d);
265 	inline void updateSbgNHoursGaps(int sbg, int d);
266 
267 	inline void updateTchNHoursGapsRealDay(int tch, int real_d);
268 	inline void updateSbgNHoursGapsRealDay(int sbg, int real_d);
269 
270 	inline void tchGetNHoursGaps(int tch);
271 	inline void tchGetNHoursGapsRealDays(int tch);
272 	inline void teacherGetNHoursGaps(int tch);
273 	inline bool teacherRemoveAnActivityFromBeginOrEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
274 	inline bool teacherRemoveAnActivityFromEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
275 	inline bool teacherRemoveAnActivityFromAnywhere(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
276 	inline bool teacherRemoveAnActivityFromBeginOrEndCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
277 	inline bool teacherRemoveAnActivityFromAnywhereCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
278 
279 	inline bool teacherRemoveAnActivityFromAnywhereCertainDayCertainActivityTag(int d2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
280 	inline bool teacherRemoveAnActivityFromAnywhereCertainDayDayPairCertainActivityTag(int d2, int dpair2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
281 
282 	inline bool teacherRemoveAnActivityFromBeginOrEndCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
283 	inline bool teacherRemoveAnActivityFromAnywhereCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
284 
285 	//constraints teachers max gaps per real day
286 	inline bool teacherRemoveAnActivityFromBeginMorningOrEndAfternoon(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
287 	inline bool teacherRemoveAnActivityFromBeginOrEndCertainRealDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
288 
289 	inline void sbgGetNHoursGaps(int sbg);
290 	inline void sbgGetNHoursGapsRealDays(int sbg);
291 	inline void subgroupGetNHoursGaps(int sbg);
292 	inline bool subgroupRemoveAnActivityFromBegin(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
293 	inline bool subgroupRemoveAnActivityFromEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
294 	inline bool subgroupRemoveAnActivityFromBeginOrEnd(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
295 	inline bool subgroupRemoveAnActivityFromAnywhere(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
296 	inline bool subgroupRemoveAnActivityFromBeginCertainDay(int d2, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
297 	inline bool subgroupRemoveAnActivityFromEndCertainDay(int d2, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
298 	inline bool subgroupRemoveAnActivityFromAnywhereCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
299 
300 	//2017-02-07
301 	//used only in students max span per day
302 	inline bool subgroupRemoveAnActivityFromBeginOrEndCertainDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
303 
304 	inline bool subgroupRemoveAnActivityFromAnywhereCertainDayCertainActivityTag(int d2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
305 
306 	//constraints students max gaps per real day
307 	inline bool subgroupRemoveAnActivityFromBeginMorning(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
308 	inline bool subgroupRemoveAnActivityFromEndAfternoon(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
309 	inline bool subgroupRemoveAnActivityFromBeginMorningOrEndAfternoon(int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
310 
311 	inline bool subgroupRemoveAnActivityFromBeginOrEndCertainRealDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
312 	inline bool subgroupRemoveAnActivityFromEndCertainRealDay(int d2, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
313 
314 	inline bool subgroupRemoveAnActivityFromAnywhereCertainDayDayPairCertainActivityTag(int d2, int dpair2, int actTag, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
315 
316 	inline bool subgroupRemoveAnActivityFromBeginCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
317 	inline bool subgroupRemoveAnActivityFromEndCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
318 	inline bool subgroupRemoveAnActivityFromAnywhereCertainTwoDays(int d2, int d4, int level, int ai, QList<int>& conflActivities, int& nConflActivities, int& removedActivity);
319 
320 	inline bool checkActivitiesOccupyMaxDifferentRooms(const QList<int>& globalConflActivities, int rm, int level, int ai, QList<int>& tmp_list);
321 	inline bool checkActivitiesSameRoomIfConsecutive(const QList<int>& globalConflActivities, int rm, int ai, int d, int h, QList<int>& tmp_list);
322 
323 	//only one out of sbg and tch is >=0, the other one is -1
324 	inline bool checkBuildingChanges(int sbg, int tch, const QList<int>& globalConflActivities, int rm, int level, const Activity* act, int ai, int d, int h, QList<int>& tmp_list);
325 	inline bool checkRoomChanges(int sbg, int tch, const QList<int>& globalConflActivities, int rm, int level, const Activity* act, int ai, int d, int h, QList<int>& tmp_list);
326 
327 	inline bool checkRoomChangesPerRealDay(int sbg, int tch, const QList<int>& globalConflActivities, int rm, int level, const Activity* act, int ai, int d, int h, QList<int>& tmp_list);
328 
329 	inline bool chooseRoom(const QList<int>& listOfRooms, const QList<int>& globalConflActivities, int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& localConflActivities, QList<int>& realRoomsList);
330 	inline bool getHomeRoom(const QList<int>& globalConflActivities, int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& localConflActivities, QList<int>& realRoomsList);
331 	inline bool getPreferredRoom(const QList<int>& globalConflActivities, int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& localConflActivities, bool& canBeUnspecifiedPreferredRoom, QList<int>& realRoomsList);
332 	inline bool getRoom(int level, const Activity* act, int ai, int d, int h, int& roomSlot, int& selectedSlot, QList<int>& conflActivities, int& nConflActivities, QList<int>& realRoomsList);
333 
334 	Solution c;
335 
336 	int nPlacedActivities;
337 
338 	//difficult activities
339 	int nDifficultActivities;
340 	Matrix1D<int> difficultActivities;
341 
342 	int searchTime; //seconds
343 
344 	int timeToHighestStage; //seconds
345 
346 	bool abortOptimization;
347 
348 	bool precompute(QWidget* parent, QTextStream* maxPlacedActivityStream=nullptr);
349 
350 	void generate(int maxSeconds, bool& impossible, bool& timeExceeded, bool threaded, QTextStream* maxPlacedActivityStream=nullptr);
351 
352 	void moveActivity(int ai, int fromslot, int toslot, int fromroom, int toroom, const QList<int>& fromRealRoomsList, const QList<int>& toRealRoomsList);
353 
354 	void randomSwap(int ai, int level);
355 
356 signals:
357 	void activityPlaced(int, int);
358 
359 	void simulationFinished();
360 
361 	void impossibleToSolve();
362 
363 private:
364 	bool isThreaded;
365 };
366 
367 #endif
368