aGrUM  0.13.2
essentialGraph.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
28 
29 #ifdef GUM_NO_INLINE
31 #endif // GUM_NOINLINE
32 
33 namespace gum {
34  EssentialGraph::EssentialGraph(const DAGmodel& m) : __dagmodel(&m) {
36  }
37 
39  __dagmodel(&m), __mg(mg) {}
43  }
45  if (&g != this) {
48  }
49  return *this;
50  }
51 
53 
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  }
77 
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  }
109 
110  std::string EssentialGraph::toDot() const {
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  }
142 } // namespace gum
Size size() const
wrapping MixedGraph::size()
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
Inline implementation of the class building the essential Graph from a DAGmodel.
Virtual base class for PGMs using a DAG.
Definition: DAGmodel.h:45
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:114
unsigned int NodeId
Type for node ids.
Definition: graphElements.h:97
EssentialGraph & operator=(const EssentialGraph &g)
const ArcSet & arcs() const
returns the set of nodes with arc ingoing to a given node
Definition: DAGmodel_inl.h:102
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
Generic doubly linked lists.
Definition: list.h:369
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
const NodeSet & neighbours(const NodeId id) const
returns the set of edges adjacent to a given node
bool __strongly_protected(NodeId a, NodeId b)
Class building the essential Graph from a DAGmodel.
bool exists(const Val &val) const
Checks whether there exists a given element in the list.
Definition: list_tpl.h:1854
const DAGmodel * __dagmodel
const NodeSet & parents(const NodeId id) const
returns the set of nodes with arc ingoing to a given node
The base class for all directed edgesThis class is used as a basis for manipulating all directed edge...
virtual const DiscreteVariable & variable(NodeId id) const =0
Returns a constant reference over a variabe given it&#39;s node id.
std::string toDot() const
Val & insert(const Val &val)
Inserts a new element at the end of the chained list (alias of pushBack).
Definition: list_tpl.h:1616
Class building the essential graph from a BN.
const NodeSet & children(const NodeId id) const
returns the set of nodes with arc outgoing from a given node
const NodeGraphPart & nodes() const
return *this as a NodeGraphPart
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701
const NodeGraphPart & nodes() const
Returns a constant reference to the dag of this Bayes Net.
Definition: DAGmodel_inl.h:113
const std::string & name() const
returns the name of the variable
EssentialGraph()=default
bool existsEdge(const Edge &edge) const
indicates whether a given edge exists
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
Base class for mixed graphs.
Definition: mixedGraph.h:124