aGrUM  0.20.2
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 { GUM_CONSTRUCTOR(dSeparation); }
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 37 of file dSeparation_inl.h.

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

37  {
38  GUM_CONS_CPY(dSeparation);
39  }
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 43 of file dSeparation_inl.h.

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

43  {
44  GUM_CONS_MOV(dSeparation);
45  }
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 49 of file dSeparation_inl.h.

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

49 { GUM_DESTRUCTOR(dSeparation); }
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 53 of file dSeparation_inl.h.

53  {
54  return *this;
55  }

◆ 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().

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