Parma_Polyhedra_Library::PIP_Decision_Node Class Reference

A tree node representing a decision in the space of solutions. More...

#include <PIP_Tree_defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::PIP_Decision_Node:

Collaboration diagram for Parma_Polyhedra_Library::PIP_Decision_Node:

Public Member Functions
virtual PIP_Tree_Node *	clone () const
	Returns a pointer to a dynamically-allocated copy of *this. More...
virtual	~PIP_Decision_Node ()
	Destructor. More...
virtual bool	OK () const
	Returns true if and only if *this is well formed. More...
virtual const PIP_Decision_Node *	as_decision () const
	Returns this. More...
virtual const PIP_Solution_Node *	as_solution () const
	Returns 0, since this is not a solution node. More...
const PIP_Tree_Node *	child_node (bool b) const
	Returns a const pointer to the b (true or false) branch of *this. More...
PIP_Tree_Node *	child_node (bool b)
	Returns a pointer to the b (true or false) branch of *this. More...
void	ascii_dump (std::ostream &s) const
	Dumps to s an ASCII representation of *this. More...
bool	ascii_load (std::istream &s)
	Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise. More...
virtual memory_size_type	total_memory_in_bytes () const
	Returns the total size in bytes of the memory occupied by *this. More...
virtual memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by *this. More...
Public Member Functions inherited from Parma_Polyhedra_Library::PIP_Tree_Node
virtual	~PIP_Tree_Node ()
	Destructor. More...
const Constraint_System &	constraints () const
	Returns the system of parameter constraints controlling *this. More...
Artificial_Parameter_Sequence::const_iterator	art_parameter_begin () const
	Returns a const_iterator to the beginning of local artificial parameters. More...
Artificial_Parameter_Sequence::const_iterator	art_parameter_end () const
	Returns a const_iterator to the end of local artificial parameters. More...
dimension_type	art_parameter_count () const
	Returns the number of local artificial parameters. More...
void	print (std::ostream &s, int indent=0) const
	Prints on s the tree rooted in *this. More...
void	ascii_dump (std::ostream &s) const
	Dumps to s an ASCII representation of *this. More...
bool	ascii_load (std::istream &s)
	Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise. More...

Protected Member Functions
	PIP_Decision_Node (const PIP_Decision_Node &y)
	Copy constructor. More...
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)
	Implements pure virtual method PIP_Tree_Node::update_tableau. More...
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)
	Implements pure virtual method PIP_Tree_Node::solve. More...
virtual void	print_tree (std::ostream &s, int indent, const std::vector< bool > &pip_dim_is_param, dimension_type first_art_dim) const
	Prints on s the tree rooted in *this. More...
Protected Member Functions inherited from Parma_Polyhedra_Library::PIP_Tree_Node
	PIP_Tree_Node (const PIP_Problem *owner)
	Constructor: builds a node owned by *owner. More...
	PIP_Tree_Node (const PIP_Tree_Node &y)
	Copy constructor. More...
const PIP_Problem *	get_owner () const
	Returns a pointer to the PIP_Problem owning object. More...
const PIP_Decision_Node *	parent () const
	Returns a pointer to this node's parent. More...
void	set_parent (const PIP_Decision_Node *p)
	Set this node's parent to *p. More...
void	add_constraint (const Row &row, const Variables_Set &parameters)
	Inserts a new parametric constraint in internal row format. More...
void	parent_merge ()
	Merges parent's artificial parameters into *this. More...

Private Member Functions
	PIP_Decision_Node (const PIP_Problem *owner, PIP_Tree_Node *fcp, PIP_Tree_Node *tcp)
	Builds a decision node having fcp and tcp as child. More...
virtual void	set_owner (const PIP_Problem *owner)
	Sets the pointer to the PIP_Problem owning object. More...
virtual bool	check_ownership (const PIP_Problem *owner) const
	Returns true if and only if all the nodes in the subtree rooted in *this is owned by *pip. More...

Private Attributes
PIP_Tree_Node *	false_child
	Pointer to the "false" child of *this. More...
PIP_Tree_Node *	true_child
	Pointer to the "true" child of *this. More...

Friends
class	PIP_Solution_Node
bool	PIP_Problem::ascii_load (std::istream &s)

