The base class for all elimination sequence algorithms used by triangulation algorithms. More...

#include <eliminationSequenceStrategy.h>

Inheritance diagram for gum::EliminationSequenceStrategy:

Collaboration diagram for gum::EliminationSequenceStrategy:

Public Member Functions
Accessors / Modifiers
virtual bool	setGraph (UndiGraph graph, const NodeProperty< Size > dom_sizes)
	sets a new graph to be triangulated More...

virtual NodeId	nextNodeToEliminate ()=0
	returns the new node to be eliminated within the triangulation algorithm More...

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

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

virtual bool	providesGraphUpdate () const =0
	indicates whether the elimination sequence updates by itself the graph after a node has been eliminated More...

virtual void	eliminationUpdate (const NodeId node)
	performs all the graph/fill-ins updates provided (if any) More...

virtual const EdgeSet &	fillIns ()
	in case fill-ins are provided, this function returns the fill-ins due to all the nodes eliminated so far More...

virtual void	clear ()
	clears the sequence (to prepare, for instance, a new elimination sequence) More...

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

Constructors / Destructors
virtual	~EliminationSequenceStrategy ()
	destructor More...

virtual EliminationSequenceStrategy *	newFactory () const =0
	creates a new elimination sequence of the same type as the current object, but this sequence contains only an empty graph More...

virtual EliminationSequenceStrategy *	copyFactory () const =0
	virtual copy constructor More...

	EliminationSequenceStrategy ()
	default constructor More...

	EliminationSequenceStrategy (UndiGraph graph, const NodeProperty< Size > domain_sizes)
	constructor for an a priori non empty graph More...

	EliminationSequenceStrategy (const EliminationSequenceStrategy &from)
	copy constructor More...

	EliminationSequenceStrategy (EliminationSequenceStrategy &&from)
	move constructor More...

Detailed Description

The base class for all elimination sequence algorithms used by triangulation algorithms.

Definition at line 50 of file eliminationSequenceStrategy.h.

Constructor & Destructor Documentation

◆ ~EliminationSequenceStrategy()

gum::EliminationSequenceStrategy::~EliminationSequenceStrategy ( )

virtual

destructor

Definition at line 91 of file eliminationSequenceStrategy.cpp.

                                                             {
     // for debugging purposes
     GUM_DESTRUCTOR(EliminationSequenceStrategy);
   }

◆ EliminationSequenceStrategy() [1/4]

gum::EliminationSequenceStrategy::EliminationSequenceStrategy ( )

protected

default constructor

Definition at line 56 of file eliminationSequenceStrategy.cpp.

                                                            {
     // for debugging purposes
     GUM_CONSTRUCTOR(EliminationSequenceStrategy);
   }

◆ EliminationSequenceStrategy() [2/4]

gum::EliminationSequenceStrategy::EliminationSequenceStrategy	(	UndiGraph *	graph,
		const NodeProperty< Size > *	domain_sizes
	)

protected

constructor for an a priori non empty graph

Definition at line 62 of file eliminationSequenceStrategy.cpp.

References setGraph().

                                                                  {
     EliminationSequenceStrategy::setGraph(graph, domain_sizes);
 
     // for debugging purposes
     GUM_CONSTRUCTOR(EliminationSequenceStrategy);
   }

Here is the call graph for this function:

◆ EliminationSequenceStrategy() [3/4]

gum::EliminationSequenceStrategy::EliminationSequenceStrategy ( const EliminationSequenceStrategy & from )

protected

copy constructor

Definition at line 71 of file eliminationSequenceStrategy.cpp.

                                               :
       _graph(from._graph),
       _domain_sizes(from._domain_sizes),
       _log_domain_sizes(from._log_domain_sizes) {
     // for debugging purposes
     GUM_CONS_CPY(EliminationSequenceStrategy);
   }

◆ EliminationSequenceStrategy() [4/4]

gum::EliminationSequenceStrategy::EliminationSequenceStrategy ( EliminationSequenceStrategy && from )

protected

move constructor

Definition at line 81 of file eliminationSequenceStrategy.cpp.

                                          :
       _graph(from._graph),
       _domain_sizes(from._domain_sizes),
       _log_domain_sizes(std::move(from._log_domain_sizes)) {
     // for debugging purposes
     GUM_CONS_MOV(EliminationSequenceStrategy);
   }

Member Function Documentation

◆ __empty_fill_ins()

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

staticprivate

an empty fill-ins set used by default

Definition at line 40 of file eliminationSequenceStrategy.cpp.

Referenced by fillIns().

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

Here is the caller graph for this function:

◆ askFillIns()

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

pure virtual

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

Referenced by gum::StaticTriangulation::__triangulate().

Here is the caller graph for this function:

◆ clear()

void gum::EliminationSequenceStrategy::clear ( )

virtual

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

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

Definition at line 106 of file eliminationSequenceStrategy.cpp.

References _domain_sizes, _graph, and _log_domain_sizes.

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

                                           {
     _graph = nullptr;
     _domain_sizes = nullptr;
     _log_domain_sizes.clear();
   }

Here is the caller graph for this function:

◆ copyFactory()

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

pure virtual

virtual copy constructor

Returns: a full clone of the current object

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

Referenced by gum::StaticTriangulation::StaticTriangulation().

Here is the caller graph for this function:

◆ domainSizes()

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

noexcept

returns the current domain sizes

Definition at line 44 of file eliminationSequenceStrategy_inl.h.

References _domain_sizes.

                                                                        {
     return _domain_sizes;
   }

◆ eliminationUpdate()

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

virtual

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

Definition at line 97 of file eliminationSequenceStrategy.cpp.

Referenced by gum::StaticTriangulation::__triangulate().

97 {}

Here is the caller graph for this function:

◆ fillIns()

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

virtual

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

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

Definition at line 101 of file eliminationSequenceStrategy.cpp.

References __empty_fill_ins().

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

                                                       {
     return __empty_fill_ins();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ graph()

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

noexcept

returns the current graph

Definition at line 37 of file eliminationSequenceStrategy_inl.h.

References _graph.

Referenced by setGraph().

                                                                       {
     return _graph;
   }

Here is the caller graph for this function:

◆ newFactory()

virtual EliminationSequenceStrategy* gum::EliminationSequenceStrategy::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

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

◆ nextNodeToEliminate()

virtual NodeId gum::EliminationSequenceStrategy::nextNodeToEliminate ( )

pure virtual

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

Referenced by gum::StaticTriangulation::__triangulate().

Here is the caller graph for this function:

◆ providesFillIns()

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

pure virtual

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

Referenced by gum::StaticTriangulation::__triangulate(), and gum::StaticTriangulation::fillIns().

Here is the caller graph for this function:

◆ providesGraphUpdate()

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

pure virtual

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

Referenced by gum::StaticTriangulation::__triangulate().

Here is the caller graph for this function:

◆ setGraph()

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

virtual

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

Definition at line 114 of file eliminationSequenceStrategy.cpp.

References _domain_sizes, _graph, _log_domain_sizes, clear(), gum::HashTable< Key, Val, Alloc >::exists(), graph(), GUM_ERROR, and gum::NodeGraphPart::sizeNodes().

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

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

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}

protected

the domain sizes of the variables/nodes

Definition at line 159 of file eliminationSequenceStrategy.h.

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

◆ _graph

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

protected

the graph to be triangulated

Definition at line 156 of file eliminationSequenceStrategy.h.

◆ _log_domain_sizes

NodeProperty< double > gum::EliminationSequenceStrategy::_log_domain_sizes

protected

the log of the domain sizes of the variables/nodes

Definition at line 162 of file eliminationSequenceStrategy.h.

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

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

agrum/graphs/algorithms/triangulations/eliminationStrategies/eliminationSequenceStrategy.h
agrum/graphs/algorithms/triangulations/eliminationStrategies/eliminationSequenceStrategy.cpp
agrum/graphs/algorithms/triangulations/eliminationStrategies/eliminationSequenceStrategy_inl.h

Public Member Functions

Protected Attributes

Constructors / Destructors

Detailed Description

Constructor & Destructor Documentation

◆ ~EliminationSequenceStrategy()

◆ EliminationSequenceStrategy() [1/4]

◆ EliminationSequenceStrategy() [2/4]

◆ EliminationSequenceStrategy() [3/4]

◆ EliminationSequenceStrategy() [4/4]

Member Function Documentation

◆ __empty_fill_ins()

◆ askFillIns()

◆ clear()

◆ copyFactory()

◆ domainSizes()

◆ eliminationUpdate()

◆ fillIns()

◆ graph()

◆ newFactory()

◆ nextNodeToEliminate()

◆ providesFillIns()

◆ providesGraphUpdate()

◆ setGraph()

Member Data Documentation

◆ _domain_sizes

◆ _graph

◆ _log_domain_sizes