aGrUM  0.14.3
multiDimFunctionGraph_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
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  // Default constructor.
32  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
34  MultiDimFunctionGraph(bool isReduced) :
35  MultiDimImplementation< GUM_SCALAR >(),
36  __name("MultiDimFunctionGraph"), __tableName("NO NAME"), __model(500, true),
37  __manager(nullptr), __root(0), __internalNodeMap(500, true, false),
38  __var2NodeIdMap(500, true, false), __isReduced(isReduced) {
39  GUM_CONSTRUCTOR(MultiDimFunctionGraph);
40  __manager = nullptr;
41  // Pop up a first node so that id 0 is unavailable
42  __model.addNode();
43  }
44 
45  // Copy constructor.
46  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
50  MultiDimImplementation< GUM_SCALAR >(),
51  __name("MultiDimFunctionGraph"), __tableName("No NAME"), __model(500, true),
52  __manager(nullptr), __root(0), __internalNodeMap(500, true, false),
53  __var2NodeIdMap(500, true, false), __isReduced(from.isReducedAndOrdered()) {
54  GUM_CONS_CPY(MultiDimFunctionGraph);
55  copy(from);
56  }
57 
58  // Copy Operator.
59  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
63  copy(from);
64  return *this;
65  }
66 
67  // Destructor.
68  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
69  INLINE MultiDimFunctionGraph< GUM_SCALAR,
70  TerminalNodePolicy >::~MultiDimFunctionGraph() {
71  // Manager deletion
72  GUM_DESTRUCTOR(MultiDimFunctionGraph);
73  if (__manager != nullptr) delete __manager;
74  this->clear();
75  }
76 
77  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
80  if (__isReduced)
83  else
84  return MultiDimFunctionGraph< GUM_SCALAR,
85  TerminalNodePolicy >::getTreeInstance();
86  }
87 
88  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
89  INLINE const std::string&
91  return __name;
92  }
93 
94  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
96  const Instantiation& i, const GUM_SCALAR& value) const {
98  "Function Graph can't be edited so "
99  "easily.\nMultiDimFunctionGraphManager "
100  "provides the framework to edit a "
101  "Function Graph.")
102  }
103 
104  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
106  const GUM_SCALAR& d) const {
108  "Function Graph can't be edited so "
109  "easily.\nMultiDimFunctionGraphManager "
110  "provides the framework to edit a "
111  "Function Graph.")
112  }
113 
114  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
116  const std::vector< GUM_SCALAR >& v) const {
118  "Function Graph can't be edited so "
119  "easily.\nMultiDimFunctionGraphManager "
120  "provides the framework to editaa "
121  "Function Graph.")
122  }
123  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
125  std::initializer_list< GUM_SCALAR > l) const {
127  "Function Graph can't be edited so "
128  "easily.\nMultiDimFunctionGraphManager "
129  "provides the framework to edit a "
130  "Function Graph.")
131  }
132 
133  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
135  const DiscreteVariable& v) {
136  if (!this->variablesSequence().exists(&v))
138 
139  if (!this->__var2NodeIdMap.exists(&v))
140  __var2NodeIdMap.insert(&v, new LinkedList< NodeId >());
141  }
142 
143  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
145  const DiscreteVariable& v) {
146  if (this->__var2NodeIdMap.exists(&v)) {
147  while (__var2NodeIdMap[&v]->list() != nullptr) {
148  manager()->eraseNode(__var2NodeIdMap[&v]->list()->element());
149  }
150  delete __var2NodeIdMap[&v];
151  __var2NodeIdMap.erase(&v);
152  }
153 
154  if (this->variablesSequence().exists(&v))
156  }
157 
158  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
159  INLINE Size
161  return __internalNodeMap.size(); // + __valueMap.size();
162  }
163 
164 
165  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
166  INLINE void
168  const Instantiation& i,
169  const DiscreteVariable* const var,
170  Idx oldval,
171  Idx newval) {}
172 
173  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
174  INLINE void
176  const Instantiation& i) {}
177 
178  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
179  INLINE void
181  const Instantiation& i) {}
182 
183  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
184  INLINE void
186  const Instantiation& i) {}
187 
188  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
189  INLINE void
191  const Instantiation& i) {}
192 
193  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
196 
197  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
198  INLINE const std::string
200  const Instantiation* i) const {
201  std::stringstream sBuff;
202  sBuff << (*i) << " = " << this->get(*i);
203  return sBuff.str();
204  }
205 
206  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
208  const MultiDimContainer< GUM_SCALAR >& src, Instantiation* p_i) const {
210  "You cannot copy another type of multiDim "
211  "into a MultiDimFunctionGraph.");
212  }
213 
214  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
216  const MultiDimContainer< GUM_SCALAR >& src) {
218  "You cannot copy another type of multiDim "
219  "into a MultiDimFunctionGraph.");
220  }
221 
222  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
225  if (this->__isReduced != src.isReducedAndOrdered())
227  "Cannot copy a Reduced and Ordered "
228  "function graph into Tree function graph "
229  "(or vice-versa).")
230 
231  this->clear();
232 
233  // New variables insertion
235  src.variablesSequence().beginSafe();
236  varIter != src.variablesSequence().endSafe();
237  ++varIter)
238  this->add(**varIter);
239 
240  std::vector< NodeId > lifo;
242 
243  if (src.isTerminalNode(src.root()))
244  this->manager()->setRootNode(
245  this->manager()->addTerminalNode(src.nodeValue(src.root())));
246  else {
247  this->manager()->setRootNode(
248  this->manager()->addInternalNode(src.node(src.root())->nodeVar()));
249  src2dest.insert(src.root(), this->root());
250  lifo.push_back(src.root());
251  }
252 
253  // Depth-first exploration and copy
254  while (!lifo.empty()) {
255  NodeId currentSrcNodeId = lifo.back();
256  lifo.pop_back();
257 
258  const InternalNode* currentSrcNode = src.node(currentSrcNodeId);
259 
260  for (Idx index = 0; index < currentSrcNode->nbSons(); ++index) {
261  if (!src2dest.existsFirst(currentSrcNode->son(index))) {
262  NodeId srcSonNodeId = currentSrcNode->son(index), destSonNodeId = 0;
263  if (src.isTerminalNode(srcSonNodeId)) {
264  destSonNodeId =
265  this->manager()->addTerminalNode(src.nodeValue(srcSonNodeId));
266  } else {
267  destSonNodeId =
268  this->manager()->addInternalNode(src.node(srcSonNodeId)->nodeVar());
269  lifo.push_back(srcSonNodeId);
270  }
271  src2dest.insert(srcSonNodeId, destSonNodeId);
272  }
273  this->manager()->setSon(src2dest.second(currentSrcNodeId),
274  index,
275  src2dest.second(currentSrcNode->son(index)));
276  }
277  }
278 
279  manager()->clean();
280  }
281 
282  // Copies src diagrams structure into this diagrams.
283  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
284  INLINE void
288  reassign) {
289  if (this->__isReduced != src.isReducedAndOrdered())
291  "Cannot copy a Reduced and Ordered "
292  "function graph into Tree function graph "
293  "(or vice-versa).")
294 
295  this->clear();
296 
297  // New variables insertion
299  src.variablesSequence().beginSafe();
300  varIter != src.variablesSequence().endSafe();
301  ++varIter) {
302  if ((*varIter)->domainSize() != reassign.second(*varIter)->domainSize())
304  "Var " << (*varIter)->name() << " and var "
305  << reassign.second(*varIter)->name()
306  << " have different domain sizes ("
307  << (*varIter)->domainSize()
308  << "!=" << reassign.second(*varIter)->domainSize() << ")")
309  this->add(*(reassign.second(*varIter)));
310  }
311 
312  std::vector< NodeId > lifo;
314 
315  if (src.isTerminalNode(src.root())) {
316  this->manager()->setRootNode(
317  this->manager()->addTerminalNode(src.nodeValue(src.root())));
318  } else {
319  this->manager()->setRootNode(this->manager()->addInternalNode(
320  reassign.second(src.node(src.root())->nodeVar())));
321  src2dest.insert(src.root(), this->root());
322  lifo.push_back(src.root());
323  }
324 
325  // Depth-first exploration and copy
326  while (!lifo.empty()) {
327  NodeId currentSrcNodeId = lifo.back();
328  lifo.pop_back();
329 
330  const InternalNode* currentSrcNode = src.node(currentSrcNodeId);
331 
332  for (Idx index = 0; index < currentSrcNode->nbSons(); ++index) {
333  if (!src2dest.existsFirst(currentSrcNode->son(index))) {
334  NodeId srcSonNodeId = currentSrcNode->son(index), destSonNodeId = 0;
335  if (src.isTerminalNode(srcSonNodeId)) {
336  destSonNodeId =
337  this->manager()->addTerminalNode(src.nodeValue(srcSonNodeId));
338  } else {
339  destSonNodeId = this->manager()->addInternalNode(
340  reassign.second(src.node(srcSonNodeId)->nodeVar()));
341  lifo.push_back(srcSonNodeId);
342  }
343  src2dest.insert(srcSonNodeId, destSonNodeId);
344  }
345  this->manager()->setSon(src2dest.second(currentSrcNodeId),
346  index,
347  src2dest.second(currentSrcNode->son(index)));
348  }
349  }
350 
351  manager()->clean();
352  }
353 
354  // Copies src diagrams and multiply every value by the given scalar.
355  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
359  GUM_SCALAR gamma) {
360  if (this->__isReduced != src.isReducedAndOrdered())
362  "Cannot copy a Reduced and Ordered "
363  "function graph into Tree function graph "
364  "(or vice-versa).")
365 
366  this->clear();
367 
368  // New variables insertion
370  src.variablesSequence().beginSafe();
371  varIter != src.variablesSequence().endSafe();
372  ++varIter)
373  this->add(**varIter);
374 
375  std::vector< NodeId > lifo;
377 
378  if (src.isTerminalNode(src.root()))
379  this->manager()->setRootNode(
380  this->manager()->addTerminalNode(gamma * src.nodeValue(src.root())));
381  else {
382  this->manager()->setRootNode(
383  this->manager()->addInternalNode(src.node(src.root())->nodeVar()));
384  src2dest.insert(src.root(), this->root());
385  lifo.push_back(src.root());
386  }
387 
388  // Depth-first exploration an copy
389  while (!lifo.empty()) {
390  NodeId currentSrcNodeId = lifo.back();
391  lifo.pop_back();
392 
393  const InternalNode* currentSrcNode = src.node(currentSrcNodeId);
394 
395  for (Idx index = 0; index < currentSrcNode->nbSons(); ++index) {
396  if (!src2dest.exists(currentSrcNode->son(index))) {
397  NodeId srcSonNodeId = currentSrcNode->son(index), destSonNodeId = 0;
398  if (src.isTerminalNode(srcSonNodeId)) {
399  destSonNodeId = this->manager()->addTerminalNode(
400  gamma * src.nodeValue(srcSonNodeId));
401  } else {
402  destSonNodeId =
403  this->manager()->addInternalNode(src.node(srcSonNodeId)->nodeVar());
404  lifo.push_back(srcSonNodeId);
405  }
406  src2dest.insert(srcSonNodeId, destSonNodeId);
407  }
408  this->manager()->setSon(src2dest[currentSrcNodeId],
409  index,
410  src2dest[currentSrcNode->son(index)]);
411  }
412  }
413 
414  manager()->clean();
415  }
416 
417  // Clears the function graph
418  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
420  __model.clear();
421  // Always discard the nodeId 0
422  __model.addNode();
423 
424  this->clearAllTerminalNodes();
425 
426  // Nodes cleaning
428  __internalNodeMap.begin();
429  nodeIter != __internalNodeMap.end();
430  ++nodeIter) {
431  delete nodeIter.val();
432  }
433  __internalNodeMap.clear();
434 
435  // Cleaning the list of nodes for each variables
437  varIter = __var2NodeIdMap.begin();
438  varIter != __var2NodeIdMap.end();
439  ++varIter) {
440  delete varIter.val();
441  }
442  __var2NodeIdMap.clear();
443 
445  this->variablesSequence().rbeginSafe();
446  varIter != this->variablesSequence().rendSafe();
447  --varIter) {
448  this->erase(**varIter);
449  }
450  }
451 
452 
453  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
454  INLINE std::string
456  bool withBackArcs) const {
457  std::stringstream output;
458  std::stringstream terminalStream;
459  std::stringstream nonTerminalStream;
460  std::stringstream arcstream;
461  // std::stringstream defaultarcstream;
462  output << std::endl << "digraph \" " << __tableName << "\" {" << std::endl;
463 
464  terminalStream << "node [shape = box];" << std::endl;
465  nonTerminalStream << "node [shape = ellipse];" << std::endl;
466  std::string tab = " ";
467 
468  for (NodeGraphPart::NodeIterator nodeIter = __model.begin();
469  nodeIter != __model.end();
470  ++nodeIter)
471  if (*nodeIter != 0) {
472  if (this->isTerminalNode((NodeId)*nodeIter))
473  terminalStream << tab << *nodeIter << ";" << tab << *nodeIter
474  << " [label=\"" << *nodeIter << " - "
475  << std::setprecision(30)
476  << this->terminalNodeValue(*nodeIter) << "\"]"
477  << ";" << std::endl;
478  else {
479  InternalNode* currentNode = __internalNodeMap[*nodeIter];
480  nonTerminalStream << tab << *nodeIter << ";" << tab << *nodeIter
481  << " [label=\"" << *nodeIter << " - "
482  << currentNode->nodeVar()->name() << "\"]"
483  << ";" << std::endl;
484 
485  // if (_arcMap[*nodeIter] != NULL)
487  for (Idx sonIter = 0; sonIter < currentNode->nbSons(); ++sonIter) {
488  if (!sonMap.exists(currentNode->son(sonIter)))
489  sonMap.insert(currentNode->son(sonIter), new LinkedList< Idx >());
490  sonMap[currentNode->son(sonIter)]->addLink(sonIter);
491  }
492 
493  for (auto sonIter = sonMap.beginSafe(); sonIter != sonMap.endSafe();
494  ++sonIter) {
495  arcstream << tab << *nodeIter << " -> " << sonIter.key()
496  << " [label=\" ";
497  Link< Idx >* modaIter = sonIter.val()->list();
498  while (modaIter) {
499  arcstream << currentNode->nodeVar()->label(modaIter->element())
500  << ", ";
501  modaIter = modaIter->nextLink();
502  }
503  arcstream << "\",color=\"#0000ff\"]"
504  << ";" << std::endl;
505  delete sonIter.val();
506  }
507 
508  if (withBackArcs) {
509  Link< Parent >* parentIter = currentNode->parents();
510  while (parentIter != nullptr) {
511  arcstream << tab << *nodeIter << " -> "
512  << parentIter->element().parentId << " [label=\""
513  << parentIter->element().modality
514  << "\",color=\"#ff0000\"]"
515  << ";" << std::endl;
516  parentIter = parentIter->nextLink();
517  }
518  }
519  }
520  }
521 
522  output << terminalStream.str() << std::endl
523  << nonTerminalStream.str() << std::endl
524  << arcstream.str() << std::endl
525  << "}" << std::endl;
526 
527  return output.str();
528  }
529 
530  // Returns a const reference to the manager of this diagram
531  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
532  INLINE const NodeGraphPart&
534  return __model;
535  }
536 
537  // Returns a const reference to the manager of this diagram
538  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
541  if (__manager == nullptr) {
542  if (__isReduced)
543  __manager =
545  this);
546  else
547  __manager =
549  this);
550  }
551  return __manager;
552  }
553 
554  // Returns the id of the root node from the diagram
555  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
556  INLINE const NodeId&
558  return __root;
559  }
560 
561  // Indicates if given node is terminal or not
562  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
563  INLINE bool
565  const NodeId& node) const {
566  return this->existsTerminalNodeWithId(node);
567  }
568 
569  // Indicates if given node is terminal or not
570  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
571  INLINE bool
573  const NodeId& node) const {
574  return this->__internalNodeMap.exists(node);
575  }
576 
577  // Returns value associated to given node.
578  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
579  INLINE const GUM_SCALAR&
581  NodeId n) const {
582  if (!isTerminalNode(n))
584  "Id " << n << " is not bound to any terminal node")
585  return this->terminalNodeValue(n);
586  }
587 
588  // Returns internalNode structure associated to that nodeId
589  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
590  INLINE const InternalNode*
592  NodeId n) const {
593  if (!isInternalNode(n))
595  "Id " << n << " is not bound to any terminal node")
596  return this->__internalNodeMap[n];
597  }
598 
599  // Returns the list of node associated to given variable
600  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
601  INLINE const LinkedList< NodeId >*
603  const DiscreteVariable* var) const {
604  if (!this->variablesSequence().exists(var))
606  "Var " << var->name()
607  << " has not been inserted in the function graph")
608  return __var2NodeIdMap[var];
609  }
610 
611  // Returns the name of the table represented by this structure.
612  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
613  INLINE const std::string&
615  return __tableName;
616  }
617 
618  // Sets the name of the table represented by this structure.
619  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
620  INLINE void
622  const std::string& name) {
623  __tableName = name;
624  }
625 
626  // Returns true if this MultiDimFunctionGraph is reduced and Ordered.
627  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
628  INLINE bool
630  const {
631  return __isReduced;
632  }
633 
634  // Returns a reduced and ordered instance.
635  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
637  MultiDimFunctionGraph< GUM_SCALAR,
638  TerminalNodePolicy >::getReducedAndOrderedInstance() {
640  }
641 
642  // Returns an arborescent instance
643  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
647  }
648 
649  // Not implemented yet
650  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
652  const DiscreteVariable* x, const DiscreteVariable* y) {
653  GUM_ERROR(OperationNotAllowed, "Not Implemented Yet")
654  }
655 
656  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
658  const Instantiation& inst) const {
660  "You can't edit a function by other mean than the manager");
661  }
662 
663  // Return a data, given a Instantiation.
664  template < typename GUM_SCALAR, template < class > class TerminalNodePolicy >
666  const Instantiation& inst) const {
667  NodeId currentNodeId = __root;
668  InternalNode* currentNode = nullptr;
669  while (!isTerminalNode(currentNodeId)) {
670  currentNode = __internalNodeMap[currentNodeId];
671  currentNodeId = currentNode->son(inst.val(*(currentNode->nodeVar())));
672  }
673  return this->terminalNodeValue(currentNodeId);
674  }
675 
676 } // 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:1203
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:2747
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.
gum is the global namespace for all aGrUM entities
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:55
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:100
Set of pairs of elements with fast search for both elements.
Definition: bijection.h:1803
Class implementingting a function graph.
Class for node sets in graph.
Headers of MultiDimFunctionGraph.
Class for assigning/browsing values to tuples of discrete variables.
Definition: instantiation.h:80
Chain list allocated using the SmallObjectAllocator.
Definition: link.h:131
iterator_safe beginSafe()
Returns the safe iterator pointing to the beginning of the hashtable.
<agrum/multidim/multiDimImplementation.h>
Size Idx
Type for indexes.
Definition: types.h:50
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
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:97
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
void clear()
Clears the function graph.