gum::DefaultTriangulation Class Reference

The default triangulation algorithm used by aGrUM. More...

#include <defaultTriangulation.h>

Inheritance diagram for gum::DefaultTriangulation:

Collaboration diagram for gum::DefaultTriangulation:

Public Member Functions
Constructors / Destructors
	DefaultTriangulation (const UndiGraph *graph, const NodeProperty< Size > *dom_sizes, bool minimality=false, double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
	basic constructor. initialize the triangulation
	DefaultTriangulation (bool minimality=false, double theRatio=GUM_QUASI_RATIO, double theThreshold=GUM_WEIGHT_THRESHOLD)
	default constructor: initialize the triangulation for an empty graph
	DefaultTriangulation (const DefaultTriangulation &from)
	copy constructor
	DefaultTriangulation (DefaultTriangulation &&from)
	move constructor
	~DefaultTriangulation () override
	destructor
DefaultTriangulation *	newFactory () const override
	virtual clone constructor
DefaultTriangulation *	copyFactory () const override
	virtual copy constructor
Accessors / Modifiers
double	maxLog10CliqueDomainSize ()
	returns the max of log10DomainSize of the cliques in the junction tree.
const NodeProperty< Size > *	domainSizes () const
	returns the domain sizes of the variables of the graph to be triangulated

Protected Attributes
EliminationSequenceStrategy *	elimination_sequence_strategy_ {nullptr}
	the elimination sequence strategy used by the triangulation
JunctionTreeStrategy *	junction_tree_strategy_ {nullptr}
	the junction tree strategy used by the triangulation
const NodeProperty< Size > *	domain_sizes_ {nullptr}
	the domain sizes of the variables/nodes of the graph

Private Member Functions
void	_triangulate_ ()
	the function that performs the triangulation
void	_computeEliminationTree_ ()
	returns an elimination tree from a triangulated graph
void	_computeMaxPrimeJunctionTree_ ()
	computes the junction tree of the maximal prime subgraphs
void	_computeRecursiveThinning_ ()
	removes redundant fill-ins and compute proper elimination cliques and order
void	_computeMaxPrimeMergings_ (const NodeId node, const NodeId from, std::vector< Arc > &merged_cliques, NodeSet &mark) const
	used for computing the junction tree of the maximal prime subgraphs
Operators
DefaultTriangulation &	operator= (const DefaultTriangulation &)
	forbid copy operator

Private Attributes
double	_quasi_ratio_
	the ratio above which we consider nodes to be quasi simplicial
double	_threshold_
	threshold under which almost and quasi simplicial nodes can be chosen to be eliminated
const UndiGraph *	_original_graph_ {nullptr}
	a pointer to the (external) original graph (which will be triangulated)
UndiGraph	_triangulated_graph_
	the triangulated graph
EdgeSet	_fill_ins_
	the fill-ins added during the whole triangulation process
std::vector< NodeId >	_elim_order_
	the order in which nodes are eliminated by the algorithm
NodeProperty< NodeId >	_reverse_elim_order_
	the elimination order (access by NodeId)
NodeProperty< NodeSet >	_elim_cliques_
	the cliques formed by the elimination of the nodes
CliqueGraph	_elim_tree_
	the elimination tree computed by the algorithm
const CliqueGraph *	_junction_tree_ {nullptr}
	the junction tree computed by the algorithm
CliqueGraph	_max_prime_junction_tree_
	the maximal prime subgraph junction tree computed from the junction tree
NodeProperty< NodeId >	_node_2_max_prime_clique_
	indicates which clique of the max prime junction tree was created by the elmination of a given node (the key of the table)
bool	_has_triangulation_ {false}
	a boolean indicating whether we have parformed a triangulation
bool	_has_triangulated_graph_ {false}
	a boolean indicating whether we have constructed the triangulated graph
bool	_has_elimination_tree_ {false}
	a boolean indicating whether the elimination tree has been computed
bool	_has_junction_tree_ {false}
	a boolean indicating whether the junction tree has been constructed
bool	_has_max_prime_junction_tree_ {false}
	indicates whether a maximal prime subgraph junction tree has been constructed
bool	_has_fill_ins_ {false}
	indicates whether we actually computed fill-ins
bool	_minimality_required_ {false}
	indicates whether the triangulation must be minimal
std::vector< EdgeSet >	_added_fill_ins_
	a vector containing the set of fill-ins added after each node elimination (used by recursive thinning)
bool	_we_want_fill_ins_ {false}
	a boolean indicating if we want fill-ins list with the standard triangulation method

Accessors / Modifiers
void	setGraph (const UndiGraph *graph, const NodeProperty< Size > *domsizes) override
	initialize the triangulation data structures for a new graph
const EdgeSet &	fillIns () override
	returns the fill-ins added by the triangulation algorithm
const std::vector< NodeId > &	eliminationOrder () override
	returns an elimination ordering compatible with the triangulated graph
Idx	eliminationOrder (const NodeId) override
	returns the index of a given node in the elimination order (0 = first node eliminated)
const NodeProperty< NodeId > &	reverseEliminationOrder ()
	returns a table indicating, for each node, at which step it was deleted by the triangulation process
const UndiGraph &	triangulatedGraph () override
	returns the triangulated graph
const CliqueGraph &	eliminationTree () override
	returns the elimination tree of a compatible ordering
const CliqueGraph &	junctionTree () override
	returns a compatible junction tree
NodeId	createdJunctionTreeClique (const NodeId id) override
	returns the Id of the clique of the junction tree created by the elimination of a given node during the triangulation process
const NodeProperty< NodeId > &	createdJunctionTreeCliques () override
	returns the Ids of the cliques of the junction tree created by the elimination of the nodes
const CliqueGraph &	maxPrimeSubgraphTree () override
	returns a junction tree of maximal prime subgraphs
NodeId	createdMaxPrimeSubgraph (const NodeId id) override
	returns the Id of the maximal prime subgraph created by the elimination of a given node during the triangulation process
void	clear () override
	reinitialize the graph to be triangulated to an empty graph
void	setMinimalRequirement (bool)
	sets/unset the minimality requirement
virtual bool	isMinimalityRequired () const final
	indicates wether minimality is required
void	setFillIns (bool)
	sets/unsets the record of the fill-ins in the standard triangulation procedure
const UndiGraph *	originalGraph () const
	returns the graph to be triangulated
EliminationSequenceStrategy &	eliminationSequenceStrategy () const
	returns the elimination sequence strategy used by the triangulation
JunctionTreeStrategy &	junctionTreeStrategy () const
	returns the junction tree strategy used by the triangulation
virtual void	initTriangulation_ (UndiGraph &graph)
	the function called to initialize the triangulation process

Detailed Description

The default triangulation algorithm used by aGrUM.

By default, this is the very class used by aGrUM for performing triangulations. The algorithm used is the following:

the graph passed in argument is completed by fill-ins until it becomes

triangulated

then an elimination tree is computed from this triangulated graph

finally, a junction tree is derived from the elimination tree

The triangulation step first tries to remove simplicial nodes, that is, nodes that belong to only one clique. Then almost simplicial nodes of low width are removed (almost simplicial nodes are nodes such that all but one of their neighbors form a clique). Then quasi simplicial nodes are removed, that is, nodes such that the ratio of the number of fill-ins to add to form a clique by the number of edges in a clique is small. Then nodes that create cliques of small weight are removed.

The transformation from the elimination tree to the join tree is performed bottom-up. Each time a node of the elimination tree is identified to be a sub-clique, it is removed and all of its parents but one are linked to the latter. The identification of sub-cliques is very fast (comparison of 2 ints).

Definition at line 81 of file defaultTriangulation.h.

Constructor & Destructor Documentation

DefaultTriangulation() [1/4]

gum::DefaultTriangulation::DefaultTriangulation ( const UndiGraph * graph, const NodeProperty< Size > * dom_sizes, bool minimality = false, double theRatio = GUM_QUASI_RATIO, double theThreshold = GUM_WEIGHT_THRESHOLD )

explicit

basic constructor. initialize the triangulation

References GUM_QUASI_RATIO, and GUM_WEIGHT_THRESHOLD.

Referenced by DefaultTriangulation(), DefaultTriangulation(), copyFactory(), newFactory(), and operator=().

Here is the caller graph for this function:

DefaultTriangulation() [2/4]

gum::DefaultTriangulation::DefaultTriangulation ( bool minimality = false, double theRatio = GUM_QUASI_RATIO, double theThreshold = GUM_WEIGHT_THRESHOLD )

explicit

default constructor: initialize the triangulation for an empty graph

References GUM_QUASI_RATIO, and GUM_WEIGHT_THRESHOLD.

DefaultTriangulation() [3/4]

gum::DefaultTriangulation::DefaultTriangulation

(

const DefaultTriangulation &

from

)

copy constructor

References DefaultTriangulation().

Here is the call graph for this function:

DefaultTriangulation() [4/4]

gum::DefaultTriangulation::DefaultTriangulation

(

DefaultTriangulation &&

from

)

move constructor

References DefaultTriangulation().

Here is the call graph for this function:

~DefaultTriangulation()

gum::DefaultTriangulation::~DefaultTriangulation ( )

override

destructor

Member Function Documentation

_computeEliminationTree_()

void gum::StaticTriangulation::_computeEliminationTree_ ( )

privateinherited

returns an elimination tree from a triangulated graph

Definition at line 341 of file staticTriangulation.cpp.

                                                     {
    // if there already exists an elimination tree, no need to compute it again
    if (_has_elimination_tree_) return;
 
    // if the graph is not triangulated, triangulate it
    if (!_has_triangulation_) _triangulate_();
 
    // create the nodes of the elimination tree
    _elim_tree_.clear();
 
    auto size = Size(_elim_order_.size());
    for (auto i = NodeId(0); i < size; ++i)
      _elim_tree_.addNodeWithId(i, _elim_cliques_[_elim_order_[i]]);
 
    // create the edges of the elimination tree: join a node to the one in
    // its clique that is eliminated first
    for (auto i = NodeId(0); i < size; ++i) {
      NodeId         clique_i_creator = _elim_order_[i];
      const NodeSet& list_of_nodes    = _elim_cliques_[clique_i_creator];
      Idx            child            = _original_graph_->bound() + 1;
 
      for (const auto node: list_of_nodes) {
        auto it_elim_step = _reverse_elim_order_[node];
 
        if ((node != clique_i_creator) && (child > it_elim_step)) child = it_elim_step;
      }
 
      if (child <= _original_graph_->bound()) {
        // WARNING: here, we assume that the nodes of the elimination tree are
        // indexed from 0 to n-1
        _elim_tree_.addEdge(i, child);
      }
    }
 
    _has_elimination_tree_ = true;
  }

References _elim_cliques_, _elim_order_, _elim_tree_, _has_elimination_tree_, _has_triangulation_, _original_graph_, _reverse_elim_order_, and _triangulate_().

Here is the call graph for this function:

_computeMaxPrimeJunctionTree_()

void gum::StaticTriangulation::_computeMaxPrimeJunctionTree_ ( )

privateinherited

computes the junction tree of the maximal prime subgraphs

Definition at line 411 of file staticTriangulation.cpp.

                                                          {
    // if there already exists a max prime junction tree, no need
    // to recompute it
    if (_has_max_prime_junction_tree_) return;
 
    // if there is no junction tree, create it
    if (!_has_junction_tree_) junctionTree();
 
    // the maximal prime subgraph join tree is created by aggregation of some
    // cliques. More precisely, when the separator between 2 cliques is not
    // complete in the original graph, then the two cliques must be merged.
    // Create a hashtable indicating which clique has been absorbed by some
    // other
    // clique.
    NodeProperty< NodeId > T_mpd_cliques(_junction_tree_->size());
 
    for (const auto clik: _junction_tree_->nodes())
      T_mpd_cliques.insert(clik, clik);
 
    // parse all the separators of the junction tree and test those that are not
    // complete in the orginal graph
    std::vector< Arc > merged_cliques;
 
    NodeSet mark;
 
    for (const auto clik: _junction_tree_->nodes())
      if (!mark.contains(clik)) _computeMaxPrimeMergings_(clik, clik, merged_cliques, mark);
 
    // compute the transitive closure of merged_cliques. This one will contain
    // pairs (X,Y) indicating that clique X must be merged with clique Y.
    // Actually clique X will be inserted into clique Y.
    for (unsigned int i = 0; i < merged_cliques.size(); ++i) {
      T_mpd_cliques[merged_cliques[i].tail()] = T_mpd_cliques[merged_cliques[i].head()];
    }
 
    // now we can create the max prime junction tree. First, create the cliques
    for (const auto& elt: T_mpd_cliques)
      if (elt.first == elt.second)
        _max_prime_junction_tree_.addNodeWithId(elt.second, _junction_tree_->clique(elt.second));
 
    // add to the cliques previously created the nodes of the cliques that were
    // merged into them
    for (const auto& elt: T_mpd_cliques)
      if (elt.first != elt.second)
        for (const auto node: _junction_tree_->clique(elt.first)) {
          try {
            _max_prime_junction_tree_.addToClique(elt.second, node);
          } catch (DuplicateElement const&) {}
        }
 
    // add the edges to the graph
    for (const auto& edge: _junction_tree_->edges()) {
      NodeId node1 = T_mpd_cliques[edge.first()];
      NodeId node2 = T_mpd_cliques[edge.second()];
 
      if (node1 != node2) {
        try {
          _max_prime_junction_tree_.addEdge(node1, node2);
        } catch (DuplicateElement const&) {}
      }
    }
 
    // compute for each node which clique of the max prime junction tree was
    // created by the elimination of the node
    const NodeProperty< NodeId >& node_2_junction_clique
        = junction_tree_strategy_->createdCliques();
 
    for (const auto& elt: node_2_junction_clique)
      _node_2_max_prime_clique_.insert(elt.first, T_mpd_cliques[elt.second]);
 
    _has_max_prime_junction_tree_ = true;
  }

References _computeMaxPrimeMergings_(), _has_junction_tree_, _has_max_prime_junction_tree_, _junction_tree_, _max_prime_junction_tree_, _node_2_max_prime_clique_, gum::Set< Key >::contains(), gum::HashTable< Key, Val >::insert(), junction_tree_strategy_, and junctionTree().

Here is the call graph for this function:

_computeMaxPrimeMergings_()

void gum::StaticTriangulation::_computeMaxPrimeMergings_ ( const NodeId node, const NodeId from, std::vector< Arc > & merged_cliques, NodeSet & mark ) const

privateinherited

used for computing the junction tree of the maximal prime subgraphs

Definition at line 379 of file staticTriangulation.cpp.

                                                                                      {
    mark << node;
 
    for (const auto other_node: _junction_tree_->neighbours(node))
      if (other_node != from) {
        const NodeSet& separator = _junction_tree_->separator(node, other_node);
        // check that the separator between node and other_node is complete
        bool complete = true;
 
        for (auto iter_sep1 = separator.begin(); iter_sep1 != separator.end() && complete;
             ++iter_sep1) {
          auto iter_sep2 = iter_sep1;
 
          for (++iter_sep2; iter_sep2 != separator.end(); ++iter_sep2) {
            if (!_original_graph_->existsEdge(*iter_sep1, *iter_sep2)) {
              complete = false;
              break;
            }
          }
        }
 
        // here complete indicates whether the separator is complete or not
        if (!complete) merged_cliques.push_back(Arc(other_node, node));
 
        _computeMaxPrimeMergings_(other_node, node, merged_cliques, mark);
      }
  }

References _computeMaxPrimeMergings_(), _junction_tree_, _original_graph_, gum::Set< Key >::begin(), and gum::Set< Key >::end().

Referenced by _computeMaxPrimeJunctionTree_(), and _computeMaxPrimeMergings_().

Here is the call graph for this function:

Here is the caller graph for this function:

_computeRecursiveThinning_()

void gum::StaticTriangulation::_computeRecursiveThinning_ ( )

privateinherited

removes redundant fill-ins and compute proper elimination cliques and order

Definition at line 203 of file staticTriangulation.cpp.

                                                       {
    // apply recursive thinning (fmint, see Kjaerulff (90), "triangulation of
    // graphs - algorithms giving small total state space")
    NodeId                       node1, node2;
    bool                         incomplete;
    std::vector< NodeId >        adj;
    EdgeSet                      T_prime;
    NodeProperty< unsigned int > R(_triangulated_graph_.size());
 
    for (const auto node: _triangulated_graph_)
      R.insert(node, 0);
 
    // the FMINT loop
    if (_added_fill_ins_.size() > 0) {
      for (auto iter = _added_fill_ins_.rbegin(); iter != _added_fill_ins_.rend(); ++iter) {
        if (iter->size()) {
          // here apply MINT to T_i =  _added_fill_ins_[i]
          EdgeSet& T = *iter;
 
          // compute R: by default, R is equal to all the nodes in the graph
          // when R[...] >= j (see the j in the loop below), this means that the
          // node belongs to an extremal edge in R
          for (std::size_t k = 0; k < _elim_order_.size(); ++k)
            R[_elim_order_[k]] = 0;   // WARNING: do not replace R[ _elim_order_[k]] by
 
          // R[k] because the node ids may not be
          // consecutive numbers
 
          // apply MINT while some edges can possibly be deleted
          bool require_mint = true;
 
          for (unsigned int j = 0; require_mint; ++j) {
            // find T' (it is equal to the edges (v,w) of T such that
            // the intersection of adj(v,G) and adj(w,G) is complete and such
            // that
            // v and/or w belongs to an extremal node in R
            for (const auto& edge: T) {
              node1 = edge.first();
              node2 = edge.second();
 
              // check if at least one extremal node belongs to R
              if ((R[node1] < j) && (R[node2] < j)) continue;
 
              // check if the intersection of adj(v,G) and adj(w,G) is a
              // complete subgraph
              if (_triangulated_graph_.neighbours(node2).size()
                  < _triangulated_graph_.neighbours(node1).size()) {
                NodeId tmp = node1;
                node1      = node2;
                node2      = tmp;
              }
 
              incomplete = false;
 
              // find the nodes belonging to the intersection of adj(v,G)
              // and adj(w,G)
              for (const auto adjnode: _triangulated_graph_.neighbours(node1))
                if (_triangulated_graph_.existsEdge(node2, adjnode)) adj.push_back(adjnode);
 
              // check if the intersection is complete
              for (unsigned int k = 0; k < adj.size() && !incomplete; ++k) {
                for (unsigned int m = k + 1; m < adj.size(); ++m) {
                  if (!_triangulated_graph_.existsEdge(adj[k], adj[m])) {
                    incomplete = true;
                    break;
                  }
                }
              }
 
              adj.clear();
 
              if (!incomplete) {
                T_prime.insert(edge);
                R[node1] = j + 1;
                R[node2] = j + 1;
              }
            }
 
            // compute the new value of T (i.e. T\T') and update the
            // triangulated graph
            for (const auto& edge: T_prime) {
              T.erase(edge);
              _triangulated_graph_.eraseEdge(edge);
 
              if (_has_fill_ins_) _fill_ins_.erase(edge);
            }
 
            if (T_prime.size() == 0) require_mint = false;
 
            T_prime.clear();
          }
        }
      }
    }
 
    // here, the recursive thinning has removed all the superfluous edges.
    // Hence some cliques have been split and, as a result, the elimination
    // order has changed. We should thus compute a new perfect ordering. To
    // do so, we use a Maximal Cardinality Search: it has indeed the nice
    // property that, when the graph is already triangulated, it finds a
    // compatible order of elimination that does not require any edge addition
 
    // a structure storing the number of neighbours previously processed
    PriorityQueue< NodeId, unsigned int, std::greater< unsigned int > > numbered_neighbours(
        std::greater< unsigned int >(),
        _triangulated_graph_.size());
 
    for (Size i = 0; i < _elim_order_.size(); ++i)
      numbered_neighbours.insert(_elim_order_[i], 0);
 
    // perform the maximum cardinality search
    if (_elim_order_.size() > 0) {
      for (Size i = Size(_elim_order_.size()); i >= 1; --i) {
        NodeId ni                  = NodeId(i - 1);
        NodeId node                = numbered_neighbours.pop();
        _elim_order_[ni]           = node;
        _reverse_elim_order_[node] = ni;
 
        for (const auto neighbour: _triangulated_graph_.neighbours(node)) {
          if (numbered_neighbours.contains(neighbour)) {
            numbered_neighbours.setPriority(neighbour, 1 + numbered_neighbours.priority(neighbour));
          }
        }
      }
    }
 
    // here the elimination order is ok. We now need to update the
    //  _elim_cliques_
    for (Size i = 0; i < _elim_order_.size(); ++i) {
      NodeSet& cliques = _elim_cliques_.insert(_elim_order_[i], NodeSet()).second;
      cliques << _elim_order_[i];
 
      for (const auto neighbour: _triangulated_graph_.neighbours(_elim_order_[i]))
        if (_reverse_elim_order_[neighbour] > i) cliques << neighbour;
    }
  }

References _added_fill_ins_, _elim_cliques_, _elim_order_, _fill_ins_, _has_fill_ins_, _reverse_elim_order_, _triangulated_graph_, gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::contains(), gum::HashTable< Key, Val >::insert(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::insert(), gum::Set< Key >::insert(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::pop(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::priority(), and gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::setPriority().

Referenced by _triangulate_().

Here is the call graph for this function:

Here is the caller graph for this function:

_triangulate_()

void gum::StaticTriangulation::_triangulate_ ( )

privateinherited

the function that performs the triangulation

Definition at line 551 of file staticTriangulation.cpp.

                                          {
    // if the graph is already triangulated, no need to triangulate it again
    if (_has_triangulation_) return;
 
    if (!_original_graph_)
      GUM_ERROR(GraphError, "StaticTriangulation: no graph set (call setGraph first)")
 
    // copy the graph to be triangulated, so that we can modify it
    UndiGraph tmp_graph = *_original_graph_;
 
    initTriangulation_(tmp_graph);
    elimination_sequence_strategy_->askFillIns(_we_want_fill_ins_);
 
    // if we are to do recursive thinning, we will have to add fill-ins to the
    // triangulated graph each time we eliminate a node. Hence, we shall
    // initialize the triangulated graph by a copy of the original graph
    if (_minimality_required_) {
      _triangulated_graph_     = *_original_graph_;
      _has_triangulated_graph_ = true;
    }
 
    // perform the triangulation
    NodeId removable_node = 0;
 
    for (unsigned int nb_elim = 0; tmp_graph.size() != 0; ++nb_elim) {
      removable_node = elimination_sequence_strategy_->nextNodeToEliminate();
 
      // when minimality is not required, i.e., we won't apply recursive
      // thinning, the cliques sets can be computed
      if (!_minimality_required_) {
        NodeSet& cliques = _elim_cliques_.insert(removable_node, NodeSet()).second;
        cliques.resize(tmp_graph.neighbours(removable_node).size() / 2);
        cliques << removable_node;
        for (const auto clik: tmp_graph.neighbours(removable_node))
          cliques << clik;
      } else {
        // here recursive thinning will be applied, hence we need store the
        // fill-ins added by the current node removal
        EdgeSet& current_fill = _added_fill_ins_[nb_elim];
        NodeId   node1, node2;
 
        const NodeSet& nei = tmp_graph.neighbours(removable_node);
 
        for (auto iter_edges1 = nei.begin(); iter_edges1 != nei.end(); ++iter_edges1) {
          node1            = *iter_edges1;
          auto iter_edges2 = iter_edges1;
 
          for (++iter_edges2; iter_edges2 != nei.end(); ++iter_edges2) {
            node2 = *iter_edges2;
            Edge edge(node1, node2);
 
            if (!tmp_graph.existsEdge(edge)) {
              current_fill.insert(edge);
              _triangulated_graph_.addEdge(node1, node2);
            }
          }
        }
      }
 
      // if we want fill-ins but the elimination sequence strategy does not
      // compute them, we shall compute them here
      if (_we_want_fill_ins_ && !elimination_sequence_strategy_->providesFillIns()) {
        NodeId node1, node2;
 
        // add edges between removable_node's neighbours in order to create
        // a clique
        const NodeSet& nei = tmp_graph.neighbours(removable_node);
 
        for (auto iter_edges1 = nei.begin(); iter_edges1 != nei.end(); ++iter_edges1) {
          node1            = *iter_edges1;
          auto iter_edges2 = iter_edges1;
 
          for (++iter_edges2; iter_edges2 != nei.end(); ++iter_edges2) {
            node2 = *iter_edges2;
            Edge edge(node1, node2);
 
            if (!tmp_graph.existsEdge(edge)) { _fill_ins_.insert(edge); }
          }
        }
 
        // delete removable_node and its adjacent edges
        tmp_graph.eraseNode(removable_node);
      }
 
      // inform the elimination sequence that we are actually removing
      // removable_node (this enables, for instance, to update the weights of
      // the nodes in the graph)
      elimination_sequence_strategy_->eliminationUpdate(removable_node);
 
      if (!elimination_sequence_strategy_->providesGraphUpdate()) {
        NodeId node1, node2;
 
        const NodeSet& nei = tmp_graph.neighbours(removable_node);
 
        for (auto iter_edges1 = nei.begin(); iter_edges1 != nei.end(); ++iter_edges1) {
          node1            = *iter_edges1;
          auto iter_edges2 = iter_edges1;
 
          for (++iter_edges2; iter_edges2 != nei.end(); ++iter_edges2) {
            node2 = *iter_edges2;
            Edge edge(node1, node2);
 
            if (!tmp_graph.existsEdge(edge)) { tmp_graph.addEdge(node1, node2); }
          }
        }
 
        tmp_graph.eraseNode(removable_node);
      }
 
      // update the elimination order
      _elim_order_[nb_elim] = removable_node;
      _reverse_elim_order_.insert(removable_node, nb_elim);
    }
 
    // indicate whether we actually computed fill-ins
    _has_fill_ins_ = _we_want_fill_ins_;
 
    // if minimality is required, remove the redondant edges
    if (_minimality_required_) _computeRecursiveThinning_();
 
    _has_triangulation_ = true;
  }

References _added_fill_ins_, _computeRecursiveThinning_(), _elim_cliques_, _elim_order_, _fill_ins_, _has_fill_ins_, _has_triangulated_graph_, _has_triangulation_, _minimality_required_, _original_graph_, _reverse_elim_order_, _triangulated_graph_, _we_want_fill_ins_, gum::UndiGraph::addEdge(), gum::Set< Key >::begin(), elimination_sequence_strategy_, gum::Set< Key >::end(), gum::UndiGraph::eraseNode(), gum::EdgeGraphPart::existsEdge(), GUM_ERROR, initTriangulation_(), gum::Set< Key >::insert(), gum::EdgeGraphPart::neighbours(), gum::Set< Key >::resize(), gum::NodeGraphPart::size(), and gum::Set< Key >::size().

Referenced by _computeEliminationTree_(), fillIns(), and triangulatedGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

clear()

void gum::StaticTriangulation::clear ( )

overridevirtualinherited

reinitialize the graph to be triangulated to an empty graph

Implements gum::Triangulation.

Definition at line 173 of file staticTriangulation.cpp.

                                  {
    // clear the factories
    elimination_sequence_strategy_->clear();
    junction_tree_strategy_->clear();
 
    // remove the current graphs
    _original_graph_ = nullptr;
    _junction_tree_  = nullptr;
    _triangulated_graph_.clear();
    _elim_tree_.clear();
    _max_prime_junction_tree_.clear();
    _elim_cliques_.clear();
    _node_2_max_prime_clique_.clear();
 
    // remove all fill-ins and orderings
    _fill_ins_.clear();
    _added_fill_ins_.clear();
    _elim_order_.clear();
    _reverse_elim_order_.clear();
 
    // indicates that the junction tree, the max prime tree, etc, are updated
    _has_triangulation_           = true;
    _has_triangulated_graph_      = true;
    _has_elimination_tree_        = true;
    _has_junction_tree_           = true;
    _has_max_prime_junction_tree_ = true;
    _has_fill_ins_                = true;
  }

References _added_fill_ins_, _elim_cliques_, _elim_order_, _elim_tree_, _fill_ins_, _has_elimination_tree_, _has_fill_ins_, _has_junction_tree_, _has_max_prime_junction_tree_, _has_triangulated_graph_, _has_triangulation_, _junction_tree_, _max_prime_junction_tree_, _node_2_max_prime_clique_, _original_graph_, _reverse_elim_order_, _triangulated_graph_, elimination_sequence_strategy_, and junction_tree_strategy_.

Referenced by setGraph().

Here is the caller graph for this function:

copyFactory()

DefaultTriangulation * gum::DefaultTriangulation::copyFactory ( ) const

nodiscardoverridevirtual

virtual copy constructor

Implements gum::UnconstrainedTriangulation.

References DefaultTriangulation().

Here is the call graph for this function:

createdJunctionTreeClique()

NodeId gum::StaticTriangulation::createdJunctionTreeClique ( const NodeId id )

overridevirtualinherited

returns the Id of the clique of the junction tree created by the elimination of a given node during the triangulation process

Implements gum::Triangulation.

createdJunctionTreeCliques()

const NodeProperty< NodeId > & gum::StaticTriangulation::createdJunctionTreeCliques ( )

overridevirtualinherited

returns the Ids of the cliques of the junction tree created by the elimination of the nodes

Implements gum::Triangulation.

createdMaxPrimeSubgraph()

NodeId gum::StaticTriangulation::createdMaxPrimeSubgraph ( const NodeId id )

overridevirtualinherited

returns the Id of the maximal prime subgraph created by the elimination of a given node during the triangulation process

Implements gum::Triangulation.

domainSizes()

const NodeProperty< Size > * gum::Triangulation::domainSizes ( ) const

inherited

returns the domain sizes of the variables of the graph to be triangulated

eliminationOrder() [1/2]

const std::vector< NodeId > & gum::StaticTriangulation::eliminationOrder ( )

overridevirtualinherited

returns an elimination ordering compatible with the triangulated graph

Implements gum::Triangulation.

Referenced by gum::prm::StructuredInference< GUM_SCALAR >::CData::CData(), gum::prm::StructuredInference< GUM_SCALAR >::_buildReduceGraph_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodes_(), gum::prm::SVE< GUM_SCALAR >::_eliminateNodesWithEvidence_(), gum::prm::SVED< GUM_SCALAR >::_eliminateNodesWithEvidence_(), gum::prm::gspan::StrictSearch< GUM_SCALAR >::_elimination_cost_(), gum::prm::SVE< GUM_SCALAR >::_initLiftedNodes_(), gum::prm::SVED< GUM_SCALAR >::_initLiftedNodes_(), gum::prm::StructuredInference< GUM_SCALAR >::_reduceAloneInstances_(), and gum::prm::StructuredInference< GUM_SCALAR >::_reducePattern_().

Here is the caller graph for this function:

eliminationOrder() [2/2]

Idx gum::StaticTriangulation::eliminationOrder ( const NodeId )

overridevirtualinherited

returns the index of a given node in the elimination order (0 = first node eliminated)

Implements gum::Triangulation.

eliminationSequenceStrategy()

EliminationSequenceStrategy & gum::StaticTriangulation::eliminationSequenceStrategy ( ) const

inherited

returns the elimination sequence strategy used by the triangulation

References eliminationSequenceStrategy().

Referenced by eliminationSequenceStrategy().

Here is the call graph for this function:

Here is the caller graph for this function:

eliminationTree()

const CliqueGraph & gum::StaticTriangulation::eliminationTree ( )

overridevirtualinherited

returns the elimination tree of a compatible ordering

Implements gum::Triangulation.

fillIns()

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

overridevirtualinherited

returns the fill-ins added by the triangulation algorithm

Implements gum::Triangulation.

Definition at line 675 of file staticTriangulation.cpp.

                                              {
    // if we did not compute the triangulation yet, do it and commpute
    // the fill-ins at the same time
    if (!_has_triangulation_) {
      bool want_fill_ins = _we_want_fill_ins_;
      _we_want_fill_ins_ = true;
      _triangulate_();
      _we_want_fill_ins_ = want_fill_ins;
      _has_fill_ins_     = true;
    }
 
    // here, we already computed a triangulation and we already computed
    // the fill-ins, so return them
    if (_has_fill_ins_) {
      if (elimination_sequence_strategy_->providesFillIns())
        return elimination_sequence_strategy_->fillIns();
      else return _fill_ins_;
    } else {
      // ok, here, we shall compute the fill-ins as they were not precomputed
      if (!_original_graph_) return _fill_ins_;
 
      // just in case, be sure that the junction tree has been constructed
      if (!_has_junction_tree_) junctionTree();
 
      for (const auto clik_id: _junction_tree_->nodes()) {
        // for each clique, add the edges necessary to make it complete
        const NodeSet&        clique = _junction_tree_->clique(clik_id);
        std::vector< NodeId > clique_nodes(clique.size());
        unsigned int          i = 0;
 
        for (const auto node: clique) {
          clique_nodes[i] = node;
          i += 1;
        }
 
        for (i = 0; i < clique_nodes.size(); ++i) {
          for (unsigned int j = i + 1; j < clique_nodes.size(); ++j) {
            Edge edge(clique_nodes[i], clique_nodes[j]);
 
            if (!_original_graph_->existsEdge(edge)) {
              try {
                _fill_ins_.insert(edge);
              } catch (DuplicateElement const&) {}
            }
          }
        }
      }
 
      return _fill_ins_;
    }
  }

References _fill_ins_, _has_fill_ins_, _has_junction_tree_, _has_triangulation_, _junction_tree_, _original_graph_, _triangulate_(), _we_want_fill_ins_, elimination_sequence_strategy_, junctionTree(), and gum::Set< Key >::size().

Here is the call graph for this function:

initTriangulation_()

void gum::StaticTriangulation::initTriangulation_ ( UndiGraph & graph )

protectedvirtualinherited

the function called to initialize the triangulation process

This function is called when the triangulation process starts and is used to initialize the elimination sequence strategy. Actually, the graph that is modified by the triangulation algorithm is a copy of the original graph, and this copy needs be known by the elimination sequence strategy. initTriangulation_ is used to transmit this knowledge to the elimination sequence (through method setGraph of the elimination sequence class).

Parameters

graph

the very graph that is triangulated (this is a copy of original_graph)

Reimplemented in gum::OrderedTriangulation, and gum::PartialOrderedTriangulation.

Definition at line 728 of file staticTriangulation.cpp.

                                                               {
    elimination_sequence_strategy_->setGraph(&graph, domain_sizes_);
  }

References gum::Triangulation::domain_sizes_, and elimination_sequence_strategy_.

Referenced by _triangulate_(), and junctionTreeStrategy().

Here is the caller graph for this function:

isMinimalityRequired()

virtual bool gum::StaticTriangulation::isMinimalityRequired ( ) const

finalvirtualinherited

indicates wether minimality is required

junctionTree()

const CliqueGraph & gum::StaticTriangulation::junctionTree ( )

overridevirtualinherited

returns a compatible junction tree

Implements gum::Triangulation.

Referenced by _computeMaxPrimeJunctionTree_(), fillIns(), and triangulatedGraph().

Here is the caller graph for this function:

junctionTreeStrategy()

JunctionTreeStrategy & gum::StaticTriangulation::junctionTreeStrategy ( ) const

inherited

returns the junction tree strategy used by the triangulation

References StaticTriangulation(), initTriangulation_(), and junctionTreeStrategy().

Referenced by junctionTreeStrategy().

Here is the call graph for this function:

Here is the caller graph for this function:

maxLog10CliqueDomainSize()

double gum::Triangulation::maxLog10CliqueDomainSize ( )

inherited

returns the max of log10DomainSize of the cliques in the junction tree.

This is useful for instance to estimate the complexity (both in space and in time) of the inference that will use the junction tree.

This method is not 'const' since it can be called before building any junction tree and hence it needs to build it...

Definition at line 86 of file triangulation.cpp.

                                                 {
    double              res = 0.0;
    double              dSize;
    const JunctionTree& jt = junctionTree();   // here, the fact that we get
    // a junction tree ensures that domain_sizes_ is different from nullptr
 
    for (const NodeId cl: jt) {
      dSize = 0.0;
 
      for (const auto node: jt.clique(cl))
        dSize += std::log10((*domain_sizes_)[node]);
 
      if (res < dSize) res = dSize;
    }
 
    return res;
  }

References gum::CliqueGraph::clique(), domain_sizes_, and junctionTree().

Referenced by gum::MaxInducedWidthMCBayesNetGenerator< GUM_SCALAR, ICPTGenerator, ICPTDisturber >::_checkConditions_().

Here is the call graph for this function:

Here is the caller graph for this function:

maxPrimeSubgraphTree()

const CliqueGraph & gum::StaticTriangulation::maxPrimeSubgraphTree ( )

overridevirtualinherited

returns a junction tree of maximal prime subgraphs

Warning

Actually, the cliques of the junction tree are guarranteed to be maximal prime subgraph of the original graph that was triangulated only if the triangulation performed is minimal (in the sense that removing any edge in the triangulated graph results in a nontriangulated graph). This can be ensured by requiring minimality of the triangulation.

Implements gum::Triangulation.

newFactory()

DefaultTriangulation * gum::DefaultTriangulation::newFactory ( ) const

nodiscardoverridevirtual

virtual clone constructor

returns a fresh triangulation (over an empty graph) of the same type as the current object

note that we return a pointer as it enables subclasses to return pointers to their types, not Triangulation pointers. See item 25 of the more effective C++.

Implements gum::UnconstrainedTriangulation.

References DefaultTriangulation().

Here is the call graph for this function:

operator=()

DefaultTriangulation & gum::DefaultTriangulation::operator= ( const DefaultTriangulation & )

private

forbid copy operator

References DefaultTriangulation().

Here is the call graph for this function:

originalGraph()

const UndiGraph * gum::StaticTriangulation::originalGraph ( ) const

inherited

returns the graph to be triangulated

Warning

if we have not set yet a graph, then originalGraph () will return a nullptr.

References originalGraph().

Referenced by gum::DefaultJunctionTreeStrategy::copyFactory(), and originalGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

reverseEliminationOrder()

const NodeProperty< NodeId > & gum::StaticTriangulation::reverseEliminationOrder ( )

inherited

returns a table indicating, for each node, at which step it was deleted by the triangulation process

setFillIns()

void gum::StaticTriangulation::setFillIns ( bool )

inherited

sets/unsets the record of the fill-ins in the standard triangulation procedure

References setFillIns().

Referenced by setFillIns().

Here is the call graph for this function:

Here is the caller graph for this function:

setGraph()

void gum::StaticTriangulation::setGraph ( const UndiGraph * graph, const NodeProperty< Size > * domsizes )

overridevirtualinherited

initialize the triangulation data structures for a new graph

Parameters

graph	the graph to be triangulated, i.e., the nodes of which will be eliminated
domsizes	the domain sizes of the nodes to be eliminated

Warning

Note that we allow domsizes 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 not copied but only referenced by the elimination sequence algorithm.

Implements gum::Triangulation.

Definition at line 524 of file staticTriangulation.cpp.

                                                                                                 {
    // remove the old graph
    clear();
 
    if (graph != nullptr) {
      // prepare the size of the data for the new graph
      _elim_order_.resize(graph->size());
      _reverse_elim_order_.resize(graph->size());
      _elim_cliques_.resize(graph->size());
      _added_fill_ins_.resize(graph->size());
      _node_2_max_prime_clique_.resize(graph->size());
    }
 
    // keep track of the variables passed in argument
    _original_graph_ = graph;
    domain_sizes_    = domsizes;
 
    // indicate that no triangulation was performed for this graph
    _has_triangulation_           = false;
    _has_triangulated_graph_      = false;
    _has_elimination_tree_        = false;
    _has_junction_tree_           = false;
    _has_max_prime_junction_tree_ = false;
    _has_fill_ins_                = false;
  }

References _added_fill_ins_, _elim_cliques_, _elim_order_, _has_elimination_tree_, _has_fill_ins_, _has_junction_tree_, _has_max_prime_junction_tree_, _has_triangulated_graph_, _has_triangulation_, _node_2_max_prime_clique_, _original_graph_, _reverse_elim_order_, clear(), and gum::Triangulation::domain_sizes_.

Referenced by gum::OrderedTriangulation::setGraph(), and gum::PartialOrderedTriangulation::setGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

setMinimalRequirement()

void gum::StaticTriangulation::setMinimalRequirement ( bool )

inherited

sets/unset the minimality requirement

triangulatedGraph()

const UndiGraph & gum::StaticTriangulation::triangulatedGraph ( )

overridevirtualinherited

returns the triangulated graph

Implements gum::Triangulation.

Definition at line 485 of file staticTriangulation.cpp.

                                                          {
    if (!_has_triangulation_) _triangulate_();
 
    // if we did not construct the triangulated graph during the triangulation,
    // that is, we just constructed the junction tree, we shall construct it now
    if (!_has_triangulated_graph_) {
      // just in case, be sure that the junction tree has been constructed
      if (!_has_junction_tree_) junctionTree();
 
      // copy the original graph
      _triangulated_graph_ = *_original_graph_;
 
      for (const auto clik_id: *_junction_tree_) {
        // for each clique, add the edges necessary to make it complete
        const NodeSet&        clique = _junction_tree_->clique(clik_id);
        std::vector< NodeId > clique_nodes(clique.size());
        unsigned int          i = 0;
 
        for (const auto node: clique) {
          clique_nodes[i] = node;
          i += 1;
        }
 
        for (i = 0; i < clique_nodes.size(); ++i) {
          for (unsigned int j = i + 1; j < clique_nodes.size(); ++j) {
            try {
              _triangulated_graph_.addEdge(clique_nodes[i], clique_nodes[j]);
            } catch (DuplicateElement const&) {}
          }
        }
      }
 
      _has_triangulated_graph_ = true;
    }
 
    return _triangulated_graph_;
  }

References _has_junction_tree_, _has_triangulated_graph_, _has_triangulation_, _junction_tree_, _original_graph_, _triangulate_(), _triangulated_graph_, junctionTree(), and gum::Set< Key >::size().

Here is the call graph for this function:

Member Data Documentation

_added_fill_ins_

std::vector< EdgeSet > gum::StaticTriangulation::_added_fill_ins_

privateinherited

a vector containing the set of fill-ins added after each node elimination (used by recursive thinning)

Definition at line 312 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), _computeRecursiveThinning_(), _triangulate_(), clear(), and setGraph().

_elim_cliques_

NodeProperty< NodeSet > gum::StaticTriangulation::_elim_cliques_

privateinherited

the cliques formed by the elimination of the nodes

Definition at line 270 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), _computeRecursiveThinning_(), _triangulate_(), clear(), and setGraph().

_elim_order_

std::vector< NodeId > gum::StaticTriangulation::_elim_order_

privateinherited

the order in which nodes are eliminated by the algorithm

Definition at line 264 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), _computeRecursiveThinning_(), _triangulate_(), clear(), and setGraph().

_elim_tree_

CliqueGraph gum::StaticTriangulation::_elim_tree_

privateinherited

the elimination tree computed by the algorithm

Definition at line 273 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), and clear().

