001package org.cpsolver.coursett.criteria; 002 003import java.util.Collection; 004import java.util.HashSet; 005import java.util.Set; 006 007import org.cpsolver.coursett.Constants; 008import org.cpsolver.coursett.constraint.JenrlConstraint; 009import org.cpsolver.coursett.model.Lecture; 010import org.cpsolver.coursett.model.Placement; 011import org.cpsolver.coursett.model.Student; 012import org.cpsolver.coursett.model.TimeLocation; 013import org.cpsolver.coursett.model.TimetableModel; 014import org.cpsolver.ifs.assignment.Assignment; 015import org.cpsolver.ifs.util.DataProperties; 016import org.cpsolver.ifs.util.DistanceMetric; 017 018 019/** 020 * Student conflicts. This criterion counts student conflicts between classes. A conflict 021 * occurs when two classes that are attended by the same student (or students) are overlapping 022 * in time or place back-to-back in rooms that are too far a part. The combinations of classes 023 * that share students are maintained by {@link JenrlConstraint}. 024 * <br> 025 * 026 * @version CourseTT 1.3 (University Course Timetabling)<br> 027 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 028 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 029 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 030 * <br> 031 * This library is free software; you can redistribute it and/or modify 032 * it under the terms of the GNU Lesser General Public License as 033 * published by the Free Software Foundation; either version 3 of the 034 * License, or (at your option) any later version. <br> 035 * <br> 036 * This library is distributed in the hope that it will be useful, but 037 * WITHOUT ANY WARRANTY; without even the implied warranty of 038 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 039 * Lesser General Public License for more details. <br> 040 * <br> 041 * You should have received a copy of the GNU Lesser General Public 042 * License along with this library; if not see 043 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 044 */ 045public class StudentConflict extends TimetablingCriterion { 046 protected boolean iIncludeConflicts = false; 047 048 public StudentConflict() { 049 setValueUpdateType(ValueUpdateType.BeforeUnassignedBeforeAssigned); 050 } 051 052 @Override 053 public void configure(DataProperties properties) { 054 super.configure(properties); 055 iIncludeConflicts = properties.getPropertyBoolean("StudentConflict.IncludeConflicts", false); 056 } 057 058 @Override 059 public String getPlacementSelectionWeightName() { 060 return null; 061 } 062 063 public DistanceMetric getMetrics() { 064 return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric()); 065 } 066 067 public static boolean overlaps(Placement p1, Placement p2) { 068 return p1 != null && p2 != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()) && (!p1.variable().isCommitted() || !p2.variable().isCommitted()); 069 } 070 071 protected double jointEnrollment(JenrlConstraint jenrl, Placement p1, Placement p2) { 072 return jointEnrollment(jenrl); 073 } 074 075 protected double jointEnrollment(JenrlConstraint jenrl) { 076 return jenrl.jenrl(); 077 } 078 079 public static boolean distance(DistanceMetric m, Placement p1, Placement p2) { 080 if (m == null && p1 != null) m = ((TimetableModel)p1.variable().getModel()).getDistanceMetric(); 081 if (m == null && p2 != null) m = ((TimetableModel)p2.variable().getModel()).getDistanceMetric(); 082 if (p1 == null || p2 == null || m == null) return false; 083 if (p1.variable().isCommitted() && p2.variable().isCommitted()) return false; 084 TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation(); 085 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 086 if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) { 087 if (t1.getStartSlot() + t1.getLength() <= t2.getStartSlot()) { 088 return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength()); 089 } else if (t2.getStartSlot() + t2.getLength() <= t1.getStartSlot()) { 090 return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength()); 091 } 092 } else { 093 if (t1.getStartSlot() + t1.getLength() == t2.getStartSlot()) { 094 return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime(); 095 } else if (t2.getStartSlot() + t2.getLength() == t1.getStartSlot()) { 096 return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime(); 097 } 098 } 099 return false; 100 } 101 102 public static int slots(Placement p1, Placement p2) { 103 if (p1 == null || p2 == null) return 0; 104 TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation(); 105 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0; 106 return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()); 107 } 108 109 public static boolean workday(int slotsLimit, Placement p1, Placement p2) { 110 if (slotsLimit <= 0) return false; 111 return p1 != null && p2 != null && slots(p1, p2) > slotsLimit; 112 } 113 114 public static boolean ignore(Lecture l1, Lecture l2) { 115 return l1 != null && l2 != null && l1.isToIgnoreStudentConflictsWith(l2); 116 } 117 118 public static boolean committed(Lecture l1, Lecture l2) { 119 return l1 != null && l2 != null && (l1.isCommitted() || l2.isCommitted()) && (!l1.isCommitted() || !l2.isCommitted()); 120 } 121 122 public static boolean uncommitted(Lecture l1, Lecture l2) { 123 return l1 != null && l2 != null && !l1.isCommitted() && !l2.isCommitted(); 124 } 125 126 public static boolean applicable(Lecture l1, Lecture l2) { 127 return l1 != null && l2 != null && (!l1.isCommitted() || !l2.isCommitted()); 128 } 129 130 public static boolean hard(Lecture l1, Lecture l2) { 131 return l1 != null && l2 != null && l1.isSingleSection() && l2.isSingleSection() && (!l1.isCommitted() || !l2.isCommitted()); 132 } 133 134 public boolean isApplicable(Lecture l1, Lecture l2) { 135 return l1 != null && l2 != null && !ignore(l1, l2) && uncommitted(l1, l2); // exclude committed and outside student conflicts 136 } 137 138 public boolean isApplicable(Student student, Lecture l1, Lecture l2) { 139 return isApplicable(l1, l2); 140 } 141 142 public boolean inConflict(Placement p1, Placement p2) { 143 return overlaps(p1, p2) || distance(getMetrics(), p1, p2); 144 } 145 146 @Override 147 public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 148 double ret = 0.0; 149 for (JenrlConstraint jenrl: value.variable().jenrlConstraints()) { 150 Lecture other = jenrl.another(value.variable()); 151 if (!isApplicable(value.variable(), other)) continue; 152 Placement another = assignment.getValue(other); 153 if (another == null) continue; 154 if (conflicts != null && conflicts.contains(another)) continue; 155 if (inConflict(value, another)) 156 ret += jointEnrollment(jenrl, value, another); 157 } 158 if (iIncludeConflicts && conflicts != null) 159 for (Placement conflict: conflicts) { 160 for (JenrlConstraint jenrl: conflict.variable().jenrlConstraints()) { 161 Lecture other = jenrl.another(conflict.variable()); 162 if (!isApplicable(conflict.variable(), other)) continue; 163 Placement another = assignment.getValue(other); 164 if (another == null || another.variable().equals(value.variable())) continue; 165 if (conflicts != null && conflicts.contains(another)) continue; 166 if (inConflict(conflict, another)) 167 ret -= jointEnrollment(jenrl, conflict, another); 168 } 169 } 170 return ret; 171 } 172 173 @Override 174 public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 175 double ret = 0.0; 176 Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>(); 177 for (Lecture lect: variables) { 178 Placement plac = assignment.getValue(lect); 179 if (plac == null) continue; 180 for (JenrlConstraint jenrl: lect.jenrlConstraints()) { 181 if (!constraints.add(jenrl)) continue; 182 Lecture other = jenrl.another(lect); 183 if (!other.isCommitted() && !variables.contains(other)) continue; 184 if (!isApplicable(lect, other)) continue; 185 if (inConflict(plac, assignment.getValue(other))) 186 ret += jointEnrollment(jenrl, plac, assignment.getValue(other)); 187 } 188 } 189 return ret; 190 } 191 192 @Override 193 public double[] getBounds(Assignment<Lecture, Placement> assignment) { 194 double[] bounds = { 0.0, 0.0 }; 195 for (JenrlConstraint jenrl: ((TimetableModel)getModel()).getJenrlConstraints()) 196 if (isApplicable(jenrl.first(), jenrl.second())) 197 bounds[0] += jointEnrollment(jenrl); 198 return bounds; 199 } 200 201 @Override 202 public double[] getBounds(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 203 double[] bounds = { 0.0, 0.0 }; 204 Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>(); 205 for (Lecture lect: variables) { 206 if (assignment.getValue(lect) == null) continue; 207 for (JenrlConstraint jenrl: lect.jenrlConstraints()) { 208 if (isApplicable(jenrl.first(), jenrl.second()) && constraints.add(jenrl) && (jenrl.another(lect).isCommitted() || variables.contains(jenrl.another(lect)))) 209 bounds[0] += jointEnrollment(jenrl); 210 } 211 } 212 return bounds; 213 } 214 215 public void incJenrl(Assignment<Lecture, Placement> assignment, JenrlConstraint jenrl, double studentWeight, Double conflictPriority, Student student) { 216 if (isApplicable(jenrl.first(), jenrl.second()) && inConflict(assignment.getValue(jenrl.first()), assignment.getValue(jenrl.second()))) 217 super.inc(assignment, studentWeight); 218 } 219 220 @Override 221 public void bestRestored(Assignment<Lecture, Placement> assignment) { 222 super.bestRestored(assignment); 223 getContext(assignment).setTotal(getValue(assignment, getModel().variables())); 224 } 225}