Class building the essential graph from a BN. More...

#include <agrum/BN/algorithms/essentialGraph.h>

Collaboration diagram for gum::EssentialGraph:

Public Member Functions
	EssentialGraph ()=default
	EssentialGraph (const DAGmodel &m)
	EssentialGraph (const DAGmodel &m, const PDAG &mg)
	EssentialGraph (const EssentialGraph &g)
EssentialGraph &	operator= (const EssentialGraph &g)
	~EssentialGraph ()
PDAG	pdag () const
std::string	toDot () const
const NodeSet &	parents (NodeId id) const
	wrapping MixedGraph::parents(id)
const NodeSet &	children (NodeId id) const
	wrapping MixedGraph::parents(id)
NodeSet	parents (const NodeSet &ids) const
	wrapping MixedGraph::parents(ids)
NodeSet	children (const NodeSet &ids) const
	wrapping MixedGraph::parents(ids)
NodeSet	descendants (NodeId id) const
	wrapping PDAG::descendants(id)
NodeSet	ancestors (NodeId id) const
	wrapping PDAG::ancestors(id)
const NodeSet &	neighbours (NodeId id) const
	wrapping MixedGraph::parents(id)
Size	sizeArcs () const
	wrapping MixedGraph::sizeArcs()
const ArcSet &	arcs () const
	wrapping MixedGraph::arcs()
Size	sizeEdges () const
	wrapping MixedGraph::sizeEdges()
const EdgeSet &	edges () const
	wrapping MixedGraph::edges()
Size	sizeNodes () const
	wrapping MixedGraph::sizeNodes()
Size	size () const
	wrapping MixedGraph::size()
UndiGraph	skeleton () const
const NodeGraphPart &	nodes () const
	wrapping MixedGraph::nodes()
NodeProperty< NodeId >	connectedComponents () const
	Returns the connected components of the essential graph. Each node maps to the id of its component root.
NodeId	idFromName (std::string_view name) const
	wrappping DAGModel::idFromName()
const std::string &	nameFromId (NodeId node) const
	wrappping .name()

Private Member Functions
void	_buildEssentialGraph_ ()
bool	_strongly_protected_ (NodeId a, NodeId b) const

Static Private Member Functions
static bool	_strongly_protected_ (MixedGraph mg, NodeId a, NodeId b)

Private Attributes
const DAGmodel *	_dagmodel_
PDAG	_pdag_

Detailed Description

Class building the essential graph from a BN.

Essential graph is a mixed graph (Chain Graph) that represents the class of markov equivalent Bayesian networks (with the same independence model).

The main goal of this class is to nest the algorithm to build the essential graph from a BN and to encapsulate the representation (as a MixedGraph) of the essential graph.

gum::operator<<(std::ostream&, const BayesNet<GUM_SCALAR>&).

Definition at line 76 of file essentialGraph.h.

Constructor & Destructor Documentation

◆ EssentialGraph() [1/4]

gum::EssentialGraph::EssentialGraph ( )

default

References EssentialGraph().

