An algorithm producing a junction given the elimination tree produced by a triangulation algorithm. More...

#include <defaultJunctionTreeStrategy.h>

Inheritance diagram for gum::DefaultJunctionTreeStrategy:

Collaboration diagram for gum::DefaultJunctionTreeStrategy:

Public Member Functions
Constructors / Destructors
	DefaultJunctionTreeStrategy ()
	default constructor
	DefaultJunctionTreeStrategy (const DefaultJunctionTreeStrategy &from)
	copy constructor
	DefaultJunctionTreeStrategy (DefaultJunctionTreeStrategy &&from)
	move constructor
virtual	~DefaultJunctionTreeStrategy ()
	destructor
virtual DefaultJunctionTreeStrategy *	newFactory () const final
	create a clone not assigned to any triangulation algorithm
virtual DefaultJunctionTreeStrategy *	copyFactory (StaticTriangulation *triangulation=nullptr) const final
	virtual copy constructor
Accessors / Modifiers
virtual bool	requiresFillIns () const final
	indicates whether the junction tree strategy needs fill-ins to work properly
virtual const CliqueGraph &	junctionTree () final
	returns the junction tree computed
virtual void	setTriangulation (StaticTriangulation *triangulation) final
	assigns the triangulation to the junction tree strategy
virtual const NodeProperty< NodeId > &	createdCliques () final
	returns, for each node, the clique of the junction tree which was created by its deletion
virtual NodeId	createdClique (const NodeId id) final
	returns the Id of the clique of the junction tree created by the elimination of a given node during the triangulation process
virtual void	clear () final
	resets the current junction tree strategy data structures
Accessors / Modifiers
virtual void	moveTriangulation (StaticTriangulation *triangulation)
	assigns a new triangulation to the junction tree strategy during a move construction

Protected Attributes
StaticTriangulation *	triangulation_ {nullptr}
	the triangulation to which the junction tree is associated

Private Member Functions
void	_computeJunctionTree_ ()
	computes a junction tree from an elimination tree

Private Attributes
bool	_has_junction_tree_ {false}
	a boolean indicating whether the junction tree has been constructed
CliqueGraph	_junction_tree_
	the junction tree computed by the algorithm
NodeProperty< NodeId >	_node_2_junction_clique_
	indicates which clique of the junction tree was created by the elimination of a given node (the key of the table)

Detailed Description

An algorithm producing a junction given the elimination tree produced by a triangulation algorithm.

Definition at line 63 of file defaultJunctionTreeStrategy.h.

Constructor & Destructor Documentation

