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

#include <defaultPartialOrderedEliminationSequenceStrategy.h>

Inheritance diagram for gum::DefaultPartialOrderedEliminationSequenceStrategy:

Collaboration diagram for gum::DefaultPartialOrderedEliminationSequenceStrategy:

Public Member Functions
Constructors / Destructors
	DefaultPartialOrderedEliminationSequenceStrategy (double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
	default constructor (uses an empty graph)
	DefaultPartialOrderedEliminationSequenceStrategy (UndiGraph graph, const NodeProperty< Size > dom_sizes, const List< NodeSet > *subsets, double ratio=GUM_QUASI_RATIO, double threshold=GUM_WEIGHT_THRESHOLD)
	constructor for a (tensorly) non empty graph
	DefaultPartialOrderedEliminationSequenceStrategy (const DefaultPartialOrderedEliminationSequenceStrategy &from)
	copy constructor
	DefaultPartialOrderedEliminationSequenceStrategy (DefaultPartialOrderedEliminationSequenceStrategy &&from)
	move constructor
	~DefaultPartialOrderedEliminationSequenceStrategy () override
	destructor
DefaultPartialOrderedEliminationSequenceStrategy *	newFactory () const final
	creates a new elimination sequence of the same type as the current object, but this sequence contains only an empty graph
DefaultPartialOrderedEliminationSequenceStrategy *	copyFactory () const final
	virtual copy constructor
Accessors / Modifiers
bool	setGraph (UndiGraph graph, const NodeProperty< Size > dom_sizes) final
	sets a new graph to be triangulated
void	clear () final
	clears the sequence (to prepare, for instance, a new elimination sequence)
NodeId	nextNodeToEliminate () final
	returns the new node to be eliminated within the triangulation algorithm
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
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.
bool	providesGraphUpdate () const final
	indicates whether the elimination sequence updates by itself the graph after a node has been eliminated
void	eliminationUpdate (const NodeId node) final
	performs all the graph/fill-ins updates provided (if any)
const EdgeSet &	fillIns () final
	in case fill-ins are provided, this function returns the fill-ins due to all the nodes eliminated so far
Accessors / Modifiers
virtual bool	setPartialOrder (const List< NodeSet > *subsets)
	sets a new partial ordering constraint on the elimination sequence
const List< NodeSet > *	partialOrder () const noexcept
	returns the current partial ordering
bool	isPartialOrderNeeded () const noexcept
	indicates if a new partial 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 Member Functions
bool	isPartialOrderNeeded_ (const List< NodeSet > *subsets) const
	indicate whether a partial ordering is compatible with the current graph

Protected Attributes
const List< NodeSet > *	subsets_ {nullptr}
	the subsets constituting the partial ordering
List< NodeSet >::const_iterator	subset_iter_
	the iterator indicating which is the current subset on which we work
NodeSet	nodeset_
	the nodes which can be currently eliminated
bool	partial_order_needed_ {true}
	indicate whether a new partial ordering is necessary for the elimination
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
NodeId	_nodeToEliminate_ (const PriorityQueue< NodeId, double > &possibleNodes)
	returns the best possible node to be eliminated
void	_createSimplicialSet_ ()
	create a new simplicial set suited for the current graph

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

Private Attributes
NodeProperty< double >	_log_weights_
	for each node, the weight of the clique created by the node's elimination
SimplicialSet *	_simplicial_set_ {nullptr}
	the simplicial set used for determining the best nodes to eliminate
double	_simplicial_ratio_
	the ratio used by simplicial_set for its quasi-simplicial nodes
double	_simplicial_threshold_
	the threshold used by simplicial_set to determine small cliques
bool	_provide_fill_ins_ {false}
	indicates whether we compute new fill-ins

Detailed Description

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

Class DefaultPartialOrderedEliminationSequenceStrategy implements an elimination sequence algorithm that satisfies a partial ordering, that is, the set of all the nodes is divided into several subsets. All the nodes of the first subset must be eliminated before the nodes of the second, which must be eliminated before those of the third subset, and so on. Within a subset, the ordering is determined as follows:

the nodes that are simplicial (i.e., those that already form a clique

with their neighbors) are eliminated first

then the nodes that are almost simplicial (i.e. if we remove one of their

neighbors, they become simplicial) and that create small cliques, are eliminated (see Bodlaender's safe reductions)

the quasi simplicial nodes (i.e., the nodes that do not require many

fill-ins to create cliques) that would create small cliques, are eliminated

finally, the heuristic proposed by Kjaerulff(90) is used to compute the

last nodes to be eliminated.

Definition at line 99 of file defaultPartialOrderedEliminationSequenceStrategy.h.

Constructor & Destructor Documentation

◆ DefaultPartialOrderedEliminationSequenceStrategy() [1/4]

gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy	(	double	theRatio = GUM_QUASI_RATIO,
		double	theThreshold = GUM_WEIGHT_THRESHOLD )

default constructor (uses an empty graph)

Parameters

theRatio	the ratio used by the SimplicialSet included in the DefaultEliminationSequenceStrategy
theThreshold	the weight threshhold of the SimplicialSet included in the DefaultEliminationSequenceStrategy

Definition at line 58 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                                             :
      _simplicial_ratio_(theRatio), _simplicial_threshold_(theThreshold) {
    // for debugging purposes
    GUM_CONSTRUCTOR(DefaultPartialOrderedEliminationSequenceStrategy);
  }

References DefaultPartialOrderedEliminationSequenceStrategy(), _simplicial_ratio_, and _simplicial_threshold_.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DefaultPartialOrderedEliminationSequenceStrategy() [2/4]

gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy	(	UndiGraph *	graph,
		const NodeProperty< Size > *	dom_sizes,
		const List< NodeSet > *	subsets,
		double	ratio = GUM_QUASI_RATIO,
		double	threshold = GUM_WEIGHT_THRESHOLD )

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
subsets	the list of the subsets constituting the partial ordering
ratio	the ratio used by the SimplicialSet included in the DefaultEliminationSequenceStrategy
threshold	the weight threshhold of the SimplicialSet included in the DefaultEliminationSequenceStrategy

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, the domain sizes and the sequence are not copied but only referenced by the elimination sequence algorithm.

Definition at line 66 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                                              :
      _simplicial_ratio_(ratio), _simplicial_threshold_(threshold) {
    setGraph(graph, dom_sizes);
    setPartialOrder(subsets);
 
    // for debugging purposes
    GUM_CONSTRUCTOR(DefaultPartialOrderedEliminationSequenceStrategy);
  }

References DefaultPartialOrderedEliminationSequenceStrategy(), _simplicial_ratio_, _simplicial_threshold_, setGraph(), and gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder().

Here is the call graph for this function:

◆ DefaultPartialOrderedEliminationSequenceStrategy() [3/4]

gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy ( const DefaultPartialOrderedEliminationSequenceStrategy & from )

copy constructor

Warning: The newly created elimination sequence strategy points toward the same undirected graph as the one contained in from but each strategy possesses its own simplicial set. As a result, if both elimination strategies are used at the same time, they will probably result in a mess because their simplicial sets won't be synchronized correctly with the changing undirected graph. So, whenever using this copy constructor, be sure that either from or the newly created strategy is used for a triangulation but not both. This will necessarily be OK in DefaultTriangulations.

Definition at line 81 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                        :
      PartialOrderedEliminationSequenceStrategy(from),
      // no need to set  _log_weights_ because the copy of the simplicial set
      // will set it properly
      _simplicial_set_(new SimplicialSet(*from._simplicial_set_,
                                         graph_,
                                         &log_domain_sizes_,
                                         &_log_weights_,
                                         false)),
      _simplicial_ratio_(from._simplicial_ratio_),
      _simplicial_threshold_(from._simplicial_threshold_),
      _provide_fill_ins_(from._provide_fill_ins_) {
    // for debugging purposes
    GUM_CONS_CPY(DefaultPartialOrderedEliminationSequenceStrategy);
  }

References DefaultPartialOrderedEliminationSequenceStrategy(), gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy(), _log_weights_, _provide_fill_ins_, _simplicial_ratio_, _simplicial_set_, _simplicial_threshold_, gum::EliminationSequenceStrategy::graph_, and gum::EliminationSequenceStrategy::log_domain_sizes_.

Here is the call graph for this function:

◆ DefaultPartialOrderedEliminationSequenceStrategy() [4/4]

gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy ( DefaultPartialOrderedEliminationSequenceStrategy && from )

move constructor

Definition at line 100 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                   :
      PartialOrderedEliminationSequenceStrategy(std::move(from)),
      _log_weights_(std::move(from._log_weights_)), _simplicial_set_(from._simplicial_set_),
      _simplicial_ratio_(from._simplicial_ratio_),
      _simplicial_threshold_(from._simplicial_threshold_),
      _provide_fill_ins_(from._provide_fill_ins_) {
    _simplicial_set_->replaceLogWeights(&from._log_weights_, &_log_weights_);
    from._simplicial_set_ = nullptr;
 
    // for debugging purposes
    GUM_CONS_MOV(DefaultPartialOrderedEliminationSequenceStrategy);
  }

References DefaultPartialOrderedEliminationSequenceStrategy(), gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy(), _log_weights_, _provide_fill_ins_, _simplicial_ratio_, _simplicial_set_, and _simplicial_threshold_.

Here is the call graph for this function:

◆ ~DefaultPartialOrderedEliminationSequenceStrategy()

gum::DefaultPartialOrderedEliminationSequenceStrategy::~DefaultPartialOrderedEliminationSequenceStrategy ( )

override

destructor

Definition at line 116 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                          {
    // for debugging purposes
    GUM_DESTRUCTOR(DefaultPartialOrderedEliminationSequenceStrategy);
 
    if (_simplicial_set_) delete _simplicial_set_;
  }

References DefaultPartialOrderedEliminationSequenceStrategy(), and _simplicial_set_.

Here is the call graph for this function:

Member Function Documentation

◆ _createSimplicialSet_()

void gum::DefaultPartialOrderedEliminationSequenceStrategy::_createSimplicialSet_ ( )

private

create a new simplicial set suited for the current graph

Definition at line 125 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                               {
    // remove the old simplicial set, if any
    if (_simplicial_set_ != nullptr) {
      delete _simplicial_set_;
      _simplicial_set_ = nullptr;
    }
 
    if (graph_ != nullptr) {
      // create a simplicial set suited for the graph
      _simplicial_set_ = new SimplicialSet(graph_,
                                           &log_domain_sizes_,
                                           &_log_weights_,
                                           _simplicial_ratio_,
                                           _simplicial_threshold_);
 
      _simplicial_set_->setFillIns(_provide_fill_ins_);
    }
  }

References _log_weights_, _provide_fill_ins_, _simplicial_ratio_, _simplicial_set_, _simplicial_threshold_, gum::EliminationSequenceStrategy::graph_, and gum::EliminationSequenceStrategy::log_domain_sizes_.

Referenced by setGraph().

Here is the caller graph for this function:

◆ _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:

◆ _nodeToEliminate_()

NodeId gum::DefaultPartialOrderedEliminationSequenceStrategy::_nodeToEliminate_ ( const PriorityQueue< NodeId, double > & possibleNodes )

private

returns the best possible node to be eliminated

this function is used by method nextNodeToEliminate

Definition at line 168 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                            {
    bool   found     = false;
    double min_score = 0;
    NodeId best_node = 0;
 
    for (const auto node: nodeset_) {
      if (possibleNodes.contains(node)) {
        double score = possibleNodes.priority(node);
 
        if (!found || (score < min_score)) {
          found     = true;
          min_score = score;
          best_node = node;
        }
      }
    }
 
    if (!found) { GUM_ERROR(NotFound, "no possible node to eliminate") }
 
    return best_node;
  }

References gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::contains(), GUM_ERROR, gum::PartialOrderedEliminationSequenceStrategy::nodeset_, and gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::priority().

Referenced by nextNodeToEliminate().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ askFillIns()

void gum::DefaultPartialOrderedEliminationSequenceStrategy::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

if the elimination sequence is able to compute fill-ins, we indicatewhether 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 243 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                              {
    _provide_fill_ins_ = do_it;
 
    if (_simplicial_set_) _simplicial_set_->setFillIns(_provide_fill_ins_);
  }

References _provide_fill_ins_, and _simplicial_set_.

◆ clear()

void gum::DefaultPartialOrderedEliminationSequenceStrategy::clear ( )

finalvirtual

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

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 157 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                               {
    PartialOrderedEliminationSequenceStrategy::clear();
    _log_weights_.clear();
 
    if (_simplicial_set_ != nullptr) {
      delete _simplicial_set_;
      _simplicial_set_ = nullptr;
    }
  }

References _log_weights_, _simplicial_set_, and gum::PartialOrderedEliminationSequenceStrategy::clear().

Here is the call graph for this function:

◆ copyFactory()

DefaultPartialOrderedEliminationSequenceStrategy * gum::DefaultPartialOrderedEliminationSequenceStrategy::copyFactory ( ) const

nodiscardfinalvirtual

virtual copy constructor

Warning: The newly created elimination sequence strategy points toward the same undirected graph as the one contained in the current strategy but each strategy possesses its own simplicial set. As a result, if both elimination strategies are used at the same time, they will probably result in a mess because their simplicial sets won't be synchronized correctly with the changing undirected graph. So, whenever using this virtual copy constructor, be sure that either the current or the newly created strategy is used for a triangulation but not both. This will necessarily be OK in DefaultTriangulations.

Implements gum::PartialOrderedEliminationSequenceStrategy.

Definition at line 304 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                          {
    return new DefaultPartialOrderedEliminationSequenceStrategy(*this);
  }

References DefaultPartialOrderedEliminationSequenceStrategy().

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 62 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::DefaultPartialOrderedEliminationSequenceStrategy::eliminationUpdate ( const NodeId node )

finalvirtual

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

performs all the graph/fill-ins updates provided

Parameters

node	the node the elimination of which requires the graph update

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 263 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                                          {
    // check whether we can do something
    if (_simplicial_set_ != nullptr) {
      _simplicial_set_->makeClique(id);
      _simplicial_set_->eraseClique(id);
 
      if (!partial_order_needed_) {
        // remove the node from nodeset_
        nodeset_.erase(id);
 
        if (nodeset_.empty()) {
          // go to the next non-empty subset
          for (++subset_iter_; subset_iter_ != subsets_->cend(); ++subset_iter_) {
            for (const auto node: *subset_iter_) {
              if (graph_->existsNode(node)) { nodeset_.insert(node); }
            }
            if (!nodeset_.empty()) break;
          }
        }
      }
    }
  }

References _simplicial_set_, gum::EliminationSequenceStrategy::graph_, gum::PartialOrderedEliminationSequenceStrategy::nodeset_, gum::PartialOrderedEliminationSequenceStrategy::partial_order_needed_, gum::PartialOrderedEliminationSequenceStrategy::subset_iter_, and gum::PartialOrderedEliminationSequenceStrategy::subsets_.

◆ fillIns()

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

finalvirtual

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

in case fill-ins are provided, this function returns the fill-ins generated after the last node elimination

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 288 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                           {
    if (!_provide_fill_ins_ || (_simplicial_set_ == nullptr))
      return EliminationSequenceStrategy::fillIns();
    else return _simplicial_set_->fillIns();
  }

References _provide_fill_ins_, _simplicial_set_, and 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 59 of file eliminationSequenceStrategy_inl.h.

59{ return graph_; }

References graph_.

Here is the caller graph for this function:

◆ isPartialOrderNeeded()

INLINE bool gum::PartialOrderedEliminationSequenceStrategy::isPartialOrderNeeded ( ) const

noexceptinherited

indicates if a new partial ordering is needed

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

Definition at line 66 of file partialOrderedEliminationSequenceStrategy_inl.h.

                                                                                             {
    return partial_order_needed_;
  }

References partial_order_needed_.

Referenced by copyFactory().

Here is the caller graph for this function:

◆ isPartialOrderNeeded_()

bool gum::PartialOrderedEliminationSequenceStrategy::isPartialOrderNeeded_ ( const List< NodeSet > * subsets ) const

protectedinherited

indicate whether a partial ordering is compatible with the current graph

The method checks whether all the nodes of the graph belong to the partial ordering.

Returns: true if some nodes in graph_ do not belong to subsets or if graph_ is not defnined (nullptr)

Definition at line 118 of file partialOrderedEliminationSequenceStrategy.cpp.

                                            {
    if ((graph_ == nullptr) || (subsets == nullptr)) return true;
 
    // determine the set of nodes in the subsets that belong to the graph
    NodeSet nodes_found(graph_->size() / 2);
    for (const auto& nodes: *subsets) {
      for (const auto node: nodes) {
        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(), and gum::Set< Key >::size().

Referenced by setPartialOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ newFactory()

DefaultPartialOrderedEliminationSequenceStrategy * gum::DefaultPartialOrderedEliminationSequenceStrategy::newFactory ( ) const

nodiscardfinalvirtual

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::PartialOrderedEliminationSequenceStrategy.

Definition at line 297 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                         {
    return new DefaultPartialOrderedEliminationSequenceStrategy(_simplicial_ratio_,
                                                                _simplicial_threshold_);
  }

References DefaultPartialOrderedEliminationSequenceStrategy(), _simplicial_ratio_, and _simplicial_threshold_.

Here is the call graph for this function:

◆ nextNodeToEliminate()

NodeId gum::DefaultPartialOrderedEliminationSequenceStrategy::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 192 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                               {
    // if there is no simplicial set, send an exception
    if (graph_ == nullptr) GUM_ERROR(NotFound, "the graph is empty")
 
    if (partial_order_needed_)
      GUM_ERROR(NotFound,
                "the partial order does not cover all the nodes "
                "of the graph");
 
    if (nodeset_.empty()) { GUM_ERROR(NotFound, "no node is admissible") }
 
    // select a node to be eliminated: try simplicial nodes, then almost
    // simplicial nodes, then quasi-simplicial nodes
    // note that if graph_ != nullptr,  _simplicial_set_ has been allocated
    if (!_simplicial_set_->allSimplicialNodes().empty()) {
      try {
        return _nodeToEliminate_(_simplicial_set_->allSimplicialNodes());
      } catch (NotFound const&) {}
    }
 
    if (!_simplicial_set_->allAlmostSimplicialNodes().empty()) {
      try {
        return _nodeToEliminate_(_simplicial_set_->allAlmostSimplicialNodes());
      } catch (NotFound const&) {}
    }
 
    if (!_simplicial_set_->allQuasiSimplicialNodes().empty()) {
      try {
        return _nodeToEliminate_(_simplicial_set_->allQuasiSimplicialNodes());
      } catch (NotFound const&) {}
    }
 
    // here: select the node through Kjaerulff's heuristic
    auto   iter      = nodeset_.cbegin();
    double min_score = _log_weights_[*iter];
    NodeId best_node = *iter;
 
    for (++iter; iter != nodeset_.cend(); ++iter) {
      double score = _log_weights_[*iter];
 
      if (score < min_score) {
        min_score = score;
        best_node = *iter;
      }
    }
 
    return best_node;
  }

References _log_weights_, _nodeToEliminate_(), _simplicial_set_, gum::EliminationSequenceStrategy::graph_, GUM_ERROR, gum::PartialOrderedEliminationSequenceStrategy::nodeset_, and gum::PartialOrderedEliminationSequenceStrategy::partial_order_needed_.

Here is the call graph for this function:

◆ partialOrder()

INLINE const List< NodeSet > * gum::PartialOrderedEliminationSequenceStrategy::partialOrder ( ) const

noexceptinherited

returns the current partial ordering

Definition at line 61 of file partialOrderedEliminationSequenceStrategy_inl.h.

                                                                                      {
    return subsets_;
  }

References subsets_.

◆ providesFillIns()

bool gum::DefaultPartialOrderedEliminationSequenceStrategy::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.

indicates whether the new fill-ins generated by a new eliminated node, 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 252 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                               {
    return _provide_fill_ins_;
  }

References _provide_fill_ins_.

◆ providesGraphUpdate()

bool gum::DefaultPartialOrderedEliminationSequenceStrategy::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 258 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                                                   {
    return true;
  }

◆ setGraph()

bool gum::DefaultPartialOrderedEliminationSequenceStrategy::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 and a new partial ordrering

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 145 of file defaultPartialOrderedEliminationSequenceStrategy.cpp.

                                                {
    if (PartialOrderedEliminationSequenceStrategy::setGraph(graph, domain_sizes)) {
      _createSimplicialSet_();
      return true;
    }
 
    return false;
  }

References _createSimplicialSet_(), and gum::PartialOrderedEliminationSequenceStrategy::setGraph().

Referenced by DefaultPartialOrderedEliminationSequenceStrategy().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setPartialOrder()

bool gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder ( const List< NodeSet > * subsets )

virtualinherited

sets a new partial ordering constraint on the elimination sequence

sets a new partial order

Parameters

subsets the list of the subsets constituting the partial ordering

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

Warning: if the subsets contain some nodes that do not belong to the graph, then these nodes are simply ignored.; note that, by aGrUM's rule, the partial ordering is not copied but only referenced by the elimination sequence algorithm.

Definition at line 135 of file partialOrderedEliminationSequenceStrategy.cpp.

                                                                                                {
    // check that the partial order contains all the nodes of the graph
    partial_order_needed_ = isPartialOrderNeeded_(subsets);
 
    if (!partial_order_needed_) {
      subsets_ = subsets;
 
      // initialize properly the set of nodes that can be currently eliminated:
      // find the first subset that contains some node(s) of the graph
      nodeset_.clear();
      for (subset_iter_ = subsets_->cbegin(); subset_iter_ != subsets_->cend(); ++subset_iter_) {
        for (const auto node: *subset_iter_) {
          if (graph_->existsNode(node)) { nodeset_.insert(node); }
        }
        if (!nodeset_.empty()) return true;
      }
    }
 
    return false;
  }