aGrUM
3.3.2
a C++ library for (probabilistic) graphical models
Toggle main menu visibility
separation_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/separation.h
>
45
46
namespace
gum::graph
{
47
48
template
< GUM_DiGraphable G >
49
bool
dSeparated
(
const
G& g,
NodeId
X,
NodeId
Y,
const
NodeSet
& Z) {
50
NodeSet
qX;
51
qX.
insert
(X);
52
return
!
graph::dConnected
(g, qX, Z).
exists
(Y);
53
}
54
55
template
< GUM_DiGraphable G >
56
bool
dSeparated
(
const
G& g,
const
NodeSet
& X,
const
NodeSet
& Y,
const
NodeSet
& Z) {
57
if
(!(X * Y).empty())
GUM_ERROR
(
InvalidArgument
,
"NodeSets X and Y must be disjoint."
)
58
return
(
graph::dConnected
(g, X, Z) * Y).empty();
59
}
60
61
template
< GUM_MixedGraphable G >
62
bool
cSeparated
(
const
G& g,
NodeId
X,
NodeId
Y,
const
NodeSet
& Z) {
63
NodeSet
query{Z};
64
query.
insert
(X);
65
query.
insert
(Y);
66
auto
moral =
moralizedAncestralGraph
(g, query);
67
for
(
const
auto
node: Z)
68
if
(moral.existsNode(node)) moral.eraseNode(node);
69
return
!moral.hasUndirectedPath(X, Y);
70
}
71
72
template
< GUM_MixedGraphable G >
73
bool
cSeparated
(
const
G& g,
const
NodeSet
& X,
const
NodeSet
& Y,
const
NodeSet
& Z) {
74
if
(!(X * Y).empty())
GUM_ERROR
(
InvalidArgument
,
"NodeSets X and Y must be disjoint."
)
75
76
NodeSet
query{Z};
77
query += X;
78
query += Y;
79
auto
moral =
moralizedAncestralGraph
(g, query);
80
for
(
const
auto
node: Z)
81
if
(moral.existsNode(node)) moral.eraseNode(node);
82
83
const
auto
cc = moral.chainComponents();
84
85
NodeSet
Xcc, Ycc;
86
for
(
const
auto
node: X)
87
if
(moral.existsNode(node)) Xcc.
insert
(cc[node]);
88
for
(
const
auto
node: Y)
89
if
(moral.existsNode(node)) Ycc.
insert
(cc[node]);
90
91
return
(Xcc * Ycc).empty();
92
}
93
94
}
// namespace gum::graph
separation.h
d-Separation and c-Separation tests for aGrUM graphs.
InvalidArgument
Exception: at least one argument passed to a function is not what was expected.
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_ERROR
#define GUM_ERROR(type, msg)
Definition
exceptions.h:76
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
gum::graph
Definition
bayesBall.h:79
gum::graph::cSeparated
bool cSeparated(const G &g, NodeId X, NodeId Y, const NodeSet &Z)
Returns true iff X and Y are c-separated by Z in g.
Definition
separation_tpl.h:62
gum::graph::moralizedAncestralGraph
UndiGraph moralizedAncestralGraph(const G &g, const NodeSet &query)
Returns the moralized ancestral graph of query in g.
Definition
moralization_tpl.h:109
gum::graph::dSeparated
bool dSeparated(const G &g, NodeId X, NodeId Y, const NodeSet &Z)
Returns true iff X and Y are d-separated by Z in g.
Definition
separation_tpl.h:49
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