class for graph triangulations for which we enforce a given partial ordering on the nodes eliminations, that is, the set of all the nodes is divided into several subsets. More...

#include <partialOrderedTriangulation.h>

Inheritance diagram for gum::PartialOrderedTriangulation:

Collaboration diagram for gum::PartialOrderedTriangulation:

Public Member Functions
Constructors / Destructors
	PartialOrderedTriangulation (const PartialOrderedEliminationSequenceStrategy &elimSeq=DefaultPartialOrderedEliminationSequenceStrategy(), const JunctionTreeStrategy &JTStrategy=DefaultJunctionTreeStrategy(), bool minimality=false)
	default constructor
	PartialOrderedTriangulation (const UndiGraph graph, const NodeProperty< Size > domsizes, const List< NodeSet > *partial_order, const PartialOrderedEliminationSequenceStrategy &elimSeq=DefaultPartialOrderedEliminationSequenceStrategy(), const JunctionTreeStrategy &JTStrategy=DefaultJunctionTreeStrategy(), bool minimality=false)
	constructor with a given graph
	PartialOrderedTriangulation (const PartialOrderedTriangulation &from)
	copy constructor
	PartialOrderedTriangulation (PartialOrderedTriangulation &&from)
	move constructor
virtual PartialOrderedTriangulation *	newFactory () const
	returns a fresh triangulation (over an empty graph) of the same type as the current object
virtual PartialOrderedTriangulation *	copyFactory () const final
	virtual copy constructor
virtual	~PartialOrderedTriangulation ()
	destructor
Accessors / Modifiers
virtual void	setGraph (const UndiGraph graph, const NodeProperty< Size > domsizes) final
	initialize the triangulation data structures for a new graph
virtual void	setPartialOrder (const List< NodeSet > *partial_order) final
	sets the elimination sequence's partial order (only a reference is stored)
Accessors / Modifiers
const EdgeSet &	fillIns ()
	returns the fill-ins added by the triangulation algorithm
const std::vector< NodeId > &	eliminationOrder ()
	returns an elimination ordering compatible with the triangulated graph
Idx	eliminationOrder (const NodeId)
	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 ()
	returns the triangulated graph
const CliqueGraph &	eliminationTree ()
	returns the elimination tree of a compatible ordering
const CliqueGraph &	junctionTree ()
	returns a compatible junction tree
NodeId	createdJunctionTreeClique (const NodeId id)
	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 ()
	returns the Ids of the cliques of the junction tree created by the elimination of the nodes
const CliqueGraph &	maxPrimeSubgraphTree ()
	returns a junction tree of maximal prime subgraphs
NodeId	createdMaxPrimeSubgraph (const NodeId id)
	returns the Id of the maximal prime subgraph created by the elimination of a given node during the triangulation process
void	clear ()
	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
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 Member Functions
virtual void	initTriangulation_ (UndiGraph &graph) final
	the function called to initialize the triangulation process

Protected Attributes
const List< NodeSet > *	_partial_order_ {nullptr}
	the partial ordering to apply to eliminate nodes
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
PartialOrderedTriangulation &	operator= (const PartialOrderedTriangulation &)
	forbid copy operator
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 redondant 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

Private Attributes
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

Detailed Description

class for graph triangulations for which we enforce a given partial ordering on the nodes eliminations, 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 72 of file partialOrderedTriangulation.h.

Constructor & Destructor Documentation

