gum::DefaultEliminationSequenceStrategy Class Reference

An efficient unconstrained elimination sequence algorithm. More...

#include <defaultEliminationSequenceStrategy.h>

Inheritance diagram for gum::DefaultEliminationSequenceStrategy:

Collaboration diagram for gum::DefaultEliminationSequenceStrategy:

Public Member Functions
Constructors / Destructors
	DefaultEliminationSequenceStrategy (double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
	default constructor (uses an empty graph) More...
	DefaultEliminationSequenceStrategy (UndiGraph *graph, const NodeProperty< Size > *dom_sizes, double ratio=GUM_QUASI_RATIO, double threshold=GUM_WEIGHT_THRESHOLD)
	constructor for an a priori non empty graph More...
	DefaultEliminationSequenceStrategy (const DefaultEliminationSequenceStrategy &from)
	copy constructor More...
	DefaultEliminationSequenceStrategy (DefaultEliminationSequenceStrategy &&)
	move constructor More...
virtual	~DefaultEliminationSequenceStrategy ()
	destructor More...
virtual DefaultEliminationSequenceStrategy *	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 DefaultEliminationSequenceStrategy *	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 void	clear () final
	clears the sequence (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...
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 efficient unconstrained elimination sequence algorithm.

Class DefaultEliminationSequenceStrategy implements an unconstrained elimination sequence algorithm (that is, there is no external constraint on the possible elimination ordering). 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

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 75 of file defaultEliminationSequenceStrategy.h.

Constructor & Destructor Documentation

DefaultEliminationSequenceStrategy() [1/4]

gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy	(	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 35 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                          :
      simplicial_ratio__(theRatio),
      simplicial_threshold__(theThreshold) {
    // for debugging purposes
    GUM_CONSTRUCTOR(DefaultEliminationSequenceStrategy);
  }

Here is the call graph for this function:

DefaultEliminationSequenceStrategy() [2/4]

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

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	the domain sizes of the nodes to be eliminated
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 and the domain sizes are not copied but only referenced by the elimination sequence algorithm.

Definition at line 45 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                            :
      simplicial_ratio__(ratio),
      simplicial_threshold__(threshold) {
    setGraph(graph, domain_sizes);

    // for debugging purposes
    GUM_CONSTRUCTOR(DefaultEliminationSequenceStrategy);
  }

Here is the call graph for this function:

DefaultEliminationSequenceStrategy() [3/4]

gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy

(

const DefaultEliminationSequenceStrategy &

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 59 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                     :
      UnconstrainedEliminationSequenceStrategy(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(DefaultEliminationSequenceStrategy);
  }

Here is the call graph for this function:

DefaultEliminationSequenceStrategy() [4/4]

gum::DefaultEliminationSequenceStrategy::DefaultEliminationSequenceStrategy

(

DefaultEliminationSequenceStrategy &&

from

)

move constructor

Definition at line 77 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                :
      UnconstrainedEliminationSequenceStrategy(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(DefaultEliminationSequenceStrategy);
  }

Here is the call graph for this function:

~DefaultEliminationSequenceStrategy()

gum::DefaultEliminationSequenceStrategy::~DefaultEliminationSequenceStrategy ( )

virtual

destructor

Definition at line 93 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                          {
    // for debugging purposes
    GUM_DESTRUCTOR(DefaultEliminationSequenceStrategy);

    if (simplicial_set__ != nullptr) delete simplicial_set__;
  }

Here is the call graph for this function:

Member Function Documentation

askFillIns()

void gum::DefaultEliminationSequenceStrategy::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 195 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                {
    provide_fill_ins__ = do_it;

    if (simplicial_set__ != nullptr)
      simplicial_set__->setFillIns(provide_fill_ins__);
  }

Here is the call graph for this function:

clear()

void gum::DefaultEliminationSequenceStrategy::clear ( )

finalvirtual

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

Reimplemented from gum::EliminationSequenceStrategy.

Definition at line 147 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                 {
    UnconstrainedEliminationSequenceStrategy::clear();

    log_weights__.clear();
    if (simplicial_set__ != nullptr) {
      delete simplicial_set__;
      simplicial_set__ = nullptr;
    }
  }

Here is the call graph for this function:

copyFactory()

DefaultEliminationSequenceStrategy * gum::DefaultEliminationSequenceStrategy::copyFactory ( ) const

finalvirtual

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

Definition at line 110 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                           {
    return new DefaultEliminationSequenceStrategy(*this);
  }

Here is the call graph for this function:

createSimplicialSet__()

void gum::DefaultEliminationSequenceStrategy::createSimplicialSet__ ( )

private

create a new simplicial set suited for the current graph

Definition at line 115 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

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

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

References gum::Set< Key, Alloc >::emplace().

                                                                       {
    return domain_sizes_;
  }

Here is the call graph for this function:

eliminationUpdate()

void gum::DefaultEliminationSequenceStrategy::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 216 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                            {
    if (simplicial_set__ != nullptr) {
      simplicial_set__->makeClique(id);
      simplicial_set__->eraseClique(id);
    }
  }

Here is the call graph for this function:

fillIns()

const EdgeSet & gum::DefaultEliminationSequenceStrategy::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 225 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                             {
    if (!provide_fill_ins__ || (simplicial_set__ == nullptr))
      return UnconstrainedEliminationSequenceStrategy::fillIns();
    else
      return simplicial_set__->fillIns();
  }

Here is the call graph for this function:

graph()

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

noexceptinherited

returns the current graph

Definition at line 36 of file eliminationSequenceStrategy_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                      {
    return graph_;
  }

Here is the call graph for this function:

newFactory()

DefaultEliminationSequenceStrategy * gum::DefaultEliminationSequenceStrategy::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::UnconstrainedEliminationSequenceStrategy.

Definition at line 103 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                          {
    return new DefaultEliminationSequenceStrategy(simplicial_ratio__,
                                                  simplicial_threshold__);
  }

Here is the call graph for this function:

nextNodeToEliminate()

NodeId gum::DefaultEliminationSequenceStrategy::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 158 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                 {
    // if there is no simplicial set, send an exception
    if (graph_ == nullptr) { GUM_ERROR(NotFound, "the graph is empty"); }

    // select a node to be eliminated: try simplicial nodes, then almost
    // simplicial nodes, then quasi-simplicial nodes
    // note that if graph__ != 0, simplicial_set__ has been allocated
    if (simplicial_set__->hasSimplicialNode())
      return simplicial_set__->bestSimplicialNode();
    else if (simplicial_set__->hasAlmostSimplicialNode())
      return simplicial_set__->bestAlmostSimplicialNode();
    else if (simplicial_set__->hasQuasiSimplicialNode())
      return simplicial_set__->bestQuasiSimplicialNode();
    else {
      // here: select the node through Kjaerulff's heuristic
      auto iter_heuristic = log_weights__.cbegin();

      if (iter_heuristic == log_weights__.cend())
        GUM_ERROR(NotFound, "there exists no more node to eliminate");

      double min_weight     = iter_heuristic.val();
      NodeId removable_node = iter_heuristic.key();
      for (++iter_heuristic; iter_heuristic != log_weights__.cend();
           ++iter_heuristic) {
        if (iter_heuristic.val() < min_weight) {
          removable_node = iter_heuristic.key();
          min_weight     = iter_heuristic.val();
        }
      }

      return removable_node;
    }
  }

Here is the call graph for this function:

providesFillIns()

bool gum::DefaultEliminationSequenceStrategy::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 205 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                 {
    return provide_fill_ins__;
  }

Here is the call graph for this function:

providesGraphUpdate()

bool gum::DefaultEliminationSequenceStrategy::providesGraphUpdate ( ) const

finalvirtual

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. Hence the latter should delegate this operation to the elimination sequence. This is the case, for instance, for the defaultEliminationSequence, which uses a SimplicialSet that knows that some eliminated nodes do not require any fill-in.

Implements gum::EliminationSequenceStrategy.

Definition at line 211 of file defaultEliminationSequenceStrategy.cpp.

                                                                     {
    return true;
  }

setGraph()

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

finalvirtual

sets a new graph to be triangulated

The elimination sequence algorithm 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

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 135 of file defaultEliminationSequenceStrategy.cpp.

References gum::Set< Key, Alloc >::emplace().

                                               {
    if (UnconstrainedEliminationSequenceStrategy::setGraph(graph, domain_sizes)) {
      createSimplicialSet__();
      return true;
    }

    return false;
  }

Here is the call 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 158 of file eliminationSequenceStrategy.h.

graph_

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

protectedinherited

the graph to be triangulated

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

log_weights__

NodeProperty< double > gum::DefaultEliminationSequenceStrategy::log_weights__

private

for each node, the weight of the clique created by the node's elimination

Definition at line 222 of file defaultEliminationSequenceStrategy.h.

provide_fill_ins__

bool gum::DefaultEliminationSequenceStrategy::provide_fill_ins__ {false}

private

indicates whether we compute new fill-ins

Definition at line 234 of file defaultEliminationSequenceStrategy.h.

simplicial_ratio__

double gum::DefaultEliminationSequenceStrategy::simplicial_ratio__

private

the ratio used by simplicial_set__ for its quasi-simplicial nodes

Definition at line 228 of file defaultEliminationSequenceStrategy.h.

simplicial_set__

SimplicialSet* gum::DefaultEliminationSequenceStrategy::simplicial_set__ {nullptr}

private

the simplicial set used for determining the best nodes to eliminate

Definition at line 225 of file defaultEliminationSequenceStrategy.h.

simplicial_threshold__

double gum::DefaultEliminationSequenceStrategy::simplicial_threshold__

private

the threshold used by simplicial_set__ to determine small cliques

Definition at line 231 of file defaultEliminationSequenceStrategy.h.

---

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

• agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/defaultEliminationSequenceStrategy.h
• agrum/tools/graphs/algorithms/triangulations/eliminationStrategies/defaultEliminationSequenceStrategy.cpp