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

Constructor & Destructor Documentation

DefaultJunctionTreeStrategy() [1/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy

(

)

default constructor

Definition at line 36 of file defaultJunctionTreeStrategy.cpp.

Referenced by copyFactory(), and newFactory().

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

Here is the caller graph for this function:

DefaultJunctionTreeStrategy() [2/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy

(

const DefaultJunctionTreeStrategy &

from

)

copy constructor

Definition at line 42 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) {
    // for debugging purposes
    GUM_CONS_CPY(DefaultJunctionTreeStrategy);
  }

DefaultJunctionTreeStrategy() [3/3]

gum::DefaultJunctionTreeStrategy::DefaultJunctionTreeStrategy

(

DefaultJunctionTreeStrategy &&

from

)

move constructor

Definition at line 53 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)) {
    // for debugging purposes
    GUM_CONS_MOV(DefaultJunctionTreeStrategy);
  }

~DefaultJunctionTreeStrategy()

gum::DefaultJunctionTreeStrategy::~DefaultJunctionTreeStrategy ( )

virtual

destructor

Definition at line 64 of file defaultJunctionTreeStrategy.cpp.

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

Member Function Documentation

__computeJunctionTree()

void gum::DefaultJunctionTreeStrategy::__computeJunctionTree ( )

private

computes a junction tree from an elimination tree

Definition at line 144 of file defaultJunctionTreeStrategy.cpp.

References __has_junction_tree, __junction_tree, __node_2_junction_clique, gum::JunctionTreeStrategy::_triangulation, gum::CliqueGraph::addEdge(), gum::CliqueGraph::clique(), gum::EdgeGraphPart::edgesProperty(), gum::StaticTriangulation::eliminationOrder(), gum::StaticTriangulation::eliminationTree(), gum::CliqueGraph::eraseEdge(), gum::CliqueGraph::eraseNode(), GUM_ERROR, gum::HashTable< Key, Val, Alloc >::insert(), gum::EdgeGraphPart::neighbours(), and gum::Set< Key, Alloc >::size().

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

                                                          {
    // 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:

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

References __has_junction_tree, __junction_tree, __node_2_junction_clique, and gum::CliqueGraph::clear().

Referenced by setTriangulation().

                                          {
    __has_junction_tree = false;
    __junction_tree.clear();
    __node_2_junction_clique.clear();
  }

Here is the call graph for this function:

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

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

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

References __computeJunctionTree(), __has_junction_tree, and __node_2_junction_clique.

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

References __computeJunctionTree(), __has_junction_tree, and __node_2_junction_clique.

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

References __computeJunctionTree(), __has_junction_tree, and __junction_tree.

                                                               {
    // 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 60 of file junctionTreeStrategy.cpp.

References gum::JunctionTreeStrategy::_triangulation.

Referenced by gum::StaticTriangulation::StaticTriangulation().

                                                                               {
    _triangulation = triangulation;
  }

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

References DefaultJunctionTreeStrategy().

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

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

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

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

__junction_tree

CliqueGraph gum::DefaultJunctionTreeStrategy::__junction_tree

private

the junction tree computed by the algorithm

Definition at line 130 of file defaultJunctionTreeStrategy.h.

Referenced by __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 134 of file defaultJunctionTreeStrategy.h.

Referenced by __computeJunctionTree(), clear(), createdClique(), and createdCliques().

_triangulation

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

protectedinherited

the triangulation to which the junction tree is associated

Definition at line 115 of file junctionTreeStrategy.h.

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

---

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

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