causal_graph.cpp
Go to the documentation of this file.
00001 /* Computes the levels of the variables and returns an ordering of the variables 
00002  * with respect to their levels, beginning with the lowest-level variable.
00003  *
00004  * The new order does not contain any variables that are unimportant for the 
00005  * problem, i.e. variables that don't occur in the goal and don't influence 
00006  * important variables (== there is no path in the causal graph from this variable
00007  * through an important variable to the goal).
00008  * 
00009  * The constructor takes variables and operators and constructs a graph such that
00010  * there is a weighted edge from a variable A to a variable B with weight n+m if 
00011  * there are n operators that have A as prevail condition or postcondition or 
00012  * effect condition for B and that have B as postcondition, and if there are 
00013  * m axioms that have A as condition and B as effect. 
00014  * This graph is used for calculating strongly connected components (using "scc")
00015  * wich are returned in order (lowest-level component first).
00016  * In each scc with more than one variable cycles are then eliminated by 
00017  * succesivly taking out edges with minimal weight (in max_dag), returning a 
00018  * variable order.
00019  * Last, unimportant variables are identified and eliminated from the new order,
00020  * which is returned when "get_variable_ordering" is called.
00021  * Note: The causal graph will still contain the unimportant vars, but they are 
00022  * suppressed in the input for the search programm.
00023  */
00024 
00025 #include "causal_graph.h"
00026 #include "max_dag.h"
00027 #include "operator.h"
00028 #include "axiom.h"
00029 #include "scc.h"
00030 #include "variable.h"
00031 
00032 #include <iostream>
00033 #include <cassert>
00034 using namespace std;
00035 
00036 bool g_do_not_prune_variables = false;
00037 
00038 void CausalGraph::weigh_graph_from_ops(const vector<Variable *> &,
00039         const vector<Operator> &operators, const vector<pair<Variable *, int> >&)
00040 {
00041     for(int i = 0; i < operators.size(); i++) {
00042         //    cout << i << "th of " << operators.size()-1 << " operators: "
00043         //      << operators[i].get_name() << endl;
00044         const vector<Operator::Prevail> &prevail_start =
00045             operators[i].get_prevail_start();
00046         const vector<Operator::Prevail> &prevail_overall =
00047             operators[i].get_prevail_overall();
00048         const vector<Operator::Prevail> &prevail_end =
00049             operators[i].get_prevail_end();
00050         const vector<Operator::PrePost> &pre_post_start =
00051             operators[i].get_pre_post_start();
00052         const vector<Operator::PrePost> &pre_post_end =
00053             operators[i].get_pre_post_end();
00054         const vector<Operator::NumericalEffect> &numerical_effs_start =
00055             operators[i].get_numerical_effs_start();
00056         const vector<Operator::NumericalEffect> &numerical_effs_end =
00057             operators[i].get_numerical_effs_end();
00058         vector<Variable *> source_vars;
00059         for(int j = 0; j < prevail_start.size(); j++)
00060             source_vars.push_back(prevail_start[j].var);
00061         for(int j = 0; j < prevail_overall.size(); j++)
00062             source_vars.push_back(prevail_overall[j].var);
00063         for(int j = 0; j < prevail_end.size(); j++)
00064             source_vars.push_back(prevail_end[j].var);
00065         for(int j = 0; j < pre_post_start.size(); j++)
00066             //if(pre_post_start[j].pre != -1)
00067             source_vars.push_back(pre_post_start[j].var);
00068         for(int j = 0; j < pre_post_end.size(); j++)
00069             //if(pre_post_end[j].pre != -1)
00070             source_vars.push_back(pre_post_end[j].var);
00071 
00072         for(int k = 0; k < pre_post_start.size(); k++) {
00073             Variable *curr_target = pre_post_start[k].var;
00074             if(pre_post_start[k].is_conditional_effect) {
00075                 for(int l = 0; l < pre_post_start[k].effect_conds_start.size(); l++)
00076                     source_vars.push_back(pre_post_start[k].effect_conds_start[l].var);
00077                 for(int l = 0; l < pre_post_start[k].effect_conds_overall.size(); l++)
00078                     source_vars.push_back(pre_post_start[k].effect_conds_overall[l].var);
00079                 for(int l = 0; l < pre_post_start[k].effect_conds_end.size(); l++)
00080                     source_vars.push_back(pre_post_start[k].effect_conds_end[l].var);
00081             }
00082             for(int j = 0; j < source_vars.size(); j++) {
00083                 Variable *curr_source = source_vars[j];
00084                 count(curr_source, curr_target);
00085             }
00086             if(pre_post_start[k].is_conditional_effect) {
00087                 source_vars.erase(source_vars.end()
00088                         - pre_post_start[k].effect_conds_start.size()
00089                         - pre_post_start[k].effect_conds_overall.size()
00090                         - pre_post_start[k].effect_conds_end.size(), source_vars.end());
00091             }
00092         }
00093         for(int k = 0; k < pre_post_end.size(); k++) {
00094             Variable *curr_target = pre_post_end[k].var;
00095             if(pre_post_end[k].is_conditional_effect) {
00096                 for(int l = 0; l < pre_post_end[k].effect_conds_start.size(); l++)
00097                     source_vars.push_back(pre_post_end[k].effect_conds_start[l].var);
00098                 for(int l = 0; l < pre_post_end[k].effect_conds_overall.size(); l++)
00099                     source_vars.push_back(pre_post_end[k].effect_conds_overall[l].var);
00100                 for(int l = 0; l < pre_post_end[k].effect_conds_end.size(); l++)
00101                     source_vars.push_back(pre_post_end[k].effect_conds_end[l].var);
00102             }
00103             for(int j = 0; j < source_vars.size(); j++) {
00104                 Variable *curr_source = source_vars[j];
00105                 count(curr_source, curr_target);
00106             }
00107 
00108             if(pre_post_end[k].is_conditional_effect) {
00109                 source_vars.erase(source_vars.end()
00110                         - pre_post_end[k].effect_conds_start.size()
00111                         - pre_post_end[k].effect_conds_overall.size()
00112                         - pre_post_end[k].effect_conds_end.size(), source_vars.end());
00113             }
00114         }
00115         for(int k = 0; k < numerical_effs_start.size(); k++) {
00116             Variable *curr_target = numerical_effs_start[k].var;
00117             if(numerical_effs_start[k].is_conditional_effect) {
00118                 for(int l = 0; l < numerical_effs_start[k].effect_conds_start.size(); l++)
00119                     source_vars.push_back(numerical_effs_start[k].effect_conds_start[l].var);
00120                 for(int l = 0; l < numerical_effs_start[k].effect_conds_overall.size(); l++)
00121                     source_vars.push_back(numerical_effs_start[k].effect_conds_overall[l].var);
00122                 for(int l = 0; l < numerical_effs_start[k].effect_conds_end.size(); l++)
00123                     source_vars.push_back(numerical_effs_start[k].effect_conds_end[l].var);
00124             }
00125             source_vars.push_back(numerical_effs_start[k].foperand);
00126             for(int j = 0; j < source_vars.size(); j++) {
00127                 Variable *curr_source = source_vars[j];
00128                 count(curr_source, curr_target);
00129             }
00130             source_vars.pop_back();//foperand
00131             if(numerical_effs_start[k].is_conditional_effect)
00132                 source_vars.erase(source_vars.end()
00133                         - numerical_effs_start[k].effect_conds_start.size()
00134                         - numerical_effs_start[k].effect_conds_overall.size()
00135                         - numerical_effs_start[k].effect_conds_end.size(),
00136                         source_vars.end());
00137         }
00138         for(int k = 0; k < numerical_effs_end.size(); k++) {
00139             Variable *curr_target = numerical_effs_end[k].var;
00140             if(numerical_effs_end[k].is_conditional_effect) {
00141                 for(int l = 0; l < numerical_effs_end[k].effect_conds_start.size(); l++)
00142                     source_vars.push_back(numerical_effs_end[k].effect_conds_start[l].var);
00143                 for(int l = 0; l < numerical_effs_end[k].effect_conds_overall.size(); l++)
00144                     source_vars.push_back(numerical_effs_end[k].effect_conds_overall[l].var);
00145                 for(int l = 0; l < numerical_effs_end[k].effect_conds_end.size(); l++)
00146                     source_vars.push_back(numerical_effs_end[k].effect_conds_end[l].var);
00147             }
00148             source_vars.push_back(numerical_effs_end[k].foperand);
00149 
00150             for(int j = 0; j < source_vars.size(); j++) {
00151                 Variable *curr_source = source_vars[j];
00152                 count(curr_source, curr_target);
00153             }
00154             source_vars.pop_back();//foperand
00155             if(numerical_effs_end[k].is_conditional_effect)
00156                 source_vars.erase(source_vars.end()
00157                         - numerical_effs_end[k].effect_conds_start.size()
00158                         - numerical_effs_end[k].effect_conds_overall.size()
00159                         - numerical_effs_end[k].effect_conds_end.size(), source_vars.end());
00160         }
00161     }
00162 }
00163 
00164 void CausalGraph::count(Variable *curr_source, Variable *curr_target) {
00165     WeightedSuccessors &weighted_succ = weighted_graph[curr_source];
00166     if(predecessor_graph.count(curr_target) == 0)
00167         predecessor_graph[curr_target] = Predecessors();
00168     if(curr_source != curr_target) {
00169         if(weighted_succ.find(curr_target) != weighted_succ.end()) {
00170             weighted_succ[curr_target]++;
00171             predecessor_graph[curr_target][curr_source]++;
00172         } else {
00173             weighted_succ[curr_target] = 1;
00174             predecessor_graph[curr_target][curr_source] = 1;
00175         }
00176         //    cout << "weighing edge from " << curr_source->get_name() << " to "
00177         //      << curr_target->get_name() << endl;
00178     }
00179 }
00180 
00181 void CausalGraph::weigh_graph_from_axioms_rel(const vector<Variable *> &,
00182         const vector<Axiom_relational> &axioms_rel,
00183         const vector<pair<Variable *, int> >&) {
00184     for(int i = 0; i < axioms_rel.size(); i++) {
00185         //    cout << i << "th of " << axioms_rel.size()-1 << " relational axioms: "
00186         //      << endl;
00187         const vector<Condition> &conds = axioms_rel[i].get_conditions();
00188         vector<Variable *> source_vars;
00189         for(int j = 0; j < conds.size(); j++)
00190             source_vars.push_back(conds[j].var);
00191 
00192         for(int j = 0; j < source_vars.size(); j++) {
00193             Variable *curr_source = source_vars[j];
00194             // only one target var: the effect var of axiom[i]
00195             Variable *curr_target = axioms_rel[i].get_effect_var();
00196             count(curr_source, curr_target);
00197         }
00198     }
00199 }
00200 
00201 void CausalGraph::weigh_graph_from_axioms_func(const vector<Variable *> &,
00202         const vector<Axiom_functional> &axioms_func,
00203         const vector<pair<Variable *, int> >&) {
00204     for(int i = 0; i < axioms_func.size(); i++) {
00205         //    cout << i << "th of " << axioms_func.size()-1 << " functional axioms: "
00206         //      << endl;
00207         count(axioms_func[i].get_left_var(), axioms_func[i].get_effect_var());
00208         count(axioms_func[i].get_right_var(), axioms_func[i].get_effect_var());
00209     }
00210 }
00211 
00212 CausalGraph::CausalGraph(const vector<Variable *> &the_variables,
00213         const vector<Operator> &the_operators,
00214         const vector<Axiom_relational> &the_axioms_rel,
00215         const vector<Axiom_functional> &the_axioms_func,
00216         const vector<pair<Variable *, int> > &the_goals) :
00217     variables(the_variables), operators(the_operators),
00218     axioms_rel(the_axioms_rel), axioms_func(the_axioms_func),
00219     goals(the_goals), acyclic(false) {
00220 
00221         for(int i = 0; i < variables.size(); i++)
00222             weighted_graph[variables[i]] = WeightedSuccessors();
00223         weigh_graph_from_ops(variables, operators, goals);
00224         weigh_graph_from_axioms_rel(variables, axioms_rel, goals);
00225         weigh_graph_from_axioms_func(variables, axioms_func, goals);
00226         //dump();
00227 
00228         Partition sccs;
00229         get_strongly_connected_components(sccs);
00230 
00231         cout << "The causal graph is " << (sccs.size() == variables.size() ? ""
00232                 : "not ") << "acyclic." << endl;
00233         /*
00234            if (sccs.size() != variables.size()) {
00235            cout << "Components: " << endl;
00236            for(int i = 0; i < sccs.size(); i++) {
00237            for(int j = 0; j < sccs[i].size(); j++)
00238            cout << " " << sccs[i][j]->get_name();
00239            cout << endl;
00240            }
00241            }
00242            */
00243         calculate_pseudo_sort();
00244         //calculate_topological_pseudo_sort(sccs);
00245         calculate_important_vars();
00246 
00247         //   cout << "new variable order: ";
00248         //   for(int i = 0; i < ordering.size(); i++)
00249         //     cout << ordering[i]->get_name()<<" - "; 
00250         //   cout << endl;
00251     }
00252 
00253 void CausalGraph::calculate_pseudo_sort() {
00254     ordering = variables;
00255 }
00256 
00257 void CausalGraph::calculate_topological_pseudo_sort(const Partition &sccs) {
00258     map<Variable *, int> goal_map;
00259     for(int i = 0; i < goals.size(); i++)
00260         goal_map[goals[i].first] = goals[i].second;
00261     for(int scc_no = 0; scc_no < sccs.size(); scc_no++) {
00262         const vector<Variable *> &curr_scc = sccs[scc_no];
00263         if(curr_scc.size()> 1) {
00264             // component needs to be turned into acyclic subgraph  
00265 
00266             // Map variables to indices in the strongly connected component.
00267             map<Variable *, int> variableToIndex;
00268             for(int i = 0; i < curr_scc.size(); i++)
00269                 variableToIndex[curr_scc[i]] = i;
00270 
00271             // Compute subgraph induced by curr_scc and convert the successor
00272             // representation from a map to a vector.
00273             vector<vector<pair<int, int> > > subgraph;
00274             for(int i = 0; i < curr_scc.size(); i++) {
00275                 // For each variable in component only list edges inside component.
00276                 WeightedSuccessors &all_edges = weighted_graph[curr_scc[i]];
00277                 vector<pair<int, int> > subgraph_edges;
00278                 for(WeightedSuccessors::const_iterator curr = all_edges.begin(); curr
00279                         != all_edges.end(); ++curr) {
00280                     Variable *target = curr->first;
00281                     int cost = curr->second;
00282                     map<Variable *, int>::iterator index_it = variableToIndex.find(target);
00283                     if(index_it != variableToIndex.end()) {
00284                         int new_index = index_it->second;
00285                         if(goal_map.find(target) != goal_map.end()) {
00286                             //FIXME: soll das so bleiben? (Zahl taucht in max_dag auf)
00287                             // target is goal
00288                             subgraph_edges.push_back(make_pair(new_index, 100000 + cost));
00289                         }
00290                         subgraph_edges.push_back(make_pair(new_index, cost));
00291                     }
00292                 }
00293                 subgraph.push_back(subgraph_edges);
00294             }
00295 
00296             vector<int> order = MaxDAG(subgraph).get_result();
00297             for(int i = 0; i < order.size(); i++) {
00298                 ordering.push_back(curr_scc[order[i]]);
00299             }
00300         } else {
00301             ordering.push_back(curr_scc[0]);
00302         }
00303     }
00304 }
00305 
00306 void CausalGraph::get_strongly_connected_components(Partition &result) {
00307     map<Variable *, int> variableToIndex;
00308     for(int i = 0; i < variables.size(); i++)
00309         variableToIndex[variables[i]] = i;
00310 
00311     vector<vector<int> > unweighted_graph;
00312     unweighted_graph.resize(variables.size());
00313     for(WeightedGraph::const_iterator it = weighted_graph.begin(); it
00314             != weighted_graph.end(); ++it) {
00315         int index = variableToIndex[it->first];
00316         vector<int> &succ = unweighted_graph[index];
00317         const WeightedSuccessors &weighted_succ = it->second;
00318         for(WeightedSuccessors::const_iterator it = weighted_succ.begin(); it
00319                 != weighted_succ.end(); ++it)
00320             succ.push_back(variableToIndex[it->first]);
00321     }
00322 
00323     vector<vector<int> > int_result = SCC(unweighted_graph).get_result();
00324 
00325     result.clear();
00326     for(int i = 0; i < int_result.size(); i++) {
00327         vector<Variable *> component;
00328         for(int j = 0; j < int_result[i].size(); j++)
00329             component.push_back(variables[int_result[i][j]]);
00330         result.push_back(component);
00331     }
00332 }
00333 void CausalGraph::calculate_important_vars() {
00334     //variables occuring in a duration constrain are necessary!
00335     for(int i = 0; i < variables.size(); i++) {
00336         if(variables[i]->is_used_in_duration_condition()) {
00337             variables[i]->set_necessary();
00338             dfs(variables[i]);
00339         }
00340     }
00341     //variables occuring in a module are necessary!
00342     for(int i = 0; i < variables.size(); ++i) {
00343         if (variables[i]->is_module()) {
00344             variables[i]->set_necessary();
00345             dfs(variables[i]);
00346         }
00347     }
00348     for(int i = 0; i < goals.size(); i++) {
00349         if(!goals[i].first->is_necessary()) {
00350             //cout << "var " << goals[i].first->get_name() <<" is directly neccessary." 
00351             // << endl;
00352             goals[i].first->set_necessary();
00353             dfs(goals[i].first);
00354         }
00355     }
00356     // change ordering to leave out unimportant vars
00357     vector<Variable *> new_ordering;
00358     int old_size = ordering.size();
00359     for(int i = 0; i < old_size; i++)
00360         if(ordering[i]->is_necessary() || g_do_not_prune_variables)
00361             new_ordering.push_back(ordering[i]);
00362         else {
00363             cout << "variable " << ordering[i]->get_name() << " is not necessary!" << endl;
00364         }
00365     ordering = new_ordering;
00366     for(int i = 0; i < ordering.size(); i++) {
00367         ordering[i]->set_level(i);
00368     }
00369     cout << ordering.size() << " variables of " << old_size << " necessary"
00370         << endl;
00371 }
00372 
00373 void CausalGraph::dfs(Variable *from) {
00374     for(Predecessors::iterator pred = predecessor_graph[from].begin(); pred
00375             != predecessor_graph[from].end(); ++pred) {
00376         Variable* curr_predecessor = pred->first;
00377         if(!curr_predecessor->is_necessary()) {
00378             curr_predecessor->set_necessary();
00379             //cout << "var " << curr_predecessor->get_name() <<" is neccessary." << endl;
00380             dfs(curr_predecessor);
00381         }
00382     }
00383 }
00384 
00385 const vector<Variable *> &CausalGraph::get_variable_ordering() const {
00386     return ordering;
00387 }
00388 
00389 bool CausalGraph::is_acyclic() const {
00390     return acyclic;
00391 }
00392 
00393 void CausalGraph::dump() const {
00394     for(WeightedGraph::const_iterator source = weighted_graph.begin(); source
00395             != weighted_graph.end(); ++source) {
00396         cout << "dependent on var " << source->first->get_name() << ": " << endl;
00397         const WeightedSuccessors &curr = source->second;
00398         for(WeightedSuccessors::const_iterator it = curr.begin(); it != curr.end(); ++it) {
00399             cout << "  [" << it->first->get_name() << ", " << it->second << "]"
00400                 << endl;
00401             //assert(predecessor_graph[it->first][source->first] == it->second); 
00402         }
00403     }
00404     for(PredecessorGraph::const_iterator source = predecessor_graph.begin(); source
00405             != predecessor_graph.end(); ++source) {
00406         cout << "var " << source->first->get_name() << " is dependent of: " << endl;
00407         const Predecessors &curr = source->second;
00408         for(Predecessors::const_iterator it = curr.begin(); it != curr.end(); ++it)
00409             cout << "  [" << it->first->get_name() << ", " << it->second << "]"
00410                 << endl;
00411     }
00412 }
00413 void CausalGraph::generate_cpp_input(ostream &outfile,
00414         const vector<Variable *> & ordered_vars) const
00415 {
00416     vector<WeightedSuccessors *> succs; // will be ordered like ordered_vars
00417     vector<int> number_of_succ; // will be ordered like ordered_vars
00418     succs.resize(ordered_vars.size());
00419     number_of_succ.resize(ordered_vars.size());
00420     for(WeightedGraph::const_iterator source = weighted_graph.begin(); source
00421             != weighted_graph.end(); ++source) {
00422         Variable * source_var = source->first;
00423         if(source_var->get_level() != -1) {
00424             // source variable influences others 
00425             WeightedSuccessors &curr = (WeightedSuccessors &) source->second;
00426             succs[source_var->get_level()] = &curr;
00427             // count number of influenced vars
00428             int num = 0;
00429             for(WeightedSuccessors::const_iterator it = curr.begin(); it
00430                     != curr.end(); ++it)
00431                 if(it->first->get_level() != -1
00432                         // && it->first->get_level() > source_var->get_level()
00433                   )
00434                     num++;
00435             number_of_succ[source_var->get_level()] = num;
00436         }
00437     }
00438     for(int i = 0; i < ordered_vars.size(); i++) {
00439         WeightedSuccessors *curr = succs[i];
00440         // print number of variables influenced by variable i
00441         outfile << number_of_succ[i] << endl;
00442         for(WeightedSuccessors::const_iterator it = curr->begin(); it
00443                 != curr->end(); ++it) {
00444             if(it->first->get_level() != -1
00445                     // && it->first->get_level() > ordered_vars[i]->get_level()
00446               )
00447                 // the variable it->first is important and influenced by variable i
00448                 // print level
00449                 outfile << it->first->get_level() << endl;
00450         }
00451     }
00452 }
00453 


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