aGrUM  0.20.2
a C++ library for (probabilistic) graphical models
structuredInference_tpl.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4  * info_at_agrum_dot_org
5  *
6  * This library is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Inline implementation of StructuredInference.
25  *
26  * @author Lionel TORTI and Pierre-Henri WUILLEMIN(@LIP6)
27  */
28 
29 #include <agrum/PRM/inference/structuredInference.h>
30 
31 namespace gum {
32  namespace prm {
33 
34  template < typename GUM_SCALAR >
35  StructuredInference< GUM_SCALAR >::StructuredInference(
36  const PRM< GUM_SCALAR >& prm,
37  const PRMSystem< GUM_SCALAR >& system,
38  gspan::SearchStrategy< GUM_SCALAR >* strategy) :
39  PRMInference< GUM_SCALAR >(prm, system),
40  gspan__(0), pdata__(0), mining__(false), dot__(".") {
41  GUM_CONSTRUCTOR(StructuredInference);
42  gspan__ = new GSpan< GUM_SCALAR >(prm, system, strategy);
43  triang_time = 0.0;
44  mining_time = 0.0;
45  pattern_time = 0.0;
46  inner_time = 0.0;
47  obs_time = 0.0;
48  full_time = 0.0;
49  }
50 
51  template < typename GUM_SCALAR >
52  StructuredInference< GUM_SCALAR >::StructuredInference(
53  const StructuredInference< GUM_SCALAR >& source) :
54  PRMInference< GUM_SCALAR >(source),
55  gspan__(0), pdata__(0), mining__(source.mining__), found_query__(false),
56  dot__(".") {
57  GUM_CONS_CPY(StructuredInference);
58  gspan__ = new GSpan< GUM_SCALAR >(*(this->prm_), *(this->sys_));
59  }
60 
61  template < typename GUM_SCALAR >
62  StructuredInference< GUM_SCALAR >::~StructuredInference() {
63  GUM_DESTRUCTOR(StructuredInference);
64  delete this->gspan__;
65 
66  for (const auto& elt: elim_map__)
67  delete elt.second;
68 
69  for (const auto& elt: cdata_map__)
70  delete elt.second;
71 
72  for (const auto elt: trash__)
73  delete (elt);
74 
75  for (const auto& elt: outputs__)
76  delete elt.second;
77 
78  if (pdata__) delete pdata__;
79  }
80 
81  template < typename GUM_SCALAR >
82  StructuredInference< GUM_SCALAR >&
83  StructuredInference< GUM_SCALAR >::operator=(
84  const StructuredInference< GUM_SCALAR >& source) {
85  this->prm_ = source.prm_;
86  this->sys_ = source.sys_;
87 
88  if (this->gspan__) delete this->gspan__;
89 
90  this->gspan__ = new GSpan< GUM_SCALAR >(*(this->prm_), *(this->sys_));
91  return *this;
92  }
93 
94  template < typename GUM_SCALAR >
95  void StructuredInference< GUM_SCALAR >::evidenceAdded_(
96  const typename PRMInference< GUM_SCALAR >::Chain& chain) {}
97 
98  template < typename GUM_SCALAR >
99  void StructuredInference< GUM_SCALAR >::evidenceRemoved_(
100  const typename PRMInference< GUM_SCALAR >::Chain& chain) {}
101 
102  template < typename GUM_SCALAR >
103  void StructuredInference< GUM_SCALAR >::posterior_(
104  const typename PRMInference< GUM_SCALAR >::Chain& chain,
105  Potential< GUM_SCALAR >& m) {
106  timer.reset();
107  found_query__ = false;
108  query__ = chain;
109  typename StructuredInference< GUM_SCALAR >::RGData data;
110 
111  if (!this->hasEvidence() && (chain.second->cpf().nbrDim() == 1)) {
112  Instantiation i(m);
113 
114  for (i.setFirst(); !i.end(); i.inc())
115  m.set(i, chain.second->cpf().get(i));
116 
117  return;
118  } else if (this->hasEvidence(chain)) {
119  Instantiation i(m);
120  const Potential< GUM_SCALAR >* e
121  = this->evidence(query__.first)[query__.second->id()];
122 
123  for (i.setFirst(); !i.end(); i.inc())
124  m.set(i, e->get(i));
125 
126  return;
127  }
128 
129  buildReduceGraph__(data);
130  Set< const Potential< GUM_SCALAR >* > pots;
131 
132  if (data.pool.size() > 1) {
133  for (const auto pot: data.pool)
134  if (pot->contains(query__.second->type().variable())) pots.insert(pot);
135 
136  if (pots.size() == 1) {
137  Potential< GUM_SCALAR >* pot
138  = const_cast< Potential< GUM_SCALAR >* >(*(pots.begin()));
139  GUM_ASSERT(pot->contains(query__.second->type().variable()));
140  GUM_ASSERT(pot->variablesSequence().size() == 1);
141  Instantiation i(*pot), j(m);
142 
143  for (i.setFirst(), j.setFirst(); !i.end(); i.inc(), j.inc())
144  m.set(j, pot->get(i));
145  } else {
146  MultiDimCombinationDefault< GUM_SCALAR, Potential > Comb(multPotential);
147  Potential< GUM_SCALAR >* tmp = Comb.combine(pots);
148  Instantiation i(m), j(*tmp);
149 
150  for (i.setFirst(), j.setFirst(); !i.end(); i.inc(), j.inc())
151  m.set(i, tmp->get(j));
152 
153  delete tmp;
154  }
155  } else {
156  Potential< GUM_SCALAR >* pot = *(data.pool.begin());
157  GUM_ASSERT(pot->contains(query__.second->type().variable()));
158  GUM_ASSERT(pot->variablesSequence().size() == 1);
159  Instantiation i(*pot), j(m);
160 
161  for (i.setFirst(), j.setFirst(); !i.end(); i.inc(), j.inc())
162  m.set(j, pot->get(i));
163  }
164 
165  m.normalize();
166 
167  if (pdata__) {
168  delete pdata__;
169  pdata__ = 0;
170  }
171 
172  full_time = timer.step();
173  }
174 
175  template < typename GUM_SCALAR >
176  void StructuredInference< GUM_SCALAR >::joint_(
177  const std::vector< typename PRMInference< GUM_SCALAR >::Chain >& queries,
178  Potential< GUM_SCALAR >& j) {
179  GUM_ERROR(FatalError, "not implemented");
180  }
181 
182  template < typename GUM_SCALAR >
183  std::string StructuredInference< GUM_SCALAR >::info() const {
184  std::stringstream s;
185  s << "Triangulation time: " << triang_time << std::endl;
186  s << "Pattern mining time: " << mining_time << std::endl;
187  s << "Pattern elimination time: " << pattern_time << std::endl;
188  s << "Inner node elimination time: " << inner_time << std::endl;
189  s << "Observed node elimination time: " << obs_time << std::endl;
190  s << "Full inference time: " << full_time << std::endl;
191  s << "#patterns: " << gspan__->patterns().size() << std::endl;
192  Size count = 0;
193  typedef std::vector< gspan::Pattern* >::const_iterator Iter;
194 
195  for (Iter p = gspan__->patterns().begin(); p != gspan__->patterns().end();
196  ++p) {
197  if (gspan__->matches(**p).size()) {
198  s << "Pattern n°" << count++
199  << " match count: " << gspan__->matches(**p).size() << std::endl;
200  s << "Pattern n°" << count++ << " instance count: " << (**p).size()
201  << std::endl;
202  }
203  }
204 
205  return s.str();
206  }
207 
208  template < typename GUM_SCALAR >
209  void StructuredInference< GUM_SCALAR >::buildReduceGraph__(
210  typename StructuredInference< GUM_SCALAR >::RGData& data) {
211  // Launch the pattern mining
212  plopTimer.reset();
213 
214  if (mining__) gspan__->discoverPatterns();
215 
216  mining_time = plopTimer.step();
217  // Reducing each used pattern
218  plopTimer.reset();
219  typedef std::vector< gspan::Pattern* >::const_iterator Iter;
220 
221  for (Iter p = gspan__->patterns().begin(); p != gspan__->patterns().end();
222  ++p)
223  if (gspan__->matches(**p).size()) reducePattern__(*p);
224 
225  pattern_time = plopTimer.step();
226  // reducing instance not already reduced in a pattern
227  reduceAloneInstances__(data);
228  // Adding edges using the pools
229  addEdgesInReducedGraph__(data);
230  // Placing the query where it belongs
231  NodeId id = data.var2node.second(&(query__.second->type().variable()));
232  data.outputs().erase(id);
233  data.queries().insert(id);
234  // Triangulating, then eliminating
235  PartialOrderedTriangulation t(&(data.reducedGraph),
236  &(data.mods),
237  &(data.partial_order));
238  const std::vector< NodeId >& elim_order = t.eliminationOrder();
239 
240  for (size_t i = 0; i < data.outputs().size(); ++i)
241  eliminateNode(data.var2node.first(elim_order[i]), data.pool, trash__);
242  }
243 
244  template < typename GUM_SCALAR >
245  void StructuredInference< GUM_SCALAR >::reducePattern__(
246  const gspan::Pattern* p) {
247  Set< Potential< GUM_SCALAR >* > pool;
248  typename StructuredInference< GUM_SCALAR >::PData data(*p,
249  gspan__->matches(*p));
250  buildPatternGraph__(data, pool, **(data.matches.begin()));
251  removeBarrenNodes__(data, pool);
252  PartialOrderedTriangulation t(&(data.graph),
253  &(data.mod),
254  data.partial_order());
255  const std::vector< NodeId >& elim_order = t.eliminationOrder();
256 
257  for (size_t i = 0; i < data.inners().size(); ++i)
258  if (!data.barren.exists(elim_order[i]))
259  eliminateNode(data.vars.second(elim_order[i]), pool, trash__);
260 
261  typename GSpan< GUM_SCALAR >::MatchedInstances fake_patterns;
262  typename GSpan< GUM_SCALAR >::MatchedInstances::const_iterator iter
263  = data.matches.begin();
264 
265  for (const auto elt: **iter)
266  reducedInstances__.insert(elt);
267 
268  if (data.obs().size())
269  elim_map__.insert(
270  *iter,
271  eliminateObservedNodesInSource__(data, pool, **iter, elim_order));
272  else
273  elim_map__.insert(*iter, new Set< Potential< GUM_SCALAR >* >(pool));
274 
275  ++iter;
276 
277  if (data.obs().size()) {
278  for (; iter != data.matches.end(); ++iter) {
279  try {
280  elim_map__.insert(
281  *iter,
282  eliminateObservedNodes__(data, pool, **iter, elim_order));
283  } catch (OperationNotAllowed&) { fake_patterns.insert(*iter); }
284  }
285  } else {
286  for (; iter != data.matches.end(); ++iter) {
287  try {
288  elim_map__.insert(*iter, translatePotSet__(data, pool, **iter));
289  } catch (OperationNotAllowed&) { fake_patterns.insert(*iter); }
290  }
291  }
292 
293  for (const auto pat: fake_patterns) {
294  for (const auto elt: *pat)
295  reducedInstances__.erase(elt);
296 
297  data.matches.erase(pat);
298  }
299 
300  obs_time += plopTimer.step();
301 
302  if (data.queries().size())
303  for (const auto m: data.matches)
304  if (!(m->exists(
305  const_cast< PRMInstance< GUM_SCALAR >* >(query__.first))))
306  eliminateNode(&(m->atPos(query_data__.first)
307  ->get(query_data__.second)
308  .type()
309  .variable()),
310  *(elim_map__[m]),
311  trash__);
312  }
313 
314  template < typename GUM_SCALAR >
315  void StructuredInference< GUM_SCALAR >::insertNodeInElimLists__(
316  typename StructuredInference< GUM_SCALAR >::PData& data,
317  const Sequence< PRMInstance< GUM_SCALAR >* >& match,
318  PRMInstance< GUM_SCALAR >* inst,
319  PRMAttribute< GUM_SCALAR >* attr,
320  NodeId id,
321  std::pair< Idx, std::string >& v) {
322  if ((*inst).hasRefAttr((*inst).get(v.second).id())) {
323  std::vector< std::pair< PRMInstance< GUM_SCALAR >*, std::string > >& refs
324  = inst->getRefAttr(inst->get(v.second).id());
325 
326  for (auto r = refs.begin(); r != refs.end(); ++r) {
327  if (!match.exists(r->first)) {
328  data.outputs().insert(id);
329  break;
330  }
331  }
332  }
333 
334  if (!(data.outputs().size() && (data.outputs().exists(id)))) {
335  for (const auto m: data.matches) {
336  if (this->hasEvidence(
337  std::make_pair((*m)[v.first], &((*m)[v.first]->get(v.second))))) {
338  GUM_ASSERT(inst->type().name() == (*m)[v.first]->type().name());
339  GUM_ASSERT(inst->get(v.second).safeName()
340  == (*m)[v.first]->get(v.second).safeName());
341  data.obs().insert(id);
342  break;
343  }
344  }
345 
346  if (!(data.obs().size() && (data.obs().exists(id))))
347  data.inners().insert(id);
348  }
349  }
350 
351  template < typename GUM_SCALAR >
352  void StructuredInference< GUM_SCALAR >::buildPatternGraph__(
353  typename StructuredInference< GUM_SCALAR >::PData& data,
354  Set< Potential< GUM_SCALAR >* >& pool,
355  const Sequence< PRMInstance< GUM_SCALAR >* >& match) {
356  std::pair< Idx, std::string > v;
357  Potential< GUM_SCALAR >* pot = 0;
358 
359  for (const auto inst: match) {
360  for (const auto& elt: *inst) {
361  NodeId id = data.graph.addNode();
362  v = std::make_pair(match.pos(inst), elt.second->safeName());
363  data.map.insert(id, v);
364  data.node2attr.insert(id, str__(inst, elt.second));
365  data.mod.insert(id, elt.second->type()->domainSize());
366  data.vars.insert(id, &(elt.second->type().variable()));
367  pool.insert(
368  const_cast< Potential< GUM_SCALAR >* >(&(elt.second->cpf())));
369  pot = &(
370  const_cast< Potential< GUM_SCALAR >& >(inst->get(v.second).cpf()));
371 
372  for (const auto var: pot->variablesSequence()) {
373  try {
374  if (id != data.vars.first(var))
375  data.graph.addEdge(id, data.vars.first(var));
376  } catch (DuplicateElement&) {
377  } catch (NotFound&) {}
378  }
379 
380  insertNodeInElimLists__(data, match, inst, elt.second, id, v);
381 
382  if (data.inners().exists(id)
383  && (inst->type().containerDag().children(elt.second->id()).size()
384  == 0)
385  && allInstanceNoRefAttr__(data, v))
386  data.barren.insert(id);
387  }
388  }
389 
390  if (!found_query__) {
391  for (const auto mat: data.matches) {
392  if (mat->exists(
393  const_cast< PRMInstance< GUM_SCALAR >* >(query__.first))) {
394  Idx pos
395  = mat->pos(const_cast< PRMInstance< GUM_SCALAR >* >(query__.first));
396  DiscreteVariable& var = match.atPos(pos)
397  ->get(query__.second->safeName())
398  .type()
399  .variable();
400  NodeId id = data.vars.first(&var);
401  data.barren.erase(id);
402  data.inners().erase(id);
403  data.obs().erase(id);
404  data.outputs().erase(id);
405  data.queries().insert(id);
406  found_query__ = true;
407  query_data__ = std::make_pair(pos, query__.second->safeName());
408  break;
409  }
410  }
411  }
412  }
413 
414  template < typename GUM_SCALAR >
415  bool StructuredInference< GUM_SCALAR >::allInstanceNoRefAttr__(
416  typename StructuredInference< GUM_SCALAR >::PData& data,
417  std::pair< Idx, std::string > attr) {
418  for (const auto mat: data.matches)
419  if (mat->atPos(attr.first)
420  ->hasRefAttr(mat->atPos(attr.first)->get(attr.second).id()))
421  return false;
422 
423  return true;
424  }
425 
426  template < typename GUM_SCALAR >
427  void StructuredInference< GUM_SCALAR >::removeBarrenNodes__(
428  typename StructuredInference< GUM_SCALAR >::PData& data,
429  Set< Potential< GUM_SCALAR >* >& pool) {
430  Sequence< NodeId > candidates;
431 
432  for (const auto node: data.barren) {
433  for (const auto pot: pool)
434  if (pot->contains(*data.vars.second(node))) {
435  pool.erase(pot);
436  break;
437  }
438 
439  for (const auto nei: data.graph.neighbours(node))
440  if (data.inners().exists(nei)) {
441  try {
442  candidates.insert(nei);
443  } catch (DuplicateElement&) {}
444  }
445  }
446 
447  NodeId node;
448  Potential< GUM_SCALAR >* my_pot = nullptr;
449  short count = 0;
450 
451  while (candidates.size()) {
452  node = candidates.back();
453  candidates.erase(node);
454  count = 0;
455 
456  for (const auto pot: pool) {
457  if (pot->contains(*data.vars.second(node))) {
458  ++count;
459  my_pot = pot;
460  }
461  }
462 
463  if (count == 1) {
464  pool.erase(my_pot);
465  data.barren.insert(node);
466 
467  for (const auto nei: data.graph.neighbours(node)) {
468  if (data.inners().exists(nei)) {
469  try {
470  candidates.insert(nei);
471  } catch (DuplicateElement&) {}
472  }
473  }
474  }
475  }
476  }
477 
478  template < typename GUM_SCALAR >
479  Set< Potential< GUM_SCALAR >* >*
480  StructuredInference< GUM_SCALAR >::eliminateObservedNodesInSource__(
481  typename StructuredInference< GUM_SCALAR >::PData& data,
482  const Set< Potential< GUM_SCALAR >* >& pool,
483  const Sequence< PRMInstance< GUM_SCALAR >* >& match,
484  const std::vector< NodeId >& elim_order) {
485  Set< Potential< GUM_SCALAR >* >* my_pool
486  = new Set< Potential< GUM_SCALAR >* >(pool);
487  std::pair< Idx, std::string > target;
488  size_t end = data.inners().size() + data.obs().size();
489 
490  for (size_t idx = data.inners().size(); idx < end; ++idx) {
491  target = data.map[data.vars.first(data.vars.second(elim_order[idx]))];
492  eliminateNode(&(match[target.first]->get(target.second).type().variable()),
493  *my_pool,
494  trash__);
495  }
496 
497  return my_pool;
498  }
499 
500  template < typename GUM_SCALAR >
501  Set< Potential< GUM_SCALAR >* >*
502  StructuredInference< GUM_SCALAR >::eliminateObservedNodes__(
503  typename StructuredInference< GUM_SCALAR >::PData& data,
504  const Set< Potential< GUM_SCALAR >* >& pool,
505  const Sequence< PRMInstance< GUM_SCALAR >* >& match,
506  const std::vector< NodeId >& elim_order) {
507  Set< Potential< GUM_SCALAR >* >* my_pool
508  = translatePotSet__(data, pool, match);
509  std::pair< Idx, std::string > target;
510  size_t end = data.inners().size() + data.obs().size();
511 
512  for (size_t idx = data.inners().size(); idx < end; ++idx) {
513  target = data.map[data.vars.first(data.vars.second(elim_order[idx]))];
514  eliminateNode(&(match[target.first]->get(target.second).type().variable()),
515  *my_pool,
516  trash__);
517  }
518 
519  return my_pool;
520  }
521 
522  template < typename GUM_SCALAR >
523  Set< Potential< GUM_SCALAR >* >*
524  StructuredInference< GUM_SCALAR >::translatePotSet__(
525  typename StructuredInference< GUM_SCALAR >::PData& data,
526  const Set< Potential< GUM_SCALAR >* >& pool,
527  const Sequence< PRMInstance< GUM_SCALAR >* >& match) {
528 #ifdef DEBUG
529 
530  for (GSpan< GUM_SCALAR >::MatchedInstances::const_iterator iter
531  = data.matches.begin();
532  iter != data.matches.end();
533  ++iter) {
534  GUM_ASSERT((**iter).size() == match.size());
535 
536  for (Size idx = 0; idx < match.size(); ++idx) {
537  GUM_ASSERT((**iter).atPos(idx)->type() == match.atPos(idx)->type());
538  }
539  }
540 
541 #endif
542  Set< Potential< GUM_SCALAR >* >* my_pool
543  = new Set< Potential< GUM_SCALAR >* >();
544  std::pair< Idx, std::string > target;
545  Bijection< const DiscreteVariable*, const DiscreteVariable* > bij;
546  const Sequence< PRMInstance< GUM_SCALAR >* >& source
547  = **(data.matches.begin());
548 
549  for (Size idx = 0; idx < match.size(); ++idx) {
550  reducedInstances__.insert(match[idx]);
551  const auto& chains = source[idx]->type().slotChains();
552 
553  for (const auto sc: chains) {
554 #ifdef DEBUG
555  GUM_ASSERT(!(sc->isMultiple()));
556 #endif
557 
558  try {
559  bij.insert(&(source[idx]
560  ->getInstance(sc->id())
561  .get(sc->lastElt().safeName())
562  .type()
563  .variable()),
564  &(match[idx]
565  ->getInstance(sc->id())
566  .get(sc->lastElt().safeName())
567  .type()
568  .variable()));
569  } catch (DuplicateElement&) {
570  try {
571  if (bij.first(&(match[idx]
572  ->getInstance(sc->id())
573  .get(sc->lastElt().safeName())
574  .type()
575  .variable()))
576  != &(source[idx]
577  ->getInstance(sc->id())
578  .get(sc->lastElt().safeName())
579  .type()
580  .variable())) {
581  delete my_pool;
582  GUM_ERROR(OperationNotAllowed, "fake pattern");
583  }
584  } catch (NotFound&) {
585  delete my_pool;
586  GUM_ERROR(OperationNotAllowed, "fake pattern");
587  }
588  }
589  }
590  }
591 
592  for (const auto p: pool) {
593  for (const auto v: p->variablesSequence()) {
594  try {
595  target = data.map[data.vars.first(v)];
596  bij.insert(
597  v,
598  &(match[target.first]->get(target.second).type().variable()));
599  } catch (NotFound&) {
600  GUM_ASSERT(bij.existsFirst(v));
601  } catch (DuplicateElement&) {}
602  }
603 
604  try {
605  my_pool->insert(copyPotential(bij, *p));
606  } catch (Exception&) {
607  for (const auto pot: *my_pool)
608  delete pot;
609 
610  delete my_pool;
611  GUM_ERROR(OperationNotAllowed, "fake pattern");
612  }
613  }
614 
615  return my_pool;
616  }
617 
618  template < typename GUM_SCALAR >
619  void StructuredInference< GUM_SCALAR >::reduceAloneInstances__(
620  typename StructuredInference< GUM_SCALAR >::RGData& rg_data) {
621  StructuredInference< GUM_SCALAR >::CData* data = 0;
622  Potential< GUM_SCALAR >* pot = nullptr;
623  PRMInstance< GUM_SCALAR >* inst = nullptr;
624 
625  for (const auto& elt: *this->sys_) {
626  inst = elt.second;
627 
628  if (!reducedInstances__.exists(inst)) {
629  // Checking if its not an empty class
630  if (inst->size()) {
631  Set< Potential< GUM_SCALAR >* > pool;
632 
633  try {
634  data = cdata_map__[&(inst->type())];
635  } catch (NotFound&) {
636  data = new StructuredInference< GUM_SCALAR >::CData(inst->type());
637  cdata_map__.insert(&(inst->type()), data);
638  }
639 
640  data->instances.insert(inst);
641  // Filling up the partial ordering
642  List< NodeSet > partial_order;
643 
644  if (data->inners().size()) partial_order.push_back(data->inners());
645 
646  if (data->aggregators().size())
647  for (const auto agg: data->aggregators())
648  partial_order[0].insert(agg);
649 
650  if (data->outputs().size()) partial_order.push_back(data->outputs());
651 
652  if (query__.first == inst) {
653  // First case, the instance contains the query
654  partial_order[0].erase(query__.second->id());
655 
656  if (partial_order[0].empty()) partial_order.erase(0);
657 
658  if (partial_order.size() > 1) {
659  partial_order[1].erase(query__.second->id());
660 
661  if (partial_order[1].empty()) partial_order.erase(1);
662  }
663 
664  NodeSet query_set;
665  query_set.insert(query__.second->id());
666  partial_order.insert(query_set);
667 
668  // Adding the potentials
669  for (auto attr = inst->begin(); attr != inst->end(); ++attr)
670  pool.insert(&(
671  const_cast< Potential< GUM_SCALAR >& >((*(attr.val())).cpf())));
672 
673  // Adding evidences if any
674  if (this->hasEvidence(inst))
675  for (const auto& elt: this->evidence(inst))
676  pool.insert(const_cast< Potential< GUM_SCALAR >* >(elt.second));
677 
678  PartialOrderedTriangulation t(&(data->moral_graph),
679  &(data->mods),
680  &(partial_order));
681  const std::vector< NodeId >& v = t.eliminationOrder();
682 
683  if (partial_order.size() > 1)
684  for (size_t idx = 0; idx < partial_order[0].size(); ++idx)
685  eliminateNode(&(inst->get(v[idx]).type().variable()),
686  pool,
687  trash__);
688  } else if (this->hasEvidence(inst)) {
689  // Second case, the instance has evidences
690  // Adding the potentials
691  for (const auto elt: *inst)
692  pool.insert(
693  &const_cast< Potential< GUM_SCALAR >& >(elt.second->cpf()));
694 
695  // Adding evidences
696  for (const auto& elt: this->evidence(inst))
697  pool.insert(const_cast< Potential< GUM_SCALAR >* >(elt.second));
698 
699  PartialOrderedTriangulation t(&(data->moral_graph),
700  &(data->mods),
701  &(partial_order));
702 
703  for (size_t idx = 0; idx < partial_order[0].size(); ++idx)
704  eliminateNode(
705  &(inst->get(t.eliminationOrder()[idx]).type().variable()),
706  pool,
707  trash__);
708  } else {
709  // Last cast, the instance neither contains evidences nor
710  // instances
711  // We translate the class level potentials into the instance ones
712  // and
713  // proceed with elimination
714  for (const auto srcPot: data->pool) {
715  pot = copyPotential(inst->bijection(), *srcPot);
716  pool.insert(pot);
717  trash__.insert(pot);
718  }
719 
720  for (const auto agg: data->c.aggregates())
721  pool.insert(&(const_cast< Potential< GUM_SCALAR >& >(
722  inst->get(agg->id()).cpf())));
723 
724  // We eliminate inner aggregators with their parents if necessary
725  // (see
726  // CData constructor)
727  Size size = data->inners().size() + data->aggregators().size();
728 
729  for (size_t idx = data->inners().size(); idx < size; ++idx)
730  eliminateNode(
731  &(inst->get(data->elim_order()[idx]).type().variable()),
732  pool,
733  trash__);
734  }
735 
736  for (const auto pot: pool)
737  rg_data.pool.insert(pot);
738  }
739  }
740  }
741  }
742 
743  template < typename GUM_SCALAR >
744  void StructuredInference< GUM_SCALAR >::addEdgesInReducedGraph__(
745  typename StructuredInference< GUM_SCALAR >::RGData& data) {
746  // We first add edges between variables already in pool (i.e. those of the
747  // reduced instances)
748  NodeId id_1, id_2;
749 
750  for (const auto pot: data.pool) {
751  const Sequence< const DiscreteVariable* >& vars = pot->variablesSequence();
752 
753  for (Size var_1 = 0; var_1 < vars.size(); ++var_1) {
754  if (data.var2node.existsFirst(vars.atPos(var_1))) {
755  id_1 = data.var2node.second(vars.atPos(var_1));
756  } else {
757  id_1 = data.reducedGraph.addNode();
758  data.var2node.insert(vars.atPos(var_1), id_1);
759  data.mods.insert(id_1, vars.atPos(var_1)->domainSize());
760  data.outputs().insert(id_1);
761  }
762 
763  for (Size var_2 = var_1 + 1; var_2 < vars.size(); ++var_2) {
764  if (data.var2node.existsFirst(vars.atPos(var_2))) {
765  id_2 = data.var2node.second(vars.atPos(var_2));
766  } else {
767  id_2 = data.reducedGraph.addNode();
768  data.var2node.insert(vars.atPos(var_2), id_2);
769  data.mods.insert(id_2, vars.atPos(var_2)->domainSize());
770  data.outputs().insert(id_2);
771  }
772 
773  try {
774  data.reducedGraph.addEdge(id_1, id_2);
775  } catch (DuplicateElement&) {}
776  }
777  }
778  }
779 
780  // Adding potentials obtained from reduced patterns
781  for (const auto& elt: elim_map__) {
782  // We add edges between variables in the same reduced patterns
783  for (const auto pot: *elt.second) {
784  data.pool.insert(pot);
785  const Sequence< const DiscreteVariable* >& vars
786  = pot->variablesSequence();
787 
788  for (Size var_1 = 0; var_1 < vars.size(); ++var_1) {
789  if (data.var2node.existsFirst(vars.atPos(var_1))) {
790  id_1 = data.var2node.second(vars.atPos(var_1));
791  } else {
792  id_1 = data.reducedGraph.addNode();
793  data.var2node.insert(vars.atPos(var_1), id_1);
794  data.mods.insert(id_1, vars.atPos(var_1)->domainSize());
795  data.outputs().insert(id_1);
796  }
797 
798  for (Size var_2 = var_1 + 1; var_2 < vars.size(); ++var_2) {
799  if (data.var2node.existsFirst(vars.atPos(var_2))) {
800  id_2 = data.var2node.second(vars.atPos(var_2));
801  } else {
802  id_2 = data.reducedGraph.addNode();
803  data.var2node.insert(vars.atPos(var_2), id_2);
804  data.mods.insert(id_2, vars.atPos(var_2)->domainSize());
805  data.outputs().insert(id_2);
806  }
807 
808  try {
809  data.reducedGraph.addEdge(id_1, id_2);
810  } catch (DuplicateElement&) {}
811  }
812  }
813  }
814  }
815  }
816 
817  template < typename GUM_SCALAR >
818  StructuredInference< GUM_SCALAR >::RGData::RGData() {
819  GUM_CONSTRUCTOR(StructuredInference< GUM_SCALAR >::RGData);
820  partial_order.insert(NodeSet());
821  partial_order.insert(NodeSet());
822  }
823 
824  template < typename GUM_SCALAR >
825  StructuredInference< GUM_SCALAR >::PData::PData(
826  const gspan::Pattern& p,
827  typename GSpan< GUM_SCALAR >::MatchedInstances& m) :
828  pattern(p),
829  matches(m), real_order__(0) {
830  GUM_CONSTRUCTOR(StructuredInference< GUM_SCALAR >::PData);
831 
832  for (int i = 0; i < 4; ++i)
833  partial_order__.push_front(NodeSet());
834  }
835 
836  template < typename GUM_SCALAR >
837  StructuredInference< GUM_SCALAR >::PData::PData(
838  const typename StructuredInference< GUM_SCALAR >::PData& source) :
839  pattern(source.pattern),
840  matches(source.matches), graph(source.graph), mod(source.mod),
841  node2attr(source.node2attr), vars(source.vars),
842  partial_order__(source.partial_order__), real_order__(0) {
843  GUM_CONS_CPY(StructuredInference< GUM_SCALAR >::PData);
844  }
845 
846  template < typename GUM_SCALAR >
847  const List< NodeSet >*
848  StructuredInference< GUM_SCALAR >::PData::partial_order() {
849  if (!real_order__) {
850  real_order__ = new List< NodeSet >();
851 
852  for (const auto set: partial_order__)
853  if (set.size() > 0) real_order__->insert(set);
854  }
855 
856  return real_order__;
857  }
858 
859  template < typename GUM_SCALAR >
860  StructuredInference< GUM_SCALAR >::CData::CData(
861  const PRMClass< GUM_SCALAR >& a_class) :
862  c(a_class),
863  elim_order__(0) {
864  GUM_CONSTRUCTOR(StructuredInference< GUM_SCALAR >::CData);
865 
866  // First step we add Attributes and Aggregators
867  for (const auto node: c.containerDag().nodes()) {
868  switch (c.get(node).elt_type()) {
869  case PRMClassElement< GUM_SCALAR >::prm_attribute: {
870  pool.insert(
871  &(const_cast< Potential< GUM_SCALAR >& >(c.get(node).cpf())));
872  // break omited : We want to execute the next block
873  // for attributes
874  }
875 
876  case PRMClassElement< GUM_SCALAR >::prm_aggregate: {
877  moral_graph.addNodeWithId(node);
878  mods.insert(node, c.get(node).type()->domainSize());
879  break;
880  }
881 
882  default: { /* do nothing */
883  }
884  }
885  }
886 
887  // Second, we add edges, moralise the graph and build the partial ordering
888  for (const auto node: moral_graph.nodes()) {
889  const auto& parents = c.containerDag().parents(node);
890 
891  // Adding edges and marrying parents
892  for (auto tail = parents.begin(); tail != parents.end(); ++tail) {
893  if (PRMClassElement< GUM_SCALAR >::isAttribute(c.get(*tail))
894  || PRMClassElement< GUM_SCALAR >::isAggregate(c.get(*tail))) {
895  moral_graph.addEdge(*tail, node);
896  NodeSet::const_iterator marry = tail;
897  ++marry;
898 
899  while (marry != parents.end()) {
900  if (PRMClassElement< GUM_SCALAR >::isAttribute(c.get(*marry))
901  || PRMClassElement< GUM_SCALAR >::isAggregate(c.get(*marry)))
902  moral_graph.addEdge(*tail, *marry);
903 
904  ++marry;
905  }
906  }
907  }
908 
909  // Adding nodes to the partial ordering
910  switch (c.get(node).elt_type()) {
911  case PRMClassElement< GUM_SCALAR >::prm_aggregate: {
912  if (c.isOutputNode(c.get(node)))
913  outputs().insert(node);
914  else
915  aggregators().insert(node);
916 
917  // If the aggregators is not an output and have parents which are
918  // not outputs, we must eliminate the parents after adding the
919  // aggregator's CPT
920  for (const auto par: c.containerDag().parents(node)) {
921  const auto& prnt = c.get(par);
922 
923  if ((!c.isOutputNode(prnt))
924  && (PRMClassElement< GUM_SCALAR >::isAttribute(prnt)
925  || PRMClassElement< GUM_SCALAR >::isAggregate(prnt))) {
926  inners().erase(prnt.id());
927  aggregators().insert(prnt.id());
928  }
929  }
930 
931  break;
932  }
933 
934  case PRMClassElement< GUM_SCALAR >::prm_attribute: {
935  pool.insert(
936  const_cast< Potential< GUM_SCALAR >* >(&(c.get(node).cpf())));
937 
938  if (c.isOutputNode(c.get(node)))
939  outputs().insert(node);
940  else if (!aggregators().exists(node))
941  inners().insert(node);
942 
943  break;
944  }
945 
946  default: { /* Do nothing */
947  }
948  }
949  }
950 
951  if (inners().size()) partial_order.insert(inners());
952 
953  if (aggregators().size()) partial_order.insert(aggregators());
954 
955  if (outputs().size()) partial_order.insert(outputs());
956 
957  GUM_ASSERT(partial_order.size());
958  PartialOrderedTriangulation t(&moral_graph, &mods, &partial_order);
959  elim_order__ = t.eliminationOrder();
960 
961  for (size_t i = 0; i < inners().size(); ++i)
962  eliminateNode(&(c.get(elim_order__[i]).type().variable()), pool, trash__);
963  }
964 
965  template < typename GUM_SCALAR >
966  StructuredInference< GUM_SCALAR >::CData::~CData() {
967  GUM_DESTRUCTOR(StructuredInference< GUM_SCALAR >::CData);
968 
969  for (const auto pot: trash__)
970  delete pot;
971  }
972 
973  template < typename GUM_SCALAR >
974  void StructuredInference< GUM_SCALAR >::searchPatterns() {
975  const PRMInstance< GUM_SCALAR >* i = (this->sys_->begin()).val();
976  query__ = std::make_pair(i, i->begin().val());
977  found_query__ = false;
978  typename StructuredInference< GUM_SCALAR >::RGData data;
979  buildReduceGraph__(data);
980  }
981 
982  template < typename GUM_SCALAR >
983  INLINE void StructuredInference< GUM_SCALAR >::setPatternMining(bool b) {
984  mining__ = b;
985  }
986 
987  template < typename GUM_SCALAR >
988  INLINE std::string StructuredInference< GUM_SCALAR >::str__(
989  const PRMInstance< GUM_SCALAR >* i,
990  const PRMAttribute< GUM_SCALAR >* a) const {
991  return i->name() + dot__ + a->safeName();
992  }
993 
994  template < typename GUM_SCALAR >
995  INLINE std::string StructuredInference< GUM_SCALAR >::str__(
996  const PRMInstance< GUM_SCALAR >* i,
997  const PRMAttribute< GUM_SCALAR >& a) const {
998  return i->name() + dot__ + a.safeName();
999  }
1000 
1001  template < typename GUM_SCALAR >
1002  INLINE std::string StructuredInference< GUM_SCALAR >::str__(
1003  const PRMInstance< GUM_SCALAR >* i,
1004  const PRMSlotChain< GUM_SCALAR >& a) const {
1005  return i->name() + dot__ + a.lastElt().safeName();
1006  }
1007 
1008  template < typename GUM_SCALAR >
1009  INLINE StructuredInference< GUM_SCALAR >::RGData::~RGData() {
1010  GUM_DESTRUCTOR(StructuredInference< GUM_SCALAR >::RGData);
1011  }
1012 
1013  template < typename GUM_SCALAR >
1014  INLINE StructuredInference< GUM_SCALAR >::PData::~PData() {
1015  GUM_DESTRUCTOR(StructuredInference< GUM_SCALAR >::PData);
1016  }
1017 
1018  template < typename GUM_SCALAR >
1019  INLINE std::string StructuredInference< GUM_SCALAR >::name() const {
1020  return "StructuredInference";
1021  }
1022 
1023  template < typename GUM_SCALAR >
1024  INLINE GSpan< GUM_SCALAR >& StructuredInference< GUM_SCALAR >::gspan() {
1025  return *gspan__;
1026  }
1027 
1028  template < typename GUM_SCALAR >
1029  INLINE const GSpan< GUM_SCALAR >&
1030  StructuredInference< GUM_SCALAR >::gspan() const {
1031  return *gspan__;
1032  }
1033 
1034  template < typename GUM_SCALAR >
1035  INLINE void StructuredInference< GUM_SCALAR >::removeNode__(
1036  typename StructuredInference< GUM_SCALAR >::PData& data,
1037  NodeId id,
1038  Set< Potential< GUM_SCALAR >* >& pool) {
1039  data.graph.eraseNode(id);
1040  GUM_ASSERT(!data.graph.exists(id));
1041  data.mod.erase(id);
1042  GUM_ASSERT(!data.mod.exists(id));
1043  data.node2attr.eraseFirst(id);
1044  GUM_ASSERT(!data.node2attr.existsFirst(id));
1045  data.map.erase(id);
1046  GUM_ASSERT(!data.map.exists(id));
1047  data.vars.eraseFirst(id);
1048  GUM_ASSERT(!data.vars.existsFirst(id));
1049  data.inners().erase(id);
1050  GUM_ASSERT(!data.inners().exists(id));
1051  pool.erase(data.pots[id]);
1052  GUM_ASSERT(!pool.exists(data.pots[id]));
1053  data.pots.erase(id);
1054  GUM_ASSERT(!data.pots.exists(id));
1055  }
1056 
1057  } /* namespace prm */
1058 } /* namespace gum */
gum::Set::emplace
INLINE void emplace(Args &&... args)
Definition: set_tpl.h:669
gum::prm::ParamScopeData::ParamScopeData
ParamScopeData(const std::string &s, const PRMReferenceSlot< GUM_SCALAR > &ref, Idx d)
Definition: PRMClass_tpl.h:1101
aGrUM 0.20.2
Sun May 2 2021 12:35:56
© PHW&CG&others - 2021
DoXyGeN 1.8.13