aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
gum::EssentialGraph Class Reference

Class building the essential graph from a BN. More...

#include <agrum/BN/algorithms/essentialGraph.h>

Collaboration diagram for gum::EssentialGraph:
[legend]

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
std::string toDot (const dot::DotOptions &options) 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)
NodeSet descendants (NodeId id) const
 wrapping PDAG::descendants(id)
NodeSet ancestors (NodeId id) const
 wrapping PDAG::ancestors(id)
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()
NodeProperty< NodeId > connectedComponents () const
 Returns the connected components of the essential graph. Each node maps to the id of its component root.
NodeId idFromName (std::string_view 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 80 of file essentialGraph.h.

Constructor & Destructor Documentation

◆ EssentialGraph() [1/4]

gum::EssentialGraph::EssentialGraph ( )
default

References EssentialGraph(), and operator=().

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

const DAGmodel * _dagmodel_

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

59: _dagmodel_(&m), _pdag_(mg) {}

References _dagmodel_, and _pdag_.

◆ EssentialGraph() [4/4]

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

Definition at line 61 of file essentialGraph.cpp.

61 {
62 _dagmodel_ = g._dagmodel_;
64 }

References EssentialGraph(), _buildEssentialGraph_(), and _dagmodel_.

Here is the call graph for this function:

◆ ~EssentialGraph()

gum::EssentialGraph::~EssentialGraph ( )
default

References _buildEssentialGraph_(), _strongly_protected_(), ancestors(), arcs(), children(), connectedComponents(), descendants(), edges(), idFromName(), nameFromId(), neighbours(), nodes(), parents(), pdag(), size(), sizeArcs(), sizeEdges(), sizeNodes(), skeleton(), and toDot().

Here is the call graph for this function:

Member Function Documentation

◆ _buildEssentialGraph_()

void gum::EssentialGraph::_buildEssentialGraph_ ( )
private

Definition at line 76 of file essentialGraph.cpp.

76 {
77 MixedGraph mg; // during the process, the graph may not be a PDAG
78 _pdag_.clear();
79 if (_dagmodel_ == nullptr) return;
80
81 for (const auto& node: _dagmodel_->nodes()) {
82 mg.addNodeWithId(node);
84 }
85 for (const auto& arc: _dagmodel_->arcs()) {
86 mg.addArc(arc.tail(), arc.head());
87 }
88
89 std::vector< Arc > v;
90 do {
91 v.clear();
92 for (const auto x: _dagmodel_->topologicalOrder())
93 for (const auto y: mg.children(x))
94 if (!_strongly_protected_(mg, x, y)) v.emplace_back(x, y);
95
96 for (const auto& arc: v) {
97 mg.eraseArc(arc);
98 mg.addEdge(arc.tail(), arc.head());
99 }
100 } while (!v.empty());
101
102 for (const auto& arc: mg.arcs()) {
103 _pdag_.addArc(arc.tail(), arc.head());
104 }
105 for (const auto& edge: mg.edges()) {
106 _pdag_.addEdge(edge.first(), edge.second());
107 }
108
109 for (auto id: _pdag_)
110 _pdag_.setName(id, _dagmodel_->variable(id).name());
111 }
const ArcSet & arcs() const
return true if the arc tail->head exists in the DAGmodel
Sequence< NodeId > topologicalOrder() const
The topological order stays the same as long as no variable or arcs are added or erased src the topol...
const NodeGraphPart & nodes() const final
Returns a named copy of the internal DAG: each node id is assigned the name of the corresponding vari...
const DiscreteVariable & variable(NodeId id) const override
Returns a constant reference over a variable given its node id.
bool _strongly_protected_(NodeId a, NodeId b) const
void clear() override
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
void addEdge(NodeId first, NodeId second) final
insert a new edge into the partially directed graph
Definition PDAG_inl.h:93
void addArc(NodeId tail, NodeId head) final
insert a new arc into the directed graph
Definition PDAG_inl.h:75
const std::string & name() const
returns the name of the variable

References _dagmodel_, _pdag_, _strongly_protected_(), gum::DiGraph::addArc(), gum::PDAG::addArc(), gum::PDAG::addEdge(), gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::ArcGraphPart::arcs(), gum::DAGmodel::arcs(), gum::ArcGraphPart::children(), gum::MixedGraph::clear(), gum::EdgeGraphPart::edges(), gum::ArcGraphPart::eraseArc(), gum::Variable::name(), gum::DAGmodel::nodes(), gum::DAGmodel::topologicalOrder(), and gum::DiscreteGraphicalModel::variable().

Referenced by EssentialGraph(), 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 117 of file essentialGraph.cpp.

117 {
118 // testing a->b from
119 // A Characterization of Markov Equivalence Classes for Acyclic Digraphs (2001)
120 // Steen A. Andersson, David Madigan, and Michael D. Perlman*
121
122 // condition (a)
123 for (const auto& c: mg.parents(a)) {
124 if (!mg.existsArc(c, b)) { return true; }
125 }
126
127
128 for (const auto& c: mg.parents(b)) {
129 if (c == a) { continue; }
130 // condition (c)
131 if (mg.existsArc(a, c)) { return true; }
132
133 // condition (b) knowing that a can not be a parent of c (condition below)
134 if (!mg.existsEdge(a, c) && !mg.existsArc(c, a)) { return true; }
135 }
136
137 // condition (d)
138 bool oneFound = false;
139 for (const auto& c: mg.parents(b)) {
140 if (c == a) { continue; }
141 // condition (d)
142 if (mg.existsEdge(c, a)) {
143 if (oneFound) { // this is the second found
144 return true;
145 }
146 oneFound = true;
147 }
148 }
149
150 return false;
151 }

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

113 {
114 return _strongly_protected_(_pdag_, a, b);
115 }

References _pdag_, and _strongly_protected_().

Referenced by ~EssentialGraph(), _buildEssentialGraph_(), and _strongly_protected_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ancestors()

INLINE NodeSet gum::EssentialGraph::ancestors ( NodeId id) const

wrapping PDAG::ancestors(id)

Definition at line 68 of file essentialGraph_inl.h.

68{ return _pdag_.ancestors(id); }
NodeSet ancestors(NodeId id) const
returns the set of all ancestors of id (nodes from which id is reachable)

References _pdag_, and gum::DiGraph::ancestors().

Referenced by ~EssentialGraph().

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

76{ return _pdag_.arcs(); }
const ArcSet & arcs() const
returns the set of arcs stored within the ArcGraphPart

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

Referenced by ~EssentialGraph(), and skeleton().

Here is the call graph for this function:
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 64 of file essentialGraph_inl.h.

64{ return _pdag_.children(ids); }
NodeSet children(const NodeSet &ids) const
returns the set of nodes which consists in the node and its parents returns the set of children of a ...

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

Here is the call graph for this function:

◆ children() [2/2]

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

wrapping MixedGraph::parents(id)

Definition at line 60 of file essentialGraph_inl.h.

60{ return _pdag_.children(id); }

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

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ connectedComponents()

INLINE NodeProperty< NodeId > gum::EssentialGraph::connectedComponents ( ) const

Returns the connected components of the essential graph. Each node maps to the id of its component root.

Definition at line 96 of file essentialGraph_inl.h.

96 {
98 }
NodeProperty< NodeId > connectedComponents() const
returns a property {node:id of weakly connected component}

References _pdag_, and gum::MixedGraph::connectedComponents().

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ descendants()

INLINE NodeSet gum::EssentialGraph::descendants ( NodeId id) const

wrapping PDAG::descendants(id)

Definition at line 66 of file essentialGraph_inl.h.

66{ return _pdag_.descendants(id); }
NodeSet descendants(NodeId id) const
returns the set of all descendants of id (nodes reachable from id)

References _pdag_, and gum::DiGraph::descendants().

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ edges()

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

wrapping MixedGraph::edges()

Definition at line 80 of file essentialGraph_inl.h.

80{ return _pdag_.edges(); }
const EdgeSet & edges() const
returns the set of edges stored within the EdgeGraphPart

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

Referenced by ~EssentialGraph(), and skeleton().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ idFromName()

INLINE NodeId gum::EssentialGraph::idFromName ( std::string_view name) const

wrappping DAGModel::idFromName()

Definition at line 88 of file essentialGraph_inl.h.

88 {
89 return _dagmodel_->idFromName(name);
90 }
NodeId idFromName(std::string_view name) const override
Returns the NodeId of a variable given its name.

References _dagmodel_, and gum::DiscreteGraphicalModel::idFromName().

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ nameFromId()

INLINE const std::string & gum::EssentialGraph::nameFromId ( NodeId node) const

wrappping .name()

Definition at line 92 of file essentialGraph_inl.h.

92 {
93 return _dagmodel_->variable(node).name();
94 }

References _dagmodel_, gum::Variable::name(), and gum::DiscreteGraphicalModel::variable().

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ neighbours()

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

wrapping MixedGraph::parents(id)

Definition at line 70 of file essentialGraph_inl.h.

70 {
71 return _pdag_.neighbours(id);
72 }
const NodeSet & neighbours(NodeId id) const
returns the set of node neighbours to a given node

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

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ nodes()

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

wrapping MixedGraph::nodes()

Definition at line 86 of file essentialGraph_inl.h.

86{ return _pdag_.nodes(); }
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart

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

Referenced by ~EssentialGraph(), and skeleton().

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

66 {
67 if (&g != this) {
68 _dagmodel_ = g._dagmodel_;
70 }
71 return *this;
72 }

References EssentialGraph(), _buildEssentialGraph_(), and _dagmodel_.

Referenced by EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ parents() [1/2]

INLINE NodeSet gum::EssentialGraph::parents ( const NodeSet & ids) const

wrapping MixedGraph::parents(ids)

Definition at line 62 of file essentialGraph_inl.h.

62{ return _pdag_.parents(ids); }
const NodeSet & parents(NodeId id) const
returns the set of nodes with arc ingoing to a given node

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

Here is the call graph for this function:

◆ parents() [2/2]

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

wrapping MixedGraph::parents(id)

Definition at line 58 of file essentialGraph_inl.h.

58{ return _pdag_.parents(id); }

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

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ pdag()

INLINE PDAG gum::EssentialGraph::pdag ( ) const
Returns
a copy of the mixed graph

Definition at line 56 of file essentialGraph_inl.h.

56{ return _pdag_; }

References _pdag_.

Referenced by ~EssentialGraph().

Here is the caller graph for this function:

◆ size()

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

wrapping MixedGraph::size()

Definition at line 84 of file essentialGraph_inl.h.

84{ return _pdag_.size(); }
Size size() const
alias for sizeNodes

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

Referenced by ~EssentialGraph().

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

74{ return _pdag_.sizeArcs(); }
Size sizeArcs() const
indicates the number of arcs stored within the ArcGraphPart

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

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ sizeEdges()

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

wrapping MixedGraph::sizeEdges()

Definition at line 78 of file essentialGraph_inl.h.

78{ return _pdag_.sizeEdges(); }
Size sizeEdges() const
indicates the number of edges stored within the EdgeGraphPart

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

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ sizeNodes()

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

wrapping MixedGraph::sizeNodes()

Definition at line 82 of file essentialGraph_inl.h.

82{ return _pdag_.sizeNodes(); }
Size sizeNodes() const
returns the number of nodes in the NodeGraphPart

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

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ skeleton()

UndiGraph gum::EssentialGraph::skeleton ( ) const

Definition at line 187 of file essentialGraph.cpp.

187 {
188 UndiGraph skel;
189 for (const auto& n: nodes())
190 skel.addNodeWithId(n);
191 for (const auto& edge: edges())
192 skel.addEdge(edge.first(), edge.second());
193 for (const auto& arc: arcs())
194 skel.addEdge(arc.tail(), arc.head());
195 if (_dagmodel_ != nullptr)
196 for (auto id: skel)
197 skel.setName(id, _dagmodel_->variable(id).name());
198 return skel;
199 }
const ArcSet & arcs() const
wrapping MixedGraph::arcs()
const NodeGraphPart & nodes() const
wrapping MixedGraph::nodes()
const EdgeSet & edges() const
wrapping MixedGraph::edges()

References _dagmodel_, gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), arcs(), edges(), gum::Variable::name(), nodes(), gum::NodeGraphPart::setName(), and gum::DiscreteGraphicalModel::variable().

