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