domain_transition_graph_symb.cpp
Go to the documentation of this file.
00001 /* unary operators are constructed in "build_DTGs" by calling
00002  * "addTransition" with the appropriate arguments: for every
00003  * pre-postcondition pair of an operator, an edge in the
00004  * DTG is built between the corresponding values in the dtg of the
00005  * variable, annotated with all prevail conditions and preconditions and
00006  * effect conditions of that postcondition.
00007  */
00008 
00009 #include "domain_transition_graph_symb.h"
00010 #include "operator.h"
00011 #include "axiom.h"
00012 #include "variable.h"
00013 #include "scc.h"
00014 
00015 #include <algorithm>
00016 #include <cassert>
00017 #include <iostream>
00018 using namespace std;
00019 
00020 DomainTransitionGraphSymb::DomainTransitionGraphSymb(const Variable &var) {
00021     //cout << "creating symbolical DTG for " << var.get_name() << endl;
00022     int range = var.get_range();
00023     if(range == -1) {
00024         range = 0;
00025     }
00026     vertices.clear();
00027     vertices.resize(range);
00028     level = var.get_level();
00029     assert(level != -1);
00030 }
00031 
00032 void DomainTransitionGraphSymb::addTransition(int from, int to,
00033         const Operator &op, int op_index, trans_type type,
00034         vector<Variable *> variables)
00035 {
00036     class self_fulfilled_ {
00037         public:
00038             bool operator()(const vector<Operator::PrePost> &pre_post_start,
00039                     const Variable *var, const int &val) {
00040                 for(unsigned int j = 0; j < pre_post_start.size(); j++)
00041                     if(pre_post_start[j].var == var && pre_post_start[j].post == val)
00042                         return true;
00043                 return false;
00044             }
00045     } self_fulfilled;
00046 
00047     Transition trans(to, op_index, type);
00048     SetEdgeCondition &cond = trans.set_condition;
00049     const vector<Operator::Prevail> &prevail_start = op.get_prevail_start();
00050     const vector<Operator::Prevail> &prevail_overall = op.get_prevail_overall();
00051     const vector<Operator::Prevail> &prevail_end = op.get_prevail_end();
00052     const vector<Operator::PrePost> &pre_post_start = op.get_pre_post_start();
00053     const vector<Operator::PrePost> &pre_post_end = op.get_pre_post_end();
00054 
00055     assert(type == compressed || type == end || type == start);
00056 
00057     //  if(type == compressed) {
00058     // insert all at-start conditions
00059     for(int i = 0; i < prevail_start.size(); i++) {
00060         cond.insert(std::tr1::make_tuple(prevail_start[i].var, prevail_start[i].prev, start_cond));
00061     }
00062     // insert all overall conditions if not satiesfied by an at-start effect of the same operator
00063     for(int i = 0; i < prevail_overall.size(); i++) {
00064         if(!self_fulfilled(pre_post_start, prevail_overall[i].var,
00065                     prevail_overall[i].prev)) {
00066             cond.insert(std::tr1::make_tuple(prevail_overall[i].var, prevail_overall[i].prev, overall_cond));
00067         }
00068     }
00069 
00070     // insert all end conditions if not satiesfied by an at-start effect of the same operator
00071     for(int i = 0; i < prevail_end.size(); i++) {
00072         if(!self_fulfilled(pre_post_start, prevail_end[i].var, prevail_end[i].prev)) {
00073             cond.insert(std::tr1::make_tuple(prevail_end[i].var, prevail_end[i].prev, end_cond));
00074         }
00075     }
00076     //  }
00077     //  if(type == compressed) {
00078     // for each start effect, if the effect affects the Variable of this DTG, insert its SAS-Precondition,
00079     // if it affects another variable, add its start effect conditions.
00080     for(int i = 0; i < pre_post_start.size(); i++) {
00081         if(pre_post_start[i].var->get_level() != level && pre_post_start[i].pre
00082                 != -1) {
00083             cond.insert(std::tr1::make_tuple(pre_post_start[i].var, pre_post_start[i].pre, start_cond));
00084         } else if(pre_post_start[i].var->get_level() == level
00085                 && pre_post_start[i].is_conditional_effect) {
00086             for(int j = 0; j < pre_post_start[i].effect_conds_start.size(); j++)
00087                 cond.insert(std::tr1::make_tuple(pre_post_start[i].effect_conds_start[j].var,
00088                             pre_post_start[i].effect_conds_start[j].cond, start_cond));
00089         }
00090     }
00091 
00092     // for each end effect, if the effect affects the Variable of this DTG, insert its SAS-Precondition,
00093     // if it affects another variable, add its end effect conditions (if they are not satiesfied by an
00094     // start effect of the same operator).
00095     for(int i = 0; i < pre_post_end.size(); i++) {
00096         if(pre_post_end[i].var->get_level() != level && pre_post_end[i].pre != -1) {
00097             if(!self_fulfilled(pre_post_start, pre_post_end[i].var,
00098                         pre_post_end[i].pre)) {
00099                 cond.insert(std::tr1::make_tuple(pre_post_end[i].var, pre_post_end[i].pre, end_cond));
00100             }
00101         } else if(pre_post_end[i].var->get_level() == level
00102                 && pre_post_end[i].is_conditional_effect) {
00103             for(int j = 0; j < pre_post_end[i].effect_conds_end.size(); j++) {
00104                 if(!self_fulfilled(pre_post_start,
00105                         pre_post_end[i].effect_conds_end[j].var,
00106                         pre_post_end[i].effect_conds_end[j].cond)) {
00107                     cond.insert(std::tr1::make_tuple(
00108                             pre_post_end[i].effect_conds_end[j].var,
00109                             pre_post_end[i].effect_conds_end[j].cond, end_cond));
00110                 }
00111             }
00112         }
00113 
00114     }
00115     //write from set to vector
00116     EdgeCondition &cond_vec = trans.condition;
00117     for(SetEdgeCondition::iterator it = cond.begin(); it != cond.end(); ++it) {
00118         //cout << "writing [" << (*it).first->get_level() << "," << (*it).second << "]" << endl;
00119         cond_vec.push_back(*it);
00120     }
00121 
00122     trans.duration = op.get_duration_cond();
00123     vertices[from].push_back(trans);
00124 }
00125 
00126 void DomainTransitionGraphSymb::addAxRelTransition(int from, int to,
00127         const Axiom_relational &ax, int ax_index) {
00128     Transition trans(to, ax_index, ax_rel);
00129     EdgeCondition &cond = trans.condition;
00130     const vector<Condition> &ax_conds = ax.get_conditions();
00131     for(int i = 0; i < ax_conds.size(); i++)
00132         if(true) // [cycles]
00133             // if(prevail[i].var->get_level() < level) // [no cycles]
00134             cond.push_back(std::tr1::make_tuple(ax_conds[i].var, ax_conds[i].cond, ax_cond));
00135     vertices[from].push_back(trans);
00136 }
00137 
00138 bool DomainTransitionGraphSymb::Transition::operator<(const Transition &other) const {
00139     if (target != other.target)
00140         return target < other.target;
00141     else if (duration.var != other.duration.var)
00142         return duration.var < other.duration.var;
00143     return (condition.size() < other.condition.size());
00144 }
00145 
00146 void DomainTransitionGraphSymb::Transition::dump() {
00147     cout << "target: " << target << ", dur_var: " << duration.var->get_level()
00148         << endl;
00149     for(int k = 0; k < condition.size(); k++) {
00150         cout << " " << std::tr1::get<0>(condition[k])->get_level() << " : "
00151             << std::tr1::get<1>(condition[k]) << " (" << std::tr1::get<2>(condition[k]) << ")" << endl;
00152     }
00153 }
00154 
00155 void DomainTransitionGraphSymb::finalize() {
00156     for(int i = 0; i < vertices.size(); i++) {
00157 
00158         //    if((level == 6) && (i == 0)) {
00159         //      cout << "before sorting transitions: " << endl;
00160         //      for(int j = 0; j < vertices[i].size(); j++)
00161         //      vertices[i][j].dump();
00162         //    }
00163 
00164         //    for(int j = 0; j < vertices[i].size(); j++) {
00165         //      cout << " " << j << endl;
00166         //      vertices[i][j].dump();
00167         //    }
00168         // For all sources, sort transitions according to targets and condition length
00169         sort(vertices[i].begin(), vertices[i].end());
00170 
00171         vertices[i].erase(unique(vertices[i].begin(), vertices[i].end()),
00172                 vertices[i].end());
00173 
00174         //    if((level == 6) && (i == 0)) {
00175         //      cout << "after sorting transitions: " << endl;
00176         //      for(int j = 0; j < vertices[i].size(); j++)
00177         //      vertices[i][j].dump();
00178         //    }
00179 
00180         // For all transitions, sort conditions (acc. to pointer addresses)
00181         for(int j = 0; j < vertices[i].size(); j++) {
00182             Transition &trans = vertices[i][j];
00183             sort(trans.condition.begin(), trans.condition.end());
00184         }
00185 
00186         //    if((level == 6) && (i == 0)) {
00187         //      cout << "after sorting conditions: " << endl;
00188         //      for(int j = 0; j < vertices[i].size(); j++)
00189         //      vertices[i][j].dump();
00190         //    }
00191 
00192         // Look for dominated transitions
00193         vector<Transition> undominated_trans;
00194         vector<bool> is_dominated;
00195         is_dominated.resize(vertices[i].size(), false);
00196         for(int j = 0; j < vertices[i].size(); j++) {
00197             if(!is_dominated[j]) {
00198                 Transition &trans = vertices[i][j];
00199                 undominated_trans.push_back(trans);
00200                 EdgeCondition &cond = trans.condition;
00201                 int comp = j + 1; // compare transition no. j to no. comp
00202                 // comp is dominated if it has same target and same duration and more conditions
00203                 while(comp < vertices[i].size()) {
00204                     if(is_dominated[comp]) {
00205                         comp++;
00206                         continue;
00207                     }
00208                     Transition &other_trans = vertices[i][comp];
00209                     assert(other_trans.target >= trans.target);
00210                     if(other_trans.target != trans.target)
00211                         break; // transition and all after it have different targets
00212                     if(other_trans.duration.var->get_level()
00213                             != trans.duration.var->get_level())
00214                         break; // transition and all after it have different durations
00215                     else { //domination possible
00216                         if(other_trans.condition.size() < cond.size()) {
00217                             cout << "level: " << level << ", i: " << i << ", j: " << j;
00218                             assert(false);
00219                         }
00220                         if(cond.size() == 0) {
00221                             is_dominated[comp] = true; // comp is dominated
00222                             comp++;
00223                         } else {
00224                             bool same_conditions = true;
00225                             for(int k = 0; k < cond.size(); k++) {
00226                                 bool cond_k = false;
00227                                 for(int l = 0; l < other_trans.condition.size(); l++) {
00228                                     if(std::tr1::get<0>(other_trans.condition[l]) > std::tr1::get<0>(cond[k])) {
00229                                         break; // comp doesn't have this condition, not dominated
00230                                     }
00231                                     if(std::tr1::get<0>(other_trans.condition[l]) == std::tr1::get<0>(cond[k])
00232                                             && std::tr1::get<1>(other_trans.condition[l]) == std::tr1::get<1>(cond[k])) {
00233                                         // FIXME: should we also check the type of the condition at this point?
00234                                         cond_k = true;
00235 
00236                                         break; // comp has this condition, look for next cond
00237                                     }
00238                                 }
00239                                 if(!cond_k) { // comp is not dominated
00240                                     same_conditions = false;
00241                                     break;
00242                                 }
00243                             }
00244                             is_dominated[comp] = same_conditions;
00245                             comp++;
00246                         }
00247                     }
00248                 }
00249             }
00250         }
00251 
00252         vertices[i].swap(undominated_trans);
00253 
00254         //    if((level == 6) && (i == 0)) {
00255         //      cout << "after searching for dominated transitions: " << endl;
00256         //      for(int j = 0; j < vertices[i].size(); j++)
00257         //      vertices[i][j].dump();
00258         //    }
00259 
00260     }
00261 }
00262 
00263 bool DomainTransitionGraphSymb::is_strongly_connected() const {
00264     vector<vector<int> > easy_graph;
00265     for(int i = 0; i < vertices.size(); i++) {
00266         vector<int> empty_vector;
00267         easy_graph.push_back(empty_vector);
00268         for(int j = 0; j < vertices[i].size(); j++) {
00269             const Transition &trans = vertices[i][j];
00270             easy_graph[i].push_back(trans.target);
00271         }
00272     }
00273     vector<vector<int> > sccs = SCC(easy_graph).get_result();
00274     //  cout << "easy graph sccs for var " << level << endl;
00275     //   for(int i = 0; i < sccs.size(); i++) {
00276     //     for(int j = 0; j < sccs[i].size(); j++)
00277     //       cout << " " << sccs[i][j];
00278     //     cout << endl;
00279     //   }
00280     bool connected = false;
00281     if(sccs.size() == 1) {
00282         connected = true;
00283         //cout <<"is strongly connected" << endl;
00284     }
00285     //else cout << "not strongly connected" << endl;
00286     return connected;
00287 }
00288 
00289 void DomainTransitionGraphSymb::dump() const {
00290     cout << "Symbolical DTG!" << endl;
00291     for(int i = 0; i < vertices.size(); i++) {
00292         cout << "  From value " << i << ":" << endl;
00293         for(int j = 0; j < vertices[i].size(); j++) {
00294             const Transition &trans = vertices[i][j];
00295             cout << "    " << "To value " << trans.target << endl;
00296             if(trans.type == start || trans.type == end || trans.type == compressed)
00297                 cout << "     duration " << trans.duration.op << " "
00298                     << trans.duration.var->get_level() << endl;
00299             else
00300                 cout << "     " << "axiom" << endl;
00301             for(int k = 0; k < trans.condition.size(); k++)
00302                 cout << "      if " << std::tr1::get<0>(trans.condition[k])->get_level() << " = "
00303                     << std::tr1::get<1>(trans.condition[k]) <<  " (" << std::tr1::get<2>(trans.condition[k]) << ")" << endl;
00304         }
00305     }
00306 }
00307 
00308 void DomainTransitionGraphSymb::generate_cpp_input(ostream &outfile) const {
00309     //outfile << vertices.size() << endl; // the variable's range
00310     for(int i = 0; i < vertices.size(); i++) {
00311         outfile << vertices[i].size() << endl; // number of transitions from this value
00312         for(int j = 0; j < vertices[i].size(); j++) {
00313             const Transition &trans = vertices[i][j];
00314             outfile << trans.target << endl; // target of transition
00315             outfile << trans.op << endl; // operator doing the transition
00316             //duration:
00317             if(trans.type == compressed)
00318                 outfile << "c" << endl;
00319             else if(trans.type == start)
00320                 outfile << "s" << endl;
00321             else if(trans.type == end)
00322                 outfile << "e" << endl;
00323             else {
00324                 assert(trans.type==ax_rel);
00325                 outfile << "a" << endl;
00326             }
00327             if(trans.type == start || trans.type == end || trans.type == compressed)
00328                 outfile << trans.duration.op << " " << trans.duration.var->get_level()
00329                     << endl;
00330             // calculate number of important prevail conditions
00331             int number = 0;
00332             for(int k = 0; k < trans.condition.size(); k++)
00333                 if(std::tr1::get<0>(trans.condition[k])->get_level() != -1)
00334                     number++;
00335             outfile << number << endl;
00336             for(int k = 0; k < trans.condition.size(); k++)
00337                 if(std::tr1::get<0>(trans.condition[k])->get_level() != -1)
00338                     outfile << std::tr1::get<0>(trans.condition[k])->get_level() << " "
00339                         << std::tr1::get<1>(trans.condition[k]) << " " << std::tr1::get<2>(trans.condition[k]) << endl; // condition: var, val
00340         }
00341     }
00342 }
00343 


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