aGrUM  0.13.2
BayesBall.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Pierre-Henri WUILLEMIN et Christophe GONZALES *
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  ***************************************************************************/
26 
27 #ifdef GUM_NO_INLINE
29 #endif // GUM_NO_INLINE
30 
31 namespace gum {
32 
33  void BayesBall::requisiteNodes(const DAG& dag,
34  const NodeSet& query,
35  const NodeSet& hardEvidence,
36  const NodeSet& softEvidence,
37  NodeSet& requisite) {
38  // for the moment, no node is requisite
39  requisite.clear();
40 
41  // create the marks (top = first and bottom = second )
43  const std::pair< bool, bool > empty_mark(false, false);
44 
45  // indicate that we will send the ball to all the query nodes (as children):
46  // in list nodes_to_visit, the first element is the next node to send the
47  // ball to and the Boolean indicates whether we shall reach it from one of
48  // its children (true) or from one parent (false)
49  List< std::pair< NodeId, bool > > nodes_to_visit;
50  for (const auto node : query) {
51  nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
52  }
53 
54  // perform the bouncing ball until there is no node in the graph to send
55  // the ball to
56  while (!nodes_to_visit.empty()) {
57  // get the next node to visit
58  NodeId node = nodes_to_visit.front().first;
59 
60  // if the marks of the node do not exist, create them
61  if (!marks.exists(node)) marks.insert(node, empty_mark);
62 
63  // bounce the ball toward the neighbors
64  if (nodes_to_visit.front().second) { // visit from a child
65  nodes_to_visit.popFront();
66  requisite.insert(node);
67 
68  if (hardEvidence.exists(node)) { continue; }
69 
70  if (!marks[node].first) {
71  marks[node].first = true; // top marked
72  for (const auto par : dag.parents(node)) {
73  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
74  }
75  }
76 
77  if (!marks[node].second) {
78  marks[node].second = true; // bottom marked
79  for (const auto chi : dag.children(node)) {
80  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
81  }
82  }
83  } else { // visit from a parent
84  nodes_to_visit.popFront();
85 
86  const bool is_hard_evidence = hardEvidence.exists(node);
87  const bool is_evidence = is_hard_evidence || softEvidence.exists(node);
88 
89  if (is_evidence && !marks[node].first) {
90  marks[node].first = true;
91  requisite.insert(node);
92 
93  for (const auto par : dag.parents(node)) {
94  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
95  }
96  }
97 
98  if (!is_hard_evidence && !marks[node].second) {
99  marks[node].second = true;
100 
101  for (const auto chi : dag.children(node)) {
102  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
103  }
104  }
105  }
106  }
107  }
108 
109 } /* namespace gum */
Val & front() const
Returns a reference to first element of a list, if any.
Definition: list_tpl.h:1828
bool empty() const noexcept
Returns a boolean indicating whether the chained list is empty.
Definition: list_tpl.h:1967
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
The BayesBall algorithm (as described by Schachter).
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:607
Generic doubly linked lists.
Definition: list.h:369
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
void popFront()
Removes the first element of a List, if any.
Definition: list_tpl.h:1961
The class for generic Hash Tables.
Definition: hashTable.h:676
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
Size size() const
alias for sizeNodes
Val & insert(const Val &val)
Inserts a new element at the end of the chained list (alias of pushBack).
Definition: list_tpl.h:1616
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
Implementation of the BayesBall class.
void clear()
Removes all the elements, if any, from the set.
Definition: set_tpl.h:375
Base class for dag.
Definition: DAG.h:98
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
static void requisiteNodes(const DAG &dag, const NodeSet &query, const NodeSet &hardEvidence, const NodeSet &softEvidence, NodeSet &requisite)
Fill the &#39;requisite&#39; nodeset with the requisite nodes in dag given a query and evidence.
Definition: BayesBall.cpp:33