aGrUM  0.15.1
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 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().

37  : __dagmodel(&m) {
39  }
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 41 of file essentialGraph.cpp.

41  :
42  __dagmodel(&m), __mg(mg) {}
const DAGmodel * __dagmodel

◆ EssentialGraph() [4/4]

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

Definition at line 43 of file essentialGraph.cpp.

References __buildEssentialGraph(), and __dagmodel.

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

◆ ~EssentialGraph()

gum::EssentialGraph::~EssentialGraph ( )

Definition at line 55 of file essentialGraph.cpp.

55 {}

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=().

57  {
58  __mg.clear();
59  if (__dagmodel == nullptr) return;
60 
61  for (const auto& node : __dagmodel->nodes()) {
62  __mg.addNodeWithId(node);
63  }
64  for (const auto& arc : __dagmodel->arcs()) {
65  __mg.addArc(arc.tail(), arc.head());
66  }
67 
68  std::vector< Arc > v;
69  do {
70  v.clear();
71  for (const auto x : __dagmodel->topologicalOrder())
72  for (const auto y : __mg.children(x))
73  if (!__strongly_protected(x, y)) v.push_back(Arc(x, y));
74  for (const auto& arc : v) {
75  __mg.eraseArc(arc);
76  __mg.addEdge(arc.tail(), arc.head());
77  }
78  } while (v.size() > 0);
79  }
const ArcSet & arcs() const
returns the set of nodes with arc ingoing to a given node
Definition: DAGmodel_inl.h:104
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:35
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:35
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:117
const NodeGraphPart & nodes() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:115
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 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().

81  {
82  // testing a->b from
83  // A Characterization of Markov Equivalence Classes for Acyclic Digraphs (2001)
84  // Steen A. Andersson, David Madigan, and Michael D. Perlman*
85 
86  // condition (c)
87  if ((__mg.parents(a) - __mg.parents(b)).size() > 0) { return true; }
88 
89  NodeSet cs;
90  for (const auto& c : __mg.parents(b)) {
91  // condition (b) & (c)
92  if (c == a) { continue; }
93  if (!__mg.existsEdge(c, a)) {
94  return true;
95  } else {
96  cs.insert(c);
97  }
98  }
99 
100  // condition (d)
101  NodeSet ss(cs);
102  if (cs.size() < 2) {
103  return false;
104  } else {
105  for (const auto& i : cs) {
106  ss = ss - __mg.neighbours(i);
107  if (ss.size() < 2) { return false; }
108  }
109  return true;
110  }
111  }
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:613
+ 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().

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

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

41  {
42  return __mg.children(id);
43  }
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 56 of file essentialGraph_inl.h.

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

Referenced by skeleton().

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

References __mg.

35 { 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().

45  {
46  return __mg.neighbours(id);
47  }
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 62 of file essentialGraph_inl.h.

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

Referenced by skeleton().

62  {
63  return __mg.nodes();
64  }
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 47 of file essentialGraph.cpp.

References __buildEssentialGraph(), and __dagmodel.

47  {
48  if (&g != this) {
49  __dagmodel = g.__dagmodel;
51  }
52  return *this;
53  }
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 37 of file essentialGraph_inl.h.

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

37  {
38  return __mg.parents(id);
39  }
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 60 of file essentialGraph_inl.h.

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

Referenced by __strongly_protected().

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

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

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

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

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

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

58 { 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 146 of file essentialGraph.cpp.

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

146  {
147  UndiGraph skel;
148  for (const auto& n : nodes())
149  skel.addNodeWithId(n);
150  for (const auto& edge : edges())
151  skel.addEdge(edge.first(), edge.second());
152  for (const auto& arc : arcs())
153  skel.addEdge(arc.tail(), arc.head());
154  return skel;
155  }
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 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().

113  {
114  std::stringstream output;
115  std::stringstream nodeStream;
116  std::stringstream edgeStream;
117  List< NodeId > treatedNodes;
118  output << "digraph \""
119  << "no_name\" {" << std::endl;
120  nodeStream << "node [shape = ellipse];" << std::endl;
121  std::string tab = " ";
122  if (__dagmodel != nullptr) {
123  for (const auto node : __mg.nodes()) {
124  nodeStream << tab << node << "[label=\""
125  << __dagmodel->variable(node).name() << "\"];";
126 
127  for (const auto nei : __mg.neighbours(node))
128  if (!treatedNodes.exists(nei))
129  edgeStream << tab << node << " -> " << nei << " [dir=none];"
130  << std::endl;
131 
132  for (const auto chi : __mg.children(node))
133  edgeStream << tab << node << " -> " << chi << " [color=red];"
134  << std::endl;
135 
136  treatedNodes.insert(node);
137  }
138  }
139  output << nodeStream.str() << std::endl
140  << edgeStream.str() << std::endl
141  << "}" << std::endl;
142 
143  return output.str();
144  }
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 109 of file essentialGraph.h.

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

◆ __mg


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