Back to index

fet  5.18.0
solution.cpp
Go to the documentation of this file.
00001 /*
00002 File solution.cpp
00003 */
00004 
00005 /*
00006 Copyright 2002, 2003 Lalescu Liviu.
00007 
00008 This file is part of FET.
00009 
00010 FET is free software; you can redistribute it and/or modify
00011 it under the terms of the GNU General Public License as published by
00012 the Free Software Foundation; either version 2 of the License, or
00013 (at your option) any later version.
00014 
00015 FET is distributed in the hope that it will be useful,
00016 but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 GNU General Public License for more details.
00019 
00020 You should have received a copy of the GNU General Public License
00021 along with FET; if not, write to the Free Software
00022 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00023 */
00024 
00025 //Teachers free periods code contributed by Volker Dirr (http://timetabling.de/)
00026 
00027 #include <iostream>
00028 using namespace std;
00029 
00030 #include <QFile>
00031 #include <QTextStream>
00032 
00033 #include "timetable_defs.h"
00034 #include "solution.h"
00035 #include "rules.h"
00036 #include "timeconstraint.h"
00037 
00038 #include "matrix.h"
00039 
00040 #include <QMap>
00041 #include <QMultiMap>
00042 
00043 //extern bool breakDayHour[MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];
00044 extern Matrix2D<bool> breakDayHour;
00045 //extern bool teacherNotAvailableDayHour[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];
00046 extern Matrix3D<bool> teacherNotAvailableDayHour;
00047 
00048 //critical function here - must be optimized for speed
00049 void Solution::copy(Rules& r, Solution& c){
00050        this->_fitness=c._fitness;
00051 
00052        assert(r.internalStructureComputed);
00053 
00054        for(int i=0; i<r.nInternalActivities; i++){
00055               this->times[i] = c.times[i];
00056               this->rooms[i]=c.rooms[i];
00057        }
00058        //memcpy(times, c.times, r.nActivities * sizeof(times[0]));
00059        
00060        this->changedForMatrixCalculation=c.changedForMatrixCalculation;
00061 
00062        //added in version 5.2.0
00063        conflictsWeightList=c.conflictsWeightList;
00064        conflictsDescriptionList=c.conflictsDescriptionList;
00065        conflictsTotal=c.conflictsTotal;
00066        
00067        teachersMatrixReady=c.teachersMatrixReady;
00068        subgroupsMatrixReady=c.subgroupsMatrixReady;
00069        roomsMatrixReady=c.roomsMatrixReady;
00070        
00071        nPlacedActivities=c.nPlacedActivities;
00072 }
00073 
00074 void Solution::init(Rules& r){
00075        assert(r.internalStructureComputed);
00076 
00077        for(int i=0; i<r.nInternalActivities; i++){
00078               this->times[i]=UNALLOCATED_TIME;
00079               this->rooms[i]=UNALLOCATED_SPACE;
00080        }
00081 
00082        this->_fitness=-1;
00083        
00084        this->changedForMatrixCalculation=true;
00085 }
00086 
00087 void Solution::makeUnallocated(Rules& r){
00088        assert(r.initialized);
00089        assert(r.internalStructureComputed);
00090 
00091        for(int i=0; i<r.nInternalActivities; i++){
00092               this->times[i]=UNALLOCATED_TIME;
00093               this->rooms[i]=UNALLOCATED_SPACE;
00094        }
00095 
00096        this->_fitness=-1;
00097 
00098        this->changedForMatrixCalculation=true;
00099 }
00100 
00101 double Solution::fitness(Rules& r, QString* conflictsString){
00102        assert(r.initialized);
00103        assert(r.internalStructureComputed);
00104 
00105        if(this->_fitness>=0)
00106               assert(this->changedForMatrixCalculation==false);
00107               
00108        if(this->_fitness>=0 && conflictsString==NULL)
00109        //If you want to see the log, you have to recompute the fitness, even if it is
00110        //already computed
00111               return this->_fitness;
00112               
00113        this->changedForMatrixCalculation=true;
00114        
00115        this->_fitness=0;
00116        //I AM NOT SURE IF THE COMMENT BELOW IS DEPRECATED/FALSE NOW (IT IS OLD).
00117        //here we must not have compulsory activity preferred time nor
00118        //compulsory activities same time and/or hour
00119        //Also, here I compute soft fitness (for faster results,
00120        //I do not want to pass again through the constraints)
00121        
00122        this->conflictsDescriptionList.clear();
00123        this->conflictsWeightList.clear();
00124        
00125        this->teachersMatrixReady=false;
00126        this->subgroupsMatrixReady=false;
00127        this->roomsMatrixReady=false;
00128        
00129        this->nPlacedActivities=0;
00130        for(int i=0; i<r.nInternalActivities; i++)
00131               if(this->times[i]!=UNALLOCATED_TIME)
00132                      this->nPlacedActivities++;
00133               
00134        for(int i=0; i<r.nInternalTimeConstraints; i++){
00135               QList<QString> sl;
00136               QList<double> cl;
00137               this->_fitness += r.internalTimeConstraintsList[i]->fitness(*this, r, cl, sl, conflictsString);
00138               
00139               conflictsWeightList+=cl;
00140               conflictsDescriptionList+=sl;
00141        }      
00142        for(int i=0; i<r.nInternalSpaceConstraints; i++){
00143               QList<QString> sl;
00144               QList<double> cl;
00145               this->_fitness += r.internalSpaceConstraintsList[i]->fitness(*this, r, cl, sl, conflictsString);
00146               conflictsWeightList+=cl;
00147               conflictsDescriptionList+=sl;
00148        }
00149               
00150        this->conflictsTotal=0;
00151        foreach(double cn, conflictsWeightList){
00152               //cout<<"cn=="<<cn<<endl;
00153               conflictsTotal+=cn;
00154        }
00155               
00156 #if 0
00157        //I cannot put this test. I got situations of assert failed with 15.2 != 15.2 ??? Maybe rounding errors
00158        if(this->_fitness!=conflictsTotal){
00159               cout<<"this->_fitness=="<<this->_fitness<<endl;
00160               cout<<"conflictsTotal=="<<conflictsTotal<<endl;
00161        }
00162        assert(this->_fitness==conflictsTotal);//TODO
00163 #endif
00164               
00165        //sort descending according to conflicts in O(n log n)
00166        int ttt=conflictsWeightList.count();
00167               
00168        QMultiMap<double, QString> map;
00169        assert(conflictsWeightList.count()==conflictsDescriptionList.count());
00170        for(int i=0; i<conflictsWeightList.count(); i++)
00171               map.insert(conflictsWeightList.at(i), conflictsDescriptionList.at(i));
00172               
00173        conflictsWeightList.clear();
00174        conflictsDescriptionList.clear();
00175        
00176        QMapIterator<double, QString> i(map);
00177        while (i.hasNext()) {
00178               i.next();
00179               conflictsWeightList.prepend(i.key());
00180               conflictsDescriptionList.prepend(i.value());
00181        }
00182        
00183        for(int i=0; i<conflictsWeightList.count()-1; i++)
00184               assert(conflictsWeightList.at(i) >= conflictsWeightList.at(i+1));
00185               
00186        assert(conflictsWeightList.count()==conflictsDescriptionList.count());
00187        assert(conflictsWeightList.count()==ttt);
00188        
00189        this->changedForMatrixCalculation=false;
00190 
00191        return this->_fitness;
00192 }
00193 
00194 int Solution::getTeachersMatrix(Rules& r, Matrix3D<qint8>& a){
00195        assert(r.initialized);
00196        assert(r.internalStructureComputed);
00197        
00198        int conflicts=0;
00199        
00200        a.resize(r.nInternalTeachers, r.nDaysPerWeek, r.nHoursPerDay);
00201 
00202        int i;
00203        for(i=0; i<r.nInternalTeachers; i++)
00204               for(int j=0; j<r.nDaysPerWeek; j++)
00205                      for(int k=0; k<r.nHoursPerDay; k++)
00206                             a[i][j][k]=0;
00207 
00208        for(i=0; i<r.nInternalActivities; i++)
00209               if(this->times[i]!=UNALLOCATED_TIME) {
00210                      int hour = this->times[i] / r.nDaysPerWeek;
00211                      int day = this->times[i] % r.nDaysPerWeek;
00212                      Activity* act=&r.internalActivitiesList[i];
00213                      for(int dd=0; dd<act->duration && hour+dd<r.nHoursPerDay; dd++)
00214                             for(int it=0; it<act->iTeachersList.count(); it++){
00215                                    int tch=act->iTeachersList.at(it);
00216                                    int tmp=a[tch][day][hour+dd];
00217                                    conflicts += tmp==0 ? 0 : 1;
00218                                    a[tch][day][hour+dd]++;
00219                             }
00220               }
00221 
00222        this->changedForMatrixCalculation=false;
00223               
00224        return conflicts;
00225 }
00226 
00227 int Solution::getSubgroupsMatrix(Rules& r, Matrix3D<qint8>& a){
00228        assert(r.initialized);
00229        assert(r.internalStructureComputed);
00230        
00231        int conflicts=0;
00232        
00233        a.resize(r.nInternalSubgroups, r.nDaysPerWeek, r.nHoursPerDay);
00234 
00235        int i;
00236        for(i=0; i<r.nInternalSubgroups; i++)
00237               for(int j=0; j<r.nDaysPerWeek; j++)
00238                      for(int k=0; k<r.nHoursPerDay; k++)
00239                             a[i][j][k]=0;
00240 
00241        for(i=0; i<r.nInternalActivities; i++)
00242               if(this->times[i]!=UNALLOCATED_TIME){
00243                      int hour=this->times[i]/r.nDaysPerWeek;
00244                      int day=this->times[i]%r.nDaysPerWeek;
00245                      Activity* act = &r.internalActivitiesList[i];
00246                      for(int dd=0; dd < act->duration && hour+dd < r.nHoursPerDay; dd++)
00247                             for(int isg=0; isg < act->iSubgroupsList.count(); isg++){ //isg => index subgroup
00248                                    int sg = act->iSubgroupsList.at(isg); //sg => subgroup
00249                                    int tmp=a[sg][day][hour+dd];
00250                                    conflicts += tmp==0 ? 0 : 1;
00251                                    a[sg][day][hour+dd]++;
00252                             }
00253               }
00254               
00255        this->changedForMatrixCalculation=false;
00256               
00257        return conflicts;
00258 }
00259 
00260 //The following 2 functions (GetTeachersTimetable & GetSubgroupsTimetable)
00261 //are very similar to the above 2 ones (GetTeachersMatrix & GetSubgroupsMatrix)
00262 void Solution::getTeachersTimetable(Rules& r, Matrix3D<qint16>& a, Matrix3D<QList<qint16> >& b){
00263        assert(r.initialized);
00264        assert(r.internalStructureComputed);
00265        
00266        a.resize(r.nInternalTeachers, r.nDaysPerWeek, r.nHoursPerDay);
00267        b.resize(TEACHERS_FREE_PERIODS_N_CATEGORIES, r.nDaysPerWeek, r.nHoursPerDay);
00268        
00269        int i, j, k;
00270        for(i=0; i<r.nInternalTeachers; i++)
00271               for(j=0; j<r.nDaysPerWeek; j++)
00272                      for(k=0; k<r.nHoursPerDay; k++)
00273                             a[i][j][k]=UNALLOCATED_ACTIVITY;
00274 
00275        Activity *act;
00276        for(i=0; i<r.nInternalActivities; i++) 
00277               if(this->times[i]!=UNALLOCATED_TIME) {
00278                      act=&r.internalActivitiesList[i];
00279                      int hour=this->times[i]/r.nDaysPerWeek;
00280                      int day=this->times[i]%r.nDaysPerWeek;
00281                      for(int dd=0; dd < act->duration; dd++){
00282                             assert(hour+dd<r.nHoursPerDay);
00283                             for(int ti=0; ti<act->iTeachersList.count(); ti++){
00284                                    int tch = act->iTeachersList.at(ti); //teacher index
00285                                    assert(a[tch][day][hour+dd]==UNALLOCATED_ACTIVITY);
00286                                    a[tch][day][hour+dd]=i;
00287                             }
00288                      }
00289               }
00290 
00291        //Prepare teachers free periods timetable.
00292        //Code contributed by Volker Dirr (http://timetabling.de/) BEGIN
00293        int d,h,tch;
00294        for(d=0; d<r.nDaysPerWeek; d++){
00295               for(h=0; h<r.nHoursPerDay; h++){
00296                      for(int tfp=0; tfp<TEACHERS_FREE_PERIODS_N_CATEGORIES; tfp++){
00297                             b[tfp][d][h].clear();
00298                      }
00299               }
00300        }
00301        for(tch=0; tch<r.nInternalTeachers; tch++){
00302               for(d=0; d<r.nDaysPerWeek; d++){
00303                      int firstPeriod=-1;
00304                      int lastPeriod=-1;
00305                      for(h=0; h<r.nHoursPerDay; h++){
00306                             if(a[tch][d][h]!=UNALLOCATED_ACTIVITY){
00307                                    if(firstPeriod==-1)
00308                                           firstPeriod=h;
00309                                    lastPeriod=h;
00310                             }
00311                      }
00312                      if(firstPeriod==-1){
00313                             for(h=0; h<r.nHoursPerDay; h++){
00314                                    b[TEACHER_HAS_A_FREE_DAY][d][h]<<tch;
00315                             }
00316                      } else {
00317                             for(h=0; h<firstPeriod; h++){
00318                                    if(firstPeriod-h==1){
00319                                           b[TEACHER_MUST_COME_EARLIER][d][h]<<tch;
00320                                    }
00321                                    else {
00322                                           b[TEACHER_MUST_COME_MUCH_EARLIER][d][h]<<tch;
00323                                    }
00324                             }
00325                             for(; h<lastPeriod+1; h++){
00326                                    if(a[tch][d][h]==UNALLOCATED_ACTIVITY){
00327                                           if(a[tch][d][h+1]==UNALLOCATED_ACTIVITY){
00328                                                  if(a[tch][d][h-1]==UNALLOCATED_ACTIVITY){
00329                                                         b[TEACHER_HAS_BIG_GAP][d][h]<<tch;
00330                                                  } else {
00331                                                         b[TEACHER_HAS_BORDER_GAP][d][h]<<tch;
00332                                                  }
00333                                           } else {
00334                                                  if(a[tch][d][h-1]==UNALLOCATED_ACTIVITY){
00335                                                         b[TEACHER_HAS_BORDER_GAP][d][h]<<tch;
00336                                                  } else {
00337                                                         b[TEACHER_HAS_SINGLE_GAP][d][h]<<tch;
00338                                                  }
00339                                           }
00340                                    }
00341                             }
00342                             for(; h<r.nHoursPerDay; h++){
00343                                    if(lastPeriod-h==-1){
00344                                           b[TEACHER_MUST_STAY_LONGER][d][h]<<tch;
00345                                    }
00346                                    else {
00347                                           b[TEACHER_MUST_STAY_MUCH_LONGER][d][h]<<tch;
00348                                    }
00349                             }
00350                      }
00351               }
00352        }
00353        //care about not available teacher and breaks
00354        for(tch=0; tch<r.nInternalTeachers; tch++){
00355               for(d=0; d<r.nDaysPerWeek; d++){
00356                      for(h=0; h<r.nHoursPerDay; h++){
00357                             if(teacherNotAvailableDayHour[tch][d][h]==true || breakDayHour[d][h]==true){
00358                                    int removed=0;
00359                                    for(int tfp=0; tfp<TEACHER_IS_NOT_AVAILABLE; tfp++){
00360                                           if(b[tfp][d][h].contains(tch)){
00361                                                  removed+=b[tfp][d][h].removeAll(tch);
00362                                                  if(breakDayHour[d][h]==false)
00363                                                         b[TEACHER_IS_NOT_AVAILABLE][d][h]<<tch;
00364                                           }
00365                                    }
00366                                    assert(removed==1);
00367                             }
00368                      }
00369               }
00370        }
00371        //END of Code contributed by Volker Dirr (http://timetabling.de/) END
00372        //bool visited[MAX_TEACHERS];
00373        Matrix1D<bool> visited;
00374        visited.resize(r.nInternalTeachers);
00375        for(d=0; d<r.nDaysPerWeek; d++){
00376               for(h=0; h<r.nHoursPerDay; h++){
00377                      for(tch=0; tch<r.nInternalTeachers; tch++)
00378                             visited[tch]=false;
00379                      for(int tfp=0; tfp<TEACHERS_FREE_PERIODS_N_CATEGORIES; tfp++){
00380                             foreach(int tch, b[tfp][d][h]){
00381                                    assert(!visited[tch]);
00382                                    visited[tch]=true;
00383                             }
00384                      }
00385               }
00386        }
00387 }
00388 
00389 void Solution::getSubgroupsTimetable(Rules& r, Matrix3D<qint16>& a){
00390        assert(r.initialized);
00391        assert(r.internalStructureComputed);
00392        
00393        a.resize(r.nInternalSubgroups, r.nDaysPerWeek, r.nHoursPerDay);
00394        
00395        int i, j, k;
00396        for(i=0; i<r.nInternalSubgroups; i++)
00397               for(j=0; j<r.nDaysPerWeek; j++)
00398                      for(k=0; k<r.nHoursPerDay; k++)
00399                             a[i][j][k]=UNALLOCATED_ACTIVITY;
00400 
00401        Activity *act;
00402        for(i=0; i<r.nInternalActivities; i++)
00403               if(this->times[i]!=UNALLOCATED_TIME) {
00404                      act=&r.internalActivitiesList[i];
00405                      int hour=this->times[i]/r.nDaysPerWeek;
00406                      int day=this->times[i]%r.nDaysPerWeek;
00407                      for(int dd=0; dd < act->duration; dd++){
00408                             assert(hour+dd<r.nHoursPerDay);
00409                      
00410                             for(int isg=0; isg < act->iSubgroupsList.count(); isg++){ //isg -> index subgroup
00411                                    int sg = act->iSubgroupsList.at(isg); //sg -> subgroup
00412                                    assert(a[sg][day][hour+dd]==UNALLOCATED_ACTIVITY);
00413                                    a[sg][day][hour+dd]=i;
00414                             }
00415                      }
00416               }
00417 }
00418 
00419 int Solution::getRoomsMatrix(
00420        Rules& r, 
00421        Matrix3D<qint8>& a)
00422 {
00423        assert(r.initialized);
00424        assert(r.internalStructureComputed);
00425 
00426        int conflicts=0;
00427        
00428        a.resize(r.nInternalRooms, r.nDaysPerWeek, r.nHoursPerDay);
00429 
00430        int i;
00431        for(i=0; i<r.nInternalRooms; i++)
00432               for(int j=0; j<r.nDaysPerWeek; j++)
00433                      for(int k=0; k<r.nHoursPerDay; k++)
00434                             a[i][j][k]=0;
00435 
00436        for(i=0; i<r.nInternalActivities; i++){
00437               int room=this->rooms[i];
00438               int hour=times[i]/r.nDaysPerWeek;
00439               int day=times[i]%r.nDaysPerWeek;
00440               //int hour = hours[i];
00441               //int day = days[i];
00442               if(room!=UNALLOCATED_SPACE && room!=UNSPECIFIED_ROOM && hour!=UNALLOCATED_TIME && day!=UNALLOCATED_TIME) {
00443                      Activity* act=&r.internalActivitiesList[i];
00444                      for(int dd=0; dd<act->duration && hour+dd<r.nHoursPerDay; dd++){
00445                             int tmp=a[room][day][hour+dd];
00446                             conflicts += tmp==0 ? 0 : 1;
00447                             a[room][day][hour+dd]++;
00448                      }
00449               }
00450        }
00451        
00452        this->changedForMatrixCalculation=false;
00453        
00454        return conflicts;
00455 }
00456 
00457 void Solution::getRoomsTimetable(
00458        Rules& r,
00459        Matrix3D<qint16>& a)
00460 {
00461        assert(r.initialized);
00462        assert(r.internalStructureComputed);
00463        
00464        a.resize(r.nInternalRooms, r.nDaysPerWeek, r.nHoursPerDay);
00465        
00466        int i, j, k;
00467        for(i=0; i<r.nInternalRooms; i++)
00468               for(j=0; j<r.nDaysPerWeek; j++)
00469                      for(k=0; k<r.nHoursPerDay; k++)
00470                             a[i][j][k]=UNALLOCATED_ACTIVITY;
00471 
00472        Activity *act;
00473        for(i=0; i<r.nInternalActivities; i++){
00474               act=&r.internalActivitiesList[i];
00475               int room=this->rooms[i];
00476               int hour=times[i]/r.nDaysPerWeek;
00477               int day=times[i]%r.nDaysPerWeek;
00478               if(room!=UNALLOCATED_SPACE && room!=UNSPECIFIED_ROOM && day!=UNALLOCATED_TIME && hour!=UNALLOCATED_TIME){
00479                      for(int dd=0; dd < act->duration; dd++){
00480                             assert(hour+dd<r.nHoursPerDay);
00481                      
00482                             assert(a[room][day][hour+dd]==UNALLOCATED_ACTIVITY);
00483                             a[room][day][hour+dd]=i;
00484                      }
00485               }
00486        }
00487 }