#include <binaryJoinTreeConverterDefault.h>

Collaboration diagram for gum::BinaryJoinTreeConverterDefault:

Public Member Functions
Constructors / Destructors
	BinaryJoinTreeConverterDefault ()
	default constructor More...

virtual	~BinaryJoinTreeConverterDefault ()
	destructor More...

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

const NodeSet &	roots () const
	returns all the roots considered for all the connected components More...

Detailed Description

Definition at line 34 of file binaryJoinTreeConverterDefault.h.

Constructor & Destructor Documentation

◆ BinaryJoinTreeConverterDefault() [1/2]

gum::BinaryJoinTreeConverterDefault::BinaryJoinTreeConverterDefault ( )

default constructor

Definition at line 36 of file binaryJoinTreeConverterDefault.cpp.

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

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

Here is the call graph for this function:

◆ ~BinaryJoinTreeConverterDefault()

gum::BinaryJoinTreeConverterDefault::~BinaryJoinTreeConverterDefault ( )

virtual

destructor

Definition at line 42 of file binaryJoinTreeConverterDefault.cpp.

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

                                                                   {
     GUM_DESTRUCTOR(BinaryJoinTreeConverterDefault);
   }

Here is the call graph for this function:

◆ BinaryJoinTreeConverterDefault() [2/2]

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

private

forbid copy constructor

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 83 of file binaryJoinTreeConverterDefault.cpp.

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

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

Here is the call 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 potentials 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 247 of file binaryJoinTreeConverterDefault.cpp.

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

                                                   {
     // 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.nodesProperty(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.nodesProperty(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;
   }

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

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

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

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

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

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

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

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

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