    001package org.cpsolver.exam;
    002
    003import java.io.File;
    004import java.io.IOException;
    005import java.io.PrintWriter;
    006import java.util.ArrayList;
    007import java.util.HashMap;
    008import java.util.HashSet;
    009import java.util.List;
    010import java.util.Locale;
    011import java.util.Map;
    012import java.util.Set;
    013
    014
    015import org.cpsolver.exam.model.Exam;
    016import org.cpsolver.exam.model.ExamModel;
    017import org.cpsolver.exam.model.ExamPlacement;
    018import org.cpsolver.exam.model.ExamRoom;
    019import org.cpsolver.exam.model.ExamRoomPlacement;
    020import org.cpsolver.exam.model.ExamStudent;
    021import org.cpsolver.ifs.assignment.Assignment;
    022import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
    023import org.cpsolver.ifs.util.DataProperties;
    024import org.cpsolver.ifs.util.Progress;
    025import org.cpsolver.ifs.util.ToolBox;
    026import org.dom4j.io.SAXReader;
    027
    028/**
    029 * A simple program that prints a few statistics about the given examination problem in the format of the MISTA 2013 paper
    030 * (entitled Real-life Examination Timetabling).
    031 * It outputs data for the Table 1 (characteristics of the data sets) and Table 2 (number of rooms and exams of a certain size).
    032 * <br>
    033 * Usage:
    034 * <pre><code>java -cp cpsolver-all-1.2.jar org.cpsolver.exam.MistaTables problem1.xml problem2.xml ...</code></pre>
    035 * <br>
    036 *
    037 * @author  Tomáš Müller
    038 * @version ExamTT 1.3 (Examination Timetabling)<br>
    039 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
    040 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    041 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    042 * <br>
    043 *          This library is free software; you can redistribute it and/or modify
    044 *          it under the terms of the GNU Lesser General Public License as
    045 *          published by the Free Software Foundation; either version 3 of the
    046 *          License, or (at your option) any later version. <br>
    047 * <br>
    048 *          This library is distributed in the hope that it will be useful, but
    049 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    050 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    051 *          Lesser General Public License for more details. <br>
    052 * <br>
    053 *          You should have received a copy of the GNU Lesser General Public
    054 *          License along with this library; if not see
    055 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    056 */
    057public class MistaTables {
    058    private static org.apache.logging.log4j.Logger sLog = org.apache.logging.log4j.LogManager.getLogger(MistaTables.class);
    059    private static java.text.DecimalFormat sNF = new java.text.DecimalFormat("###,##0", new java.text.DecimalFormatSymbols(Locale.US));
    060    private static java.text.DecimalFormat sDF = new java.text.DecimalFormat("###,##0.000", new java.text.DecimalFormatSymbols(Locale.US));
    061
    062    public static void main(String[] args) {
    063        try {
    064            ToolBox.configureLogging();
    065            DataProperties config = new DataProperties();
    066
    067            Table[] tables = new Table[] { new Problems(), new Rooms() };
    068
    069            for (int i = 0; i < args.length; i++) {
    070                File file = new File(args[i]);
    071                sLog.info("Loading " + file);
    072                ExamModel model = new ExamModel(config);
    073                Assignment<Exam, ExamPlacement> assignment = new DefaultSingleAssignment<Exam, ExamPlacement>();
    074                model.load(new SAXReader().read(file), assignment);
    075
    076                String name = file.getName();
    077                if (name.contains("."))
    078                    name = name.substring(0, name.indexOf('.'));
    079
    080                for (Table table: tables)
    081                    table.add(name, model);
    082
    083                Progress.removeInstance(model);
    084            }
    085
    086            sLog.info("Saving tables...");
    087            File output = new File("tables"); output.mkdir();
    088            for (Table table: tables)
    089                table.save(output);
    090
    091            sLog.info("All done.");
    092        } catch (Exception e) {
    093            sLog.error(e.getMessage(), e);
    094        }
    095    }
    096
    097    public static class Counter {
    098        private double iTotal = 0.0, iMin = 0.0, iMax = 0.0, iTotalSquare = 0.0;
    099        private int iCount = 0;
    100
    101        public Counter() {
    102        }
    103
    104        public void inc(double value) {
    105                if (iCount == 0) {
    106                        iTotal = value;
    107                        iMin = value;
    108                        iMax = value;
    109                        iTotalSquare = value * value;
    110                } else {
    111                        iTotal += value;
    112                        iMin = Math.min(iMin, value);
    113                        iMax = Math.max(iMax, value);
    114                        iTotalSquare += value * value;
    115                }
    116                iCount ++;
    117        }
    118
    119        public int count() { return iCount; }
    120        public double sum() { return iTotal; }
    121        public double min() { return iMin; }
    122        public double max() { return iMax; }
    123        public double rms() { return (iCount == 0 ? 0.0 : Math.sqrt(iTotalSquare / iCount) - Math.abs(avg())); }
    124        public double avg() { return (iCount == 0 ? 0.0 : iTotal / iCount); }
    125
    126        @Override
    127        public String toString() {
    128                return sDF.format(sum()) +
    129                " (min: " + sDF.format(min()) +
    130                ", max: " + sDF.format(max()) +
    131                ", avg: " + sDF.format(avg()) +
    132                ", rms: " + sDF.format(rms()) +
    133                ", cnt: " + count() + ")";
    134        }
    135    }
    136
    137    public static abstract class Table {
    138        private List<String> iProblems = new ArrayList<String>();
    139        private List<String> iProperties = new ArrayList<String>();
    140        private Map<String, Map<String, String>> iData = new HashMap<String, Map<String, String>>();
    141
    142        public abstract void add(String problem, ExamModel model);
    143
    144
    145        protected void add(String problem, String property, int value) {
    146            add(problem, property, sNF.format(value));
    147        }
    148
    149        protected void add(String problem, String property, double value) {
    150            add(problem, property, sDF.format(value));
    151        }
    152
    153        protected void add(String problem, String property, Counter value) {
    154            add(problem, property, sDF.format(value.avg()) + " ± " + sDF.format(value.rms()));
    155        }
    156
    157        protected void add(String problem, String property, String value) {
    158            if (!iProblems.contains(problem)) iProblems.add(problem);
    159            if (!iProperties.contains(property)) iProperties.add(property);
    160            Map<String, String> table = iData.get(problem);
    161            if (table == null) {
    162                table = new HashMap<String, String>();
    163                iData.put(problem, table);
    164            }
    165            table.put(property, value);
    166        }
    167
    168        public void save(File folder) throws IOException {
    169            PrintWriter pw = new PrintWriter(new File(folder, getClass().getSimpleName() + ".csv"));
    170
    171            pw.print("Problem");
    172            for (String problem: iProblems) pw.print(",\"" + problem + "\"");
    173            pw.println();
    174
    175            for (String property: iProperties) {
    176                pw.print("\"" + property + "\"");
    177                for (String problem: iProblems) {
    178                    String value = iData.get(problem).get(property);
    179                    pw.print("," + (value == null ? "" : "\"" + value + "\""));
    180                }
    181                pw.println();
    182            }
    183
    184            pw.flush(); pw.close();
    185        }
    186    }
    187
    188    public static class Problems extends Table {
    189        @Override
    190        public void add(String problem, ExamModel model) {
    191            int enrollments = 0;
    192            for (ExamStudent student: model.getStudents())
    193                enrollments += student.variables().size();
    194
    195            int examSeating = 0;
    196            int examsFixedInTime = 0, examsFixedInRoom = 0, examsLarge = 0, examsToSplit = 0, examsWithOriginalRoom = 0;
    197            Counter avgPeriods = new Counter(), avgRooms = new Counter(), avgBigRooms = new Counter();
    198            double density = 0;
    199
    200            for (Exam exam: model.variables()) {
    201                if (exam.hasAltSeating()) examSeating ++;
    202
    203                if (exam.getPeriodPlacements().size() <= 2)
    204                    examsFixedInTime ++;
    205                if (exam.getRoomPlacements().size() <= 2)
    206                    examsFixedInRoom ++;
    207
    208                for (ExamRoomPlacement room: exam.getRoomPlacements()) {
    209                    if (room.getPenalty() < -2) { examsWithOriginalRoom ++; break; }
    210                }
    211
    212                int bigEnoughRooms = 0;
    213                for (ExamRoomPlacement room: exam.getRoomPlacements()) {
    214                    if (room.getSize(exam.hasAltSeating()) >= exam.getSize()) bigEnoughRooms ++;
    215                }
    216
    217                if (bigEnoughRooms == 0)
    218                    examsToSplit ++;
    219
    220                if (exam.getSize() >= 600)
    221                    examsLarge ++;
    222
    223                avgPeriods.inc(exam.getPeriodPlacements().size());
    224                avgRooms.inc(exam.getRoomPlacements().size());
    225                avgBigRooms.inc(bigEnoughRooms);
    226
    227                density += exam.nrStudentCorrelatedExams();
    228            }
    229
    230            add(problem, "Exams", model.variables().size());
    231            add(problem, "   with exam seating", examSeating);
    232            add(problem, "Students", model.getStudents().size());
    233            add(problem, "Enrollments", enrollments);
    234            add(problem, "Distribution constraints", model.getDistributionConstraints().size());
    235
    236            add(problem, "Exams fixed in time", examsFixedInTime);
    237            add(problem, "Exams fixed in room", examsFixedInRoom);
    238            add(problem, "Large exams (600+)", examsLarge);
    239            add(problem, "Exams needing a room split", examsToSplit);
    240            add(problem, "Exams with original room", examsWithOriginalRoom);
    241            add(problem, "Density", sDF.format(100.0 * density / (model.variables().size() * (model.variables().size() - 1))) + "%");
    242
    243            add(problem, "Average periods", avgPeriods);
    244            add(problem, "Average rooms", avgRooms);
    245            add(problem, "   that are big enough", avgBigRooms);
    246        }
    247    }
    248
    249    public static class Rooms extends Table {
    250        @Override
    251        public void add(String problem, ExamModel model) {
    252            int[] sizes = new int[] { 0, 100, 200, 400, 600 };
    253            int[] nrRooms = new int[] { 0, 0, 0, 0, 0 }, nrRoomsAlt = new int[] { 0, 0, 0, 0, 0 };
    254            int[] nrExams = new int[] { 0, 0, 0, 0, 0 }, nrExamsAlt = new int[] { 0, 0, 0, 0, 0 };
    255            double[] density = new double[] { 0, 0, 0, 0, 0 };
    256
    257            Set<ExamRoom> rooms = new HashSet<ExamRoom>();
    258            for (Exam exam: model.variables()) {
    259                for (ExamRoomPlacement room: exam.getRoomPlacements()) {
    260                    if (rooms.add(room.getRoom())) {
    261                        for (int i = 0; i < sizes.length; i++) {
    262                            if (room.getRoom().getSize() >= sizes[i])
    263                                nrRooms[i] ++;
    264                            if (room.getRoom().getAltSize() >= sizes[i])
    265                                nrRoomsAlt[i] ++;
    266                        }
    267                    }
    268                }
    269
    270                for (int i = 0; i < sizes.length; i++) {
    271                    if (exam.getSize() >= sizes[i]) {
    272                        nrExams[i] ++;
    273                        if (exam.hasAltSeating())
    274                            nrExamsAlt[i] ++;
    275                        for (Exam x: exam.getStudentCorrelatedExams())
    276                            if (x.getSize() >= sizes[i])
    277                                density[i] ++;
    278                    }
    279                }
    280            }
    281
    282            for (int i = 0; i < sizes.length; i++) {
    283                add(problem, "Rooms" + (sizes[i] == 0 ? "" : " (≥ " + sizes[i] + " seats)"), sNF.format(nrRooms[i]) + (sizes[i] == 0 ? "" : " (" + sNF.format(nrRoomsAlt[i]) + ")"));
    284            }
    285            for (int i = 0; i < sizes.length; i++) {
    286                add(problem, "Exams" + (sizes[i] == 0 ? "" : " (≥ " + sizes[i] + " seats)"), sNF.format(nrExams[i]) + (sizes[i] == 0 ? "" : " (" + sNF.format(nrExamsAlt[i]) + ")"));
    287            }
    288            for (int i = 0; i < sizes.length; i++) {
    289                add(problem, "Density" + (sizes[i] == 0 ? "" : " (≥ " + sizes[i] + " seats)"), sDF.format(100.0 * density[i] / (nrExams[i] * (nrExams[i] - 1))) + "%");
    290            }
    291        }
    292    }
    293
    294}