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