testScheduler.cpp

Go to the documentation of this file.

/*
 * testScheduler.cpp
 * @date March 25, 2011
 * @author Frank Dellaert
 */
 
//#define ENABLE_TIMING
#include <CppUnitLite/TestHarness.h>
#include <gtsam/base/Testable.h>
#include <gtsam/base/timing.h>
#include <gtsam_unstable/discrete/Scheduler.h>
 
 
using namespace std;
using namespace gtsam;
 
/* ************************************************************************* */
// Create the expected graph of constraints
DiscreteFactorGraph createExpected() {
  // Start building
  size_t nrFaculty = 4, nrTimeSlots = 3;
 
  // variables assigning a time to a student:
  // Akansel and Jake
  DiscreteKey A(6, nrTimeSlots), J(7, nrTimeSlots);
 
  // variables assigning a faculty member to a student area
  // Akansel:AI,ME,PC and Jake:HR,CT,AI
  DiscreteKey A1(0, nrFaculty), J1(3, nrFaculty);
  DiscreteKey A2(1, nrFaculty), J2(4, nrFaculty);
  DiscreteKey A3(2, nrFaculty), J3(5, nrFaculty);
 
  CSP expected;
 
  // Area constraints
  string faculty_in_A = "1 0 0 1";
  string faculty_in_C = "0 0 1 0";
  string faculty_in_H = "0 0 0 1";
  string faculty_in_M = "0 1 0 0";
  string faculty_in_P = "1 0 1 0";
  string available = "1 1 1 0   1 1 1 1   0 1 1 1";
 
  // Akansel
  expected.add(A1, faculty_in_A);  // Area 1
  expected.add(A1, "1 1 1 0");     // Advisor
  expected.add(A & A1, available);
  expected.add(A2, faculty_in_M);  // Area 2
  expected.add(A2, "1 1 1 0");     // Advisor
  expected.add(A & A2, available);
  expected.add(A3, faculty_in_P);  // Area 3
  expected.add(A3, "1 1 1 0");     // Advisor
  expected.add(A & A3, available);
  // Mutual exclusion for faculty
  expected.addAllDiff(A1 & A2 & A3);
 
  // Jake
  expected.add(J1, faculty_in_H);  // Area 1
  expected.add(J1, "1 0 1 1");     // Advisor
  expected.add(J & J1, available);
  expected.add(J2, faculty_in_C);  // Area 2
  expected.add(J2, "1 0 1 1");     // Advisor
  expected.add(J & J2, available);
  expected.add(J3, faculty_in_A);  // Area 3
  expected.add(J3, "1 0 1 1");     // Advisor
  expected.add(J & J3, available);
  // Mutual exclusion for faculty
  expected.addAllDiff(J1 & J2 & J3);
 
  // Mutual exclusion for students
  expected.addAllDiff(A, J);
 
  return std::move(expected);
}
 
/* ************************************************************************* */
TEST(schedulingExample, test) {
  Scheduler s(2);
 
  // add faculty
  s.addFaculty("Frank");
  s.addFaculty("Harvey");
  s.addFaculty("Magnus");
  s.addFaculty("Andrea");
 
  // add time slots
  s.addSlot("Mon");
  s.addSlot("Wed");
  s.addSlot("Fri");
 
  // add areas
  s.addArea("Frank", "AI");
  s.addArea("Frank", "PC");
  s.addArea("Harvey", "ME");
  s.addArea("Magnus", "CT");
  s.addArea("Magnus", "PC");
  s.addArea("Andrea", "AI");
  s.addArea("Andrea", "HR");
 
  // add availability, nrTimeSlots * nrFaculty
  string available = "1 1 1 0  1 1 1 1  0 1 1 1";
  s.setAvailability(available);
 
  // add students
  s.addStudent("Akansel", "AI", "ME", "PC", "Andrea");
  s.addStudent("Jake", "HR", "CT", "AI", "Harvey");
 
  // BUILD THE GRAPH !
  s.buildGraph();
  //  s.print();
 
  // Check graph
  DiscreteFactorGraph expected = createExpected();
  EXPECT(assert_equal(expected, (DiscreteFactorGraph)s));
 
  // Do brute force product and output that to file
  DecisionTreeFactor product = s.product();
  // product.dot("scheduling", false);
 
  // Do exact inference
  gttic(small);
  auto MPE = s.optimize();
  gttoc(small);
 
  // print MPE, commented out as unit tests don't print
  //  s.printAssignment(MPE);
 
  // Commented out as does not work yet
  // s.runArcConsistency(8,10,true);
 
  // find the assignment of students to slots with most possible committees
  // Commented out as not implemented yet
  //  auto bestSchedule = s.bestSchedule();
  //  GTSAM_PRINT(bestSchedule);
 
  //  find the corresponding most desirable committee assignment
  // Commented out as not implemented yet
  //  auto bestAssignment = s.bestAssignment(bestSchedule);
  //  GTSAM_PRINT(bestAssignment);
}
 
/* ************************************************************************* */
TEST(schedulingExample, smallFromFile) {
  string path(TOPSRCDIR "/gtsam_unstable/discrete/examples/");
  Scheduler s(2, path + "small.csv");
 
  // add areas
  s.addArea("Frank", "AI");
  s.addArea("Frank", "PC");
  s.addArea("Harvey", "ME");
  s.addArea("Magnus", "CT");
  s.addArea("Magnus", "PC");
  s.addArea("Andrea", "AI");
  s.addArea("Andrea", "HR");
 
  //   add students
  s.addStudent("Akansel", "AI", "ME", "PC", "Andrea");
  s.addStudent("Jake", "HR", "CT", "AI", "Harvey");
  //  s.print();
 
  // BUILD THE GRAPH !
  s.buildGraph();
 
  // Check graph
  DiscreteFactorGraph expected = createExpected();
  EXPECT(assert_equal(expected, (DiscreteFactorGraph)s));
}
 
/* ************************************************************************* */
int main() {
  TestResult tr;
  return TestRegistry::runAllTests(tr);
}
/* ************************************************************************* */