aGrUM  0.13.2
gum::BinaryJoinTreeConverterDefault Class Reference

#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 NodeSetroots () const
 returns all the roots considered for all the connected components More...
 

Detailed Description

Definition at line 32 of file binaryJoinTreeConverterDefault.h.

Constructor & Destructor Documentation

gum::BinaryJoinTreeConverterDefault::BinaryJoinTreeConverterDefault ( )

default constructor

Definition at line 34 of file binaryJoinTreeConverterDefault.cpp.

34  {
35  // for debugging purposes
36  GUM_CONSTRUCTOR(BinaryJoinTreeConverterDefault);
37  }
gum::BinaryJoinTreeConverterDefault::~BinaryJoinTreeConverterDefault ( )
virtual

destructor

Definition at line 40 of file binaryJoinTreeConverterDefault.cpp.

40  {
41  GUM_DESTRUCTOR(BinaryJoinTreeConverterDefault);
42  }
gum::BinaryJoinTreeConverterDefault::BinaryJoinTreeConverterDefault ( const BinaryJoinTreeConverterDefault )
private

forbid copy constructor

Member Function Documentation

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

Referenced by __convertClique().

82  {
83  float result = 1;
84 
85  for (const auto node : nodes1)
86  result *= domain_sizes[node];
87 
88  for (const auto node : nodes2)
89  if (!nodes1.exists(node)) result *= domain_sizes[node];
90 
91  return result;
92  }

+ Here is the caller graph for this function:

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

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

Referenced by __convertConnectedComponent().

