gum::EssentialGraph Class Reference

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 MixedGraph &mg)
	EssentialGraph (const EssentialGraph &g)
EssentialGraph &	operator= (const EssentialGraph &g)
	~EssentialGraph ()
MixedGraph	mixedGraph ()
std::string	toDot () const
const NodeSet &	parents (const NodeId id) const
	wrapping MixedGraph::parents(id) More...
const NodeSet &	children (const NodeId id) const
	wrapping MixedGraph::parents(id) More...
const NodeSet &	neighbours (const NodeId id) const
	wrapping MixedGraph::parents(id) More...
Size	sizeArcs () const
	wrapping MixedGraph::sizeArcs() More...
const ArcSet &	arcs () const
	wrapping MixedGraph::arcs() More...
Size	sizeEdges () const
	wrapping MixedGraph::sizeEdges() More...
const EdgeSet &	edges () const
	wrapping MixedGraph::edges() More...
Size	sizeNodes () const
	wrapping MixedGraph::sizeNodes() More...
Size	size () const
	wrapping MixedGraph::size() More...
UndiGraph	skeleton () const
const NodeGraphPart &	nodes () const
	wrapping MixedGraph::nodes() More...

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 independency 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 57 of file essentialGraph.h.

Constructor & Destructor Documentation

EssentialGraph() [1/4]

gum::EssentialGraph::EssentialGraph ( )

default

EssentialGraph() [2/4]

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

explicit

Definition at line 37 of file essentialGraph.cpp.

References __buildEssentialGraph().

                                                  : __dagmodel(&m) {
    __buildEssentialGraph();
  }

Here is the call graph for this function:

EssentialGraph() [3/4]

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

Definition at line 41 of file essentialGraph.cpp.

                                                                        :
      __dagmodel(&m), __mg(mg) {}

EssentialGraph() [4/4]

gum::EssentialGraph::EssentialGraph

(

const EssentialGraph &

g

)

Definition at line 43 of file essentialGraph.cpp.

References __buildEssentialGraph(), and __dagmodel.

                                                        {
    __dagmodel = g.__dagmodel;
    __buildEssentialGraph();
  }

Here is the call graph for this function:

~EssentialGraph()

gum::EssentialGraph::~EssentialGraph

(

)

Definition at line 55 of file essentialGraph.cpp.

{}

Member Function Documentation

__buildEssentialGraph()

void gum::EssentialGraph::__buildEssentialGraph ( )

private

Definition at line 57 of file essentialGraph.cpp.

References __dagmodel, __mg, __strongly_protected(), gum::DiGraph::addArc(), gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::DAGmodel::arcs(), gum::ArcGraphPart::children(), gum::MixedGraph::clear(), gum::ArcGraphPart::eraseArc(), gum::DAGmodel::nodes(), and gum::DAGmodel::topologicalOrder().

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

                                             {
    __mg.clear();
    if (__dagmodel == nullptr) return;

    for (const auto& node : __dagmodel->nodes()) {
      __mg.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(x, y)) v.push_back(Arc(x, y));
      for (const auto& arc : v) {
        __mg.eraseArc(arc);
        __mg.addEdge(arc.tail(), arc.head());
      }
    } while (v.size() > 0);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

__strongly_protected()

bool gum::EssentialGraph::__strongly_protected ( NodeId  a, NodeId  b  )

private

Definition at line 81 of file essentialGraph.cpp.

References __mg, gum::EdgeGraphPart::existsEdge(), gum::Set< Key, Alloc >::insert(), gum::EdgeGraphPart::neighbours(), gum::ArcGraphPart::parents(), size(), and gum::Set< Key, Alloc >::size().

Referenced by __buildEssentialGraph().

                                                              {
    // testing a->b from
    // A Characterization of Markov Equivalence Classes for Acyclic Digraphs (2001)
    //  Steen A. Andersson, David Madigan, and Michael D. Perlman*

    // condition (c)
    if ((__mg.parents(a) - __mg.parents(b)).size() > 0) { return true; }

    NodeSet cs;
    for (const auto& c : __mg.parents(b)) {
      // condition (b) & (c)
      if (c == a) { continue; }
      if (!__mg.existsEdge(c, a)) {
        return true;
      } else {
        cs.insert(c);
      }
    }

    // condition (d)
    NodeSet ss(cs);
    if (cs.size() < 2) {
      return false;
    } else {
      for (const auto& i : cs) {
        ss = ss - __mg.neighbours(i);
        if (ss.size() < 2) { return false; }
      }
      return true;
    }
  }

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 52 of file essentialGraph_inl.h.

References __mg, and gum::ArcGraphPart::arcs().

Referenced by skeleton().

{ return __mg.arcs(); }

Here is the call graph for this function:

Here is the caller graph for this function:

children()

INLINE const NodeSet & gum::EssentialGraph::children

(

const NodeId

id

)

const

wrapping MixedGraph::parents(id)

Definition at line 41 of file essentialGraph_inl.h.

