Module: ppl/ppl Branch: master Commit: 7da6c43b438cf0948998e17eb6e8077fb39a7b1d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7da6c43b438cf... Author: Enea Zaffanella <zaffanella@cs.unipr.it> Date: Wed Feb 17 12:47:08 2010 +0100 Added method PIP_Problem::print_solution(). The new method exploits added virtual method PIP_Tree_Node::print_tree(). Implementation is based on code from the many display_solution() helper functions that are currently spread in the tests. --- src/PIP_Problem.cc | 26 ++++++++++++ src/PIP_Problem.defs.hh | 6 ++- src/PIP_Tree.cc | 99 +++++++++++++++++++++++++++++++++++++++++++++++ src/PIP_Tree.defs.hh | 51 ++++++++++++++++++++++++- 4 files changed, 179 insertions(+), 3 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 07248d4..bdefa78 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -639,3 +639,29 @@ PPL::memory_size_type PPL::PIP_Problem::total_memory_in_bytes() const { return sizeof(*this) + external_memory_in_bytes(); } + +void +PPL::PIP_Problem::print_solution(std::ostream& s, unsigned indent) const { + switch (status) { + + case UNSATISFIABLE: + PPL_ASSERT(current_solution == 0); + PIP_Tree_Node::indent_and_print(s, indent, "_|_\n"); + break; + + case OPTIMIZED: + PPL_ASSERT(current_solution); + PPL_ASSERT(internal_space_dim == external_space_dim); + current_solution->print_tree(s, indent, + internal_space_dim, + // NOTE: first_art_param == space_dim. + internal_space_dim, + parameters); + break; + + case PARTIALLY_SATISFIABLE: + throw std::domain_error("PIP_Problem::print_solution():\n" + "the PIP problem has not been solved."); + } +} + diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 459a309..b4c6081 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -319,8 +319,7 @@ public: (resp., the parameter variables) is strictly greater than \p dim. */ template <typename In> - PIP_Problem(dimension_type dim, - In first, In last, + PIP_Problem(dimension_type dim, In first, In last, const Variables_Set& p_vars); //! Ordinary copy-constructor. @@ -456,6 +455,9 @@ public: //! Checks if all the invariants are satisfied. bool OK() const; + //! Prints on \p s the solution computed for \p *this. + void print_solution(std::ostream& s, unsigned indent = 0) const; + PPL_OUTPUT_DECLARATIONS /*! \brief diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 60b8fbf..4f08797 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -2470,4 +2470,103 @@ PIP_Solution_Node::total_memory_in_bytes() const { return sizeof(*this) + external_memory_in_bytes(); } +void +PIP_Tree_Node::indent_and_print(std::ostream& s, + const unsigned indent, + const char* str) { + s << std::setw(2*indent) << "" << str; +} + +void +PIP_Tree_Node::print_tree(std::ostream& s, + const unsigned indent, + const dimension_type space_dim, + dimension_type first_art_dim, + const Variables_Set& params) const { + used(space_dim); + used(params); + + using namespace IO_Operators; + + // Print artificial parameters. + for (Artificial_Parameter_Sequence::const_iterator + api = art_parameter_begin(), + api_end = art_parameter_end(); api != api_end; ++api) { + indent_and_print(s, indent, "Parameter "); + s << Variable(first_art_dim) << " = " << *api << "\n"; + ++first_art_dim; + } + + // Print constraints, if any. + if (!constraints_.empty()) { + indent_and_print(s, indent, "if "); + + Constraint_System::const_iterator + ci = constraints_.begin(), + ci_end = constraints_.end(); + PPL_ASSERT(ci != ci_end); + s << *ci; + for (++ci; ci != ci_end; ++ci) + s << " and " << *ci; + + s << " then\n"; + } +} + +void +PIP_Decision_Node::print_tree(std::ostream& s, unsigned indent, + const dimension_type space_dim, + const dimension_type first_art_dim, + const Variables_Set& params) const { + // First print info common to decision and solution nodes. + PIP_Tree_Node::print_tree(s, indent, space_dim, first_art_dim, params); + + // Then print info specific of decision nodes. + dimension_type child_first_art_dim = first_art_dim + art_parameter_count(); + + if (true_child) + true_child->print_tree(s, indent+1, space_dim, + child_first_art_dim, params); + else + indent_and_print(s, indent+1, "_|_\n"); + + indent_and_print(s, indent, "else\n"); + + if (false_child) + false_child->print_tree(s, indent+1, space_dim, + child_first_art_dim, params); + else + indent_and_print(s, indent+1, "_|_\n"); +} + +void +PIP_Solution_Node::print_tree(std::ostream& s, unsigned indent, + const dimension_type space_dim, + const dimension_type first_art_dim, + const Variables_Set& params) const { + // First print info common to decision and solution nodes. + PIP_Tree_Node::print_tree(s, indent, space_dim, first_art_dim, params); + + // Then print info specific of solution nodes. + const bool no_constraints = constraints_.empty(); + bool printed_first_variable = false; + indent_and_print(s, indent + (no_constraints ? 0 : 1), "{"); + for (dimension_type i = 0; i < space_dim; ++i) { + if (params.count(i) != 0) + continue; + if (printed_first_variable) + s << " ; "; + else + printed_first_variable = true; + using namespace IO_Operators; + s << parametric_values(Variable(i), params); + } + s << "}\n"; + + if (!no_constraints) { + indent_and_print(s, indent, "else\n"); + indent_and_print(s, indent+1, "_|_\n"); + } +} + } // namespace Parma_Polyhedra_Library diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index cfaed23..1064746 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -1,4 +1,4 @@ -/* PIP_Tree class declaration. +/* PIP_Tree_Node class declaration. Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it> This file is part of the Parma Polyhedra Library (PPL). @@ -93,6 +93,30 @@ public: //! Returns the number of local artificial parameters. dimension_type art_parameter_count() const; + //! Prints on \p s the tree rooted in \p *this. + /*! + \param s + The output stream. + + \param indent + The amount of indentation. + + \param space_dim + The space dimension of the PIP problem. + + \param first_art_dim + The first space dimension corresponding to an artificial parameter + that was created in this node (if any). + + \param params + The set of PIP problem parameters indices. + */ + virtual void print_tree(std::ostream& s, + unsigned indent, + dimension_type space_dim, + dimension_type first_art_dim, + const Variables_Set& params) const; + void ascii_dump(std::ostream& s) const; bool ascii_load(std::istream& s); @@ -200,6 +224,10 @@ protected: //! Inserts a new parametric constraint in internal Row format void add_constraint(const Row& x, const Variables_Set& parameters); + //! A helper function used when printing PIP trees. + static void + indent_and_print(std::ostream& s, unsigned indent, const char* str); + }; // class PIP_Tree_Node @@ -299,6 +327,13 @@ public: //! Returns \p this. virtual PIP_Solution_Node* as_solution(); + //! Prints on \p s the tree rooted in \p *this. + virtual void print_tree(std::ostream& s, + unsigned indent, + dimension_type space_dim, + dimension_type first_art_dim, + const Variables_Set& params) const; + /*! \brief Returns a parametric expression of the values of variable \p v. @@ -319,7 +354,14 @@ public: parametric_values(Variable v, const Variables_Set& parameters) const; + //! Dumps to \p s an ASCII representation of \p *this. void ascii_dump(std::ostream& s) const; + + /*! \brief + Loads from \p s an ASCII representation (as produced by + ascii_dump(std::ostream&) const) and sets \p *this accordingly. + Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. + */ bool ascii_load(std::istream& s); //! Returns the total size in bytes of the memory occupied by \p *this. @@ -658,6 +700,13 @@ public: //! Returns a pointer to the \p b (true or false) branch of \p *this. PIP_Tree_Node* child_node(bool b); + //! Prints on \p s the tree rooted in \p *this. + virtual void print_tree(std::ostream& s, + unsigned indent, + dimension_type space_dim, + dimension_type first_art_dim, + const Variables_Set& params) const; + void ascii_dump(std::ostream& s) const; bool ascii_load(std::istream& s);