Additional Inherited Members
Public Types inherited from Parma_Polyhedra_Library::PIP_Tree_Node
typedef Sparse_Row	Row
typedef std::vector< Artificial_Parameter >	Artificial_Parameter_Sequence
	A type alias for a sequence of Artificial_Parameter's. More...
Protected Types inherited from Parma_Polyhedra_Library::PIP_Tree_Node
typedef std::vector< Constraint >	Constraint_Sequence
	A type alias for a sequence of constraints. More...
Static Protected Member Functions inherited from Parma_Polyhedra_Library::PIP_Tree_Node
static void	indent_and_print (std::ostream &s, int indent, const char *str)
	A helper function used when printing PIP trees. More...
static bool	compatibility_check (Matrix< Row > &s)
	Checks whether a context matrix is satisfiable. More...
static bool	compatibility_check (const Matrix< Row > &context, const Row &row)
	Helper method: checks for satisfiability of the restricted context obtained by adding row to context. More...
Protected Attributes inherited from Parma_Polyhedra_Library::PIP_Tree_Node
const PIP_Problem *	owner_
	A pointer to the PIP_Problem object owning this node. More...
const PIP_Decision_Node *	parent_
	A pointer to the parent of *this, null if *this is the root. More...
Constraint_System	constraints_
	The local system of parameter constraints. More...
Artificial_Parameter_Sequence	artificial_parameters
	The local sequence of expressions for local artificial parameters. More...
Related Functions inherited from Parma_Polyhedra_Library::PIP_Tree_Node
std::ostream &	operator<< (std::ostream &os, const PIP_Tree_Node &x)
	Output operator: prints the solution tree rooted in x. More...

Detailed Description

A tree node representing a decision in the space of solutions.

Definition at line 707 of file PIP_Tree_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::PIP_Decision_Node::~PIP_Decision_Node ( )

virtual

Destructor.

Definition at line 1114 of file PIP_Tree.cc.

References false_child, and true_child.

                                      {
  delete false_child;
  delete true_child;
}

Parma_Polyhedra_Library::PIP_Decision_Node::PIP_Decision_Node ( const PIP_Problem *  owner, PIP_Tree_Node *  fcp, PIP_Tree_Node *  tcp  )

explicitprivate

Builds a decision node having fcp and tcp as child.

The decision node will encode the structure "if \c cs then \p tcp else \p fcp", where the system of constraints cs is initially empty.

Parameters

owner	Pointer to the owning PIP_Problem object; it may be null if and only if both children are null.
fcp	Pointer to "false" child; it may be null.
tcp	Pointer to "true" child; it may be null.

Note

If any of fcp or tcp is not null, then owner is required to be not null and equal to the owner of its non-null children; otherwise the behavior is undefined.

Definition at line 1082 of file PIP_Tree.cc.

References false_child, Parma_Polyhedra_Library::PIP_Tree_Node::set_parent(), and true_child.

  : PIP_Tree_Node(owner),
    false_child(fcp),
    true_child(tcp) {
  if (false_child != 0) {
    false_child->set_parent(this);
  }
  if (true_child != 0) {
    true_child->set_parent(this);
  }
}

Parma_Polyhedra_Library::PIP_Decision_Node::PIP_Decision_Node ( const PIP_Decision_Node &  y )

protected

Copy constructor.

Definition at line 1096 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::clone(), false_child, Parma_Polyhedra_Library::PIP_Tree_Node::set_parent(), and true_child.

  : PIP_Tree_Node(y),
    false_child(0),
    true_child(0) {
  if (y.false_child != 0) {
    false_child = y.false_child->clone();
    false_child->set_parent(this);
  }
  // Protect false_child from exception safety issues via std::auto_ptr.
  std::auto_ptr<PIP_Tree_Node> wrapped_node(false_child);
  if (y.true_child != 0) {
    true_child = y.true_child->clone();
    true_child->set_parent(this);
  }
  // It is now safe to release false_child.
  wrapped_node.release();
}

Member Function Documentation

const PIP_Decision_Node * Parma_Polyhedra_Library::PIP_Decision_Node::as_decision ( ) const

virtual

Returns this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1148 of file PIP_Tree.cc.