102  {
103  // get the neighbors of clique. If there are fewer than 3 neighbors,
104  // there is nothing to do
105  const NodeSet& neighbors = JT.neighbours(clique);
106 
107  if (neighbors.size() <= 2) return;
108 
109  if ((neighbors.size() == 3) && (clique != from)) return;
110 
111  // here we need to transform the neighbors into a binary tree
112  // create a vector with all the ids of the cliques to combine
113  std::vector< NodeId > cliques;
114  cliques.reserve(neighbors.size());
115 
116  for (const auto nei : neighbors)
117  if (nei != from) cliques.push_back(nei);
118 
119  // create a vector indicating wether the elements in cliques contain
120  // relevant information or not (during the execution of the for
121  // loop below, a cell of vector cliques may actually contain only
122  // trash data)
123  std::vector< bool > is_cliques_relevant(cliques.size(), true);
124 
125  // for each pair of cliques (i,j), compute the size of the clique that would
126  // result from the combination of clique i with clique j and store the
127  // result
128  // into a priorityQueue
129  std::pair< NodeId, NodeId > pair;
130 
131  PriorityQueue< std::pair< NodeId, NodeId >, float > queue;
132 
133  for (NodeId i = 0; i < cliques.size(); ++i) {
134  pair.first = i;
135  const NodeSet& nodes1 = JT.separator(cliques[i], clique);
136 
137  for (NodeId j = i + 1; j < cliques.size(); ++j) {
138  pair.second = j;
139  queue.insert(
140  pair,
141  __combinedSize(nodes1, JT.separator(cliques[j], clique), domain_sizes));
142  }
143  }
144 
145  // now parse the priority queue: the top element (i,j) gives the combination
146  // to perform. When the result R has been computed, substitute i by R,
147  // remove
148  // table j and recompute all the priorities of all the pairs (R,k) still
149  // available.
150  for (NodeId k = 2; k < cliques.size(); ++k) {
151  // get the combination to perform and do it
152  pair = queue.pop();
153  NodeId ti = pair.first;
154  NodeId tj = pair.second;
155 
156  // create a new clique that will become adjacent to ti and tj
157  // and remove the edges between ti, tj and clique
158  const NodeSet& nodes1 = JT.separator(cliques[ti], clique);
159  const NodeSet& nodes2 = JT.separator(cliques[tj], clique);
160  NodeId new_node = JT.addNode(nodes1 + nodes2);
161  JT.addEdge(cliques[ti], new_node);
162  JT.addEdge(cliques[tj], new_node);
163  JT.addEdge(clique, new_node);
164  JT.eraseEdge(Edge(cliques[ti], clique));
165  JT.eraseEdge(Edge(cliques[tj], clique));
166 
167  // substitute cliques[pair.first] by the result
168  cliques[ti] = new_node;
169  is_cliques_relevant[tj] = false; // now tj is no more a neighbor of clique
170 
171  // remove all the pairs involving tj in the priority queue
172 
173  for (NodeId ind = 0; ind < tj; ++ind) {
174  if (is_cliques_relevant[ind]) {
175  pair.first = ind;
176  queue.erase(pair);
177  }
178  }
179 
180  pair.first = tj;
181 
182  for (NodeId ind = tj + 1; ind < cliques.size(); ++ind) {
183  if (is_cliques_relevant[ind]) {
184  pair.second = ind;
185  queue.erase(pair);
186  }
187  }
188 
189  // update the "combined" size of all the pairs involving "new_node"
190  {
191  const NodeSet& nodes1 = JT.separator(cliques[ti], clique);
192  pair.second = ti;
193  float newsize;
194 
195  for (NodeId ind = 0; ind < ti; ++ind) {
196  if (is_cliques_relevant[ind]) {
197  pair.first = ind;
198  newsize = __combinedSize(
199  nodes1, JT.separator(cliques[ind], clique), domain_sizes);
200  queue.setPriority(pair, newsize);
201  }
202  }
203 
204  pair.first = ti;
205 
206  for (NodeId ind = ti + 1; ind < cliques.size(); ++ind) {
207  if (is_cliques_relevant[ind]) {
208  pair.second = ind;
209  newsize = __combinedSize(
210  nodes1, JT.separator(cliques[ind], clique), domain_sizes);
211  queue.setPriority(pair, newsize);
212  }
213  }
214  }
215  }
216  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
float __combinedSize(const NodeSet &nodes1, const NodeSet &nodes2, const NodeProperty< Size > &domain_sizes) const
returns the domain size of the union of two cliques

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

References __convertClique(), and gum::EdgeGraphPart::neighbours().

Referenced by convert().

224  {
225  // first, indicate that the node has been marked (this avoids looping
226  // if JT is not a tree
227  mark[current_node] = true;
228 
229  // parse all the neighbors except nodes already converted and convert them
230  for (const auto neigh : JT.neighbours(current_node)) {
231  if (!mark[neigh]) {
232  __convertConnectedComponent(JT, neigh, current_node, domain_sizes, mark);
233  }
234  }
235 
236  // convert the current node
237  __convertClique(JT, current_node, from, domain_sizes);
238  }
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

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

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

Referenced by convert().

47  {
48  // we mark the nodes in a depth first search manner. To avoid a recursive
49  // algorithm, use a vector to simulate a stack of nodes to inspect.
50  // stack => depth first search
51  std::vector< NodeId > nodes_to_inspect;
52  nodes_to_inspect.reserve(JT.sizeNodes());
53 
54  // the idea to populate the marks is to use the stack: root is
55  // put onto the stack. Then, while the stack is not empty, remove
56  // the top of the stack and mark it and put into the stack its
57  // adjacent nodes.
58  nodes_to_inspect.push_back(root);
59 
60  while (!nodes_to_inspect.empty()) {
61  // process the top of the stack
62  NodeId current_node = nodes_to_inspect.back();
63  nodes_to_inspect.pop_back();
64 
65  // only process the node if it has not been processed yet (actually,
66  // this should not occur unless the clique graph is not singly connected)
67 
68  if (!mark[current_node]) {
69  mark[current_node] = true;
70 
71  // put the neighbors onto the stack
72  for (const auto neigh : JT.neighbours(current_node))
73  if (!mark[neigh]) nodes_to_inspect.push_back(neigh);
74  }
75  }
76  }
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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

References __convertConnectedComponent(), __markConnectedComponent(), __roots, GUM_ERROR, gum::NodeGraphPart::nodesProperty(), and gum::NodeGraphPart::sizeNodes().

244  {
245  // first, we copy the current clique graph. By default, this is what we
246  // will return
247  CliqueGraph binJT = JT;
248 
249  // check that there is no connected component without a root. In such a
250  // case,
251  // assign an arbitrary root to it
252  __roots = specified_roots;
253 
254  NodeProperty< bool > mark = JT.nodesProperty(false, JT.sizeNodes());
255 
256  // for each specified root, populate its connected component
257  for (const auto root : specified_roots) {
258  // check that the root has not already been marked
259  // in this case, this means that more than one root has been specified
260  // for a given connected component
261  if (mark[root])
262  GUM_ERROR(InvalidNode,
263  "several roots have been specified for a given "
264  "connected component");
265 
266  __markConnectedComponent(JT, root, mark);
267  }
268 
269  // check that all nodes have been marked. If this is not the case, then
270  // this means that we need to add new roots
271  for (const auto& elt : mark)
272  if (!elt.second) {
273  __roots << elt.first;
274  __markConnectedComponent(JT, elt.first, mark);
275  }
276 
277  // here, we know that each connected component has one and only one root.
278  // Now we can apply a recursive collect algorithm starting from root
279  // that transforms each clique with more than 3 neighbors into a set of
280  // cliques having at most 3 neighbors.
281  NodeProperty< bool > mark2 = JT.nodesProperty(false, JT.sizeNodes());
282 
283  for (const auto root : __roots)
284  __convertConnectedComponent(binJT, root, root, domain_sizes, mark2);
285 
286  // binJT is now a binary join tree, so we can return it
287  return binJT;
288  }
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 __markConnectedComponent(const CliqueGraph &JT, NodeId root, NodeProperty< bool > &mark) const
a function used to mark the nodes belonging to a given connected component
NodeSet __roots
the new roots that have been created to compute the last query
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66

+ Here is the call graph for this function:

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

forbid copy operator

const NodeSet & gum::BinaryJoinTreeConverterDefault::roots ( ) const

returns all the roots considered for all the connected components

Definition at line 95 of file binaryJoinTreeConverterDefault.cpp.

References __roots.

95 { return __roots; }
NodeSet __roots
the new roots that have been created to compute the last query

Member Data Documentation

NodeSet gum::BinaryJoinTreeConverterDefault::__roots
private

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

Definition at line 76 of file binaryJoinTreeConverterDefault.h.

Referenced by convert(), and roots().


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