_fill_ins_

EdgeSet gum::StaticTriangulation::_fill_ins_

privateinherited

the fill-ins added during the whole triangulation process

Definition at line 261 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), _computeRecursiveThinning_(), _triangulate_(), clear(), and fillIns().

_has_elimination_tree_

bool gum::StaticTriangulation::_has_elimination_tree_ {false}

privateinherited

a boolean indicating whether the elimination tree has been computed

Definition at line 295 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), clear(), and setGraph().

_has_fill_ins_

bool gum::StaticTriangulation::_has_fill_ins_ {false}

privateinherited

indicates whether we actually computed fill-ins

Definition at line 305 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _computeRecursiveThinning_(), _triangulate_(), clear(), fillIns(), and setGraph().

_has_junction_tree_

bool gum::StaticTriangulation::_has_junction_tree_ {false}

privateinherited

a boolean indicating whether the junction tree has been constructed

Definition at line 298 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _computeMaxPrimeJunctionTree_(), clear(), fillIns(), setGraph(), and triangulatedGraph().

_has_max_prime_junction_tree_

bool gum::StaticTriangulation::_has_max_prime_junction_tree_ {false}

privateinherited

indicates whether a maximal prime subgraph junction tree has been constructed

Definition at line 302 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _computeMaxPrimeJunctionTree_(), clear(), and setGraph().

