aGrUM  0.14.2
List of all members
gum::dSeparation Class Reference
Bayesian Networks » Inference Algorithms

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 41 of file dSeparation.h.

Constructor & Destructor Documentation

◆ dSeparation() [1/3]

INLINE gum::dSeparation::dSeparation ( )

default constructor

Definition at line 31 of file dSeparation_inl.h.

31 { GUM_CONSTRUCTOR(dSeparation); }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:31

◆ dSeparation() [2/3]

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

copy constructor

Definition at line 35 of file dSeparation_inl.h.

35  {
36  GUM_CONS_CPY(dSeparation);
37  }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:31

◆ dSeparation() [3/3]

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

move constructor

Definition at line 41 of file dSeparation_inl.h.

41  {
42  GUM_CONS_MOV(dSeparation);
43  }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:31

◆ ~dSeparation()

INLINE gum::dSeparation::~dSeparation ( )

destructor

Definition at line 47 of file dSeparation_inl.h.

47 { GUM_DESTRUCTOR(dSeparation); }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:31

Member Function Documentation

◆ operator=() [1/2]

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

copy operator

Definition at line 51 of file dSeparation_inl.h.

51  {
52  return *this;
53  }

◆ operator=() [2/2]

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

move operator

Definition at line 57 of file dSeparation_inl.h.

57 { 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 34 of file dSeparation_tpl.h.

References gum::ArcGraphPart::children(), gum::DAGmodel::dag(), gum::List< Val, Alloc >::empty(), gum::Set< Key, Alloc >::exists(), gum::List< Val, Alloc >::front(), gum::List< Val, Alloc >::insert(), gum::IBayesNet< GUM_SCALAR >::nodeId(), gum::ArcGraphPart::parents(), gum::List< Val, Alloc >::popFront(), and gum::NodeGraphPart::size().

39  {
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 
69  HashTable< NodeId, Set< const TABLE< GUM_SCALAR >* > > node2potentials;
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  }
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:610
+ 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 38 of file dSeparation.cpp.

References gum::ArcGraphPart::children(), gum::Set< Key, Alloc >::clear(), gum::List< Val, Alloc >::empty(), gum::Set< Key, Alloc >::exists(), gum::List< Val, Alloc >::front(), gum::Set< Key, Alloc >::insert(), gum::List< Val, Alloc >::insert(), gum::ArcGraphPart::parents(), gum::List< Val, Alloc >::popFront(), and gum::NodeGraphPart::size().

Referenced by gum::SamplingInference< GUM_SCALAR >::contextualize().

42  {
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  }
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:610
+ Here is the call graph for this function:
+ Here is the caller graph for this function:
The documentation for this class was generated from the following files:
aGrUM 0.14.2
Thu Feb 28 2019 14:11:23
© CG&PHW&others - LIP6 2005-2007-2012
DoXyGeN 1.8.13