gum::DefaultJunctionTreeStrategy Class Reference

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

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

Detailed Description

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

Definition at line 43 of file defaultJunctionTreeStrategy.h.

Constructor & Destructor Documentation

DefaultJunctionTreeStrategy() [1/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy

(

)

default constructor

Definition at line 38 of file defaultJunctionTreeStrategy.cpp.

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

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

Here is the call graph for this function:

DefaultJunctionTreeStrategy() [2/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy

(

const DefaultJunctionTreeStrategy &

from

)

copy constructor

Definition at line 44 of file defaultJunctionTreeStrategy.cpp.

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

                                              :
      JunctionTreeStrategy(from),
      has_junction_tree__(from.has_junction_tree__),
      junction_tree__(from.junction_tree__),
      node_2_junction_clique__(from.node_2_junction_clique__) {
    // for debugging purposes
    GUM_CONS_CPY(DefaultJunctionTreeStrategy);
  }

Here is the call graph for this function:

DefaultJunctionTreeStrategy() [3/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy

(

DefaultJunctionTreeStrategy &&

from

)

move constructor

Definition at line 55 of file defaultJunctionTreeStrategy.cpp.

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

                                         :
      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__)) {
    // for debugging purposes
    GUM_CONS_MOV(DefaultJunctionTreeStrategy);
  }

Here is the call graph for this function:

~DefaultJunctionTreeStrategy()

gum::DefaultJunctionTreeStrategy::~DefaultJunctionTreeStrategy ( )

virtual

destructor

Definition at line 66 of file defaultJunctionTreeStrategy.cpp.

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

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

Here is the call graph for this function:

Member Function Documentation

clear()

void gum::DefaultJunctionTreeStrategy::clear ( )

finalvirtual

resets the current junction tree strategy data structures

Implements gum::JunctionTreeStrategy.

Definition at line 139 of file defaultJunctionTreeStrategy.cpp.

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

                                          {
    has_junction_tree__ = false;
    junction_tree__.clear();
    node_2_junction_clique__.clear();
  }

Here is the call graph for this function:

computeJunctionTree__()

void gum::DefaultJunctionTreeStrategy::computeJunctionTree__ ( )

private

computes a junction tree from an elimination tree

Definition at line 146 of file defaultJunctionTreeStrategy.cpp.

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

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

Here is the call 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 78 of file defaultJunctionTreeStrategy.cpp.

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

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

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 123 of file defaultJunctionTreeStrategy.cpp.

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

                                                                   {
    // compute the junction tree only if it does not already exist
    if (!has_junction_tree__) computeJunctionTree__();

    return node_2_junction_clique__[id];
  }

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 114 of file defaultJunctionTreeStrategy.cpp.

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

                                                                            {
    // compute the junction tree only if it does not already exist
    if (!has_junction_tree__) computeJunctionTree__();

    return 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 131 of file defaultJunctionTreeStrategy.cpp.

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

                                                               {
    // compute the junction tree only if it does not already exist
    if (!has_junction_tree__) computeJunctionTree__();

    return 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 62 of file junctionTreeStrategy.cpp.

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

                                                                               {
    triangulation_ = triangulation;
  }

Here is the call graph for this function:

newFactory()

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

finalvirtual

create a clone not assigned to any triangulation algorithm

Implements gum::JunctionTreeStrategy.

Definition at line 72 of file defaultJunctionTreeStrategy.cpp.

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

                                                                             {
    return new 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 105 of file defaultJunctionTreeStrategy.cpp.

{ 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 108 of file defaultJunctionTreeStrategy.cpp.

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

                                                                            {
    clear();
    triangulation_ = tr;
  }

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 129 of file defaultJunctionTreeStrategy.h.

junction_tree__

CliqueGraph gum::DefaultJunctionTreeStrategy::junction_tree__

private

the junction tree computed by the algorithm

Definition at line 132 of file defaultJunctionTreeStrategy.h.

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 136 of file defaultJunctionTreeStrategy.h.

triangulation_

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

protectedinherited

the triangulation to which the junction tree is associated

Definition at line 117 of file junctionTreeStrategy.h.

---

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

• agrum/tools/graphs/algorithms/triangulations/junctionTreeStrategies/defaultJunctionTreeStrategy.h
• agrum/tools/graphs/algorithms/triangulations/junctionTreeStrategies/defaultJunctionTreeStrategy.cpp