[PPL-devel] [GIT] ppl/ppl(master): Added method PIP_Problem::print_solution().
Enea Zaffanella
zaffanella at cs.unipr.it
Wed Feb 17 12:51:28 CET 2010
Module: ppl/ppl
Branch: master
Commit: 7da6c43b438cf0948998e17eb6e8077fb39a7b1d
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7da6c43b438cf0948998e17eb6e8077fb39a7b1d
Author: Enea Zaffanella <zaffanella at 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 at 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);
More information about the PPL-devel
mailing list