Referenced by Parma_Polyhedra_Library::PIP_Problem::ascii_dump(), and ascii_dump().

                                     {
  return this;
}

const PIP_Solution_Node * Parma_Polyhedra_Library::PIP_Decision_Node::as_solution ( ) const

virtual

Returns 0, since this is not a solution node.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1158 of file PIP_Tree.cc.

                                     {
  return 0;
}

void Parma_Polyhedra_Library::PIP_Decision_Node::ascii_dump

(

std::ostream &

s

)

const

Dumps to s an ASCII representation of *this.

Definition at line 1525 of file PIP_Tree.cc.

References as_decision(), Parma_Polyhedra_Library::PIP_Solution_Node::as_solution(), Parma_Polyhedra_Library::PIP_Tree_Node::ascii_dump(), and Parma_Polyhedra_Library::PIP_Solution_Node::ascii_dump().

                                                 {
  // Dump base class info.
  PIP_Tree_Node::ascii_dump(s);

  // Dump true child (if any).
  s << "\ntrue_child: ";
  if (true_child == 0) {
    // Note: this branch should normally be unreachable code, since a
    // well-formed decision node always has a true child. We keep this code
    // for debugging purposes (since we want to dump broken nodes).
    s << "BOTTOM\n";
  }
  else if (const PIP_Decision_Node* const dec = true_child->as_decision()) {
    s << "DECISION\n";
    dec->ascii_dump(s);
  }
  else {
    const PIP_Solution_Node* const sol = true_child->as_solution();
    PPL_ASSERT(sol != 0);
    s << "SOLUTION\n";
    sol->ascii_dump(s);
  }

  // Dump false child (if any).
  s << "\nfalse_child: ";
  if (false_child == 0) {
    s << "BOTTOM\n";
  }
  else if (const PIP_Decision_Node* const dec = false_child->as_decision()) {
    // Note: this branch should normally be unreachable code.
    // Since a well-formed decision node having a false child should have
    // a single context constraint, its false child will have no context
    // constraints at all, so that no further branch is possible.
    // We keep this code for debugging purposes.
    s << "DECISION\n";
    dec->ascii_dump(s);
  }
  else {
    const PIP_Solution_Node* const sol = false_child->as_solution();
    PPL_ASSERT(sol != 0);
    s << "SOLUTION\n";
    sol->ascii_dump(s);
  }
}

bool Parma_Polyhedra_Library::PIP_Decision_Node::ascii_load

(

std::istream &

s

)

Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.

Definition at line 1571 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::ascii_load(), Parma_Polyhedra_Library::PIP_Solution_Node::ascii_load(), ascii_load(), Parma_Polyhedra_Library::PIP_Solution_Node::OK(), Parma_Polyhedra_Library::PIP_Tree_Node::PIP_Decision_Node, and Parma_Polyhedra_Library::PIP_Solution_Node::PIP_Solution_Node().

Referenced by Parma_Polyhedra_Library::PIP_Problem::ascii_load(), and ascii_load().

                                           {
  std::string str;

  // Load base class info.
  if (!PIP_Tree_Node::ascii_load(s)) {
    return false;
  }

  // Release the "true" subtree (if any).
  delete true_child;
  true_child = 0;

  // Load true child (if any).
  if (!(s >> str) || str != "true_child:") {
    return false;
  }
  if (!(s >> str)) {
    return false;
  }
  if (str == "BOTTOM") {
    // Note: normally unreachable code (see comment on ascii_dump).
    true_child = 0;
  }
  else if (str == "DECISION") {
    PIP_Decision_Node* const dec = new PIP_Decision_Node(0, 0, 0);
    true_child = dec;
    if (!dec->ascii_load(s)) {
      return false;
    }
  }
  else if (str == "SOLUTION") {
    PIP_Solution_Node* const sol = new PIP_Solution_Node(0);
    true_child = sol;
    if (!sol->ascii_load(s)) {
      return false;
    }
  }
  else {
    // Unknown node kind.
    return false;
  }

  // Release the "false" subtree (if any).
  delete false_child;
  false_child = 0;

  // Load false child (if any).
  if (!(s >> str) || str != "false_child:") {
    return false;
  }
  if (!(s >> str)) {
    return false;
  }
  if (str == "BOTTOM") {
    false_child = 0;
  }
  else if (str == "DECISION") {
    // Note: normally unreachable code (see comment on ascii_dump).
    PIP_Decision_Node* const dec = new PIP_Decision_Node(0, 0, 0);
    false_child = dec;
    if (!dec->ascii_load(s)) {
      return false;
    }
  }
  else if (str == "SOLUTION") {
    PIP_Solution_Node* const sol = new PIP_Solution_Node(0);
    false_child = sol;
    if (!sol->ascii_load(s)) {
      return false;
    }
  }
  else {
    // Unknown node kind.
    return false;
  }

  // Loaded all info.
  PPL_ASSERT(OK());
  return true;
}

