001package org.cpsolver.studentsct.constraint; 002 003import java.util.ArrayList; 004import java.util.Iterator; 005import java.util.List; 006import java.util.Set; 007 008import org.cpsolver.ifs.assignment.Assignment; 009import org.cpsolver.ifs.model.GlobalConstraint; 010import org.cpsolver.studentsct.constraint.LinkedSections.EnrollmentAssignment; 011import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection; 012import org.cpsolver.studentsct.model.Course; 013import org.cpsolver.studentsct.model.Enrollment; 014import org.cpsolver.studentsct.model.Request; 015import org.cpsolver.studentsct.model.Student; 016 017/** 018 * Global constraint for dependent courses. If a student requests both a course and its 019 * parent (identified by {@link Course#getParent()}), the student cannot get the dependent 020 * course without also having the parent course assigned. 021 * 022 * @author Tomáš Müller 023 * @version StudentSct 1.4 (Student Sectioning)<br> 024 * Copyright (C) 2007 - 2025 Tomáš Müller<br> 025 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 026 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 027 * <br> 028 * This library is free software; you can redistribute it and/or modify 029 * it under the terms of the GNU Lesser General Public License as 030 * published by the Free Software Foundation; either version 3 of the 031 * License, or (at your option) any later version. <br> 032 * <br> 033 * This library is distributed in the hope that it will be useful, but 034 * WITHOUT ANY WARRANTY; without even the implied warranty of 035 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 036 * Lesser General Public License for more details. <br> 037 * <br> 038 * You should have received a copy of the GNU Lesser General Public 039 * License along with this library; if not see 040 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 041 */ 042 043public class DependentCourses extends GlobalConstraint<Request, Enrollment> { 044 045 @Override 046 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment value, Set<Enrollment> conflicts) { 047 if (value != null && value.getCourse() != null) { 048 // check if assigned course has a parent 049 Course parent = value.getCourse().getParent(); 050 if (parent != null && !value.getAssignments().isEmpty()) { 051 // has parent -> check if student has the parent course assigned 052 for (Request request: value.getStudent().getRequests()) { 053 if (request.hasCourse(parent)) { // this request has the parent course 054 if (request.equals(value.variable())) { 055 // same request >> problem 056 conflicts.add(value); 057 break; 058 } 059 Enrollment enrollment = assignment.getValue(request); 060 // not assigned or assigned to a different offering -> conflict 061 if (enrollment == null || enrollment.getCourse() == null || !parent.equals(enrollment.getCourse())) { 062 conflicts.add(value); 063 break; 064 } 065 } 066 } 067 } 068 // check the previous enrollment of the given request 069 Enrollment original = assignment.getValue(value.variable()); 070 if (original != null && original.getCourse() != null && original.getCourse().hasChildren() && !original.getCourse().equals(value.getCourse())) { 071 // moving to another course, check that the original offering is not a parent to an assigned course 072 for (Request r: original.getStudent().getRequests()) { 073 Enrollment e = assignment.getValue(r); 074 Course p = (e == null || e.getCourse() == null ? null : e.getCourse().getParent()); 075 if (p != null && original.getCourse().equals(p)) 076 conflicts.add(e); 077 } 078 } 079 } 080 081 if (!conflicts.contains(value)) { 082 List<Enrollment> additionalConflicts = null; 083 // check the conflicts 084 for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext(); ) { 085 Enrollment conf = i.next(); 086 if (conf != null && conf.getCourse() != null && conf.getCourse().hasChildren()) { 087 for (Request r: conf.getStudent().getRequests()) { 088 Enrollment e = assignment.getValue(r); 089 if (r.equals(value.getRequest())) e = value; 090 Course p = (e == null || e.getCourse() == null ? null : e.getCourse().getParent()); 091 if (p != null && conf.getCourse().equals(p)) { 092 if (additionalConflicts == null) additionalConflicts = new ArrayList<Enrollment>(); 093 additionalConflicts.add(e); 094 } 095 } 096 } 097 } 098 if (additionalConflicts != null) conflicts.addAll(additionalConflicts); 099 } 100 } 101 102 /** 103 * Conflict check. There is a conflict when a student has an assigned course that has 104 * a parent course, the student also has the parent course requested, 105 * but does not have the parent course assigned. 106 */ 107 @Override 108 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment value) { 109 if (value == null || value.getCourse() == null) return false; 110 111 // check if assigned course has a parent 112 Course parent = value.getCourse().getParent(); 113 if (parent != null) { 114 // has parent -> check if student has the parent course assigned 115 for (Request request: value.getStudent().getRequests()) { 116 if (request.hasCourse(parent)) { // this request has the parent course 117 if (request.equals(value.variable())) return true; // same request >> problem 118 Enrollment enrollment = assignment.getValue(request); 119 // not assigned or assigned to a different offering -> conflict 120 if (enrollment == null || enrollment.getCourse() == null || !parent.equals(enrollment.getCourse())) { 121 return true; 122 } 123 } 124 } 125 } 126 127 // check the previous enrollment of the given request 128 Enrollment original = assignment.getValue(value.variable()); 129 if (original != null && original.getCourse() != null && original.getCourse().hasChildren() && !original.getCourse().equals(value.getCourse())) { 130 // moving to another course, check that the original offering is not a parent to an assigned course 131 for (Request r: original.getStudent().getRequests()) { 132 Enrollment e = assignment.getValue(r); 133 Course p = (e == null || e.getCourse() == null ? null : e.getCourse().getParent()); 134 if (p != null && original.getCourse().equals(p)) 135 return true; 136 } 137 } 138 139 return false; 140 } 141 142 /** 143 * A special check for the branch-and-bound routine (such as {@link BranchBoundSelection}) which 144 * constructs a full schedule for a student. 145 * There is a conflict when there is a dependent course assigned within the already constructed 146 * schedule (up to the given index) and the already constructed schedule also contains the parent 147 * course but it is not assigned. 148 * @param student a student 149 * @param assignment current assigned up to the given index 150 * @param index index of the variable that is being assigned 151 * @return true if there is no conflict 152 */ 153 public boolean isPartialScheduleInConflict(Student student, EnrollmentAssignment assignment, int index) { 154 /* 155 // check all requests up to index 156 for (int i = 0; i <= index; i++) { 157 Request request = student.getRequests().get(i); 158 Enrollment enrollment = assignment.getEnrollment(request, i); 159 if (enrollment == null || enrollment.getCourse() == null) continue; 160 Course parent = enrollment.getCourse().getParent(); 161 if (parent != null) { 162 // has assigned a dependent offering >> check if there is a parent 163 for (int j = 0; j <= index; j++) { 164 Request other = student.getRequests().get(j); 165 if (other.hasCourse(parent)) { 166 Enrollment otherEnrollment = assignment.getEnrollment(other, j); 167 // parent request is not assigned or assigned to a different offering > conflict 168 if (otherEnrollment == null || otherEnrollment.getCourse() == null || 169 !parent.equals(otherEnrollment.getCourse())) return true; 170 } 171 } 172 } 173 } 174 */ 175 Request request = student.getRequests().get(index); 176 Enrollment enrollment = assignment.getEnrollment(request, index); 177 Course parent = (enrollment == null || enrollment.getCourse() == null ? null : enrollment.getCourse().getParent()); 178 if (parent != null) { 179 // current-level enrollment has a parent > check if the parent is already assigned 180 for (int j = 0; j <= index; j++) { 181 Request other = student.getRequests().get(j); 182 if (other.hasCourse(parent)) { 183 Enrollment otherEnrollment = assignment.getEnrollment(request, j); 184 // parent request is not assigned or assigned to a different offering > conflict 185 if (otherEnrollment == null || otherEnrollment.getCourse() == null || 186 !parent.equals(otherEnrollment.getCourse())) { 187 return true; 188 } 189 } 190 } 191 } 192 if (request.hasChildren()) { 193 for (int j = 0; j <= index; j++) { 194 Request other = student.getRequests().get(j); 195 Enrollment otherEnrollment = assignment.getEnrollment(other, j); 196 Course otherParent = (otherEnrollment == null || otherEnrollment.getCourse() == null ? null : otherEnrollment.getCourse().getParent()); 197 // other is assigned and has a parent that is included in the current-level request > must be assigned 198 if (otherParent != null && request.hasCourse(otherParent)) { 199 if (enrollment == null || !otherParent.equals(enrollment.getCourse())) { 200 return true; 201 } 202 } 203 } 204 } 205 206 return false; 207 } 208 209 /** 210 * A special check for the branch-and-bound routine (such as {@link BranchBoundSelection}) which 211 * constructs a full schedule for a student. 212 * The parent request cannot be left unassigned if it contains a parent course for any of the already 213 * assigned dependent course. 214 * @param student a student 215 * @param assignment current assigned up to the given index 216 * @param parentRequest parent request (that is being checked if it can be left unassigned) 217 * @return true if the parent request can be left unassigned (it is not a parent course for an assigned dependent course) 218 */ 219 public boolean canLeaveUnassigned(Student student, EnrollmentAssignment assignment, Request parentRequest) { 220 if (!parentRequest.hasChildren()) return false; 221 // request has children > check if assigned 222 for (int i = 0; i < student.getRequests().size(); i++) { 223 Request request = student.getRequests().get(i); 224 if (parentRequest.equals(request)) break; 225 Enrollment enrollment = assignment.getEnrollment(request, i); 226 Course parent = (enrollment == null || enrollment.getCourse() == null ? null : enrollment.getCourse().getParent()); 227 // assigned to a dependent course >> check if the given request has the parent 228 if (parent != null && parentRequest.hasCourse(parent)) { 229 return false; 230 } 231 } 232 return true; 233 } 234}