gum::OrderedEliminationSequenceStrategy Class Reference

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) More...
	OrderedEliminationSequenceStrategy (UndiGraph *graph, const NodeProperty< Size > *dom_sizes, const std::vector< NodeId > *order)
	constructor for an a priori non empty graph More...
	OrderedEliminationSequenceStrategy (const OrderedEliminationSequenceStrategy &from)
	copy constructor More...
	OrderedEliminationSequenceStrategy (OrderedEliminationSequenceStrategy &&from)
	move constructor More...
virtual	~OrderedEliminationSequenceStrategy ()
	destructor More...
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 More...
virtual OrderedEliminationSequenceStrategy *	copyFactory () const final
	virtual copy constructor More...
Accessors / Modifiers
virtual bool	setGraph (UndiGraph *graph, const NodeProperty< Size > *dom_sizes) final
	sets a new graph to be triangulated More...
virtual bool	setOrder (const std::vector< NodeId > *order) final
	sets the sequence of elimination More...
virtual void	clear () final
	clears the order (to prepare, for instance, a new elimination sequence) More...
virtual NodeId	nextNodeToEliminate () final
	returns the new node to be eliminated within the triangulation algorithm More...
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 More...
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. More...
virtual bool	providesGraphUpdate () const final
	indicates whether the elimination sequence updates by itself the graph after a node has been eliminated More...
virtual void	eliminationUpdate (const NodeId node) final
	performs all the graph/fill-ins updates provided (if any) More...
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 More...
const std::vector< NodeId > *	order () const noexcept
	returns the current complete ordering More...
bool	isOrderNeeded () const noexcept
	indicates whether a new complete ordering is needed More...
Accessors / Modifiers
UndiGraph *	graph () const noexcept
	returns the current graph More...
const NodeProperty< Size > *	domainSizes () const noexcept
	returns the current domain sizes More...

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

Detailed Description

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

Definition at line 44 of file orderedEliminationSequenceStrategy.h.

Constructor & Destructor Documentation

OrderedEliminationSequenceStrategy() [1/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy

(

)

default constructor (uses an empty graph)

Definition at line 41 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                         {
    GUM_CONSTRUCTOR(OrderedEliminationSequenceStrategy);
  }

Here is the call graph for this function:

OrderedEliminationSequenceStrategy() [2/4]

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

constructor for an a priori 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 46 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                       :
      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);
  }

Here is the call graph for this function:

OrderedEliminationSequenceStrategy() [3/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy

(

const OrderedEliminationSequenceStrategy &

from

)

copy constructor

Definition at line 64 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

OrderedEliminationSequenceStrategy() [4/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy

(

OrderedEliminationSequenceStrategy &&

from

)

move constructor

Definition at line 73 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

~OrderedEliminationSequenceStrategy()

gum::OrderedEliminationSequenceStrategy::~OrderedEliminationSequenceStrategy ( )

virtual

destructor

Definition at line 82 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                          {
    GUM_DESTRUCTOR(OrderedEliminationSequenceStrategy);
  }

Here is the call graph for this function:

Member Function Documentation

_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 110 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                                               {
    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();
  }

Here is the call 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 164 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 146 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

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

Here is the call graph for this function:

copyFactory()

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

finalvirtual

virtual copy constructor

Implements gum::EliminationSequenceStrategy.

Definition at line 93 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                                            {
    return new OrderedEliminationSequenceStrategy(*this);
  }

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 40 of file eliminationSequenceStrategy_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                                             {
    return domain_sizes_;
  }

Here is the call 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 178 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                              {
    // 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_;
    }
  }

Here is the call graph for this function:

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 198 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                             {
    return 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 36 of file eliminationSequenceStrategy_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return graph_; }

Here is the call 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 39 of file orderedEliminationSequenceStrategy_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                               {
    return _order_needed_;
  }

Here is the call graph for this function:

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 88 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                                           {
    return new 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 153 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                 {
    // 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_];
  }

Here is the call graph for this function:

order()

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

noexcept

returns the current complete ordering

Definition at line 33 of file orderedEliminationSequenceStrategy_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                                             {
    return _order_;
  }

Here is the call 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 171 of file orderedEliminationSequenceStrategy.cpp.

{ 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 175 of file orderedEliminationSequenceStrategy.cpp.

{ 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 98 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

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

    return false;
  }

Here is the call 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 124 of file orderedEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                                    {
    // 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;
  }

Here is the call 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 175 of file orderedEliminationSequenceStrategy.h.

_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 178 of file orderedEliminationSequenceStrategy.h.

_order_needed_

bool gum::OrderedEliminationSequenceStrategy::_order_needed_ {true}

private

indicate whether a new complete ordering is necessary for the elimination

Definition at line 182 of file orderedEliminationSequenceStrategy.h.

domain_sizes_

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

protectedinherited

the domain sizes of the variables/nodes

Definition at line 158 of file eliminationSequenceStrategy.h.

graph_

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

protectedinherited

the graph to be triangulated

Definition at line 155 of file eliminationSequenceStrategy.h.

log_domain_sizes_

NodeProperty< double > gum::EliminationSequenceStrategy::log_domain_sizes_

protectedinherited

the log of the domain sizes of the variables/nodes

Definition at line 161 of file eliminationSequenceStrategy.h.

---

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

• agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/orderedEliminationSequenceStrategy.h
• agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/orderedEliminationSequenceStrategy.cpp
• agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/orderedEliminationSequenceStrategy_inl.h