aGrUM  0.16.0
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 44 of file dSeparation.h.

Constructor & Destructor Documentation

◆ dSeparation() [1/3]

INLINE gum::dSeparation::dSeparation ( )

default constructor

Definition at line 34 of file dSeparation_inl.h.

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

◆ dSeparation() [2/3]

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

copy constructor

Definition at line 38 of file dSeparation_inl.h.

38  {
39  GUM_CONS_CPY(dSeparation);
40  }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:34

◆ dSeparation() [3/3]

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

move constructor

Definition at line 44 of file dSeparation_inl.h.

44  {
45  GUM_CONS_MOV(dSeparation);
46  }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:34

◆ ~dSeparation()

INLINE gum::dSeparation::~dSeparation ( )

destructor

Definition at line 50 of file dSeparation_inl.h.

50 { GUM_DESTRUCTOR(dSeparation); }
gum::dSeparation::dSeparation
dSeparation()
default constructor
Definition: dSeparation_inl.h:34

Member Function Documentation

◆ operator=() [1/2]

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

copy operator

Definition at line 54 of file dSeparation_inl.h.

54  {
55  return *this;
56  }

◆ operator=() [2/2]

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

move operator

Definition at line 60 of file dSeparation_inl.h.

60 { 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 37 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().

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

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