bool Parma_Polyhedra_Library::PIP_Decision_Node::check_ownership ( const PIP_Problem *  owner ) const

privatevirtual

Returns true if and only if all the nodes in the subtree rooted in *this is owned by *pip.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1141 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::check_ownership(), false_child, Parma_Polyhedra_Library::PIP_Tree_Node::get_owner(), and true_child.

                                                                 {
  return get_owner() == owner
    && (false_child == 0 || false_child->check_ownership(owner))
    && (true_child == 0 || true_child->check_ownership(owner));
}

const PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::child_node ( bool  b ) const

inline

Returns a const pointer to the b (true or false) branch of *this.

Definition at line 92 of file PIP_Tree_inlines.hh.

                                          {
  return b ? true_child : false_child;
}

PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::child_node ( bool  b )

inline

Returns a pointer to the b (true or false) branch of *this.

Definition at line 98 of file PIP_Tree_inlines.hh.

                                    {
  return b ? true_child : false_child;
}

PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::clone ( ) const

virtual

Returns a pointer to a dynamically-allocated copy of *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1868 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::PIP_Decision_Node.

                               {
  return new PIP_Decision_Node(*this);
}

memory_size_type Parma_Polyhedra_Library::PIP_Decision_Node::external_memory_in_bytes ( ) const

virtual

Returns the size in bytes of the memory managed by *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 3755 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::external_memory_in_bytes().

                                                  {
  memory_size_type n = PIP_Tree_Node::external_memory_in_bytes();
  PPL_ASSERT(true_child != 0);
  n += true_child->total_memory_in_bytes();
  if (false_child != 0) {
    n += false_child->total_memory_in_bytes();
  }
  return n;
}

bool Parma_Polyhedra_Library::PIP_Decision_Node::OK ( ) const

virtual

Returns true if and only if *this is well formed.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1335 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::constraints_, Parma_Polyhedra_Library::Implementation::num_constraints(), and Parma_Polyhedra_Library::PIP_Tree_Node::OK().

                            {
  // Perform base class well-formedness check on this node.
  if (!PIP_Tree_Node::OK()) {
    return false;
  }

  // Recursively check if child nodes are well-formed.
  if (false_child != 0 && !false_child->OK()) {
    return false;
  }
  if (true_child != 0 && !true_child->OK()) {
    return false;
  }

  // Decision nodes should always have a true child.
  if (true_child == 0) {
#ifndef NDEBUG
    std::cerr << "PIP_Decision_Node with no 'true' child.\n";
#endif
    return false;
  }

  // Decision nodes with a false child must have exactly one constraint.
  if (false_child != 0) {
    const dimension_type dist = Implementation::num_constraints(constraints_);
    if (dist != 1) {
#ifndef NDEBUG
      std::cerr << "PIP_Decision_Node with a 'false' child has "
                << dist << " parametric constraints (should be 1).\n";
#endif
      return false;
    }
  }

  // All checks passed.
  return true;
}

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

protectedvirtual

Prints on s the tree rooted in *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 3862 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::art_parameter_count(), Parma_Polyhedra_Library::PIP_Tree_Node::indent_and_print(), and Parma_Polyhedra_Library::PIP_Tree_Node::print_tree().

                                                                        {
  // First print info common to decision and solution nodes.
  PIP_Tree_Node::print_tree(s, indent, pip_dim_is_param, first_art_dim);

  // Then print info specific of decision nodes.
  const dimension_type child_first_art_dim
    = first_art_dim + art_parameter_count();

  PPL_ASSERT(true_child != 0);
  true_child->print_tree(s, indent+1, pip_dim_is_param, child_first_art_dim);

  indent_and_print(s, indent, "else\n");

  if (false_child != 0) {
    false_child->print_tree(s, indent+1, pip_dim_is_param,
                            child_first_art_dim);
  }
  else {
    indent_and_print(s, indent+1, "_|_\n");
  }
}

