bayesBall.h File Reference

Generic Bayes Ball algorithm (Shachter 1998) for directed graphs. More...

#include <utility>
#include <agrum/agrum.h>
#include <agrum/base/graphs/graphConcepts.h>
#include <agrum/base/graphs/algorithms/generic/bayesBall_tpl.h>

Include dependency graph for bayesBall.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>
NodeSet	gum::graph::requisiteNodes (const G &g, const NodeSet &query, const NodeSet &Zhard=NodeSet(), const NodeSet &Zsoft=NodeSet())
	Returns the Shachter-requisite nodes for query given evidence.
template<GUM_DiGraphable G>
NodeSet	gum::graph::dConnected (const G &g, const NodeSet &query, const NodeSet &Zhard=NodeSet(), const NodeSet &Zsoft=NodeSet())
	Returns all nodes d-connected to query given evidence.

Detailed Description

Generic Bayes Ball algorithm (Shachter 1998) for directed graphs.

Provides a single template function:

gum::graph::requisiteNodes(g, query, Zhard, Zsoft)

which computes the set of nodes d-connected to query given hard evidence Zhard and soft evidence Zsoft, using the Bayes Ball message-passing algorithm.

The algorithm operates purely on the graph structure (parents / children) and is therefore constrained by GUM_DiGraphable. It does not depend on any Bayesian-network–specific notion.

Complexity: O(n + e) in the number of nodes and arcs, versus O(n² + e) for the moralization-based approach.

Hard vs soft evidence

• Hard evidence (Zhard): the node is observed; it blocks upward propagation (as in a chain or fork) but does not activate a collider for downstream propagation.
• Soft evidence (Zsoft): the node is "virtually" observed; it activates colliders (upward propagation) but does not block downward propagation.

Author

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

Definition in file bayesBall.h.