Base class for all elimination sequence algorithm that impose a given partial ordering on the nodes elimination sequence, that is, the set of all the nodes is divided into several subsets. More...

#include <partialOrderedEliminationSequenceStrategy.h>

Inheritance diagram for gum::PartialOrderedEliminationSequenceStrategy:

Collaboration diagram for gum::PartialOrderedEliminationSequenceStrategy:

Public Member Functions
Accessors / Modifiers
virtual bool	setGraph (UndiGraph graph, const NodeProperty< Size > dom_sizes)
	sets a new graph to be triangulated
virtual bool	setPartialOrder (const List< NodeSet > *subsets)
	sets a new partial ordering constraint on the elimination sequence
virtual void	clear ()
	clears the sequence (to prepare, for instance, a new 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
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
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

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

Constructors / Destructors
virtual	~PartialOrderedEliminationSequenceStrategy ()
	destructor
virtual PartialOrderedEliminationSequenceStrategy *	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 PartialOrderedEliminationSequenceStrategy *	copyFactory () const =0
	virtual copy constructor
	PartialOrderedEliminationSequenceStrategy ()
	default constructor (uses an empty graph)
	PartialOrderedEliminationSequenceStrategy (UndiGraph graph, const NodeProperty< Size > dom_sizes, const List< NodeSet > *subsets)
	constructor for a (tensorly) non empty graph
	PartialOrderedEliminationSequenceStrategy (const PartialOrderedEliminationSequenceStrategy &)
	copy constructor
	PartialOrderedEliminationSequenceStrategy (PartialOrderedEliminationSequenceStrategy &&)
	move constructor

Detailed Description

Base class for all elimination sequence algorithm that impose a given partial ordering on the nodes elimination sequence, that is, the set of all the nodes is divided into several subsets.

Within each subset, any ordering can be chosen. But 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.

Definition at line 73 of file partialOrderedEliminationSequenceStrategy.h.

Constructor & Destructor Documentation

◆ ~PartialOrderedEliminationSequenceStrategy()

gum::PartialOrderedEliminationSequenceStrategy::~PartialOrderedEliminationSequenceStrategy ( )

virtual

destructor

Definition at line 101 of file partialOrderedEliminationSequenceStrategy.cpp.

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

References PartialOrderedEliminationSequenceStrategy().

Here is the call graph for this function:

◆ PartialOrderedEliminationSequenceStrategy() [1/4]

gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy ( )

protected

default constructor (uses an empty graph)

default constructor

Definition at line 62 of file partialOrderedEliminationSequenceStrategy.cpp.

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

References PartialOrderedEliminationSequenceStrategy().

Referenced by gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy(), gum::DefaultPartialOrderedEliminationSequenceStrategy::DefaultPartialOrderedEliminationSequenceStrategy(), PartialOrderedEliminationSequenceStrategy(), PartialOrderedEliminationSequenceStrategy(), PartialOrderedEliminationSequenceStrategy(), PartialOrderedEliminationSequenceStrategy(), ~PartialOrderedEliminationSequenceStrategy(), copyFactory(), and newFactory().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PartialOrderedEliminationSequenceStrategy() [2/4]

gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy	(	UndiGraph *	graph,
		const NodeProperty< Size > *	dom_sizes,
		const List< NodeSet > *	subsets )

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	thedomain sizes of the nodes/variables
subsets	the list of the subsets constituting the partial ordering

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 68 of file partialOrderedEliminationSequenceStrategy.cpp.

                                           {
    setGraph(graph, dom_sizes);
    setPartialOrder(subsets);
 
    // for debugging purposes
    GUM_CONSTRUCTOR(PartialOrderedEliminationSequenceStrategy);
  }

References PartialOrderedEliminationSequenceStrategy(), gum::EliminationSequenceStrategy::graph(), setGraph(), and setPartialOrder().

Here is the call graph for this function:

◆ PartialOrderedEliminationSequenceStrategy() [3/4]

gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy ( const PartialOrderedEliminationSequenceStrategy & from )

protected

copy constructor

Definition at line 80 of file partialOrderedEliminationSequenceStrategy.cpp.

                                                             :
      EliminationSequenceStrategy(from), subsets_(from.subsets_), subset_iter_(from.subset_iter_),
      nodeset_(from.nodeset_), partial_order_needed_(from.partial_order_needed_) {
    // for debugging purposes
    GUM_CONS_CPY(PartialOrderedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), PartialOrderedEliminationSequenceStrategy(), nodeset_, partial_order_needed_, subset_iter_, and subsets_.

Here is the call graph for this function:

◆ PartialOrderedEliminationSequenceStrategy() [4/4]

gum::PartialOrderedEliminationSequenceStrategy::PartialOrderedEliminationSequenceStrategy ( PartialOrderedEliminationSequenceStrategy && from )

protected

move constructor

Definition at line 89 of file partialOrderedEliminationSequenceStrategy.cpp.

                                                        :
      EliminationSequenceStrategy(std::move(from)), subsets_(from.subsets_),
      subset_iter_(from.subset_iter_), nodeset_(std::move(from.nodeset_)),
      partial_order_needed_(from.partial_order_needed_) {
    from.partial_order_needed_ = true;
 
    // for debugging purposes
    GUM_CONS_MOV(PartialOrderedEliminationSequenceStrategy);
  }

References gum::EliminationSequenceStrategy::EliminationSequenceStrategy(), PartialOrderedEliminationSequenceStrategy(), nodeset_, partial_order_needed_, subset_iter_, and subsets_.

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::PartialOrderedEliminationSequenceStrategy::clear ( )

virtual

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

Reimplemented from gum::EliminationSequenceStrategy.

Reimplemented in gum::DefaultPartialOrderedEliminationSequenceStrategy.

Definition at line 157 of file partialOrderedEliminationSequenceStrategy.cpp.

                                                        {
    EliminationSequenceStrategy::clear();
    subsets_ = nullptr;
    nodeset_.clear();
    partial_order_needed_ = true;
  }

References gum::EliminationSequenceStrategy::clear(), nodeset_, partial_order_needed_, and subsets_.

Referenced by gum::DefaultPartialOrderedEliminationSequenceStrategy::clear().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ copyFactory()

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

pure virtual

virtual copy constructor

Implements gum::EliminationSequenceStrategy.

Implemented in gum::DefaultPartialOrderedEliminationSequenceStrategy.

References PartialOrderedEliminationSequenceStrategy(), gum::EliminationSequenceStrategy::graph(), and isPartialOrderNeeded().

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.

112{}

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

116{ return _empty_fill_ins_(); }

gum::EliminationSequenceStrategy::_empty_fill_ins_

static const EdgeSet & _empty_fill_ins_()

an empty fill-ins set used by default

Definition eliminationSequenceStrategy.cpp:60

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.

56{ return graph_; }

gum::EliminationSequenceStrategy::graph_

UndiGraph * graph_

the graph to be triangulated

Definition eliminationSequenceStrategy.h:174

References graph_.

Here is the caller graph for this function:

◆ isPartialOrderNeeded()

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

noexcept

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

protected

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()

virtual PartialOrderedEliminationSequenceStrategy * gum::PartialOrderedEliminationSequenceStrategy::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::DefaultPartialOrderedEliminationSequenceStrategy.

References PartialOrderedEliminationSequenceStrategy().

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.

◆ partialOrder()

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

noexcept

returns the current partial ordering

Definition at line 58 of file partialOrderedEliminationSequenceStrategy_inl.h.

                                                                                      {
    return subsets_;
  }

References subsets_.

◆ 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::PartialOrderedEliminationSequenceStrategy::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 nodes/variables

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 is altered during the triangulation.; note that, by aGrUM's rule, the graph and the sequence are not copied but only referenced by the elimination sequence algorithm.

Reimplemented from gum::EliminationSequenceStrategy.

Reimplemented in gum::DefaultPartialOrderedEliminationSequenceStrategy.

Definition at line 107 of file partialOrderedEliminationSequenceStrategy.cpp.

                                                {
    if (EliminationSequenceStrategy::setGraph(graph, domain_sizes)) {
      setPartialOrder(subsets_);
      return true;
    }
    return false;
  }

References gum::EliminationSequenceStrategy::graph(), gum::EliminationSequenceStrategy::setGraph(), setPartialOrder(), and subsets_.

Referenced by PartialOrderedEliminationSequenceStrategy(), gum::PartialOrderedTriangulation::initTriangulation_(), and gum::DefaultPartialOrderedEliminationSequenceStrategy::setGraph().

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 )

virtual

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