aGrUM 3.2.0
a C++ library for (probabilistic) graphical models
gum::dSeparationAlgorithm Class Reference
Theoretical topics » Bayesian networks » Inference Algorithms for Bayesian networks

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

#include <dSeparationAlgorithm.h>

Public Member Functions

Constructors / Destructors
 dSeparationAlgorithm ()
 default constructor
 dSeparationAlgorithm (const dSeparationAlgorithm &from)
 copy constructor
 dSeparationAlgorithm (dSeparationAlgorithm &&from)
 move constructor
 ~dSeparationAlgorithm ()
 destructor
Operators
dSeparationAlgorithm & operator= (const dSeparationAlgorithm &from)
 copy operator
dSeparationAlgorithm & operator= (dSeparationAlgorithm &&from)
 move operator
Accessors / Modifiers
void requisiteNodes (const DAG &dag, const NodeSet &query, const NodeSet &hardEvidence, const NodeSet &softEvidence, NodeSet &requisite) const
 Fill the 'requisite' nodeset with the requisite nodes in dag given a query and evidence.
template<GUM_Numeric GUM_SCALAR, class TABLE>
void relevantTensors (const IBayesNet< GUM_SCALAR > &bn, const NodeSet &query, const NodeSet &hardEvidence, const NodeSet &softEvidence, Set< const TABLE * > &tensors)
 update a set of tensors, keeping only those d-connected with query variables given evidence

Detailed Description

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

Definition at line 63 of file dSeparationAlgorithm.h.

Constructor & Destructor Documentation

◆ dSeparationAlgorithm() [1/3]

gum::dSeparationAlgorithm::dSeparationAlgorithm ( )

default constructor

Definition at line 65 of file dSeparationAlgorithm.cpp.

65{ GUM_CONSTRUCTOR(dSeparationAlgorithm); }
gum::dSeparationAlgorithm::dSeparationAlgorithm
dSeparationAlgorithm()
default constructor
Definition dSeparationAlgorithm.cpp:65

References dSeparationAlgorithm().

Referenced by dSeparationAlgorithm(), dSeparationAlgorithm(), dSeparationAlgorithm(), ~dSeparationAlgorithm(), operator=(), and operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ dSeparationAlgorithm() [2/3]

gum::dSeparationAlgorithm::dSeparationAlgorithm ( const dSeparationAlgorithm & from)

copy constructor

Definition at line 68 of file dSeparationAlgorithm.cpp.

68 {
69 GUM_CONS_CPY(dSeparationAlgorithm);
70 }

References dSeparationAlgorithm().

Here is the call graph for this function:

◆ dSeparationAlgorithm() [3/3]

gum::dSeparationAlgorithm::dSeparationAlgorithm ( dSeparationAlgorithm && from)

move constructor

Definition at line 73 of file dSeparationAlgorithm.cpp.

73 {
74 GUM_CONS_MOV(dSeparationAlgorithm);
75 }

References dSeparationAlgorithm().

Here is the call graph for this function:

◆ ~dSeparationAlgorithm()

gum::dSeparationAlgorithm::~dSeparationAlgorithm ( )

destructor

Definition at line 78 of file dSeparationAlgorithm.cpp.

78{ GUM_DESTRUCTOR(dSeparationAlgorithm); }

References dSeparationAlgorithm().

Here is the call graph for this function:

Member Function Documentation

◆ operator=() [1/2]

dSeparationAlgorithm & gum::dSeparationAlgorithm::operator= ( const dSeparationAlgorithm & from)
default

copy operator

References dSeparationAlgorithm(), operator=(), relevantTensors(), and requisiteNodes().

Referenced by operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ operator=() [2/2]

dSeparationAlgorithm & gum::dSeparationAlgorithm::operator= ( dSeparationAlgorithm && from)

move operator

Definition at line 84 of file dSeparationAlgorithm.cpp.

84 {
85 return *this;
86 }

References dSeparationAlgorithm().

Here is the call graph for this function:

◆ relevantTensors()

template<GUM_Numeric GUM_SCALAR, class TABLE>
void gum::dSeparationAlgorithm::relevantTensors ( const IBayesNet< GUM_SCALAR > & bn,
const NodeSet & query,
const NodeSet & hardEvidence,
const NodeSet & softEvidence,
Set< const TABLE * > & tensors )

