rules.cpp

基于遗传算法的排课软件源码 根据需要安排合理的课程时间等

/*
File rules.cpp
*/

/*
Copyright 2002, 2003 Lalescu Liviu.

This file is part of FET.

FET is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

FET is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with FET; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "genetictimetable_defs.h"
#include "rules.h"

#include <string.h>

#include <iostream>
using namespace std;

#include <qdom.h>
#include <qstring.h>
#include <qtranslator.h>
#include <qmessagebox.h>

void Rules::init() //initializes the rules (empty, but with default hours and days)
{
	this->subjectsList.setAutoDelete(true);
	this->subjectTagsList.setAutoDelete(true);
	this->yearsList.setAutoDelete(true);
	this->teachersList.setAutoDelete(true);
	this->activitiesList.setAutoDelete(true);
	this->timeConstraintsList.setAutoDelete(true);
	this->spaceConstraintsList.setAutoDelete(true);
	this->equipmentsList.setAutoDelete(true);
	this->buildingsList.setAutoDelete(true);
	this->roomsList.setAutoDelete(true);

	//defaults
	this->nHoursPerDay=12;
	this->hoursOfTheDay[0]="0";
	this->hoursOfTheDay[1]="1";
	this->hoursOfTheDay[2]="2";
	this->hoursOfTheDay[3]="3";
	this->hoursOfTheDay[4]="4";
	this->hoursOfTheDay[5]="5";
	this->hoursOfTheDay[6]="6";
	this->hoursOfTheDay[7]="7";
	this->hoursOfTheDay[8]="8";
	this->hoursOfTheDay[9]="9";
	this->hoursOfTheDay[10]="10";
	this->hoursOfTheDay[11]="11";
	this->hoursOfTheDay[12]="12";

	this->nDaysPerWeek=5;
	this->daysOfTheWeek[0] = QObject::tr("Monday");
	this->daysOfTheWeek[1] = QObject::tr("Tuesday");
	this->daysOfTheWeek[2] = QObject::tr("Wednesday");
	this->daysOfTheWeek[3] = QObject::tr("Thursday");
	this->daysOfTheWeek[4] = QObject::tr("Friday");
	
	this->institutionName=QObject::tr("Default institution");
	this->comments=QObject::tr("Default comments");

	this->initialized=true;
}

bool Rules::computeInternalStructure()
{
	//The order is important - firstly the teachers, subjects and students.
	//After that, the equipments.
	//After that, the rooms.
	//After that, the activities.
	//After that, the time constraints.
	//After that, initialization of the matrix "roomHasEquipment".
	//After that, the space constraints.

	int i;
	
	if(this->teachersList.count()>(uint)(MAX_TEACHERS)){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many teachers.\nPlease talk to the author or increase variable MAX_TEACHERS"));
		return false;
	}
	if(this->subjectsList.count()>(uint)(MAX_SUBJECTS)){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many subjects.\nPlease talk to the author or increase variable MAX_SUBJECTS"));
		return false;
	}

	int tmpNSubgroups=0;
	if(this->yearsList.count()>(uint)(MAX_YEARS)){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many years.\nPlease talk to the author or increase variable MAX_YEARS"));
		return false;
	}
	for(StudentsYear* sty=this->yearsList.first(); sty; sty=this->yearsList.next()){
		if(sty->groupsList.count()>(uint)(MAX_GROUPS_PER_YEAR)){
			QMessageBox::warning(NULL, QObject::tr("FET information"),
			 QObject::tr("You have too many groups per year.\nPlease talk to the author or increase variable MAX_GROUPS_PER_YEAR"));
			return false;
		}
		for(StudentsGroup* stg=sty->groupsList.first(); stg; stg=sty->groupsList.next()){
			if(stg->subgroupsList.count()>(uint)(MAX_SUBGROUPS_PER_GROUP)){
				QMessageBox::warning(NULL, QObject::tr("FET information"),
				 QObject::tr("You have too many subgroups per group.\nPlease talk to the author or increase variable MAX_SUBGROUPS_PER_GROUP"));
				return false;
			}
			tmpNSubgroups+=stg->subgroupsList.count();
					assert(this->nInternalSubgroups<MAX_TOTAL_SUBGROUPS);
		}
	}
	if(tmpNSubgroups>MAX_TOTAL_SUBGROUPS){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many total subgroups.\nPlease talk to the author or increase variable MAX_TOTAL_SUBGROUPS"));
		return false;
	}

	int counter=0;
	for(Activity* act=this->activitiesList.first(); act; act=this->activitiesList.next())
		if(act->active)
			counter++;
	if(counter>MAX_ACTIVITIES){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many active activities.\nPlease talk to the author or increase variable MAX_ACTIVITIES"));
		return false;
	}

	if(this->equipmentsList.count()>(uint)(MAX_EQUIPMENTS)){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many equipments.\nPlease talk to the author or increase variable MAX_EQUIPMENTS"));
		return false;
	}
	if(this->roomsList.count()>(uint)(MAX_ROOMS)){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many rooms.\nPlease talk to the author or increase variable MAX_ROOMS"));
		return false;
	}
	if(this->buildingsList.count()>(uint)(MAX_BUILDINGS)){
		QMessageBox::warning(NULL, QObject::tr("FET information"),
		 QObject::tr("You have too many buildings.\nPlease talk to the author or increase variable MAX_BUILDINGS"));
		return false;
	}

	assert(this->initialized);

	//days and hours
	assert(this->nHoursPerDay>0);
	assert(this->nDaysPerWeek>0);
	this->nHoursPerWeek=this->nHoursPerDay*this->nDaysPerWeek;

	//teachers
	Teacher* tch;
	this->nInternalTeachers=this->teachersList.count();
	assert(this->nInternalTeachers<=MAX_TEACHERS);
	for(tch=this->teachersList.first(), i=0; tch; tch=this->teachersList.next(), i++)
		this->internalTeachersList[i]=tch;
	assert(i==this->nInternalTeachers);

	//subjects
	Subject* sbj;
	this->nInternalSubjects=this->subjectsList.count();
	assert(this->nInternalSubjects<=MAX_SUBJECTS);	
	for(sbj=this->subjectsList.first(), i=0; sbj; sbj=this->subjectsList.next(), i++)
		this->internalSubjectsList[i]=sbj;
	assert(i==this->nInternalSubjects);

	//students
	this->nInternalSubgroups=0;
	assert(this->yearsList.count()<=(uint)(MAX_YEARS));
	for(StudentsYear* sty=this->yearsList.first(); sty; sty=this->yearsList.next()){
		//if this year has no groups, insert something to simulate the whole year
		if(sty->groupsList.count()==0){
			StudentsGroup* tmpGroup = new StudentsGroup();
			tmpGroup->name = sty->name+" WHOLE YEAR";
			tmpGroup->numberOfStudents = sty->numberOfStudents;
			sty->groupsList.append(tmpGroup);
		}
		assert(sty->groupsList.count()<=(uint)(MAX_GROUPS_PER_YEAR));
		for(StudentsGroup* stg=sty->groupsList.first(); stg; stg=sty->groupsList.next()){
			//if this group has no subgroups, insert something to simulate the whole group
			if(stg->subgroupsList.count()==0){
				StudentsSubgroup* tmpSubgroup = new StudentsSubgroup();
				tmpSubgroup->name = stg->name+" WHOLE GROUP";
				tmpSubgroup->numberOfStudents=stg->numberOfStudents;
				stg->subgroupsList.append(tmpSubgroup);
			}
			assert(stg->subgroupsList.count()<=(uint)(MAX_SUBGROUPS_PER_GROUP));
			for(StudentsSubgroup* sts=stg->subgroupsList.first(); sts; sts=stg->subgroupsList.next()){
				bool existing=false;
				for(int i=0; i<this->nInternalSubgroups; i++)
					if(this->internalSubgroupsList[i]->name==sts->name){
						existing=true;
						break;
					}
				if(!existing){
					assert(this->nInternalSubgroups<MAX_TOTAL_SUBGROUPS);
					this->internalSubgroupsList[this->nInternalSubgroups++]=sts;
				}
			}
		}
	}

	//equipments internal list
	this->nInternalEquipments=0;
	assert(this->equipmentsList.count()<=(uint)(MAX_EQUIPMENTS));
	for(Equipment* eq=this->equipmentsList.first(); eq; eq=this->equipmentsList.next())
		this->internalEquipmentsList[this->nInternalEquipments++]=eq;
	assert((uint)(this->nInternalEquipments)==this->equipmentsList.count());

	//buildings internal list
	this->nInternalBuildings=0;
	assert(this->buildingsList.count()<=(uint)(MAX_BUILDINGS));
	for(Building* bu=this->buildingsList.first(); bu; bu=this->buildingsList.next())
		this->internalBuildingsList[this->nInternalBuildings++]=bu;
	assert((uint)(this->nInternalBuildings)==this->buildingsList.count());

	//rooms
	Room* rm;
	this->nInternalRooms=0;
	assert(this->roomsList.count()<=(uint)(MAX_ROOMS));	
	for(rm=this->roomsList.first(); rm; rm=this->roomsList.next())
		rm->computeInternalStructure(*this);
	
	for(rm=this->roomsList.first(); rm; rm=this->roomsList.next())
		this->internalRoomsList[this->nInternalRooms++]=rm;
	assert((uint)(this->nInternalRooms)==this->roomsList.count());

	//activities
	Activity* act;
	counter=0;
	for(act=this->activitiesList.first(); act; act=this->activitiesList.next())
		if(act->active){
			counter++;
			act->computeInternalStructure(*this);
		}

	assert(counter<=MAX_ACTIVITIES);
	this->nInternalActivities=counter;
	i=0;
	for(act=this->activitiesList.first(); act; act=this->activitiesList.next())
		if(act->active)
			this->internalActivitiesList[i++]=*act;

	//time constraints
	assert(this->timeConstraintsList.count()<=(uint)(MAX_TIME_CONSTRAINTS));
	TimeConstraint* tctr;
	//for(tctr=this->timeConstraintsList.first(); tctr; tctr=this->timeConstraintsList.next())
	//	tctr->computeInternalStructure(*this);

	for(int i=0; i<this->nInternalActivities; i++){
		this->fixedDay[i]=-1;
		this->fixedHour[i]=-1;
		this->sameDay[i]=-1;
		this->sameHour[i]=-1;
	}
	//getting rid of compulsory preferred time-s, same starting hour-s & same starting time-s - 
	//these will be used separately to repair the chromosomes (it was practically
	//found that this is the best method).	
	for(tctr=this->timeConstraintsList.first(), i=0; tctr; tctr=this->timeConstraintsList.next()){
		//if the activities which refer to this constraints are not active
		if(!tctr->computeInternalStructure(*this))
			continue;
		if(tctr->type==CONSTRAINT_ACTIVITY_PREFERRED_TIME && tctr->compulsory==true){
			ConstraintActivityPreferredTime* c = (ConstraintActivityPreferredTime*)tctr;

			bool t1=this->fixedDay[c->activityIndex]==-1 || this->fixedDay[c->activityIndex]==c->day;
			bool t2=this->fixedHour[c->activityIndex]==-1 || this->fixedHour[c->activityIndex]==c->hour;
			if(!t1){
				QMessageBox::warning(NULL, QObject::tr("FET information"), 
				 QObject::tr("Activity with id=%1 has fixed day on %2 and %3 - impossible\n"
				 "Please fix that")
				 .arg(this->internalActivitiesList[c->activityIndex].id)
				 .arg(this->daysOfTheWeek[this->fixedDay[c->activityIndex]])
				 .arg(this->daysOfTheWeek[c->day]));
				this->internalStructureComputed=false;
				return false;
			}
			if(!t2){
				QMessageBox::warning(NULL, QObject::tr("FET information"), 
				 QObject::tr("Activity with id=%1 has fixed hour on %2 and %3 - impossible\n"
				 "Please fix that")
				 .arg(this->internalActivitiesList[c->activityIndex].id)
				 .arg(this->hoursOfTheDay[this->fixedHour[c->activityIndex]])
				 .arg(this->hoursOfTheDay[c->hour]));
				this->internalStructureComputed=false;
				return false;
			}

			this->fixedDay[c->activityIndex] = c->day;
			this->fixedHour[c->activityIndex] = c->hour;
		}
		else if(tctr->type==CONSTRAINT_ACTIVITIES_SAME_STARTING_TIME && tctr->compulsory==true){
			ConstraintActivitiesSameStartingTime* c=(ConstraintActivitiesSameStartingTime*)tctr;
			int ai1=c->_activities[0];
			for(int i=1; i<c->_n_activities; i++){
				int ai2=c->_activities[i];
				
				int old=sameDay[ai2];
				if(old>=0){
					bool visited[MAX_ACTIVITIES];
					for(int i=0; i<this->nInternalActivities; i++)
						visited[i]=false;					
					visited[old]=true;
					while(sameDay[old]>=0 && !visited[sameDay[old]]){
						old=sameDay[old];
						visited[old]=true;
					}
					this->sameDay[old]=ai1;
				}
				else
					this->sameDay[ai2]=ai1;
				
				old=sameHour[ai2];
				if(old>=0){
					bool visited[MAX_ACTIVITIES];
					for(int i=0; i<this->nInternalActivities; i++)
						visited[i]=false;					
					visited[old]=true;
					while(sameHour[old]>=0 && !visited[sameHour[old]]){
						old=sameHour[old];
						visited[old]=true;
					}
					this->sameHour[old]=ai1;
				}
				else
					this->sameHour[ai2]=ai1;
			}
		}
		else if(tctr->type==CONSTRAINT_ACTIVITIES_SAME_STARTING_HOUR && tctr->compulsory==true){
			ConstraintActivitiesSameStartingHour* c=(ConstraintActivitiesSameStartingHour*)tctr;
			int ai1=c->_activities[0];
			for(int i=1; i<c->_n_activities; i++){
				int ai2=c->_activities[i];

				int old=sameHour[ai2];
				if(old>=0){
					bool visited[MAX_ACTIVITIES];
					for(int i=0; i<this->nInternalActivities; i++)
						visited[i]=false;
					visited[old]=true;
					while(sameHour[old]>=0 && !visited[sameHour[old]]){
						old=sameHour[old];
						visited[old]=true;
					}
					this->sameHour[old]=ai1;
				}
				else
					this->sameHour[ai2]=ai1;
			}
		}
		else{
			this->internalTimeConstraintsList[i++]=tctr;
		}
	}

	//all activities will depend on only one "head"
	for(int i=0; i<this->nInternalActivities; i++){
		for(int j=0; j<this->nInternalActivities; j++){
			int k=this->sameDay[j];
			if(k>=0 && this->sameDay[k]>=0)
				this->sameDay[j]=this->sameDay[k];
			k=this->sameHour[j];
			if(k>=0 && this->sameHour[k]>=0)
				this->sameHour[j]=this->sameHour[k];
		}
	}
	//make the head have the fixed day & hour
	for(int i=0; i<this->nInternalActivities; i++){