PIP_Tree_defs.hh

Go to the documentation of this file.

/* PIP_Tree_Node class declaration.
   Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
   Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)

This file is part of the Parma Polyhedra Library (PPL).

The PPL is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version.

The PPL is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software Foundation,
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.

For the most up-to-date information see the Parma Polyhedra Library
site: http://bugseng.com/products/ppl/ . */

#ifndef PPL_PIP_Tree_defs_hh
#define PPL_PIP_Tree_defs_hh 1

#include "PIP_Tree_types.hh"
#include "Variable_defs.hh"
#include "Linear_Expression_types.hh"
#include "Constraint_System_defs.hh"
#include "Constraint_System_inlines.hh"
#include "Constraint_defs.hh"
#include "Variables_Set_defs.hh"
#include "globals_defs.hh"
#include "PIP_Problem_defs.hh"

#include "Matrix_defs.hh"
#include "Dense_Row_defs.hh"
#include "Sparse_Row_defs.hh"

namespace Parma_Polyhedra_Library {


class PIP_Tree_Node {
protected:
  explicit PIP_Tree_Node(const PIP_Problem* owner);

  PIP_Tree_Node(const PIP_Tree_Node& y);

  const PIP_Problem* get_owner() const;

  virtual void set_owner(const PIP_Problem* owner) = 0;

  virtual bool check_ownership(const PIP_Problem* owner) const = 0;

public:
#if PPL_USE_SPARSE_MATRIX
  typedef Sparse_Row Row;
#else
  typedef Dense_Row Row;
#endif

  virtual PIP_Tree_Node* clone() const = 0;

  virtual ~PIP_Tree_Node();

  virtual bool OK() const = 0;

  virtual const PIP_Solution_Node* as_solution() const = 0;

  virtual const PIP_Decision_Node* as_decision() const = 0;

  const Constraint_System& constraints() const;

  class Artificial_Parameter;

  typedef std::vector<Artificial_Parameter> Artificial_Parameter_Sequence;

  Artificial_Parameter_Sequence::const_iterator art_parameter_begin() const;

  Artificial_Parameter_Sequence::const_iterator art_parameter_end() const;

  dimension_type art_parameter_count() const;


  void print(std::ostream& s, int indent = 0) const;

  void ascii_dump(std::ostream& s) const;

  bool ascii_load(std::istream& s);

  virtual memory_size_type total_memory_in_bytes() const = 0;
  virtual memory_size_type external_memory_in_bytes() const = 0;

protected:
  typedef std::vector<Constraint> Constraint_Sequence;

  // Only PIP_Problem and PIP_Decision_Node are allowed to use the
  // constructor and methods.
  friend class PIP_Problem;
  friend class PIP_Decision_Node;
  friend class PIP_Solution_Node;

  const PIP_Problem* owner_;

  const PIP_Decision_Node* parent_;

  Constraint_System constraints_;

  Artificial_Parameter_Sequence artificial_parameters;

  const PIP_Decision_Node* parent() const;

  void set_parent(const PIP_Decision_Node* p);

  virtual void update_tableau(const PIP_Problem& pip,
                              dimension_type external_space_dim,
                              dimension_type first_pending_constraint,
                              const Constraint_Sequence& input_cs,
                              const Variables_Set& parameters) = 0;

  virtual PIP_Tree_Node* solve(const PIP_Problem& pip,
                               bool check_feasible_context,
                               const Matrix<Row>& context,
                               const Variables_Set& params,
                               dimension_type space_dim,
                               int indent_level) = 0;

  void add_constraint(const Row& row, const Variables_Set& parameters);

  void parent_merge();


  virtual void print_tree(std::ostream& s,
                          int indent,
                          const std::vector<bool>& pip_dim_is_param,
                          dimension_type first_art_dim) const = 0;

  static void
  indent_and_print(std::ostream& s, int indent, const char* str);

  static bool compatibility_check(Matrix<Row>& s);

  static bool compatibility_check(const Matrix<Row>& context, const Row& row);

}; // class PIP_Tree_Node


class PIP_Tree_Node::Artificial_Parameter
  : public Linear_Expression {
public:
  Artificial_Parameter();


  Artificial_Parameter(const Linear_Expression& expr,
                       Coefficient_traits::const_reference d);

  Artificial_Parameter(const Artificial_Parameter& y);

  Coefficient_traits::const_reference denominator() const;

  void m_swap(Artificial_Parameter& y);


  bool operator==(const Artificial_Parameter& y) const;
  bool operator!=(const Artificial_Parameter& y) const;

  PPL_OUTPUT_DECLARATIONS

  bool ascii_load(std::istream& s);

  memory_size_type total_memory_in_bytes() const;
  memory_size_type external_memory_in_bytes() const;

  bool OK() const;

private:
  Coefficient denom;
}; // class PIP_Tree_Node::Artificial_Parameter



void
swap(PIP_Tree_Node::Artificial_Parameter& x,
     PIP_Tree_Node::Artificial_Parameter& y);


class PIP_Solution_Node : public PIP_Tree_Node {
public:

  explicit PIP_Solution_Node(const PIP_Problem* owner);

  virtual PIP_Tree_Node* clone() const;

  virtual ~PIP_Solution_Node();

  virtual bool OK() const;

  virtual const PIP_Solution_Node* as_solution() const;

  virtual const PIP_Decision_Node* as_decision() const;

  const Linear_Expression& parametric_values(Variable var) const;

