001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.HashSet; 006import java.util.List; 007import java.util.Map; 008import java.util.Set; 009 010import org.cpsolver.coursett.model.Lecture; 011import org.cpsolver.coursett.model.Placement; 012import org.cpsolver.coursett.model.Student; 013import org.cpsolver.coursett.model.TimetableModel; 014import org.cpsolver.ifs.assignment.Assignment; 015import org.cpsolver.ifs.model.Constraint; 016import org.cpsolver.ifs.model.GlobalConstraint; 017import org.cpsolver.ifs.model.Model; 018import org.cpsolver.ifs.model.ModelListener; 019import org.cpsolver.ifs.solver.Solver; 020import org.cpsolver.ifs.util.DataProperties; 021import org.cpsolver.ifs.util.DistanceMetric; 022 023/** 024 * An experimental global constraint that does not allow any two classes that can be attended 025 * by the same student to have a conflict. The constraint checks any two classes of different 026 * offerings that share at least one student and that the student is allowed to take (not restricted 027 * by reservations). Class pairs included in the Ignore Student Conflicts constraints are ignored. 028 * Some classes may be excluded by using ExtendedStudentConflicts.IgnoreClasses parameter which may 029 * contain a regular expression matching class name(s). 030 * <br> 031 * Pairs of classes of the same offering are checked, too. In this case, the course structure must 032 * allow the two classes to be attended together (e.g., they are from the same configuration), and at 033 * least one student in the offering is allowed to take both classes. This feature can be disabled by 034 * setting ExtendedStudentConflicts.CheckSameCourse to false. 035 * <br> 036 * @version CourseTT 1.3 (University Course Timetabling)<br> 037 * Copyright (C) 2013 - 2024 Tomáš Müller<br> 038 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 039 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 040 * <br> 041 * This library is free software; you can redistribute it and/or modify 042 * it under the terms of the GNU Lesser General Public License as 043 * published by the Free Software Foundation; either version 3 of the 044 * License, or (at your option) any later version. <br> 045 * <br> 046 * This library is distributed in the hope that it will be useful, but 047 * WITHOUT ANY WARRANTY; without even the implied warranty of 048 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 049 * Lesser General Public License for more details. <br> 050 * <br> 051 * You should have received a copy of the GNU Lesser General Public 052 * License along with this library; if not see 053 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 054 */ 055public class ExtendedStudentConflicts extends GlobalConstraint<Lecture, Placement> implements ModelListener<Lecture, Placement>{ 056 private String iIgnoreClasses = null; 057 private Map<Long, Map<Long, List<Student>>> iCommonStudents = null; 058 private Set<Long> iIgnoreClassIds = null; 059 private Map<Long, Map<Long, Boolean>> iClassCache = new HashMap<Long, Map<Long, Boolean>>(); 060 private boolean iCheckSameCourse = true; 061 062 @Override 063 public void setModel(Model<Lecture, Placement> model) { 064 super.setModel(model); 065 if (model != null && model instanceof TimetableModel) { 066 DataProperties config = ((TimetableModel)model).getProperties(); 067 iIgnoreClasses = config.getProperty("ExtendedStudentConflicts.IgnoreClasses"); 068 iCheckSameCourse = config.getPropertyBoolean("ExtendedStudentConflicts.CheckSameCourse", true); 069 } 070 } 071 072 protected void clearCache() { 073 iCommonStudents = null; 074 iIgnoreClassIds = null; 075 iClassCache.clear(); 076 } 077 078 private DistanceMetric getDistanceMetric() { 079 return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric()); 080 } 081 082 protected List<Student> getCommonStudents(Long offeringId1, Long offeringId2) { 083 if (iCommonStudents == null) { 084 iCommonStudents = new HashMap<Long, Map<Long, List<Student>>>(); 085 for (Lecture lecture: getModel().variables()) { 086 if (lecture.isCommitted() || lecture.getConfiguration() == null) continue; 087 Map<Long, List<Student>> commonStudents = iCommonStudents.get(lecture.getConfiguration().getOfferingId()); 088 if (commonStudents != null) continue; 089 commonStudents = new HashMap<Long, List<Student>>(); 090 iCommonStudents.put(lecture.getConfiguration().getOfferingId(), commonStudents); 091 for (Lecture other: getModel().variables()) { 092 if (other.isCommitted() || other.getConfiguration() == null) continue; 093 // if (other.getConfiguration().getOfferingId().equals(lecture.getConfiguration().getOfferingId())) continue; 094 if (commonStudents.containsKey(other.getConfiguration().getOfferingId())) continue; 095 List<Student> students = new ArrayList<Student>(); 096 for (Student student: ((TimetableModel)getModel()).getAllStudents()) { 097 if (student.getOfferings().contains(lecture.getConfiguration().getOfferingId()) && student.getOfferings().contains(other.getConfiguration().getOfferingId())) 098 students.add(student); 099 } 100 commonStudents.put(other.getConfiguration().getOfferingId(), students); 101 } 102 } 103 } 104 Map<Long, List<Student>> offeringIds = iCommonStudents.get(offeringId1); 105 return (offeringIds == null ? null : offeringIds.get(offeringId2)); 106 } 107 108 protected boolean isIgnoreClass(Lecture lecture) { 109 if (iIgnoreClassIds == null) { 110 iIgnoreClassIds = new HashSet<Long>(); 111 if (iIgnoreClasses != null && !iIgnoreClasses.isEmpty()) 112 for (Lecture l: getModel().variables()) { 113 if (l.getName().matches(iIgnoreClasses)) iIgnoreClassIds.add(l.getClassId()); 114 } 115 } 116 return iIgnoreClassIds.contains(lecture.getClassId()); 117 118 } 119 120 private Boolean getCachedPair(Lecture l1, Lecture l2) { 121 if (l1.getClassId() < l2.getClassId()) { 122 Map<Long, Boolean> cache = iClassCache.get(l1.getClassId()); 123 return (cache == null ? null : cache.get(l2.getClassId())); 124 } else { 125 Map<Long, Boolean> cache = iClassCache.get(l2.getClassId()); 126 return (cache == null ? null : cache.get(l1.getClassId())); 127 } 128 } 129 130 private void setCachedPair(Lecture l1, Lecture l2, boolean value) { 131 if (l1.getClassId() < l2.getClassId()) { 132 Map<Long, Boolean> cache = iClassCache.get(l1.getClassId()); 133 if (cache == null) { 134 cache = new HashMap<Long, Boolean>(); 135 iClassCache.put(l1.getClassId(), cache); 136 } 137 cache.put(l2.getClassId(), value); 138 } else { 139 Map<Long, Boolean> cache = iClassCache.get(l2.getClassId()); 140 if (cache == null) { 141 cache = new HashMap<Long, Boolean>(); 142 iClassCache.put(l2.getClassId(), cache); 143 } 144 cache.put(l1.getClassId(), value); 145 } 146 } 147 148 private boolean checkSameCourseCanTakeTogether(Lecture l1, Lecture l2) { 149 // check if the feature is disabled 150 if (!iCheckSameCourse) return false; 151 // same subpart -> cannot take together 152 if (l1.getSchedulingSubpartId().equals(l2.getSchedulingSubpartId())) return false; 153 // different config -> cannot take together 154 if (!l1.getConfiguration().equals(l2.getConfiguration())) return false; 155 // subpart id > class id (classes that are given by class l1 and its parents) 156 Map<Long, Long> mustTake = new HashMap<Long, Long>(); 157 for (Lecture l = l1; l != null; l = l.getParent()) { 158 mustTake.put(l.getSchedulingSubpartId(), l.getClassId()); 159 } 160 // also include top-level subparts of the same configuration that have only one class 161 for (Map.Entry<Long, Set<Lecture>> e: l1.getConfiguration().getTopLectures().entrySet()) { 162 if (e.getValue().size() == 1) { 163 Lecture l = e.getValue().iterator().next(); 164 mustTake.put(l.getSchedulingSubpartId(), l.getClassId()); 165 } 166 } 167 // check l2 and its parents, if any of them does not follow mustTake -> cannot take together 168 for (Lecture l = l2; l != null; l = l.getParent()) { 169 Long id = mustTake.get(l.getSchedulingSubpartId()); 170 if (id != null && !l.getClassId().equals(id)) return false; 171 } 172 // no issue found -> can take together 173 return true; 174 } 175 176 protected boolean checkStudentForStudentConflicts(Lecture l1, Lecture l2) { 177 // are student conflicts between the two classes to be ignored ? 178 if (l1.isToIgnoreStudentConflictsWith(l2)) return false; 179 // check the cache 180 Boolean cache = getCachedPair(l1, l2); 181 if (cache != null) return cache.booleanValue(); 182 // classes of the same offering that cannot be taken together 183 if (l1.getConfiguration().getOfferingId().equals(l2.getConfiguration().getOfferingId()) && !checkSameCourseCanTakeTogether(l1, l2)) { 184 setCachedPair(l1, l2, false); 185 return false; 186 } 187 // ignore matching class pairs 188 if (isIgnoreClass(l1) && isIgnoreClass(l2)) { 189 setCachedPair(l1, l2, false); 190 return false; 191 } 192 // check offerings 193 List<Student> commonStudents = getCommonStudents(l1.getConfiguration().getOfferingId(), l2.getConfiguration().getOfferingId()); 194 // less then two students in common > do not check for conflicts 195 if (commonStudents == null || commonStudents.size() <= 1) { 196 setCachedPair(l1, l2, false); 197 return false; 198 } 199 // check if there is a student that can attend l1 and l2 together 200 for (Student student: commonStudents) 201 if (student.canEnroll(l1) && student.canEnroll(l2)) { 202 setCachedPair(l1, l2, true); 203 return true; 204 } 205 // no common students that can attend both classes 206 setCachedPair(l1, l2, false); 207 return false; 208 } 209 210 @Override 211 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) { 212 Lecture lecture = placement.variable(); 213 for (Lecture other: getModel().assignedVariables(assignment)) { 214 Placement otherPlacement = assignment.getValue(other); 215 if (checkStudentForStudentConflicts(lecture, other) && JenrlConstraint.isInConflict(placement, otherPlacement, getDistanceMetric(), 0)) 216 conflicts.add(otherPlacement); 217 } 218 } 219 220 @Override 221 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) { 222 Lecture lecture = placement.variable(); 223 for (Lecture other: getModel().assignedVariables(assignment)) { 224 Placement otherPlacement = assignment.getValue(other); 225 if (checkStudentForStudentConflicts(lecture, other) && JenrlConstraint.isInConflict(placement, otherPlacement, getDistanceMetric(), 0)) 226 return true; 227 } 228 return false; 229 } 230 231 @Override 232 public boolean isConsistent(Placement p1, Placement p2) { 233 return p1 != null && p2 != null && 234 checkStudentForStudentConflicts(p1.variable(), p2.variable()) && 235 JenrlConstraint.isInConflict(p1, p2, getDistanceMetric(), 0); 236 } 237 238 @Override 239 public String getName() { 240 return "Extended Student Conflicts"; 241 } 242 243 @Override 244 public String toString() { 245 return "Extended Student Conflicts"; 246 } 247 248 @Override 249 public void variableAdded(Lecture variable) { 250 clearCache(); 251 } 252 253 @Override 254 public void variableRemoved(Lecture variable) { 255 clearCache(); 256 } 257 258 @Override 259 public void constraintAdded(Constraint<Lecture, Placement> constraint) {} 260 261 @Override 262 public void constraintRemoved(Constraint<Lecture, Placement> constraint) {} 263 264 @Override 265 public void beforeAssigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {} 266 267 @Override 268 public void beforeUnassigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {} 269 270 @Override 271 public void afterAssigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {} 272 273 @Override 274 public void afterUnassigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {} 275 276 @Override 277 public boolean init(Solver<Lecture, Placement> solver) { 278 clearCache(); 279 return true; 280 } 281}