update a set of tensors, keeping only those d-connected with query variables given evidence

Definition at line 59 of file dSeparationAlgorithm_tpl.h.

63 {
64 const DAG& dag = bn.internalDag();
65
66 // mark the set of ancestors of the evidence
67 NodeSet ev_ancestors(dag.size());
68 {
69 List< NodeId > anc_to_visit;
70 for (const auto node: hardEvidence)
71 anc_to_visit.insert(node);
72 for (const auto node: softEvidence)
73 anc_to_visit.insert(node);
74 while (!anc_to_visit.empty()) {
75 const NodeId node = anc_to_visit.front();
76 anc_to_visit.popFront();
77
78 if (!ev_ancestors.exists(node)) {
79 ev_ancestors.insert(node);
80 for (const auto par: dag.parents(node)) {
81 anc_to_visit.insert(par);
82 }
83 }
84 }
85 }
86
87 // create the marks indicating that we have visited a node
88 NodeSet visited_from_child(dag.size());
89 NodeSet visited_from_parent(dag.size());
90
93 HashTable< NodeId, Set< const TABLE* > > node2tensors;
94 for (const auto pot: tensors) {
95 const Sequence< const DiscreteVariable* >& vars = pot->variablesSequence();
96 for (const auto var: vars) {
97 const NodeId id = bn.nodeId(*var);
98 if (!node2tensors.exists(id)) { node2tensors.insert(id, Set< const TABLE* >()); }
99 node2tensors[id].insert(pot);
100 }
101 }
102
103 // indicate that we will send the ball to all the query nodes (as children):
104 // in list nodes_to_visit, the first element is the next node to send the
105 // ball to and the Boolean indicates whether we shall reach it from one of
106 // its children (true) or from one parent (false)
107 List< std::pair< NodeId, bool > > nodes_to_visit;
108 for (const auto node: query) {
109 nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
110 }
111
112 // perform the bouncing ball until there is no node in the graph to send
113 // the ball to
114 while (!nodes_to_visit.empty() && !node2tensors.empty()) {
115 // get the next node to visit
116 const NodeId node = nodes_to_visit.front().first;
117 const bool direction = nodes_to_visit.front().second;
118 nodes_to_visit.popFront();
119
120 // check if the node has not already been visited in the same direction
121 bool already_visited;
122 if (direction) {
123 already_visited = visited_from_child.exists(node);
124 if (!already_visited) { visited_from_child.insert(node); }
125 } else {
126 already_visited = visited_from_parent.exists(node);
127 if (!already_visited) { visited_from_parent.insert(node); }
128 }
129
130 // if the node belongs to the query, update _node2tensors_: remove all
131 // the tensors containing the node
132 if (node2tensors.exists(node)) {
133 auto& pot_set = node2tensors[node];
134 for (const auto pot: pot_set) {
135 const auto& vars = pot->variablesSequence();
136 for (const auto var: vars) {
137 const NodeId id = bn.nodeId(*var);
138 if (id != node) {
139 node2tensors[id].erase(pot);
140 if (node2tensors[id].empty()) { node2tensors.erase(id); }
141 }
142 }
143 }
144 node2tensors.erase(node);
145
146 // if _node2tensors_ is empty, no need to go on: all the tensors
147 // are d-connected to the query
148 if (node2tensors.empty()) return;
149 }
150
151 // if this is the first time we meet the node, then visit it
152 if (!already_visited) {
153 // mark the node as reachable if this is not a hard evidence
154 const bool is_hard_evidence = hardEvidence.exists(node);
155
156 // bounce the ball toward the neighbors
157 if (direction && !is_hard_evidence) { // visit from a child
158 // visit the parents
159 for (const auto par: dag.parents(node)) {
160 nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
161 }
162
163 // visit the children
164 for (const auto chi: dag.children(node)) {
165 nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
166 }
167 } else { // visit from a parent
168 if (!hardEvidence.exists(node)) {
169 // visit the children
170 for (const auto chi: dag.children(node)) {
171 nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
172 }
173 }
174 if (ev_ancestors.exists(node)) {
175 // visit the parents
176 for (const auto par: dag.parents(node)) {
177 nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
178 }
179 }
180 }
181 }
182 }
183
184 // here, all the tensors that belong to _node2tensors_ are d-separated
185 // from the query
186 for (const auto& elt: node2tensors) {
187 for (const auto pot: elt.second) {
188 tensors.erase(pot);
189 }
190 }
191 }
gum::NodeId
Size NodeId
Type for node ids.
Definition graphElements.h:117
gum::NodeSet
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Definition graphElements.h:392

