scheduler.cpp
Go to the documentation of this file.
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 // set the maximum distance between from and to.
00030 void SimpleTemporalProblem::setDistance(int from, int to, double distance)
00031 {
00032     //    cout << "from:" << from << ", to:" << to << endl;
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 // set the interval into which value(to)-value(from) has to fall
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 // set the exact value which value(to)-value(from) must have
00049 void SimpleTemporalProblem::setSingletonInterval(int from, int to,
00050         double lowerAndUpper)
00051 {
00052     setInterval(from, to, lowerAndUpper, lowerAndUpper);
00053 }
00054 
00055 // set the interval into which value(to)-value(from) has to fall,
00056 // with the assumption that the interval is open to the right.
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 // solve the STP using the Floyd-Warshall algorithm with running time O(n^3)
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                     // update
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 // check if solution is valid
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 // return the maximal distance from X0 to any node in the network.
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 // dump problem
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;//variable_names[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;//variable_names[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 // dump problem
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;//variable_names[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;//variable_names[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 // dump solution
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 


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06