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 (NodeId id) const
	wrapping MixedGraph::parents(id) More...
const NodeSet &	children (NodeId id) const
	wrapping MixedGraph::parents(id) More...
NodeSet	parents (const NodeSet &ids) const
	wrapping MixedGraph::parents(ids) More...
NodeSet	children (const NodeSet &ids) const
	wrapping MixedGraph::parents(ids) More...
const NodeSet &	neighbours (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 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 54 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 36 of file essentialGraph.cpp.

References gum::Set< Key, Alloc >::emplace().

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

References gum::Set< Key, Alloc >::emplace().

                                                                        :
      dagmodel__(&m), mg__(mg) {}

Here is the call graph for this function:

EssentialGraph() [4/4]

gum::EssentialGraph::EssentialGraph

(

const EssentialGraph &

g

)

Definition at line 42 of file essentialGraph.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                        {
    dagmodel__ = g.dagmodel__;
    buildEssentialGraph__();
  }

Here is the call graph for this function:

~EssentialGraph()

gum::EssentialGraph::~EssentialGraph ( )

default

Member Function Documentation

arcs()

INLINE const ArcSet & gum::EssentialGraph::arcs

(

)

const

wrapping MixedGraph::arcs()

Definition at line 59 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__.arcs(); }

Here is the call graph for this function:

buildEssentialGraph__()

void gum::EssentialGraph::buildEssentialGraph__ ( )

private

Definition at line 56 of file essentialGraph.cpp.

References gum::Set< Key, Alloc >::emplace().

                                             {
    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.emplace_back(x, y);

      for (const auto& arc: v) {
        mg__.eraseArc(arc);
        mg__.addEdge(arc.tail(), arc.head());
      }
    } while (!v.empty());
  }

Here is the call graph for this function:

children() [1/2]

INLINE const NodeSet & gum::EssentialGraph::children

(

NodeId

id

)

const

wrapping MixedGraph::parents(id)

Definition at line 40 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                {
    return mg__.children(id);
  }

Here is the call graph for this function:

children() [2/2]

INLINE NodeSet gum::EssentialGraph::children

(

const NodeSet &

ids

)

const

wrapping MixedGraph::parents(ids)

Definition at line 48 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                  {
    return mg__.children(ids);
  }

Here is the call graph for this function:

edges()

INLINE const EdgeSet & gum::EssentialGraph::edges

(

)

const

wrapping MixedGraph::edges()

Definition at line 63 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__.edges(); }

Here is the call graph for this function:

mixedGraph()

INLINE MixedGraph gum::EssentialGraph::mixedGraph

(

)

Returns

a copy of the mixed graph

Definition at line 34 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__; }

Here is the call graph for this function:

neighbours()

INLINE const NodeSet & gum::EssentialGraph::neighbours

(

NodeId

id

)

const

wrapping MixedGraph::parents(id)

Definition at line 52 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

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

References gum::Set< Key, Alloc >::emplace().

                                                          {
    return mg__.nodes();
  }

Here is the call graph for this function:

operator=()

EssentialGraph & gum::EssentialGraph::operator=

(

const EssentialGraph &

g

)

Definition at line 46 of file essentialGraph.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                   {
    if (&g != this) {
      dagmodel__ = g.dagmodel__;
      buildEssentialGraph__();
    }
    return *this;
  }

Here is the call graph for this function:

parents() [1/2]

INLINE const NodeSet & gum::EssentialGraph::parents

(

NodeId

id

)

const

wrapping MixedGraph::parents(id)

Definition at line 36 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                               {
    return mg__.parents(id);
  }

Here is the call graph for this function:

parents() [2/2]

INLINE NodeSet gum::EssentialGraph::parents

(

const NodeSet &

ids

)

const

wrapping MixedGraph::parents(ids)

Definition at line 44 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

                                                                 {
    return mg__.parents(ids);
  }

Here is the call graph for this function:

size()

INLINE Size gum::EssentialGraph::size

(

)

const

wrapping MixedGraph::size()

Definition at line 67 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__.size(); }

Here is the call graph for this function:

sizeArcs()

INLINE Size gum::EssentialGraph::sizeArcs

(

)

const

wrapping MixedGraph::sizeArcs()

Definition at line 57 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__.sizeArcs(); }

Here is the call graph for this function:

sizeEdges()

INLINE Size gum::EssentialGraph::sizeEdges

(

)

const

wrapping MixedGraph::sizeEdges()

Definition at line 61 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__.sizeEdges(); }

Here is the call graph for this function:

sizeNodes()

INLINE Size gum::EssentialGraph::sizeNodes

(

)

const

wrapping MixedGraph::sizeNodes()

Definition at line 65 of file essentialGraph_inl.h.

References gum::Set< Key, Alloc >::emplace().

{ return mg__.sizeNodes(); }

Here is the call graph for this function:

skeleton()

UndiGraph gum::EssentialGraph::skeleton

(

)

const

Definition at line 160 of file essentialGraph.cpp.

References gum::Set< Key, Alloc >::emplace().

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

strongly_protected__()

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

private

Definition at line 81 of file essentialGraph.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                              {
    // 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)) {
        // GUM_TRACE(a << "->" << b << " with "<<c<<" : (a)")
        return true;
      }
    }


    for (const auto& c: mg__.parents(b)) {
      if (c == a) { continue; }
      // condition (c)
      if (mg__.existsArc(a, c)) {
        // GUM_TRACE(a << "->" << b << " with "<<c<<" : (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)) {
        // GUM_TRACE(a << "->" << b << " with "<<c<<" : (b)")
        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
          // GUM_TRACE(a << "->" << b << " : (d)")
          return true;
        }
        oneFound = true;
      }
    }

    return false;
  }

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

References gum::Set< Key, Alloc >::emplace().

                                        {
    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 112 of file essentialGraph.h.

mg__

MixedGraph gum::EssentialGraph::mg__

private

Definition at line 113 of file essentialGraph.h.

---

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