001 package net.sf.cpsolver.studentsct.extension;
002
003 import java.util.HashMap;
004 import java.util.HashSet;
005 import java.util.Iterator;
006 import java.util.Map;
007 import java.util.Set;
008
009 import org.apache.log4j.Logger;
010
011 import net.sf.cpsolver.coursett.Constants;
012 import net.sf.cpsolver.coursett.model.Placement;
013 import net.sf.cpsolver.coursett.model.RoomLocation;
014 import net.sf.cpsolver.coursett.model.TimeLocation;
015 import net.sf.cpsolver.ifs.extension.Extension;
016 import net.sf.cpsolver.ifs.model.ModelListener;
017 import net.sf.cpsolver.ifs.solver.Solver;
018 import net.sf.cpsolver.ifs.util.DataProperties;
019 import net.sf.cpsolver.ifs.util.DistanceMetric;
020 import net.sf.cpsolver.studentsct.StudentSectioningModel;
021 import net.sf.cpsolver.studentsct.model.CourseRequest;
022 import net.sf.cpsolver.studentsct.model.Enrollment;
023 import net.sf.cpsolver.studentsct.model.Request;
024 import net.sf.cpsolver.studentsct.model.Section;
025 import net.sf.cpsolver.studentsct.model.Student;
026
027 /**
028 * This extension computes student distant conflicts. Two sections that are
029 * attended by the same student are considered in a distance conflict if they
030 * are back-to-back taught in locations that are two far away. This means that
031 * the (walking) distance in minutes between the two classes are longer than
032 * the break time of the earlier class. See {@link DistanceMetric} for more details.
033 *
034 * @see TimeLocation
035 * @see Placement
036 *
037 * <br>
038 * <br>
039 *
040 * @version StudentSct 1.2 (Student Sectioning)<br>
041 * Copyright (C) 2007 - 2010 Tomas Muller<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 */
059
060 public class DistanceConflict extends Extension<Request, Enrollment> implements ModelListener<Request, Enrollment> {
061 private static Logger sLog = Logger.getLogger(DistanceConflict.class);
062 private Set<Conflict> iAllConflicts = new HashSet<Conflict>();
063 /** Debug flag */
064 public static boolean sDebug = false;
065 private Request iOldVariable = null;
066 private Enrollment iUnassignedValue = null;
067 private DistanceMetric iDistanceMetric = null;
068
069 /**
070 * Constructor. Beside of other thigs, this constructor also uses
071 * {@link StudentSectioningModel#setDistanceConflict(DistanceConflict)} to
072 * set the this instance to the model.
073 *
074 * @param solver
075 * constraint solver
076 * @param properties
077 * configuration
078 */
079 public DistanceConflict(Solver<Request, Enrollment> solver, DataProperties properties) {
080 super(solver, properties);
081 if (solver != null)
082 ((StudentSectioningModel) solver.currentSolution().getModel()).setDistanceConflict(this);
083 iDistanceMetric = new DistanceMetric(properties);
084 }
085
086 /**
087 * Alternative constructor (for online student sectioning)
088 * @param metrics distance metrics
089 * @param properties configuration
090 */
091 public DistanceConflict(DistanceMetric metrics, DataProperties properties) {
092 super(null, properties);
093 iDistanceMetric = metrics;
094 }
095
096 /**
097 * Initialize extension
098 */
099 @Override
100 public boolean init(Solver<Request, Enrollment> solver) {
101 StudentSectioningModel m = (StudentSectioningModel)solver.currentSolution().getModel();
102 iAllConflicts = computeAllConflicts();
103 for (Conflict c: iAllConflicts)
104 m.add(c);
105 return true;
106 }
107
108 @Override
109 public String toString() {
110 return "DistanceConstraint";
111 }
112
113 public DistanceMetric getDistanceMetric() {
114 return iDistanceMetric;
115 }
116
117
118 private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>();
119 protected int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) {
120 if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1);
121 if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar())
122 return 0;
123 if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null)
124 return iDistanceMetric.getMaxTravelDistanceInMinutes();
125 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId());
126 if (other2distance == null) {
127 other2distance = new HashMap<Long, Integer>();
128 iDistanceCache.put(r1.getId(), other2distance);
129 }
130 Integer distance = other2distance.get(r2.getId());
131 if (distance == null) {
132 distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY());
133 other2distance.put(r2.getId(), distance);
134 }
135 return distance;
136 }
137
138 protected int getDistanceInMinutes(Placement p1, Placement p2) {
139 if (p1.isMultiRoom()) {
140 if (p2.isMultiRoom()) {
141 int dist = 0;
142 for (RoomLocation r1 : p1.getRoomLocations()) {
143 for (RoomLocation r2 : p2.getRoomLocations()) {
144 dist = Math.max(dist, getDistanceInMinutes(r1, r2));
145 }
146 }
147 return dist;
148 } else {
149 if (p2.getRoomLocation() == null)
150 return 0;
151 int dist = 0;
152 for (RoomLocation r1 : p1.getRoomLocations()) {
153 dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation()));
154 }
155 return dist;
156 }
157 } else if (p2.isMultiRoom()) {
158 if (p1.getRoomLocation() == null)
159 return 0;
160 int dist = 0;
161 for (RoomLocation r2 : p2.getRoomLocations()) {
162 dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2));
163 }
164 return dist;
165 } else {
166 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null)
167 return 0;
168 return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation());
169 }
170 }
171
172 /**
173 * Return true if the given two sections are in distance conflict. This
174 * means that the sections are back-to-back and that they are placed in
175 * locations that are two far.
176 *
177 * @param s1
178 * a section
179 * @param s2
180 * a section
181 * @return true, if the given sections are in a distance conflict
182 */
183 public boolean inConflict(Section s1, Section s2) {
184 if (s1.getPlacement() == null || s2.getPlacement() == null)
185 return false;
186 TimeLocation t1 = s1.getTime();
187 TimeLocation t2 = s2.getTime();
188 if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
189 return false;
190 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
191 if (getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
192 if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
193 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
194 if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()))
195 return true;
196 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
197 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
198 if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()))
199 return true;
200 }
201 } else {
202 if (a1 + t1.getNrSlotsPerMeeting() == a2) {
203 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
204 if (dist > t1.getBreakTime())
205 return true;
206 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
207 int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
208 if (dist > t2.getBreakTime())
209 return true;
210 }
211 }
212 return false;
213 }
214
215 /**
216 * Return number of distance conflict of a (course) enrollment. It is the
217 * number of pairs of assignments of the enrollment that are in a distance
218 * conflict.
219 *
220 * @param e1
221 * an enrollment
222 * @return number of distance conflicts
223 */
224 public int nrConflicts(Enrollment e1) {
225 if (!e1.isCourseRequest())
226 return 0;
227 int cnt = 0;
228 for (Section s1 : e1.getSections()) {
229 for (Section s2 : e1.getSections()) {
230 if (s1.getId() < s2.getId() && inConflict(s1, s2))
231 cnt ++;
232 }
233 }
234 return cnt;
235 }
236
237 /**
238 * Return number of distance conflicts that are between two enrollments. It
239 * is the number of pairs of assignments of these enrollments that are in a
240 * distance conflict.
241 *
242 * @param e1
243 * an enrollment
244 * @param e2
245 * an enrollment
246 * @return number of distance conflict between given enrollments
247 */
248 public int nrConflicts(Enrollment e1, Enrollment e2) {
249 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent()))
250 return 0;
251 int cnt = 0;
252 for (Section s1 : e1.getSections()) {
253 for (Section s2 : e2.getSections()) {
254 if (inConflict(s1, s2))
255 cnt ++;
256 }
257 }
258 return cnt;
259 }
260
261 /**
262 * Return a set of distance conflicts ({@link Conflict} objects) of a
263 * (course) enrollment.
264 *
265 * @param e1
266 * an enrollment
267 * @return list of distance conflicts that are between assignment of the
268 * given enrollment
269 */
270 public Set<Conflict> conflicts(Enrollment e1) {
271 Set<Conflict> ret = new HashSet<Conflict>();
272 if (!e1.isCourseRequest())
273 return ret;
274 for (Section s1 : e1.getSections()) {
275 for (Section s2 : e1.getSections()) {
276 if (s1.getId() < s2.getId() && inConflict(s1, s2))
277 ret.add(new Conflict(e1.getStudent(), e1, s1, e1, s2));
278 }
279 }
280 return ret;
281 }
282
283 /**
284 * Return a set of distance conflicts ({@link Conflict} objects) between
285 * given (course) enrollments.
286 *
287 * @param e1
288 * an enrollment
289 * @param e2
290 * an enrollment
291 * @return list of distance conflicts that are between assignment of the
292 * given enrollments
293 */
294 public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) {
295 Set<Conflict> ret = new HashSet<Conflict>();
296 if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent()))
297 return ret;
298 for (Section s1 : e1.getSections()) {
299 for (Section s2 : e2.getSections()) {
300 if (inConflict(s1, s2))
301 ret.add(new Conflict(e1.getStudent(), e1, s1, e2, s2));
302 }
303 }
304 return ret;
305 }
306
307 /**
308 * Total sum of all conflict of the given enrollment and other enrollments
309 * that are assignmed to the same student.
310 */
311 public int nrAllConflicts(Enrollment enrollment) {
312 if (!enrollment.isCourseRequest())
313 return 0;
314 int cnt = nrConflicts(enrollment);
315 for (Request request : enrollment.getStudent().getRequests()) {
316 if (request.equals(enrollment.getRequest()) || request.getAssignment() == null
317 || request.equals(iOldVariable))
318 continue;
319 cnt += nrConflicts(enrollment, request.getAssignment());
320 }
321 return cnt;
322 }
323
324 /**
325 * The set of all conflicts ({@link Conflict} objects) of the given
326 * enrollment and other enrollments that are assignmed to the same student.
327 */
328 public Set<Conflict> allConflicts(Enrollment enrollment) {
329 Set<Conflict> ret = conflicts(enrollment);
330 if (!enrollment.isCourseRequest())
331 return ret;
332 for (Request request : enrollment.getStudent().getRequests()) {
333 if (request.equals(enrollment.getRequest()) || request.getAssignment() == null)
334 continue;
335 ret.addAll(conflicts(enrollment, request.getAssignment()));
336 }
337 return ret;
338 }
339
340 /**
341 * Called when a value is assigned to a variable. Internal number of
342 * distance conflicts is updated, see
343 * {@link DistanceConflict#getTotalNrConflicts()}.
344 */
345 public void assigned(long iteration, Enrollment value) {
346 StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
347 for (Conflict c: allConflicts(value)) {
348 if (iAllConflicts.add(c))
349 m.add(c);
350 }
351 if (sDebug) {
352 sLog.debug("A:" + value.variable() + " := " + value);
353 int inc = nrConflicts(value);
354 if (inc != 0) {
355 sLog.debug("-- DC+" + inc + " A: " + value.variable() + " := " + value);
356 for (Iterator<Conflict> i = allConflicts(value).iterator(); i.hasNext();)
357 sLog.debug(" -- " + i.next());
358 }
359 }
360 }
361
362 /**
363 * Called when a value is unassigned from a variable. Internal number of
364 * distance conflicts is updated, see
365 * {@link DistanceConflict#getTotalNrConflicts()}.
366 */
367 public void unassigned(long iteration, Enrollment value) {
368 if (value.variable().equals(iOldVariable))
369 return;
370 StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
371 for (Conflict c: allConflicts(value)) {
372 if (iAllConflicts.remove(c))
373 m.remove(c);
374 }
375 if (sDebug) {
376 sLog.debug("U:" + value.variable() + " := " + value);
377 int dec = nrAllConflicts(value);
378 if (dec != 0) {
379 sLog.debug("-- DC+" + dec + " U: " + value.variable() + " := " + value);
380 Set<Conflict> confs = allConflicts(value);
381 for (Iterator<Conflict> i = confs.iterator(); i.hasNext();)
382 sLog.debug(" -- " + i.next());
383 }
384 }
385 }
386
387 /** Checks the counter counting all conflicts */
388 public void checkAllConflicts() {
389 Set<Conflict> allConfs = computeAllConflicts();
390 if (iAllConflicts.size() != allConfs.size()) {
391 sLog.error("Different number of conflicts " + iAllConflicts.size() + "!=" + allConfs.size());
392 for (Iterator<Conflict> i = allConfs.iterator(); i.hasNext();) {
393 Conflict c = i.next();
394 if (!iAllConflicts.contains(c))
395 sLog.debug(" +add+ " + c);
396 }
397 for (Iterator<Conflict> i = iAllConflicts.iterator(); i.hasNext();) {
398 Conflict c = i.next();
399 if (!allConfs.contains(c))
400 sLog.debug(" -rem- " + c);
401 }
402 iAllConflicts = allConfs;
403 }
404 }
405 /** Actual number of all distance conflicts */
406 public int getTotalNrConflicts() {
407 return iAllConflicts.size();
408 }
409
410 /**
411 * Compute the actual number of all distance conflicts. Should be equal to
412 * {@link DistanceConflict#getTotalNrConflicts()}.
413 */
414 public int countTotalNrConflicts() {
415 int total = 0;
416 for (Request r1 : getModel().variables()) {
417 if (r1.getAssignment() == null || !(r1 instanceof CourseRequest))
418 continue;
419 total += nrConflicts(r1.getAssignment());
420 for (Request r2 : r1.getStudent().getRequests()) {
421 if (r2.getAssignment() == null || r1.getId() >= r2.getId() || !(r2 instanceof CourseRequest))
422 continue;
423 total += nrConflicts(r1.getAssignment(), r2.getAssignment());
424 }
425 }
426 return total;
427 }
428
429 /**
430 * Compute a set of all distance conflicts ({@link Conflict} objects).
431 */
432 public Set<Conflict> computeAllConflicts() {
433 Set<Conflict> ret = new HashSet<Conflict>();
434 for (Request r1 : getModel().variables()) {
435 if (r1.getAssignment() == null || !(r1 instanceof CourseRequest))
436 continue;
437 ret.addAll(conflicts(r1.getAssignment()));
438 for (Request r2 : r1.getStudent().getRequests()) {
439 if (r2.getAssignment() == null || r1.getId() >= r2.getId() || !(r2 instanceof CourseRequest))
440 continue;
441 ret.addAll(conflicts(r1.getAssignment(), r2.getAssignment()));
442 }
443 }
444 return ret;
445 }
446
447 /**
448 * Return a set of all distance conflicts ({@link Conflict} objects).
449 */
450 public Set<Conflict> getAllConflicts() {
451 return iAllConflicts;
452 }
453
454 /**
455 * Called before a value is assigned to a variable.
456 */
457 @Override
458 public void beforeAssigned(long iteration, Enrollment value) {
459 if (value != null) {
460 if (value.variable().getAssignment() != null) {
461 unassigned(iteration, value.variable().getAssignment());
462 iUnassignedValue = value.variable().getAssignment();
463 }
464 iOldVariable = value.variable();
465 }
466 }
467
468 /**
469 * Called after a value is assigned to a variable.
470 */
471 @Override
472 public void afterAssigned(long iteration, Enrollment value) {
473 iOldVariable = null;
474 iUnassignedValue = null;
475 if (value != null)
476 assigned(iteration, value);
477 }
478
479 /**
480 * Called after a value is unassigned from a variable.
481 */
482 @Override
483 public void afterUnassigned(long iteration, Enrollment value) {
484 if (value != null && !value.equals(iUnassignedValue))
485 unassigned(iteration, value);
486 }
487
488 /** A representation of a distance conflict */
489 public static class Conflict {
490 private Student iStudent;
491 private Section iS1, iS2;
492 private Enrollment iE1, iE2;
493 private int iHashCode;
494
495 /**
496 * Constructor
497 *
498 * @param student
499 * related student
500 * @param s1
501 * first conflicting section
502 * @param s2
503 * second conflicting section
504 */
505 public Conflict(Student student, Enrollment e1, Section s1, Enrollment e2, Section s2) {
506 iStudent = student;
507 if (s1.getId() < s2.getId()) {
508 iS1 = s1;
509 iS2 = s2;
510 iE1 = e1;
511 iE2 = e2;
512 } else {
513 iS1 = s2;
514 iS2 = s1;
515 iE1 = e2;
516 iE2 = e1;
517 }
518 iHashCode = (iStudent.getId() + ":" + iS1.getId() + ":" + iS2.getId()).hashCode();
519 }
520
521 /** Related student */
522 public Student getStudent() {
523 return iStudent;
524 }
525
526 /** First section */
527 public Section getS1() {
528 return iS1;
529 }
530
531 /** Second section */
532 public Section getS2() {
533 return iS2;
534 }
535
536 /** First request */
537 public Request getR1() {
538 return iE1.getRequest();
539 }
540
541 /** Second request */
542 public Request getR2() {
543 return iE2.getRequest();
544 }
545
546 /** First enrollment */
547 public Enrollment getE1() {
548 return iE1;
549 }
550
551 /** Second enrollment */
552 public Enrollment getE2() {
553 return iE2;
554 }
555
556 @Override
557 public int hashCode() {
558 return iHashCode;
559 }
560
561 /** The distance between conflicting sections */
562 public double getDistance(DistanceMetric dm) {
563 return Placement.getDistanceInMeters(dm, getS1().getPlacement(), getS2().getPlacement());
564 }
565
566 @Override
567 public boolean equals(Object o) {
568 if (o == null || !(o instanceof Conflict)) return false;
569 Conflict c = (Conflict) o;
570 return getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2());
571 }
572
573 @Override
574 public String toString() {
575 return getStudent() + ": " + getS1() + " -- " + getS2();
576 }
577 }
578 }