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