An Elimination sequence algorithm that imposes a given complete ordering on the nodes elimination sequence. More...

#include <orderedEliminationSequenceStrategy.h>

Inheritance diagram for gum::OrderedEliminationSequenceStrategy:

Collaboration diagram for gum::OrderedEliminationSequenceStrategy:

Public Member Functions
Constructors / Destructors
	OrderedEliminationSequenceStrategy ()
	default constructor (uses an empty graph)
	OrderedEliminationSequenceStrategy (UndiGraph graph, const NodeProperty< Size > dom_sizes, const std::vector< NodeId > *order)
	constructor for a (tensorly) non empty graph
	OrderedEliminationSequenceStrategy (const OrderedEliminationSequenceStrategy &from)
	copy constructor
	OrderedEliminationSequenceStrategy (OrderedEliminationSequenceStrategy &&from)
	move constructor
virtual	~OrderedEliminationSequenceStrategy ()
	destructor
virtual OrderedEliminationSequenceStrategy *	newFactory () const final
	creates a new elimination sequence of the same type as the current object, but this sequence contains only an empty graph
virtual OrderedEliminationSequenceStrategy *	copyFactory () const final
	virtual copy constructor
Accessors / Modifiers
virtual bool	setGraph (UndiGraph graph, const NodeProperty< Size > dom_sizes) final
	sets a new graph to be triangulated
virtual bool	setOrder (const std::vector< NodeId > *order) final
	sets the sequence of elimination
virtual void	clear () final
	clears the order (to prepare, for instance, a new elimination sequence)
virtual NodeId	nextNodeToEliminate () final
	returns the new node to be eliminated within the triangulation algorithm
virtual void	askFillIns (bool do_it) final
	if the elimination sequence is able to compute fill-ins, we indicate whether we want this feature to be activated
virtual bool	providesFillIns () const final
	indicates whether the fill-ins generated by the eliminated nodes, if needed, will be computed by the elimination sequence, or need be computed by the triangulation itself.
virtual bool	providesGraphUpdate () const final
	indicates whether the elimination sequence updates by itself the graph after a node has been eliminated
virtual void	eliminationUpdate (const NodeId node) final
	performs all the graph/fill-ins updates provided (if any)
virtual const EdgeSet &	fillIns () final
	in case fill-ins are provided, this function returns the fill-ins due to all the nodes eliminated so far
const std::vector< NodeId > *	order () const noexcept
	returns the current complete ordering
bool	isOrderNeeded () const noexcept
	indicates whether a new complete ordering is needed
Accessors / Modifiers
UndiGraph *	graph () const noexcept
	returns the current graph
const NodeProperty< Size > *	domainSizes () const noexcept
	returns the current domain sizes

Protected Attributes
UndiGraph *	graph_ {nullptr}
	the graph to be triangulated
const NodeProperty< Size > *	domain_sizes_ {nullptr}
	the domain sizes of the variables/nodes
NodeProperty< double >	log_domain_sizes_
	the log of the domain sizes of the variables/nodes

Private Member Functions
bool	_isOrderNeeded_ (const std::vector< NodeId > *order) const
	indicates whether an order is compatible with the current graph

Static Private Member Functions
static const EdgeSet &	_empty_fill_ins_ ()
	an empty fill-ins set used by default

Private Attributes
const std::vector< NodeId > *	_order_ {nullptr}
	the vector indicating in which order we should eliminate the nodes
std::size_t	_order_index_ {std::size_t(0)}
	the index in the order indicating the new node to eliminate
bool	_order_needed_ {true}
	indicate whether a new complete ordering is necessary for the elimination

Detailed Description

An Elimination sequence algorithm that imposes a given complete ordering on the nodes elimination sequence.

Definition at line 65 of file orderedEliminationSequenceStrategy.h.

Constructor & Destructor Documentation

