aGrUM  0.13.2
BayesBall_tpl.h
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  ***************************************************************************/
25 namespace gum {
26 
27 
28  // update a set of potentials, keeping only those d-connected with
29  // query variables
30  template < typename GUM_SCALAR, template < typename > class TABLE >
31  void
33  const NodeSet& query,
34  const NodeSet& hardEvidence,
35  const NodeSet& softEvidence,
36  Set< const TABLE< GUM_SCALAR >* >& potentials) {
37  const DAG& dag = bn.dag();
38 
39  // create the marks (top = first and bottom = second)
41  marks.resize(dag.size());
42  const std::pair< bool, bool > empty_mark(false, false);
43 
47  for (const auto pot : potentials) {
48  const Sequence< const DiscreteVariable* >& vars = pot->variablesSequence();
49  for (const auto var : vars) {
50  const NodeId id = bn.nodeId(*var);
51  if (!node2potentials.exists(id)) {
52  node2potentials.insert(id, Set< const TABLE< GUM_SCALAR >* >());
53  }
54  node2potentials[id].insert(pot);
55  }
56  }
57 
58  // indicate that we will send the ball to all the query nodes (as children):
59  // in list nodes_to_visit, the first element is the next node to send the
60  // ball to and the Boolean indicates whether we shall reach it from one of
61  // its children (true) or from one parent (false)
62  List< std::pair< NodeId, bool > > nodes_to_visit;
63  for (const auto node : query) {
64  nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
65  }
66 
67  // perform the bouncing ball until __node2potentials becomes empty (which
68  // means that we have reached all the potentials and, therefore, those
69  // are d-connected to query) or until there is no node in the graph to send
70  // the ball to
71  while (!nodes_to_visit.empty() && !node2potentials.empty()) {
72  // get the next node to visit
73  NodeId node = nodes_to_visit.front().first;
74 
75  // if the marks of the node do not exist, create them
76  if (!marks.exists(node)) marks.insert(node, empty_mark);
77 
78  // if the node belongs to the query, update __node2potentials: remove all
79  // the potentials containing the node
80  if (node2potentials.exists(node)) {
81  auto& pot_set = node2potentials[node];
82  for (const auto pot : pot_set) {
83  const auto& vars = pot->variablesSequence();
84  for (const auto var : vars) {
85  const NodeId id = bn.nodeId(*var);
86  if (id != node) {
87  node2potentials[id].erase(pot);
88  if (node2potentials[id].empty()) { node2potentials.erase(id); }
89  }
90  }
91  }
92  node2potentials.erase(node);
93 
94  // if __node2potentials is empty, no need to go on: all the potentials
95  // are d-connected to the query
96  if (node2potentials.empty()) return;
97  }
98 
99 
100  // bounce the ball toward the neighbors
101  if (nodes_to_visit.front().second) { // visit from a child
102  nodes_to_visit.popFront();
103 
104  if (hardEvidence.exists(node)) { continue; }
105 
106  if (!marks[node].first) {
107  marks[node].first = true; // top marked
108  for (const auto par : dag.parents(node)) {
109  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
110  }
111  }
112 
113  if (!marks[node].second) {
114  marks[node].second = true; // bottom marked
115  for (const auto chi : dag.children(node)) {
116  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
117  }
118  }
119  } else { // visit from a parent
120  nodes_to_visit.popFront();
121 
122  const bool is_hard_evidence = hardEvidence.exists(node);
123  const bool is_evidence = is_hard_evidence || softEvidence.exists(node);
124 
125  if (is_evidence && !marks[node].first) {
126  marks[node].first = true;
127 
128  for (const auto par : dag.parents(node)) {
129  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
130  }
131  }
132 
133  if (!is_hard_evidence && !marks[node].second) {
134  marks[node].second = true;
135 
136  for (const auto chi : dag.children(node)) {
137  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
138  }
139  }
140  }
141  }
142 
143 
144  // here, all the potentials that belong to __node2potentials are d-separated
145  // from the query
146  for (const auto elt : node2potentials) {
147  for (const auto pot : elt.second) {
148  potentials.erase(pot);
149  }
150  }
151  }
152 
153 
154 } /* namespace gum */
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
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
const DAG & dag() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:61
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
void erase(const Key &key)
Removes a given element from the hash table.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
The generic class for storing (ordered) sequences of objects.
Definition: sequence.h:1019
static void relevantPotentials(const IBayesNet< GUM_SCALAR > &bn, const NodeSet &query, const NodeSet &hardEvidence, const NodeSet &softEvidence, Set< const TABLE< GUM_SCALAR > * > &potentials)
update a set of potentials, keeping only those d-connected with query variables given evidence ...
Definition: BayesBall_tpl.h:32
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
Class representing the minimal interface for Bayesian Network.
Definition: IBayesNet.h:59
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
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
bool empty() const noexcept
Indicates whether the hash table is empty.
virtual NodeId nodeId(const DiscreteVariable &var) const =0
Return id node from discrete var pointer.
Base class for dag.
Definition: DAG.h:98