Back to index

fet  5.18.0
Public Member Functions | Public Attributes
Solution Class Reference

This class represents a solution (time and space allocation for the activities). More...

#include <solution.h>

List of all members.

Public Member Functions

void copy (Rules &r, Solution &c)
 Assignment method.
void init (Rules &r)
 Initializes, marking all activities as unscheduled (time)
void makeUnallocated (Rules &r)
 Marks the starting time of all the activities as undefined (all activities are unallocated).
double fitness (Rules &r, QString *conflictsString=NULL)
 ATTENTION: if the rules change, the user has to reset _fitness to -1.
void getTeachersTimetable (Rules &r, Matrix3D< qint16 > &a, Matrix3D< QList< qint16 > > &b)
void getSubgroupsTimetable (Rules &r, Matrix3D< qint16 > &a)
void getRoomsTimetable (Rules &r, Matrix3D< qint16 > &a)
int getSubgroupsMatrix (Rules &r, Matrix3D< qint8 > &a)
int getTeachersMatrix (Rules &r, Matrix3D< qint8 > &a)
int getRoomsMatrix (Rules &r, Matrix3D< qint8 > &a)

Public Attributes

QList< double > conflictsWeightList
QList< QString > conflictsDescriptionList
double conflictsTotal
bool teachersMatrixReady
bool subgroupsMatrixReady
bool roomsMatrixReady
int nPlacedActivities
bool changedForMatrixCalculation
qint16 times [MAX_ACTIVITIES]
 This array represents every activity's start time (time is a unified representation of hour and day, stored as an integer value).
qint16 rooms [MAX_ACTIVITIES]
double _fitness
 Fitness; it is calculated only at the initialization or at the modification.

Detailed Description

This class represents a solution (time and space allocation for the activities).

Definition at line 41 of file solution.h.


Member Function Documentation

void Solution::copy ( Rules r,
Solution c 
)

Assignment method.

We need to have access to the Rules instantiation to know the number of activities.

Definition at line 49 of file solution.cpp.

Here is the caller graph for this function:

double Solution::fitness ( Rules r,
QString *  conflictsString = NULL 
)

ATTENTION: if the rules change, the user has to reset _fitness to -1.

If conflictsString is not null, then this function will append at this string an explanation of the conflicts.

Definition at line 101 of file solution.cpp.

                                                          {
       assert(r.initialized);
       assert(r.internalStructureComputed);

       if(this->_fitness>=0)
              assert(this->changedForMatrixCalculation==false);
              
       if(this->_fitness>=0 && conflictsString==NULL)
       //If you want to see the log, you have to recompute the fitness, even if it is
       //already computed
              return this->_fitness;
              
       this->changedForMatrixCalculation=true;
       
       this->_fitness=0;
       //I AM NOT SURE IF THE COMMENT BELOW IS DEPRECATED/FALSE NOW (IT IS OLD).
       //here we must not have compulsory activity preferred time nor
       //compulsory activities same time and/or hour
       //Also, here I compute soft fitness (for faster results,
       //I do not want to pass again through the constraints)
       
       this->conflictsDescriptionList.clear();
       this->conflictsWeightList.clear();
       
       this->teachersMatrixReady=false;
       this->subgroupsMatrixReady=false;
       this->roomsMatrixReady=false;
       
       this->nPlacedActivities=0;
       for(int i=0; i<r.nInternalActivities; i++)
              if(this->times[i]!=UNALLOCATED_TIME)
                     this->nPlacedActivities++;
              
       for(int i=0; i<r.nInternalTimeConstraints; i++){
              QList<QString> sl;
              QList<double> cl;
              this->_fitness += r.internalTimeConstraintsList[i]->fitness(*this, r, cl, sl, conflictsString);
              
              conflictsWeightList+=cl;
              conflictsDescriptionList+=sl;
       }      
       for(int i=0; i<r.nInternalSpaceConstraints; i++){
              QList<QString> sl;
              QList<double> cl;
              this->_fitness += r.internalSpaceConstraintsList[i]->fitness(*this, r, cl, sl, conflictsString);
              conflictsWeightList+=cl;
              conflictsDescriptionList+=sl;
       }
              
       this->conflictsTotal=0;
       foreach(double cn, conflictsWeightList){
              //cout<<"cn=="<<cn<<endl;
              conflictsTotal+=cn;
       }
              
#if 0
       //I cannot put this test. I got situations of assert failed with 15.2 != 15.2 ??? Maybe rounding errors
       if(this->_fitness!=conflictsTotal){
              cout<<"this->_fitness=="<<this->_fitness<<endl;
              cout<<"conflictsTotal=="<<conflictsTotal<<endl;
       }
       assert(this->_fitness==conflictsTotal);//TODO
#endif
              
       //sort descending according to conflicts in O(n log n)
       int ttt=conflictsWeightList.count();
              
       QMultiMap<double, QString> map;
       assert(conflictsWeightList.count()==conflictsDescriptionList.count());
       for(int i=0; i<conflictsWeightList.count(); i++)
              map.insert(conflictsWeightList.at(i), conflictsDescriptionList.at(i));
              
       conflictsWeightList.clear();
       conflictsDescriptionList.clear();
       
       QMapIterator<double, QString> i(map);
       while (i.hasNext()) {
              i.next();
              conflictsWeightList.prepend(i.key());
              conflictsDescriptionList.prepend(i.value());
       }
       
       for(int i=0; i<conflictsWeightList.count()-1; i++)
              assert(conflictsWeightList.at(i) >= conflictsWeightList.at(i+1));
              
       assert(conflictsWeightList.count()==conflictsDescriptionList.count());
       assert(conflictsWeightList.count()==ttt);
       
       this->changedForMatrixCalculation=false;

       return this->_fitness;
}

