aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
Generic algorithms

Generic algorithms come in two flavors: approximation schemes/policies (see the Topics below) and a family of graph algorithms genericized via C++20 concepts, detailed in the section below. More...

Collaboration diagram for Generic algorithms:

Topics

 Approximation Scheme algorithms
 About aGrUM approximation schemes.
 Approximation algorithms
 About aGrUM approximation policies.

Detailed Description

Generic algorithms come in two flavors: approximation schemes/policies (see the Topics below) and a family of graph algorithms genericized via C++20 concepts, detailed in the section below.

Generic graph algorithms via GUM_*Graphable concepts

A family of free functions in gum::graph (src/agrum/base/graphs/algorithms/generic/) is written once and generalized across concrete graph types through four C++20 concepts defined in graphConcepts.h: GUM_NodeGraphable (base), GUM_DiGraphable and GUM_UndiGraphable (both refine it), and GUM_MixedGraphable (refines both). DiGraph/DAG satisfy GUM_DiGraphable, UndiGraph satisfies GUM_UndiGraphable, MixedGraph/PDAG satisfy GUM_MixedGraphable – each checked by a compile-time static_assert.

  • Path finding (pathFinding.h): directedPath(), hasDirectedPath(), directedUnorientedPath() on GUM_DiGraphable; undirectedPath(), hasUndirectedPath() on GUM_UndiGraphable; mixedOrientedPath(), mixedUnorientedPath() on GUM_MixedGraphable.
  • Reachability & connectivity (reachability.h): ancestors(), descendants(), family() on GUM_DiGraphable; chainComponents(), areConnected() on GUM_UndiGraphable; connectedComponents() on the base GUM_NodeGraphable (dispatches internally via if constexpr); chainComponent(), boundary() on GUM_MixedGraphable.
  • Topological structure (cycleDetection.h): topologicalOrder() (Kahn's algorithm) on GUM_DiGraphable; hasUndirectedCycle() on GUM_UndiGraphable.
  • Causal/probabilistic separation (separation.h, bayesBall.h, moralization.h): dSeparated() (Bayes Ball) and cSeparated() (moralization-based, Pearl 1988) on GUM_DiGraphable / GUM_MixedGraphable, built on requisiteNodes(), dConnected(), moralGraph() and moralizedAncestralGraph().
  • Markov blanket (markovBlanket.h): markovBlanket() on GUM_DiGraphable.
  • Minimal conditioning set (minimalConditioningSet.h): minimalCondSet() on GUM_DiGraphable.
  • Textual graph construction (fastGraph.h): fastGraph() parses a DOT-like description ("A->B->C; B-E") into any GUM_NodeGraphable graph type, using GUM_DiGraphable / GUM_UndiGraphable internally to decide which edge tokens are legal for the requested type.

This generalization is currently confined to src/agrum/base/graphs/: higher-level modules (BN, MRF, CN, PRM, ...) call these free functions directly rather than constraining their own templates by these concepts.