aGrUM  0.20.3
a C++ library for (probabilistic) graphical models
List of all members
gum::dSeparation Class Reference
Bayesian networks » Inference Algorithms for Bayesian networks

the d-separation algorithm as described in Koller & Friedman (2009) More...

#include <dSeparation.h>

Public Member Functions

Constructors / Destructors
 dSeparation ()
 default constructor More...
 
 dSeparation (const dSeparation &from)
 copy constructor More...
 
 dSeparation (dSeparation &&from)
 move constructor More...
 
 ~dSeparation ()
 destructor More...
 
Operators
dSeparation & operator= (const dSeparation &from)
 copy operator More...
 
dSeparation & operator= (dSeparation &&from)
 move operator More...
 
Accessors / Modifiers
void requisiteNodes (const DAG &dag, const NodeSet &query, const NodeSet &hardEvidence, const NodeSet &softEvidence, NodeSet &requisite)
 Fill the 'requisite' nodeset with the requisite nodes in dag given a query and evidence. More...
 
template<typename GUM_SCALAR , template< typename > class TABLE>
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 More...
 

Detailed Description

the d-separation algorithm as described in Koller & Friedman (2009)

Definition at line 43 of file dSeparation.h.

Constructor & Destructor Documentation

◆ dSeparation() [1/3]

INLINE gum::dSeparation::dSeparation ( )

default constructor

Definition at line 33 of file dSeparation_inl.h.

References gum::Set< Key, Alloc >::emplace().

33  {
34  GUM_CONSTRUCTOR(dSeparation);
35  ;
36  }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:33
+ Here is the call graph for this function:

◆ dSeparation() [2/3]

INLINE gum::dSeparation::dSeparation ( const dSeparation &  from)

copy constructor

Definition at line 40 of file dSeparation_inl.h.

References gum::Set< Key, Alloc >::emplace().

40 { GUM_CONS_CPY(dSeparation); }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:33
+ Here is the call graph for this function:

◆ dSeparation() [3/3]

INLINE gum::dSeparation::dSeparation ( dSeparation &&  from)

move constructor

Definition at line 44 of file dSeparation_inl.h.

References gum::Set< Key, Alloc >::emplace().

44 { GUM_CONS_MOV(dSeparation); }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:33
+ Here is the call graph for this function:

◆ ~dSeparation()

INLINE gum::dSeparation::~dSeparation ( )

destructor

Definition at line 48 of file dSeparation_inl.h.

References gum::Set< Key, Alloc >::emplace().

48  {
49  GUM_DESTRUCTOR(dSeparation);
50  ;
51  }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:33
+ Here is the call graph for this function:

Member Function Documentation

◆ operator=() [1/2]

INLINE dSeparation & gum::dSeparation::operator= ( const dSeparation &  from)

copy operator

Definition at line 55 of file dSeparation_inl.h.

55 { return *this; }

◆ operator=() [2/2]

INLINE dSeparation & gum::dSeparation::operator= ( dSeparation &&  from)

move operator

Definition at line 59 of file dSeparation_inl.h.

59 { return *this; }

◆ relevantPotentials()

template<typename GUM_SCALAR , template< typename > class TABLE>
void gum::dSeparation::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 at line 36 of file dSeparation_tpl.h.

References gum::Set< Key, Alloc >::emplace().

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

◆ requisiteNodes()

void gum::dSeparation::requisiteNodes ( const DAG &  dag,
const NodeSet &  query,
const NodeSet &  hardEvidence,
const NodeSet &  softEvidence,
NodeSet &  requisite 
)

Fill the 'requisite' nodeset with the requisite nodes in dag given a query and evidence.

Requisite nodes are those that are d-connected to at least one of the query nodes given a set of hard and soft evidence

Definition at line 40 of file dSeparation.cpp.

References gum::Set< Key, Alloc >::emplace().

44  {
45  // for the moment, no node is requisite
46  requisite.clear();
47 
48  // mark the set of ancestors of the evidence
49  NodeSet ev_ancestors(dag.size());
50  {
51  List< NodeId > anc_to_visit;
52  for (const auto node: hardEvidence)
53  anc_to_visit.insert(node);
54  for (const auto node: softEvidence)
55  anc_to_visit.insert(node);
56  while (!anc_to_visit.empty()) {
57  const NodeId node = anc_to_visit.front();
58  anc_to_visit.popFront();
59 
60  if (!ev_ancestors.exists(node)) {
61  ev_ancestors.insert(node);
62  for (const auto par: dag.parents(node)) {
63  anc_to_visit.insert(par);
64  }
65  }
66  }
67  }
68 
69  // create the marks indicating that we have visited a node
70  NodeSet visited_from_child(dag.size());
71  NodeSet visited_from_parent(dag.size());
72 
73  // indicate that we will send the ball to all the query nodes (as children):
74  // in list nodes_to_visit, the first element is the next node to send the
75  // ball to and the Boolean indicates whether we shall reach it from one of
76  // its children (true) or from one parent (false)
77  List< std::pair< NodeId, bool > > nodes_to_visit;
78  for (const auto node: query) {
79  nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
80  }
81 
82  // perform the bouncing ball until there is no node in the graph to send
83  // the ball to
84  while (!nodes_to_visit.empty()) {
85  // get the next node to visit
86  const NodeId node = nodes_to_visit.front().first;
87  const bool direction = nodes_to_visit.front().second;
88  nodes_to_visit.popFront();
89 
90  // check if the node has not already been visited in the same direction
91  bool already_visited;
92  if (direction) {
93  already_visited = visited_from_child.exists(node);
94  if (!already_visited) { visited_from_child.insert(node); }
95  } else {
96  already_visited = visited_from_parent.exists(node);
97  if (!already_visited) { visited_from_parent.insert(node); }
98  }
99 
100  // if this is the first time we meet the node, then visit it
101  if (!already_visited) {
102  // mark the node as reachable if this is not a hard evidence
103  const bool is_hard_evidence = hardEvidence.exists(node);
104  if (!is_hard_evidence) { requisite.insert(node); }
105 
106  // bounce the ball toward the neighbors
107  if (direction && !is_hard_evidence) { // visit from a child
108  // visit the parents
109  for (const auto par: dag.parents(node)) {
110  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
111  }
112 
113  // visit the children
114  for (const auto chi: dag.children(node)) {
115  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
116  }
117  } else { // visit from a parent
118  if (!hardEvidence.exists(node)) {
119  // visit the children
120  for (const auto chi: dag.children(node)) {
121  nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
122  }
123  }
124  if (ev_ancestors.exists(node)) {
125  // visit the parents
126  for (const auto par: dag.parents(node)) {
127  nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
128  }
129  }
130  }
131  }
132  }
133  }
gum::NodeSet
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Definition: graphElements.h:374
gum::NodeId
Size NodeId
Type for node ids.
Definition: graphElements.h:97
gum::Set::insert
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:606
+ Here is the call graph for this function:
The documentation for this class was generated from the following files:
aGrUM 0.20.3
Mon Jun 7 2021 17:34:44
© PHW&CG&others - 2021
DoXyGeN 1.8.13