separation.h File Reference

d-Separation and c-Separation tests for aGrUM graphs. More...

#include <agrum/agrum.h>
#include <agrum/base/core/exceptions.h>
#include <agrum/base/graphs/algorithms/generic/bayesBall.h>
#include <agrum/base/graphs/algorithms/generic/moralization.h>
#include <agrum/base/graphs/algorithms/generic/separation_tpl.h>

Include dependency graph for separation.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	gum
	gum is the global namespace for all aGrUM entities
namespace	gum::graph

Functions
template<GUM_DiGraphable G>
bool	gum::graph::dSeparated (const G &g, NodeId X, NodeId Y, const NodeSet &Z)
	Returns true iff X and Y are d-separated by Z in g.
template<GUM_DiGraphable G>
bool	gum::graph::dSeparated (const G &g, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Returns true iff every node in X is d-separated from every node in Y by Z in g.
template<GUM_MixedGraphable G>
bool	gum::graph::cSeparated (const G &g, NodeId X, NodeId Y, const NodeSet &Z)
	Returns true iff X and Y are c-separated by Z in g.
template<GUM_MixedGraphable G>
bool	gum::graph::cSeparated (const G &g, const NodeSet &X, const NodeSet &Y, const NodeSet &Z)
	Returns true iff X and Y are c-separated by Z in g.

Detailed Description

d-Separation and c-Separation tests for aGrUM graphs.

All functions live in namespace gum::graph and are constrained by the concepts defined in graphConcepts.h :

GUM_DiGraphable — dSeparated (DAGs) GUM_MixedGraphable — cSeparated (PDAGs / chain graphs)

dSeparated uses the Bayes Ball algorithm (Shachter 1998, O(n+e)): X ⊥ Y | Z iff Y ∉ requisiteNodes(g, {X}, Z).

cSeparated uses the moralization-based algorithm (Pearl 1988):

1. Moralize the ancestral subgraph of X ∪ Y ∪ Z (following arcs and edges, marrying co-parents per chain component).
2. Remove all nodes of Z.
3. X and Y are separated iff they are disconnected in the result.

Author

Pierre-Henri WUILLEMIN(_at_LIP6) and Christophe GONZALES(_at_AMU)

Definition in file separation.h.