00001
00002
00003
00004
00005
00006
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
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
00058
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
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
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
00078
00079
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
00093
00094
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
00116 EdgeCondition &cond_vec = trans.condition;
00117 for(SetEdgeCondition::iterator it = cond.begin(); it != cond.end(); ++it) {
00118
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)
00133
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
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
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
00175
00176
00177
00178
00179
00180
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
00187
00188
00189
00190
00191
00192
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;
00202
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;
00212 if(other_trans.duration.var->get_level()
00213 != trans.duration.var->get_level())
00214 break;
00215 else {
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;
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;
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
00234 cond_k = true;
00235
00236 break;
00237 }
00238 }
00239 if(!cond_k) {
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
00255
00256
00257
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
00275
00276
00277
00278
00279
00280 bool connected = false;
00281 if(sccs.size() == 1) {
00282 connected = true;
00283
00284 }
00285
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
00310 for(int i = 0; i < vertices.size(); i++) {
00311 outfile << vertices[i].size() << endl;
00312 for(int j = 0; j < vertices[i].size(); j++) {
00313 const Transition &trans = vertices[i][j];
00314 outfile << trans.target << endl;
00315 outfile << trans.op << endl;
00316
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
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;
00340 }
00341 }
00342 }
00343