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