Referenced by EssentialGraph(), EssentialGraph(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EssentialGraph() [2/4]

gum::EssentialGraph::EssentialGraph ( const DAGmodel & m )

explicit

Definition at line 56 of file essentialGraph.cpp.

56: _dagmodel_(&m) { _buildEssentialGraph_(); }

gum::EssentialGraph::_dagmodel_

const DAGmodel * _dagmodel_

Definition essentialGraph.h:152

gum::EssentialGraph::_buildEssentialGraph_

void _buildEssentialGraph_()

Definition essentialGraph.cpp:75

References _buildEssentialGraph_(), and _dagmodel_.

Here is the call graph for this function:

◆ EssentialGraph() [3/4]

gum::EssentialGraph::EssentialGraph	(	const DAGmodel &	m,
		const PDAG &	mg )

Definition at line 58 of file essentialGraph.cpp.

58: _dagmodel_(&m), _pdag_(mg) {}

gum::EssentialGraph::_pdag_

PDAG _pdag_

Definition essentialGraph.h:153

References _dagmodel_, and _pdag_.

◆ EssentialGraph() [4/4]

gum::EssentialGraph::EssentialGraph ( const EssentialGraph & g )

Definition at line 60 of file essentialGraph.cpp.

                                                        {
    _dagmodel_ = g._dagmodel_;
    _buildEssentialGraph_();
  }

References EssentialGraph(), _buildEssentialGraph_(), and _dagmodel_.

Here is the call graph for this function:

◆ ~EssentialGraph()

gum::EssentialGraph::~EssentialGraph ( )

default

Member Function Documentation

◆ _buildEssentialGraph_()

void gum::EssentialGraph::_buildEssentialGraph_ ( )

private

Definition at line 75 of file essentialGraph.cpp.

                                             {
    MixedGraph mg;   // during the process, the graph may not be a PDAG
    _pdag_.clear();
    if (_dagmodel_ == nullptr) return;
 
    for (const auto& node: _dagmodel_->nodes()) {
      mg.addNodeWithId(node);
      _pdag_.addNodeWithId(node);
    }
    for (const auto& arc: _dagmodel_->arcs()) {
      mg.addArc(arc.tail(), arc.head());
    }
 
    std::vector< Arc > v;
    do {
      v.clear();
      for (const auto x: _dagmodel_->topologicalOrder())
        for (const auto y: mg.children(x))
          if (!_strongly_protected_(mg, x, y)) v.emplace_back(x, y);
 
      for (const auto& arc: v) {
        mg.eraseArc(arc);
        mg.addEdge(arc.tail(), arc.head());
      }
    } while (!v.empty());
 
    for (const auto& arc: mg.arcs()) {
      _pdag_.addArc(arc.tail(), arc.head());
    }
    for (const auto& edge: mg.edges()) {
      _pdag_.addEdge(edge.first(), edge.second());
    }
 
    for (auto id: _pdag_)
      _pdag_.setName(id, _dagmodel_->variable(id).name());
  }

References _dagmodel_, _pdag_, _strongly_protected_(), gum::DiGraph::addArc(), gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::ArcGraphPart::arcs(), gum::ArcGraphPart::children(), gum::EdgeGraphPart::edges(), and gum::ArcGraphPart::eraseArc().

Referenced by EssentialGraph(), EssentialGraph(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _strongly_protected_() [1/2]

bool gum::EssentialGraph::_strongly_protected_	(	MixedGraph	mg,
		NodeId	a,
		NodeId	b )

staticprivate

Definition at line 116 of file essentialGraph.cpp.

                                                                             {
    // testing a->b from
    // A Characterization of Markov Equivalence Classes for Acyclic Digraphs (2001)
    //  Steen A. Andersson, David Madigan, and Michael D. Perlman*
 
    // condition (a)
    for (const auto& c: mg.parents(a)) {
      if (!mg.existsArc(c, b)) { return true; }
    }
 
 
    for (const auto& c: mg.parents(b)) {
      if (c == a) { continue; }
      // condition (c)
      if (mg.existsArc(a, c)) { return true; }
 
      // condition (b) knowing that a can not be a parent of c (condition below)
      if (!mg.existsEdge(a, c) && !mg.existsArc(c, a)) { return true; }
    }
 
    // condition (d)
    bool oneFound = false;
    for (const auto& c: mg.parents(b)) {
      if (c == a) { continue; }
      // condition (d)
      if (mg.existsEdge(c, a)) {
        if (oneFound) {   // this is the second found
          return true;
        }
        oneFound = true;
      }
    }
 
    return false;
  }

References gum::ArcGraphPart::existsArc(), gum::EdgeGraphPart::existsEdge(), and gum::ArcGraphPart::parents().

Here is the call graph for this function:

◆ _strongly_protected_() [2/2]

bool gum::EssentialGraph::_strongly_protected_	(	NodeId	a,
		NodeId	b ) const

private

Definition at line 112 of file essentialGraph.cpp.

                                                                    {
    return _strongly_protected_(_pdag_, a, b);
  }

References _pdag_, and _strongly_protected_().

Referenced by _buildEssentialGraph_(), and _strongly_protected_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ancestors()

INLINE NodeSet gum::EssentialGraph::ancestors ( NodeId id ) const

wrapping PDAG::ancestors(id)

Definition at line 68 of file essentialGraph_inl.h.

68{ return _pdag_.ancestors(id); }

References _pdag_.

◆ arcs()

INLINE const ArcSet & gum::EssentialGraph::arcs ( ) const

wrapping MixedGraph::arcs()

Definition at line 76 of file essentialGraph_inl.h.

76{ return _pdag_.arcs(); }

References _pdag_.

Referenced by skeleton().

Here is the caller graph for this function:

◆ children() [1/2]

INLINE NodeSet gum::EssentialGraph::children ( const NodeSet & ids ) const

wrapping MixedGraph::parents(ids)

Definition at line 64 of file essentialGraph_inl.h.

64{ return _pdag_.children(ids); }

References _pdag_.

◆ children() [2/2]

INLINE const NodeSet & gum::EssentialGraph::children ( NodeId id ) const

wrapping MixedGraph::parents(id)

Definition at line 60 of file essentialGraph_inl.h.

60{ return _pdag_.children(id); }

References _pdag_.

◆ connectedComponents()

INLINE NodeProperty< NodeId > gum::EssentialGraph::connectedComponents ( ) const

Returns the connected components of the essential graph. Each node maps to the id of its component root.

Definition at line 96 of file essentialGraph_inl.h.

                                                                          {
    return _pdag_.connectedComponents();
  }

References _pdag_.

◆ descendants()

INLINE NodeSet gum::EssentialGraph::descendants ( NodeId id ) const

wrapping PDAG::descendants(id)

Definition at line 66 of file essentialGraph_inl.h.

66{ return _pdag_.descendants(id); }

References _pdag_.

◆ edges()

INLINE const EdgeSet & gum::EssentialGraph::edges ( ) const

wrapping MixedGraph::edges()

Definition at line 80 of file essentialGraph_inl.h.

80{ return _pdag_.edges(); }

References _pdag_.

Referenced by skeleton().

Here is the caller graph for this function:

◆ idFromName()

INLINE NodeId gum::EssentialGraph::idFromName ( std::string_view name ) const

wrappping DAGModel::idFromName()

Definition at line 88 of file essentialGraph_inl.h.

                                                                    {
    return _dagmodel_->idFromName(name);
  }

References _dagmodel_.

◆ nameFromId()

INLINE const std::string & gum::EssentialGraph::nameFromId ( NodeId node ) const

wrappping .name()

Definition at line 92 of file essentialGraph_inl.h.

                                                                      {
    return _dagmodel_->variable(node).name();
  }

References _dagmodel_.

◆ neighbours()

INLINE const NodeSet & gum::EssentialGraph::neighbours ( NodeId id ) const

wrapping MixedGraph::parents(id)

Definition at line 70 of file essentialGraph_inl.h.

                                                                  {
    return _pdag_.neighbours(id);
  }

References _pdag_.

◆ nodes()

INLINE const NodeGraphPart & gum::EssentialGraph::nodes ( ) const

wrapping MixedGraph::nodes()

Definition at line 86 of file essentialGraph_inl.h.

86{ return _pdag_.nodes(); }

References _pdag_.

Referenced by skeleton().

Here is the caller graph for this function:

◆ operator=()

EssentialGraph & gum::EssentialGraph::operator= ( const EssentialGraph & g )

Definition at line 65 of file essentialGraph.cpp.

                                                                 {
    if (&g != this) {
      _dagmodel_ = g._dagmodel_;
      _buildEssentialGraph_();
    }
    return *this;
  }

References EssentialGraph(), _buildEssentialGraph_(), and _dagmodel_.

Here is the call graph for this function:

◆ parents() [1/2]

INLINE NodeSet gum::EssentialGraph::parents ( const NodeSet & ids ) const

wrapping MixedGraph::parents(ids)

Definition at line 62 of file essentialGraph_inl.h.

62{ return _pdag_.parents(ids); }

References _pdag_.

◆ parents() [2/2]

INLINE const NodeSet & gum::EssentialGraph::parents ( NodeId id ) const

wrapping MixedGraph::parents(id)

Definition at line 58 of file essentialGraph_inl.h.

58{ return _pdag_.parents(id); }

References _pdag_.

◆ pdag()

INLINE PDAG gum::EssentialGraph::pdag ( ) const

Returns: a copy of the mixed graph

Definition at line 56 of file essentialGraph_inl.h.

56{ return _pdag_; }

References _pdag_.

◆ size()

INLINE Size gum::EssentialGraph::size ( ) const

wrapping MixedGraph::size()

Definition at line 84 of file essentialGraph_inl.h.

84{ return _pdag_.size(); }

References _pdag_.

◆ sizeArcs()

INLINE Size gum::EssentialGraph::sizeArcs ( ) const

wrapping MixedGraph::sizeArcs()

Definition at line 74 of file essentialGraph_inl.h.

74{ return _pdag_.sizeArcs(); }

References _pdag_.

◆ sizeEdges()

INLINE Size gum::EssentialGraph::sizeEdges ( ) const

wrapping MixedGraph::sizeEdges()

Definition at line 78 of file essentialGraph_inl.h.

78{ return _pdag_.sizeEdges(); }

References _pdag_.

◆ sizeNodes()

INLINE Size gum::EssentialGraph::sizeNodes ( ) const

wrapping MixedGraph::sizeNodes()

Definition at line 82 of file essentialGraph_inl.h.

82{ return _pdag_.sizeNodes(); }

References _pdag_.

◆ skeleton()

UndiGraph gum::EssentialGraph::skeleton ( ) const

Definition at line 182 of file essentialGraph.cpp.

                                           {
    UndiGraph skel;
    for (const auto& n: nodes())
      skel.addNodeWithId(n);
    for (const auto& edge: edges())
      skel.addEdge(edge.first(), edge.second());
    for (const auto& arc: arcs())
      skel.addEdge(arc.tail(), arc.head());
    if (_dagmodel_ != nullptr)
      for (auto id: skel)
        skel.setName(id, _dagmodel_->variable(id).name());
    return skel;
  }

References _dagmodel_, gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), arcs(), edges(), nodes(), and gum::NodeGraphPart::setName().

Here is the call graph for this function:

◆ toDot()

std::string gum::EssentialGraph::toDot ( ) const

Returns: a dot representation of this essentialGraph

Definition at line 152 of file essentialGraph.cpp.

                                        {
    std::stringstream output;
    std::stringstream nodeStream;
    std::stringstream edgeStream;
    List< NodeId >    treatedNodes;
    output << "digraph \"no_name\" {\n";
    nodeStream << "node [shape = ellipse];\n";
    std::string tab = "  ";
    if (_dagmodel_ != nullptr) {
      for (const auto node: _pdag_.nodes()) {
        nodeStream << std::format("{}{}[label=\"{}\"];",
                                  tab,
                                  node,
                                  _dagmodel_->variable(node).name());
 
        for (const auto nei: _pdag_.neighbours(node))
          if (!treatedNodes.exists(nei))
            edgeStream << std::format("{}{} -> {} [dir=none];\n", tab, node, nei);
 
        for (const auto chi: _pdag_.children(node))
          edgeStream << std::format("{}{} -> {} [color=red];\n", tab, node, chi);
 
        treatedNodes.insert(node);
      }
    }
    output << nodeStream.str() << '\n' << edgeStream.str() << '\n' << "}\n";
 
    return output.str();
  }

References _dagmodel_, _pdag_, gum::List< Val >::exists(), and gum::List< Val >::insert().

Here is the call graph for this function:

Member Data Documentation

◆ _dagmodel_

const DAGmodel* gum::EssentialGraph::_dagmodel_

private

Definition at line 152 of file essentialGraph.h.

Referenced by EssentialGraph(), EssentialGraph(), EssentialGraph(), _buildEssentialGraph_(), idFromName(), nameFromId(), operator=(), skeleton(), and toDot().

◆ _pdag_

PDAG gum::EssentialGraph::_pdag_

private

Definition at line 153 of file essentialGraph.h.

Referenced by EssentialGraph(), _buildEssentialGraph_(), _strongly_protected_(), ancestors(), arcs(), children(), children(), connectedComponents(), descendants(), edges(), neighbours(), nodes(), parents(), parents(), pdag(), size(), sizeArcs(), sizeEdges(), sizeNodes(), and toDot().

The documentation for this class was generated from the following files:

agrum/BN/algorithms/essentialGraph.h
agrum/BN/algorithms/essentialGraph.cpp
agrum/BN/algorithms/essentialGraph_inl.h

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ EssentialGraph() [1/4]

◆ EssentialGraph() [2/4]

◆ EssentialGraph() [3/4]

◆ EssentialGraph() [4/4]

◆ ~EssentialGraph()

Member Function Documentation

◆ _buildEssentialGraph_()

◆ _strongly_protected_() [1/2]

◆ _strongly_protected_() [2/2]

◆ ancestors()

◆ arcs()

◆ children() [1/2]

◆ children() [2/2]

◆ connectedComponents()

◆ descendants()

◆ edges()

◆ idFromName()

◆ nameFromId()

◆ neighbours()

◆ nodes()

◆ operator=()

◆ parents() [1/2]

◆ parents() [2/2]

◆ pdag()

◆ size()

◆ sizeArcs()

◆ sizeEdges()

◆ sizeNodes()

◆ skeleton()

◆ toDot()

Member Data Documentation

◆ _dagmodel_

◆ _pdag_