_has_triangulated_graph_

bool gum::StaticTriangulation::_has_triangulated_graph_ {false}

privateinherited

a boolean indicating whether we have constructed the triangulated graph

Definition at line 292 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _triangulate_(), clear(), setGraph(), and triangulatedGraph().

_has_triangulation_

bool gum::StaticTriangulation::_has_triangulation_ {false}

privateinherited

a boolean indicating whether we have parformed a triangulation

Definition at line 289 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), _triangulate_(), clear(), fillIns(), setGraph(), and triangulatedGraph().

_junction_tree_

const CliqueGraph* gum::StaticTriangulation::_junction_tree_ {nullptr}

privateinherited

the junction tree computed by the algorithm

note that the junction tree is owned by the junctionTreeStrategy and, therefore, its deletion from memory is not handled by the static triangulation class.

Definition at line 279 of file staticTriangulation.h.

{nullptr};

Referenced by StaticTriangulation(), _computeMaxPrimeJunctionTree_(), _computeMaxPrimeMergings_(), clear(), fillIns(), and triangulatedGraph().

_max_prime_junction_tree_

CliqueGraph gum::StaticTriangulation::_max_prime_junction_tree_

privateinherited

the maximal prime subgraph junction tree computed from the junction tree

Definition at line 282 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), _computeMaxPrimeJunctionTree_(), and clear().

