aGrUM  0.18.1
a C++ library for (probabilistic) graphical models
multiDimFunctionGraph_tpl.h
Go to the documentation of this file.
1 
31 
32 namespace gum {
33 
34  // Default constructor.
35  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
37  MultiDimFunctionGraph(bool isReduced) :
38  MultiDimImplementation< GUM_SCALAR >(),
39  name__("MultiDimFunctionGraph"), tableName__("NO NAME"), model__(500, true),
40  manager__(nullptr), root__(0), internalNodeMap__(500, true, false),
41  var2NodeIdMap__(500, true, false), isReduced__(isReduced) {
42  GUM_CONSTRUCTOR(MultiDimFunctionGraph);
43  manager__ = nullptr;
44  // Pop up a first node so that id 0 is unavailable
45  model__.addNode();
46  }
47 
48  // Copy constructor.
49  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
53  MultiDimImplementation< GUM_SCALAR >(),
54  name__("MultiDimFunctionGraph"), tableName__("No NAME"), model__(500, true),
55  manager__(nullptr), root__(0), internalNodeMap__(500, true, false),
56  var2NodeIdMap__(500, true, false), isReduced__(from.isReducedAndOrdered()) {
57  GUM_CONS_CPY(MultiDimFunctionGraph);
58  copy(from);
59  }
60 
61  // Copy Operator.
62  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
66  copy(from);
67  return *this;
68  }
69 
70  // Destructor.
71  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
72  INLINE MultiDimFunctionGraph< GUM_SCALAR,
73  TerminalNodePolicy >::~MultiDimFunctionGraph() {
74  // Manager deletion
75  GUM_DESTRUCTOR(MultiDimFunctionGraph);
76  if (manager__ != nullptr) delete manager__;
77  this->clear();
78  }
79 
80  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
83  if (isReduced__)
86  else
87  return MultiDimFunctionGraph< GUM_SCALAR,
88  TerminalNodePolicy >::getTreeInstance();
89  }
90 
91  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
92  INLINE const std::string&
94  return name__;
95  }
96 
97  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
99  const Instantiation& i, const GUM_SCALAR& value) const {
101  "Function Graph can't be edited so "
102  "easily.\nMultiDimFunctionGraphManager "
103  "provides the framework to edit a "
104  "Function Graph.")
105  }
106 
107  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
109  const GUM_SCALAR& d) const {
111  "Function Graph can't be edited so "
112  "easily.\nMultiDimFunctionGraphManager "
113  "provides the framework to edit a "
114  "Function Graph.")
115  }
116 
117  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
119  const std::vector< GUM_SCALAR >& v) const {
121  "Function Graph can't be edited so "
122  "easily.\nMultiDimFunctionGraphManager "
123  "provides the framework to editaa "
124  "Function Graph.")
125  }
126  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
128  std::initializer_list< GUM_SCALAR > l) const {
130  "Function Graph can't be edited so "
131  "easily.\nMultiDimFunctionGraphManager "
132  "provides the framework to edit a "
133  "Function Graph.")
134  }
135 
136  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
138  const DiscreteVariable& v) {
139  if (!this->variablesSequence().exists(&v))
141 
142  if (!this->var2NodeIdMap__.exists(&v))
143  var2NodeIdMap__.insert(&v, new LinkedList< NodeId >());
144  }
145 
146  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
148  const DiscreteVariable& v) {
149  if (this->var2NodeIdMap__.exists(&v)) {
150  while (var2NodeIdMap__[&v]->list() != nullptr) {
151  manager()->eraseNode(var2NodeIdMap__[&v]->list()->element());
152  }
153  delete var2NodeIdMap__[&v];
154  var2NodeIdMap__.erase(&v);
155  }
156 
157  if (this->variablesSequence().exists(&v))
159  }
160 
161  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
162  INLINE Size
164  return internalNodeMap__.size(); // + valueMap__.size();
165  }
166 
167 
168  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
169  INLINE void
171  const Instantiation& i,
172  const DiscreteVariable* const var,
173  Idx oldval,
174  Idx newval) {}
175 
176  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
177  INLINE void
179  const Instantiation& i) {}
180 
181  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
182  INLINE void
184  const Instantiation& i) {}
185 
186  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
187  INLINE void
189  const Instantiation& i) {}
190 
191  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
192  INLINE void
194  const Instantiation& i) {}
195 
196  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
199 
200  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
201  INLINE const std::string
203  const Instantiation* i) const {
204  std::stringstream sBuff;
205  sBuff << (*i) << " = " << this->get(*i);
206  return sBuff.str();
207  }
208 
209  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
211  const MultiDimContainer< GUM_SCALAR >& src, Instantiation* p_i) const {
213  "You cannot copy another type of multiDim "
214  "into a MultiDimFunctionGraph.");
215  }
216 
217  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
219  const MultiDimContainer< GUM_SCALAR >& src) {
221  "You cannot copy another type of multiDim "
222  "into a MultiDimFunctionGraph.");
223  }
224 
225  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
228  if (this->isReduced__ != src.isReducedAndOrdered())
230  "Cannot copy a Reduced and Ordered "
231  "function graph into Tree function graph "
232  "(or vice-versa).")
233 
234  this->clear();
235 
236  // New variables insertion
238  src.variablesSequence().beginSafe();
239  varIter != src.variablesSequence().endSafe();
240  ++varIter)
241  this->add(**varIter);
242 
243  std::vector< NodeId > lifo;
245 
246  if (src.isTerminalNode(src.root()))
247  this->manager()->setRootNode(
248  this->manager()->addTerminalNode(src.nodeValue(src.root())));
249  else {
250  this->manager()->setRootNode(
251  this->manager()->addInternalNode(src.node(src.root())->nodeVar()));
252  src2dest.insert(src.root(), this->root());
253  lifo.push_back(src.root());
254  }
255 
256  // Depth-first exploration and copy
257  while (!lifo.empty()) {
258  NodeId currentSrcNodeId = lifo.back();
259  lifo.pop_back();
260 
261  const InternalNode* currentSrcNode = src.node(currentSrcNodeId);
262 
263  for (Idx index = 0; index < currentSrcNode->nbSons(); ++index) {
264  if (!src2dest.existsFirst(currentSrcNode->son(index))) {
265  NodeId srcSonNodeId = currentSrcNode->son(index), destSonNodeId = 0;
266  if (src.isTerminalNode(srcSonNodeId)) {
267  destSonNodeId =
268  this->manager()->addTerminalNode(src.nodeValue(srcSonNodeId));
269  } else {
270  destSonNodeId =
271  this->manager()->addInternalNode(src.node(srcSonNodeId)->nodeVar());
272  lifo.push_back(srcSonNodeId);
273  }
274  src2dest.insert(srcSonNodeId, destSonNodeId);
275  }
276  this->manager()->setSon(src2dest.second(currentSrcNodeId),
277  index,
278  src2dest.second(currentSrcNode->son(index)));
279  }
280  }
281 
282  manager()->clean();
283  }
284 
285  // Copies src diagrams structure into this diagrams.
286  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
287  INLINE void
291  reassign) {
292  if (this->isReduced__ != src.isReducedAndOrdered())
294  "Cannot copy a Reduced and Ordered "
295  "function graph into Tree function graph "
296  "(or vice-versa).")
297 
298  this->clear();
299 
300  // New variables insertion
302  src.variablesSequence().beginSafe();
303  varIter != src.variablesSequence().endSafe();
304  ++varIter) {
305  if ((*varIter)->domainSize() != reassign.second(*varIter)->domainSize())
307  "Var " << (*varIter)->name() << " and var "
308  << reassign.second(*varIter)->name()
309  << " have different domain sizes ("
310  << (*varIter)->domainSize()
311  << "!=" << reassign.second(*varIter)->domainSize() << ")")
312  this->add(*(reassign.second(*varIter)));
313  }
314 
315  std::vector< NodeId > lifo;
317 
318  if (src.isTerminalNode(src.root())) {
319  this->manager()->setRootNode(
320  this->manager()->addTerminalNode(src.nodeValue(src.root())));
321  } else {
322  this->manager()->setRootNode(this->manager()->addInternalNode(
323  reassign.second(src.node(src.root())->nodeVar())));
324  src2dest.insert(src.root(), this->root());
325  lifo.push_back(src.root());
326  }
327 
328  // Depth-first exploration and copy
329  while (!lifo.empty()) {
330  NodeId currentSrcNodeId = lifo.back();
331  lifo.pop_back();
332 
333  const InternalNode* currentSrcNode = src.node(currentSrcNodeId);
334 
335  for (Idx index = 0; index < currentSrcNode->nbSons(); ++index) {
336  if (!src2dest.existsFirst(currentSrcNode->son(index))) {
337  NodeId srcSonNodeId = currentSrcNode->son(index), destSonNodeId = 0;
338  if (src.isTerminalNode(srcSonNodeId)) {
339  destSonNodeId =
340  this->manager()->addTerminalNode(src.nodeValue(srcSonNodeId));
341  } else {
342  destSonNodeId = this->manager()->addInternalNode(
343  reassign.second(src.node(srcSonNodeId)->nodeVar()));
344  lifo.push_back(srcSonNodeId);
345  }
346  src2dest.insert(srcSonNodeId, destSonNodeId);
347  }
348  this->manager()->setSon(src2dest.second(currentSrcNodeId),
349  index,
350  src2dest.second(currentSrcNode->son(index)));
351  }
352  }
353 
354  manager()->clean();
355  }
356 
357  // Copies src diagrams and multiply every value by the given scalar.
358  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
362  GUM_SCALAR gamma) {
363  if (this->isReduced__ != src.isReducedAndOrdered())
365  "Cannot copy a Reduced and Ordered "
366  "function graph into Tree function graph "
367  "(or vice-versa).")
368 
369  this->clear();
370 
371  // New variables insertion
373  src.variablesSequence().beginSafe();
374  varIter != src.variablesSequence().endSafe();
375  ++varIter)
376  this->add(**varIter);
377 
378  std::vector< NodeId > lifo;
380 
381  if (src.isTerminalNode(src.root()))
382  this->manager()->setRootNode(
383  this->manager()->addTerminalNode(gamma * src.nodeValue(src.root())));
384  else {
385  this->manager()->setRootNode(
386  this->manager()->addInternalNode(src.node(src.root())->nodeVar()));
387  src2dest.insert(src.root(), this->root());
388  lifo.push_back(src.root());
389  }
390 
391  // Depth-first exploration an copy
392  while (!lifo.empty()) {
393  NodeId currentSrcNodeId = lifo.back();
394  lifo.pop_back();
395 
396  const InternalNode* currentSrcNode = src.node(currentSrcNodeId);
397 
398  for (Idx index = 0; index < currentSrcNode->nbSons(); ++index) {
399  if (!src2dest.exists(currentSrcNode->son(index))) {
400  NodeId srcSonNodeId = currentSrcNode->son(index), destSonNodeId = 0;
401  if (src.isTerminalNode(srcSonNodeId)) {
402  destSonNodeId = this->manager()->addTerminalNode(
403  gamma * src.nodeValue(srcSonNodeId));
404  } else {
405  destSonNodeId =
406  this->manager()->addInternalNode(src.node(srcSonNodeId)->nodeVar());
407  lifo.push_back(srcSonNodeId);
408  }
409  src2dest.insert(srcSonNodeId, destSonNodeId);
410  }
411  this->manager()->setSon(src2dest[currentSrcNodeId],
412  index,
413  src2dest[currentSrcNode->son(index)]);
414  }
415  }
416 
417  manager()->clean();
418  }
419 
420  // Clears the function graph
421  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
423  model__.clear();
424  // Always discard the nodeId 0
425  model__.addNode();
426 
427  this->clearAllTerminalNodes();
428 
429  // Nodes cleaning
431  internalNodeMap__.begin();
432  nodeIter != internalNodeMap__.end();
433  ++nodeIter) {
434  delete nodeIter.val();
435  }
436  internalNodeMap__.clear();
437 
438  // Cleaning the list of nodes for each variables
440  varIter = var2NodeIdMap__.begin();
441  varIter != var2NodeIdMap__.end();
442  ++varIter) {
443  delete varIter.val();
444  }
445  var2NodeIdMap__.clear();
446 
448  this->variablesSequence().rbeginSafe();
449  varIter != this->variablesSequence().rendSafe();
450  --varIter) {
451  this->erase(**varIter);
452  }
453  }
454 
455 
456  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
457  INLINE std::string
459  bool withBackArcs) const {
460  std::stringstream output;
461  std::stringstream terminalStream;
462  std::stringstream nonTerminalStream;
463  std::stringstream arcstream;
464  // std::stringstream defaultarcstream;
465  output << std::endl << "digraph \" " << tableName__ << "\" {" << std::endl;
466 
467  terminalStream << "node [shape = box];" << std::endl;
468  nonTerminalStream << "node [shape = ellipse];" << std::endl;
469  std::string tab = " ";
470 
471  for (NodeGraphPart::NodeIterator nodeIter = model__.begin();
472  nodeIter != model__.end();
473  ++nodeIter)
474  if (*nodeIter != 0) {
475  if (this->isTerminalNode((NodeId)*nodeIter))
476  terminalStream << tab << *nodeIter << ";" << tab << *nodeIter
477  << " [label=\"" << *nodeIter << " - "
478  << std::setprecision(30)
479  << this->terminalNodeValue(*nodeIter) << "\"]"
480  << ";" << std::endl;
481  else {
482  InternalNode* currentNode = internalNodeMap__[*nodeIter];
483  nonTerminalStream << tab << *nodeIter << ";" << tab << *nodeIter
484  << " [label=\"" << *nodeIter << " - "
485  << currentNode->nodeVar()->name() << "\"]"
486  << ";" << std::endl;
487 
488  // if (arcMap_[*nodeIter] != NULL)
490  for (Idx sonIter = 0; sonIter < currentNode->nbSons(); ++sonIter) {
491  if (!sonMap.exists(currentNode->son(sonIter)))
492  sonMap.insert(currentNode->son(sonIter), new LinkedList< Idx >());
493  sonMap[currentNode->son(sonIter)]->addLink(sonIter);
494  }
495 
496  for (auto sonIter = sonMap.beginSafe(); sonIter != sonMap.endSafe();
497  ++sonIter) {
498  arcstream << tab << *nodeIter << " -> " << sonIter.key()
499  << " [label=\" ";
500  Link< Idx >* modaIter = sonIter.val()->list();
501  while (modaIter) {
502  arcstream << currentNode->nodeVar()->label(modaIter->element())
503  << ", ";
504  modaIter = modaIter->nextLink();
505  }
506  arcstream << "\",color=\"#0000ff\"]"
507  << ";" << std::endl;
508  delete sonIter.val();
509  }
510 
511  if (withBackArcs) {
512  Link< Parent >* parentIter = currentNode->parents();
513  while (parentIter != nullptr) {
514  arcstream << tab << *nodeIter << " -> "
515  << parentIter->element().parentId << " [label=\""
516  << parentIter->element().modality
517  << "\",color=\"#ff0000\"]"
518  << ";" << std::endl;
519  parentIter = parentIter->nextLink();
520  }
521  }
522  }
523  }
524 
525  output << terminalStream.str() << std::endl
526  << nonTerminalStream.str() << std::endl
527  << arcstream.str() << std::endl
528  << "}" << std::endl;
529 
530  return output.str();
531  }
532 
533  // Returns a const reference to the manager of this diagram
534  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
535  INLINE const NodeGraphPart&
537  return model__;
538  }
539 
540  // Returns a const reference to the manager of this diagram
541  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
544  if (manager__ == nullptr) {
545  if (isReduced__)
546  manager__ =
548  this);
549  else
550  manager__ =
552  this);
553  }
554  return manager__;
555  }
556 
557  // Returns the id of the root node from the diagram
558  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
559  INLINE const NodeId&
561  return root__;
562  }
563 
564  // Indicates if given node is terminal or not
565  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
566  INLINE bool
568  const NodeId& node) const {
569  return this->existsTerminalNodeWithId(node);
570  }
571 
572  // Indicates if given node is terminal or not
573  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
574  INLINE bool
576  const NodeId& node) const {
577  return this->internalNodeMap__.exists(node);
578  }
579 
580  // Returns value associated to given node.
581  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
582  INLINE const GUM_SCALAR&
584  NodeId n) const {
585  if (!isTerminalNode(n))
587  "Id " << n << " is not bound to any terminal node")
588  return this->terminalNodeValue(n);
589  }
590 
591  // Returns internalNode structure associated to that nodeId
592  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
593  INLINE const InternalNode*
595  NodeId n) const {
596  if (!isInternalNode(n))
598  "Id " << n << " is not bound to any terminal node")
599  return this->internalNodeMap__[n];
600  }
601 
602  // Returns the list of node associated to given variable
603  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
604  INLINE const LinkedList< NodeId >*
606  const DiscreteVariable* var) const {
607  if (!this->variablesSequence().exists(var))
609  "Var " << var->name()
610  << " has not been inserted in the function graph")
611  return var2NodeIdMap__[var];
612  }
613 
614  // Returns the name of the table represented by this structure.
615  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
616  INLINE const std::string&
618  return tableName__;
619  }
620 
621  // Sets the name of the table represented by this structure.
622  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
623  INLINE void
625  const std::string& name) {
626  tableName__ = name;
627  }
628 
629  // Returns true if this MultiDimFunctionGraph is reduced and Ordered.
630  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
631  INLINE bool
633  const {
634  return isReduced__;
635  }
636 
637  // Returns a reduced and ordered instance.
638  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
640  MultiDimFunctionGraph< GUM_SCALAR,
641  TerminalNodePolicy >::getReducedAndOrderedInstance() {
643  }
644 
645  // Returns an arborescent instance
646  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
650  }
651 
652  // Not implemented yet
653  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
655  const DiscreteVariable* x, const DiscreteVariable* y) {
656  GUM_ERROR(OperationNotAllowed, "Not Implemented Yet")
657  }
658 
659  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
661  const Instantiation& inst) const {
663  "You can't edit a function by other mean than the manager");
664  }
665 
666  // Return a data, given a Instantiation.
667  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
669  const Instantiation& inst) const {
670  NodeId currentNodeId = root__;
671  InternalNode* currentNode = nullptr;
672  while (!isTerminalNode(currentNodeId)) {
673  currentNode = internalNodeMap__[currentNodeId];
674  currentNodeId = currentNode->son(inst.val(*(currentNode->nodeVar())));
675  }
676  return this->terminalNodeValue(currentNodeId);
677  }
678 
679 } // namespace gum
void insert(const T1 &first, const T2 &second)
Inserts a new association in the gum::Bijection.
const T2 & second(const T1 &first) const
Returns the second value of a pair given its first value.
Safe iterators for Sequence.
Definition: sequence.h:1206
const iterator_safe & endSafe() noexcept
Returns the safe iterator pointing to the end of the hashtable.
const DiscreteVariable * nodeVar() const
Returns the node variable.
Idx nbSons() const
Returns the number of sons.
MultiDimFunctionGraph(bool isReduced=true)
Default constructor.
Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables...
Definition: hashTable.h:2750
NodeId son(Idx modality) const
Returns the son at a given index.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
const Key & key(const Key &key) const
Returns a reference on a given key.
virtual void erase(const DiscreteVariable &v)
Removes a var from the variables of the multidimensional matrix.
Link< Parent > * parents()
Returns the list of parents.
Base class for discrete random variable.
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
Definition: agrum.h:25
Abstract base class for all multi dimensionnal containers.
Idx val(Idx i) const
Returns the current value of the variable at position i.
bool existsFirst(const T1 &first) const
Returns true if first is the first element in a pair in the gum::Bijection.
Unsafe iterator on the node set of a graph.
Definition: nodeGraphPart.h:58
Class implementingting a function graph manager.
virtual std::string label(Idx i) const =0
get the indice-th label. This method is pure virtual.
Structure used to represent a node internal structure.
Definition: internalNode.h:102
Set of pairs of elements with fast search for both elements.
Definition: bijection.h:1805
Class implementingting a function graph.
Class for node sets in graph.
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
Class for assigning/browsing values to tuples of discrete variables.
Definition: instantiation.h:83
Chain list allocated using the SmallObjectAllocator.
Definition: link.h:134
iterator_safe beginSafe()
Returns the safe iterator pointing to the beginning of the hashtable.
<agrum/tools/multidim/multiDimImplementation.h>
Size Idx
Type for indexes.
Definition: types.h:53
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
const std::string & name() const
returns the name of the variable
Size NodeId
Type for node ids.
Definition: graphElements.h:98
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55
void clear()
Clears the function graph.