aGrUM
3.3.2
a C++ library for (probabilistic) graphical models
Toggle main menu visibility
minimalConditioningSet_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/minimalConditioningSet.h
>
45
46
namespace
gum::graph
{
47
48
template
< GUM_DiGraphable G >
49
void
_mcsVisitUp_
(
const
G& g,
50
NodeId
node,
51
const
NodeSet
& soids,
52
NodeSet
& minimal,
53
NodeSet
& visitedUp,
54
NodeSet
& visitedDn) {
55
if
(visitedUp.
contains
(node))
return
;
56
visitedUp << node;
57
58
if
(soids.
contains
(node)) {
59
minimal << node;
60
}
else
{
61
for
(
const
auto
par: g.parents(node))
62
_mcsVisitUp_
(g, par, soids, minimal, visitedUp, visitedDn);
63
for
(
const
auto
chi: g.children(node))
64
_mcsVisitDn_
(g, chi, soids, minimal, visitedUp, visitedDn);
65
}
66
}
67
68
template
< GUM_DiGraphable G >
69
void
_mcsVisitDn_
(
const
G& g,
70
NodeId
node,
71
const
NodeSet
& soids,
72
NodeSet
& minimal,
73
NodeSet
& visitedUp,
74
NodeSet
& visitedDn) {
75
if
(visitedDn.
contains
(node))
return
;
76
visitedDn << node;
77
78
if
(soids.
contains
(node)) {
79
minimal << node;
80
for
(
const
auto
par: g.parents(node))
81
_mcsVisitUp_
(g, par, soids, minimal, visitedUp, visitedDn);
82
}
else
{
83
for
(
const
auto
chi: g.children(node))
84
_mcsVisitDn_
(g, chi, soids, minimal, visitedUp, visitedDn);
85
}
86
}
87
88
template
< GUM_DiGraphable G >
89
NodeSet
minimalCondSet
(
const
G& g,
NodeId
target,
const
NodeSet
& soids) {
90
if
(soids.
contains
(target))
return
NodeSet
({target});
91
92
NodeSet
res, visitedUp, visitedDn;
93
visitedUp << target;
94
visitedDn << target;
95
96
for
(
const
auto
par: g.parents(target))
97
_mcsVisitUp_
(g, par, soids, res, visitedUp, visitedDn);
98
for
(
const
auto
chi: g.children(target))
99
_mcsVisitDn_
(g, chi, soids, res, visitedUp, visitedDn);
100
101
return
res;
102
}
103
104
template
< GUM_DiGraphable G >
105
NodeSet
minimalCondSet
(
const
G& g,
const
NodeSet
& targets,
const
NodeSet
& soids) {
106
NodeSet
res;
107
for
(
const
auto
node: targets)
108
res +=
minimalCondSet
(g, node, soids);
109
return
res;
110
}
111
112
}
// namespace gum::graph
gum::Set::contains
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition
set_tpl.h:468
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
minimalConditioningSet.h
Generic minimal conditioning set algorithm for directed graphs.
gum::graph
Definition
bayesBall.h:79
gum::graph::_mcsVisitUp_
void _mcsVisitUp_(const G &g, NodeId node, const NodeSet &soids, NodeSet &minimal, NodeSet &visitedUp, NodeSet &visitedDn)
Definition
minimalConditioningSet_tpl.h:49
gum::graph::minimalCondSet
NodeSet minimalCondSet(const G &g, NodeId target, const NodeSet &soids)
Returns the minimal subset of soids that d-connects target.
Definition
minimalConditioningSet_tpl.h:89
gum::graph::_mcsVisitDn_
void _mcsVisitDn_(const G &g, NodeId node, const NodeSet &soids, NodeSet &minimal, NodeSet &visitedUp, NodeSet &visitedDn)
Definition
minimalConditioningSet_tpl.h:69
aGrUM
3.3.2
© PHW&CG&others - 2022
DoXyGeN 1.18.0