_minimality_required_

bool gum::StaticTriangulation::_minimality_required_ {false}

privateinherited

indicates whether the triangulation must be minimal

Definition at line 308 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), and _triangulate_().

_node_2_max_prime_clique_

NodeProperty< NodeId > gum::StaticTriangulation::_node_2_max_prime_clique_

privateinherited

indicates which clique of the max prime junction tree was created by the elmination of a given node (the key of the table)

Definition at line 286 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), _computeMaxPrimeJunctionTree_(), clear(), and setGraph().

_original_graph_

const UndiGraph* gum::StaticTriangulation::_original_graph_ {nullptr}

privateinherited

a pointer to the (external) original graph (which will be triangulated)

Definition at line 255 of file staticTriangulation.h.

{nullptr};

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), _computeMaxPrimeMergings_(), _triangulate_(), clear(), fillIns(), setGraph(), and triangulatedGraph().

_quasi_ratio_

double gum::DefaultTriangulation::_quasi_ratio_

private

the ratio above which we consider nodes to be quasi simplicial

Definition at line 126 of file defaultTriangulation.h.

_reverse_elim_order_

NodeProperty< NodeId > gum::StaticTriangulation::_reverse_elim_order_

privateinherited

the elimination order (access by NodeId)

Definition at line 267 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), _computeEliminationTree_(), _computeRecursiveThinning_(), _triangulate_(), clear(), and setGraph().

