aGrUM  0.14.3
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)
 
EssentialGraphoperator= (const EssentialGraph &g)
 
 ~EssentialGraph ()
 
MixedGraph mixedGraph ()
 
std::string toDot () const
 
const NodeSetparents (const NodeId id) const
 wrapping MixedGraph::parents(id) More...
 
const NodeSetchildren (const NodeId id) const
 wrapping MixedGraph::parents(id) More...
 
const NodeSetneighbours (const NodeId id) const
 wrapping MixedGraph::parents(id) More...
 
Size sizeArcs () const
 wrapping MixedGraph::sizeArcs() More...
 
const ArcSetarcs () const
 wrapping MixedGraph::arcs() More...
 
Size sizeEdges () const
 wrapping MixedGraph::sizeEdges() More...
 
const EdgeSetedges () const
 wrapping MixedGraph::edges() More...
 
Size sizeNodes () const
 wrapping MixedGraph::sizeNodes() More...
 
Size size () const
 wrapping MixedGraph::size() More...
 
UndiGraph skeleton () const
 
const NodeGraphPartnodes () 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 55 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 34 of file essentialGraph.cpp.

References __buildEssentialGraph().

34  : __dagmodel(&m) {
36  }
const DAGmodel * __dagmodel
+ Here is the call graph for this function:

◆ EssentialGraph() [3/4]

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

Definition at line 38 of file essentialGraph.cpp.

38  :
39  __dagmodel(&m), __mg(mg) {}
const DAGmodel * __dagmodel

◆ EssentialGraph() [4/4]

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

Definition at line 40 of file essentialGraph.cpp.

References __buildEssentialGraph(), and __dagmodel.

40  {
41  __dagmodel = g.__dagmodel;
43  }
const DAGmodel * __dagmodel
+ Here is the call graph for this function:

◆ ~EssentialGraph()

gum::EssentialGraph::~EssentialGraph ( )

Definition at line 52 of file essentialGraph.cpp.

52 {}

Member Function Documentation

◆ __buildEssentialGraph()

void gum::EssentialGraph::__buildEssentialGraph ( )
private

Definition at line 54 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=().

54  {
55  __mg.clear();
56  if (__dagmodel == nullptr) return;
57 
58  for (const auto& node : __dagmodel->nodes()) {
59  __mg.addNodeWithId(node);
60  }
61  for (const auto& arc : __dagmodel->arcs()) {
62  __mg.addArc(arc.tail(), arc.head());
63  }
64 
65  std::vector< Arc > v;
66  do {
67  v.clear();
68  for (const auto x : __dagmodel->topologicalOrder())
69  for (const auto y : __mg.children(x))
70  if (!__strongly_protected(x, y)) v.push_back(Arc(x, y));
71  for (const auto& arc : v) {
72  __mg.eraseArc(arc);
73  __mg.addEdge(arc.tail(), arc.head());
74  }
75  } while (v.size() > 0);
76  }
const ArcSet & arcs() const
returns the set of nodes with arc ingoing to a given node
Definition: DAGmodel_inl.h:101
virtual void clear()
removes all the nodes, arcs and edges from the graph
virtual void addNodeWithId(const NodeId id)
try to insert a node with the given id
virtual void addArc(const NodeId tail, const NodeId head)
insert a new arc into the directed graph
Definition: diGraph_inl.h:32
virtual void eraseArc(const Arc &arc)
removes an arc from the ArcGraphPart
virtual void addEdge(const NodeId first, const NodeId second)
insert a new edge into the undirected graph
Definition: undiGraph_inl.h:32
bool __strongly_protected(NodeId a, NodeId b)
const DAGmodel * __dagmodel
const Sequence< NodeId > & topologicalOrder(bool clear=true) const
The topological order stays the same as long as no variable or arcs are added or erased src the topol...
Definition: DAGmodel.cpp:115
const NodeGraphPart & nodes() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:112
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
+ 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 78 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().

78  {
79  // testing a->b from
80  // A Characterization of Markov Equivalence Classes for Acyclic Digraphs (2001)
81  // Steen A. Andersson, David Madigan, and Michael D. Perlman*
82 
83  // condition (c)
84  if ((__mg.parents(a) - __mg.parents(b)).size() > 0) { return true; }
85 
86  NodeSet cs;
87  for (const auto& c : __mg.parents(b)) {
88  // condition (b) & (c)
89  if (c == a) { continue; }
90  if (!__mg.existsEdge(c, a)) {
91  return true;
92  } else {
93  cs.insert(c);
94  }
95  }
96 
97  // condition (d)
98  NodeSet ss(cs);
99  if (cs.size() < 2) {
100  return false;
101  } else {
102  for (const auto& i : cs) {
103  ss = ss - __mg.neighbours(i);
104  if (ss.size() < 2) { return false; }
105  }
106  return true;
107  }
108  }
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
Size size() const
wrapping MixedGraph::size()
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:610
+ 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 49 of file essentialGraph_inl.h.

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

