1 /**
2  *
3  *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
4  *   info_at_agrum_dot_org
5  *
6  *  This library is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU Lesser General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public License
17  *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /** @file
23  * @brief Source implementation of Base classes for directed acyclic graphs
24  *
25  * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
26  *
27  */
28 #include <agrum/tools/graphs/DAG.h>
29 
30 #ifdef GUM_NO_INLINE
31 #  include <agrum/tools/graphs/DAG_inl.h>
32 #endif   // GUM_NOINLINE
33 
34 namespace gum {
35 
36   // diamond structure require to explicitly initialize NodeGraphPart
DAG(Size nodes_size,bool nodes_resize_policy,Size arcs_size,bool arcs_resize_policy)37   DAG::DAG(Size nodes_size, bool nodes_resize_policy, Size arcs_size, bool arcs_resize_policy) :
38       NodeGraphPart(nodes_size, nodes_resize_policy),
39       DiGraph(nodes_size, nodes_resize_policy, arcs_size, arcs_resize_policy) {
40     GUM_CONSTRUCTOR(DAG);
41   }
42 
43   // diamond structure require to explicitly initialize NodeGraphPart
DAG(const DAG & g)44   DAG::DAG(const DAG& g) : NodeGraphPart(g), DiGraph(g) {
45     GUM_CONS_CPY(DAG);
46     ;
47   }
48 
~DAG()49   DAG::~DAG() {
50     GUM_DESTRUCTOR(DAG);
51     ;
52   }
53 
54 
moralGraph() const55   UndiGraph DAG::moralGraph() const {
56     UndiGraph moralgraph;
57     moralgraph.populateNodes(*this);
58     // transform the arcs into edges
59     for (const auto& arc: arcs())
60       moralgraph.addEdge(arc.first(), arc.second());
61 
62     // marry the parents
63     for (const auto node: nodes()) {
64       const auto& par = parents(node);
65 
66       for (auto it1 = par.begin(); it1 != par.end(); ++it1) {
67         auto it2 = it1;
68 
69         for (++it2; it2 != par.end(); ++it2) {
70           // will automatically check if this edge already exists
71           moralgraph.addEdge(*it1, *it2);
72         }
73       }
74     }
75     return moralgraph;
76   }
77 
78 
moralizedAncestralGraph(const NodeSet & nodes) const79   UndiGraph DAG::moralizedAncestralGraph(const NodeSet& nodes) const {
80     UndiGraph res;
81     NodeSet   tmp{nodes};
82 
83     // findings all nodes
84     while (!tmp.empty()) {
85       auto current = *(tmp.begin());
86       tmp.erase(current);
87 
88       res.addNodeWithId(current);
89       for (auto next: parents(current))
90         if (!tmp.contains(next) && !res.exists(next)) tmp.insert(next);
91     }
92 
93     // finding all edges and moralizing
94     for (auto current: res)
95       for (auto father: parents(current)) {
96         res.addEdge(current,
97                     father);   // addEdge does not complain if edge already exists
98         for (auto other_father: parents(current))
99           if (other_father != father) res.addEdge(father, other_father);
100       }
101 
102     return res;
103   }
104 
dSeparation(NodeId X,NodeId Y,const NodeSet & Z) const105   bool DAG::dSeparation(NodeId X, NodeId Y, const NodeSet& Z) const {
106     NodeSet cumul{Z};
107     cumul << X << Y;
108     auto g = moralizedAncestralGraph(cumul);
109     for (auto node: Z)
110       g.eraseNode(node);
111     return !g.hasUndirectedPath(X, Y);
112   }
113 
dSeparation(const NodeSet & X,const NodeSet & Y,const NodeSet & Z) const114   bool DAG::dSeparation(const NodeSet& X, const NodeSet& Y, const NodeSet& Z) const {
115     if (!(X * Y).empty())
116       GUM_ERROR(InvalidArgument, "NodeSets " << X << ", " << Y << " should have no intersection")
117 
118     NodeSet cumul{Z};
119     cumul += X;
120     cumul += Y;
121     auto g = moralizedAncestralGraph(cumul);
122     for (auto node: Z)
123       g.eraseNode(node);
124     auto cc = g.nodes2ConnectedComponent();
125 
126     NodeSet Xcc, Ycc;
127     for (const auto node: X)
128       if (g.existsNode(node))   // it may be in Z too
129         if (!Xcc.exists(cc[node])) Xcc.insert(cc[node]);
130     for (const auto node: Y)
131       if (g.existsNode(node))   // it may be in Z too
132         if (!Ycc.exists(cc[node])) Ycc.insert(cc[node]);
133 
134     return (Xcc * Ycc).empty();
135   }
136 } /* namespace gum */
137