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)
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()
NodeId	idFromName (const std::string &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 74 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:140

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:141

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());
    }
  }

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 113 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 109 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:

◆ arcs()

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

wrapping MixedGraph::arcs()

Definition at line 71 of file essentialGraph_inl.h.

71{ 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 63 of file essentialGraph_inl.h.

63{ 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 59 of file essentialGraph_inl.h.

59{ return _pdag_.children(id); }

References _pdag_.

◆ edges()

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

wrapping MixedGraph::edges()

Definition at line 75 of file essentialGraph_inl.h.

75{ return _pdag_.edges(); }

References _pdag_.

Referenced by skeleton().

Here is the caller graph for this function:

◆ idFromName()

INLINE NodeId gum::EssentialGraph::idFromName ( const std::string & name ) const

wrappping DAGModel::idFromName()

Definition at line 83 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 87 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 65 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 81 of file essentialGraph_inl.h.

81{ 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 61 of file essentialGraph_inl.h.

61{ 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 57 of file essentialGraph_inl.h.

57{ return _pdag_.parents(id); }

References _pdag_.

◆ pdag()

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

Returns: a copy of the mixed graph

Definition at line 55 of file essentialGraph_inl.h.

55{ return _pdag_; }

References _pdag_.

◆ size()

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

wrapping MixedGraph::size()

Definition at line 79 of file essentialGraph_inl.h.

79{ return _pdag_.size(); }

References _pdag_.

◆ sizeArcs()

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

wrapping MixedGraph::sizeArcs()

Definition at line 69 of file essentialGraph_inl.h.

69{ return _pdag_.sizeArcs(); }

References _pdag_.

◆ sizeEdges()

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

wrapping MixedGraph::sizeEdges()

Definition at line 73 of file essentialGraph_inl.h.

73{ return _pdag_.sizeEdges(); }

References _pdag_.

◆ sizeNodes()

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

wrapping MixedGraph::sizeNodes()

Definition at line 77 of file essentialGraph_inl.h.

77{ return _pdag_.sizeNodes(); }

References _pdag_.

◆ skeleton()

UndiGraph gum::EssentialGraph::skeleton ( ) const

Definition at line 177 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());
    return skel;
  }

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

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 149 of file essentialGraph.cpp.

                                        {
    std::stringstream output;
    std::stringstream nodeStream;
    std::stringstream edgeStream;
    List< NodeId >    treatedNodes;
    output << "digraph \""
           << "no_name\" {" << std::endl;
    nodeStream << "node [shape = ellipse];" << std::endl;
    std::string tab = "  ";
    if (_dagmodel_ != nullptr) {
      for (const auto node: _pdag_.nodes()) {
        nodeStream << tab << node << "[label=\"" << _dagmodel_->variable(node).name() << "\"];";
 
        for (const auto nei: _pdag_.neighbours(node))
          if (!treatedNodes.exists(nei))
            edgeStream << tab << node << " -> " << nei << " [dir=none];" << std::endl;
 
        for (const auto chi: _pdag_.children(node))
          edgeStream << tab << node << " -> " << chi << " [color=red];" << std::endl;
 
        treatedNodes.insert(node);
      }
    }
    output << nodeStream.str() << std::endl << edgeStream.str() << std::endl << "}" << std::endl;
 
    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 140 of file essentialGraph.h.

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

◆ _pdag_

PDAG gum::EssentialGraph::_pdag_

private

Definition at line 141 of file essentialGraph.h.

Referenced by EssentialGraph(), _buildEssentialGraph_(), _strongly_protected_(), arcs(), children(), children(), 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]

◆ arcs()

◆ children() [1/2]

◆ children() [2/2]

◆ edges()

◆ idFromName()

◆ nameFromId()

◆ neighbours()

◆ nodes()

◆ operator=()

◆ parents() [1/2]

◆ parents() [2/2]

◆ pdag()

◆ size()

◆ sizeArcs()

◆ sizeEdges()

◆ sizeNodes()

◆ skeleton()

◆ toDot()

Member Data Documentation

◆ _dagmodel_

◆ _pdag_