aGrUM  0.13.2
dSeparation.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  ***************************************************************************/
28 #include <agrum/core/list.h>
29 
30 #ifdef GUM_NO_INLINE
32 #endif // GUM_NO_INLINE
33 
34 namespace gum {
35 
36  // Fill 'requisite' with the requisite nodes in dag given a query and
37  // evidence.
39  const NodeSet& query,
40  const NodeSet& hardEvidence,
41  const NodeSet& softEvidence,
42  NodeSet& requisite) {
43  // for the moment, no node is requisite
44  requisite.clear();
45 
46  // mark the set of ancestors of the evidence
47  NodeSet ev_ancestors(dag.size());
48  {
49  List< NodeId > anc_to_visit;
50  for (const auto node : hardEvidence)
51  anc_to_visit.insert(node);
52  for (const auto node : softEvidence)
53  anc_to_visit.insert(node);
54  while (!anc_to_visit.empty()) {
55  const NodeId node = anc_to_visit.front();
56  anc_to_visit.popFront();
57 
58  if (!ev_ancestors.exists(node)) {
59  ev_ancestors.insert(node);
60  for (const auto par : dag.parents(node)) {
61  anc_to_visit.insert(par);
62  }
63  }
64  }
65  }
66 
67  // create the marks indicating that we have visited a node
68  NodeSet visited_from_child(dag.size());
69  NodeSet visited_from_parent(dag.size());
70 
71  // indicate that we will send the ball to all the query nodes (as children):
72  // in list nodes_to_visit, the first element is the next node to send the
73  // ball to and the Boolean indicates whether we shall reach it from one of
74  // its children (true) or from one parent (false)
75  List< std::pair< NodeId, bool > > nodes_to_visit;
76  for (const auto node : query) {
77  nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
78  }
79 
80  // perform the bouncing ball until there is no node in the graph to send
81  // the ball to
82  while (!nodes_to_visit.empty()) {
83  // get the next node to visit
84  const NodeId node = nodes_to_visit.front().first;
85  const bool direction = nodes_to_visit.front().second;
86  nodes_to_visit.popFront();
87 
88  // check if the node has not already been visited in the same direction
89  bool already_visited;
90  if (direction) {
91  already_visited = visited_from_child.exists(node);
92  if (!already_visited) { visited_from_child.insert(node); }
93  } else {
94  already_visited = visited_from_parent.exists(node);
95  if (!already_visited) { visited_from_parent.insert(node); }
96  }
97 
98  // if this is the first time we meet the node, then visit it
99  if (!already_visited) {
100  // mark the node as reachable if this is not a hard evidence
101  const bool is_hard_evidence = hardEvidence.exists(node);
102  if (!is_hard_evidence) { requisite.insert(node); }
103 
104  // bounce the ball toward the neighbors
105  if (direction && !is_hard_evidence) { // visit from a child
106  // visit the parents
107  for (const auto par : dag.parents(node)) {
108  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
109  }
110 
111  // visit the children
112  for (const auto chi : dag.children(node)) {
113  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
114  }
115  } else { // visit from a parent
116  if (!hardEvidence.exists(node)) {
117  // visit the children
118  for (const auto chi : dag.children(node)) {
119  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
120  }
121  }
122  if (ev_ancestors.exists(node)) {
123  // visit the parents
124  for (const auto par : dag.parents(node)) {
125  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
126  }
127  }
128  }
129  }
130  }
131  }
132 
133 } /* 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
d-separation analysis (as described in Koller & Friedman 2009)
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
d-separation analysis (as described in Koller & Friedman 2009)
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
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
Generic class for manipulating lists.
Size size() const
alias for sizeNodes
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: dSeparation.cpp:38
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
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