gum::UnconstrainedEliminationSequenceStrategy Class Reference

The base class for all elimination sequence algorithms that require only the graph to be triangulated and the nodes' domain sizes to produce the node elimination ordering. More...

#include <unconstrainedEliminationSequenceStrategy.h>

Inheritance diagram for gum::UnconstrainedEliminationSequenceStrategy:

Collaboration diagram for gum::UnconstrainedEliminationSequenceStrategy:

Public Member Functions
Accessors / Modifiers
virtual bool	setGraph (UndiGraph *graph, const NodeProperty< Size > *dom_sizes)
	sets a new graph to be triangulated
virtual NodeId	nextNodeToEliminate ()=0
	returns the new node to be eliminated within the triangulation algorithm
virtual void	askFillIns (bool do_it)=0
	if the elimination sequence is able to compute fill-ins, we indicate whether we want this feature to be activated
virtual bool	providesFillIns () const =0
	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 =0
	indicates whether the elimination sequence updates by itself the graph after a node has been eliminated
virtual void	eliminationUpdate (const NodeId node)
	performs all the graph/fill-ins updates provided (if any)
virtual const EdgeSet &	fillIns ()
	in case fill-ins are provided, this function returns the fill-ins due to all the nodes eliminated so far
virtual void	clear ()
	clears the sequence (to prepare, for instance, a new elimination sequence)
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

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

Constructors / Destructors
virtual	~UnconstrainedEliminationSequenceStrategy ()
	destructor
virtual UnconstrainedEliminationSequenceStrategy *	newFactory () const =0
	creates a new elimination sequence of the same type as the current object, but this sequence contains only an empty graph
virtual UnconstrainedEliminationSequenceStrategy *	copyFactory () const =0
	virtual copy constructor
	UnconstrainedEliminationSequenceStrategy ()
	default constructor
	UnconstrainedEliminationSequenceStrategy (UndiGraph *graph, const NodeProperty< Size > *dom_sizes)
	constructor for a (tensorly) non empty graph
	UnconstrainedEliminationSequenceStrategy (const UnconstrainedEliminationSequenceStrategy &)
	copy constructor
	UnconstrainedEliminationSequenceStrategy (UnconstrainedEliminationSequenceStrategy &&)
	move constructor

Detailed Description

The base class for all elimination sequence algorithms that require only the graph to be triangulated and the nodes' domain sizes to produce the node elimination ordering.

Definition at line 79 of file unconstrainedEliminationSequenceStrategy.h.

Constructor & Destructor Documentation

~UnconstrainedEliminationSequenceStrategy()

gum::UnconstrainedEliminationSequenceStrategy::~UnconstrainedEliminationSequenceStrategy ( )

virtual

destructor

Definition at line 81 of file unconstrainedEliminationSequenceStrategy.cpp.

                                                                                      {
    GUM_DESTRUCTOR(UnconstrainedEliminationSequenceStrategy);
  }

References UnconstrainedEliminationSequenceStrategy().

Here is the call graph for this function:

UnconstrainedEliminationSequenceStrategy() [1/4]

gum::UnconstrainedEliminationSequenceStrategy::UnconstrainedEliminationSequenceStrategy ( )

protected

default constructor

Definition at line 56 of file unconstrainedEliminationSequenceStrategy.cpp.

                                                                                     {
    GUM_CONSTRUCTOR(UnconstrainedEliminationSequenceStrategy);
  }

References UnconstrainedEliminationSequenceStrategy().

Referenced by gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy(), gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy(), UnconstrainedEliminationSequenceStrategy(), UnconstrainedEliminationSequenceStrategy(), UnconstrainedEliminationSequenceStrategy(), UnconstrainedEliminationSequenceStrategy(), ~UnconstrainedEliminationSequenceStrategy(), copyFactory(), and newFactory().

Here is the call graph for this function:

Here is the caller graph for this function:

UnconstrainedEliminationSequenceStrategy() [2/4]

gum::UnconstrainedEliminationSequenceStrategy::UnconstrainedEliminationSequenceStrategy ( UndiGraph * graph, const NodeProperty< Size > * dom_sizes )

protected

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	the domain sizes of the nodes to be eliminated

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.

