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 Base classes for directed acyclic graphs 24 * 25 * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 26 */ 27 #ifndef GUM_DAG_H 28 #define GUM_DAG_H 29 30 #include <agrum/tools/graphs/undiGraph.h> 31 #include <agrum/tools/graphs/diGraph.h> 32 33 namespace gum { 34 35 /* ====================================================================== */ 36 /* === BASE CLASS FOR MANIPULATING GRAPHS WITH BOTH EDGES AND ARCS */ 37 /* ====================================================================== */ 38 /** @class DAG 39 * @brief Base class for dag 40 * 41 * \ingroup graph_group 42 * 43 * 44 * This is the base class for Directed Acyclic Graph : addArc may throw a 45 * DirectedCycle if any (directed) cycle is created by this arc. 46 * 47 * @par exemple de code 48 * @code 49 * // creating empty graphs 50 * gum::DAG g1,g2; 51 * 52 * // adding nodes and arcs to g1 53 * gum::NodeId i1=g1.addNode(); 54 * gum::NodeId i2=g1.addNode(); 55 * gum::NodeId i3=g1.addNode(); 56 * g1.addArc( i1,i2 ); 57 * g1.addArc( i1,i3 ); 58 * g1.addArc( i2,i3 ); 59 * 60 * //throw an InvalidNode 61 * // g1.addArc( i1+i2+i3,i1 ); 62 * 63 * // throw an InvalidDirectedCycle 64 * // g1.addArc( i3,i1 ); 65 * 66 * // copying graphs 67 * gum::DAG g3 = g1; 68 * g2 = g1; 69 * gum::DAG g4=g1; 70 * 71 * // check if a graph has no node 72 * if ( g1.empty() ) cerr << "graph g1 is empty" << endl; 73 * 74 * // remove all the nodes (as well as their adjacent arcs) 75 * g1.clear(); 76 * 77 * // remove some arc 78 * g4.eraseArc( Arc ( i1,i3 ) ); 79 * 80 * // remove node 81 * g2.eraseNode( i2 ); 82 * 83 * // parse a graph 84 * for ( const auto node : g3.nodes() ) // type of node = gum::NodeId 85 * cerr << node << endl; 86 * 87 * for ( const auto& arc= g3.arcs()) // type of arc : gum::Arc& 88 * cerr << iter << endl; 89 * 90 * for ( const auto node :g3.pare nts( gum::NodeId(3) )) 91 * cerr << " - "<<*iter; 92 * 93 * cerr<<endl; 94 * 95 * // remove all the arcs that are parent of a given node 96 * g3.eraseParents( gum::NodeId(2) ); 97 * 98 * @endcode 99 */ 100 /* ====================================================================== */ 101 class DAG: public DiGraph { 102 public: 103 // ############################################################################ 104 /// @name Constructors / Destructors 105 // ############################################################################ 106 /// @{ 107 108 /// default constructor 109 /** 110 * @param nodes_size the size of the hash table used to store all the nodes 111 * @param nodes_resize_policy the resizing policy of this hash table 112 * @param arcs_size the size of the hash table used to store all the arcs 113 * @param arcs_resize_policy the resizing policy of this hash table 114 */ 115 explicit DAG(Size nodes_size = HashTableConst::default_size, 116 bool nodes_resize_policy = true, 117 Size arcs_size = HashTableConst::default_size, 118 bool arcs_resize_policy = true); 119 120 /// copy constructor 121 /** @param g the DAG to copy */ 122 DAG(const DAG& g); 123 124 /// destructor 125 virtual ~DAG(); 126 127 /// @} 128 129 // ############################################################################ 130 /// @name Operators 131 // ############################################################################ 132 /// @{ 133 134 /// copy operator 135 /** @param g the DAG to copy */ 136 DAG& operator=(const DAG& g); 137 138 /// @} 139 140 // ############################################################################ 141 /// @name Accessors/Modifiers 142 // ############################################################################ 143 /// @{ 144 145 /// insert a new arc into the directed graph 146 /** 147 * @param tail the id of the tail of the new inserted arc 148 * @param head the id of the head of the new inserted arc 149 * @warning if the arc already exists, nothing is done. In particular, no 150 * exception is raised. 151 * @throw InvalidNode if head or tail does not belong to the graph nodes 152 * @throw InvalidDirectedCycle if any (directed) cycle is created by this 153 * arc. 154 * @warning Unfortunately, this means that addArc is not in constant 155 * time anymore. 156 */ 157 void addArc(NodeId tail, NodeId head) final; 158 /// @} 159 160 161 /** build a UndiGraph by moralizing the dag 162 * 163 * @return the moralized graph 164 */ 165 UndiGraph moralGraph() const; 166 167 /** build a UndiGraph by moralizing the Ancestral Graph of a set of Nodes 168 * 169 * @param nodes the set of nodeId 170 * @return the moralized ancestral graph 171 */ 172 UndiGraph moralizedAncestralGraph(const NodeSet& nodes) const; 173 174 /** check if node X and node Y are independent given nodes Z (in the sense of 175 * d-separation)*/ 176 bool dSeparation(NodeId X, NodeId Y, const NodeSet& Z) const; 177 178 /** check if nodes X and nodes Y are independent given Z (in the sense of 179 * d-separation)*/ 180 bool dSeparation(const NodeSet& X, const NodeSet& Y, const NodeSet& Z) const; 181 }; 182 183 } /* namespace gum */ 184 185 #ifndef GUM_NO_INLINE 186 # include <agrum/tools/graphs/DAG_inl.h> 187 #endif // GUM_NOINLINE 188 189 #endif /* GUM_DAG_H */ 190