00001 #include "scheduler.h"
00002
00003 #include <cassert>
00004 #include <iostream>
00005 #include <iomanip>
00006 #include <sstream>
00007 #include <algorithm>
00008
00009 SimpleTemporalProblem::SimpleTemporalProblem(
00010 std::vector<std::string> _variable_names) :
00011 variable_names(_variable_names)
00012 {
00013 variable_names.push_back("X0");
00014 number_of_nodes = variable_names.size();
00015 m_minimalDistances.resize(number_of_nodes);
00016 for (int i = 0; i < number_of_nodes; ++i) {
00017 matrix.push_back(MatrixLine(number_of_nodes, INF));
00018 m_minimalDistances[i] = INF;
00019 m_connections.push_back(vector<short> (number_of_nodes, 0));
00020 m_orderingIndexIsNode.push_back(-1);
00021 m_orderingIndexIsOrder.push_back(-1);
00022 }
00023 m_minimalDistances[number_of_nodes - 1] = 0.0;
00024 for (int i = 0; i < number_of_nodes; i++) {
00025 matrix[i][i] = 0.0;
00026 }
00027 }
00028
00029
00030 void SimpleTemporalProblem::setDistance(int from, int to, double distance)
00031 {
00032
00033 assert(0 <= from && from < number_of_nodes);
00034 assert(0 <= to && to < number_of_nodes);
00035 assert(from != to);
00036 matrix[from][to] = distance;
00037 m_connections[from][to] = 1;
00038 }
00039
00040
00041 void SimpleTemporalProblem::setInterval(int from, int to, double lower,
00042 double upper)
00043 {
00044 setDistance(from, to, upper);
00045 setDistance(to, from, -lower);
00046 }
00047
00048
00049 void SimpleTemporalProblem::setSingletonInterval(int from, int to,
00050 double lowerAndUpper)
00051 {
00052 setInterval(from, to, lowerAndUpper, lowerAndUpper);
00053 }
00054
00055
00056
00057 void SimpleTemporalProblem::setUnboundedInterval(int from, int to, double lower)
00058 {
00059 setInterval(from, to, lower, INF);
00060 }
00061
00062 void SimpleTemporalProblem::setIntervalFromXZero(int to, double lower,
00063 double upper)
00064 {
00065 setInterval(number_of_nodes - 1, to, lower, upper);
00066 }
00067
00068 void SimpleTemporalProblem::setUnboundedIntervalFromXZero(int to, double lower)
00069 {
00070 setUnboundedInterval(number_of_nodes - 1, to, lower);
00071 }
00072
00073
00074 void SimpleTemporalProblem::solve()
00075 {
00076 double triangle_length;
00077
00078 for (size_t k = 0; k < number_of_nodes; k++) {
00079 vector<double>& matrixK = matrix[k];
00080 for (size_t i = 0; i < number_of_nodes; i++) {
00081 vector<double>& matrixI = matrix[i];
00082 for (size_t j = 0; j < number_of_nodes; j++) {
00083 triangle_length = matrixI[k];
00084 if (triangle_length != INF) {
00085 triangle_length += matrixK[j];
00086 }
00087 double& mij = matrixI[j];
00088 if (triangle_length < INF && triangle_length < mij) {
00089
00090 mij = triangle_length;
00091 }
00092 }
00093 }
00094 }
00095 }
00096
00097 bool SimpleTemporalProblem::solveWithP3C()
00098 {
00099 makeGraphChordal();
00100 initializeArcVectors();
00101 if (!performDPC()) {
00102 return false;
00103 }
00104 assert(m_orderingIndexIsNode.size() == number_of_nodes);
00105 for (int k = 0; k < number_of_nodes; ++k) {
00106 int kNode = m_orderingIndexIsOrder[k];
00107 for (int i = 0; i < m_arcsLarger[kNode].size(); ++i) {
00108 int iNode = m_arcsLarger[kNode][i];
00109 for (int j = 0; j < m_arcsLarger[kNode].size(); ++j) {
00110 if (i == j) {
00111 continue;
00112 }
00113 int jNode = m_arcsLarger[kNode][j];
00114 assert(arcExists(iNode, kNode) && arcExists(jNode, kNode));
00115 assert(arcExists(kNode, jNode));
00116 assert(arcExists(iNode, kNode));
00117 double triangleLength = add(matrix[iNode][jNode],
00118 matrix[jNode][kNode]);
00119 double originalLength = matrix[iNode][kNode];
00120 if (triangleLength < originalLength) {
00121 matrix[iNode][kNode] = triangleLength;
00122 }
00123 triangleLength
00124 = add(matrix[kNode][iNode], matrix[iNode][jNode]);
00125 originalLength = matrix[kNode][jNode];
00126 if (triangleLength < originalLength) {
00127 matrix[kNode][jNode] = triangleLength;
00128 }
00129 }
00130 }
00131 }
00132 extractMinimalDistances();
00133 return true;
00134 }
00135
00136 bool SimpleTemporalProblem::performDPC()
00137 {
00138 assert(m_orderingIndexIsNode.size() == m_orderingIndexIsOrder.size());
00139 assert(m_orderingIndexIsNode.size() == number_of_nodes);
00140 for (int k = number_of_nodes - 1; k >= 0; --k) {
00141 int kNode = m_orderingIndexIsOrder[k];
00142 for (int i = 0; i < m_arcsSmaller[kNode].size(); ++i) {
00143 int iNode = m_arcsSmaller[kNode][i];
00144 for (int j = 0; j < m_arcsSmaller[kNode].size(); ++j) {
00145 if (i == j) {
00146 continue;
00147 }
00148 int jNode = m_arcsSmaller[kNode][j];
00149 assert(arcExists(iNode, kNode) && arcExists(jNode, kNode));
00150 assert(arcExists(iNode, jNode));
00151 double triangleLength = add(matrix[iNode][kNode],
00152 matrix[kNode][jNode]);
00153 double originalLength = matrix[iNode][jNode];
00154 if (triangleLength < originalLength) {
00155 matrix[iNode][jNode] = triangleLength;
00156 }
00157 if (matrix[iNode][jNode] + matrix[jNode][iNode] < 0) {
00158 return false;
00159 }
00160 }
00161 }
00162 }
00163 return true;
00164 }
00165
00166 void SimpleTemporalProblem::makeGraphChordal()
00167 {
00168 m_numberOfNeighbors.resize(number_of_nodes);
00169 for (int i = 0; i < number_of_nodes; ++i) {
00170 m_numberOfNeighbors[i] = calcNumberOfNeighbors(i);
00171 }
00172
00173 int currentNode;
00174 list<int> currentChildren;
00175 int nextPositionInOrdering = 0;
00176 while ((currentNode = getNextNodeInOrdering()) != -1) {
00177 for (int j = 0; j < number_of_nodes; ++j) {
00178 if (arcExists(currentNode, j)) {
00179 m_numberOfNeighbors[j]--;
00180 }
00181 }
00182
00183 m_orderingIndexIsNode[m_orderingIndexIsNode.size() - currentNode - 1]
00184 = nextPositionInOrdering;
00185 m_orderingIndexIsOrder[m_orderingIndexIsOrder.size()
00186 - nextPositionInOrdering - 1] = currentNode;
00187 nextPositionInOrdering++;
00188
00189 currentChildren.clear();
00190 collectChildren(currentNode, currentChildren, true);
00191 createFillEdges(currentChildren);
00192 }
00193 }
00194
00195 void SimpleTemporalProblem::extractMinimalDistances()
00196 {
00197 assert(m_minimalDistances[number_of_nodes-1] == 0.0);
00198 list<int> nodesToUpdate;
00199 nodesToUpdate.push_front(number_of_nodes - 1);
00200 while (!nodesToUpdate.empty()) {
00201 int currentNode = nodesToUpdate.back();
00202 nodesToUpdate.pop_back();
00203 list<int> currentChilds;
00204 currentChilds.clear();
00205 collectChildren(currentNode, currentChilds, false);
00206 list<int>::const_iterator it;
00207 for (it = currentChilds.begin(); it != currentChilds.end(); ++it) {
00208 int currentChild = *it;
00209 assert(currentNode != currentChild);
00210 double newDistance = add(m_minimalDistances[currentNode],
00211 matrix[currentChild][currentNode]);
00212 if (newDistance < m_minimalDistances[currentChild]) {
00213 m_minimalDistances[currentChild] = newDistance;
00214 nodesToUpdate.push_front(currentChild);
00215 }
00216 }
00217 }
00218 }
00219
00220 void SimpleTemporalProblem::initializeArcVectors()
00221 {
00222 m_arcsLarger.clear();
00223 m_arcsSmaller.clear();
00224 for (int i = 0; i < number_of_nodes; ++i) {
00225 int iNode = m_orderingIndexIsOrder[i];
00226 m_arcsLarger.resize(number_of_nodes);
00227 m_arcsSmaller.resize(number_of_nodes);
00228 for (int j = i + 1; j < number_of_nodes; ++j) {
00229 int jNode = m_orderingIndexIsOrder[j];
00230 if (arcExists(iNode, jNode)) {
00231 m_arcsLarger[iNode].push_back(jNode);
00232 }
00233 }
00234 for (int j = i - 1; j >= 0; --j) {
00235 int jNode = m_orderingIndexIsOrder[j];
00236 if (arcExists(iNode, jNode)) {
00237 m_arcsSmaller[iNode].push_back((jNode));
00238 }
00239 }
00240 }
00241 }
00242
00243 double SimpleTemporalProblem::add(double a, double b)
00244 {
00245 if (a == INF || b == INF || a + b >= INF)
00246 return INF;
00247 return a + b;
00248 }
00249
00250 void SimpleTemporalProblem::createFillEdges(list<int>& currentChildren)
00251 {
00252 list<int>::const_iterator it1, it2;
00253 for (it1 = currentChildren.begin(); it1 != currentChildren.end(); ++it1) {
00254 it2 = it1;
00255 it2++;
00256 for (; it2 != currentChildren.end(); ++it2) {
00257 if (!arcExists(*it1, *it2)) {
00258 setInterval(*it1, *it2, -INF, +INF);
00259 m_numberOfNeighbors[*it1]++;
00260 m_numberOfNeighbors[*it2]++;
00261 }
00262 }
00263 }
00264 }
00265
00266 void SimpleTemporalProblem::collectChildren(int currentNode,
00267 list<int>& currentChildren, bool ignoreNodesInOrdering)
00268 {
00269 for (int i = 0; i < number_of_nodes; ++i) {
00270 if (arcExists(currentNode, i) && (!ignoreNodesInOrdering
00271 || !isNodeAlreadyInOrdering(i))) {
00272 currentChildren.push_back(i);
00273 }
00274 }
00275 }
00276
00277 int SimpleTemporalProblem::getNextNodeInOrdering()
00278 {
00279 int ret = -1;
00280 int maxNumberOfNeighbors = 10000;
00281 for (int i = 0; i < matrix.size(); ++i) {
00282 if (!isNodeAlreadyInOrdering(i)) {
00283 int numberOfNeighbors = m_numberOfNeighbors[i];
00284 if (numberOfNeighbors < maxNumberOfNeighbors) {
00285 ret = i;
00286 maxNumberOfNeighbors = numberOfNeighbors;
00287 }
00288 }
00289 }
00290 return ret;
00291 }
00292
00293 int SimpleTemporalProblem::calcNumberOfNeighbors(int node)
00294 {
00295 int ret = 0;
00296 for (int i = 0; i < number_of_nodes; ++i) {
00297 if (arcExists(node, i) && !isNodeAlreadyInOrdering(i)) {
00298 ret++;
00299 }
00300 }
00301 return ret;
00302 }
00303
00304 bool SimpleTemporalProblem::isNodeAlreadyInOrdering(int node)
00305 {
00306 return (m_orderingIndexIsNode[m_orderingIndexIsNode.size() - node - 1]
00307 != -1);
00308 }
00309
00310
00311 bool SimpleTemporalProblem::solution_is_valid()
00312 {
00313 for (size_t i = 0; i < number_of_nodes; i++) {
00314 for (size_t j = i + 1; j < number_of_nodes; j++) {
00315 if (matrix[i][j] < -matrix[j][i]) {
00316 return false;
00317 }
00318 }
00319 }
00320 return true;
00321 }
00322
00323
00324 double SimpleTemporalProblem::getMaximalTimePointInTightestSchedule(bool useP3C)
00325 {
00326 double min = 0.0;
00327 for (size_t i = 0; i < number_of_nodes - 1; i++) {
00328 double time = useP3C ? m_minimalDistances[i]
00329 : matrix[i][number_of_nodes - 1];
00330 if (time < min)
00331 min = time;
00332 }
00333 return -min;
00334 }
00335
00336 void SimpleTemporalProblem::setCurrentDistancesAsDefault()
00337 {
00338 m_defaultDistances = matrix;
00339 }
00340
00341 void SimpleTemporalProblem::reset()
00342 {
00343 matrix = m_defaultDistances;
00344 for (int i = 0; i < number_of_nodes; ++i) {
00345 m_orderingIndexIsNode[i] = -1;
00346 m_orderingIndexIsOrder[i] = -1;
00347 m_minimalDistances[i] = INF;
00348 }
00349 m_minimalDistances[number_of_nodes - 1] = 0.0;
00350 }
00351
00352
00353 void SimpleTemporalProblem::dumpDistances()
00354 {
00355 std::cout << std::setw(10) << "";
00356 for (size_t i = 0; i < number_of_nodes; i++) {
00357 std::cout << std::setw(10) << i;
00358 }
00359 std::cout << std::endl;
00360 for (size_t i = 0; i < number_of_nodes; i++) {
00361 std::cout << std::setw(10) << i;
00362 for (size_t j = 0; j < number_of_nodes; j++) {
00363 std::cout << std::setw(10) << matrix[i][j];
00364 }
00365 std::cout << std::endl;
00366 }
00367 std::cout << std::endl;
00368 }
00369
00370
00371 void SimpleTemporalProblem::dumpConnections()
00372 {
00373 std::cout << std::setw(10) << "";
00374 for (size_t i = 0; i < number_of_nodes; i++) {
00375 std::cout << std::setw(10) << i;
00376 }
00377 std::cout << std::endl;
00378 for (size_t i = 0; i < number_of_nodes; i++) {
00379 std::cout << std::setw(10) << i;
00380 for (size_t j = 0; j < number_of_nodes; j++) {
00381 std::cout << std::setw(10) << m_connections[i][j];
00382 }
00383 std::cout << std::endl;
00384 }
00385 std::cout << std::endl;
00386 }
00387
00388
00389 void SimpleTemporalProblem::dumpSolution()
00390 {
00391
00392 std::vector<Happening> happenings = getHappenings(true);
00393
00394 for (size_t i = 0; i < happenings.size(); i++) {
00395 assert(happenings[i].second <= number_of_nodes-1);
00396 std::string& node = variable_names[happenings[i].second];
00397 std::cout << " " << node << "@" << happenings[i].first << std::endl;
00398 }
00399 std::cout << std::endl;
00400 }
00401
00402 std::vector<Happening> SimpleTemporalProblem::getHappenings(bool useP3C)
00403 {
00404 std::vector<Happening> happenings;
00405 for (size_t i = 0; i < number_of_nodes - 1; i++) {
00406 double time = useP3C ? -m_minimalDistances[i]
00407 : -matrix[i][number_of_nodes - 1];
00408 happenings.push_back(std::make_pair(time, i));
00409 }
00410
00411 sort(happenings.begin(), happenings.end(), HappeningComparator());
00412
00413 return happenings;
00414 }
00415