Referenced by ~EssentialGraph().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ toDot() [1/2]

std::string gum::EssentialGraph::toDot ( ) const
Returns
a dot representation of this essentialGraph

Definition at line 153 of file essentialGraph.cpp.

153{ return toDot(dot::DotOptions()); }
std::string toDot() const

References toDot().

Referenced by ~EssentialGraph(), and toDot().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ toDot() [2/2]

std::string gum::EssentialGraph::toDot ( const dot::DotOptions & options) const
Returns
a dot representation of this essentialGraph, with the options given by the caller

Definition at line 155 of file essentialGraph.cpp.

155 {
156 const auto style = dot::DotStyle::read();
157 dot::DotWriter writer(true);
158 dot::writePreamble(writer, style, options);
159
160 if (_dagmodel_ != nullptr) {
161 for (const auto node: _pdag_.nodes()) {
162 const auto& name = _dagmodel_->variable(node).name();
163 writer.node(node,
165 options.node(node),
166 name,
167 "(" + std::to_string(node) + ") " + name));
168 }
169
170 for (const auto& edge: _pdag_.edges()) {
171 auto attributes = dot::arcAttributes(options.edge(edge.first(), edge.second()));
172 attributes.insert(attributes.begin(), {"dir", "none"});
173 writer.edge(edge.first(), edge.second(), attributes);
174 }
175
176 // the arcs which are in every DAG of the equivalence class are in red
177 for (const auto& arc: _pdag_.arcs()) {
178 auto attributes = dot::arcAttributes(options.arc(arc.tail(), arc.head()));
179 dot::addDefaultAttribute(attributes, "color", "red");
180 writer.edge(arc.tail(), arc.head(), attributes);
181 }
182 }
183
184 return writer.str();
185 }
DotAttributes nodeAttributes(const DotStyle &style, const DotNodeOptions *options, std::string_view defaultLabel, std::string_view defaultTooltip)
The attributes of a node : its label and tooltip, and its colors if the options give some.
void writePreamble(DotWriter &writer, const DotStyle &style, const DotOptions &options, std::string_view defaultLabel)
Writes the beginning of a graph, as pyAgrum displays it.
void addDefaultAttribute(DotAttributes &attributes, std::string_view key, std::string_view value)
Adds an attribute at the beginning of the list, unless the list already gives a value for this key : ...
DotAttributes arcAttributes(const DotArcOptions *options)
The attributes of an arc or an edge given by the options : color, penwidth, label,...
static DotStyle read()
the style of the graphs of the section notebook
Definition dotStyle.cpp:89

References _dagmodel_, _pdag_, gum::dot::addDefaultAttribute(), gum::dot::DotOptions::arc(), gum::dot::arcAttributes(), gum::ArcGraphPart::arcs(), gum::dot::DotOptions::edge(), gum::dot::DotWriter::edge(), gum::EdgeGraphPart::edges(), gum::Variable::name(), gum::dot::DotOptions::node(), gum::dot::DotWriter::node(), gum::dot::nodeAttributes(), gum::NodeGraphPart::nodes(), gum::dot::DotStyle::read(), gum::dot::DotWriter::str(), gum::DiscreteGraphicalModel::variable(), and gum::dot::writePreamble().

Here is the call graph for this function:

Member Data Documentation

◆ _dagmodel_

const DAGmodel* gum::EssentialGraph::_dagmodel_
private

◆ _pdag_


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