void Parma_Polyhedra_Library::PIP_Decision_Node::set_owner ( const PIP_Problem *  owner )

privatevirtual

Sets the pointer to the PIP_Problem owning object.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1125 of file PIP_Tree.cc.

References false_child, Parma_Polyhedra_Library::PIP_Tree_Node::owner_, Parma_Polyhedra_Library::PIP_Tree_Node::set_owner(), and true_child.

Referenced by Parma_Polyhedra_Library::PIP_Problem::ascii_load().

                                                     {
  owner_ = owner;
  if (false_child != 0) {
    false_child->set_owner(owner);
  }
  if (true_child != 0) {
    true_child->set_owner(owner);
  }
}

PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_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  )

protectedvirtual

Implements pure virtual method PIP_Tree_Node::solve.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1397 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::artificial_parameters, Parma_Polyhedra_Library::Constraint_System::begin(), Parma_Polyhedra_Library::PIP_Tree_Node::compatibility_check(), Parma_Polyhedra_Library::PIP_Tree_Node::constraints_, Parma_Polyhedra_Library::Constraint_System::empty(), Parma_Polyhedra_Library::Constraint_System::end(), Parma_Polyhedra_Library::PIP_Tree_Node::indent_and_print(), Parma_Polyhedra_Library::Constraint_System::insert(), Parma_Polyhedra_Library::Implementation::num_constraints(), Parma_Polyhedra_Library::Matrix< Row >::num_rows(), Parma_Polyhedra_Library::PIP_Tree_Node::OK(), Parma_Polyhedra_Library::PIP_Solution_Node::OK(), Parma_Polyhedra_Library::PIP_Tree_Node::parent(), Parma_Polyhedra_Library::PIP_Tree_Node::parent_merge(), PPL_USED, Parma_Polyhedra_Library::PIP_Tree_Node::set_parent(), and Parma_Polyhedra_Library::swap().

                                                 {
  PPL_ASSERT(indent_level >= 0);
#ifdef NOISY_PIP_TREE_STRUCTURE
  indent_and_print(std::cerr, indent_level, "=== SOLVING DECISION NODE\n");
#else
  PPL_USED(indent_level);
#endif
  PPL_ASSERT(true_child != 0);
  Matrix<Row> context_true(context);
  Variables_Set all_params(params);
  const dimension_type num_art_params = artificial_parameters.size();
  add_artificial_parameters(context_true, all_params, space_dim,
                            num_art_params);
  merge_assign(context_true, constraints_, all_params);
  const bool has_false_child = (false_child != 0);
  const bool has_true_child = (true_child != 0);
#ifdef NOISY_PIP_TREE_STRUCTURE
  indent_and_print(std::cerr, indent_level,
                   "=== DECISION: SOLVING THEN CHILD\n");
#endif
  true_child = true_child->solve(pip, check_feasible_context,
                                 context_true, all_params, space_dim,
                                 indent_level + 1);

  if (has_false_child) {
    // Decision nodes with false child must have exactly one constraint
    PPL_ASSERT(1 == Implementation::num_constraints(constraints_));
    // NOTE: modify context_true in place, complementing its last constraint.
    Matrix<Row>& context_false = context_true;
    Row& last = context_false[context_false.num_rows() - 1];
    complement_assign(last, last, 1);
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: SOLVING ELSE CHILD\n");
#endif
    false_child = false_child->solve(pip, check_feasible_context,
                                     context_false, all_params, space_dim,
                                     indent_level + 1);
  }

  if (true_child == 0 && false_child == 0) {
    // No children: the whole subtree is unfeasible.
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: BOTH BRANCHES NOW UNFEASIBLE: _|_\n");
#endif
    delete this;
    return 0;
  }

  if (has_false_child && false_child == 0) {
    // False child has become unfeasible: merge this node's artificials with
    // the true child, while removing the local parameter constraints, which
    // are no longer discriminative.
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: ELSE BRANCH NOW UNFEASIBLE\n");
    indent_and_print(std::cerr, indent_level,
                     "==> merge then branch with parent.\n");
#endif
    PIP_Tree_Node* const node = true_child;
    node->parent_merge();
    node->set_parent(parent());
    true_child = 0;
    delete this;
    PPL_ASSERT(node->OK());
    return node;
  }
  else if (has_true_child && true_child == 0) {
    // True child has become unfeasible: merge this node's artificials
    // with the false child.
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: THEN BRANCH NOW UNFEASIBLE\n");
    indent_and_print(std::cerr, indent_level,
                     "==> merge else branch with parent.\n");
#endif
    PIP_Tree_Node* const node = false_child;
    node->parent_merge();
    node->set_parent(parent());
    false_child = 0;
    delete this;
    PPL_ASSERT(node->OK());
    return node;
  }
  else if (check_feasible_context) {
    // Test all constraints for redundancy with the context, and eliminate
    // them if not necessary.
    Constraint_System cs;
    swap(cs, constraints_);
    for (Constraint_System::const_iterator ci = cs.begin(),
           ci_end = cs.end(); ci != ci_end; ++ci) {
      Matrix<Row> ctx_copy(context);
      merge_assign(ctx_copy, Constraint_System(*ci), all_params);
      Row& last = ctx_copy[ctx_copy.num_rows()-1];
      complement_assign(last, last, 1);
      if (compatibility_check(ctx_copy)) {
        // The constraint is not redundant with the context: keep it.
        constraints_.insert(*ci);
      }
    }
    // If the constraints set has become empty, only keep the true child.
    if (constraints_.empty()) {
#ifdef NOISY_PIP_TREE_STRUCTURE
      indent_and_print(std::cerr, indent_level,
                       "=== DECISION: NO BRANCHING CONSTRAINTS LEFT\n");
      indent_and_print(std::cerr, indent_level,
                       "==> merge then branch with parent.\n");
#endif
      PIP_Tree_Node* const node = true_child;
      node->parent_merge();
      node->set_parent(parent());
      true_child = 0;
      delete this;
      PPL_ASSERT(node->OK());
      return node;
    }
  }
  PPL_ASSERT(OK());
  return this;
}

