    001package org.cpsolver.ifs.example.tt;
    002
    003import java.io.File;
    004import java.io.FileInputStream;
    005import java.io.FileOutputStream;
    006import java.io.IOException;
    007import java.util.ArrayList;
    008import java.util.HashSet;
    009import java.util.HashMap;
    010import java.util.Iterator;
    011import java.util.List;
    012import java.util.Map;
    013import java.util.Set;
    014import java.util.TreeSet;
    015
    016
    017import org.cpsolver.ifs.assignment.Assignment;
    018import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
    019import org.cpsolver.ifs.model.Constraint;
    020import org.cpsolver.ifs.model.Model;
    021import org.cpsolver.ifs.solution.Solution;
    022import org.cpsolver.ifs.util.DataProperties;
    023import org.cpsolver.ifs.util.ToolBox;
    024import org.dom4j.Document;
    025import org.dom4j.DocumentException;
    026import org.dom4j.DocumentHelper;
    027import org.dom4j.Element;
    028import org.dom4j.io.OutputFormat;
    029import org.dom4j.io.SAXReader;
    030import org.dom4j.io.XMLWriter;
    031
    032/**
    033 * Simple Timetabling Problem. <br>
    034 * <br>
    035 * The problem is modelled in such a way that every lecture was represented by a
    036 * variable, resource as a constraint and every possible location of an activity
    037 * in the time and space was represented by a single value. It means that a
    038 * value stands for a selection of the time (starting time slot), and one of the
    039 * available rooms. Binary dependencies are of course represented as constraints
    040 * as well.
    041 *
    042 * @author  Tomáš Müller
    043 * @version IFS 1.3 (Iterative Forward Search)<br>
    044 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    045 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    046 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    047 * <br>
    048 *          This library is free software; you can redistribute it and/or modify
    049 *          it under the terms of the GNU Lesser General Public License as
    050 *          published by the Free Software Foundation; either version 3 of the
    051 *          License, or (at your option) any later version. <br>
    052 * <br>
    053 *          This library is distributed in the hope that it will be useful, but
    054 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    055 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    056 *          Lesser General Public License for more details. <br>
    057 * <br>
    058 *          You should have received a copy of the GNU Lesser General Public
    059 *          License along with this library; if not see
    060 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    061 */
    062public class TimetableModel extends Model<Activity, Location> {
    063    private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(TimetableModel.class);
    064    private int iNrDays, iNrHours;
    065
    066    public TimetableModel(int nrDays, int nrHours) {
    067        super();
    068        iNrDays = nrDays;
    069        iNrHours = nrHours;
    070    }
    071
    072    public int getNrDays() {
    073        return iNrDays;
    074    }
    075
    076    public int getNrHours() {
    077        return iNrHours;
    078    }
    079
    080    @SuppressWarnings("unchecked")
    081    public static TimetableModel generate(DataProperties cfg, Assignment<Activity, Location> assignment) {
    082        int nrDays = cfg.getPropertyInt("Generator.NrDays", 5);
    083        int nrHours = cfg.getPropertyInt("Generator.NrHours", 20);
    084        int nrSlots = nrDays * nrHours;
    085        TimetableModel m = new TimetableModel(nrDays, nrHours);
    086
    087        int nrRooms = cfg.getPropertyInt("Generator.NrRooms", 20);
    088        int nrInstructors = cfg.getPropertyInt("Generator.NrInstructors", 20);
    089        int nrClasses = cfg.getPropertyInt("Generator.NrClasses", 20);
    090        int nrGroupsOfRooms = cfg.getPropertyInt("Generator.NrGroupsOfRooms", 20);
    091        int nrRoomsInGroupMin = cfg.getPropertyInt("Generator.NrRoomsInGroupMin", 1);
    092        int nrRoomsInGroupMax = cfg.getPropertyInt("Generator.NrRoomsInGroupMax", 10);
    093        int nrRoomInGroupMin = cfg.getPropertyInt("Generator.NrRoomInGroupMin", 1);
    094        double fillFactor = cfg.getPropertyDouble("Generator.FillFactor", 0.8);
    095        int maxLength = cfg.getPropertyInt("Generator.ActivityLengthMax", 5);
    096        double hardFreeResource = cfg.getPropertyDouble("Generator.HardFreeResource", 0.05);
    097        double softFreeResource = cfg.getPropertyDouble("Generator.SoftFreeResource", 0.3);
    098        double softUsedResource = cfg.getPropertyDouble("Generator.SoftUsedResource", 0.05);
    099        double softUsedActivity = cfg.getPropertyDouble("Generator.SoftUsedActivity", 0.05);
    100        double softFreeActivity = cfg.getPropertyDouble("Generator.SoftFreeActivity", 0.3);
    101        double hardFreeActivity = cfg.getPropertyDouble("Generator.HardFreeActivity", 0.05);
    102        int nrDependencies = cfg.getPropertyInt("Generator.NrDependencies", 50);
    103
    104        Resource rooms[] = new Resource[nrRooms];
    105        ArrayList<ArrayList<Resource>> groupForRoom[] = new ArrayList[nrRooms];
    106        for (int i = 0; i < nrRooms; i++) {
    107            rooms[i] = new Resource("r" + (i + 1), Resource.TYPE_ROOM, "Room " + (i + 1));
    108            groupForRoom[i] = new ArrayList<ArrayList<Resource>>();
    109            m.addConstraint(rooms[i]);
    110        }
    111        ArrayList<Resource> groupOfRooms[] = new ArrayList[nrGroupsOfRooms];
    112        for (int i = 0; i < nrGroupsOfRooms; i++) {
    113            groupOfRooms[i] = new ArrayList<Resource>();
    114            for (int j = 0; j < ToolBox.random(1 + nrRoomsInGroupMax - nrRoomsInGroupMin) + nrRoomsInGroupMin; j++) {
    115                int r = 0;
    116                do {
    117                    r = ToolBox.random(nrRooms);
    118                } while (groupOfRooms[i].contains(rooms[r]));
    119                groupOfRooms[i].add(rooms[r]);
    120                groupForRoom[r].add(groupOfRooms[i]);
    121            }
    122        }
    123        for (int i = 0; i < nrRooms; i++) {
    124            int cnt = 0;
    125            for (int j = 0; j < nrGroupsOfRooms; j++)
    126                if (groupOfRooms[j].contains(rooms[i]))
    127                    cnt++;
    128            while (cnt < nrRoomInGroupMin) {
    129                int r = 0;
    130                do {
    131                    r = ToolBox.random(nrGroupsOfRooms);
    132                } while (groupOfRooms[r].contains(rooms[i]));
    133                groupOfRooms[r].add(rooms[i]);
    134                groupForRoom[i].add(groupOfRooms[r]);
    135                cnt++;
    136            }
    137        }
    138        Resource instructors[] = new Resource[nrInstructors];
    139        for (int i = 0; i < nrInstructors; i++) {
    140            instructors[i] = new Resource("t" + (i + 1), Resource.TYPE_INSTRUCTOR, "Teacher " + (i + 1));
    141            m.addConstraint(instructors[i]);
    142        }
    143        Resource classes[] = new Resource[nrClasses];
    144        for (int i = 0; i < nrClasses; i++) {
    145            classes[i] = new Resource("c" + (i + 1), Resource.TYPE_CLASS, "Class " + (i + 1));
    146            m.addConstraint(classes[i]);
    147        }
    148
    149        int[][] timetable4room = new int[nrRooms][nrSlots];
    150        int[][] timetable4instr = new int[nrInstructors][nrSlots];
    151        int[][] timetable4class = new int[nrClasses][nrSlots];
    152        int act = 0;
    153        for (int i = 0; i < timetable4room.length; i++)
    154            for (int j = 0; j < timetable4room[i].length; j++)
    155                timetable4room[i][j] = 0;
    156        for (int i = 0; i < timetable4instr.length; i++)
    157            for (int j = 0; j < timetable4instr[i].length; j++)
    158                timetable4instr[i][j] = 0;
    159        for (int i = 0; i < timetable4class.length; i++)
    160            for (int j = 0; j < timetable4class[i].length; j++)
    161                timetable4class[i][j] = 0;
    162
    163        int totalSlots = nrRooms * nrSlots;
    164        int usedSlots = 0;
    165        ArrayList<Integer> starts = new ArrayList<Integer>();
    166        ArrayList<Integer> arooms = new ArrayList<Integer>();
    167        while ((((double) usedSlots / ((double) totalSlots))) < fillFactor) {
    168            int attempt = 0;
    169            int slot = ToolBox.random(nrSlots);
    170            int room = ToolBox.random(nrRooms);
    171            while (attempt < 500 && timetable4room[room][slot] != 0) {
    172                slot = ToolBox.random(nrSlots);
    173                room = ToolBox.random(nrRooms);
    174            }
    175            if (attempt == 500) {
    176                int s = slot;
    177                int r = room;
    178                while (timetable4room[r][s] != 0) {
    179                    r++;
    180                    if (r == nrRooms)
    181                        r = 0;
    182                    if (r == room)
    183                        s++;
    184                    if (s == nrSlots)
    185                        s = 0;
    186                }
    187                slot = s;
    188                room = r;
    189            }
    190            int length = maxLength;// ToolBox.random(maxLength)+1;
    191            int aclass = ToolBox.random(nrClasses);
    192            int instr = ToolBox.random(nrInstructors);
    193            attempt = 0;
    194            while (attempt < 500 && (timetable4class[aclass][slot] != 0 || timetable4instr[instr][slot] != 0)) {
    195                aclass = ToolBox.random(nrClasses);
    196                instr = ToolBox.random(nrInstructors);
    197            }
    198            if (attempt == 500)
    199                continue;
    200            int len = 1;
    201            while (len < length) {
    202                if ((((slot + len) % nrHours) != 0) && timetable4room[room][slot + len] == 0
    203                        && timetable4instr[instr][slot + len] == 0 && timetable4class[aclass][slot + len] == 0)
    204                    len++;
    205                else
    206                    break;
    207            }
    208            ArrayList<Resource> roomGr = ToolBox.random(groupForRoom[room]);
    209            act++;
    210            usedSlots += len;
    211            Activity a = new Activity(len, "a" + act, "Activity " + act);
    212            a.addResourceGroup(roomGr);
    213            a.addResourceGroup(instructors[instr]);
    214            a.addResourceGroup(classes[aclass]);
    215            m.addVariable(a);
    216            starts.add(slot);
    217            arooms.add(room);
    218            for (int i = slot; i < slot + len; i++) {
    219                timetable4room[room][i] = act;
    220                timetable4instr[instr][i] = act;
    221                timetable4class[aclass][i] = act;
    222            }
    223        }
    224        int nrHardFreeRes = 0;
    225        int nrSoftFreeRes = 0;
    226        int nrSoftUsedRes = 0;
    227        for (int slot = 0; slot < nrSlots; slot++) {
    228            for (int room = 0; room < nrRooms; room++) {
    229                if (timetable4room[room][slot] == 0) {
    230                    if (ToolBox.random() < hardFreeResource) {
    231                        nrHardFreeRes++;
    232                        rooms[room].addProhibitedSlot(slot);
    233                    } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) {
    234                        nrSoftFreeRes++;
    235                        rooms[room].addDiscouragedSlot(slot);
    236                    }
    237                } else if (ToolBox.random() < softUsedResource) {
    238                    nrSoftUsedRes++;
    239                    rooms[room].addDiscouragedSlot(slot);
    240                }
    241            }
    242            for (int instr = 0; instr < nrInstructors; instr++) {
    243                if (timetable4instr[instr][slot] == 0) {
    244                    if (ToolBox.random() < hardFreeResource) {
    245                        nrHardFreeRes++;
    246                        instructors[instr].addProhibitedSlot(slot);
    247                    } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) {
    248                        nrSoftFreeRes++;
    249                        instructors[instr].addDiscouragedSlot(slot);
    250                    }
    251                } else if (ToolBox.random() < softUsedResource) {
    252                    nrSoftUsedRes++;
    253                    instructors[instr].addDiscouragedSlot(slot);
    254                }
    255            }
    256            for (int aclass = 0; aclass < nrClasses; aclass++) {
    257                if (timetable4class[aclass][slot] == 0) {
    258                    if (ToolBox.random() < hardFreeResource) {
    259                        nrHardFreeRes++;
    260                        classes[aclass].addProhibitedSlot(slot);
    261                    } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) {
    262                        nrSoftFreeRes++;
    263                        classes[aclass].addDiscouragedSlot(slot);
    264                    }
    265                } else if (ToolBox.random() < softUsedResource) {
    266                    nrSoftUsedRes++;
    267                    classes[aclass].addDiscouragedSlot(slot);
    268                }
    269            }
    270        }
    271        int nrSoftFreeAct = 0;
    272        int nrSoftUsedAct = 0;
    273        int nrHardFreeAct = 0;
    274        for (int i = 0; i < m.variables().size(); i++) {
    275            Activity activity = m.variables().get(i);
    276            for (int slot = 0; slot < nrSlots; slot++) {
    277                int start = starts.get(i);
    278                if (slot < start || slot >= start + activity.getLength()) {
    279                    if (ToolBox.random() < hardFreeActivity) {
    280                        nrHardFreeAct++;
    281                        activity.addProhibitedSlot(slot);
    282                    } else if (ToolBox.random() < (softFreeActivity / (1.0 - hardFreeActivity))) {
    283                        nrSoftFreeAct++;
    284                        activity.addDiscouragedSlot(slot);
    285                    }
    286                } else {
    287                    if (ToolBox.random() < softUsedActivity) {
    288                        nrSoftUsedAct++;
    289                        activity.addDiscouragedSlot(slot);
    290                    }
    291                }
    292            }
    293            activity.init();
    294        }
    295        for (int i = 0; i < nrDependencies;) {
    296            int ac1 = ToolBox.random(m.variables().size());
    297            int ac2 = ToolBox.random(m.variables().size());
    298            while (ac1 == ac2) {
    299                ac2 = ToolBox.random(m.variables().size());
    300            }
    301            int s1 = starts.get(ac1);
    302            int s2 = starts.get(ac2);
    303            Activity a1 = m.variables().get(ac1);
    304            Activity a2 = m.variables().get(ac2);
    305            Dependence dep = null;
    306            if (s1 < s2) {
    307                if (s1 + a1.getLength() == s2)
    308                    dep = new Dependence("d" + (i + 1), Dependence.TYPE_CLOSELY_BEFORE);
    309                else if (s1 + a1.getLength() < s2)
    310                    dep = new Dependence("d" + (i + 1), Dependence.TYPE_BEFORE);
    311            } else {
    312                if (s2 == s1 + a1.getLength())
    313                    dep = new Dependence("d" + (i + 1), Dependence.TYPE_CLOSELY_AFTER);
    314                else if (s2 > s1 + a1.getLength())
    315                    dep = new Dependence("d" + (i + 1), Dependence.TYPE_AFTER);
    316            }
    317            if (dep != null) {
    318                dep.addVariable(a1);
    319                dep.addVariable(a2);
    320                m.addConstraint(dep);
    321                i++;
    322            }
    323        }
    324        for (int i = 0; i < m.variables().size(); i++) {
    325            Activity activity = m.variables().get(i);
    326            // sLogger.debug("-- processing activity "+activity.getName());
    327            int start = starts.get(i);
    328            int room = arooms.get(i);
    329            Location location = null;
    330            for (Location l : activity.values(assignment)) {
    331                if (l.getSlot() == start && l.getResource(0).getResourceId().equals("r" + (room + 1))) {
    332                    location = l;
    333                    break;
    334                }
    335            }
    336            if (location != null) {
    337                Set<Location> conflicts = m.conflictValues(assignment, location);
    338                if (!conflicts.isEmpty()) {
    339                    sLogger.warn("Unable to assign " + location.getName() + " to " + activity.getName() + ", reason:");
    340                    for (Constraint<Activity, Location> c : activity.constraints()) {
    341                        Set<Location> cc = new HashSet<Location>();
    342                        c.computeConflicts(assignment, location, cc);
    343                        if (!cc.isEmpty())
    344                            sLogger.warn("  -- Constraint " + c.getName() + " causes conflicts " + cc);
    345                    }
    346                } else {
    347                    assignment.assign(0, location);
    348                    activity.setInitialAssignment(location);
    349                }
    350                // sLogger.debug("  -- location "+location.getName()+" found");
    351                activity.setInitialAssignment(location);
    352            } else {
    353                sLogger.warn("Unable to assign " + activity.getName() + " -- no location matching slot=" + start
    354                        + " room='R" + (room + 1) + "'");
    355            }
    356        }
    357        if (!cfg.getPropertyBoolean("General.InitialAssignment", true)) {
    358            for (int i = 0; i < m.variables().size(); i++) {
    359                Activity activity = m.variables().get(i);
    360                assignment.unassign(0, activity);
    361            }
    362        }
    363
    364        int forcedPerturbances = cfg.getPropertyInt("General.ForcedPerturbances", 0);
    365        if (forcedPerturbances > 0) {
    366            List<Activity> initialVariables = new ArrayList<Activity>();
    367            for (Activity v : m.variables()) {
    368                if (v.getInitialAssignment() != null)
    369                    initialVariables.add(v);
    370            }
    371            for (int i = 0; i < forcedPerturbances; i++) {
    372                if (initialVariables.isEmpty())
    373                    break;
    374                Activity var = ToolBox.random(initialVariables);
    375                initialVariables.remove(var);
    376                var.removeInitialValue();
    377            }
    378        }
    379
    380        sLogger.debug("-- Generator Info ---------------------------------------------------------");
    381        sLogger.debug("  Total number of " + m.variables().size() + " activities generated.");
    382        sLogger.debug("  Total number of " + usedSlots + " slots are filled (" + ((100.0 * usedSlots) / totalSlots)
    383                + "% filled).");
    384        sLogger.debug("  Average length of an activity is " + (((double) usedSlots) / m.variables().size()));
    385        sLogger.debug("  Total number of hard constraints posted on free slots on activities: " + nrHardFreeAct);
    386        sLogger.debug("  Total number of soft constraints posted on free slots on activities: " + nrSoftFreeAct);
    387        sLogger.debug("  Total number of soft constraints posted on used slots on activities: " + nrSoftUsedAct);
    388        sLogger.debug("  Total number of hard constraints posted on free slots on resources: " + nrHardFreeRes);
    389        sLogger.debug("  Total number of soft constraints posted on free slots on resources: " + nrSoftFreeRes);
    390        sLogger.debug("  Total number of soft constraints posted on used slots on resources: " + nrSoftUsedRes);
    391        sLogger.debug("  Total number of " + nrDependencies + " dependencies generated.");
    392        sLogger.debug("---------------------------------------------------------------------------");
    393
    394        return m;
    395    }
    396
    397    public static void main(String[] args) {
    398        try {
    399            // Configure logging
    400            ToolBox.configureLogging();
    401
    402            // Load properties (take first argument as input file, containing key=value lines)
    403            DataProperties properties = new DataProperties();
    404            properties.load(new FileInputStream(args[0]));
    405
    406            // Generate model
    407            Assignment<Activity, Location> assignment = new DefaultSingleAssignment<Activity, Location>();
    408            TimetableModel model = TimetableModel.generate(new DataProperties(), assignment);
    409            System.out.println(model.getInfo(assignment));
    410
    411            // Save solution (take second argument as output file)
    412            model.saveAsXML(properties, true, new Solution<Activity, Location>(model, assignment), assignment, new File(args[1]));
    413        } catch (Exception e) {
    414            e.printStackTrace();
    415        }
    416    }
    417
    418    public void saveAsXML(DataProperties cfg, boolean gen, Solution<Activity, Location> solution, Assignment<Activity, Location> assignment, File outFile) throws IOException {
    419        outFile.getParentFile().mkdirs();
    420        sLogger.debug("Writting XML data to:" + outFile);
    421
    422        Document document = DocumentHelper.createDocument();
    423        document.addComment("Interactive Timetabling - University Timetable Generator (version 2.0)");
    424        if (assignment == null && solution != null)
    425            assignment = solution.getAssignment();
    426        if (assignment == null)
    427            assignment = new DefaultSingleAssignment<Activity, Location>();
    428
    429        if (!assignedVariables(assignment).isEmpty()) {
    430            StringBuffer comments = new StringBuffer("Solution Info:\n");
    431            Map<String, String> solutionInfo = (solution == null ? getInfo(assignment) : solution.getInfo());
    432            for (String key : new TreeSet<String>(solutionInfo.keySet())) {
    433                String value = solutionInfo.get(key);
    434                comments.append("    " + key + ": " + value + "\n");
    435            }
    436            document.addComment(comments.toString());
    437        }
    438
    439        Element root = document.addElement("Timetable");
    440        if (gen) {
    441            Element generator = root.addElement("Generator");
    442            generator.addAttribute("version", "2.0");
    443            generator.addElement("DaysPerWeek").setText(String.valueOf(iNrDays));
    444            generator.addElement("SlotsPerDay").setText(String.valueOf(iNrHours));
    445            generator.addElement("NrRooms").setText(cfg.getProperty("Generator.NrRooms", "20"));
    446            generator.addElement("NrInstructors").setText(cfg.getProperty("Generator.NrInstructors", "20"));
    447            generator.addElement("NrClasses").setText(cfg.getProperty("Generator.NrClasses", "20"));
    448            generator.addElement("FillFactor").setText(cfg.getProperty("Generator.FillFactor", "0.8"));
    449            generator.addElement("ActivityLengthMax").setText(cfg.getProperty("Generator.ActivityLengthMax", "5"));
    450            generator.addElement("NrGroupsOfRooms").setText(cfg.getProperty("Generator.NrGroupsOfRooms", "20"));
    451            generator.addElement("NrRoomsInGroupMin").setText(cfg.getProperty("Generator.NrRoomsInGroupMin", "1"));
    452            generator.addElement("NrRoomsInGroupMax").setText(cfg.getProperty("Generator.NrRoomsInGroupMax", "10"));
    453            generator.addElement("NrRoomInGroupMin").setText(cfg.getProperty("Generator.NrRoomInGroupMin", "1"));
    454            generator.addElement("HardFreeResource").setText(cfg.getProperty("Generator.HardFreeResource", "0.05"));
    455            generator.addElement("SoftFreeResource").setText(cfg.getProperty("Generator.SoftFreeResource", "0.3"));
    456            generator.addElement("SoftUsedResource").setText(cfg.getProperty("Generator.SoftUsedResource", "0.05"));
    457            generator.addElement("SoftUsedActivity").setText(cfg.getProperty("Generator.SoftUsedActivity", "0.05"));
    458            generator.addElement("SoftFreeActivity").setText(cfg.getProperty("Generator.SoftFreeActivity", "0.3"));
    459            generator.addElement("HardFreeActivity").setText(cfg.getProperty("Generator.HardFreeActivity", "0.05"));
    460            generator.addElement("NrDependencies").setText(cfg.getProperty("Generator.NrDependencies", "50"));
    461        }
    462
    463        ArrayList<Resource> rooms = new ArrayList<Resource>();
    464        ArrayList<Resource> classes = new ArrayList<Resource>();
    465        ArrayList<Resource> instructors = new ArrayList<Resource>();
    466        ArrayList<Resource> specials = new ArrayList<Resource>();
    467        ArrayList<Dependence> dependencies = new ArrayList<Dependence>();
    468
    469        for (Constraint<Activity, Location> c : constraints()) {
    470            if (c instanceof Resource) {
    471                Resource r = (Resource) c;
    472                switch (r.getType()) {
    473                    case Resource.TYPE_ROOM:
    474                        rooms.add(r);
    475                        break;
    476                    case Resource.TYPE_CLASS:
    477                        classes.add(r);
    478                        break;
    479                    case Resource.TYPE_INSTRUCTOR:
    480                        instructors.add(r);
    481                        break;
    482                    default:
    483                        specials.add(r);
    484                }
    485            } else if (c instanceof Dependence) {
    486                dependencies.add((Dependence) c);
    487            }
    488        }
    489
    490        Element problem = root.addElement("Problem");
    491        problem.addAttribute("version", "2.0");
    492        Element problemGen = problem.addElement("General");
    493        problemGen.addElement("DaysPerWeek").setText(String.valueOf(iNrDays));
    494        problemGen.addElement("SlotsPerDay").setText(String.valueOf(iNrHours));
    495        Element resourceGen = problemGen.addElement("Resources");
    496        resourceGen.addElement("Classrooms").setText(String.valueOf(rooms.size()));
    497        resourceGen.addElement("Teachers").setText(String.valueOf(instructors.size()));
    498        resourceGen.addElement("Classes").setText(String.valueOf(classes.size()));
    499        resourceGen.addElement("Special").setText(String.valueOf(specials.size()));
    500        problemGen.addElement("Activities").setText(String.valueOf(variables().size()));
    501        problemGen.addElement("Dependences").setText(String.valueOf(dependencies.size()));
    502
    503        Element resources = problem.addElement("Resources");
    504
    505        Element resEl = resources.addElement("Classrooms");
    506        for (Resource r : rooms) {
    507            Element el = resEl.addElement("Resource");
    508            el.addAttribute("id", r.getResourceId());
    509            el.addElement("Name").setText(r.getName());
    510            Element pref = el.addElement("TimePreferences");
    511            for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
    512                pref.addElement("Soft").setText(slot.toString());
    513            for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
    514                pref.addElement("Hard").setText(slot.toString());
    515        }
    516
    517        resEl = resources.addElement("Teachers");
    518        for (Resource r : instructors) {
    519            Element el = resEl.addElement("Resource");
    520            el.addAttribute("id", r.getResourceId());
    521            el.addElement("Name").setText(r.getName());
    522            Element pref = el.addElement("TimePreferences");
    523            for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
    524                pref.addElement("Soft").setText(slot.toString());
    525            for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
    526                pref.addElement("Hard").setText(slot.toString());
    527        }
    528
    529        resEl = resources.addElement("Classes");
    530        for (Resource r : classes) {
    531            Element el = resEl.addElement("Resource");
    532            el.addAttribute("id", r.getResourceId());
    533            el.addElement("Name").setText(r.getName());
    534            Element pref = el.addElement("TimePreferences");
    535            for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
    536                pref.addElement("Soft").setText(slot.toString());
    537            for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
    538                pref.addElement("Hard").setText(slot.toString());
    539        }
    540
    541        resEl = resources.addElement("Special");
    542        for (Resource r : specials) {
    543            Element el = resEl.addElement("Resource");
    544            el.addAttribute("id", r.getResourceId());
    545            el.addElement("Name").setText(r.getName());
    546            Element pref = el.addElement("TimePreferences");
    547            for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
    548                pref.addElement("Soft").setText(slot.toString());
    549            for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
    550                pref.addElement("Hard").setText(slot.toString());
    551        }
    552
    553        boolean hasSolution = false;
    554        Element actEl = problem.addElement("Activities");
    555        for (Activity a : variables()) {
    556            Element el = actEl.addElement("Activity");
    557            el.addAttribute("id", a.getActivityId());
    558            el.addElement("Name").setText(a.getName());
    559            el.addElement("Length").setText(String.valueOf(a.getLength()));
    560            if (assignment.getValue(a) != null)
    561                hasSolution = true;
    562            Element pref = el.addElement("TimePreferences");
    563            for (Integer slot : new TreeSet<Integer>(a.getDiscouragedSlots()))
    564                pref.addElement("Soft").setText(slot.toString());
    565            for (Integer slot : new TreeSet<Integer>(a.getProhibitedSlots()))
    566                pref.addElement("Hard").setText(slot.toString());
    567            Element reqRes = el.addElement("RequiredResources");
    568            for (List<Resource> gr : a.getResourceGroups()) {
    569                if (gr.size() == 1) {
    570                    reqRes.addElement("Resource").setText(gr.get(0).getResourceId());
    571                } else {
    572                    Element grEl = reqRes.addElement("Group").addAttribute("conjunctive", "no");
    573                    for (Resource r : gr)
    574                        grEl.addElement("Resource").setText(r.getResourceId());
    575                }
    576            }
    577        }
    578
    579        Element depEl = problem.addElement("Dependences");
    580        for (Dependence d : dependencies) {
    581            Element el = depEl.addElement("Dependence");
    582            el.addAttribute("id", d.getResourceId());
    583            el.addElement("FirstActivity").setText((d.first()).getActivityId());
    584            el.addElement("SecondActivity").setText((d.second()).getActivityId());
    585            switch (d.getType()) {
    586                case Dependence.TYPE_AFTER:
    587                    el.addElement("Operator").setText("After");
    588                    break;
    589                case Dependence.TYPE_BEFORE:
    590                    el.addElement("Operator").setText("Before");
    591                    break;
    592                case Dependence.TYPE_CLOSELY_BEFORE:
    593                    el.addElement("Operator").setText("Closely before");
    594                    break;
    595                case Dependence.TYPE_CLOSELY_AFTER:
    596                    el.addElement("Operator").setText("Closely after");
    597                    break;
    598                case Dependence.TYPE_CONCURRENCY:
    599                    el.addElement("Operator").setText("Concurrently");
    600                    break;
    601                default:
    602                    el.addElement("Operator").setText("Unknown");
    603            }
    604        }
    605
    606        if (hasSolution) {
    607            Element solutionEl = root.addElement("Solution");
    608            solutionEl.addAttribute("version", "2.0");
    609            for (Activity a : variables()) {
    610                Element el = solutionEl.addElement("Activity");
    611                el.addAttribute("id", a.getActivityId());
    612                Location location = assignment.getValue(a);
    613                if (location != null) {
    614                    el.addElement("StartTime").setText(String.valueOf(location.getSlot()));
    615                    Element res = el.addElement("UsedResources");
    616                    for (int i = 0; i < location.getResources().length; i++)
    617                        res.addElement("Resource").setText(location.getResources()[i].getResourceId());
    618                }
    619            }
    620        }
    621
    622        FileOutputStream fos = new FileOutputStream(outFile);
    623        (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(document);
    624        fos.flush();
    625        fos.close();
    626    }
    627
    628    public static TimetableModel loadFromXML(File inFile, Assignment<Activity, Location> assignment) throws IOException, DocumentException {
    629        Document document = (new SAXReader()).read(inFile);
    630        Element root = document.getRootElement();
    631        if (!"Timetable".equals(root.getName())) {
    632            sLogger.error("Given XML file is not interactive timetabling problem.");
    633            return null;
    634        }
    635
    636        Element problem = root.element("Problem");
    637        Element problemGen = problem.element("General");
    638        TimetableModel m = new TimetableModel(Integer.parseInt(problemGen.elementText("DaysPerWeek")), Integer
    639                .parseInt(problemGen.elementText("SlotsPerDay")));
    640
    641        Element resources = problem.element("Resources");
    642
    643        HashMap<String, Resource> resTab = new HashMap<String, Resource>();
    644
    645        Element resEl = resources.element("Classrooms");
    646        for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
    647            Element el = (Element) i.next();
    648            Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_ROOM, el.elementText("Name"));
    649            Element pref = el.element("TimePreferences");
    650            for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
    651                r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
    652            for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
    653                r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
    654            m.addConstraint(r);
    655            resTab.put(r.getResourceId(), r);
    656        }
    657
    658        resEl = resources.element("Teachers");
    659        for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
    660            Element el = (Element) i.next();
    661            Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_INSTRUCTOR, el.elementText("Name"));
    662            Element pref = el.element("TimePreferences");
    663            for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
    664                r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
    665            for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
    666                r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
    667            m.addConstraint(r);
    668            resTab.put(r.getResourceId(), r);
    669        }
    670
    671        resEl = resources.element("Classes");
    672        for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
    673            Element el = (Element) i.next();
    674            Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_CLASS, el.elementText("Name"));
    675            Element pref = el.element("TimePreferences");
    676            for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
    677                r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
    678            for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
    679                r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
    680            m.addConstraint(r);
    681            resTab.put(r.getResourceId(), r);
    682        }
    683
    684        resEl = resources.element("Special");
    685        for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
    686            Element el = (Element) i.next();
    687            Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_OTHER, el.elementText("Name"));
    688            Element pref = el.element("TimePreferences");
    689            for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
    690                r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
    691            for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
    692                r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
    693            m.addConstraint(r);
    694            resTab.put(r.getResourceId(), r);
    695        }
    696
    697        Element actEl = problem.element("Activities");
    698        HashMap<String, Activity> actTab = new HashMap<String, Activity>();
    699        for (Iterator<?> i = actEl.elementIterator("Activity"); i.hasNext();) {
    700            Element el = (Element) i.next();
    701            Activity a = new Activity(Integer.parseInt(el.elementText("Length")), el.attributeValue("id"), el
    702                    .elementText("Name"));
    703            Element pref = el.element("TimePreferences");
    704            for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
    705                a.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
    706            for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
    707                a.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
    708            Element req = el.element("RequiredResources");
    709            for (Iterator<?> j = req.elementIterator(); j.hasNext();) {
    710                Element rqEl = (Element) j.next();
    711                if ("Resource".equals(rqEl.getName())) {
    712                    a.addResourceGroup(resTab.get(rqEl.getText()));
    713                } else if ("Group".equals(rqEl.getName())) {
    714                    if ("no".equalsIgnoreCase(rqEl.attributeValue("conjunctive"))
    715                            || "false".equalsIgnoreCase(rqEl.attributeValue("conjunctive"))) {
    716                        List<Resource> gr = new ArrayList<Resource>();
    717                        for (Iterator<?> k = rqEl.elementIterator("Resource"); k.hasNext();)
    718                            gr.add(resTab.get(((Element) k.next()).getText()));
    719                        a.addResourceGroup(gr);
    720                    } else {
    721                        for (Iterator<?> k = rqEl.elementIterator("Resource"); k.hasNext();)
    722                            a.addResourceGroup(resTab.get(((Element) k.next()).getText()));
    723                    }
    724                }
    725            }
    726            m.addVariable(a);
    727            a.init();
    728            actTab.put(a.getActivityId(), a);
    729        }
    730
    731        Element depEl = problem.element("Dependences");
    732        for (Iterator<?> i = depEl.elementIterator("Dependence"); i.hasNext();) {
    733            Element el = (Element) i.next();
    734            int type = Dependence.TYPE_NO_DEPENDENCE;
    735            String typeStr = el.elementText("Operator");
    736            if ("After".equals(typeStr))
    737                type = Dependence.TYPE_AFTER;
    738            else if ("Before".equals(typeStr))
    739                type = Dependence.TYPE_BEFORE;
    740            else if ("After".equals(typeStr))
    741                type = Dependence.TYPE_AFTER;
    742            else if ("Closely before".equals(typeStr))
    743                type = Dependence.TYPE_CLOSELY_BEFORE;
    744            else if ("Closely after".equals(typeStr))
    745                type = Dependence.TYPE_CLOSELY_AFTER;
    746            else if ("Concurrently".equals(typeStr))
    747                type = Dependence.TYPE_CONCURRENCY;
    748            Dependence d = new Dependence(el.attributeValue("id"), type);
    749            d.addVariable(actTab.get(el.elementText("FirstActivity")));
    750            d.addVariable(actTab.get(el.elementText("SecondActivity")));
    751            m.addConstraint(d);
    752        }
    753
    754        Element solEl = root.element("Solution");
    755        if (solEl != null) {
    756            for (Iterator<?> i = solEl.elementIterator("Activity"); i.hasNext();) {
    757                Element el = (Element) i.next();
    758                Activity a = actTab.get(el.attributeValue("id"));
    759                if (a == null)
    760                    continue;
    761                int slot = Integer.parseInt(el.elementText("StartTime"));
    762                Element usResEl = el.element("UsedResources");
    763                List<Resource> res = new ArrayList<Resource>();
    764                for (Iterator<?> j = usResEl.elementIterator("Resource"); j.hasNext();)
    765                    res.add(resTab.get(((Element) j.next()).getText()));
    766                for (Location loc : a.values(assignment)) {
    767                    if (loc.getSlot() != slot || loc.getResources().length != res.size())
    768                        continue;
    769                    boolean same = true;
    770                    for (int j = 0; j < loc.getResources().length && same; j++)
    771                        if (!res.get(j).equals(loc.getResources()[j]))
    772                            same = false;
    773                    if (!same)
    774                        continue;
    775                    a.setInitialAssignment(loc);
    776                    if (assignment != null)
    777                        assignment.assign(0, loc);
    778                    break;
    779                }
    780            }
    781        }
    782        return m;
    783    }
    784}