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 #ifndef GUM_EDGE_GRAPH_PART_H 23 #define GUM_EDGE_GRAPH_PART_H 24 25 26 #include <agrum/agrum.h> 27 #include <algorithm> 28 #include <utility> 29 30 #include <agrum/tools/core/signal/signaler.h> 31 32 #include <agrum/tools/graphs/graphElements.h> 33 34 namespace gum { 35 36 /** @class EdgeGraphPart 37 * @brief Classes for undirected edge sets 38 * 39 * \ingroup graph_group 40 * 41 * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 42 * 43 * @par Usage example: 44 * @code 45 * EdgeGraphPart edges1,edges2; 46 * 47 * // insert elements into edges1 48 * edges1.addEdge( 2,3 ); 49 * Edge edge( 5,3 ); 50 * edges1.addEdge( 5,3 ); 51 * 52 * // copy edges1 into edges2 53 * edges2=edges1; 54 * std::cerr<<"edges2:"<<edges2.toString()<<std::endl; 55 * 56 * // remove some elements from edges1 57 * edges1.eraseEdge( Edge (2,3) ); 58 * edges1.eraseEdge( edge ); 59 * 60 * if ( edges1.empty() ) std::cerr<<" edges1 is empty"<<std::endl; 61 * 62 * // checks whether a given edge exists 63 * if ( edges2.exists( edge ) ) 64 * std::cerr << "set contains " << edge << endl; 65 * 66 * if ( edges2.exists( 5,3 ) ) 67 * std::cerr << "set contains " << edge << endl; 68 * 69 * std::cerr<<edges2.toString()<<std::endl; 70 * std::cerr<<edges2.neighbours( 5 )<<std::endl; 71 * @endcode 72 */ 73 74 class EdgeGraphPart { 75 public: 76 typedef EdgeSetIterator EdgeIterator; 77 78 Signaler2< NodeId, NodeId > onEdgeAdded; 79 Signaler2< NodeId, NodeId > onEdgeDeleted; 80 81 // ############################################################################ 82 /// @name Constructors / Destructors 83 // ############################################################################ 84 /// @{ 85 86 /// default constructor 87 /** @param edges_size the size of the hash table used to store all the edges 88 * @param edges_resize_policy the resizing policy of this hash table */ 89 explicit EdgeGraphPart(Size edges_size = HashTableConst::default_size, 90 bool edges_resize_policy = true); 91 92 /// copy constructor 93 /** @param s the EdgeGraphPart to copy */ 94 EdgeGraphPart(const EdgeGraphPart& s); 95 96 /// destructor 97 virtual ~EdgeGraphPart(); 98 99 /// @} 100 101 // ############################################################################ 102 /// @name Operators 103 // ############################################################################ 104 /// @{ 105 106 /// copy operator 107 /** @param s the EdgeGraphPart to copy */ 108 EdgeGraphPart& operator=(const EdgeGraphPart& s); 109 110 /// tests whether two EdgeGraphParts contain the same edges 111 /** @param p the EdgeGraphPart that we compare with this */ 112 bool operator==(const EdgeGraphPart& p) const; 113 114 /// tests whether two EdgeGraphParts contain different edges 115 /** @param p the EdgeGraphPart that we compare with this */ 116 bool operator!=(const EdgeGraphPart& p) const; 117 118 /// @} 119 120 // ############################################################################ 121 /// @name Accessors/Modifiers 122 // ############################################################################ 123 /// @{ 124 125 /// insert a new edge into the EdgeGraphPart 126 /** @param n1 the id of one extremity of the new edge to be inserted 127 * @param n2 the id of the other extremity of the new edge to be inserted 128 * @warning if the edge already exists, nothing is done. In particular, no 129 * exception is raised. */ 130 virtual void addEdge(const NodeId n1, const NodeId n2); 131 132 /// removes an edge from the EdgeGraphPart 133 /** @param edge the edge to be removed 134 * @warning if the edge does not exist, nothing is done. In particular, no 135 * exception is thrown. However, the signal onEdgeDeleted is fired 136 * only if a node is effectively removed. */ 137 virtual void eraseEdge(const Edge& edge); 138 139 /// indicates whether a given edge exists 140 /** @param edge the edge we test whether or not it belongs to the 141 * EdgeGraphPart */ 142 bool existsEdge(const Edge& edge) const; 143 144 /// indicates whether a given edge exists 145 /** @param n1 the id of one extremity of the edge we test the existence in 146 * the EdgeGraphPart 147 * @param n2 the id of the other extremity of the edge we test the existence 148 * in the EdgeGraphPart */ 149 bool existsEdge(const NodeId n1, const NodeId n2) const; 150 151 /// indicates wether the EdgeGraphPart contains any edge 152 bool emptyEdges() const; 153 154 /// removes all the edges from the EdgeGraphPart 155 virtual void clearEdges(); 156 157 /// indicates the number of edges stored within the EdgeGraphPart 158 Size sizeEdges() const; 159 160 /// returns the set of edges stored within the EdgeGraphPart 161 const EdgeSet& edges() const; 162 163 /// returns the set of node neighbours to a given node 164 /** Note that the set of nodes returned may be empty if no edge within the 165 * EdgeGraphPart is adjacent the given node. 166 * @param id the node to which the edges are adjacent */ 167 const NodeSet& neighbours(const NodeId id) const; 168 169 /// erase all the edges adjacent to a given node 170 /** @param id the node the adjacent edges of which will be removed 171 * @warning if no edge is adjacent to id, nothing is done. In particular, no 172 * exception is thrown. 173 * @warning although this method is not virtual, it calls method 174 * eraseEdge( const Edge& edge ) and, as such, has a "virtual" behaviour */ 175 void eraseNeighbours(const NodeId id); 176 177 /// same function as eraseNeighbours but without any virtual call to an 178 /// erase 179 /** @param id the node whose ingoing arcs will be removed */ 180 void unvirtualizedEraseNeighbours(const NodeId id); 181 182 /// to friendly display the content of the EdgeGraphPart 183 std::string toString() const; 184 185 /** @brief a method to create a hashMap of VAL from a set of edges 186 * (using for every edge, say x, the VAL f(x)) 187 * @param f a function assigning a VAL to any edge 188 * @param size an optional parameter enabling to fine-tune the returned 189 * Property. Roughly speaking, it is a good practice to have a size equal to 190 * half the number of edges. If you do not specify this parameter, the 191 * method 192 * will assign it for you. */ 193 template < typename VAL > 194 EdgeProperty< VAL > edgesProperty(VAL (*f)(const Edge&), Size size = 0) const; 195 196 /** @brief a method to create a hashMap of VAL from a set of edges 197 * (using for every edge, say x, the VAL a) 198 * @param a the default value assigned to each edge in the returned Property 199 * @param size an optional parameter enabling to fine-tune the returned 200 * Property. Roughly speaking, it is a good practice to have a size equal to 201 * half the number of edges. If you do not specify this parameter, the 202 * method 203 * will assign it for you. */ 204 template < typename VAL > 205 EdgeProperty< VAL > edgesProperty(const VAL& a, Size size = 0) const; 206 207 /** @brief a method to create a list of VAL from a set of edges 208 * (using for every edge, say x, the VAL f(x)) 209 * @param f a function assigning a VAL to any edge */ 210 template < typename VAL > 211 List< VAL > listMapEdges(VAL (*f)(const Edge&)) const; 212 213 /// returns a possible path from node1 to node2 in the edge set 214 /** @param node1 the id from which the path begins 215 * @param node2 the id to which the path ends 216 * @throw NotFound exception is raised if no path can be found between the 217 * two nodes */ 218 const std::vector< NodeId > undirectedPath(const NodeId node1, const NodeId node2) const; 219 /** 220 * return true if n1 and n2 are connected (by an undirected path) in the graph. 221 * @param n1 NodeId 222 * @param n2 NodeId 223 * @return bool 224 */ 225 bool hasUndirectedPath(const NodeId n1, const NodeId n2) const; 226 227 /** 228 * return true if n1 and n2 are connected (by an undirected path not using the 229 * nodes of except) in the graph. 230 * @param n1 NodeId 231 * @param n2 NodeId 232 * @param except NodeSet 233 * @warning n1 in except has no repercussion. However n2 in except naturally 234 * leads to 'false' 235 * @return bool 236 */ 237 bool hasUndirectedPath(const NodeId n1, const NodeId n2, const NodeSet& except) const; 238 /** 239 * return true if n1 and n2 are connected (by an undirected path not using the 240 * nodes of except) in the graph. 241 * @param n1 NodeSet 242 * @param n2 NodeSet 243 * @param except NodeSet 244 * @return bool 245 */ 246 bool hasUndirectedPath(const NodeSet& n1, const NodeSet& n2, const NodeSet& except) const; 247 /// @} 248 249 private: 250 /// the set of all the edges contained within the EdgeGraphPart 251 EdgeSet _edges_; 252 253 /// for each node, the set of its adjacent edges 254 mutable NodeProperty< NodeSet* > _neighbours_; 255 256 /** @brief when the EdgeGraphPart contains no edge adjacent to a given node, 257 * this function adds an empty set entry to _neighbours_[id] 258 * @param id the node whose _neighbours_[id] is checked */ 259 void _checkNeighbours_(const NodeId id) const; 260 }; 261 262 /// for friendly displaying the content of an edge set 263 std::ostream& operator<<(std::ostream&, const EdgeGraphPart&); 264 265 } /* namespace gum */ 266 267 #ifndef GUM_NO_INLINE 268 # include <agrum/tools/graphs/parts/edgeGraphPart_inl.h> 269 #endif // GUM_NOINLINE 270 271 #include <agrum/tools/graphs/parts/edgeGraphPart_tpl.h> 272 273 #endif // GUM_EDGEGRAPHPART_H 274