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