Definition at line 61 of file unconstrainedEliminationSequenceStrategy.cpp.

                                             : EliminationSequenceStrategy(graph, dom_sizes) {
    GUM_CONSTRUCTOR(UnconstrainedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), UnconstrainedEliminationSequenceStrategy(), and gum::EliminationSequenceStrategy::graph().

Here is the call graph for this function:

UnconstrainedEliminationSequenceStrategy() [3/4]

gum::UnconstrainedEliminationSequenceStrategy::UnconstrainedEliminationSequenceStrategy ( const UnconstrainedEliminationSequenceStrategy & from )

protected

copy constructor

Definition at line 68 of file unconstrainedEliminationSequenceStrategy.cpp.

                                                            : EliminationSequenceStrategy(from) {
    GUM_CONS_CPY(UnconstrainedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), and UnconstrainedEliminationSequenceStrategy().

Here is the call graph for this function:

UnconstrainedEliminationSequenceStrategy() [4/4]

gum::UnconstrainedEliminationSequenceStrategy::UnconstrainedEliminationSequenceStrategy ( UnconstrainedEliminationSequenceStrategy && from )

protected

move constructor

Definition at line 74 of file unconstrainedEliminationSequenceStrategy.cpp.

                                                       :
      EliminationSequenceStrategy(std::move(from)) {
    GUM_CONS_MOV(UnconstrainedEliminationSequenceStrategy)
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), and UnconstrainedEliminationSequenceStrategy().

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:

askFillIns()

virtual void gum::EliminationSequenceStrategy::askFillIns ( bool do_it )

pure virtualinherited

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.

Implemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, and gum::OrderedEliminationSequenceStrategy.

clear()

void gum::EliminationSequenceStrategy::clear ( )

virtualinherited

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

Reimplemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, gum::OrderedEliminationSequenceStrategy, and gum::PartialOrderedEliminationSequenceStrategy.

Definition at line 119 of file eliminationSequenceStrategy.cpp.

                                          {
    graph_        = nullptr;
    domain_sizes_ = nullptr;
    log_domain_sizes_.clear();
  }

References domain_sizes_, graph_, and log_domain_sizes_.

Referenced by gum::DefaultEliminationSequenceStrategy::clear(), gum::OrderedEliminationSequenceStrategy::clear(), gum::PartialOrderedEliminationSequenceStrategy::clear(), and setGraph().

Here is the caller graph for this function:

copyFactory()

virtual UnconstrainedEliminationSequenceStrategy * gum::UnconstrainedEliminationSequenceStrategy::copyFactory ( ) const

pure virtual

virtual copy constructor

Implements gum::EliminationSequenceStrategy.

Implemented in gum::DefaultEliminationSequenceStrategy.

References UnconstrainedEliminationSequenceStrategy(), and gum::EliminationSequenceStrategy::graph().

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

virtualinherited

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

Parameters

node	the node the elimination of which requires the graph update

Reimplemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, and gum::OrderedEliminationSequenceStrategy.

Definition at line 112 of file eliminationSequenceStrategy.cpp.

{}

fillIns()

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

virtualinherited

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

Reimplemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, and gum::OrderedEliminationSequenceStrategy.

Definition at line 116 of file eliminationSequenceStrategy.cpp.

{ return _empty_fill_ins_(); }

References _empty_fill_ins_().

Referenced by gum::DefaultEliminationSequenceStrategy::fillIns(), gum::DefaultPartialOrderedEliminationSequenceStrategy::fillIns(), and gum::OrderedEliminationSequenceStrategy::fillIns().

Here is the call graph for this function:

Here is the caller 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.

{ return graph_; }

References graph_.

Referenced by gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy(), gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy(), EliminationSequenceStrategy(), gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy(), gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy(), gum::UnconstrainedEliminationSequenceStrategy::UnconstrainedEliminationSequenceStrategy(), copyFactory(), gum::PartialOrderedEliminationSequenceStrategy::copyFactory(), gum::UnconstrainedEliminationSequenceStrategy::copyFactory(), gum::DefaultEliminationSequenceStrategy::setGraph(), gum::DefaultPartialOrderedEliminationSequenceStrategy::setGraph(), setGraph(), gum::OrderedEliminationSequenceStrategy::setGraph(), and gum::PartialOrderedEliminationSequenceStrategy::setGraph().

Here is the caller graph for this function:

newFactory()

virtual UnconstrainedEliminationSequenceStrategy * gum::UnconstrainedEliminationSequenceStrategy::newFactory ( ) const

pure virtual

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.

Implemented in gum::DefaultEliminationSequenceStrategy.

References UnconstrainedEliminationSequenceStrategy().

Here is the call graph for this function:

nextNodeToEliminate()

virtual NodeId gum::EliminationSequenceStrategy::nextNodeToEliminate ( )

pure virtualinherited

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

Implemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, and gum::OrderedEliminationSequenceStrategy.

providesFillIns()

virtual bool gum::EliminationSequenceStrategy::providesFillIns ( ) const

pure virtualinherited

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)

Implemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, and gum::OrderedEliminationSequenceStrategy.

providesGraphUpdate()

virtual bool gum::EliminationSequenceStrategy::providesGraphUpdate ( ) const

pure virtualinherited

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

Some algorithms have more informations than the triangulation algorithm to update the graph after a node has been eliminated. They can thus exploit these informations to update the graph faster than the triangulation itself. Hence the latter should delegate this operation to the elimination sequence. This is the case, for instance, for the defaultEliminationSequenceStrategy, which uses a SimplicialSet that knows that some eliminated nodes do not require any fill-in.

Implemented in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, and gum::OrderedEliminationSequenceStrategy.

References domainSizes().

Here is the call graph for this function:

setGraph()

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

virtualinherited

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 variables/nodes

Returns

true if the data structures were modified (if the graph or the domain sizes did not change, then there is no need to update the data structures).

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 can be 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 in gum::DefaultEliminationSequenceStrategy, gum::DefaultPartialOrderedEliminationSequenceStrategy, gum::OrderedEliminationSequenceStrategy, and gum::PartialOrderedEliminationSequenceStrategy.

Definition at line 126 of file eliminationSequenceStrategy.cpp.

                                                                                    {
    // check that both the graph and the domain sizes are different from nullptr
    // or else that both are equal to nullptr
    if (((graph != nullptr) && (dom_sizes == nullptr))
        || ((graph == nullptr) && (dom_sizes != nullptr))) {
      GUM_ERROR(GraphError,
                "EliminationSequenceStrategy: one of the graph or the set of "
                "domain sizes is a null pointer.");
    }
 
    // check that each node has a domain size
    if (graph != nullptr) {
      for (const auto node: *graph)
        if (!dom_sizes->exists(node))
          GUM_ERROR(GraphError,
                    "EliminationSequenceStrategy needs a domain size "
                    "for every node in the graph.");
    }
 
    // avoid empty modifications
    if ((graph != graph_) || (dom_sizes != domain_sizes_)) {
      // remove, if any, the current graph
      clear();
 
      // assign a new graph
      graph_        = graph;
      domain_sizes_ = dom_sizes;
 
      if (graph_ != nullptr) {
        // compute the log of the modalities
        log_domain_sizes_.resize(graph_->sizeNodes() / 2);
 
        for (const auto node: *graph_)
          log_domain_sizes_.insert(node, std::log((*domain_sizes_)[node]));
      }
 
      return true;
    }
 
    return false;
  }

References clear(), domain_sizes_, gum::HashTable< Key, Val >::exists(), graph(), graph_, GUM_ERROR, and log_domain_sizes_.

Referenced by EliminationSequenceStrategy(), gum::DefaultEliminationSequenceStrategy::setGraph(), gum::OrderedEliminationSequenceStrategy::setGraph(), and gum::PartialOrderedEliminationSequenceStrategy::setGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

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.

{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.

{nullptr};

Referenced by gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy(), gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy(), EliminationSequenceStrategy(), EliminationSequenceStrategy(), gum::DefaultEliminationSequenceStrategy::_createSimplicialSet_(), gum::DefaultPartialOrderedEliminationSequenceStrategy::_createSimplicialSet_(), gum::OrderedEliminationSequenceStrategy::_isOrderNeeded_(), clear(), gum::DefaultPartialOrderedEliminationSequenceStrategy::eliminationUpdate(), gum::OrderedEliminationSequenceStrategy::eliminationUpdate(), graph(), gum::PartialOrderedEliminationSequenceStrategy::isPartialOrderNeeded_(), gum::DefaultEliminationSequenceStrategy::nextNodeToEliminate(), gum::DefaultPartialOrderedEliminationSequenceStrategy::nextNodeToEliminate(), setGraph(), gum::OrderedEliminationSequenceStrategy::setOrder(), and gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder().

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/unconstrainedEliminationSequenceStrategy.h
• agrum/base/graphs/algorithms/triangulations/eliminationStrategies/unconstrainedEliminationSequenceStrategy.cpp