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