◆ OrderedEliminationSequenceStrategy() [1/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy ( )

default constructor (uses an empty graph)

Definition at line 61 of file orderedEliminationSequenceStrategy.cpp.

                                                                         {
    GUM_CONSTRUCTOR(OrderedEliminationSequenceStrategy);
  }

References OrderedEliminationSequenceStrategy().

Referenced by OrderedEliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), ~OrderedEliminationSequenceStrategy(), copyFactory(), and newFactory().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ OrderedEliminationSequenceStrategy() [2/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy	(	UndiGraph *	graph,
		const NodeProperty< Size > *	dom_sizes,
		const std::vector< NodeId > *	order )

constructor for a (tensorly) non empty graph

Parameters

graph	the graph to be triangulated, i.e., the nodes of which will be eliminated
dom_sizes	thedomain sizes of the nodes/variables
order	the order in which the nodes should be eliminated

Warning: Note that we allow dom_sizes and order to be defined over nodes/variables that do not belong to graph. These sizes/nodes will simply be ignored. However, it is compulsory that all the nodes of graph belong to both dom_sizes and order; the graph is altered during the triangulation.; note that, by aGrUM's rule, the graph and the order are not copied but only referenced by the elimination sequence algorithm.

Definition at line 66 of file orderedEliminationSequenceStrategy.cpp.

                                        : EliminationSequenceStrategy(graph, dom_sizes) {
    // check that the user passed appropriate graphs and orders
    if (((graph == nullptr) && (order != nullptr)) || ((graph != nullptr) && (order == nullptr))) {
      GUM_ERROR(GraphError,
                "OrderedEliminationSequenceStrategy needs either both nullptrs "
                "or both non-nullptrs on graph and elimination ordering");
    }
 
    setOrder(order);
 
    GUM_CONSTRUCTOR(OrderedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), gum::EliminationSequenceStrategy::graph(), GUM_ERROR, order(), and setOrder().

Here is the call graph for this function:

◆ OrderedEliminationSequenceStrategy() [3/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy ( const OrderedEliminationSequenceStrategy & from )

copy constructor

Definition at line 83 of file orderedEliminationSequenceStrategy.cpp.

                                                      :
      EliminationSequenceStrategy(from), _order_(from._order_), _order_index_(from._order_index_),
      _order_needed_(from._order_needed_) {
    GUM_CONS_CPY(OrderedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), _order_, _order_index_, and _order_needed_.

Here is the call graph for this function:

◆ OrderedEliminationSequenceStrategy() [4/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy ( OrderedEliminationSequenceStrategy && from )

move constructor

Definition at line 91 of file orderedEliminationSequenceStrategy.cpp.

                                                 :
      EliminationSequenceStrategy(std::move(from)), _order_(from._order_),
      _order_index_(from._order_index_), _order_needed_(from._order_needed_) {
    GUM_CONS_MOV(OrderedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), _order_, _order_index_, and _order_needed_.

Here is the call graph for this function:

◆ ~OrderedEliminationSequenceStrategy()

gum::OrderedEliminationSequenceStrategy::~OrderedEliminationSequenceStrategy ( )

virtual

destructor

Definition at line 99 of file orderedEliminationSequenceStrategy.cpp.

                                                                          {
    GUM_DESTRUCTOR(OrderedEliminationSequenceStrategy);
  }

References OrderedEliminationSequenceStrategy().

Here is the call graph for this function:

Member Function Documentation

◆ _empty_fill_ins_()

const EdgeSet & gum::EliminationSequenceStrategy::_empty_fill_ins_ ( )

staticprivateinherited

an empty fill-ins set used by default

Definition at line 60 of file eliminationSequenceStrategy.cpp.

                                                               {
#ifdef GUM_DEBUG_MODE
    static bool first_use = true;
    if (first_use) {
      first_use = false;
      __debug__::_dec_creation_("Set", " __empty_edge_set", 0, "static variable correction", 0);
      __debug__::_dec_creation_("HashTable",
                                " __empty_edge_set",
                                0,
                                "static variable correction",
                                0);
    }
#endif
    static EdgeSet empty_fill_ins;
    return empty_fill_ins;
  }

Referenced by fillIns().

Here is the caller graph for this function:

◆ _isOrderNeeded_()

bool gum::OrderedEliminationSequenceStrategy::_isOrderNeeded_ ( const std::vector< NodeId > * order ) const

private

indicates whether an order is compatible with the current graph

Definition at line 126 of file orderedEliminationSequenceStrategy.cpp.

                                              {
    if ((graph_ == nullptr) || (order == nullptr)) return true;
 
    // determine the set of nodes in the order that belong to the graph
    NodeSet nodes_found(graph_->size() / 2);
    for (const auto node: *order) {
      if (graph_->existsNode(node)) { nodes_found.insert(node); }
    }
 
    // check that the size of nodes_found is equal to that of the graph
    return nodes_found.size() != graph_->size();
  }

References gum::EliminationSequenceStrategy::graph_, gum::Set< Key >::insert(), order(), and gum::Set< Key >::size().

Referenced by setOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ askFillIns()

void gum::OrderedEliminationSequenceStrategy::askFillIns ( bool do_it )

finalvirtual

if the elimination sequence is able to compute fill-ins, we indicate whether we want this feature to be activated

Parameters

do_it when true and the elimination sequence has the ability to compute fill-ins, the elimination sequence will actually compute them (for the triangulation to use them), else they will not be available.

Implements gum::EliminationSequenceStrategy.

Definition at line 181 of file orderedEliminationSequenceStrategy.cpp.

                                                                {
    // do nothing: we are not able to compute fill-ins
  }

◆ clear()

void gum::OrderedEliminationSequenceStrategy::clear ( )

finalvirtual

clears the order (to prepare, for instance, a new elimination sequence)

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 163 of file orderedEliminationSequenceStrategy.cpp.

                                                 {
    EliminationSequenceStrategy::clear();
    _order_needed_ = true;
    _order_index_  = std::size_t(0);
  }

References _order_index_, _order_needed_, and gum::EliminationSequenceStrategy::clear().

Here is the call graph for this function:

◆ copyFactory()

OrderedEliminationSequenceStrategy * gum::OrderedEliminationSequenceStrategy::copyFactory ( ) const

finalvirtual

virtual copy constructor

Implements gum::EliminationSequenceStrategy.

Definition at line 110 of file orderedEliminationSequenceStrategy.cpp.

                                                                                            {
    return new OrderedEliminationSequenceStrategy(*this);
  }

References OrderedEliminationSequenceStrategy().

Here is the call graph for this function:

◆ domainSizes()

INLINE const NodeProperty< Size > * gum::EliminationSequenceStrategy::domainSizes ( ) const

noexceptinherited

returns the current domain sizes

Definition at line 59 of file eliminationSequenceStrategy_inl.h.

                                                                                             {
    return domain_sizes_;
  }

References domain_sizes_.

Referenced by providesGraphUpdate().

Here is the caller graph for this function:

◆ eliminationUpdate()

void gum::OrderedEliminationSequenceStrategy::eliminationUpdate ( const NodeId node )

finalvirtual

performs all the graph/fill-ins updates provided (if any)

Parameters

node	the node the elimination of which requires the graph update

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 195 of file orderedEliminationSequenceStrategy.cpp.

                                                                              {
    // check whether there is something to update
    if (!_order_needed_) {
      // check that node corresponds to the current index
      if ((_order_index_ >= _order_->size()) || ((*_order_)[_order_index_] != node)) {
        GUM_ERROR(OutOfBounds,
                  "update impossible because node "
                      << node << " does not correspond to the current elimination index");
      }
 
      // now perform the update: goto the next node that belongs to graph_
      ++_order_index_;
      std::size_t size = _order_->size();
      while ((_order_index_ < size) && !graph_->existsNode((*_order_)[_order_index_]))
        ++_order_index_;
    }
  }

References _order_, _order_index_, _order_needed_, gum::EliminationSequenceStrategy::graph_, and GUM_ERROR.

◆ fillIns()

const EdgeSet & gum::OrderedEliminationSequenceStrategy::fillIns ( )

finalvirtual

in case fill-ins are provided, this function returns the fill-ins due to all the nodes eliminated so far

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 215 of file orderedEliminationSequenceStrategy.cpp.

                                                             {
    return EliminationSequenceStrategy::fillIns();
  }

References gum::EliminationSequenceStrategy::fillIns().

Here is the call graph for this function:

◆ graph()

INLINE UndiGraph * gum::EliminationSequenceStrategy::graph ( ) const

noexceptinherited

returns the current graph

Definition at line 56 of file eliminationSequenceStrategy_inl.h.

56{ return graph_; }

References graph_.

Here is the caller graph for this function:

◆ isOrderNeeded()

INLINE bool gum::OrderedEliminationSequenceStrategy::isOrderNeeded ( ) const

noexcept

indicates whether a new complete ordering is needed

if the current complete ordering does not contain all the nodes of the graph or if the graph itself is not defined (nullptr) a new complete ordering will be needed for the next triangulation

Definition at line 58 of file orderedEliminationSequenceStrategy_inl.h.

                                                                               {
    return _order_needed_;
  }

References _order_needed_.

◆ newFactory()

OrderedEliminationSequenceStrategy * gum::OrderedEliminationSequenceStrategy::newFactory ( ) const

finalvirtual

creates a new elimination sequence of the same type as the current object, but this sequence contains only an empty graph

Warning: you must deallocate by yourself the object returned

Returns: an empty clone of the current object with the same type

Implements gum::EliminationSequenceStrategy.

Definition at line 105 of file orderedEliminationSequenceStrategy.cpp.

                                                                                           {
    return new OrderedEliminationSequenceStrategy();
  }

References OrderedEliminationSequenceStrategy().

Here is the call graph for this function:

◆ nextNodeToEliminate()

NodeId gum::OrderedEliminationSequenceStrategy::nextNodeToEliminate ( )

finalvirtual

returns the new node to be eliminated within the triangulation algorithm

Exceptions

NotFound exception is thrown if there is no more node to eliminate in the graph

Implements gum::EliminationSequenceStrategy.

Definition at line 170 of file orderedEliminationSequenceStrategy.cpp.

                                                                 {
    // check that we can return a nodeId
    if (_order_needed_ || (_order_->size() <= _order_index_)) {
      GUM_ERROR(NotFound, "no node id can be returned")
    }
 
    return (*_order_)[_order_index_];
  }

References _order_, _order_index_, _order_needed_, and GUM_ERROR.

◆ order()

INLINE const std::vector< NodeId > * gum::OrderedEliminationSequenceStrategy::order ( ) const

noexcept

returns the current complete ordering

Definition at line 53 of file orderedEliminationSequenceStrategy_inl.h.

                                                                                             {
    return _order_;
  }

References _order_.

Referenced by OrderedEliminationSequenceStrategy(), _isOrderNeeded_(), and setOrder().

Here is the caller graph for this function:

◆ providesFillIns()

bool gum::OrderedEliminationSequenceStrategy::providesFillIns ( ) const

finalvirtual

indicates whether the fill-ins generated by the eliminated nodes, if needed, will be computed by the elimination sequence, or need be computed by the triangulation itself.

An elimination sequence provides fill-ins to its triangulation if and only if it has the ability to compute them and it has been asked to do so (by method askFillIns)

Implements gum::EliminationSequenceStrategy.

Definition at line 188 of file orderedEliminationSequenceStrategy.cpp.

188{ return false; }

◆ providesGraphUpdate()

bool gum::OrderedEliminationSequenceStrategy::providesGraphUpdate ( ) const

finalvirtual

indicates whether the elimination sequence updates by itself the graph after a node has been eliminated

Implements gum::EliminationSequenceStrategy.

Definition at line 192 of file orderedEliminationSequenceStrategy.cpp.

192{ return false; }

◆ setGraph()

bool gum::OrderedEliminationSequenceStrategy::setGraph	(	UndiGraph *	graph,
		const NodeProperty< Size > *	dom_sizes )

finalvirtual

sets a new graph to be triangulated

The elimination sequence algorithms reinitializes its data to start a new triangulation with graph Graph

Parameters

graph	the new graph to be triangulated
dom_sizes	the domain sizes of the nodes/variables

Warning: Note that we allow dom_sizes to be defined over nodes/variables that do not belong to graph. These sizes will simply be ignored. However, it is compulsory that all the nodes of graph belong to dom_sizes; the graph is altered during the triangulation.; note that, by aGrUM's rule, the graph and the domain sizes are not copied but only referenced by the elimination sequence algorithm.

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 115 of file orderedEliminationSequenceStrategy.cpp.

                                                                                              {
    if (EliminationSequenceStrategy::setGraph(graph, domain_sizes)) {
      setOrder(_order_);
      return true;
    }
 
    return false;
  }

References _order_, gum::EliminationSequenceStrategy::graph(), gum::EliminationSequenceStrategy::setGraph(), and setOrder().

Referenced by gum::OrderedTriangulation::initTriangulation_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setOrder()

bool gum::OrderedEliminationSequenceStrategy::setOrder ( const std::vector< NodeId > * order )

finalvirtual

sets the sequence of elimination

sets a new complete order

Parameters

order the order in which the nodes should be eliminated

Returns: true if the new complete order has been successfully assigned (i.e., if all the nodes of the graph belong to one of the subsets)

Warning: note that we allow order to contain nodes that do not belong to the current graph to be triangulated: those will simply be ignored. However, all the nodes of the graph need be contained in order.; note that, by aGrUM's rule, the graph and the domain sizes are not copied but only referenced by the elimination sequence algorithm.

Definition at line 141 of file orderedEliminationSequenceStrategy.cpp.

                                                                                    {
    // check that the order contains all the nodes of the graph
    _order_needed_ = _isOrderNeeded_(order);
 
    if (!_order_needed_) {
      _order_ = order;
 
      // determine the first element in order that belong to the graph
      // here, note that we have the guarantee that  _order_index_ will be
      // lower than the size of  _order_ since all the nodes in the graph
      // belong to vector  _order_
      _order_index_ = 0;
      while (!graph_->existsNode((*_order_)[_order_index_]))
        ++_order_index_;
 
      return true;
    }
 
    return false;
  }

References _isOrderNeeded_(), _order_, _order_index_, _order_needed_, gum::EliminationSequenceStrategy::graph_, and order().

Referenced by OrderedEliminationSequenceStrategy(), gum::OrderedTriangulation::OrderedTriangulation(), gum::OrderedTriangulation::initTriangulation_(), and setGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ _order_

const std::vector< NodeId >* gum::OrderedEliminationSequenceStrategy::_order_ {nullptr}

private

the vector indicating in which order we should eliminate the nodes

Definition at line 196 of file orderedEliminationSequenceStrategy.h.

196{nullptr};

Referenced by OrderedEliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), eliminationUpdate(), nextNodeToEliminate(), order(), setGraph(), and setOrder().

◆ _order_index_

std::size_t gum::OrderedEliminationSequenceStrategy::_order_index_ {std::size_t(0)}

private

the index in the order indicating the new node to eliminate

Definition at line 199 of file orderedEliminationSequenceStrategy.h.

199{std::size_t(0)};

Referenced by OrderedEliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), clear(), eliminationUpdate(), nextNodeToEliminate(), and setOrder().

◆ _order_needed_

bool gum::OrderedEliminationSequenceStrategy::_order_needed_ {true}

private

indicate whether a new complete ordering is necessary for the elimination

Definition at line 203 of file orderedEliminationSequenceStrategy.h.

203{true};

Referenced by OrderedEliminationSequenceStrategy(), OrderedEliminationSequenceStrategy(), clear(), eliminationUpdate(), isOrderNeeded(), nextNodeToEliminate(), and setOrder().

◆ domain_sizes_

const NodeProperty< Size >* gum::EliminationSequenceStrategy::domain_sizes_ {nullptr}

protectedinherited

the domain sizes of the variables/nodes

Definition at line 177 of file eliminationSequenceStrategy.h.

177{nullptr};

Referenced by EliminationSequenceStrategy(), EliminationSequenceStrategy(), clear(), domainSizes(), and setGraph().

◆ graph_

UndiGraph* gum::EliminationSequenceStrategy::graph_ {nullptr}

protectedinherited

the graph to be triangulated

Definition at line 174 of file eliminationSequenceStrategy.h.

174{nullptr};

◆ log_domain_sizes_

NodeProperty< double > gum::EliminationSequenceStrategy::log_domain_sizes_

protectedinherited

the log of the domain sizes of the variables/nodes

Definition at line 180 of file eliminationSequenceStrategy.h.

Referenced by gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy(), gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy(), EliminationSequenceStrategy(), EliminationSequenceStrategy(), gum::DefaultEliminationSequenceStrategy::_createSimplicialSet_(), gum::DefaultPartialOrderedEliminationSequenceStrategy::_createSimplicialSet_(), clear(), and setGraph().

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

agrum/base/graphs/algorithms/triangulations/eliminationStrategies/orderedEliminationSequenceStrategy.h
agrum/base/graphs/algorithms/triangulations/eliminationStrategies/orderedEliminationSequenceStrategy.cpp
agrum/base/graphs/algorithms/triangulations/eliminationStrategies/orderedEliminationSequenceStrategy_inl.h

Public Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ OrderedEliminationSequenceStrategy() [1/4]

◆ OrderedEliminationSequenceStrategy() [2/4]

◆ OrderedEliminationSequenceStrategy() [3/4]

◆ OrderedEliminationSequenceStrategy() [4/4]

◆ ~OrderedEliminationSequenceStrategy()

Member Function Documentation

◆ _empty_fill_ins_()

◆ _isOrderNeeded_()

◆ askFillIns()

◆ clear()

◆ copyFactory()

◆ domainSizes()

◆ eliminationUpdate()

◆ fillIns()

◆ graph()

◆ isOrderNeeded()

◆ newFactory()

◆ nextNodeToEliminate()

◆ order()

◆ providesFillIns()

◆ providesGraphUpdate()

◆ setGraph()

◆ setOrder()

Member Data Documentation

◆ _order_

◆ _order_index_

◆ _order_needed_

◆ domain_sizes_

◆ graph_

◆ log_domain_sizes_