    001    package ttsolver;
    002
    003    import ifs.model.*;
    004    import ifs.util.*;
    005
    006    import java.io.*;
    007    import java.util.*;
    008
    009    import org.dom4j.*;
    010    import org.dom4j.io.*;
    011
    012    import ttsolver.constraint.*;
    013    import ttsolver.model.*;
    014
    015    /**
    016     * This class loads the input model from XML file.
    017     * <br><br>
    018     * Parameters:
    019     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    020     * <tr><td>General.Input</td><td>{@link String}</td><td>Input XML file</td></tr>
    021     * <tr><td>General.InitialAssignment</td><td>{@link Boolean}</td><td>Use the solution as initial assignment</td></tr>
    022     * <tr><td>General.UseDepartmentSpreadConstraints</td><td>{@link Boolean}</td><td>Use {@link DepartmentSpreadConstraint}</td></tr>
    023     * <tr><td>General.MPP</td><td>{@link Boolean}</td><td>Minimal perturbation problem (if true, initial assignments are set from solution)</td></tr>
    024     * <tr><td>General.ForcedPerturbances</td><td>{@link Integer}</td><td>For testing of MPP: number of input perturbations, i.e., classes with prohibited intial assignment</td></tr>
    025     * <tr><td>General.UseDistanceConstraints</td><td>{@link Boolean}</td><td>Consider distances between buildings</td></tr>
    026     * </table>
    027     *
    028     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    029     * @version 1.0
    030     */
    031
    032    public class TimetableXMLLoader extends TimetableLoader {
    033        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableXMLLoader.class);
    034
    035        private boolean iUseDepartmentSpreadConstraints = true;
    036        private int iForcedPerturbances = 0;
    037
    038        private boolean iInitialAssignment;
    039        private boolean iMppAssignment;
    040        private boolean iUseDistanceConstraints;
    041        private File iInputFile;
    042
    043        public TimetableXMLLoader(TimetableModel model) {
    044            super(model);
    045            iInputFile                 = new File(getModel().getProperties().getProperty("General.Input"));
    046            iForcedPerturbances        = getModel().getProperties().getPropertyInt("General.ForcedPerturbances",0);
    047            iMppAssignment             = getModel().getProperties().getPropertyBoolean("General.MPP",false);
    048            iInitialAssignment         = !iMppAssignment && getModel().getProperties().getPropertyBoolean("General.InitialAssignment",false);
    049            iUseDepartmentSpreadConstraints = getModel().getProperties().getPropertyBoolean("General.UseDepartmentSpreadConstraints",true);
    050            iUseDistanceConstraints = getModel().getProperties().getPropertyBoolean("General.UseDistanceConstraints", true);
    051        }
    052
    053        public void load(PrintWriter out) throws Exception {
    054            sLogger.debug("Reading XML data from "+iInputFile);
    055            Progress.getInstance().setPhase("Reading "+iInputFile.getName()+" ...");
    056
    057            Document document = (new SAXReader()).read(iInputFile);
    058            Element root = document.getRootElement();
    059            sLogger.debug("Root element: "+root.getName());
    060            if (!"llrt".equals(root.getName())) {
    061                sLogger.error("Given XML file is not large lecture room timetabling problem.");
    062                return;
    063            }
    064
    065            if (root.element("input")!=null) root = root.element("input");
    066
    067            sLogger.info("Going to load data "+root.attributeValue("semester")+root.attributeValue("year")+"v"+root.attributeValue("version")+" ...");
    068            getModel().getProperties().setProperty("Data.Semester", root.attributeValue("semester"));
    069            getModel().getProperties().setProperty("Data.Year", root.attributeValue("year"));
    070            getModel().getProperties().setProperty("Data.Version", root.attributeValue("version"));
    071
    072            Progress.getInstance().setPhase("Creating rooms ...",root.element("rooms").elements("room").size());
    073            Hashtable roomElements = new Hashtable();
    074            Hashtable roomConstraints = new Hashtable();
    075            Hashtable sameLectures = new Hashtable();
    076            for (Iterator i=root.element("rooms").elementIterator("room");i.hasNext();) {
    077                Element roomEl = (Element)i.next();
    078                RoomConstraint constraint = new RoomConstraint(roomEl.attributeValue("id"), "r"+roomEl.attributeValue("id"), edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY,edu.purdue.smas.timetable.util.Constants.DAY_CODES.length, roomEl.attributeValue("capacity")+" seats");
    079                getModel().addConstraint(constraint);
    080                Progress.getInstance().incProgress();
    081                roomElements.put(roomEl.attributeValue("id"), roomEl);
    082                roomConstraints.put(roomEl.attributeValue("id"), constraint);
    083            }
    084
    085            Progress.getInstance().setPhase("Creating variables ...",root.element("classes").elements("class").size());
    086
    087            int nrClasses = root.element("classes").elements("class").size();
    088
    089            Hashtable classElements = new Hashtable();
    090            Hashtable lectures = new Hashtable();
    091            Hashtable initialPlacements = new Hashtable();
    092            Hashtable instructorConstraints = new Hashtable();
    093            for (Iterator i1=root.element("classes").elementIterator("class");i1.hasNext();) {
    094                Element classEl = (Element)i1.next();
    095
    096                classElements.put(classEl.attributeValue("id"),classEl);
    097                Element instructorEl = (Element)classEl.element("instructor");
    098                InstructorConstraint instructorConstraint = null;
    099                if (instructorEl!=null) {
    100                    instructorConstraint = (InstructorConstraint)instructorConstraints.get(instructorEl.attributeValue("id"));
    101                    if (instructorConstraint==null) {
    102                        instructorConstraint = new InstructorConstraint(instructorEl.attributeValue("id"), "i"+instructorEl.attributeValue("id"), edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY,edu.purdue.smas.timetable.util.Constants.DAY_CODES.length);
    103                        instructorConstraints.put(instructorEl.attributeValue("id"), instructorConstraint);
    104                        getModel().addConstraint(instructorConstraint);
    105                    }
    106                }
    107                Vector roomLocations = new FastVector();
    108                Vector roomConstraintsThisClass = new FastVector();
    109                RoomLocation initialRoomLocation = null;
    110                int bestRoomPref = Integer.MAX_VALUE;
    111                for (Iterator i2=classEl.elementIterator("room");i2.hasNext();) {
    112                    Element roomLocationEl = (Element)i2.next();
    113                    Element roomEl = (Element)roomElements.get(roomLocationEl.attributeValue("id"));
    114                    RoomConstraint roomConstraint = (RoomConstraint)roomConstraints.get(roomLocationEl.attributeValue("id"));
    115                    roomConstraintsThisClass.add(roomConstraint);
    116                    RoomLocation rl = new RoomLocation(roomConstraint.getResourceId(),roomConstraint.getName(),null,Integer.parseInt(roomLocationEl.attributeValue("pref")),Integer.parseInt(roomEl.attributeValue("capacity")));
    117                    if (roomEl.attributeValue("location")!=null) {
    118                        String loc = roomEl.attributeValue("location");
    119                        int posX = Integer.parseInt(loc.substring(0,loc.indexOf(',')));
    120                        int posY = Integer.parseInt(loc.substring(loc.indexOf(',')+1));
    121                        rl.setCoordinates(posX, posY);
    122                    }
    123                    bestRoomPref = Math.min(bestRoomPref, Integer.parseInt(roomLocationEl.attributeValue("pref")));
    124                    if ("true".equals(roomLocationEl.attributeValue("solution")))
    125                        initialRoomLocation = rl;
    126                    roomLocations.add(rl);
    127                }
    128                if (roomLocations.isEmpty()) {
    129                    sLogger.error("  ERROR: No room.");
    130                    continue;
    131                }
    132                double bestTimePref = Double.MAX_VALUE;
    133                Vector timeLocations = new FastVector();
    134                TimeLocation initialTimeLocation = null;
    135                for (Iterator i2=classEl.elementIterator("time");i2.hasNext();) {
    136                    Element timeLocationEl = (Element)i2.next();
    137                    TimeLocation tl = new TimeLocation(
    138                        Integer.parseInt(timeLocationEl.attributeValue("days"),2),
    139                        Integer.parseInt(timeLocationEl.attributeValue("start")),
    140                        Integer.parseInt(timeLocationEl.attributeValue("length")),
    141                        Integer.parseInt(timeLocationEl.attributeValue("pref"))
    142                        );
    143                    bestTimePref = Math.min(bestTimePref, Integer.parseInt(timeLocationEl.attributeValue("pref")));
    144                    if ("true".equals(timeLocationEl.attributeValue("solution")))
    145                        initialTimeLocation = tl;
    146                    timeLocations.add(tl);
    147                }
    148                if (timeLocations.isEmpty()) {
    149                    sLogger.error("  ERROR: No time.");
    150                    continue;
    151                }
    152
    153                Lecture lecture = new Lecture(Long.parseLong(classEl.attributeValue("id")),  "c"+classEl.attributeValue("id"),  timeLocations,  bestTimePref,  (instructorEl==null?null:instructorEl.attributeValue("id")), roomLocations, bestRoomPref,  null, Integer.parseInt(classEl.attributeValue("expectedCapacity")),  (instructorEl==null?null:"i"+instructorEl.attributeValue("id")), "?");
    154                if (initialTimeLocation!=null && initialRoomLocation!=null) {
    155                    initialPlacements.put(lecture, new Placement(null,initialTimeLocation, initialRoomLocation));
    156                } else {
    157                    sLogger.debug("Lecture "+lecture+" has no initial placement (time="+initialTimeLocation+", room="+initialRoomLocation+")");
    158                }
    159                lectures.put(classEl.attributeValue("id"), lecture);
    160                lecture.setDepartment(classEl.attributeValue("department"));
    161                Vector sames = (Vector)sameLectures.get(classEl.attributeValue("course"));
    162                if (sames==null) {
    163                    sames = new FastVector();
    164                    sameLectures.put(classEl.attributeValue("course"), sames);
    165                }
    166                sames.addElement(lecture);
    167
    168                getModel().setBestRoomPreference(getModel().getBestRoomPreference() + bestRoomPref);
    169                getModel().setBestTimePreference(getModel().getBestTimePreference() + bestTimePref);
    170                getModel().addVariable(lecture);
    171                if (instructorConstraint!=null) instructorConstraint.addVariable(lecture);
    172
    173                for (Enumeration e2=roomConstraintsThisClass.elements(); e2.hasMoreElements();)
    174                    ((Constraint)e2.nextElement()).addVariable(lecture);
    175
    176                if (lecture.getInitialAssignment()!=null && getModel().conflictValues(lecture.getInitialAssignment()).isEmpty()) {
    177                    lecture.assign(0,lecture.getInitialAssignment());
    178                }
    179                Progress.getInstance().incProgress();
    180            }
    181
    182            Progress.getInstance().setPhase("Creating constraints ...",root.element("groupConstraints").elements("constraint").size());
    183            Hashtable grConstraintElements = new Hashtable();
    184            Hashtable groupConstraints = new Hashtable();
    185            for (Iterator i1=root.element("groupConstraints").elementIterator("constraint");i1.hasNext();) {
    186                Element grConstraintEl = (Element)i1.next();
    187                GroupConstraint gc = new GroupConstraint(Long.parseLong(grConstraintEl.attributeValue("id")), grConstraintEl.attributeValue("type"), grConstraintEl.attributeValue("pref"));
    188                gc.setGlobalPreference(getModel().getGlobalGroupConstraintPreferenceCounter());
    189                getModel().addConstraint(gc);
    190                for (Iterator i2=grConstraintEl.elementIterator("class");i2.hasNext();) {
    191                    String classId = ((Element)i2.next()).attributeValue("id");
    192                    gc.addVariable((Lecture)lectures.get(classId));
    193                }
    194                grConstraintElements.put(grConstraintEl.attributeValue("id"),grConstraintEl);
    195                groupConstraints.put(grConstraintEl.attributeValue("id"),gc);
    196                Progress.getInstance().incProgress();
    197            }
    198
    199            Progress.getInstance().setPhase("Loading students ...",root.element("students").elements("student").size());
    200            Hashtable jenrlConstraints = new Hashtable();
    201            for (Iterator i1=root.element("students").elementIterator("student");i1.hasNext();) {
    202                Element studentEl = (Element)i1.next();
    203                Vector lecturesThisStudent = new Vector();
    204                for (Iterator i2=studentEl.elementIterator("class");i2.hasNext();) {
    205                    String classId = ((Element)i2.next()).attributeValue("id");
    206                    Lecture lecture = (Lecture)lectures.get(classId);
    207                    lecture.addStudent(studentEl.attributeValue("id"));
    208                    lecturesThisStudent.add(lecture);
    209                }
    210                for (Enumeration e1=lecturesThisStudent.elements();e1.hasMoreElements();) {
    211                    Lecture lect1 = (Lecture)e1.nextElement();
    212                    for (Enumeration e2=lecturesThisStudent.elements();e2.hasMoreElements();) {
    213                        Lecture lect2 = (Lecture)e2.nextElement();
    214                        if (lect1.getClassId()<lect2.getClassId()) {
    215                            JenrlConstraint jenrl =  (JenrlConstraint)jenrlConstraints.get(lect1.getClassId()+","+lect2.getClassId());
    216                            if (jenrl==null) {
    217                                jenrl = new JenrlConstraint(1, getModel().getViolatedStudentConflictsCounter());
    218                                getModel().addConstraint(jenrl);
    219                                jenrl.addVariable(lect1);
    220                                jenrl.addVariable(lect2);
    221                                jenrlConstraints.put(lect1.getClassId()+","+lect2.getClassId(), jenrl);
    222                            } else {
    223                                jenrl.incJenrl();
    224                            }
    225                        }
    226                    }
    227                }
    228                Progress.getInstance().incProgress();
    229            }
    230
    231            for (Enumeration e1=sameLectures.elements();e1.hasMoreElements();) {
    232                Vector sames = (Vector)e1.nextElement();
    233                for (Enumeration e2=sames.elements(); e2.hasMoreElements();) {
    234                    Lecture lect = (Lecture)e2.nextElement();
    235                    lect.setSameLectures(sames);
    236                }
    237            }
    238
    239            if (iMppAssignment || iInitialAssignment) {
    240                Progress.getInstance().setPhase("Creating initial assignment ...",initialPlacements.size());
    241                for (Iterator ip=initialPlacements.entrySet().iterator();ip.hasNext();) {
    242                    Map.Entry entry = (Map.Entry)ip.next();
    243                    Lecture lecture = (Lecture)entry.getKey();
    244                    Placement placement = (Placement)entry.getValue();
    245                    placement.setVariable(lecture);
    246                    if (iMppAssignment) lecture.setInitialAssignment(placement);
    247                    Hashtable conflictConstraints = getModel().conflictConstraints(placement);
    248                    if (conflictConstraints.isEmpty()) {
    249                        lecture.assign(0,placement);
    250                    } else {
    251                        sLogger.warn("WARNING: Unable to assign "+lecture.getName()+" := "+placement.getName());
    252                        sLogger.debug("  Reason:");
    253                        for (Enumeration ex=conflictConstraints.keys();ex.hasMoreElements();) {
    254                            Constraint c = (Constraint)ex.nextElement();
    255                            Collection vals = (Collection)conflictConstraints.get(c);
    256                            for (Iterator i=vals.iterator();i.hasNext();) {
    257                                Value v = (Value) i.next();
    258                                sLogger.debug("    "+v.variable().getName()+" = "+v.getName());
    259                            }
    260                            sLogger.debug("    in constraint "+c);
    261                        }
    262                    }
    263                    Progress.getInstance().incProgress();
    264                }
    265            }
    266
    267            if (iForcedPerturbances>0) {
    268                Progress.getInstance().setPhase("Forcing perturbances",iForcedPerturbances);
    269                for (int i=0;i<iForcedPerturbances;i++) {
    270                    Progress.getInstance().setProgress(i);
    271                    Variable var = null;
    272                    do {
    273                        var = (Variable)ToolBox.random(getModel().variables());
    274                    } while (var.getInitialAssignment()==null || var.values().size()<=1);
    275                    var.removeInitialValue();
    276                }
    277            }
    278
    279            if (iUseDepartmentSpreadConstraints) {
    280                Progress.getInstance().setPhase("Creating dept. spread constraints ...",getModel().variables().size());
    281                Hashtable depSpreadConstraints = new Hashtable();
    282                for (Enumeration e=getModel().variables().elements();e.hasMoreElements();) {
    283                    Lecture lecture = (Lecture)e.nextElement();
    284                    if (lecture.getDepartment()==null) continue;
    285                    DepartmentSpreadConstraint deptConstr = (DepartmentSpreadConstraint)depSpreadConstraints.get(lecture.getDepartment());
    286                    if (deptConstr==null) {
    287                        deptConstr = new DepartmentSpreadConstraint(getModel().getProperties(),lecture.getDepartment());
    288                        depSpreadConstraints.put(lecture.getDepartment(),deptConstr);
    289                        getModel().addConstraint(deptConstr);
    290                    }
    291                    deptConstr.addVariable(lecture);
    292                    Progress.getInstance().incProgress();
    293                }
    294                for (Enumeration e=depSpreadConstraints.elements();e.hasMoreElements();)
    295                    ((DepartmentSpreadConstraint)e.nextElement()).init();
    296            }
    297            Progress.getInstance().setPhase("Done",1);Progress.getInstance().incProgress();
    298
    299            sLogger.debug("Model successfully loaded.");
    300            out.println("Model successfully loaded.");
    301        }
    302    }