aGrUM  0.18.1
a C++ library for (probabilistic) graphical models
DAGmodel.cpp
Go to the documentation of this file.
1 
24 
25 #ifdef GUM_NO_INLINE
27 #endif /* GUM_NO_INLINE */
28 
29 namespace gum {
30  DAGmodel::DAGmodel() : mutableMoralGraph__(nullptr) {
31  GUM_CONSTRUCTOR(DAGmodel);
32  }
33 
35  dag_(from.dag_), mutableMoralGraph__(nullptr) {
36  GUM_CONS_CPY(DAGmodel);
37  }
38 
40  GUM_DESTRUCTOR(DAGmodel);
42  }
43 
44  void DAGmodel::moralGraph__() const {
46  // transform the arcs into edges
47 
48  for (const auto& arc: arcs())
49  mutableMoralGraph__->addEdge(arc.first(), arc.second());
50 
51  //}
52 
53  // marry the parents
54  for (const auto node: nodes()) {
55  const auto& par = parents(node);
56 
57  for (auto it1 = par.begin(); it1 != par.end(); ++it1) {
58  auto it2 = it1;
59 
60  for (++it2; it2 != par.end(); ++it2) {
61  // will automatically check if this edge already exists
62  mutableMoralGraph__->addEdge(*it1, *it2);
63  }
64  }
65  }
66  }
67 
69  if (this != &source) {
71 
72  if (mutableMoralGraph__) {
73  delete mutableMoralGraph__;
74  mutableMoralGraph__ = nullptr;
75  }
76  dag_ = source.dag_;
77  }
78 
79  return *this;
80  }
81 
82  const UndiGraph& DAGmodel::moralGraph(bool clear) const {
83  if (clear
84  || (mutableMoralGraph__ == nullptr)) { // we have to call moralGraph_
85  if (mutableMoralGraph__ == nullptr) {
87  } else {
88  // clear is True ,__mutableMoralGraph exists
90  }
91 
92  moralGraph__();
93  }
94 
95  return *mutableMoralGraph__;
96  }
97 
99  return this->dag().topologicalOrder(clear);
100  }
101 
103  if (this == &other) return true;
104 
105  if (size() != other.size()) return false;
106 
107  if (sizeArcs() != other.sizeArcs()) return false;
108 
109  for (const auto& nid: nodes()) {
110  try {
111  other.idFromName(variable(nid).name());
112  } catch (NotFound) { return false; }
113  }
114 
115  for (const auto& arc: arcs()) {
116  if (!other.arcs().exists(Arc(other.idFromName(variable(arc.tail()).name()),
117  other.idFromName(variable(arc.head()).name()))))
118  return false;
119  }
120 
121  return true;
122  }
123 
125  NodeSet res;
126  NodeSet tmp;
127  for (auto next: children(id))
128  tmp.insert(next);
129 
130  while (!tmp.empty()) {
131  auto current = *(tmp.begin());
132  tmp.erase(current);
133  res.insert(current);
134  for (auto next: children(current)) {
135  if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
136  }
137  }
138  return res;
139  }
140 
141  NodeSet DAGmodel::descendants(const std::string& name) const {
142  return descendants(idFromName(name));
143  }
144 
146  NodeSet res;
147  NodeSet tmp;
148  for (auto next: parents(id))
149  tmp.insert(next);
150 
151  while (!tmp.empty()) {
152  auto current = *(tmp.begin());
153  tmp.erase(current);
154  res.insert(current);
155  for (auto next: parents(current)) {
156  if (!tmp.contains(next) && !res.contains(next)) { tmp.insert(next); }
157  }
158  }
159  return res;
160  }
161 
162  NodeSet DAGmodel::ancestors(const std::string& name) const {
163  return ancestors(idFromName(name));
164  }
165 
167  UndiGraph res;
168  NodeSet tmp{nodes};
169 
170  // findings all nodes
171  while (!tmp.empty()) {
172  auto current = *(tmp.begin());
173  tmp.erase(current);
174 
175  res.addNodeWithId(current);
176  for (auto next: parents(current))
177  if (!tmp.contains(next) && !res.exists(next)) tmp.insert(next);
178  }
179 
180  // finding all edges and moralizing
181  for (auto current: res)
182  for (auto father: parents(current)) {
183  res.addEdge(current,
184  father); // addEdge does not complain if edge already exists
185  for (auto other_father: parents(current))
186  if (other_father != father) res.addEdge(father, other_father);
187  }
188 
189  return res;
190  }
191 
193  const std::vector< std::string >& nodenames) const {
194  NodeSet nodes;
195  for (const auto& name: nodenames)
196  nodes.insert(idFromName(name));
197  return moralizedAncestralGraph(nodes);
198  }
199 
200  bool DAGmodel::isIndependent(NodeId X, NodeId Y, const NodeSet& Z) const {
201  NodeSet cumul{Z};
202  cumul << X << Y;
203  auto g = moralizedAncestralGraph(cumul);
204  for (auto node: Z)
205  g.eraseNode(node);
206  return !g.hasUndirectedPath(X, Y);
207  }
208 
209  bool DAGmodel::isIndependent(const std::string& Xname,
210  const std::string& Yname,
211  const std::vector< std::string >& Znames) const {
212  NodeSet Z;
213  for (const auto& name: Znames)
214  Z.insert(idFromName(name));
215  return isIndependent(idFromName(Xname), idFromName(Yname), Z);
216  }
217 } // namespace gum
DAGmodel & operator=(const DAGmodel &source)
Private copy operator.
Definition: DAGmodel.cpp:68
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:581
const ArcSet & arcs() const
return true if the arc tail->head exists in the DAGmodel
Definition: DAGmodel_inl.h:44
virtual void clear()
removes all the nodes and edges from the graph
Definition: undiGraph_inl.h:47
virtual void addNodeWithId(const NodeId id)
try to insert a node with the given id
Virtual base class for PGMs using a DAG.
Definition: DAGmodel.h:47
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
Definition: DAGmodel_inl.h:63
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
Definition: DAGmodel_inl.h:55
UndiGraph moralizedAncestralGraph(const NodeSet &nodes) const
build a UndiGraph by moralizing the Ancestral Graph of a set of Nodes
Definition: DAGmodel.cpp:166
Size sizeArcs() const
Returns the number of arcs in this Directed Graphical Model.
Definition: DAGmodel_inl.h:42
virtual void addEdge(const NodeId first, const NodeId second)
insert a new edge into the undirected graph
Definition: undiGraph_inl.h:35
virtual Size size() const final
Returns the number of variables in this Directed Graphical Model.
Definition: DAGmodel_inl.h:39
virtual ~DAGmodel()
Destructor.
Definition: DAGmodel.cpp:39
void erase(const Key &k)
Erases an element from the set.
Definition: set_tpl.h:656
bool exists(const NodeId id) const
alias for existsNode
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
Definition: agrum.h:25
iterator begin() const
The usual unsafe begin iterator to parse the set.
Definition: set_tpl.h:517
virtual NodeId idFromName(const std::string &name) const =0
Getter by name.
bool hasSameStructure(const DAGmodel &other)
Definition: DAGmodel.cpp:102
bool isIndependent(NodeId X, NodeId Y, const NodeSet &Z) const
check if X and Y are independent given Z
Definition: DAGmodel.cpp:200
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:607
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:98
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
The base class for all directed edgesThis class is used as a basis for manipulating all directed edge...
DAGmodel()
Default constructor.
Definition: DAGmodel.cpp:30
const NodeGraphPart & nodes() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:70
UndiGraph * mutableMoralGraph__
The moral graph of this Directed Graphical Model.
Definition: DAGmodel.h:221
GraphicalModel & operator=(const GraphicalModel &source)
Private copy operator.
virtual const DiscreteVariable & variable(NodeId id) const =0
Returns a constant reference over a variable given it&#39;s node id.
Copyright 2005-2020 Pierre-Henri WUILLEMIN() et Christophe GONZALES() () info_at_agrum_dot_org.
void moralGraph__() const
Returns the moral graph of this DAGModel.
Definition: DAGmodel.cpp:44
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: diGraph.cpp:91
DAG dag_
The DAG of this Directed Graphical Model.
Definition: DAGmodel.h:213
const UndiGraph & moralGraph(bool clear=true) const
The node&#39;s id are coherent with the variables and nodes of the topology.
Definition: DAGmodel.cpp:82
NodeSet descendants(const NodeId id) const
returns the set of nodes with directed path outgoing from a given node
Definition: DAGmodel.cpp:124
Base class for undirected graphs.
Definition: undiGraph.h:109
NodeSet ancestors(const NodeId id) const
returns the set of nodes with directed path ingoing to a given node
Definition: DAGmodel.cpp:145
void populateNodes(const NodeGraphPart &s)
populateNodes clears *this and fills it with the same nodes as "s"
const DAG & dag() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:36
Size NodeId
Type for node ids.
Definition: graphElements.h:98
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613