aGrUM  0.13.2
MCBayesNetGenerator_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Pierre-Henri WUILLEMIN & Ariele-Paolo MAESANO *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
28 
29 namespace gum {
30 
31 #ifdef _MSC_VER
32 # define IBNG IBayesNetGenerator
33 #else
34 # define IBNG IBayesNetGenerator< GUM_SCALAR, ICPTGenerator >
35 #endif
36 
37  template < typename GUM_SCALAR >
39  gum::Size maxMod = 0;
40 
41  for (auto node : bayesNet.nodes())
42  if (maxMod < bayesNet.variable(node).domainSize())
43  maxMod = bayesNet.variable(node).domainSize();
44 
45  return maxMod;
46  }
47 
48  // Default constructor.
49  // Use the SimpleCPTGenerator for generating the BNs CPT.
50  template < typename GUM_SCALAR,
51  template < typename > class ICPTGenerator,
52  template < typename > class ICPTDisturber >
55  Size nbrNodes, Size maxArcs, Idx maxModality, Size iteration, Idx p, Idx q) :
56  IBNG(nbrNodes, maxArcs, maxModality),
57  _bayesNettemp(), _hashMarginal() {
58  if (p + q > 100)
59  GUM_ERROR(
61  "the sum of the probabilities p and q must be at most equal to 100");
62 
64  _p = p;
65  _q = q;
66  _disturbing = false;
67 
68  GUM_CONSTRUCTOR(MCBayesNetGenerator);
69  }
70 
71  template < typename GUM_SCALAR,
72  template < typename > class ICPTGenerator,
73  template < typename > class ICPTDisturber >
77  Idx p,
78  Idx q) :
79  MCBayesNetGenerator(bayesNet.size(),
80  (Size)(bayesNet.sizeArcs() * 1.1),
81  getMaxModality(bayesNet)) {
83  _p = p;
84  _q = q;
85  _disturbing = false;
86  }
87 
88  // Destructor.
89  template < typename GUM_SCALAR,
90  template < typename > class ICPTGenerator,
91  template < typename > class ICPTDisturber >
94  GUM_DESTRUCTOR(MCBayesNetGenerator);
95  }
96 
97  template < typename GUM_SCALAR,
98  template < typename > class ICPTGenerator,
99  template < typename > class ICPTDisturber >
101  BayesNet< GUM_SCALAR >& bayesNet) {
103 
104  // this->_bayesNet = bayesNet;
105  __createTree(this->_nbrNodes);
106  __transformPoly(this->_nbrNodes / 2);
107  _bayesNettemp = this->_bayesNet;
108  __PMMx_poly();
109 
110  this->fillCPT();
112 
113  bayesNet = this->_bayesNet;
114  }
115 
116  // density represent de
117  template < typename GUM_SCALAR,
118  template < typename > class ICPTGenerator,
119  template < typename > class ICPTDisturber >
121  BayesNet< GUM_SCALAR >& bayesNetinit,
122  Size iteration) { // insert option for the variation
123  _disturbing = true;
124  Size iter = _iteration;
125 
126  if (iteration) _iteration = iteration;
127 
128  this->_bayesNet = bayesNetinit;
129 
130  if (__checkConditions()) {
131  LazyPropagation< GUM_SCALAR > inf(&bayesNetinit);
132  inf.makeInference();
133 
134  for (auto node : bayesNetinit.nodes()) {
135  auto pottemp = new Potential< GUM_SCALAR >();
136  pottemp->copy(inf.posterior(node));
137  _hashMarginal.insert(node, pottemp);
138  }
139 
140  _bayesNettemp = this->_bayesNet;
141 
142  if (__isPolytree())
143  __PMMx_poly();
144  else
145  __PMMx_multi();
146 
147  bayesNetinit = (this->_bayesNet);
148 
149  while (_hashMarginal.size()) {
150  delete (_hashMarginal.begin().val());
151  _hashMarginal.erase(
152  _hashMarginal.beginSafe()); // safe iterator needed here.
153  }
154 
155  } else {
156  std::cout << this->_bayesNet.toDot() << std::endl;
158  "BN is not valid cause it does not respect constraint ");
159  }
160 
161  _iteration = iter;
162  _disturbing = false;
163  }
164 
165  template < typename GUM_SCALAR,
166  template < typename > class ICPTGenerator,
167  template < typename > class ICPTDisturber >
170  return this->_maxArcs >= this->_bayesNet.sizeArcs();
171  }
172 
173  // main algorithme for moving between state of the IBayesNet according on the
174  // nature of the topology polytree or multi-connected
175 
176  template < typename GUM_SCALAR,
177  template < typename > class ICPTGenerator,
178  template < typename > class ICPTDisturber >
181  if (!_iteration--) return;
182 
183  Idx per = randomValue(100);
184 
185  if (per < _p) {
186  __AorR();
187 
188  if (__checkConditions()) {
189  _bayesNettemp = this->_bayesNet;
190  __PMMx_multi();
191  } else {
192  this->_bayesNet = _bayesNettemp;
193  __PMMx_poly();
194  }
195  } else {
196  if (per < _p + _q) {
197  __AR();
198 
199  if (!__checkConditions()) {
200  this->_bayesNet = _bayesNettemp;
201  } else
202  _bayesNettemp = this->_bayesNet;
203 
204  __PMMx_poly();
205  } else {
206  __jump_poly();
207 
208  if (__checkConditions()) {
209  _bayesNettemp = this->_bayesNet;
210  __PMMx_multi();
211 
212  } else {
213  this->_bayesNet = _bayesNettemp;
214  __PMMx_poly();
215  }
216  }
217  }
218  }
219 
220  template < typename GUM_SCALAR,
221  template < typename > class ICPTGenerator,
222  template < typename > class ICPTDisturber >
225  if (!_iteration--) return;
226 
227  Idx per = randomValue(100);
228 
229  if (per < _p + _q) {
230  __AorR();
231 
232  if (__checkConditions()) {
233  if (__isPolytree()) {
234  if (per < _p) {
235  _bayesNettemp = this->_bayesNet;
236  __PMMx_poly();
237  } else {
238  this->_bayesNet = _bayesNettemp;
239  __PMMx_multi();
240  }
241  } else {
242  _bayesNettemp = this->_bayesNet;
243  __PMMx_multi();
244  }
245  } else {
246  this->_bayesNet = _bayesNettemp;
247  __PMMx_multi();
248  }
249  } else {
250  __jump_multi();
251 
252  if (__checkConditions()) {
253  _bayesNettemp = this->_bayesNet;
254 
255  if (__isPolytree())
256  __PMMx_poly();
257  else
258  __PMMx_multi(); // TODO verification required
259 
260  } else {
261  this->_bayesNet = _bayesNettemp;
262  __PMMx_multi();
263  }
264  }
265  }
266 
267  template < typename GUM_SCALAR,
268  template < typename > class ICPTGenerator,
269  template < typename > class ICPTDisturber >
271  NodeId i, j;
272  __chooseNodes(i, j);
273  const DAG __dag = this->_bayesNet.dag();
274 
275  if (__dag.existsArc(i, j)) {
276  __eraseArc(i, j);
277 
278  return;
279  } else
280  __insertArc(i, j);
281  }
282 
283  template < typename GUM_SCALAR,
284  template < typename > class ICPTGenerator,
285  template < typename > class ICPTDisturber >
287  NodeId i, j, head, tail;
288  __chooseNodes(i, j);
289  const DAG __dag = this->_bayesNet.dag();
290 
291  if (__dag.existsArc(i, j) || __dag.existsArc(j, i)) {
292  return;
293  } else {
294  Idx per = randomValue(100);
295 
296  if (per < 50) {
297  head = i;
298  tail = j;
299  } else {
300  head = j;
301  tail = i;
302  }
303 
304  for (auto node : __dag.parents(j)) {
305  NodeSet excluded;
306  excluded.insert(j);
307 
308  if (__connect(node, i, excluded)) {
309  this->_bayesNet.eraseArc(node, j); // TODO reflect
310  this->_bayesNet.addArc(head, tail);
311  return;
312  }
313  }
314 
315  for (auto node : __dag.children(j)) {
316  NodeSet excluded;
317  excluded.insert(j);
318 
319  if (__connect(node, i, excluded)) {
320  this->_bayesNet.eraseArc(j, node);
321  this->_bayesNet.addArc(head, tail);
322  return;
323  }
324  }
325  }
326  }
327 
328  template < typename GUM_SCALAR,
329  template < typename > class ICPTGenerator,
330  template < typename > class ICPTDisturber >
333  NodeId i, j;
334  __chooseNodes(i, j);
335  const DAG __dag = this->_bayesNet.dag();
336 
337  if (!__dag.existsArc(i, j)) __insertArc(i, j);
338  }
339 
340  template < typename GUM_SCALAR,
341  template < typename > class ICPTGenerator,
342  template < typename > class ICPTDisturber >
345  NodeId i, j;
346  __chooseNodes(i, j);
347  const DAG __dag = this->_bayesNet.dag();
348 
349  if (__dag.existsArc(i, j)) { __eraseArc(i, j); }
350  }
351 
352  template < typename GUM_SCALAR,
353  template < typename > class ICPTGenerator,
354  template < typename > class ICPTDisturber >
355  INLINE void
357  NodeId i, NodeId j) {
358  if (__directedPath(j, i)) return;
359 
360  if (_disturbing) {
361  auto potj = this->_bayesNet.cpt(j);
362  this->_bayesNet.addArc(i, j);
363 
364  this->disturbAugmCPT(j, this->_bayesNet, potj, (GUM_SCALAR)0.5);
365  } else
366  this->_bayesNet.addArc(i, j);
367  }
368 
369  template < typename GUM_SCALAR,
370  template < typename > class ICPTGenerator,
371  template < typename > class ICPTDisturber >
372  INLINE void
374  NodeId i, NodeId j, bool mustbeconnex) {
375  if (_disturbing) {
376  const BayesNet< GUM_SCALAR > bayesNet(this->_bayesNet);
378  potj.copy(this->_bayesNet.cpt(j));
379  this->_bayesNet.eraseArc(i, j);
380 
381  if (__connect(i, j) || !mustbeconnex) {
382  auto marg = *_hashMarginal[i];
383 
384  this->disturbReducCPT(j, this->_bayesNet, potj, marg);
385  } else
386  this->_bayesNet.addArc(i, j);
387  } else {
388  this->_bayesNet.eraseArc(i, j);
389 
390  if (!__connect(i, j) && mustbeconnex) { this->_bayesNet.addArc(i, j); }
391  }
392  }
393 
394  template < typename GUM_SCALAR,
395  template < typename > class ICPTGenerator,
396  template < typename > class ICPTDisturber >
397  INLINE void
399  NodeId& i, NodeId& j) {
400  i = randomValue(this->_bayesNet.size());
401  j = randomValue(this->_bayesNet.size());
402 
403  while (i == j)
404  j = randomValue(this->_bayesNet.size());
405  }
406 
407  template < typename GUM_SCALAR,
408  template < typename > class ICPTGenerator,
409  template < typename > class ICPTDisturber >
412  NodeId temp = randomValue(this->_bayesNet.size());
413  Size co = 0;
414 
415  if (this->_bayesNet.parents(temp).size()) {
416  j = temp;
417  auto it = this->_bayesNet.parents(j).begin();
418  co = randomValue(this->_bayesNet.parents(j).size());
419 
420  while (co--) {
421  ++it;
422  }
423 
424  i = *it;
425  } else if (this->_bayesNet.children(temp).size()) {
426  i = temp;
427  auto it = this->_bayesNet.children(i).begin();
428  co = randomValue(this->_bayesNet.children(i).size());
429 
430  while (co--) {
431  ++it;
432  }
433 
434  j = *it;
435  } else {
436  GUM_ERROR(FatalError, "Sorry Misconstructed BN because of isolated node.");
437  }
438  }
439 
440  template < typename GUM_SCALAR,
441  template < typename > class ICPTGenerator,
442  template < typename > class ICPTDisturber >
443  void
445  Size BNSize) {
446  Idx n = 0;
447  int nb_mod = 2 + randomValue(this->_maxModality - 1);
448  std::stringstream strBuff;
449  strBuff << "n_" << n++;
450  NodeId root =
451  this->_bayesNet.add(LabelizedVariable(strBuff.str(), "", nb_mod));
452  Size maxNodes = BNSize - 1;
453  Size SubG = 0;
454 
455  while (maxNodes) {
456  SubG = randomValue(maxNodes) + 1;
457  maxNodes = maxNodes - SubG;
458  NodeId rootS = __createPartTree(SubG, n);
459  this->_bayesNet.addArc(root, rootS);
460  }
461  }
462 
463  template < typename GUM_SCALAR,
464  template < typename > class ICPTGenerator,
465  template < typename > class ICPTDisturber >
468  int nb_mod = 2 + randomValue(this->_maxModality - 1);
469  std::stringstream strBuff;
470  strBuff << "n_" << n++;
471  NodeId root =
472  this->_bayesNet.add(LabelizedVariable(strBuff.str(), "", nb_mod));
473  Size maxNodes = BNSize - 1;
474  Size SubG = 0;
475 
476  while (maxNodes) {
477  SubG = randomValue(maxNodes) + 1;
478  maxNodes = maxNodes - SubG;
479  NodeId rootS = __createPartTree(SubG, n);
480  this->_bayesNet.addArc(root, rootS);
481  }
482 
483  return root;
484  }
485 
486  // Allow to invert maximum nbiter arc to use from polytree only
487  template < typename GUM_SCALAR,
488  template < typename > class ICPTGenerator,
489  template < typename > class ICPTDisturber >
492  while (nbiter--) {
493  NodeId i, j;
494  __chooseCloseNodes(i, j);
495  _bayesNettemp = this->_bayesNet;
496  __eraseArc(i, j, false);
497  this->_bayesNet.addArc(j, i);
498 
499  if (!__checkConditions()) this->_bayesNet = _bayesNettemp;
500  }
501  }
502 
503  template < typename GUM_SCALAR,
504  template < typename > class ICPTGenerator,
505  template < typename > class ICPTDisturber >
508  const DAG __dag = this->_bayesNet.dag();
509  return this->_bayesNet.size() - 1 == this->_bayesNet.sizeArcs();
510  }
511 
512  template < typename GUM_SCALAR,
513  template < typename > class ICPTGenerator,
514  template < typename > class ICPTDisturber >
516  const NodeId i, const NodeId j) {
517  const DAG __dag = this->_bayesNet.dag();
518 
519  if (__dag.existsArc(i, j) || __dag.existsArc(j, i))
520  return true;
521  else {
522  NodeSet excluded;
523  excluded.insert(i);
524 
525  for (auto par : __dag.parents(i)) {
526  if (!excluded.exists(par) && __connect(par, j, excluded)) return true;
527  }
528 
529  for (auto chi : __dag.children(i)) {
530  if (!excluded.exists(chi) && __connect(chi, j, excluded)) return true;
531  }
532 
533  return false;
534  }
535  }
536 
537  template < typename GUM_SCALAR,
538  template < typename > class ICPTGenerator,
539  template < typename > class ICPTDisturber >
541  const NodeId i, const NodeId j, NodeSet& excluded) {
542  const DAG __dag = this->_bayesNet.dag();
543 
544  if (__dag.existsArc(i, j) || __dag.existsArc(j, i))
545  return true;
546  else {
547  excluded.insert(i);
548 
549  for (auto par : __dag.parents(i)) {
550  if (!excluded.exists(par) && __connect(par, j, excluded)) return true;
551  }
552 
553  for (auto chi : __dag.children(i)) {
554  if (!excluded.exists(chi) && __connect(chi, j, excluded)) return true;
555  }
556 
557  return false;
558  }
559  }
560 
561  template < typename GUM_SCALAR,
562  template < typename > class ICPTGenerator,
563  template < typename > class ICPTDisturber >
566  const DAG __dag = this->_bayesNet.dag();
567 
568  if (__dag.existsArc(tail, head))
569  return true;
570  else {
571  NodeSet excluded;
572  excluded.insert(tail);
573 
574  for (auto node : __dag.children(tail)) {
575  if (__directedPath(node, head, excluded)) return true;
576  }
577 
578  return false;
579  }
580  }
581 
582  template < typename GUM_SCALAR,
583  template < typename > class ICPTGenerator,
584  template < typename > class ICPTDisturber >
586  __directedPath(NodeId tail, NodeId head, NodeSet& excluded) {
587  const DAG __dag = this->_bayesNet.dag();
588 
589  if (__dag.existsArc(tail, head))
590  return true;
591  else {
592  excluded.insert(tail);
593 
594  for (auto node : __dag.children(tail)) {
595  if (!excluded.exists(node) && __directedPath(node, head, excluded))
596  return true;
597  }
598 
599  return false;
600  }
601  }
602 
603  template < typename GUM_SCALAR,
604  template < typename > class ICPTGenerator,
605  template < typename > class ICPTDisturber >
606  INLINE Size
608  const {
609  return _iteration;
610  }
611 
612  template < typename GUM_SCALAR,
613  template < typename > class ICPTGenerator,
614  template < typename > class ICPTDisturber >
615  INLINE Idx
617  return _p;
618  }
619 
620  template < typename GUM_SCALAR,
621  template < typename > class ICPTGenerator,
622  template < typename > class ICPTDisturber >
623  INLINE Idx
625  return _q;
626  }
627 
628  template < typename GUM_SCALAR,
629  template < typename > class ICPTGenerator,
630  template < typename > class ICPTDisturber >
631  INLINE void
633  Size iteration) {
635  }
636  template < typename GUM_SCALAR,
637  template < typename > class ICPTGenerator,
638  template < typename > class ICPTDisturber >
639  INLINE void
641  _p = p;
642 
643  if (p + _q > 100)
644  GUM_ERROR(
646  "the sum of the probabilities p and q must be at most equal to 100");
647  }
648  template < typename GUM_SCALAR,
649  template < typename > class ICPTGenerator,
650  template < typename > class ICPTDisturber >
651  INLINE void
653  _q = q;
654 
655  if (_p + q > 100)
656  GUM_ERROR(
658  "the sum of the probabilities p and q must be at most equal to 100");
659  }
660 
661 } /* namespace gum */
aGrUM&#39;s Potential is a multi-dimensional array with tensor operators.
Definition: potential.h:57
Class representing a Bayesian Network.
Definition: BayesNet.h:76
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
MCBayesNetGenerator(Size nbrNodes, Size maxArcs, Idx maxModality=2, Size iteration=5000, Idx p=30, Idx q=40)
Constructor.
virtual bool __checkConditions()
The boolean function that will assert the respect of the constraint.
void __PMMx_poly()
In the case that the graph is a polytree, the function will, according to the probability p and q...
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
const DiscreteVariable & variable(NodeId id) const final
Returns a gum::DiscreteVariable given its gum::NodeId in the gum::BayesNet.
Definition: BayesNet_tpl.h:189
class LabelizedVariable
Idx randomValue(const Size max=2)
Returns a random Idx between 0 and max-1 included.
<agrum/BN/generator/MCayesNetGenerator.h>
void fillCPT()
function that insert random values in the CPT of each nodes according to the CPTGenerator.
gum::Size getMaxModality(gum::BayesNet< GUM_SCALAR > &bayesNet)
bool __connect(NodeId i, NodeId j)
The function that verify if node i and j are connected.
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:607
void setQ(Idx q)
Modifies the value of the probability q imposed on the BayesNetGenerator.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
virtual void copy(const MultiDimContainer< GUM_SCALAR > &src)
Removes all variables in this MultiDimContainer and copy the content of src, variables included...
void __jump_multi()
In the case that the graph is a multiconnect graph, the function will choose randomly two nodes and w...
bool __isPolytree()
The function that verify if graph is a polytree.
virtual void makeInference() final
perform the heavy computations needed to compute the targets&#39; posteriors
#define IBNG
virtual Size domainSize() const =0
void setP(Idx p)
Modifies the value of the probability p imposed on the BayesNetGenerator.
~MCBayesNetGenerator() override
Destructor.
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
BayesNet< GUM_SCALAR > _bayesNet
BayesNet< GUM_SCALAR > _bayesNettemp
void __transformPoly(Idx nbiter)
The function that randomly change the simple tree into a polytree.
void __jump_poly()
In the case that the graph is a polytree, the function will add a ramdom arc by the use of the functi...
Idx p() const
Return a constant reference to the probabilité p imposed on the Markov Chain BayesNetGenerator.
NodeId __createPartTree(Size BNSize, Idx &n)
The internal function used by __createTree that randomly generate a simple tree.
Size iteration() const
Return a constant reference to the number of iteration imposed on the Markov Chain BayesNetGenerator...
void setIteration(Size iteration)
Modifies the value of the number of iterations impose on the BayesNetGenerator.
void disturbBN(BayesNet< GUM_SCALAR > &bayesNetinit, Size iteration=0)
Change randomly the topology of a specific bayesian networks.
bool existsArc(const Arc &arc) const
indicates whether a given arc exists
void __chooseNodes(NodeId &i, NodeId &j)
The function that randomly choose two nodes of the graph.
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
virtual const Potential< GUM_SCALAR > & posterior(NodeId node) final
Computes and returns the posterior of a node.
void __AR()
The function will remove and add a random arc changing the topology of the graph but asserting its co...
<agrum/BN/inference/lazyPropagation.h>
void __insertArc(NodeId i, NodeId j)
The function that will insert an arc between node i to node j, but only if there isn&#39;t any cycle crea...
void generateBN(BayesNet< GUM_SCALAR > &bayesNet) override
Generates a random bayesian network.
void __eraseArc(NodeId i, NodeId j, bool mustbeconnex=true)
The function that will remove the arc between node i and node j.
void __chooseCloseNodes(NodeId &i, NodeId &j)
The function that randomly choose two neighbours nodes of the graph.
void __AorR()
The function will add or remove a random arc in the graph using the functions __insertArc and __remov...
void __PMMx_multi()
In the case that the graph is a multiconnected graph, the function will, according to the probability...
bool __directedPath(NodeId tail, NodeId head)
The function that verify if there is a oriented path from node i to node j.
const NodeGraphPart & nodes() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:113
unsigned long Idx
Type for indexes.
Definition: types.h:43
Idx q() const
Return a constant reference to the probabilité imposed on the Markov Chain BayesNetGenerator.
Class for generating bayesian networks.using MC algorithm cf.
void __createTree(Size BNSize)
The function that randomly generate a simple tree.
Base class for dag.
Definition: DAG.h:98
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
HashTable< NodeId, Potential< GUM_SCALAR > * > _hashMarginal