Here is the caller graph for this function:

int Solution::getRoomsMatrix ( Rules r,
Matrix3D< qint8 > &  a 
)

Definition at line 419 of file solution.cpp.

{
       assert(r.initialized);
       assert(r.internalStructureComputed);

       int conflicts=0;
       
       a.resize(r.nInternalRooms, r.nDaysPerWeek, r.nHoursPerDay);

       int i;
       for(i=0; i<r.nInternalRooms; i++)
              for(int j=0; j<r.nDaysPerWeek; j++)
                     for(int k=0; k<r.nHoursPerDay; k++)
                            a[i][j][k]=0;

       for(i=0; i<r.nInternalActivities; i++){
              int room=this->rooms[i];
              int hour=times[i]/r.nDaysPerWeek;
              int day=times[i]%r.nDaysPerWeek;
              //int hour = hours[i];
              //int day = days[i];
              if(room!=UNALLOCATED_SPACE && room!=UNSPECIFIED_ROOM && hour!=UNALLOCATED_TIME && day!=UNALLOCATED_TIME) {
                     Activity* act=&r.internalActivitiesList[i];
                     for(int dd=0; dd<act->duration && hour+dd<r.nHoursPerDay; dd++){
                            int tmp=a[room][day][hour+dd];
                            conflicts += tmp==0 ? 0 : 1;
                            a[room][day][hour+dd]++;
                     }
              }
       }
       
       this->changedForMatrixCalculation=false;
       
       return conflicts;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void Solution::getRoomsTimetable ( Rules r,
Matrix3D< qint16 > &  a 
)

Definition at line 457 of file solution.cpp.

{
       assert(r.initialized);
       assert(r.internalStructureComputed);
       
       a.resize(r.nInternalRooms, r.nDaysPerWeek, r.nHoursPerDay);
       
       int i, j, k;
       for(i=0; i<r.nInternalRooms; i++)
              for(j=0; j<r.nDaysPerWeek; j++)
                     for(k=0; k<r.nHoursPerDay; k++)
                            a[i][j][k]=UNALLOCATED_ACTIVITY;

       Activity *act;
       for(i=0; i<r.nInternalActivities; i++){
              act=&r.internalActivitiesList[i];
              int room=this->rooms[i];
              int hour=times[i]/r.nDaysPerWeek;
              int day=times[i]%r.nDaysPerWeek;
              if(room!=UNALLOCATED_SPACE && room!=UNSPECIFIED_ROOM && day!=UNALLOCATED_TIME && hour!=UNALLOCATED_TIME){
                     for(int dd=0; dd < act->duration; dd++){
                            assert(hour+dd<r.nHoursPerDay);
                     
                            assert(a[room][day][hour+dd]==UNALLOCATED_ACTIVITY);
                            a[room][day][hour+dd]=i;
                     }
              }
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Solution::getSubgroupsMatrix ( Rules r,
Matrix3D< qint8 > &  a 
)

Definition at line 227 of file solution.cpp.

                                                            {
       assert(r.initialized);
       assert(r.internalStructureComputed);
       
       int conflicts=0;
       
       a.resize(r.nInternalSubgroups, r.nDaysPerWeek, r.nHoursPerDay);

       int i;
       for(i=0; i<r.nInternalSubgroups; i++)
              for(int j=0; j<r.nDaysPerWeek; j++)
                     for(int k=0; k<r.nHoursPerDay; k++)
                            a[i][j][k]=0;

       for(i=0; i<r.nInternalActivities; i++)
              if(this->times[i]!=UNALLOCATED_TIME){
                     int hour=this->times[i]/r.nDaysPerWeek;
                     int day=this->times[i]%r.nDaysPerWeek;
                     Activity* act = &r.internalActivitiesList[i];
                     for(int dd=0; dd < act->duration && hour+dd < r.nHoursPerDay; dd++)
                            for(int isg=0; isg < act->iSubgroupsList.count(); isg++){ //isg => index subgroup
                                   int sg = act->iSubgroupsList.at(isg); //sg => subgroup
                                   int tmp=a[sg][day][hour+dd];
                                   conflicts += tmp==0 ? 0 : 1;
                                   a[sg][day][hour+dd]++;
                            }
              }
              
       this->changedForMatrixCalculation=false;
              
       return conflicts;
}

Here is the call graph for this function:

void Solution::getSubgroupsTimetable ( Rules r,
Matrix3D< qint16 > &  a 
)

Definition at line 389 of file solution.cpp.

                                                                 {
       assert(r.initialized);
       assert(r.internalStructureComputed);
       
       a.resize(r.nInternalSubgroups, r.nDaysPerWeek, r.nHoursPerDay);
       
       int i, j, k;
       for(i=0; i<r.nInternalSubgroups; i++)
              for(j=0; j<r.nDaysPerWeek; j++)
                     for(k=0; k<r.nHoursPerDay; k++)
                            a[i][j][k]=UNALLOCATED_ACTIVITY;

       Activity *act;
       for(i=0; i<r.nInternalActivities; i++)
              if(this->times[i]!=UNALLOCATED_TIME) {
                     act=&r.internalActivitiesList[i];
                     int hour=this->times[i]/r.nDaysPerWeek;
                     int day=this->times[i]%r.nDaysPerWeek;
                     for(int dd=0; dd < act->duration; dd++){
                            assert(hour+dd<r.nHoursPerDay);
                     
                            for(int isg=0; isg < act->iSubgroupsList.count(); isg++){ //isg -> index subgroup
                                   int sg = act->iSubgroupsList.at(isg); //sg -> subgroup
                                   assert(a[sg][day][hour+dd]==UNALLOCATED_ACTIVITY);
                                   a[sg][day][hour+dd]=i;
                            }
                     }
              }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Solution::getTeachersMatrix ( Rules r,
Matrix3D< qint8 > &  a 
)

Definition at line 194 of file solution.cpp.

                                                           {
       assert(r.initialized);
       assert(r.internalStructureComputed);
       
       int conflicts=0;
       
       a.resize(r.nInternalTeachers, r.nDaysPerWeek, r.nHoursPerDay);

       int i;
       for(i=0; i<r.nInternalTeachers; i++)
              for(int j=0; j<r.nDaysPerWeek; j++)
                     for(int k=0; k<r.nHoursPerDay; k++)
                            a[i][j][k]=0;

       for(i=0; i<r.nInternalActivities; i++)
              if(this->times[i]!=UNALLOCATED_TIME) {
                     int hour = this->times[i] / r.nDaysPerWeek;
                     int day = this->times[i] % r.nDaysPerWeek;
                     Activity* act=&r.internalActivitiesList[i];
                     for(int dd=0; dd<act->duration && hour+dd<r.nHoursPerDay; dd++)
                            for(int it=0; it<act->iTeachersList.count(); it++){
                                   int tch=act->iTeachersList.at(it);
                                   int tmp=a[tch][day][hour+dd];
                                   conflicts += tmp==0 ? 0 : 1;
                                   a[tch][day][hour+dd]++;
                            }
              }

       this->changedForMatrixCalculation=false;
              
       return conflicts;
}

Here is the call graph for this function:

void Solution::getTeachersTimetable ( Rules r,
Matrix3D< qint16 > &  a,
Matrix3D< QList< qint16 > > &  b 
)

Definition at line 262 of file solution.cpp.

                                                                                             {
       assert(r.initialized);
       assert(r.internalStructureComputed);
       
       a.resize(r.nInternalTeachers, r.nDaysPerWeek, r.nHoursPerDay);
       b.resize(TEACHERS_FREE_PERIODS_N_CATEGORIES, r.nDaysPerWeek, r.nHoursPerDay);
       
       int i, j, k;
       for(i=0; i<r.nInternalTeachers; i++)
              for(j=0; j<r.nDaysPerWeek; j++)
                     for(k=0; k<r.nHoursPerDay; k++)
                            a[i][j][k]=UNALLOCATED_ACTIVITY;

       Activity *act;
       for(i=0; i<r.nInternalActivities; i++) 
              if(this->times[i]!=UNALLOCATED_TIME) {
                     act=&r.internalActivitiesList[i];
                     int hour=this->times[i]/r.nDaysPerWeek;
                     int day=this->times[i]%r.nDaysPerWeek;
                     for(int dd=0; dd < act->duration; dd++){
                            assert(hour+dd<r.nHoursPerDay);
                            for(int ti=0; ti<act->iTeachersList.count(); ti++){
                                   int tch = act->iTeachersList.at(ti); //teacher index
                                   assert(a[tch][day][hour+dd]==UNALLOCATED_ACTIVITY);
                                   a[tch][day][hour+dd]=i;
                            }
                     }
              }

       //Prepare teachers free periods timetable.
       //Code contributed by Volker Dirr (http://timetabling.de/) BEGIN
       int d,h,tch;
       for(d=0; d<r.nDaysPerWeek; d++){
              for(h=0; h<r.nHoursPerDay; h++){
                     for(int tfp=0; tfp<TEACHERS_FREE_PERIODS_N_CATEGORIES; tfp++){
                            b[tfp][d][h].clear();
                     }
              }
       }
       for(tch=0; tch<r.nInternalTeachers; tch++){
              for(d=0; d<r.nDaysPerWeek; d++){
                     int firstPeriod=-1;
                     int lastPeriod=-1;
                     for(h=0; h<r.nHoursPerDay; h++){
                            if(a[tch][d][h]!=UNALLOCATED_ACTIVITY){
                                   if(firstPeriod==-1)
                                          firstPeriod=h;
                                   lastPeriod=h;
                            }
                     }
                     if(firstPeriod==-1){
                            for(h=0; h<r.nHoursPerDay; h++){
                                   b[TEACHER_HAS_A_FREE_DAY][d][h]<<tch;
                            }
                     } else {
                            for(h=0; h<firstPeriod; h++){
                                   if(firstPeriod-h==1){
                                          b[TEACHER_MUST_COME_EARLIER][d][h]<<tch;
                                   }
                                   else {
                                          b[TEACHER_MUST_COME_MUCH_EARLIER][d][h]<<tch;
                                   }
                            }
                            for(; h<lastPeriod+1; h++){
                                   if(a[tch][d][h]==UNALLOCATED_ACTIVITY){
                                          if(a[tch][d][h+1]==UNALLOCATED_ACTIVITY){
                                                 if(a[tch][d][h-1]==UNALLOCATED_ACTIVITY){
                                                        b[TEACHER_HAS_BIG_GAP][d][h]<<tch;
                                                 } else {
                                                        b[TEACHER_HAS_BORDER_GAP][d][h]<<tch;
                                                 }
                                          } else {
                                                 if(a[tch][d][h-1]==UNALLOCATED_ACTIVITY){
                                                        b[TEACHER_HAS_BORDER_GAP][d][h]<<tch;
                                                 } else {
                                                        b[TEACHER_HAS_SINGLE_GAP][d][h]<<tch;
                                                 }
                                          }
                                   }
                            }
                            for(; h<r.nHoursPerDay; h++){
                                   if(lastPeriod-h==-1){
                                          b[TEACHER_MUST_STAY_LONGER][d][h]<<tch;
                                   }
                                   else {
                                          b[TEACHER_MUST_STAY_MUCH_LONGER][d][h]<<tch;
                                   }
                            }
                     }
              }
       }
       //care about not available teacher and breaks
       for(tch=0; tch<r.nInternalTeachers; tch++){
              for(d=0; d<r.nDaysPerWeek; d++){
                     for(h=0; h<r.nHoursPerDay; h++){
                            if(teacherNotAvailableDayHour[tch][d][h]==true || breakDayHour[d][h]==true){
                                   int removed=0;
                                   for(int tfp=0; tfp<TEACHER_IS_NOT_AVAILABLE; tfp++){
                                          if(b[tfp][d][h].contains(tch)){
                                                 removed+=b[tfp][d][h].removeAll(tch);
                                                 if(breakDayHour[d][h]==false)
                                                        b[TEACHER_IS_NOT_AVAILABLE][d][h]<<tch;
                                          }
                                   }
                                   assert(removed==1);
                            }
                     }
              }
       }
       //END of Code contributed by Volker Dirr (http://timetabling.de/) END
       //bool visited[MAX_TEACHERS];
       Matrix1D<bool> visited;
       visited.resize(r.nInternalTeachers);
       for(d=0; d<r.nDaysPerWeek; d++){
              for(h=0; h<r.nHoursPerDay; h++){
                     for(tch=0; tch<r.nInternalTeachers; tch++)
                            visited[tch]=false;
                     for(int tfp=0; tfp<TEACHERS_FREE_PERIODS_N_CATEGORIES; tfp++){
                            foreach(int tch, b[tfp][d][h]){
                                   assert(!visited[tch]);
                                   visited[tch]=true;
                            }
                     }
              }
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void Solution::init ( Rules r)

Initializes, marking all activities as unscheduled (time)

Definition at line 74 of file solution.cpp.

                           {
       assert(r.internalStructureComputed);

       for(int i=0; i<r.nInternalActivities; i++){
              this->times[i]=UNALLOCATED_TIME;
              this->rooms[i]=UNALLOCATED_SPACE;
       }

       this->_fitness=-1;
       
       this->changedForMatrixCalculation=true;
}

Marks the starting time of all the activities as undefined (all activities are unallocated).

Definition at line 87 of file solution.cpp.

                                      {
       assert(r.initialized);
       assert(r.internalStructureComputed);

       for(int i=0; i<r.nInternalActivities; i++){
              this->times[i]=UNALLOCATED_TIME;
              this->rooms[i]=UNALLOCATED_SPACE;
       }

       this->_fitness=-1;

       this->changedForMatrixCalculation=true;
}

Here is the caller graph for this function:


Member Data Documentation

Fitness; it is calculated only at the initialization or at the modification.

Important assumption: the rules have to ramain the same; otherwise the user has to reset this value to -1

Definition at line 76 of file solution.h.

Definition at line 58 of file solution.h.

Definition at line 44 of file solution.h.

Definition at line 45 of file solution.h.

Definition at line 43 of file solution.h.

Definition at line 51 of file solution.h.

Definition at line 68 of file solution.h.

Definition at line 49 of file solution.h.

Definition at line 48 of file solution.h.

Definition at line 47 of file solution.h.

This array represents every activity's start time (time is a unified representation of hour and day, stored as an integer value).

We have a special value here: UNALLOCATED_TIME, which is a large number.

Definition at line 66 of file solution.h.


The documentation for this class was generated from the following files: