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

Constructor & Destructor Documentation

◆ OrderedEliminationSequenceStrategy() [1/4]

gum::OrderedEliminationSequenceStrategy::OrderedEliminationSequenceStrategy ( )

default constructor (uses an empty graph)

Definition at line 39 of file orderedEliminationSequenceStrategy.cpp.

Referenced by copyFactory(), and newFactory().

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

Here is the caller graph for this function:

◆ OrderedEliminationSequenceStrategy() [2/4]

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

constructor for 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 45 of file orderedEliminationSequenceStrategy.cpp.

References GUM_ERROR, and setOrder().

                                        :
       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);
 
     // for debugging purposes
     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 65 of file orderedEliminationSequenceStrategy.cpp.

                                                      :
       EliminationSequenceStrategy(from),
       __order(from.__order), __order_index(from.__order_index),
       __order_needed(from.__order_needed) {
     // for debugging purposes
     GUM_CONS_CPY(OrderedEliminationSequenceStrategy);
   }

◆ OrderedEliminationSequenceStrategy() [4/4]

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

move constructor

Definition at line 75 of file orderedEliminationSequenceStrategy.cpp.

                                                 :
       EliminationSequenceStrategy(std::move(from)),
       __order(from.__order), __order_index(from.__order_index),
       __order_needed(from.__order_needed) {
     // for debugging purposes
     GUM_CONS_MOV(OrderedEliminationSequenceStrategy);
   }

◆ ~OrderedEliminationSequenceStrategy()

gum::OrderedEliminationSequenceStrategy::~OrderedEliminationSequenceStrategy ( )

virtual

destructor

Definition at line 85 of file orderedEliminationSequenceStrategy.cpp.

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

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

References gum::EliminationSequenceStrategy::_graph, gum::NodeGraphPart::existsNode(), gum::Set< Key, Alloc >::insert(), and gum::NodeGraphPart::size().

Referenced by setOrder().

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

Here is the caller graph for this function:

◆ askFillIns()

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

finalvirtual

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

Parameters

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

Implements gum::EliminationSequenceStrategy.

Definition at line 171 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 153 of file orderedEliminationSequenceStrategy.cpp.

References __order_index, __order_needed, and gum::EliminationSequenceStrategy::clear().

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

References OrderedEliminationSequenceStrategy().

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

References gum::EliminationSequenceStrategy::_domain_sizes.

                                                                        {
     return _domain_sizes;
   }

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

References __order, __order_index, __order_needed, gum::EliminationSequenceStrategy::_graph, gum::NodeGraphPart::existsNode(), and GUM_ERROR.

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

References gum::EliminationSequenceStrategy::fillIns().

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

References gum::EliminationSequenceStrategy::_graph.

Referenced by gum::EliminationSequenceStrategy::setGraph().

                                                                       {
     return _graph;
   }

Here is the caller graph for this function:

◆ isOrderNeeded()

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

noexcept

indicates whether a new complete ordering is needed

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

Definition at line 38 of file orderedEliminationSequenceStrategy_inl.h.

References __order_needed.

                                                                                {
     return __order_needed;
   }

◆ newFactory()

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

finalvirtual

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

Warning: you must deallocate by yourself the object returned

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

Implements gum::EliminationSequenceStrategy.

Definition at line 93 of file orderedEliminationSequenceStrategy.cpp.

References OrderedEliminationSequenceStrategy().

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

References __order, __order_index, __order_needed, and GUM_ERROR.

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

◆ order()

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

noexcept

returns the current complete ordering

Definition at line 32 of file orderedEliminationSequenceStrategy_inl.h.

References __order.

Referenced by setOrder().

                                                                         {
     return __order;
   }

Here is the caller graph for this function:

◆ providesFillIns()

bool gum::OrderedEliminationSequenceStrategy::providesFillIns ( ) const

finalvirtual

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

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

Implements gum::EliminationSequenceStrategy.

Definition at line 178 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 184 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 104 of file orderedEliminationSequenceStrategy.cpp.

References __order, gum::EliminationSequenceStrategy::setGraph(), and setOrder().

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setOrder()

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

finalvirtual

sets the sequence of elimination

sets a new complete order

Parameters

order the order in which the nodes should be eliminated

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

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

Definition at line 130 of file orderedEliminationSequenceStrategy.cpp.

References __isOrderNeeded(), __order, __order_index, __order_needed, gum::EliminationSequenceStrategy::_graph, gum::NodeGraphPart::existsNode(), and order().

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

                                        {
     // 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:

Here is the caller graph for this function:

Member Data Documentation

◆ __order

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

private

the vector indicating in which order we should eliminate the nodes

Definition at line 175 of file orderedEliminationSequenceStrategy.h.

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

◆ __order_index

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

private

the index in the order indicating the new node to eliminate

Definition at line 178 of file orderedEliminationSequenceStrategy.h.

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

◆ __order_needed

bool gum::OrderedEliminationSequenceStrategy::__order_needed {true}

private

indicate whether a new complete ordering is necessary for the elimination

Definition at line 182 of file orderedEliminationSequenceStrategy.h.

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

◆ _domain_sizes

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

protectedinherited

the domain sizes of the variables/nodes

Definition at line 156 of file eliminationSequenceStrategy.h.

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

◆ _graph

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

protectedinherited

the graph to be triangulated

Definition at line 153 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 159 of file eliminationSequenceStrategy.h.

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

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

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

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ OrderedEliminationSequenceStrategy() [1/4]

◆ OrderedEliminationSequenceStrategy() [2/4]

◆ OrderedEliminationSequenceStrategy() [3/4]

◆ OrderedEliminationSequenceStrategy() [4/4]

◆ ~OrderedEliminationSequenceStrategy()

Member Function Documentation

◆ __isOrderNeeded()

◆ askFillIns()

◆ clear()

◆ copyFactory()

◆ domainSizes()

◆ eliminationUpdate()

◆ fillIns()

◆ graph()

◆ isOrderNeeded()

◆ newFactory()

◆ nextNodeToEliminate()

◆ order()

◆ providesFillIns()

◆ providesGraphUpdate()

◆ setGraph()

◆ setOrder()

Member Data Documentation

◆ __order

◆ __order_index

◆ __order_needed

◆ _domain_sizes

◆ _graph

◆ _log_domain_sizes