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