◆ PartialOrderedTriangulation() [1/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation	(	const PartialOrderedEliminationSequenceStrategy &	elimSeq = DefaultPartialOrderedEliminationSequenceStrategy(),
		const JunctionTreeStrategy &	JTStrategy = DefaultJunctionTreeStrategy(),
		bool	minimality = false )

default constructor

Parameters

elimSeq	the elimination sequence used to triangulate the graph
JTStrategy	the junction tree strategy used to create junction trees
minimality	a Boolean indicating whether we should enforce that the triangulation is minimal w.r.t. inclusion

Definition at line 56 of file partialOrderedTriangulation.cpp.

                       : StaticTriangulation(elimSeq, JTStrategy, minimality) {
    // for debugging purposes
    GUM_CONSTRUCTOR(PartialOrderedTriangulation);
  }

References PartialOrderedTriangulation(), and gum::StaticTriangulation::StaticTriangulation().

Referenced by PartialOrderedTriangulation(), PartialOrderedTriangulation(), PartialOrderedTriangulation(), PartialOrderedTriangulation(), ~PartialOrderedTriangulation(), copyFactory(), newFactory(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PartialOrderedTriangulation() [2/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation	(	const UndiGraph *	graph,
		const NodeProperty< Size > *	domsizes,
		const List< NodeSet > *	partial_order,
		const PartialOrderedEliminationSequenceStrategy &	elimSeq = DefaultPartialOrderedEliminationSequenceStrategy(),
		const JunctionTreeStrategy &	JTStrategy = DefaultJunctionTreeStrategy(),
		bool	minimality = false )

constructor with a given 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
partial_order	the list of the subsets constituting the partial ordering
elimSeq	the elimination sequence used to triangulate the graph
JTStrategy	the junction tree strategy used to create junction trees
minimality	a Boolean indicating whether we should enforce that the triangulation is minimal w.r.t. inclusion

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; note that, by aGrUM's rule, the graph, the domain sizes and the partial ordering are not copied but only referenced by the triangulation algorithm.

Definition at line 65 of file partialOrderedTriangulation.cpp.

                                                                   :
      StaticTriangulation(theGraph, dom, elimSeq, JTStrategy, minimality),
      _partial_order_(partial_order) {
    static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_)
        ->setPartialOrder(_partial_order_);
 
    // for debugging purposes
    GUM_CONSTRUCTOR(PartialOrderedTriangulation);
  }

References PartialOrderedTriangulation(), gum::StaticTriangulation::StaticTriangulation(), _partial_order_, gum::StaticTriangulation::elimination_sequence_strategy_, and gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder().

Here is the call graph for this function:

◆ PartialOrderedTriangulation() [3/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation ( const PartialOrderedTriangulation & from )

copy constructor

Definition at line 82 of file partialOrderedTriangulation.cpp.

                                               :
      StaticTriangulation(from), _partial_order_(from._partial_order_) {
    // for debugging purposes
    GUM_CONS_CPY(PartialOrderedTriangulation);
  }

References PartialOrderedTriangulation(), gum::StaticTriangulation::StaticTriangulation(), and _partial_order_.

Here is the call graph for this function:

◆ PartialOrderedTriangulation() [4/4]

gum::PartialOrderedTriangulation::PartialOrderedTriangulation ( PartialOrderedTriangulation && from )

move constructor

Definition at line 90 of file partialOrderedTriangulation.cpp.

                                                                                             :
      StaticTriangulation(std::move(from)), _partial_order_(from._partial_order_) {
    // for debugging purposes
    GUM_CONS_MOV(PartialOrderedTriangulation);
  }

References PartialOrderedTriangulation(), gum::StaticTriangulation::StaticTriangulation(), and _partial_order_.

Here is the call graph for this function:

◆ ~PartialOrderedTriangulation()

gum::PartialOrderedTriangulation::~PartialOrderedTriangulation ( )

virtual

destructor

Definition at line 110 of file partialOrderedTriangulation.cpp.

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

References PartialOrderedTriangulation().

Here is the call graph for this function:

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 redondant 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)) {
          try {
            numbered_neighbours.setPriority(neighbour, 1 + numbered_neighbours.priority(neighbour));
          } catch (NotFound const&) {}
        }
      }
    }
 
    // 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::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;
 
    // 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(), 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 ( )

virtualinherited

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

PartialOrderedTriangulation * gum::PartialOrderedTriangulation::copyFactory ( ) const

finalvirtual

virtual copy constructor

Implements gum::StaticTriangulation.

Definition at line 105 of file partialOrderedTriangulation.cpp.

                                                                              {
    return new PartialOrderedTriangulation(*this);
  }

References PartialOrderedTriangulation().

Here is the call graph for this function:

◆ createdJunctionTreeClique()

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

virtualinherited

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

virtualinherited

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 )

virtualinherited

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

virtualinherited

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 )

virtualinherited

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

virtualinherited

returns the elimination tree of a compatible ordering

Implements gum::Triangulation.

◆ fillIns()

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

virtualinherited

returns the fill-ins added by the triangulation algorithm

Implements gum::Triangulation.

Definition at line 672 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::PartialOrderedTriangulation::initTriangulation_ ( UndiGraph & graph )

finalprotectedvirtual

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 need 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 from gum::StaticTriangulation.

Definition at line 131 of file partialOrderedTriangulation.cpp.

                                                                       {
    PartialOrderedEliminationSequenceStrategy* elim
        = static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_);
    elim->setGraph(&graph, domain_sizes_);
    elim->setPartialOrder(_partial_order_);
  }

References _partial_order_, gum::Triangulation::domain_sizes_, gum::StaticTriangulation::elimination_sequence_strategy_, gum::PartialOrderedEliminationSequenceStrategy::setGraph(), and gum::PartialOrderedEliminationSequenceStrategy::setPartialOrder().

Here is the call graph for this function:

◆ isMinimalityRequired()

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

finalvirtualinherited

indicates wether minimality is required

◆ junctionTree()

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

virtualinherited

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

virtualinherited

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

PartialOrderedTriangulation * gum::PartialOrderedTriangulation::newFactory ( ) const

virtual

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