Referenced by skeleton().

49 { return __mg.arcs(); }
const ArcSet & arcs() const
returns the set of arcs stored within the ArcGraphPart
+ 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 38 of file essentialGraph_inl.h.

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

38  {
39  return __mg.children(id);
40  }
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
+ Here is the call graph for this function:

◆ edges()

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

wrapping MixedGraph::edges()

Definition at line 53 of file essentialGraph_inl.h.

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

Referenced by skeleton().

53 { return __mg.edges(); }
const EdgeSet & edges() const
returns the set of edges stored within the EdgeGraphPart
+ 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 32 of file essentialGraph_inl.h.

References __mg.

32 { return __mg; }

◆ neighbours()

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

wrapping MixedGraph::parents(id)

Definition at line 42 of file essentialGraph_inl.h.

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

42  {
43  return __mg.neighbours(id);
44  }
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
+ Here is the call graph for this function:

◆ nodes()

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

wrapping MixedGraph::nodes()

Definition at line 59 of file essentialGraph_inl.h.

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

Referenced by skeleton().

59  {
60  return __mg.nodes();
61  }
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
+ 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 44 of file essentialGraph.cpp.

References __buildEssentialGraph(), and __dagmodel.

44  {
45  if (&g != this) {
46  __dagmodel = g.__dagmodel;
48  }
49  return *this;
50  }
const DAGmodel * __dagmodel
+ 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 34 of file essentialGraph_inl.h.

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

34  {
35  return __mg.parents(id);
36  }
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
+ Here is the call graph for this function:

◆ size()

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

wrapping MixedGraph::size()

Definition at line 57 of file essentialGraph_inl.h.

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

Referenced by __strongly_protected().

57 { return __mg.size(); }
Size size() const
alias for sizeNodes
+ 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 47 of file essentialGraph_inl.h.

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

47 { return __mg.sizeArcs(); }
Size sizeArcs() const
indicates the number of arcs stored within the ArcGraphPart
+ Here is the call graph for this function:

◆ sizeEdges()

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

wrapping MixedGraph::sizeEdges()

Definition at line 51 of file essentialGraph_inl.h.

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

51 { return __mg.sizeEdges(); }
Size sizeEdges() const
indicates the number of edges stored within the EdgeGraphPart
+ Here is the call graph for this function:

◆ sizeNodes()

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

wrapping MixedGraph::sizeNodes()

Definition at line 55 of file essentialGraph_inl.h.

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

55 { return __mg.sizeNodes(); }
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart
+ Here is the call graph for this function:

◆ skeleton()

UndiGraph gum::EssentialGraph::skeleton ( ) const

Definition at line 143 of file essentialGraph.cpp.

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

143  {
144  UndiGraph skel;
145  for (const auto& n : nodes())
146  skel.addNodeWithId(n);
147  for (const auto& edge : edges())
148  skel.addEdge(edge.first(), edge.second());
149  for (const auto& arc : arcs())
150  skel.addEdge(arc.tail(), arc.head());
151  return skel;
152  }
const NodeGraphPart & nodes() const
wrapping MixedGraph::nodes()
const EdgeSet & edges() const
wrapping MixedGraph::edges()
const ArcSet & arcs() const
wrapping MixedGraph::arcs()
+ 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 110 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().

110  {
111  std::stringstream output;
112  std::stringstream nodeStream;
113  std::stringstream edgeStream;
114  List< NodeId > treatedNodes;
115  output << "digraph \""
116  << "no_name\" {" << std::endl;
117  nodeStream << "node [shape = ellipse];" << std::endl;
118  std::string tab = " ";
119  if (__dagmodel != nullptr) {
120  for (const auto node : __mg.nodes()) {
121  nodeStream << tab << node << "[label=\""
122  << __dagmodel->variable(node).name() << "\"];";
123 
124  for (const auto nei : __mg.neighbours(node))
125  if (!treatedNodes.exists(nei))
126  edgeStream << tab << node << " -> " << nei << " [dir=none];"
127  << std::endl;
128 
129  for (const auto chi : __mg.children(node))
130  edgeStream << tab << node << " -> " << chi << " [color=red];"
131  << std::endl;
132 
133  treatedNodes.insert(node);
134  }
135  }
136  output << nodeStream.str() << std::endl
137  << edgeStream.str() << std::endl
138  << "}" << std::endl;
139 
140  return output.str();
141  }
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
const DAGmodel * __dagmodel
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
virtual const DiscreteVariable & variable(NodeId id) const =0
Returns a constant reference over a variabe given it&#39;s node id.
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
const std::string & name() const
returns the name of the variable
+ Here is the call graph for this function:

Member Data Documentation

◆ __dagmodel

const DAGmodel* gum::EssentialGraph::__dagmodel
private

Definition at line 107 of file essentialGraph.h.

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

◆ __mg


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