aGrUM  0.20.3
a C++ library for (probabilistic) graphical models
influenceDiagram_tpl.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright (c) 2005-2021 by 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 Template implementation of InfluenceDiagram/InfluenceDiagram.h classes.
25  *
26  * @author Pierre-Henri WUILLEMIN(@LIP6) and Jean-Christophe MAGNAN and Christophe
27  * GONZALES(@AMU)
28  */
29 
30 #include <cstdio>
31 #include <iostream>
32 
33 #include <agrum/tools/variables/rangeVariable.h>
34 #include <agrum/tools/variables/labelizedVariable.h>
35 #include <agrum/tools/variables/discretizedVariable.h>
36 
37 #include <agrum/ID/influenceDiagram.h>
38 
39 namespace gum {
40  template < typename GUM_SCALAR >
41  NodeId build_node_for_ID(gum::InfluenceDiagram< GUM_SCALAR >& infdiag,
42  std::string node,
43  gum::Size default_domain_size) {
44  auto ds = default_domain_size;
45  long range_min = 0;
46  long range_max = long(ds) - 1;
47  std::vector< std::string > labels;
48  std::vector< GUM_SCALAR > ticks;
49  bool isUtil, isDeci, isChanc;
50  isUtil = false;
51  isDeci = false;
52  isChanc = false;
53 
54  switch (*(node.begin())) {
55  case '*':
56  isDeci = true;
57  node.erase(0, 1);
58  break;
59  case '$':
60  isUtil = true;
61  node.erase(0, 1);
62  break;
63  default:
64  isChanc = true;
65  }
66 
67  std::string name = node;
68  if (*(node.rbegin()) == ']') {
69  auto posBrack = node.find('[');
70  if (posBrack != std::string::npos) {
71  name = node.substr(0, posBrack);
72  const auto& s_args = node.substr(posBrack + 1, node.size() - posBrack - 2);
73  const auto& args = split(s_args, ",");
74  if (args.empty()) { // n[]
75  GUM_ERROR(InvalidArgument, "Empty range for variable " << node)
76  } else if (args.size() == 1) { // n[4]
77  ds = static_cast< Size >(std::stoi(args[0]));
78  range_min = 0;
79  range_max = long(ds) - 1;
80  } else if (args.size() == 2) { // n[5,10]
81  range_min = std::stol(args[0]);
82  range_max = std::stol(args[1]);
83  if (1 + range_max - range_min < 2) {
84  GUM_ERROR(InvalidArgument, "Invalid range for variable " << node)
85  }
86  ds = static_cast< Size >(1 + range_max - range_min);
87  } else { // n[3.14,5,10,12]
88  for (const auto& tick: args) {
89  ticks.push_back(static_cast< GUM_SCALAR >(std::strtod(tick.c_str(), nullptr)));
90  }
91  ds = static_cast< Size >(args.size() - 1);
92  }
93  }
94  } else if (*(node.rbegin()) == '}') { // node like "n{one|two|three}"
95  auto posBrack = node.find('{');
96  if (posBrack != std::string::npos) {
97  name = node.substr(0, posBrack);
98  labels = split(node.substr(posBrack + 1, node.size() - posBrack - 2), "|");
99  if (labels.size() < 2) { GUM_ERROR(InvalidArgument, "Not enough labels in node " << node) }
100  if (!hasUniqueElts(labels)) {
101  GUM_ERROR(InvalidArgument, "Duplicate labels in node " << node)
102  }
103  ds = static_cast< Size >(labels.size());
104  }
105  }
106 
107  if (ds == 0) {
108  GUM_ERROR(InvalidArgument, "No value for variable " << name << ".")
109  } else if (ds == 1) {
110  GUM_ERROR(InvalidArgument,
111  "Only one value for variable " << name << " (2 at least are needed).")
112  }
113 
114  // now we add the node in the BN
115  NodeId idVar;
116  try {
117  idVar = infdiag.idFromName(name);
118  } catch (gum::NotFound&) {
119  if (isChanc) {
120  if (!labels.empty()) {
121  idVar = infdiag.addChanceNode(LabelizedVariable(name, name, labels));
122  } else if (!ticks.empty()) {
123  idVar = infdiag.addChanceNode(DiscretizedVariable< GUM_SCALAR >(name, name, ticks));
124  } else {
125  idVar = infdiag.addChanceNode(RangeVariable(name, name, range_min, range_max));
126  }
127  } else if (isDeci) {
128  if (!labels.empty()) {
129  idVar = infdiag.addDecisionNode(LabelizedVariable(name, name, labels));
130  } else if (!ticks.empty()) {
131  idVar = infdiag.addDecisionNode(DiscretizedVariable< GUM_SCALAR >(name, name, ticks));
132  } else {
133  idVar = infdiag.addDecisionNode(RangeVariable(name, name, range_min, range_max));
134  }
135  } else if (isUtil) {
136  idVar = infdiag.addUtilityNode(LabelizedVariable(name, name, 1));
137  } else {
138  GUM_ERROR(FatalError,
139  "No type (chance, decision or utility) for the node '" << node << "'.")
140  }
141  }
142 
143  return idVar;
144  }
145 
146 
147  template < typename GUM_SCALAR >
148  InfluenceDiagram< GUM_SCALAR >
149  InfluenceDiagram< GUM_SCALAR >::fastPrototype(const std::string& dotlike, Size domainSize) {
150  gum::InfluenceDiagram< GUM_SCALAR > infdiag;
151 
152  for (const auto& chaine: split(dotlike, ";")) {
153  NodeId lastId = 0;
154  bool notfirst = false;
155  for (const auto& souschaine: split(chaine, "->")) {
156  bool forward = true;
157  for (const auto& node: split(souschaine, "<-")) {
158  auto idVar = build_node_for_ID(infdiag, node, domainSize);
159  if (notfirst) {
160  if (forward) {
161  infdiag.addArc(lastId, idVar);
162  forward = false;
163  } else {
164  infdiag.addArc(idVar, lastId);
165  }
166  } else {
167  notfirst = true;
168  forward = false;
169  }
170  lastId = idVar;
171  }
172  }
173  }
174 
175  for (const auto n: infdiag.nodes()) {
176  if (infdiag.isChanceNode(n))
177  infdiag.cpt(n).randomCPT();
178  else if (infdiag.isUtilityNode(n)) {
179  infdiag.utility(n).random().scale(50).translate(-10);
180  }
181  }
182 
183  infdiag.setProperty("name", "fastPrototype");
184  return infdiag;
185  }
186  // ===========================================================================
187  // Constructors / Destructors
188  // ===========================================================================
189 
190  /*
191  * Default constructor.
192  */
193  template < typename GUM_SCALAR >
194  INLINE InfluenceDiagram< GUM_SCALAR >::InfluenceDiagram() : DAGmodel() {
195  GUM_CONSTRUCTOR(InfluenceDiagram);
196  }
197 
198  /*
199  * Destructor.
200  */
201  template < typename GUM_SCALAR >
202  InfluenceDiagram< GUM_SCALAR >::~InfluenceDiagram() {
203  GUM_DESTRUCTOR(InfluenceDiagram);
204  removeTables_();
205  }
206 
207  /*
208  * Copy Constructor
209  */
210  template < typename GUM_SCALAR >
211  InfluenceDiagram< GUM_SCALAR >::InfluenceDiagram(const InfluenceDiagram< GUM_SCALAR >& source) {
212  GUM_CONS_CPY(InfluenceDiagram);
213  copyStructureAndTables_(source);
214  }
215 
216  /*
217  * Copy Operator
218  */
219  template < typename GUM_SCALAR >
220  InfluenceDiagram< GUM_SCALAR >&
221  InfluenceDiagram< GUM_SCALAR >::operator=(const InfluenceDiagram< GUM_SCALAR >& source) {
222  if (this != &source) {
223  clear();
224  // Copying tables and structure
225  copyStructureAndTables_(source);
226  }
227 
228  return *this;
229  }
230 
231  template < typename GUM_SCALAR >
232  void InfluenceDiagram< GUM_SCALAR >::InfluenceDiagram::clear() {
233  // Removing previous potentials
234  removeTables_();
235  _variableMap_.clear();
236  dag_.clear();
237  _potentialMap_.clear();
238  _utilityMap_.clear();
239  }
240 
241  /*
242  * Removing ancient table
243  */
244  template < typename GUM_SCALAR >
245  void InfluenceDiagram< GUM_SCALAR >::removeTables_() {
246  for (const auto node: dag_.nodes()) {
247  if (isChanceNode(node))
248  delete &cpt(node);
249  else if (isUtilityNode(node))
250  delete &utility(node);
251  }
252  }
253 
254  /*
255  * Copying tables from another influence diagram
256  */
257  template < typename GUM_SCALAR >
258  void InfluenceDiagram< GUM_SCALAR >::copyStructureAndTables_(
259  const InfluenceDiagram< GUM_SCALAR >& IDsource) {
260  for (auto node: IDsource.nodes()) {
261  if (IDsource.isChanceNode(node))
262  addChanceNode(IDsource.variable(node), node);
263  else if (IDsource.isUtilityNode(node))
264  addUtilityNode(IDsource.variable(node), node);
265  else // decision node
266  addDecisionNode(IDsource.variable(node), node);
267  }
268  // we add arc in the same order of the potentials
269  for (auto node: IDsource.nodes()) {
270  const auto& s = IDsource.variable(node).name();
271  if (IDsource.isChanceNode(node)) {
272  for (Idx par = 1; par <= IDsource.parents(node).size(); par++)
273  addArc(IDsource.cpt(node).variable(par).name(), s);
274  } else if (IDsource.isUtilityNode(node)) {
275  for (Idx par = 1; par <= IDsource.parents(node).size(); par++)
276  addArc(IDsource.utility(node).variable(par).name(), s);
277  } else { // decision node
278  // here the order does not depends on a Potential
279  for (NodeId par: IDsource.parents(node))
280  addArc(par, node);
281  }
282  }
283 
284  // Copying potentials
285  for (auto node: IDsource.nodes()) {
286  const auto& s = IDsource.variable(node).name();
287  if (IDsource.isChanceNode(node)) {
288  cpt(node).fillWith(IDsource.cpt(s));
289  } else if (IDsource.isUtilityNode(node)) {
290  utility(node).fillWith(IDsource.utility(s));
291  }
292  }
293  }
294 
295  template < typename GUM_SCALAR >
296  std::string InfluenceDiagram< GUM_SCALAR >::toDot() const {
297  std::stringstream output;
298  std::stringstream decisionNode;
299  std::stringstream utilityNode;
300  std::stringstream chanceNode;
301  std::stringstream arcstream;
302  output << "digraph \"";
303 
304  try {
305  output << this->property("name") << "\" {" << std::endl;
306  } catch (NotFound&) { output << "no_name\" {" << std::endl; }
307 
308  output << " node [bgcolor=\"#AAAAAA\", style=filled, height=0];" << std::endl;
309 
310  decisionNode << "node [shape = box];" << std::endl;
311 
312  utilityNode << "node [shape = hexagon, margin=0];" << std::endl;
313  chanceNode << "node [shape = ellipse];" << std::endl;
314  std::string tab = " ";
315 
316  for (const auto node: dag_.nodes()) {
317  if (isChanceNode(node))
318  chanceNode << tab << "\"" << node << "-" << variable(node).name() << "\""
319  << ";";
320  else if (isUtilityNode(node))
321  utilityNode << tab << "\"" << node << "-" << variable(node).name() << "\""
322  << ";";
323  else
324  decisionNode << tab << "\"" << node << "-" << variable(node).name() << "\""
325  << ";";
326 
327  if (dag_.children(node).size() > 0)
328  for (const auto chi: dag_.children(node)) {
329  arcstream << "\"" << node << "-" << variable(node).name() << "\""
330  << " -> "
331  << "\"" << chi << "-" << variable(chi).name() << "\"";
332  if (isDecisionNode(chi)) { arcstream << " [style=\"tapered, bold\"]"; }
333  arcstream << ";" << std::endl;
334  }
335  }
336 
337  output << decisionNode.str() << std::endl
338  << utilityNode.str() << std::endl
339  << chanceNode.str() << std::endl
340  << std::endl
341  << arcstream.str() << std::endl
342  << "}" << std::endl;
343 
344  return output.str();
345  }
346 
347  template < typename GUM_SCALAR >
348  std::string InfluenceDiagram< GUM_SCALAR >::toString() const {
349  std::stringstream output;
350 
351  output << "Influence Diagram{" << std::endl;
352  output << " chance: " << chanceNodeSize() << "," << std::endl;
353  output << " utility: " << utilityNodeSize() << "," << std::endl;
354  output << " decision: " << decisionNodeSize() << "," << std::endl;
355  output << " arcs: " << dag().sizeArcs() << "," << std::endl;
356 
357  double dSize = log10DomainSize();
358 
359  if (dSize > 6)
360  output << " domainSize: 10^" << dSize;
361  else
362  output << " domainSize: " << std::round(std::pow(10.0, dSize));
363 
364  output << std::endl << "}";
365 
366  return output.str();
367  }
368 
369  // ===========================================================================
370  // Variable manipulation methods.
371  // ===========================================================================
372 
373  /*
374  * Returns the CPT of a chance variable.
375  */
376  template < typename GUM_SCALAR >
377  INLINE const Potential< GUM_SCALAR >& InfluenceDiagram< GUM_SCALAR >::cpt(NodeId varId) const {
378  return *(_potentialMap_[varId]);
379  }
380 
381  /*
382  * Returns the utility table of a utility node.
383  */
384  template < typename GUM_SCALAR >
385  INLINE const Potential< GUM_SCALAR >&
386  InfluenceDiagram< GUM_SCALAR >::utility(NodeId varId) const {
387  return *(_utilityMap_[varId]);
388  }
389 
390  /*
391  * Return true if node is a utility one
392  */
393  template < typename GUM_SCALAR >
394  INLINE bool InfluenceDiagram< GUM_SCALAR >::isUtilityNode(NodeId varId) const {
395  return _utilityMap_.exists(varId);
396  }
397 
398  /*
399  * Return true if node is a utility one
400  */
401  template < typename GUM_SCALAR >
402  INLINE bool InfluenceDiagram< GUM_SCALAR >::isDecisionNode(NodeId varId) const {
403  bool ret = true;
404 
405  if (isUtilityNode(varId) || isChanceNode(varId)) ret = false;
406 
407  return ret;
408  }
409 
410  /*
411  * Return true if node is a chance one
412  */
413  template < typename GUM_SCALAR >
414  INLINE bool InfluenceDiagram< GUM_SCALAR >::isChanceNode(NodeId varId) const {
415  return _potentialMap_.exists(varId);
416  }
417 
418  /*
419  * Returns the number of utility nodes
420  */
421  template < typename GUM_SCALAR >
422  INLINE Size InfluenceDiagram< GUM_SCALAR >::utilityNodeSize() const {
423  return _utilityMap_.size();
424  }
425 
426  /*
427  * Returns the number of chance nodes
428  */
429  template < typename GUM_SCALAR >
430  INLINE Size InfluenceDiagram< GUM_SCALAR >::chanceNodeSize() const {
431  return _potentialMap_.size();
432  }
433 
434  /*
435  * Returns the number of decision nodes
436  */
437  template < typename GUM_SCALAR >
438  INLINE Size InfluenceDiagram< GUM_SCALAR >::decisionNodeSize() const {
439  return (size() - _utilityMap_.size() - _potentialMap_.size());
440  }
441 
442  /*
443  * Returns a constant reference to the VariableNodeMap of this Influence
444  * Diagram
445  */
446  template < typename GUM_SCALAR >
447  INLINE const VariableNodeMap& InfluenceDiagram< GUM_SCALAR >::variableNodeMap() const {
448  return _variableMap_;
449  }
450 
451  /*
452  * Returns a constant reference over a variable given it's node id.
453  */
454  template < typename GUM_SCALAR >
455  INLINE const DiscreteVariable& InfluenceDiagram< GUM_SCALAR >::variable(NodeId id) const {
456  return _variableMap_[id];
457  }
458 
459  /*
460  * Return id node from discrete var pointer.
461  */
462  template < typename GUM_SCALAR >
463  INLINE NodeId InfluenceDiagram< GUM_SCALAR >::nodeId(const DiscreteVariable& var) const {
464  return _variableMap_.get(var);
465  }
466 
467  // Getter by name
468  template < typename GUM_SCALAR >
469  INLINE NodeId InfluenceDiagram< GUM_SCALAR >::idFromName(const std::string& name) const {
470  return _variableMap_.idFromName(name);
471  }
472 
473  // Getter by name
474  template < typename GUM_SCALAR >
475  INLINE const DiscreteVariable&
476  InfluenceDiagram< GUM_SCALAR >::variableFromName(const std::string& name) const {
477  return _variableMap_.variableFromName(name);
478  }
479 
480  /*
481  * Add a chance variable, it's associate node and it's CPT. The id of the new
482  * variable is automatically generated.
483  */
484  template < typename GUM_SCALAR >
485  NodeId InfluenceDiagram< GUM_SCALAR >::add(const DiscreteVariable& var, NodeId varId) {
486  return addChanceNode(var, varId);
487  }
488 
489  /*
490  * Add a utility variable, it's associate node and it's UT. The id of the new
491  * variable is automatically generated.
492  * @Throws : Gum::InvalidArgument if var has more than one state
493  */
494  template < typename GUM_SCALAR >
495  NodeId InfluenceDiagram< GUM_SCALAR >::addUtilityNode(const DiscreteVariable& var, NodeId varId) {
496  auto newMultiDim = new MultiDimArray< GUM_SCALAR >();
497  NodeId res;
498 
499  try {
500  res = addUtilityNode(var, newMultiDim, varId);
501  } catch (Exception&) {
502  if (newMultiDim != nullptr) delete newMultiDim;
503  throw;
504  }
505 
506  return res;
507  }
508 
509  /*
510  * Add a decision variable. The id of the new
511  * variable is automatically generated.
512  */
513  template < typename GUM_SCALAR >
514  NodeId InfluenceDiagram< GUM_SCALAR >::addDecisionNode(const DiscreteVariable& var,
515  NodeId varId) {
516  return addNode_(var, varId);
517  }
518 
519  /*
520  * Add a chance variable, it's associate node and it's CPT. The id of the new
521  * variable is automatically generated.
522  */
523  template < typename GUM_SCALAR >
524  NodeId InfluenceDiagram< GUM_SCALAR >::addChanceNode(const DiscreteVariable& var, NodeId varId) {
525  auto newMultiDim = new MultiDimArray< GUM_SCALAR >();
526  NodeId res;
527 
528  try {
529  res = addChanceNode(var, newMultiDim, varId);
530  } catch (Exception&) {
531  delete newMultiDim;
532  throw;
533  }
534 
535  return res;
536  }
537 
538  /*
539  * Add a chance variable, it's associate node and it's CPT. The id of the new
540  * variable is automatically generated.
541  */
542  template < typename GUM_SCALAR >
543  NodeId
544  InfluenceDiagram< GUM_SCALAR >::addChanceNode(const DiscreteVariable& var,
545  MultiDimImplementation< GUM_SCALAR >* aContent,
546  NodeId DesiredId) {
547  NodeId proposedId = addNode_(var, DesiredId);
548 
549  auto varcpt = new Potential< GUM_SCALAR >(aContent);
550  (*varcpt) << variable(proposedId);
551  _potentialMap_.insert(proposedId, varcpt);
552 
553  return proposedId;
554  }
555 
556  /*
557  * Add a utility variable, it's associate node and it's UT. The id of the new
558  * variable is automatically generated.
559  * @Throws : Gum::InvalidArgument if var has more than one state
560  */
561  template < typename GUM_SCALAR >
562  NodeId
563  InfluenceDiagram< GUM_SCALAR >::addUtilityNode(const DiscreteVariable& var,
564  MultiDimImplementation< GUM_SCALAR >* aContent,
565  NodeId DesiredId) {
566  if (var.domainSize() != 1) {
567  GUM_ERROR(InvalidArgument,
568  "Utility var have no state ( which implicates a "
569  "single label for data output reasons ).")
570  }
571 
572  NodeId proposedId = addNode_(var, DesiredId);
573 
574  auto varut = new Potential< GUM_SCALAR >(aContent);
575 
576  (*varut) << variable(proposedId);
577 
578  _utilityMap_.insert(proposedId, varut);
579 
580  return proposedId;
581  }
582 
583  /*
584  * Add a node
585  */
586  template < typename GUM_SCALAR >
587  NodeId InfluenceDiagram< GUM_SCALAR >::addNode_(const DiscreteVariable& variableType,
588  NodeId DesiredId) {
589  // None thread safe code!
590  NodeId proposedId;
591 
592  if (DesiredId == 0)
593  proposedId = dag_.nextNodeId();
594  else
595  proposedId = DesiredId;
596 
597  _variableMap_.insert(proposedId, variableType);
598 
599  dag_.addNodeWithId(proposedId);
600 
601  // end critical section
602  return proposedId;
603  }
604 
605  /*
606  * Erase a Variable from the network and remove the variable from
607  * all children of id.
608  * If no variable matches the id, then nothing is done.
609  */
610  template < typename GUM_SCALAR >
611  void InfluenceDiagram< GUM_SCALAR >::erase(NodeId varId) {
612  if (_variableMap_.exists(varId)) {
613  // Reduce the variable child's CPT or Utility Table if necessary
614  for (const auto chi: dag_.children(varId))
615  if (isChanceNode(chi))
616  _potentialMap_[chi]->erase(variable(varId));
617  else if (isUtilityNode(chi))
618  _utilityMap_[chi]->erase(variable(varId));
619 
620  if (isChanceNode(varId)) {
621  delete _potentialMap_[varId];
622  _potentialMap_.erase(varId);
623  } else if (isUtilityNode(varId)) {
624  delete _utilityMap_[varId];
625  _utilityMap_.erase(varId);
626  }
627 
628  _variableMap_.erase(varId);
629  dag_.eraseNode(varId);
630  }
631  }
632 
633  /*
634  * Erase a Variable from the network and remove the variable from
635  * all children of var.
636  * If no variable matches, then nothing is done.
637  */
638  template < typename GUM_SCALAR >
639  INLINE void InfluenceDiagram< GUM_SCALAR >::erase(const DiscreteVariable& var) {
640  erase(_variableMap_.get(var));
641  }
642 
643  /* we allow the user to change the name of a variable
644  */
645  template < typename GUM_SCALAR >
646  INLINE void InfluenceDiagram< GUM_SCALAR >::changeVariableName(NodeId id,
647  const std::string& new_name) {
648  _variableMap_.changeName(id, new_name);
649  }
650 
651  // ===========================================================================
652  // @name Arc manipulation methods.
653  // ===========================================================================
654  /*
655  * Add an arc in the ID, and update diagram's chance nodes cpt if necessary.
656  */
657  template < typename GUM_SCALAR >
658  INLINE void InfluenceDiagram< GUM_SCALAR >::addArc(NodeId tail, NodeId head) {
659  if (isUtilityNode(tail)) { GUM_ERROR(InvalidArc, "Tail cannot be a utility node") }
660 
661  dag_.addArc(tail, head);
662 
663  if (isChanceNode(head))
664  // Add parent in the child's CPT
665  (*(_potentialMap_[head])) << variable(tail);
666  else if (isUtilityNode(head)) {
667  // Add parent in the child's UT
668  (*(_utilityMap_[head])) << variable(tail);
669  }
670  }
671 
672  /*
673  * Removes an arc in the ID, and update diagram chance nodes cpt if necessary.
674  *
675  * If (tail, head) doesn't exist, the nothing happens.
676  */
677  template < typename GUM_SCALAR >
678  INLINE void InfluenceDiagram< GUM_SCALAR >::eraseArc(const Arc& arc) {
679  if (dag_.existsArc(arc)) {
680  NodeId head = arc.head(), tail = arc.tail();
681  dag_.eraseArc(arc);
682 
683  if (isChanceNode(head))
684  // Removes parent in the child's CPT
685  (*(_potentialMap_[head])) >> variable(tail);
686  else if (isUtilityNode(head))
687  // Removes parent in the child's UT
688  (*(_utilityMap_[head])) >> variable(tail);
689  }
690  }
691 
692  /*
693  * Removes an arc in the ID, and update diagram chance nodes cpt if necessary.
694  *
695  * If (tail, head) doesn't exist, the nothing happens.
696  */
697  template < typename GUM_SCALAR >
698  INLINE void InfluenceDiagram< GUM_SCALAR >::eraseArc(NodeId tail, NodeId head) {
699  eraseArc(Arc(tail, head));
700  }
701 
702  // ===========================================================================
703  // Graphical methods
704  // ===========================================================================
705 
706  /*
707  * The node's id are coherent with the variables and nodes of the topology.
708  */
709  template < typename GUM_SCALAR >
710  void InfluenceDiagram< GUM_SCALAR >::moralGraph_(UndiGraph& graph) const {
711  for (const auto node: dag_.nodes())
712  if (!isUtilityNode(node)) graph.addNodeWithId(node);
713 
714  for (const auto node: dag_.nodes()) {
715  if (!isDecisionNode(node))
716  for (const auto par: dag_.parents(node)) {
717  if (isChanceNode(node)) graph.addEdge(node, par);
718 
719  for (const auto par2: dag_.parents(node))
720  if (par != par2) graph.addEdge(par, par2);
721  }
722  }
723  }
724 
725  /*
726  * True if a directed path exist with all decision nodes
727  */
728  template < typename GUM_SCALAR >
729  bool InfluenceDiagram< GUM_SCALAR >::decisionOrderExists() const {
730  const Sequence< NodeId >& order = topologicalOrder(true);
731 
732  // Finding first decision node
733  Sequence< NodeId >::const_iterator orderIter = order.begin();
734 
735  while ((orderIter != order.end()) && (!isDecisionNode(*orderIter)))
736  ++orderIter;
737 
738  if (orderIter == order.end()) return true;
739 
740  NodeId parentDecision = (*orderIter);
741  ++orderIter;
742 
743  // Checking path between decisions nodes
744  while (orderIter != order.end()) {
745  if (isDecisionNode(*orderIter)) {
746  if (!existsPathBetween(parentDecision, *orderIter)) return false;
747 
748  parentDecision = *orderIter;
749  }
750 
751  ++orderIter;
752  }
753 
754  return true;
755  }
756 
757  /*
758  * Returns true if a path exists between source and destination
759  */
760  template < typename GUM_SCALAR >
761  bool InfluenceDiagram< GUM_SCALAR >::existsPathBetween(NodeId src, NodeId dest) const {
762  List< NodeId > nodeFIFO;
763  // mark[node] contains 0 if not visited
764  // mark[node] = predecessor if visited
765  NodeProperty< int > mark = dag_.nodesProperty((int)-1);
766  NodeId current;
767 
768  mark[src] = (int)src;
769  nodeFIFO.pushBack(src);
770 
771  while (!nodeFIFO.empty()) {
772  current = nodeFIFO.front();
773  nodeFIFO.popFront();
774 
775  for (const auto new_one: dag_.children(current)) {
776  if (mark[new_one] != -1) continue; // if this node is already marked, continue
777 
778  mark[new_one] = (int)current;
779 
780  if (new_one == dest) break; // if we reach *orderIter, stop.
781 
782  nodeFIFO.pushBack(new_one);
783  }
784  }
785 
786  if (mark[dest] == -1) return false;
787 
788  return true;
789  }
790 
791  /*
792  * Returns the decision graph
793  */
794  template < typename GUM_SCALAR >
795  gum::DAG* InfluenceDiagram< GUM_SCALAR >::getDecisionGraph() const {
796  auto temporalGraph = new gum::DAG();
797 
798  for (const auto node: dag_.nodes()) {
799  if (isDecisionNode(node)) {
800  if (!temporalGraph->existsNode(node)) temporalGraph->addNodeWithId(node);
801 
802  for (const auto chi: getChildrenDecision_(node)) {
803  if (!temporalGraph->existsNode(chi)) temporalGraph->addNodeWithId(chi);
804 
805  temporalGraph->addArc(node, chi);
806  }
807  }
808  }
809 
810  return temporalGraph;
811  }
812 
813  /*
814  * Returns the list of children decision for a given nodeId
815  */
816  template < typename GUM_SCALAR >
817  Sequence< NodeId >
818  InfluenceDiagram< GUM_SCALAR >::getChildrenDecision_(NodeId parentDecision) const {
819  Sequence< NodeId > childrenSeq;
820 
821  List< NodeId > nodeFIFO;
822  NodeId current;
823 
824  // mark[node] contains false if not visited
825  // mark[node] contains true if visited
826  NodeProperty< bool > mark = dag_.nodesProperty(false);
827 
828  mark[parentDecision] = true;
829 
830  nodeFIFO.pushBack(parentDecision);
831 
832  while (!nodeFIFO.empty()) {
833  current = nodeFIFO.front();
834  nodeFIFO.popFront();
835 
836  for (const auto new_one: dag_.children(current)) {
837  if (mark[new_one]) continue; // if this node is already marked, continue
838 
839  mark[new_one] = true;
840 
841  if (!isDecisionNode(new_one))
842  nodeFIFO.pushBack(new_one);
843  else
844  childrenSeq.insert(new_one);
845  }
846  }
847 
848  return childrenSeq;
849  }
850 
851  /*
852  * Returns the sequence of decision nodes
853  * @throw NotFound if such a sequence does not exist
854  */
855  template < typename GUM_SCALAR >
856  std::vector< NodeId > InfluenceDiagram< GUM_SCALAR >::decisionOrder() const {
857  if (!decisionOrderExists()) { GUM_ERROR(NotFound, "No decision path exists") }
858 
859  std::vector< NodeId > decisionSequence;
860 
861  for (const auto elt: topologicalOrder(false))
862  if (isDecisionNode(elt)) decisionSequence.push_back(elt);
863 
864  return decisionSequence;
865  }
866 
867  /*
868  * Returns partial temporal ordering
869  * @throw NotFound if such a sequence does not exist
870  */
871  template < typename GUM_SCALAR >
872  const List< NodeSet >& InfluenceDiagram< GUM_SCALAR >::getPartialTemporalOrder(bool clear) const {
873  if (clear) {
874  _temporalOrder_.clear();
875 
876  std::vector< NodeId > order = decisionOrder();
877  NodeSet nodeList = dag_.asNodeSet();
878 
879  for (auto i: order) {
880  NodeSet partialOrderedSet;
881 
882  for (const auto par: dag_.parents(i)) {
883  if (nodeList.contains(par) && isChanceNode(par)) {
884  partialOrderedSet.insert(par);
885  nodeList.erase(par);
886  }
887  }
888 
889  if (!partialOrderedSet.empty()) _temporalOrder_.pushFront(partialOrderedSet);
890 
891  NodeSet decisionSet;
892 
893  decisionSet.insert(i);
894 
895  _temporalOrder_.pushFront(decisionSet);
896  }
897 
898  NodeSet lastSet; //= new gum::NodeSet();
899 
900  for (const auto node: nodeList)
901  if (isChanceNode(node)) lastSet.insert(node);
902 
903  if (!lastSet.empty()) _temporalOrder_.pushFront(lastSet);
904  }
905 
906  return _temporalOrder_;
907  }
908 } // namespace gum
aGrUM 0.20.3
Mon Jun 7 2021 17:33:54
© PHW&CG&others - 2021
DoXyGeN 1.8.13