aGrUM  0.13.2
dSeparation_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  ***************************************************************************/
28 namespace gum {
29 
30 
31  // update a set of potentials, keeping only those d-connected with
32  // query variables given evidence
33  template < typename GUM_SCALAR, template < typename > class TABLE >
35  const IBayesNet< GUM_SCALAR >& bn,
36  const NodeSet& query,
37  const NodeSet& hardEvidence,
38  const NodeSet& softEvidence,
39  Set< const TABLE< GUM_SCALAR >* >& potentials) {
40  const DAG& dag = bn.dag();
41 
42  // mark the set of ancestors of the evidence
43  NodeSet ev_ancestors(dag.size());
44  {
45  List< NodeId > anc_to_visit;
46  for (const auto node : hardEvidence)
47  anc_to_visit.insert(node);
48  for (const auto node : softEvidence)
49  anc_to_visit.insert(node);
50  while (!anc_to_visit.empty()) {
51  const NodeId node = anc_to_visit.front();
52  anc_to_visit.popFront();
53 
54  if (!ev_ancestors.exists(node)) {
55  ev_ancestors.insert(node);
56  for (const auto par : dag.parents(node)) {
57  anc_to_visit.insert(par);
58  }
59  }
60  }
61  }
62 
63  // create the marks indicating that we have visited a node
64  NodeSet visited_from_child(dag.size());
65  NodeSet visited_from_parent(dag.size());
66 
70  for (const auto pot : potentials) {
71  const Sequence< const DiscreteVariable* >& vars = pot->variablesSequence();
72  for (const auto var : vars) {
73  const NodeId id = bn.nodeId(*var);
74  if (!node2potentials.exists(id)) {
75  node2potentials.insert(id, Set< const TABLE< GUM_SCALAR >* >());
76  }
77  node2potentials[id].insert(pot);
78  }
79  }
80 
81  // indicate that we will send the ball to all the query nodes (as children):
82  // in list nodes_to_visit, the first element is the next node to send the
83  // ball to and the Boolean indicates whether we shall reach it from one of
84  // its children (true) or from one parent (false)
85  List< std::pair< NodeId, bool > > nodes_to_visit;
86  for (const auto node : query) {
87  nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
88  }
89 
90  // perform the bouncing ball until there is no node in the graph to send
91  // the ball to
92  while (!nodes_to_visit.empty() && !node2potentials.empty()) {
93  // get the next node to visit
94  const NodeId node = nodes_to_visit.front().first;
95  const bool direction = nodes_to_visit.front().second;
96  nodes_to_visit.popFront();
97 
98  // check if the node has not already been visited in the same direction
99  bool already_visited;
100  if (direction) {
101  already_visited = visited_from_child.exists(node);
102  if (!already_visited) { visited_from_child.insert(node); }
103  } else {
104  already_visited = visited_from_parent.exists(node);
105  if (!already_visited) { visited_from_parent.insert(node); }
106  }
107 
108  // if the node belongs to the query, update __node2potentials: remove all
109  // the potentials containing the node
110  if (node2potentials.exists(node)) {
111  auto& pot_set = node2potentials[node];
112  for (const auto pot : pot_set) {
113  const auto& vars = pot->variablesSequence();
114  for (const auto var : vars) {
115  const NodeId id = bn.nodeId(*var);
116  if (id != node) {
117  node2potentials[id].erase(pot);
118  if (node2potentials[id].empty()) { node2potentials.erase(id); }
119  }
120  }
121  }
122  node2potentials.erase(node);
123 
124  // if __node2potentials is empty, no need to go on: all the potentials
125  // are d-connected to the query
126  if (node2potentials.empty()) return;
127  }
128 
129  // if this is the first time we meet the node, then visit it
130  if (!already_visited) {
131  // mark the node as reachable if this is not a hard evidence
132  const bool is_hard_evidence = hardEvidence.exists(node);
133 
134  // bounce the ball toward the neighbors
135  if (direction && !is_hard_evidence) { // visit from a child
136  // visit the parents
137  for (const auto par : dag.parents(node)) {
138  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
139  }
140 
141  // visit the children
142  for (const auto chi : dag.children(node)) {
143  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
144  }
145  } else { // visit from a parent
146  if (!hardEvidence.exists(node)) {
147  // visit the children
148  for (const auto chi : dag.children(node)) {
149  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
150  }
151  }
152  if (ev_ancestors.exists(node)) {
153  // visit the parents
154  for (const auto par : dag.parents(node)) {
155  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
156  }
157  }
158  }
159  }
160  }
161 
162  // here, all the potentials that belong to __node2potentials are d-separated
163  // from the query
164  for (const auto elt : node2potentials) {
165  for (const auto pot : elt.second) {
166  potentials.erase(pot);
167  }
168  }
169  }
170 
171 
172 } /* 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
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
The generic class for storing (ordered) sequences of objects.
Definition: sequence.h:1019
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:607
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 ...
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
virtual NodeId nodeId(const DiscreteVariable &var) const =0
Return id node from discrete var pointer.
Base class for dag.
Definition: DAG.h:98