◆ DefaultJunctionTreeStrategy() [1/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy ( )

default constructor

Definition at line 59 of file defaultJunctionTreeStrategy.cpp.

                                                           {
    GUM_CONSTRUCTOR(DefaultJunctionTreeStrategy);
  }

References DefaultJunctionTreeStrategy().

Referenced by DefaultJunctionTreeStrategy(), DefaultJunctionTreeStrategy(), DefaultJunctionTreeStrategy(), ~DefaultJunctionTreeStrategy(), copyFactory(), and newFactory().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DefaultJunctionTreeStrategy() [2/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy ( const DefaultJunctionTreeStrategy & from )

copy constructor

Definition at line 64 of file defaultJunctionTreeStrategy.cpp.

                                               :
      JunctionTreeStrategy(from), _has_junction_tree_(from._has_junction_tree_),
      _junction_tree_(from._junction_tree_),
      _node_2_junction_clique_(from._node_2_junction_clique_) {
    GUM_CONS_CPY(DefaultJunctionTreeStrategy);
  }

References DefaultJunctionTreeStrategy(), gum::JunctionTreeStrategy::JunctionTreeStrategy(), _has_junction_tree_, _junction_tree_, and _node_2_junction_clique_.

Here is the call graph for this function:

◆ DefaultJunctionTreeStrategy() [3/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy ( DefaultJunctionTreeStrategy && from )

move constructor

Definition at line 73 of file defaultJunctionTreeStrategy.cpp.

                                                                                             :
      JunctionTreeStrategy(std::move(from)), _has_junction_tree_(from._has_junction_tree_),
      _junction_tree_(std::move(from._junction_tree_)),
      _node_2_junction_clique_(std::move(from._node_2_junction_clique_)) {
    GUM_CONS_MOV(DefaultJunctionTreeStrategy);
  }

References DefaultJunctionTreeStrategy(), gum::JunctionTreeStrategy::JunctionTreeStrategy(), _has_junction_tree_, _junction_tree_, and _node_2_junction_clique_.

Here is the call graph for this function:

◆ ~DefaultJunctionTreeStrategy()

gum::DefaultJunctionTreeStrategy::~DefaultJunctionTreeStrategy ( )

virtual

destructor

Definition at line 81 of file defaultJunctionTreeStrategy.cpp.

                                                            {
    GUM_DESTRUCTOR(DefaultJunctionTreeStrategy);
    ;
  }

References DefaultJunctionTreeStrategy().

Here is the call graph for this function:

Member Function Documentation

◆ _computeJunctionTree_()

void gum::DefaultJunctionTreeStrategy::_computeJunctionTree_ ( )

private

computes a junction tree from an elimination tree

Definition at line 160 of file defaultJunctionTreeStrategy.cpp.

                                                          {
    // if no triangulation is assigned to the strategy, we cannot compute
    // the junction tree, so raise an exception
    if (triangulation_ == nullptr)
      GUM_ERROR(UndefinedElement,
                "No triangulation has been assigned to "
                "the DefaultJunctionTreeStrategy")
 
    // copy the elimination tree into the junction tree
    _junction_tree_ = triangulation_->eliminationTree();
 
    // mark all the edges of the junction tree to false
    EdgeProperty< bool > mark = _junction_tree_.edgesProperty(false);
 
    // create a vector indicating by which clique a given clique has been
    // substituted during the transformation from the elimination tree to the
    // junction tree. Assume that clique J of the elimination tree has been
    // substituted by clique K of the elimination tree, and that clique J
    // (resp. K) was the jth (resp. kth) one created during the triangulation
    // process. Then, in the vector below, substitution[j] = k.
    const std::vector< NodeId >& elim_order = triangulation_->eliminationOrder();
 
    auto                  size = elim_order.size();
    std::vector< NodeId > substitution(size);
    std::iota(substitution.begin(), substitution.end(), 0);
 
    // for all cliques C_i, from the last one created to the first one, check
    // if there exists a parent C_j (a neighbor created before C_i) such that
    // |C_j| = |C_i| + 1 and such that the edge is not marked. In this case,
    // this means that C_j contains C_i. Hence, we should remove C_i, and link
    // all of its neighbors to C_j. These links will be marked to true as no
    // such neighbor can be included in C_j (and conversely).
    if (size > 0) {
      for (auto i = size; i >= 1; --i) {
        const NodeId C_i             = NodeId(i - 1);
        const auto   card_C_i_plus_1 = _junction_tree_.clique(C_i).size() + 1;
 
        // search for C_j such that |C_j| = [C_i| + 1
        NodeId C_j = C_i;
 
        for (const auto C_jj: _junction_tree_.neighbours(C_i))
          if ((C_i > C_jj) && !mark[Edge(C_jj, C_i)]
              && (_junction_tree_.clique(C_jj).size() == card_C_i_plus_1)) {
            // ok, here we found a parent such that |C_jj| = [C_i| + 1
            C_j = C_jj;
            _junction_tree_.eraseEdge(Edge(C_j, C_i));
            break;
          }
 
        // if we found a C_j, link the neighbors of C_i to C_j
        if (C_j != C_i) {
          for (const auto nei: _junction_tree_.neighbours(C_i)) {
            _junction_tree_.addEdge(C_j, nei);
            mark.insert(Edge(C_j, nei), true);
          }
 
          // remove C_i
          substitution[C_i] = C_j;
          _junction_tree_.eraseNode(C_i);
        }
      }
    }
 
    // compute the transitive closure of vector substitution
    for (std::size_t i = 0; i < size; ++i)
      substitution[i] = substitution[substitution[i]];
 
    // using the transitive closure of vector substitution, compute for each
    // node the clique of the junction tree that was created by its
    // elimination during the triangulation
    for (NodeId i = NodeId(0); i < size; ++i) {
      _node_2_junction_clique_.insert(elim_order[i], substitution[i]);
    }
 
    _has_junction_tree_ = true;
  }

References _has_junction_tree_, _junction_tree_, _node_2_junction_clique_, GUM_ERROR, gum::HashTable< Key, Val >::insert(), and gum::JunctionTreeStrategy::triangulation_.

Referenced by createdClique(), createdCliques(), and junctionTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

void gum::DefaultJunctionTreeStrategy::clear ( )

finalvirtual

resets the current junction tree strategy data structures

Implements gum::JunctionTreeStrategy.

Definition at line 153 of file defaultJunctionTreeStrategy.cpp.

                                          {
    _has_junction_tree_ = false;
    _junction_tree_.clear();
    _node_2_junction_clique_.clear();
  }

References _has_junction_tree_, _junction_tree_, and _node_2_junction_clique_.

Referenced by setTriangulation().

Here is the caller graph for this function:

◆ copyFactory()

DefaultJunctionTreeStrategy * gum::DefaultJunctionTreeStrategy::copyFactory ( StaticTriangulation * triangulation = nullptr ) const

finalvirtual

virtual copy constructor

Parameters

triangulation if triangulation is different from nullptr, this becomes the new triangulation algorithm associated with the junction tree strategy

Implements gum::JunctionTreeStrategy.

Definition at line 93 of file defaultJunctionTreeStrategy.cpp.

                                                                            {
    if (tr == nullptr) {
      return new DefaultJunctionTreeStrategy(*this);
    } else {
      // here, we need to assign new triangulation "tr" to the new strategy
 
      // if there was already a triangulation associated with the current
      // strategy, 2 cases can obtain:
      // 1/ both  _triangulation_ and tr point toward the same graph to be
      //    triangulated. In this case, no need to recompute anything
      // 2/ they point toward different graphs. Then, we must indicate that
      //    the new strategy has not computed anything yet
      if ((triangulation_ != nullptr) && (tr->originalGraph() == triangulation_->originalGraph())) {
        auto new_strategy            = new DefaultJunctionTreeStrategy(*this);   // case 1/
        new_strategy->triangulation_ = tr;
        return new_strategy;
      } else {                                                                   // case 2/
        auto new_strategy = new DefaultJunctionTreeStrategy;
        new_strategy->setTriangulation(tr);
        return new_strategy;
      }
    }
  }

References DefaultJunctionTreeStrategy(), gum::StaticTriangulation::originalGraph(), and gum::JunctionTreeStrategy::triangulation_.

Here is the call graph for this function:

◆ createdClique()

NodeId gum::DefaultJunctionTreeStrategy::createdClique ( const NodeId id )

finalvirtual

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

Parameters

id	the id of the node in the original undirected graph whose created clique's id is looked for

Exceptions

UndefinedElement is raised if no triangulation has been assigned to the DefaultJunctionTreeStrategy

Implements gum::JunctionTreeStrategy.

Definition at line 137 of file defaultJunctionTreeStrategy.cpp.

                                                                   {
    // compute the junction tree only if it does not already exist
    if (!_has_junction_tree_) _computeJunctionTree_();
 
    return _node_2_junction_clique_[id];
  }

References _computeJunctionTree_(), _has_junction_tree_, and _node_2_junction_clique_.

Here is the call graph for this function:

◆ createdCliques()

const NodeProperty< NodeId > & gum::DefaultJunctionTreeStrategy::createdCliques ( )

finalvirtual

returns, for each node, the clique of the junction tree which was created by its deletion

Exceptions

UndefinedElement is raised if no triangulation has been assigned to the DefaultJunctionTreeStrategy

Implements gum::JunctionTreeStrategy.

Definition at line 128 of file defaultJunctionTreeStrategy.cpp.

                                                                            {
    // compute the junction tree only if it does not already exist
    if (!_has_junction_tree_) _computeJunctionTree_();
 
    return _node_2_junction_clique_;
  }

References _computeJunctionTree_(), _has_junction_tree_, and _node_2_junction_clique_.

Here is the call graph for this function:

◆ junctionTree()

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

finalvirtual

returns the junction tree computed

The idea behind this method is that the JunctionTreeStrategy asks its assigned triangulation (see method setTriangulation) all the data it needs to compute correctly the junction tree. For instance, it may asks for a triangulated graph or an elimination tree, or even the order of elimination of the nodes, etc. All these data are available from the triangulation class. Knowing these data, the junctionTreeStrategy computes and returns a junction tree corresponding to the triangulated graph.

Exceptions

UndefinedElement is raised if no triangulation has been assigned to the DefaultJunctionTreeStrategy

Implements gum::JunctionTreeStrategy.

Definition at line 145 of file defaultJunctionTreeStrategy.cpp.

                                                               {
    // compute the junction tree only if it does not already exist
    if (!_has_junction_tree_) _computeJunctionTree_();
 
    return _junction_tree_;
  }

References _computeJunctionTree_(), _has_junction_tree_, and _junction_tree_.

Here is the call graph for this function:

◆ moveTriangulation()

void gum::JunctionTreeStrategy::moveTriangulation ( StaticTriangulation * triangulation )

virtualinherited

assigns a new triangulation to the junction tree strategy during a move construction

Definition at line 80 of file junctionTreeStrategy.cpp.

                                                                                 {
    triangulation_ = triangulation;
  }

References triangulation_.

◆ newFactory()

DefaultJunctionTreeStrategy * gum::DefaultJunctionTreeStrategy::newFactory ( ) const

finalvirtual

create a clone not assigned to any triangulation algorithm

Implements gum::JunctionTreeStrategy.

Definition at line 87 of file defaultJunctionTreeStrategy.cpp.

                                                                             {
    return new DefaultJunctionTreeStrategy;
  }

References DefaultJunctionTreeStrategy().

Here is the call graph for this function:

◆ requiresFillIns()

bool gum::DefaultJunctionTreeStrategy::requiresFillIns ( ) const

finalvirtual

indicates whether the junction tree strategy needs fill-ins to work properly

If the junctionTreeStrategy needs fill-ins to work properly, its assigned triangulation instance (see method setTriangulation) will be commited to compute them.

Implements gum::JunctionTreeStrategy.

Definition at line 119 of file defaultJunctionTreeStrategy.cpp.

119{ return false; }

◆ setTriangulation()

void gum::DefaultJunctionTreeStrategy::setTriangulation ( StaticTriangulation * triangulation )

finalvirtual

assigns the triangulation to the junction tree strategy

Parameters

the	triangulation whose resulting cliques will be used to construct the junction tree

Warning: note that, by aGrUM's rule, the graph and the domain sizes are not copied but only referenced by the junction tree strategy.

Implements gum::JunctionTreeStrategy.

Definition at line 122 of file defaultJunctionTreeStrategy.cpp.

                                                                            {
    clear();
    triangulation_ = tr;
  }

References clear(), and gum::JunctionTreeStrategy::triangulation_.

Here is the call graph for this function:

Member Data Documentation

◆ _has_junction_tree_

bool gum::DefaultJunctionTreeStrategy::_has_junction_tree_ {false}

private

a boolean indicating whether the junction tree has been constructed

Definition at line 149 of file defaultJunctionTreeStrategy.h.

149{false};

Referenced by DefaultJunctionTreeStrategy(), DefaultJunctionTreeStrategy(), _computeJunctionTree_(), clear(), createdClique(), createdCliques(), and junctionTree().

◆ _junction_tree_

CliqueGraph gum::DefaultJunctionTreeStrategy::_junction_tree_

private

the junction tree computed by the algorithm

Definition at line 152 of file defaultJunctionTreeStrategy.h.

Referenced by DefaultJunctionTreeStrategy(), DefaultJunctionTreeStrategy(), _computeJunctionTree_(), clear(), and junctionTree().

◆ _node_2_junction_clique_

NodeProperty< NodeId > gum::DefaultJunctionTreeStrategy::_node_2_junction_clique_

private

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

Definition at line 156 of file defaultJunctionTreeStrategy.h.

Referenced by DefaultJunctionTreeStrategy(), DefaultJunctionTreeStrategy(), _computeJunctionTree_(), clear(), createdClique(), and createdCliques().

◆ triangulation_

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

protectedinherited

the triangulation to which the junction tree is associated

Definition at line 136 of file junctionTreeStrategy.h.

136{nullptr};

Referenced by JunctionTreeStrategy(), JunctionTreeStrategy(), gum::DefaultJunctionTreeStrategy::_computeJunctionTree_(), gum::DefaultJunctionTreeStrategy::copyFactory(), moveTriangulation(), and gum::DefaultJunctionTreeStrategy::setTriangulation().

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

agrum/base/graphs/algorithms/triangulations/junctionTreeStrategies/defaultJunctionTreeStrategy.h
agrum/base/graphs/algorithms/triangulations/junctionTreeStrategies/defaultJunctionTreeStrategy.cpp

Public Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ DefaultJunctionTreeStrategy() [1/3]

◆ DefaultJunctionTreeStrategy() [2/3]

◆ DefaultJunctionTreeStrategy() [3/3]

◆ ~DefaultJunctionTreeStrategy()

Member Function Documentation

◆ _computeJunctionTree_()

◆ clear()

◆ copyFactory()

◆ createdClique()

◆ createdCliques()

◆ junctionTree()

◆ moveTriangulation()

◆ newFactory()

◆ requiresFillIns()

◆ setTriangulation()

Member Data Documentation

◆ _has_junction_tree_

◆ _junction_tree_

◆ _node_2_junction_clique_

◆ triangulation_