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#pragma once
9
10#include <gtsam_unstable/discrete/CSP.h>
11#include <gtsam/discrete/DiscreteBayesNet.h>
12
13namespace gtsam {
14
15/**
16 * Scheduler class
17 * Creates one variable for each student, and three variables for each
18 * of the student's areas, for a total of 4*nrStudents variables.
19 * The "student" variable will determine when the student takes the qual.
20 * The "area" variables determine which faculty are on his/her committee.
21 */
22class GTSAM_UNSTABLE_EXPORT Scheduler : public CSP {
23 private:
24 /** Internal data structure for students */
25 struct Student {
26 std::string name_;
27 DiscreteKey key_; // key for student
28 std::vector<DiscreteKey> keys_; // key for areas
29 std::vector<std::string> areaName_;
30 std::vector<double> advisor_;
31 Student(size_t nrFaculty, size_t advisorIndex)
32 : keys_(3), areaName_(3), advisor_(nrFaculty, 1.0) {
33 advisor_[advisorIndex] = 0.0;
34 }
35 void print() const {
36 using std::cout;
37 cout << name_ << ": ";
38 for (size_t area = 0; area < 3; area++) cout << areaName_[area] << " ";
39 cout << std::endl;
40 }
41 };
42
43 /** Maximum number of students */
44 size_t maxNrStudents_;
45
46 /** discrete keys, indexed by student and area index */
47 std::vector<Student> students_;
48
49 /** faculty identifiers */
50 std::map<std::string, size_t> facultyIndex_;
51 std::vector<std::string> facultyName_, slotName_, areaName_;
52
53 /** area constraints */
54 typedef std::map<std::string, std::vector<double> > FacultyInArea;
55 FacultyInArea facultyInArea_;
56
57 /** nrTimeSlots * nrFaculty availability constraints */
58 std::string available_;
59
60 /** which slots are good */
61 std::vector<double> slotsAvailable_;
62
63 public:
64 /**
65 * Constructor
66 * We need to know the number of students in advance for ordering keys.
67 * then add faculty, slots, areas, availability, students, in that order
68 */
69 Scheduler(size_t maxNrStudents) : maxNrStudents_(maxNrStudents) {}
70
71 /// Destructor
72 virtual ~Scheduler() {}
73
74 void addFaculty(const std::string& facultyName) {
75 facultyIndex_[facultyName] = nrFaculty();
76 facultyName_.push_back(x: facultyName);
77 }
78
79 size_t nrFaculty() const { return facultyName_.size(); }
80
81 /** boolean std::string of nrTimeSlots * nrFaculty */
82 void setAvailability(const std::string& available) { available_ = available; }
83
84 void addSlot(const std::string& slotName) { slotName_.push_back(x: slotName); }
85
86 size_t nrTimeSlots() const { return slotName_.size(); }
87
88 const std::string& slotName(size_t s) const { return slotName_[s]; }
89
90 /** slots available, boolean */
91 void setSlotsAvailable(const std::vector<double>& slotsAvailable) {
92 slotsAvailable_ = slotsAvailable;
93 }
94
95 void addArea(const std::string& facultyName, const std::string& areaName) {
96 areaName_.push_back(x: areaName);
97 std::vector<double>& table =
98 facultyInArea_[areaName]; // will create if needed
99 if (table.empty()) table.resize(new_size: nrFaculty(), x: 0);
100 table[facultyIndex_[facultyName]] = 1;
101 }
102
103 /**
104 * Constructor that reads in faculty, slots, availibility.
105 * Still need to add areas and students after this
106 */
107 Scheduler(size_t maxNrStudents, const std::string& filename);
108
109 /** get key for student and area, 0 is time slot itself */
110 const DiscreteKey& key(size_t s,
111 std::optional<size_t> area = {}) const;
112
113 /** addStudent has to be called after adding slots and faculty */
114 void addStudent(const std::string& studentName, const std::string& area1,
115 const std::string& area2, const std::string& area3,
116 const std::string& advisor);
117
118 /// current number of students
119 size_t nrStudents() const { return students_.size(); }
120
121 const std::string& studentName(size_t i) const;
122 const DiscreteKey& studentKey(size_t i) const;
123 const std::string& studentArea(size_t i, size_t area) const;
124
125 /** Add student-specific constraints to the graph */
126 void addStudentSpecificConstraints(
127 size_t i, std::optional<size_t> slot = {});
128
129 /** Main routine that builds factor graph */
130 void buildGraph(size_t mutexBound = 7);
131
132 /** print */
133 void print(
134 const std::string& s = "Scheduler",
135 const KeyFormatter& formatter = DefaultKeyFormatter) const override;
136
137 /** Print readable form of assignment */
138 void printAssignment(const DiscreteValues& assignment) const;
139
140 /** Special print for single-student case */
141 void printSpecial(const DiscreteValues& assignment) const;
142
143 /** Accumulate faculty stats */
144 void accumulateStats(const DiscreteValues& assignment,
145 std::vector<size_t>& stats) const;
146
147 /** Eliminate, return a Bayes net */
148 DiscreteBayesNet::shared_ptr eliminate() const;
149
150 /** find the assignment of students to slots with most possible committees */
151 DiscreteValues bestSchedule() const;
152
153 /** find the corresponding most desirable committee assignment */
154 DiscreteValues bestAssignment(const DiscreteValues& bestSchedule) const;
155
156}; // Scheduler
157
158} // namespace gtsam
159