_threshold_

double gum::DefaultTriangulation::_threshold_

private

threshold under which almost and quasi simplicial nodes can be chosen to be eliminated

Definition at line 130 of file defaultTriangulation.h.

_triangulated_graph_

UndiGraph gum::StaticTriangulation::_triangulated_graph_

privateinherited

the triangulated graph

Definition at line 258 of file staticTriangulation.h.

Referenced by StaticTriangulation(), StaticTriangulation(), _computeRecursiveThinning_(), _triangulate_(), clear(), and triangulatedGraph().

_we_want_fill_ins_

bool gum::StaticTriangulation::_we_want_fill_ins_ {false}

privateinherited

a boolean indicating if we want fill-ins list with the standard triangulation method

Definition at line 316 of file staticTriangulation.h.

{false};

Referenced by StaticTriangulation(), StaticTriangulation(), _triangulate_(), and fillIns().

domain_sizes_

const NodeProperty< Size >* gum::Triangulation::domain_sizes_ {nullptr}

protectedinherited

the domain sizes of the variables/nodes of the graph

Definition at line 170 of file triangulation.h.

{nullptr};

Referenced by Triangulation(), Triangulation(), Triangulation(), gum::OrderedTriangulation::initTriangulation_(), gum::PartialOrderedTriangulation::initTriangulation_(), gum::StaticTriangulation::initTriangulation_(), maxLog10CliqueDomainSize(), and gum::StaticTriangulation::setGraph().

