Go to the documentation of this file.00001 #ifndef SCHEDULER_H
00002 #define SCHEDULER_H
00003
00004 #include <vector>
00005 #include <list>
00006 #include <string>
00007 #include "globals.h"
00008
00009 const double INF = 10000000.0;
00010
00011 typedef std::pair<double, int> Happening;
00012
00013 class SimpleTemporalProblem
00014 {
00015 private:
00016
00017 struct HappeningComparator
00018 {
00019 bool operator()(const Happening& h1, const Happening& h2)
00020 {
00021 if (h1.first < h2.first)
00022 return true;
00023 if (h2.first < h1.first)
00024 return false;
00025 return h1.second < h2.second;
00026 }
00027 };
00028
00029 typedef std::vector<double> MatrixLine;
00030 typedef std::vector<MatrixLine> DistanceMatrix;
00031
00032 int number_of_nodes;
00033 std::vector<std::string> variable_names;
00034 DistanceMatrix m_defaultDistances;
00035 DistanceMatrix matrix;
00036
00037 void setDistance(int from, int to, double distance);
00038
00039 void extractMinimalDistances();
00040
00041 std::vector<std::vector<int> > m_arcsSmaller;
00042 std::vector<std::vector<int> > m_arcsLarger;
00043 std::vector<std::vector<short> > m_connections;
00044 std::vector<int> m_orderingIndexIsNode;
00045 std::vector<int> m_orderingIndexIsOrder;
00046 std::vector<int> m_numberOfNeighbors;
00047 std::vector<double> m_minimalDistances;
00048
00049 public:
00050 SimpleTemporalProblem(std::vector<std::string> _variable_names);
00051
00052 void setInterval(int from, int to, double lower, double upper);
00053
00054 void setSingletonInterval(int from, int to, double lowerAndUpper);
00055 void setUnboundedInterval(int from, int to, double lower);
00056
00057 void setIntervalFromXZero(int to, double lower, double upper);
00058 void setUnboundedIntervalFromXZero(int to, double lower);
00059
00060 void setCurrentDistancesAsDefault();
00061 void solve();
00062 bool solveWithP3C();
00063 void makeGraphChordal();
00064 void initializeArcVectors();
00065 bool performDPC();
00066 inline bool arcExists(int nodeA, int nodeB)
00067 {
00068 return (m_connections[nodeA][nodeB]);
00069 }
00070 double add(double a, double b);
00071 void createFillEdges(std::list<int>& currentChildren);
00072 void collectChildren(int currentNode, std::list<int>& currentChildren,
00073 bool ignoreNodesInOrdering);
00074 int getNextNodeInOrdering();
00075 int calcNumberOfNeighbors(int node);
00076 bool isNodeAlreadyInOrdering(int node);
00077
00078 bool solution_is_valid();
00079 double getMaximalTimePointInTightestSchedule(bool useP3C);
00080 void reset();
00081
00082 void dumpDistances();
00083 void dumpConnections();
00084 void dumpSolution();
00085 std::vector<Happening> getHappenings(bool useP3C);
00086 };
00087
00088 #endif