memory_size_type Parma_Polyhedra_Library::PIP_Decision_Node::total_memory_in_bytes ( ) const

virtual

Returns the total size in bytes of the memory occupied by *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 3766 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::external_memory_in_bytes().

                                               {
  return sizeof(*this) + external_memory_in_bytes();
}

void Parma_Polyhedra_Library::PIP_Decision_Node::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  )

protectedvirtual

Implements pure virtual method PIP_Tree_Node::update_tableau.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1374 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::OK().

                                     {

  true_child->update_tableau(pip,
                             external_space_dim,
                             first_pending_constraint,
                             input_cs,
                             parameters);
  if (false_child != 0) {
    false_child->update_tableau(pip,
                                external_space_dim,
                                first_pending_constraint,
                                input_cs,
                                parameters);
  }
  PPL_ASSERT(OK());
}

Friends And Related Function Documentation

bool PIP_Problem::ascii_load ( std::istream &  s )

friend

friend class PIP_Solution_Node

friend

Definition at line 747 of file PIP_Tree_defs.hh.

Member Data Documentation

PIP_Tree_Node* Parma_Polyhedra_Library::PIP_Decision_Node::false_child

private

Pointer to the "false" child of *this.

Definition at line 753 of file PIP_Tree_defs.hh.

Referenced by check_ownership(), PIP_Decision_Node(), set_owner(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and ~PIP_Decision_Node().

PIP_Tree_Node* Parma_Polyhedra_Library::PIP_Decision_Node::true_child

private

Pointer to the "true" child of *this.

Definition at line 756 of file PIP_Tree_defs.hh.

Referenced by check_ownership(), PIP_Decision_Node(), set_owner(), and ~PIP_Decision_Node().

---

The documentation for this class was generated from the following files:

• PIP_Tree_defs.hh
• PIP_Tree.cc
• PIP_Tree_inlines.hh