virtual copy constructor

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

Definition at line 97 of file partialOrderedTriangulation.cpp.

                                                                             {
    return new PartialOrderedTriangulation(
        static_cast< const PartialOrderedEliminationSequenceStrategy& >(
            *elimination_sequence_strategy_),
        *junction_tree_strategy_);
  }

References PartialOrderedTriangulation(), gum::StaticTriangulation::elimination_sequence_strategy_, and gum::StaticTriangulation::junction_tree_strategy_.

Here is the call graph for this function:

◆ operator=()

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

private

forbid copy operator

References PartialOrderedTriangulation().

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::PartialOrderedTriangulation::setGraph	(	const UndiGraph *	graph,
		const NodeProperty< Size > *	domsizes )

finalvirtual

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
sequence	the order in which the nodes should be eliminated

Warning: note that, by aGrUM's rule, the graph and the domain sizes are not notcopied but only referenced by the triangulation algorithm.

Reimplemented from gum::StaticTriangulation.

Definition at line 116 of file partialOrderedTriangulation.cpp.

                                                                                   {
    StaticTriangulation::setGraph(graph, domsizes);
    static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_)
        ->setPartialOrder(_partial_order_);
  }

References _partial_order_, gum::StaticTriangulation::elimination_sequence_strategy_, gum::StaticTriangulation::setGraph(), and setPartialOrder().

Here is the call graph for this function:

◆ setMinimalRequirement()

void gum::StaticTriangulation::setMinimalRequirement ( bool )

inherited

sets/unset the minimality requirement

◆ setPartialOrder()

void gum::PartialOrderedTriangulation::setPartialOrder ( const List< NodeSet > * partial_order )

finalvirtual

sets the elimination sequence's partial order (only a reference is stored)

sets the sequence of elimination

The elimination sequence is kept outside this class for efficiency reasons.

Definition at line 124 of file partialOrderedTriangulation.cpp.

                                                                                        {
    _partial_order_ = partial_order;
    static_cast< PartialOrderedEliminationSequenceStrategy* >(elimination_sequence_strategy_)
        ->setPartialOrder(_partial_order_);
  }

References _partial_order_, gum::StaticTriangulation::elimination_sequence_strategy_, and setPartialOrder().

Referenced by setGraph(), and setPartialOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ triangulatedGraph()

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

virtualinherited

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.

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

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

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

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

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

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

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

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

255{nullptr};

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

◆ _partial_order_

const List< NodeSet >* gum::PartialOrderedTriangulation::_partial_order_ {nullptr}

protected

the partial ordering to apply to eliminate nodes

Definition at line 178 of file partialOrderedTriangulation.h.

178{nullptr};

Referenced by PartialOrderedTriangulation(), PartialOrderedTriangulation(), PartialOrderedTriangulation(), initTriangulation_(), setGraph(), and setPartialOrder().

◆ _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().

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

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

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

247{nullptr};

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

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

agrum/base/graphs/algorithms/triangulations/partialOrderedTriangulation.h
agrum/base/graphs/algorithms/triangulations/partialOrderedTriangulation.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PartialOrderedTriangulation() [1/4]

◆ PartialOrderedTriangulation() [2/4]

◆ PartialOrderedTriangulation() [3/4]

◆ PartialOrderedTriangulation() [4/4]

◆ ~PartialOrderedTriangulation()

Member Function Documentation

◆ _computeEliminationTree_()

◆ _computeMaxPrimeJunctionTree_()

◆ _computeMaxPrimeMergings_()

◆ _computeRecursiveThinning_()

◆ _triangulate_()

◆ clear()

◆ copyFactory()

◆ createdJunctionTreeClique()

◆ createdJunctionTreeCliques()

◆ createdMaxPrimeSubgraph()

◆ domainSizes()

◆ eliminationOrder() [1/2]

◆ eliminationOrder() [2/2]

◆ eliminationSequenceStrategy()

◆ eliminationTree()

◆ fillIns()

◆ initTriangulation_()

◆ isMinimalityRequired()

◆ junctionTree()

◆ junctionTreeStrategy()

◆ maxLog10CliqueDomainSize()

◆ maxPrimeSubgraphTree()

◆ newFactory()

◆ operator=()

◆ originalGraph()

◆ reverseEliminationOrder()

◆ setFillIns()

◆ setGraph()

◆ setMinimalRequirement()

◆ setPartialOrder()

◆ triangulatedGraph()

Member Data Documentation

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

◆ _minimality_required_

◆ _node_2_max_prime_clique_

◆ _original_graph_

◆ _partial_order_

◆ _reverse_elim_order_

◆ _triangulated_graph_

◆ _we_want_fill_ins_

◆ domain_sizes_

◆ elimination_sequence_strategy_

◆ junction_tree_strategy_