References gum::ArcGraphPart::children(), gum::HashTable< Key, Val >::empty(), gum::List< Val >::empty(), gum::HashTable< Key, Val >::erase(), gum::Set< Key >::erase(), gum::HashTable< Key, Val >::exists(), gum::Set< Key >::exists(), gum::List< Val >::front(), gum::HashTable< Key, Val >::insert(), gum::List< Val >::insert(), gum::Set< Key >::insert(), gum::DAGmodel::internalDag(), gum::DiscreteGraphicalModel::nodeId(), gum::ArcGraphPart::parents(), gum::List< Val >::popFront(), and gum::NodeGraphPart::size().

Referenced by operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ requisiteNodes()

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

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 90 of file dSeparationAlgorithm.cpp.

94 {
95 // for the moment, no node is requisite
96 requisite.clear();
97
98 // mark the set of ancestors of the evidence
99 NodeSet ev_ancestors(dag.size());
100 {
101 List< NodeId > anc_to_visit;
102 for (const auto node: hardEvidence)
103 anc_to_visit.insert(node);
104 for (const auto node: softEvidence)
105 anc_to_visit.insert(node);
106 while (!anc_to_visit.empty()) {
107 const NodeId node = anc_to_visit.front();
108 anc_to_visit.popFront();
109
110 if (!ev_ancestors.exists(node)) {
111 ev_ancestors.insert(node);
112 for (const auto par: dag.parents(node)) {
113 anc_to_visit.insert(par);
114 }
115 }
116 }
117 }
118
119 // create the marks indicating that we have visited a node
120 NodeSet visited_from_child(dag.size());
121 NodeSet visited_from_parent(dag.size());
122
123 // indicate that we will send the ball to all the query nodes (as children):
124 // in list nodes_to_visit, the first element is the next node to send the
125 // ball to and the Boolean indicates whether we shall reach it from one of
126 // its children (true) or from one parent (false)
127 List< std::pair< NodeId, bool > > nodes_to_visit;
128 for (const auto node: query) {
129 nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
130 }
131
132 // perform the bouncing ball until there is no node in the graph to send
133 // the ball to
134 while (!nodes_to_visit.empty()) {
135 // get the next node to visit
136 const NodeId node = nodes_to_visit.front().first;
137 const bool direction = nodes_to_visit.front().second;
138 nodes_to_visit.popFront();
139
140 // check if the node has not already been visited in the same direction
141 bool already_visited;
142 if (direction) {
143 already_visited = visited_from_child.exists(node);
144 if (!already_visited) { visited_from_child.insert(node); }
145 } else {
146 already_visited = visited_from_parent.exists(node);
147 if (!already_visited) { visited_from_parent.insert(node); }
148 }
149
150 // if this is the first time we meet the node, then visit it
151 if (!already_visited) {
152 // mark the node as reachable if this is not a hard evidence
153 const bool is_hard_evidence = hardEvidence.exists(node);
154 if (!is_hard_evidence) { requisite.insert(node); }
155
156 // bounce the ball toward the neighbors
157 if (direction && !is_hard_evidence) { // visit from a child
158 // visit the parents
159 for (const auto par: dag.parents(node)) {
160 nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
161 }
162
163 // visit the children
164 for (const auto chi: dag.children(node)) {
165 nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
166 }
167 } else { // visit from a parent
168 if (!hardEvidence.exists(node)) {
169 // visit the children
170 for (const auto chi: dag.children(node)) {
171 nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
172 }
173 }
174 if (ev_ancestors.exists(node)) {
175 // visit the parents
176 for (const auto par: dag.parents(node)) {
177 nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
178 }
179 }
180 }
181 }
182 }
183 }

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

Referenced by gum::SamplingInference< GUM_SCALAR >::contextualize(), and operator=().

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: