1/*
2 * Scheduler.h
3 * @brief an example how inference can be used for scheduling qualifiers
4 * @date Mar 26, 2011
5 * @author Frank Dellaert
6 */
7
8#include <gtsam/base/debug.h>
9#include <gtsam/base/timing.h>
10#include <gtsam/discrete/DiscreteFactorGraph.h>
11#include <gtsam_unstable/discrete/Scheduler.h>
12
13#include <boost/tokenizer.hpp>
14#include <cmath>
15#include <fstream>
16#include <iomanip>
17#include <cassert>
18
19namespace gtsam {
20
21using namespace std;
22
23Scheduler::Scheduler(size_t maxNrStudents, const string& filename)
24 : maxNrStudents_(maxNrStudents) {
25 typedef boost::tokenizer<boost::escaped_list_separator<char> > Tokenizer;
26
27 // open file
28 ifstream is(filename.c_str());
29 if (!is) {
30 cerr << "Scheduler: could not open file " << filename << endl;
31 throw runtime_error("Scheduler: could not open file " + filename);
32 }
33
34 string line; // buffer
35
36 // process first line with faculty
37 if (getline(in&: is, str&: line, delim: '\r')) {
38 Tokenizer tok(line);
39 Tokenizer::iterator it = tok.begin();
40 for (++it; it != tok.end(); ++it) addFaculty(facultyName: *it);
41 }
42
43 // for all remaining lines
44 size_t count = 0;
45 while (getline(in&: is, str&: line, delim: '\r')) {
46 if (count++ > 100) throw runtime_error("reached 100 lines, exiting");
47 Tokenizer tok(line);
48 Tokenizer::iterator it = tok.begin();
49 addSlot(slotName: *it++); // add slot
50 // add availability
51 for (; it != tok.end(); ++it) available_ += (it->empty()) ? "0 " : "1 ";
52 available_ += '\n';
53 }
54} // constructor
55
56/** addStudent has to be called after adding slots and faculty */
57void Scheduler::addStudent(const string& studentName, const string& area1,
58 const string& area2, const string& area3,
59 const string& advisor) {
60 assert(nrStudents() < maxNrStudents_);
61 assert(facultyInArea_.count(area1));
62 assert(facultyInArea_.count(area2));
63 assert(facultyInArea_.count(area3));
64 size_t advisorIndex = facultyIndex_[advisor];
65 Student student(nrFaculty(), advisorIndex);
66 student.name_ = studentName;
67 // We fix the ordering by assigning a higher index to the student
68 // and numbering the areas lower
69 Key j = 3 * maxNrStudents_ + nrStudents();
70 student.key_ = DiscreteKey(j, nrTimeSlots());
71 Key base = 3 * nrStudents();
72 student.keys_[0] = DiscreteKey(base + 0, nrFaculty());
73 student.keys_[1] = DiscreteKey(base + 1, nrFaculty());
74 student.keys_[2] = DiscreteKey(base + 2, nrFaculty());
75 student.areaName_[0] = area1;
76 student.areaName_[1] = area2;
77 student.areaName_[2] = area3;
78 students_.push_back(x: student);
79}
80
81/** get key for student and area, 0 is time slot itself */
82const DiscreteKey& Scheduler::key(size_t s,
83 std::optional<size_t> area) const {
84 return area ? students_[s].keys_[*area] : students_[s].key_;
85}
86
87const string& Scheduler::studentName(size_t i) const {
88 assert(i < nrStudents());
89 return students_[i].name_;
90}
91
92const DiscreteKey& Scheduler::studentKey(size_t i) const {
93 assert(i < nrStudents());
94 return students_[i].key_;
95}
96
97const string& Scheduler::studentArea(size_t i, size_t area) const {
98 assert(i < nrStudents());
99 return students_[i].areaName_[area];
100}
101
102/** Add student-specific constraints to the graph */
103void Scheduler::addStudentSpecificConstraints(size_t i,
104 std::optional<size_t> slot) {
105 bool debug = ISDEBUG("Scheduler::buildGraph");
106
107 assert(i < nrStudents());
108 const Student& s = students_[i];
109
110 if (!slot && !slotsAvailable_.empty()) {
111 if (debug) cout << "Adding availability of slots" << endl;
112 assert(slotsAvailable_.size() == s.key_.second);
113 CSP::add(args: s.key_, args&: slotsAvailable_);
114 }
115
116 // For all areas
117 for (size_t area = 0; area < 3; area++) {
118 DiscreteKey areaKey = s.keys_[area];
119 const string& areaName = s.areaName_[area];
120
121 if (debug) cout << "Area constraints " << areaName << endl;
122 assert(facultyInArea_[areaName].size() == areaKey.second);
123 CSP::add(args&: areaKey, args&: facultyInArea_[areaName]);
124
125 if (debug) cout << "Advisor constraint " << areaName << endl;
126 assert(s.advisor_.size() == areaKey.second);
127 CSP::add(args&: areaKey, args: s.advisor_);
128
129 if (debug) cout << "Availability of faculty " << areaName << endl;
130 if (slot) {
131 // get all constraints then specialize to slot
132 size_t dummyIndex = maxNrStudents_ * 3 + maxNrStudents_;
133 DiscreteKey dummy(dummyIndex, nrTimeSlots());
134 AlgebraicDecisionTree<Key> p(dummy & areaKey,
135 available_); // available_ is Doodle string
136 auto q = p.choose(label: dummyIndex, index: *slot);
137 CSP::add(args&: areaKey, args&: q);
138 } else {
139 DiscreteKeys keys {s.key_, areaKey};
140 CSP::add(args&: keys, args&: available_); // available_ is Doodle string
141 }
142 }
143
144 // add mutex
145 if (debug) cout << "Mutex for faculty" << endl;
146 addAllDiff(dkeys: s.keys_[0] & s.keys_[1] & s.keys_[2]);
147}
148
149/** Main routine that builds factor graph */
150void Scheduler::buildGraph(size_t mutexBound) {
151 bool debug = ISDEBUG("Scheduler::buildGraph");
152
153 if (debug) cout << "Adding student-specific constraints" << endl;
154 for (size_t i = 0; i < nrStudents(); i++) addStudentSpecificConstraints(i);
155
156 // special constraint for MN
157 if (studentName(i: 0) == "Michael N")
158 CSP::add(args: studentKey(i: 0), args: "0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1");
159
160 if (!mutexBound) {
161 DiscreteKeys dkeys;
162 for (const Student& s : students_) dkeys.push_back(x: s.key_);
163 addAllDiff(dkeys);
164 } else {
165 if (debug) cout << "Mutex for Students" << endl;
166 for (size_t i1 = 0; i1 < nrStudents(); i1++) {
167 // if mutexBound=1, we only mutex with next student
168 size_t bound = min(a: (i1 + 1 + mutexBound), b: nrStudents());
169 for (size_t i2 = i1 + 1; i2 < bound; i2++) {
170 addAllDiff(key1: studentKey(i: i1), key2: studentKey(i: i2));
171 }
172 }
173 }
174} // buildGraph
175
176/** print */
177void Scheduler::print(const string& s, const KeyFormatter& formatter) const {
178 cout << s << " Faculty:" << endl;
179 for (const string& name : facultyName_) cout << name << '\n';
180 cout << endl;
181
182 cout << s << " Slots:\n";
183 size_t i = 0;
184 for (const string& name : slotName_) cout << i++ << " " << name << endl;
185 cout << endl;
186
187 cout << "Availability:\n" << available_ << '\n';
188
189 cout << s << " Area constraints:\n";
190 for (const FacultyInArea::value_type& it : facultyInArea_) {
191 cout << setw(12) << it.first << ": ";
192 for (double v : it.second) cout << v << " ";
193 cout << '\n';
194 }
195 cout << endl;
196
197 cout << s << " Students:\n";
198 for (const Student& student : students_) student.print();
199 cout << endl;
200
201 CSP::print(s: s + " Factor graph");
202 cout << endl;
203} // print
204
205/** Print readable form of assignment */
206void Scheduler::printAssignment(const DiscreteValues& assignment) const {
207 // Not intended to be general! Assumes very particular ordering !
208 cout << endl;
209 for (size_t s = 0; s < nrStudents(); s++) {
210 Key j = 3 * maxNrStudents_ + s;
211 size_t slot = assignment.at(k: j);
212 cout << studentName(i: s) << " slot: " << slotName_[slot] << endl;
213 Key base = 3 * s;
214 for (size_t area = 0; area < 3; area++) {
215 size_t faculty = assignment.at(k: base + area);
216 cout << setw(12) << studentArea(i: s, area) << ": " << facultyName_[faculty]
217 << endl;
218 }
219 cout << endl;
220 }
221}
222
223/** Special print for single-student case */
224void Scheduler::printSpecial(const DiscreteValues& assignment) const {
225 DiscreteValues::const_iterator it = assignment.begin();
226 for (size_t area = 0; area < 3; area++, it++) {
227 size_t f = it->second;
228 cout << setw(12) << studentArea(i: 0, area) << ": " << facultyName_[f] << endl;
229 }
230 cout << endl;
231}
232
233/** Accumulate faculty stats */
234void Scheduler::accumulateStats(const DiscreteValues& assignment,
235 vector<size_t>& stats) const {
236 for (size_t s = 0; s < nrStudents(); s++) {
237 Key base = 3 * s;
238 for (size_t area = 0; area < 3; area++) {
239 size_t f = assignment.at(k: base + area);
240 assert(f < stats.size());
241 stats[f]++;
242 } // area
243 } // s
244}
245
246/** Eliminate, return a Bayes net */
247DiscreteBayesNet::shared_ptr Scheduler::eliminate() const {
248 gttic(my_eliminate);
249 // TODO: fix this!!
250 size_t maxKey = keys().size();
251 Ordering defaultKeyOrdering;
252 for (size_t i = 0; i < maxKey; ++i) defaultKeyOrdering.push_back(x: i);
253 DiscreteBayesNet::shared_ptr chordal =
254 this->eliminateSequential(ordering: defaultKeyOrdering);
255 gttoc(my_eliminate);
256 return chordal;
257}
258
259/** find the assignment of students to slots with most possible committees */
260DiscreteValues Scheduler::bestSchedule() const {
261 DiscreteValues best;
262 throw runtime_error("bestSchedule not implemented");
263 return best;
264}
265
266/** find the corresponding most desirable committee assignment */
267DiscreteValues Scheduler::bestAssignment(const DiscreteValues& bestSchedule) const {
268 DiscreteValues best;
269 throw runtime_error("bestAssignment not implemented");
270 return best;
271}
272
273} // namespace gtsam
274