  void ascii_dump(std::ostream& os) const;

  bool ascii_load(std::istream& is);

  virtual memory_size_type total_memory_in_bytes() const;
  virtual memory_size_type external_memory_in_bytes() const;

private:
  struct Tableau {
    Matrix<Row> s;
    Matrix<Row> t;
    Coefficient denom;

    Tableau();
    Tableau(const Tableau& y);
    ~Tableau();

    bool is_integer() const;

    void scale(Coefficient_traits::const_reference ratio);


    void normalize();

    bool is_better_pivot(const std::vector<dimension_type>& mapping,
                         const std::vector<bool>& basis,
                         const dimension_type row_0,
                         const dimension_type col_0,
                         const dimension_type row_1,
                         const dimension_type col_1) const;

    Coefficient_traits::const_reference denominator() const;

    void ascii_dump(std::ostream& os) const;

    bool ascii_load(std::istream& is);


    memory_size_type external_memory_in_bytes() const;

    bool OK() const;
  }; // struct Tableau

  Tableau tableau;

  std::vector<bool> basis;

  std::vector<dimension_type> mapping;

  std::vector<dimension_type> var_row;

  std::vector<dimension_type> var_column;

  dimension_type special_equality_row;

  dimension_type big_dimension;

  enum Row_Sign {
    UNKNOWN,
    ZERO,
    POSITIVE,
    NEGATIVE,
    MIXED
  };

  std::vector<Row_Sign> sign;

  std::vector<Linear_Expression> solution;

  bool solution_valid;

  static Row_Sign row_sign(const Row& x,
                           dimension_type big_dimension);

protected:
  PIP_Solution_Node(const PIP_Solution_Node& y);

  struct No_Constraints {};


  PIP_Solution_Node(const PIP_Solution_Node& y, No_Constraints);

  // PIP_Problem::ascii load() method needs access set_owner().
  friend bool PIP_Problem::ascii_load(std::istream& s);

  virtual void set_owner(const PIP_Problem* owner);

  virtual bool check_ownership(const PIP_Problem* owner) const;

  virtual void update_tableau(const PIP_Problem& pip,
                              dimension_type external_space_dim,
                              dimension_type first_pending_constraint,
                              const Constraint_Sequence& input_cs,
                              const Variables_Set& parameters);

  void update_solution(const std::vector<bool>& pip_dim_is_param) const;

  void update_solution() const;

  virtual PIP_Tree_Node* solve(const PIP_Problem& pip,
                               bool check_feasible_context,
                               const Matrix<Row>& context,
                               const Variables_Set& params,
                               dimension_type space_dim,
                               int indent_level);

  void generate_cut(dimension_type index, Variables_Set& parameters,
                    Matrix<Row>& context, dimension_type& space_dimension,
                    int indent_level);

  virtual void print_tree(std::ostream& s, int indent,
                          const std::vector<bool>& pip_dim_is_param,
                          dimension_type first_art_dim) const;

}; // class PIP_Solution_Node


class PIP_Decision_Node : public PIP_Tree_Node {
public:
  virtual PIP_Tree_Node* clone() const;

  virtual ~PIP_Decision_Node();

  virtual bool OK() const;

  virtual const PIP_Decision_Node* as_decision() const;

  virtual const PIP_Solution_Node* as_solution() const;

  const PIP_Tree_Node* child_node(bool b) const;

  PIP_Tree_Node* child_node(bool b);

  void ascii_dump(std::ostream& s) const;

  bool ascii_load(std::istream& s);

  virtual memory_size_type total_memory_in_bytes() const;
  virtual memory_size_type external_memory_in_bytes() const;

private:
  // PIP_Solution_Node is allowed to use the constructor and methods.
  friend class PIP_Solution_Node;

  // PIP_Problem ascii load method needs access to private constructors.
  friend bool PIP_Problem::ascii_load(std::istream& s);

  PIP_Tree_Node* false_child;

  PIP_Tree_Node* true_child;

  explicit PIP_Decision_Node(const PIP_Problem* owner,
                             PIP_Tree_Node* fcp,
                             PIP_Tree_Node* tcp);

  virtual void set_owner(const PIP_Problem* owner);

  virtual bool check_ownership(const PIP_Problem* owner) const;

protected:
  PIP_Decision_Node(const PIP_Decision_Node& y);

  virtual void update_tableau(const PIP_Problem& pip,
                              dimension_type external_space_dim,
                              dimension_type first_pending_constraint,
                              const Constraint_Sequence& input_cs,
                              const Variables_Set& parameters);

  virtual PIP_Tree_Node* solve(const PIP_Problem& pip,
                               bool check_feasible_context,
                               const Matrix<Row>& context,
                               const Variables_Set& params,
                               dimension_type space_dim,
                               int indent_level);

  virtual void print_tree(std::ostream& s, int indent,
                          const std::vector<bool>& pip_dim_is_param,
                          dimension_type first_art_dim) const;

}; // class PIP_Decision_Node

namespace IO_Operators {


std::ostream& operator<<(std::ostream& os, const PIP_Tree_Node& x);


std::ostream& operator<<(std::ostream& os,
                         const PIP_Tree_Node::Artificial_Parameter& x);

} // namespace IO_Operators

} // namespace Parma_Polyhedra_Library

#include "PIP_Tree_inlines.hh"

#endif // !defined(PPL_PIP_Tree_defs_hh)