aGrUM 3.1.1
a C++ library for (probabilistic) graphical models
gum::dSeparationAlgorithm Class Reference
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]

INLINE gum::dSeparationAlgorithm::dSeparationAlgorithm ( )

default constructor

Definition at line 56 of file dSeparationAlgorithm_inl.h.

56 {
57 GUM_CONSTRUCTOR(dSeparationAlgorithm);
58 ;
59 }
gum::dSeparationAlgorithm::dSeparationAlgorithm
dSeparationAlgorithm()
default constructor
Definition dSeparationAlgorithm_inl.h:56

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]

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

copy constructor

Definition at line 62 of file dSeparationAlgorithm_inl.h.

62 {
63 GUM_CONS_CPY(dSeparationAlgorithm);
64 }

References dSeparationAlgorithm().

Here is the call graph for this function:

◆ dSeparationAlgorithm() [3/3]

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

move constructor

Definition at line 67 of file dSeparationAlgorithm_inl.h.

67 {
68 GUM_CONS_MOV(dSeparationAlgorithm);
69 }

References dSeparationAlgorithm().

Here is the call graph for this function:

◆ ~dSeparationAlgorithm()

INLINE gum::dSeparationAlgorithm::~dSeparationAlgorithm ( )

destructor

Definition at line 72 of file dSeparationAlgorithm_inl.h.

72 {
73 GUM_DESTRUCTOR(dSeparationAlgorithm);
74 ;
75 }

References dSeparationAlgorithm().

Here is the call graph for this function:

Member Function Documentation

◆ operator=() [1/2]

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

copy operator

References dSeparationAlgorithm().

Here is the call graph for this function:

◆ operator=() [2/2]

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

move operator

Definition at line 82 of file dSeparationAlgorithm_inl.h.

82 {
83 return *this;
84 }

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

Here is the call 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 60 of file dSeparationAlgorithm.cpp.

64 {
65 // for the moment, no node is requisite
66 requisite.clear();
67
68 // mark the set of ancestors of the evidence
69 NodeSet ev_ancestors(dag.size());
70 {
71 List< NodeId > anc_to_visit;
72 for (const auto node: hardEvidence)
73 anc_to_visit.insert(node);
74 for (const auto node: softEvidence)
75 anc_to_visit.insert(node);
76 while (!anc_to_visit.empty()) {
77 const NodeId node = anc_to_visit.front();
78 anc_to_visit.popFront();
79
80 if (!ev_ancestors.exists(node)) {
81 ev_ancestors.insert(node);
82 for (const auto par: dag.parents(node)) {
83 anc_to_visit.insert(par);
84 }
85 }
86 }
87 }
88
89 // create the marks indicating that we have visited a node
90 NodeSet visited_from_child(dag.size());
91 NodeSet visited_from_parent(dag.size());
92
93 // indicate that we will send the ball to all the query nodes (as children):
94 // in list nodes_to_visit, the first element is the next node to send the
95 // ball to and the Boolean indicates whether we shall reach it from one of
96 // its children (true) or from one parent (false)
97 List< std::pair< NodeId, bool > > nodes_to_visit;
98 for (const auto node: query) {
99 nodes_to_visit.insert(std::pair< NodeId, bool >(node, true));
100 }
101
102 // perform the bouncing ball until there is no node in the graph to send
103 // the ball to
104 while (!nodes_to_visit.empty()) {
105 // get the next node to visit
106 const NodeId node = nodes_to_visit.front().first;
107 const bool direction = nodes_to_visit.front().second;
108 nodes_to_visit.popFront();
109
110 // check if the node has not already been visited in the same direction
111 bool already_visited;
112 if (direction) {
113 already_visited = visited_from_child.exists(node);
114 if (!already_visited) { visited_from_child.insert(node); }
115 } else {
116 already_visited = visited_from_parent.exists(node);
117 if (!already_visited) { visited_from_parent.insert(node); }
118 }
119
120 // if this is the first time we meet the node, then visit it
121 if (!already_visited) {
122 // mark the node as reachable if this is not a hard evidence
123 const bool is_hard_evidence = hardEvidence.exists(node);
124 if (!is_hard_evidence) { requisite.insert(node); }
125
126 // bounce the ball toward the neighbors
127 if (direction && !is_hard_evidence) { // visit from a child
128 // visit the parents
129 for (const auto par: dag.parents(node)) {
130 nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
131 }
132
133 // visit the children
134 for (const auto chi: dag.children(node)) {
135 nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
136 }
137 } else { // visit from a parent
138 if (!hardEvidence.exists(node)) {
139 // visit the children
140 for (const auto chi: dag.children(node)) {
141 nodes_to_visit.insert(std::pair< NodeId, bool >(chi, false));
142 }
143 }
144 if (ev_ancestors.exists(node)) {
145 // visit the parents
146 for (const auto par: dag.parents(node)) {
147 nodes_to_visit.insert(std::pair< NodeId, bool >(par, true));
148 }
149 }
150 }
151 }
152 }
153 }

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

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 3.1.1

© PHW&CG&others - 2022
DoXyGeN 1.16.1