gum::BinaryJoinTreeConverterDefault Class Reference

#include <binaryJoinTreeConverterDefault.h>

Collaboration diagram for gum::BinaryJoinTreeConverterDefault:

Public Member Functions
Constructors / Destructors
	BinaryJoinTreeConverterDefault ()
	default constructor
virtual	~BinaryJoinTreeConverterDefault ()
	destructor
Accessors/Modifiers
CliqueGraph	convert (const CliqueGraph &JT, const NodeProperty< Size > &domain_sizes, const NodeSet &roots)
	returns a binary join tree corresponding to clique graph JT
const NodeSet &	roots () const
	returns all the roots considered for all the connected components

Private Member Functions
	BinaryJoinTreeConverterDefault (const BinaryJoinTreeConverterDefault &)
	forbid copy constructor
BinaryJoinTreeConverterDefault &	operator= (const BinaryJoinTreeConverterDefault &)
	forbid copy operator
void	_markConnectedComponent_ (const CliqueGraph &JT, NodeId root, NodeProperty< bool > &mark) const
	a function used to mark the nodes belonging to a given connected component
void	_convertConnectedComponent_ (CliqueGraph &JT, NodeId current_node, NodeId from, const NodeProperty< Size > &domain_sizes, NodeProperty< bool > &mark) const
	convert a whole connected component into a binary join tree
void	_convertClique_ (CliqueGraph &JT, NodeId clique, NodeId from, const NodeProperty< Size > &domain_sizes) const
	convert a clique and its adjacent cliques into a binary join tree
float	_combinedSize_ (const NodeSet &nodes1, const NodeSet &nodes2, const NodeProperty< Size > &domain_sizes) const
	returns the domain size of the union of two cliques

Private Attributes
NodeSet	_roots_
	the new roots that have been created to compute the last query

Detailed Description

Definition at line 54 of file binaryJoinTreeConverterDefault.h.

Constructor & Destructor Documentation

BinaryJoinTreeConverterDefault() [1/2]

gum::BinaryJoinTreeConverterDefault::BinaryJoinTreeConverterDefault

(

)

default constructor

Definition at line 56 of file binaryJoinTreeConverterDefault.cpp.

                                                                 {
    GUM_CONSTRUCTOR(BinaryJoinTreeConverterDefault);
  }

References BinaryJoinTreeConverterDefault().

