Scheduler.cpp
Go to the documentation of this file.
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>
12 
13 #include <boost/tokenizer.hpp>
14 #include <cmath>
15 #include <fstream>
16 #include <iomanip>
17 
18 namespace gtsam {
19 
20 using namespace std;
21 
22 Scheduler::Scheduler(size_t maxNrStudents, const string& filename)
23  : maxNrStudents_(maxNrStudents) {
24  typedef boost::tokenizer<boost::escaped_list_separator<char> > Tokenizer;
25 
26  // open file
27  ifstream is(filename.c_str());
28  if (!is) {
29  cerr << "Scheduler: could not open file " << filename << endl;
30  throw runtime_error("Scheduler: could not open file " + filename);
31  }
32 
33  string line; // buffer
34 
35  // process first line with faculty
36  if (getline(is, line, '\r')) {
37  Tokenizer tok(line);
38  Tokenizer::iterator it = tok.begin();
39  for (++it; it != tok.end(); ++it) addFaculty(*it);
40  }
41 
42  // for all remaining lines
43  size_t count = 0;
44  while (getline(is, line, '\r')) {
45  if (count++ > 100) throw runtime_error("reached 100 lines, exiting");
46  Tokenizer tok(line);
47  Tokenizer::iterator it = tok.begin();
48  addSlot(*it++); // add slot
49  // add availability
50  for (; it != tok.end(); ++it) available_ += (it->empty()) ? "0 " : "1 ";
51  available_ += '\n';
52  }
53 } // constructor
54 
56 void Scheduler::addStudent(const string& studentName, const string& area1,
57  const string& area2, const string& area3,
58  const string& advisor) {
59  assert(nrStudents() < maxNrStudents_);
60  assert(facultyInArea_.count(area1));
61  assert(facultyInArea_.count(area2));
62  assert(facultyInArea_.count(area3));
63  size_t advisorIndex = facultyIndex_[advisor];
64  Student student(nrFaculty(), advisorIndex);
65  student.name_ = studentName;
66  // We fix the ordering by assigning a higher index to the student
67  // and numbering the areas lower
68  Key j = 3 * maxNrStudents_ + nrStudents();
69  student.key_ = DiscreteKey(j, nrTimeSlots());
70  Key base = 3 * nrStudents();
71  student.keys_[0] = DiscreteKey(base + 0, nrFaculty());
72  student.keys_[1] = DiscreteKey(base + 1, nrFaculty());
73  student.keys_[2] = DiscreteKey(base + 2, nrFaculty());
74  student.areaName_[0] = area1;
75  student.areaName_[1] = area2;
76  student.areaName_[2] = area3;
77  students_.push_back(student);
78 }
79 
82  std::optional<size_t> area) const {
83  return area ? students_[s].keys_[*area] : students_[s].key_;
84 }
85 
86 const string& Scheduler::studentName(size_t i) const {
87  assert(i < nrStudents());
88  return students_[i].name_;
89 }
90 
91 const DiscreteKey& Scheduler::studentKey(size_t i) const {
92  assert(i < nrStudents());
93  return students_[i].key_;
94 }
95 
96 const string& Scheduler::studentArea(size_t i, size_t area) const {
97  assert(i < nrStudents());
98  return students_[i].areaName_[area];
99 }
100 
103  std::optional<size_t> slot) {
104  bool debug = ISDEBUG("Scheduler::buildGraph");
105 
106  assert(i < nrStudents());
107  const Student& s = students_[i];
108 
109  if (!slot && !slotsAvailable_.empty()) {
110  if (debug) cout << "Adding availability of slots" << endl;
111  assert(slotsAvailable_.size() == s.key_.second);
112  CSP::add(s.key_, slotsAvailable_);
113  }
114 
115  // For all areas
116  for (size_t area = 0; area < 3; area++) {
117  DiscreteKey areaKey = s.keys_[area];
118  const string& areaName = s.areaName_[area];
119 
120  if (debug) cout << "Area constraints " << areaName << endl;
121  assert(facultyInArea_[areaName].size() == areaKey.second);
122  CSP::add(areaKey, facultyInArea_[areaName]);
123 
124  if (debug) cout << "Advisor constraint " << areaName << endl;
125  assert(s.advisor_.size() == areaKey.second);
126  CSP::add(areaKey, s.advisor_);
127 
128  if (debug) cout << "Availability of faculty " << areaName << endl;
129  if (slot) {
130  // get all constraints then specialize to slot
131  size_t dummyIndex = maxNrStudents_ * 3 + maxNrStudents_;
132  DiscreteKey dummy(dummyIndex, nrTimeSlots());
134  available_); // available_ is Doodle string
135  auto q = p.choose(dummyIndex, *slot);
136  CSP::add(areaKey, q);
137  } else {
138  DiscreteKeys keys {s.key_, areaKey};
139  CSP::add(keys, available_); // available_ is Doodle string
140  }
141  }
142 
143  // add mutex
144  if (debug) cout << "Mutex for faculty" << endl;
145  addAllDiff(s.keys_[0] & s.keys_[1] & s.keys_[2]);
146 }
147 
149 void Scheduler::buildGraph(size_t mutexBound) {
150  bool debug = ISDEBUG("Scheduler::buildGraph");
151 
152  if (debug) cout << "Adding student-specific constraints" << endl;
153  for (size_t i = 0; i < nrStudents(); i++) addStudentSpecificConstraints(i);
154 
155  // special constraint for MN
156  if (studentName(0) == "Michael N")
157  CSP::add(studentKey(0), "0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1");
158 
159  if (!mutexBound) {
160  DiscreteKeys dkeys;
161  for (const Student& s : students_) dkeys.push_back(s.key_);
162  addAllDiff(dkeys);
163  } else {
164  if (debug) cout << "Mutex for Students" << endl;
165  for (size_t i1 = 0; i1 < nrStudents(); i1++) {
166  // if mutexBound=1, we only mutex with next student
167  size_t bound = min((i1 + 1 + mutexBound), nrStudents());
168  for (size_t i2 = i1 + 1; i2 < bound; i2++) {
170  }
171  }
172  }
173 } // buildGraph
174 
176 void Scheduler::print(const string& s, const KeyFormatter& formatter) const {
177  cout << s << " Faculty:" << endl;
178  for (const string& name : facultyName_) cout << name << '\n';
179  cout << endl;
180 
181  cout << s << " Slots:\n";
182  size_t i = 0;
183  for (const string& name : slotName_) cout << i++ << " " << name << endl;
184  cout << endl;
185 
186  cout << "Availability:\n" << available_ << '\n';
187 
188  cout << s << " Area constraints:\n";
189  for (const FacultyInArea::value_type& it : facultyInArea_) {
190  cout << setw(12) << it.first << ": ";
191  for (double v : it.second) cout << v << " ";
192  cout << '\n';
193  }
194  cout << endl;
195 
196  cout << s << " Students:\n";
197  for (const Student& student : students_) student.print();
198  cout << endl;
199 
200  CSP::print(s + " Factor graph");
201  cout << endl;
202 } // print
203 
205 void Scheduler::printAssignment(const DiscreteValues& assignment) const {
206  // Not intended to be general! Assumes very particular ordering !
207  cout << endl;
208  for (size_t s = 0; s < nrStudents(); s++) {
209  Key j = 3 * maxNrStudents_ + s;
210  size_t slot = assignment.at(j);
211  cout << studentName(s) << " slot: " << slotName_[slot] << endl;
212  Key base = 3 * s;
213  for (size_t area = 0; area < 3; area++) {
214  size_t faculty = assignment.at(base + area);
215  cout << setw(12) << studentArea(s, area) << ": " << facultyName_[faculty]
216  << endl;
217  }
218  cout << endl;
219  }
220 }
221 
223 void Scheduler::printSpecial(const DiscreteValues& assignment) const {
224  DiscreteValues::const_iterator it = assignment.begin();
225  for (size_t area = 0; area < 3; area++, it++) {
226  size_t f = it->second;
227  cout << setw(12) << studentArea(0, area) << ": " << facultyName_[f] << endl;
228  }
229  cout << endl;
230 }
231 
234  vector<size_t>& stats) const {
235  for (size_t s = 0; s < nrStudents(); s++) {
236  Key base = 3 * s;
237  for (size_t area = 0; area < 3; area++) {
238  size_t f = assignment.at(base + area);
239  assert(f < stats.size());
240  stats[f]++;
241  } // area
242  } // s
243 }
244 
247  gttic(my_eliminate);
248  // TODO: fix this!!
249  size_t maxKey = keys().size();
250  Ordering defaultKeyOrdering;
251  for (size_t i = 0; i < maxKey; ++i) defaultKeyOrdering.push_back(i);
253  this->eliminateSequential(defaultKeyOrdering);
254  gttoc(my_eliminate);
255  return chordal;
256 }
257 
260  DiscreteValues best;
261  throw runtime_error("bestSchedule not implemented");
262  return best;
263 }
264 
267  DiscreteValues best;
268  throw runtime_error("bestAssignment not implemented");
269  return best;
270 }
271 
272 } // namespace gtsam
gttoc
#define gttoc(label)
Definition: timing.h:296
timing.h
Timing utilities.
gtsam::EliminateableFactorGraph< DiscreteFactorGraph >::eliminateSequential
std::shared_ptr< BayesNetType > eliminateSequential(OptionalOrderingType orderingType={}, const Eliminate &function=EliminationTraitsType::DefaultEliminate, OptionalVariableIndex variableIndex={}) const
Definition: EliminateableFactorGraph-inst.h:29
gtsam::Scheduler::addFaculty
void addFaculty(const std::string &facultyName)
Definition: Scheduler.h:74
name
Annotation for function names.
Definition: attr.h:51
base
Annotation indicating that a class derives from another given type.
Definition: attr.h:64
s
RealScalar s
Definition: level1_cplx_impl.h:126
gtsam::Scheduler::facultyInArea_
FacultyInArea facultyInArea_
Definition: Scheduler.h:55
gtsam::bound
double bound(double a, double min, double max)
Definition: PoseRTV.cpp:17
DiscreteFactorGraph.h
gtsam::DiscreteFactorGraph::keys
KeySet keys() const
Definition: DiscreteFactorGraph.cpp:45
gtsam::Scheduler::slotName_
std::vector< std::string > slotName_
Definition: Scheduler.h:51
gtsam::maxKey
Key maxKey(const PROBLEM &problem)
Definition: ActiveSetSolver.h:191
gtsam::Scheduler::Student::keys_
std::vector< DiscreteKey > keys_
Definition: Scheduler.h:28
gtsam::Scheduler::accumulateStats
void accumulateStats(const DiscreteValues &assignment, std::vector< size_t > &stats) const
Definition: Scheduler.cpp:233
formatter
const KeyFormatter & formatter
Definition: treeTraversal-inst.h:204
gtsam::DiscreteKeys
DiscreteKeys is a set of keys that can be assembled using the & operator.
Definition: DiscreteKey.h:41
gtsam::DiscreteFactorGraph::print
void print(const std::string &s="DiscreteFactorGraph", const KeyFormatter &formatter=DefaultKeyFormatter) const override
print
Definition: DiscreteFactorGraph.cpp:84
gtsam::Scheduler::students_
std::vector< Student > students_
Definition: Scheduler.h:47
gtsam::Scheduler::printSpecial
void printSpecial(const DiscreteValues &assignment) const
Definition: Scheduler.cpp:223
pybind_wrapper_test_script.dummy
dummy
Definition: pybind_wrapper_test_script.py:42
gtsam::Scheduler::Student::areaName_
std::vector< std::string > areaName_
Definition: Scheduler.h:29
gtsam::AlgebraicDecisionTree< Key >
gtsam::Scheduler::maxNrStudents_
size_t maxNrStudents_
Definition: Scheduler.h:44
ISDEBUG
#define ISDEBUG(S)
Definition: debug.h:60
gtsam::Scheduler::bestSchedule
DiscreteValues bestSchedule() const
Definition: Scheduler.cpp:259
gtsam::Scheduler::addSlot
void addSlot(const std::string &slotName)
Definition: Scheduler.h:84
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
gtsam::Scheduler::addStudentSpecificConstraints
void addStudentSpecificConstraints(size_t i, std::optional< size_t > slot={})
Definition: Scheduler.cpp:102
stats
bool stats
Definition: SolverComparer.cpp:100
Eigen::numext::q
EIGEN_DEVICE_FUNC const Scalar & q
Definition: SpecialFunctionsImpl.h:1984
relicense.filename
filename
Definition: relicense.py:57
gtsam::Scheduler::Student::key_
DiscreteKey key_
Definition: Scheduler.h:27
gtsam::KeyFormatter
std::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
Definition: Key.h:35
gtsam::Scheduler::studentArea
const std::string & studentArea(size_t i, size_t area) const
Definition: Scheduler.cpp:96
debug
static constexpr bool debug
Definition: testDiscreteBayesTree.cpp:31
gtsam::CSP::addAllDiff
void addAllDiff(const DiscreteKey &key1, const DiscreteKey &key2)
Add a binary AllDiff constraint.
Definition: CSP.h:31
gtsam::Scheduler::eliminate
DiscreteBayesNet::shared_ptr eliminate() const
Definition: Scheduler.cpp:246
gtsam::Scheduler::facultyName_
std::vector< std::string > facultyName_
Definition: Scheduler.h:51
gtsam::Scheduler::slotsAvailable_
std::vector< double > slotsAvailable_
Definition: Scheduler.h:61
Scheduler.h
gtsam::Scheduler::facultyIndex_
std::map< std::string, size_t > facultyIndex_
Definition: Scheduler.h:50
gtsam::Scheduler::printAssignment
void printAssignment(const DiscreteValues &assignment) const
Definition: Scheduler.cpp:205
tree::f
Point2(* f)(const Point3 &, OptionalJacobian< 2, 3 >)
Definition: testExpression.cpp:218
gtsam::FactorGraph< DiscreteFactor >::size
size_t size() const
Definition: FactorGraph.h:297
gtsam
traits
Definition: SFMdata.h:40
i1
double i1(double x)
Definition: i1.c:150
gtsam::DiscreteValues
Definition: DiscreteValues.h:34
gtsam::Scheduler::Scheduler
Scheduler(size_t maxNrStudents)
Definition: Scheduler.h:69
gtsam::DiscreteKey
std::pair< Key, size_t > DiscreteKey
Definition: DiscreteKey.h:38
gtsam::Scheduler::bestAssignment
DiscreteValues bestAssignment(const DiscreteValues &bestSchedule) const
Definition: Scheduler.cpp:266
std
Definition: BFloat16.h:88
p
float * p
Definition: Tutorial_Map_using.cpp:9
gtsam::Scheduler::nrStudents
size_t nrStudents() const
current number of students
Definition: Scheduler.h:119
gtsam::Scheduler::available_
std::string available_
Definition: Scheduler.h:58
gtsam::DiscreteFactorGraph::add
void add(Args &&... args)
Definition: DiscreteFactorGraph.h:138
v
Array< int, Dynamic, 1 > v
Definition: Array_initializer_list_vector_cxx11.cpp:1
gtsam::DiscreteBayesNet::shared_ptr
std::shared_ptr< This > shared_ptr
Definition: DiscreteBayesNet.h:43
gtsam::Scheduler::Student::name_
std::string name_
Definition: Scheduler.h:26
min
#define min(a, b)
Definition: datatypes.h:19
gtsam::Scheduler::print
void print(const std::string &s="Scheduler", const KeyFormatter &formatter=DefaultKeyFormatter) const override
Definition: Scheduler.cpp:176
gtsam::Scheduler::studentName
const std::string & studentName(size_t i) const
Definition: Scheduler.cpp:86
gtsam::Scheduler::buildGraph
void buildGraph(size_t mutexBound=7)
Definition: Scheduler.cpp:149
gtsam::Scheduler::key
const DiscreteKey & key(size_t s, std::optional< size_t > area={}) const
Definition: Scheduler.cpp:81
gtsam::Scheduler::nrFaculty
size_t nrFaculty() const
Definition: Scheduler.h:79
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:97
gtsam::Ordering
Definition: inference/Ordering.h:33
gtsam::Scheduler::addStudent
void addStudent(const std::string &studentName, const std::string &area1, const std::string &area2, const std::string &area3, const std::string &advisor)
Definition: Scheduler.cpp:56
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
gtsam::Scheduler::studentKey
const DiscreteKey & studentKey(size_t i) const
Definition: Scheduler.cpp:91
gtsam::Scheduler::nrTimeSlots
size_t nrTimeSlots() const
Definition: Scheduler.h:86
gtsam::Scheduler::Student
Definition: Scheduler.h:25
gttic
#define gttic(label)
Definition: timing.h:295
debug.h
Global debugging flags.


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:35:01