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 oriented graphs 24 * 25 * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 26 */ 27 #ifndef GUM_DIGRAPH_H 28 #define GUM_DIGRAPH_H 29 30 #include <iostream> 31 #include <sstream> 32 #include <utility> 33 34 #include <agrum/agrum.h> 35 #include <agrum/tools/core/sequence.h> 36 37 #include <agrum/tools/graphs/parts/arcGraphPart.h> 38 #include <agrum/tools/graphs/parts/nodeGraphPart.h> 39 40 namespace gum { 41 42 /* =========================================================================== 43 */ 44 /* === BASE CLASS FOR MANIPULATING ALL DIRECTED GRAPHS === 45 */ 46 /* =========================================================================== 47 */ 48 /** @class DiGraph 49 * @brief Base class for all oriented graphs 50 * 51 * \ingroup graph_group 52 * 53 * 54 * This is the base class for graphs containing directed edges (so-called 55 *arcs) 56 * * 57 * @par Usage example: 58 * @code 59 * // creating empty graphs 60 * DiGraph g1,g2; 61 * 62 * // adding nodes and arcs to g1 63 * NodeId i1=g1.addNode(); 64 * NodeId i2=g1.addNode(); 65 * NodeId i3=g1.addNode(); 66 * g1.addArc( i1,i2 ); 67 * g1.addArc( i1,i3 ); 68 * g1.addArc( i2,i3 ); 69 * 70 * //throw an InvalidNode 71 * // g1.addArc( i1+i2+i3,i1 ); 72 * 73 * // copying graphs 74 * DiGraph g3 = g1; 75 * g2 = g1; 76 * DiGraph g4=g1; 77 * 78 * // check if a graph has no node 79 * if ( g1.empty() ) cerr << "graph g1 is empty" << endl; 80 * 81 * // remove all the nodes (as well as their adjacent arcs) 82 * g1.clear(); 83 * 84 * // remove some arc 85 * g4.eraseArc( Arc ( i1,i3 ) ); 86 * 87 * // remove node 88 * g2.eraseNode( i2 ); 89 * 90 * // parse a graph 91 * for ( const auto node : g3.nodes() ) 92 * cerr << node<< endl; 93 * 94 * for ( const auto & arc : g3.arcs()) 95 * cerr << arc << endl; 96 * 97 * const ArcSet& a=g3.parents( 3 ); 98 * 99 * for ( const auto & par : g3.parents(3)) 100 * cerr << " - "<< par; 101 * 102 * cerr<<endl; 103 * 104 * // remove all the arcs that are parent of a given node 105 * g3.eraseParents( 2 ); 106 * @endcode 107 */ 108 /* =========================================================================== 109 */ 110 class DiGraph: public virtual NodeGraphPart, public ArcGraphPart { 111 public: 112 // ############################################################################ 113 /// @name Constructors / Destructors 114 // ############################################################################ 115 /// @{ 116 117 /// default constructor 118 /** @param nodes_size the size of the hash table used to store all the nodes 119 * @param nodes_resize_policy the resizing policy of this hash table 120 * @param arcs_size the size of the hash table used to store all the arcs 121 * @param arcs_resize_policy the resizing policy of this hash table */ 122 explicit DiGraph(Size nodes_size = HashTableConst::default_size, 123 bool nodes_resize_policy = true, 124 Size arcs_size = HashTableConst::default_size, 125 bool arcs_resize_policy = true); 126 127 /// copy constructor 128 /** @param g the DiGraph to copy */ 129 DiGraph(const DiGraph& g); 130 131 /// destructor 132 virtual ~DiGraph(); 133 134 /// @} 135 136 // ############################################################################ 137 /// @name Operators 138 // ############################################################################ 139 /// @{ 140 141 /// copy operator 142 /** @param g the DiGraph to copy */ 143 DiGraph& operator=(const DiGraph& g); 144 145 /// tests whether two DiGraphs are identical (same nodes, same arcs) 146 /** @param g the DiGraph with which "this" is compared */ 147 // not virtual : it is a feature !!! :) 148 bool operator==(const DiGraph& g) const; 149 150 /// tests whether two DiGraphs are different 151 /** @param g the DiGraph with which "this" is compared */ 152 // not virtual : it is a feature !!! :) 153 bool operator!=(const DiGraph& g) const; 154 155 /// @} 156 157 // ############################################################################ 158 /// @name Accessors/Modifiers 159 // ############################################################################ 160 /// @{ 161 162 /// insert a new arc into the directed graph 163 /** @param tail the id of the tail of the new inserted arc 164 * @param head the id of the head of the new inserted arc 165 * @warning if the arc already exists, nothing is done. In particular, no 166 * exception is raised. 167 * @throw InvalidNode if head or tail does not belong to the graph nodes */ 168 virtual void addArc(const NodeId tail, const NodeId head); 169 170 /// remove a node and its adjacent arcs from the graph 171 /** @param id the id of the node to be removed 172 * @warning if the node does not exist, nothing is done. In particular, no 173 * exception is raised.*/ 174 virtual void eraseNode(const NodeId id); 175 176 /// removes all the nodes and arcs from the graph 177 virtual void clear(); 178 179 /// to friendly display the content of the graph 180 virtual std::string toString() const; 181 182 /// to friendly display the content of the graph in the DOT syntax 183 /** @param name The graph name in the dot syntax. Default is G. 184 * @return Returns a string describing the graph in the dot syntax */ 185 virtual std::string toDot() const; 186 187 /** 188 * The topological order stays the same as long as no variable or arcs are 189 * added or erased src the topology. 190 * @param clear If false returns the previously created topology. 191 * @throw InvalidDirectedCycle Raised if this DiGraph contains cycles. 192 */ 193 const Sequence< NodeId >& topologicalOrder(bool clear = true) const; 194 /// @} 195 196 /** checks whether there exists a directed path from \e from to \e to 197 * 198 * If from==to, this function checks if a directed cycle containing \e from 199 * exists. 200 * @param from 201 * @param to 202 * @return true if a directed path exists 203 * 204 */ 205 bool hasDirectedPath(const NodeId from, const NodeId to); 206 207 private: 208 /// The topology sequence of this Directed Graphical Model. 209 mutable Sequence< NodeId >* _mutableTopologicalOrder_; 210 211 /// Returns a topological order of this DAGModel. 212 /// @warning _mutableTopologicalOrder_ is assumed to be valid and empty 213 void _topologicalOrder_() const; 214 }; 215 216 /// for friendly displaying the content of directed graphs 217 std::ostream& operator<<(std::ostream&, const DiGraph&); 218 219 } /* namespace gum */ 220 221 #ifndef GUM_NO_INLINE 222 # include <agrum/tools/graphs/diGraph_inl.h> 223 #endif // GUM_NOINLINE 224 225 #endif /* GUM_DIGRAPH_H */ 226