Referenced by BinaryJoinTreeConverterDefault(), BinaryJoinTreeConverterDefault(), ~BinaryJoinTreeConverterDefault(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

~BinaryJoinTreeConverterDefault()

gum::BinaryJoinTreeConverterDefault::~BinaryJoinTreeConverterDefault ( )

virtual

destructor

Definition at line 61 of file binaryJoinTreeConverterDefault.cpp.

                                                                  {
    GUM_DESTRUCTOR(BinaryJoinTreeConverterDefault);
  }

References BinaryJoinTreeConverterDefault().

Here is the call graph for this function:

BinaryJoinTreeConverterDefault() [2/2]

gum::BinaryJoinTreeConverterDefault::BinaryJoinTreeConverterDefault ( const BinaryJoinTreeConverterDefault & )

private

forbid copy constructor

References BinaryJoinTreeConverterDefault().

Here is the call graph for this function:

Member Function Documentation

_combinedSize_()

float gum::BinaryJoinTreeConverterDefault::_combinedSize_ ( const NodeSet & nodes1, const NodeSet & nodes2, const NodeProperty< Size > & domain_sizes ) const

private

returns the domain size of the union of two cliques

Definition at line 101 of file binaryJoinTreeConverterDefault.cpp.

                                                      {
    float result = 1;
 
    for (const auto node: nodes1)
      result *= domain_sizes[node];
 
    for (const auto node: nodes2)
      if (!nodes1.exists(node)) result *= domain_sizes[node];
 
    return result;
  }

References gum::Set< Key >::exists().

Referenced by _convertClique_().

Here is the call graph for this function:

Here is the caller graph for this function:

_convertClique_()

void gum::BinaryJoinTreeConverterDefault::_convertClique_ ( CliqueGraph & JT, NodeId clique, NodeId from, const NodeProperty< Size > & domain_sizes ) const

private

convert a clique and its adjacent cliques into a binary join tree

Definition at line 120 of file binaryJoinTreeConverterDefault.cpp.

                                                      {
    // get the neighbors of clique. If there are fewer than 3 neighbors,
    // there is nothing to do
    const NodeSet& neighbors = JT.neighbours(clique);
 
    if (neighbors.size() <= 2) return;
 
    if ((neighbors.size() == 3) && (clique != from)) return;
 
    // here we need to transform the neighbors into a binary tree
    // create a vector with all the ids of the cliques to combine
    std::vector< NodeId > cliques;
    cliques.reserve(neighbors.size());
 
    for (const auto nei: neighbors)
      if (nei != from) cliques.push_back(nei);
 
    // create a vector indicating wether the elements in cliques contain
    // relevant information or not (during the execution of the for
    // loop below, a cell of vector cliques may actually contain only
    // trash data)
    std::vector< bool > is_cliques_relevant(cliques.size(), true);
 
    // for each pair of cliques (i,j), compute the size of the clique that would
    // result from the combination of clique i with clique j and store the
    // result
    // into a priorityQueue
    std::pair< NodeId, NodeId > pair;
 
    PriorityQueue< std::pair< NodeId, NodeId >, float > queue;
 
    for (NodeId i = 0; i < cliques.size(); ++i) {
      pair.first            = i;
      const NodeSet& nodes1 = JT.separator(cliques[i], clique);
 
      for (NodeId j = i + 1; j < cliques.size(); ++j) {
        pair.second = j;
        queue.insert(pair, _combinedSize_(nodes1, JT.separator(cliques[j], clique), domain_sizes));
      }
    }
 
    // now parse the priority queue: the top element (i,j) gives the combination
    // to perform. When the result R has been computed, substitute i by R,
    // remove
    // table j and recompute all the priorities of all the pairs (R,k) still
    // available.
    for (NodeId k = 2; k < cliques.size(); ++k) {
      // get the combination to perform and do it
      pair      = queue.pop();
      NodeId ti = pair.first;
      NodeId tj = pair.second;
 
      // create a new clique that will become adjacent to ti and tj
      // and remove the edges between ti, tj and clique
      const NodeSet& nodes1   = JT.separator(cliques[ti], clique);
      const NodeSet& nodes2   = JT.separator(cliques[tj], clique);
      NodeId         new_node = JT.addNode(nodes1 + nodes2);
      JT.addEdge(cliques[ti], new_node);
      JT.addEdge(cliques[tj], new_node);
      JT.addEdge(clique, new_node);
      JT.eraseEdge(Edge(cliques[ti], clique));
      JT.eraseEdge(Edge(cliques[tj], clique));
 
      // substitute cliques[pair.first] by the result
      cliques[ti]             = new_node;
      is_cliques_relevant[tj] = false;   // now tj is no more a neighbor of clique
 
      // remove all the pairs involving tj in the priority queue
 
      for (NodeId ind = 0; ind < tj; ++ind) {
        if (is_cliques_relevant[ind]) {
          pair.first = ind;
          queue.erase(pair);
        }
      }
 
      pair.first = tj;
 
      for (NodeId ind = tj + 1; ind < cliques.size(); ++ind) {
        if (is_cliques_relevant[ind]) {
          pair.second = ind;
          queue.erase(pair);
        }
      }
 
      // update the "combined" size of all the pairs involving "new_node"
      {
        const NodeSet& nodes1 = JT.separator(cliques[ti], clique);
        pair.second           = ti;
        float newsize;
 
        for (NodeId ind = 0; ind < ti; ++ind) {
          if (is_cliques_relevant[ind]) {
            pair.first = ind;
            newsize    = _combinedSize_(nodes1, JT.separator(cliques[ind], clique), domain_sizes);
            queue.setPriority(pair, newsize);
          }
        }
 
        pair.first = ti;
 
        for (NodeId ind = ti + 1; ind < cliques.size(); ++ind) {
          if (is_cliques_relevant[ind]) {
            pair.second = ind;
            newsize     = _combinedSize_(nodes1, JT.separator(cliques[ind], clique), domain_sizes);
            queue.setPriority(pair, newsize);
          }
        }
      }
    }
  }

References _combinedSize_(), gum::CliqueGraph::addEdge(), gum::CliqueGraph::addNode(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::erase(), gum::CliqueGraph::eraseEdge(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::insert(), gum::EdgeGraphPart::neighbours(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::pop(), gum::CliqueGraph::separator(), gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::setPriority(), and gum::Set< Key >::size().

Referenced by _convertConnectedComponent_().

Here is the call graph for this function:

Here is the caller graph for this function:

_convertConnectedComponent_()

void gum::BinaryJoinTreeConverterDefault::_convertConnectedComponent_ ( CliqueGraph & JT, NodeId current_node, NodeId from, const NodeProperty< Size > & domain_sizes, NodeProperty< bool > & mark ) const

private

convert a whole connected component into a binary join tree

Definition at line 237 of file binaryJoinTreeConverterDefault.cpp.

                                              {
    // first, indicate that the node has been marked (this avoids looping
    // if JT is not a tree
    mark[current_node] = true;
 
    // parse all the neighbors except nodes already converted and convert them
    for (const auto neigh: JT.neighbours(current_node)) {
      if (!mark[neigh]) {
        _convertConnectedComponent_(JT, neigh, current_node, domain_sizes, mark);
      }
    }
 
    // convert the current node
    _convertClique_(JT, current_node, from, domain_sizes);
  }

References _convertClique_(), _convertConnectedComponent_(), and gum::EdgeGraphPart::neighbours().

Referenced by _convertConnectedComponent_(), and convert().

Here is the call graph for this function:

Here is the caller graph for this function:

_markConnectedComponent_()

void gum::BinaryJoinTreeConverterDefault::_markConnectedComponent_ ( const CliqueGraph & JT, NodeId root, NodeProperty< bool > & mark ) const

private

a function used to mark the nodes belonging to a given connected component

Definition at line 67 of file binaryJoinTreeConverterDefault.cpp.

                                                                                                  {
    // we mark the nodes in a depth first search manner. To avoid a recursive
    // algorithm, use a vector to simulate a stack of nodes to inspect.
    // stack => depth first search
    std::vector< NodeId > nodes_to_inspect;
    nodes_to_inspect.reserve(JT.sizeNodes());
 
    // the idea to populate the marks is to use the stack: root is
    // put onto the stack. Then, while the stack is not empty, remove
    // the top of the stack and mark it and put into the stack its
    // adjacent nodes.
    nodes_to_inspect.push_back(root);
 
    while (!nodes_to_inspect.empty()) {
      // process the top of the stack
      NodeId current_node = nodes_to_inspect.back();
      nodes_to_inspect.pop_back();
 
      // only process the node if it has not been processed yet (actually,
      // this should not occur unless the clique graph is not singly connected)
 
      if (!mark[current_node]) {
        mark[current_node] = true;
 
        // put the neighbors onto the stack
        for (const auto neigh: JT.neighbours(current_node))
          if (!mark[neigh]) nodes_to_inspect.push_back(neigh);
      }
    }
  }

References gum::EdgeGraphPart::neighbours(), and gum::NodeGraphPart::sizeNodes().

Referenced by convert().

Here is the call graph for this function:

Here is the caller graph for this function:

convert()

CliqueGraph gum::BinaryJoinTreeConverterDefault::convert	(	const CliqueGraph &	JT,
		const NodeProperty< Size > &	domain_sizes,
		const NodeSet &	roots )

returns a binary join tree corresponding to clique graph JT

computes the binary join tree

This method creates and returns a new binary join tree compatible with that passed in argument (JT) and optimized for inference. As such, this requires knowing the join tree to be converted (of course), but also which roots will be used by the collect/diffusion inference engine and the domain size of the variables contained in the cliques of JT (to optimize the combination of the tensors contained in the cliques.

Exceptions

InvalidNode

exception is thrown if some roots do not belong to JT or if several roots belong to the same connected component.

Warning

If you do not pass in argument a root for each connected component, then for those with unspecified roots, an arbitrary root will be computed and used for the binarization.

Definition at line 259 of file binaryJoinTreeConverterDefault.cpp.

                                                                                                   {
    // first, we copy the current clique graph. By default, this is what we
    // will return
    CliqueGraph binJT = JT;
 
    // check that there is no connected component without a root. In such a
    // case,
    // assign an arbitrary root to it
    _roots_ = specified_roots;
 
    NodeProperty< bool > mark = JT.nodesPropertyFromVal(false, JT.sizeNodes());
 
    // for each specified root, populate its connected component
    for (const auto root: specified_roots) {
      // check that the root has not already been marked
      // in this case, this means that more than one root has been specified
      // for a given connected component
      if (mark[root])
        GUM_ERROR(InvalidNode,
                  "several roots have been specified for a given "
                  "connected component (last : "
                      << root << ")");
 
      _markConnectedComponent_(JT, root, mark);
    }
 
    // check that all nodes have been marked. If this is not the case, then
    // this means that we need to add new roots
    for (const auto& elt: mark)
      if (!elt.second) {
        _roots_ << elt.first;
        _markConnectedComponent_(JT, elt.first, mark);
      }
 
    // here, we know that each connected component has one and only one root.
    // Now we can apply a recursive collect algorithm starting from root
    // that transforms each clique with more than 3 neighbors into a set of
    // cliques having at most 3 neighbors.
    NodeProperty< bool > mark2 = JT.nodesPropertyFromVal(false, JT.sizeNodes());
 
    for (const auto root: _roots_)
      _convertConnectedComponent_(binJT, root, root, domain_sizes, mark2);
 
    // binJT is now a binary join tree, so we can return it
    return binJT;
  }

References _convertConnectedComponent_(), _markConnectedComponent_(), _roots_, GUM_ERROR, gum::NodeGraphPart::nodesPropertyFromVal(), and gum::NodeGraphPart::sizeNodes().

Here is the call graph for this function:

operator=()

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

private

forbid copy operator

References BinaryJoinTreeConverterDefault().

Here is the call graph for this function:

roots()

const NodeSet & gum::BinaryJoinTreeConverterDefault::roots

(

)

const

returns all the roots considered for all the connected components

Definition at line 117 of file binaryJoinTreeConverterDefault.cpp.

{ return _roots_; }

References _roots_.

Member Data Documentation

_roots_

NodeSet gum::BinaryJoinTreeConverterDefault::_roots_

private

the new roots that have been created to compute the last query

Definition at line 98 of file binaryJoinTreeConverterDefault.h.

Referenced by convert(), and roots().

---

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

• agrum/base/graphs/algorithms/binaryJoinTreeConverterDefault.h
• agrum/base/graphs/algorithms/binaryJoinTreeConverterDefault.cpp