elimination_sequence_strategy_

EliminationSequenceStrategy* gum::StaticTriangulation::elimination_sequence_strategy_ {nullptr}

protectedinherited

the elimination sequence strategy used by the triangulation

Definition at line 247 of file staticTriangulation.h.

{nullptr};

Referenced by gum::OrderedTriangulation::OrderedTriangulation(), gum::PartialOrderedTriangulation::PartialOrderedTriangulation(), StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), ~StaticTriangulation(), _triangulate_(), clear(), fillIns(), gum::OrderedTriangulation::initTriangulation_(), gum::PartialOrderedTriangulation::initTriangulation_(), initTriangulation_(), gum::OrderedTriangulation::newFactory(), gum::PartialOrderedTriangulation::newFactory(), gum::OrderedTriangulation::setGraph(), gum::PartialOrderedTriangulation::setGraph(), gum::OrderedTriangulation::setOrder(), and gum::PartialOrderedTriangulation::setPartialOrder().

junction_tree_strategy_

JunctionTreeStrategy* gum::StaticTriangulation::junction_tree_strategy_ {nullptr}

protectedinherited

the junction tree strategy used by the triangulation

Definition at line 250 of file staticTriangulation.h.

{nullptr};

Referenced by StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), StaticTriangulation(), ~StaticTriangulation(), _computeMaxPrimeJunctionTree_(), clear(), gum::OrderedTriangulation::newFactory(), and gum::PartialOrderedTriangulation::newFactory().

---

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

• agrum/base/graphs/algorithms/triangulations/defaultTriangulation.h