aGrUM
3.3.2
a C++ library for (probabilistic) graphical models
Toggle main menu visibility
bayesBall_tpl.h
Go to the documentation of this file.
1
/****************************************************************************
2
* This file is part of the aGrUM/pyAgrum library. *
3
* *
4
* Copyright (c) 2005-2026 by *
5
* - Pierre-Henri WUILLEMIN(_at_LIP6) *
6
* - Christophe GONZALES(_at_AMU) *
7
* *
8
* The aGrUM/pyAgrum library is free software; you can redistribute it *
9
* and/or modify it under the terms of either : *
10
* *
11
* - the GNU Lesser General Public License as published by *
12
* the Free Software Foundation, either version 3 of the License, *
13
* or (at your option) any later version, *
14
* - the MIT license (MIT), *
15
* - or both in dual license, as here. *
16
* *
17
* (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18
* *
19
* This aGrUM/pyAgrum library is distributed in the hope that it will be *
20
* useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21
* INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22
* FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26
* OTHER DEALINGS IN THE SOFTWARE. *
27
* *
28
* See LICENCES for more details. *
29
* *
30
* SPDX-FileCopyrightText: Copyright 2005-2026 *
31
* - Pierre-Henri WUILLEMIN(_at_LIP6) *
32
* - Christophe GONZALES(_at_AMU) *
33
* SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34
* *
35
* Contact : info_at_agrum_dot_org *
36
* homepage : http://agrum.gitlab.io *
37
* gitlab : https://gitlab.com/agrumery/agrum *
38
* *
39
****************************************************************************/
40
41
42
#pragma once
43
44
#include <
agrum/base/graphs/algorithms/generic/bayesBall.h
>
45
46
namespace
gum::graph
{
47
48
template
< GUM_DiGraphable G,
bool
CollectAll >
49
NodeSet
50
_bayesBall_
(
const
G& g,
const
NodeSet
& query,
const
NodeSet
& Zhard,
const
NodeSet
& Zsoft) {
51
NodeSet
result;
52
53
static
constexpr
std::pair< bool, bool > empty_mark{
false
,
false
};
54
NodeProperty< std::pair< bool, bool >
> marks(g.size());
55
56
List< std::pair< NodeId, bool >
> to_visit;
57
for
(
const
auto
node: query)
58
to_visit.
insert
(std::pair{node,
true
});
59
60
while
(!to_visit.
empty
()) {
61
const
NodeId
node = to_visit.
front
().first;
62
const
bool
from_child = to_visit.
front
().second;
63
to_visit.
popFront
();
64
65
auto
& [top, bot] = marks.
getWithDefault
(node, empty_mark);
66
67
if
(from_child) {
68
result.
insert
(node);
// always requisite on upward visit
69
if
(Zhard.
exists
(node))
continue
;
// hard evidence blocks upward
70
71
if
(!top) {
72
top =
true
;
73
for
(
const
auto
par: g.parents(node))
74
to_visit.
insert
(std::pair{par,
true
});
75
}
76
if
(!bot) {
77
bot =
true
;
78
for
(
const
auto
chi: g.children(node))
79
to_visit.
insert
(std::pair{chi,
false
});
80
}
81
82
}
else
{
83
if
constexpr
(CollectAll) result.
insert
(node);
// dConnected: all visits
84
85
const
bool
is_hard = Zhard.
exists
(node);
86
const
bool
is_ev = is_hard || Zsoft.
exists
(node);
87
88
if
(is_ev && !top) {
89
top =
true
;
90
if
constexpr
(!CollectAll) result.
insert
(node);
// requisiteNodes: collider only
91
for
(
const
auto
par: g.parents(node))
92
to_visit.
insert
(std::pair{par,
true
});
93
}
94
if
(!is_hard && !bot) {
95
bot =
true
;
96
for
(
const
auto
chi: g.children(node))
97
to_visit.
insert
(std::pair{chi,
false
});
98
}
99
}
100
}
101
102
return
result;
103
}
104
105
template
< GUM_DiGraphable G >
106
NodeSet
107
requisiteNodes
(
const
G& g,
const
NodeSet
& query,
const
NodeSet
& Zhard,
const
NodeSet
& Zsoft) {
108
return
_bayesBall_< G, false >
(g, query, Zhard, Zsoft);
109
}
110
111
template
< GUM_DiGraphable G >
112
NodeSet
dConnected
(
const
G& g,
const
NodeSet
& query,
const
NodeSet
& Zhard,
const
NodeSet
& Zsoft) {
113
return
_bayesBall_< G, true >
(g, query, Zhard, Zsoft);
114
}
115
116
}
// namespace gum::graph
bayesBall.h
Generic Bayes Ball algorithm (Shachter 1998) for directed graphs.
gum::HashTable::getWithDefault
mapped_type & getWithDefault(const Key &key, const Val &default_value)
Returns a reference on the element the key of which is passed in argument.
Definition
hashTable_tpl.h:796
gum::List
Generic doubly linked lists.
Definition
list.h:378
gum::List::front
Val & front() const
Returns a reference to first element of a list, if any.
Definition
list_tpl.h:1694
gum::List::insert
Val & insert(const Val &val)
Inserts a new element at the end of the chained list (alias of pushBack).
Definition
list_tpl.h:1508
gum::List::empty
bool empty() const noexcept
Returns a boolean indicating whether the chained list is empty.
Definition
list_tpl.h:1822
gum::List::popFront
void popFront()
Removes the first element of a List, if any.
Definition
list_tpl.h:1816
gum::Set::exists
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition
set_tpl.h:504
gum::Set::insert
void insert(const Key &k)
Inserts a new element into the set.
Definition
set_tpl.h:510
gum::NodeId
Size NodeId
Type for node ids.
Definition
graphElements.h:117
gum::NodeProperty
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Definition
graphElements.h:407
gum::NodeSet
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
Definition
graphElements.h:392
gum::graph
Definition
bayesBall.h:79
gum::graph::_bayesBall_
NodeSet _bayesBall_(const G &g, const NodeSet &query, const NodeSet &Zhard, const NodeSet &Zsoft)
Definition
bayesBall_tpl.h:50
gum::graph::requisiteNodes
NodeSet requisiteNodes(const G &g, const NodeSet &query, const NodeSet &Zhard=NodeSet(), const NodeSet &Zsoft=NodeSet())
Returns the Shachter-requisite nodes for query given evidence.
Definition
bayesBall_tpl.h:107
gum::graph::dConnected
NodeSet dConnected(const G &g, const NodeSet &query, const NodeSet &Zhard=NodeSet(), const NodeSet &Zsoft=NodeSet())
Returns all nodes d-connected to query given evidence.
Definition
bayesBall_tpl.h:112
aGrUM
3.3.2
© PHW&CG&others - 2022
DoXyGeN 1.18.0