aGrUM
3.3.2
a C++ library for (probabilistic) graphical models
Toggle main menu visibility
separation.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
45
46
#ifndef GUM_DSEPARATION_H
47
#define GUM_DSEPARATION_H
48
49
#include <
agrum/agrum.h
>
50
51
#include <
agrum/base/graphs/DAG.h
>
52
53
namespace
gum
{
54
75
class
GUM_PUBLIC_CM
Separation
{
76
public
:
77
// =======================================================================
78
// Core public API
79
// =======================================================================
80
95
static
bool
isDSeparated
(
const
DAG
& dag,
const
NodeSet
& X,
const
NodeSet
& Y,
const
NodeSet
& Z);
96
114
static
bool
115
isBackdoorSeparated
(
const
DAG
& dag,
const
NodeSet
& X,
const
NodeSet
& Y,
const
NodeSet
& Z);
116
140
static
bool
141
isForwardSeparated
(
const
DAG
& dag,
const
NodeSet
& X,
const
NodeSet
& Y,
const
NodeSet
& Z);
142
143
// =======================================================================
144
// Optional reduction for speed
145
// =======================================================================
146
159
static
DAG
160
reduceForDSeparation
(
const
DAG
& dag,
const
NodeSet
& X,
const
NodeSet
& Y,
const
NodeSet
& Z);
161
172
static
NodeSet
173
findBarrenNodes
(
const
DAG
& dag,
const
NodeSet
& evidenceZ,
const
NodeSet
& targetsXY);
174
175
// =======================================================================
176
// Minimal structural helpers (delegating to DAG where possible)
177
// =======================================================================
178
187
static
bool
isAncestorOf
(
const
DAG
& dag,
NodeId
x,
NodeId
y);
188
197
static
bool
isDescendantOf
(
const
DAG
& dag,
NodeId
x,
NodeId
y);
198
199
private
:
200
// =======================================================================
201
// Internal helper
202
// =======================================================================
203
213
static
bool
anyUndirectedConnection
(
const
UndiGraph
& ug,
const
NodeSet
& A,
const
NodeSet
& B);
214
};
215
216
}
// namespace gum
217
218
#endif
// GUM_DSEPARATION_H
DAG.h
Base classes for directed acyclic graphs.
agrum.h
gum::DAG
Base class for dag.
Definition
DAG.h:121
gum::Separation
Consolidated d-separation utilities (DAG-centric).
Definition
separation.h:75
gum::Separation::reduceForDSeparation
static DAG reduceForDSeparation(const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
Barren-node pruning relative to the interest set (X \cup Y \cup Z).
Definition
separation.cpp:153
gum::Separation::isDSeparated
static bool isDSeparated(const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
Test ( X \perp!!!\perp Y \mid Z ) (general d-separation).
Definition
separation.cpp:80
gum::Separation::isAncestorOf
static bool isAncestorOf(const DAG &dag, NodeId x, NodeId y)
Is x an ancestor of y?
Definition
separation.cpp:198
gum::Separation::findBarrenNodes
static NodeSet findBarrenNodes(const DAG &dag, const NodeSet &evidenceZ, const NodeSet &targetsXY)
Compute barren nodes given evidence and targets.
Definition
separation.cpp:182
gum::Separation::isForwardSeparated
static bool isForwardSeparated(const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
Forward-style restriction: only paths whose first edge leaves X.
Definition
separation.cpp:117
gum::Separation::isDescendantOf
static bool isDescendantOf(const DAG &dag, NodeId x, NodeId y)
Is x a descendant of y?
Definition
separation.cpp:205
gum::Separation::anyUndirectedConnection
static bool anyUndirectedConnection(const UndiGraph &ug, const NodeSet &A, const NodeSet &B)
Check if any node in A is undirected-connected to any node in B.
Definition
separation.cpp:217
gum::Separation::isBackdoorSeparated
static bool isBackdoorSeparated(const DAG &dag, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
Backdoor-style restriction: only paths whose first edge points into X.
Definition
separation.cpp:91
gum::UndiGraph
Base class for undirected graphs.
Definition
undiGraph.h:134
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
gum is the global namespace for all aGrUM entities
Definition
agrum.h:46
aGrUM
3.3.2
© PHW&CG&others - 2022
DoXyGeN 1.18.0