References __mg, and gum::ArcGraphPart::children().

                                                                      {
    return __mg.children(id);
  }

Here is the call graph for this function:

edges()

INLINE const EdgeSet & gum::EssentialGraph::edges

(

)

const

wrapping MixedGraph::edges()

Definition at line 56 of file essentialGraph_inl.h.

References __mg, and gum::EdgeGraphPart::edges().

Referenced by skeleton().

{ return __mg.edges(); }

Here is the call graph for this function:

Here is the caller graph for this function:

mixedGraph()

INLINE MixedGraph gum::EssentialGraph::mixedGraph

(

)

Returns

a copy of the mixed graph

Definition at line 35 of file essentialGraph_inl.h.

References __mg.

{ return __mg; }

neighbours()

INLINE const NodeSet & gum::EssentialGraph::neighbours

(

const NodeId

id

)

const

wrapping MixedGraph::parents(id)

Definition at line 45 of file essentialGraph_inl.h.

References __mg, and gum::EdgeGraphPart::neighbours().

                                                                        {
    return __mg.neighbours(id);
  }

Here is the call graph for this function:

nodes()

INLINE const NodeGraphPart & gum::EssentialGraph::nodes

(

)

const

wrapping MixedGraph::nodes()

Definition at line 62 of file essentialGraph_inl.h.

References __mg, and gum::NodeGraphPart::nodes().

Referenced by skeleton().

                                                          {
    return __mg.nodes();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

operator=()

EssentialGraph & gum::EssentialGraph::operator=

(

const EssentialGraph &

g

)

Definition at line 47 of file essentialGraph.cpp.

References __buildEssentialGraph(), and __dagmodel.

                                                                   {
    if (&g != this) {
      __dagmodel = g.__dagmodel;
      __buildEssentialGraph();
    }
    return *this;
  }

Here is the call graph for this function:

parents()

INLINE const NodeSet & gum::EssentialGraph::parents

(

const NodeId

id

)

const

wrapping MixedGraph::parents(id)

Definition at line 37 of file essentialGraph_inl.h.

References __mg, and gum::ArcGraphPart::parents().

                                                                     {
    return __mg.parents(id);
  }

Here is the call graph for this function:

size()

INLINE Size gum::EssentialGraph::size

(

)

const

wrapping MixedGraph::size()

Definition at line 60 of file essentialGraph_inl.h.

References __mg, and gum::NodeGraphPart::size().

Referenced by __strongly_protected().

{ return __mg.size(); }

Here is the call graph for this function:

Here is the caller graph for this function:

sizeArcs()

INLINE Size gum::EssentialGraph::sizeArcs

(

)

const

wrapping MixedGraph::sizeArcs()

Definition at line 50 of file essentialGraph_inl.h.

References __mg, and gum::ArcGraphPart::sizeArcs().

{ return __mg.sizeArcs(); }

Here is the call graph for this function:

sizeEdges()

INLINE Size gum::EssentialGraph::sizeEdges

(

)

const

wrapping MixedGraph::sizeEdges()

Definition at line 54 of file essentialGraph_inl.h.

References __mg, and gum::EdgeGraphPart::sizeEdges().

{ return __mg.sizeEdges(); }

Here is the call graph for this function:

sizeNodes()

INLINE Size gum::EssentialGraph::sizeNodes

(

)

const

wrapping MixedGraph::sizeNodes()

Definition at line 58 of file essentialGraph_inl.h.

References __mg, and gum::NodeGraphPart::sizeNodes().

{ return __mg.sizeNodes(); }

Here is the call graph for this function:

skeleton()

UndiGraph gum::EssentialGraph::skeleton

(

)

const

Definition at line 146 of file essentialGraph.cpp.

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

                                           {
    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;
  }

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

References __dagmodel, __mg, gum::ArcGraphPart::children(), gum::List< Val, Alloc >::exists(), gum::List< Val, Alloc >::insert(), gum::Variable::name(), gum::EdgeGraphPart::neighbours(), gum::NodeGraphPart::nodes(), and gum::DAGmodel::variable().

                                        {
    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 : __mg.nodes()) {
        nodeStream << tab << node << "[label=\""
                   << __dagmodel->variable(node).name() << "\"];";

        for (const auto nei : __mg.neighbours(node))
          if (!treatedNodes.exists(nei))
            edgeStream << tab << node << " -> " << nei << " [dir=none];"
                       << std::endl;

        for (const auto chi : __mg.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();
  }

Here is the call graph for this function:

Member Data Documentation

__dagmodel

const DAGmodel* gum::EssentialGraph::__dagmodel

private

Definition at line 109 of file essentialGraph.h.

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

__mg

MixedGraph gum::EssentialGraph::__mg

private

Definition at line 110 of file essentialGraph.h.

Referenced by __buildEssentialGraph(), __strongly_protected(), arcs(), children(), edges(), mixedGraph(), neighbours(), nodes(), parents(), 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