Changeset 1531:a3b20dd847b5 in lemon0.x
 Timestamp:
 07/04/05 15:10:34 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2022
 Location:
 lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r1526 r1531 144 144 } 145 145 146 /// \brief Function to count the number of the outedges from node \c n. 147 /// 148 /// This function counts the number of the outedges from node \c n 149 /// in the graph. 150 template <typename Graph> 151 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { 152 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n); 153 } 154 155 /// \brief Function to count the number of the inedges to node \c n. 156 /// 157 /// This function counts the number of the inedges to node \c n 158 /// in the graph. 159 template <typename Graph> 160 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { 161 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); 162 } 163 164 146 165 /// Finds an edge between two nodes of a graph. 147 166 … … 174 193 return e; 175 194 } 176 177 /// \brief Function to count the number of the outedges from node \c n. 178 /// 179 /// This function counts the number of the outedges from node \c n 180 /// in the graph. 181 template <typename Graph> 182 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { 183 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n); 184 } 185 186 /// \brief Function to count the number of the inedges to node \c n. 187 /// 188 /// This function counts the number of the inedges to node \c n 189 /// in the graph. 190 template <typename Graph> 191 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { 192 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); 193 } 194 195 // graph copy 196 197 template < 198 typename DestinationGraph, 199 typename SourceGraph, 200 typename NodeBijection> 201 void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 202 NodeBijection& _nb) { 203 for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) { 204 _nb[it] = _d.addNode(); 205 } 206 } 207 208 template < 209 typename DestinationGraph, 210 typename SourceGraph, 211 typename NodeBijection, 212 typename EdgeBijection> 213 void copyEdges(DestinationGraph& _d, const SourceGraph& _s, 214 const NodeBijection& _nb, EdgeBijection& _eb) { 215 for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) { 216 _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]); 217 } 218 } 219 220 template < 221 typename DestinationGraph, 222 typename SourceGraph, 223 typename NodeBijection, 224 typename EdgeBijection> 225 void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 226 NodeBijection& _nb, EdgeBijection& _eb) { 227 nodeCopy(_d, _s, _nb); 228 edgeCopy(_d, _s, _nb, _eb); 229 } 230 231 template < 232 typename _DestinationGraph, 233 typename _SourceGraph, 234 typename _NodeBijection 235 =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>, 236 typename _EdgeBijection 237 = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge> 238 > 195 196 /// \brief Copy the source map to the target map. 197 /// 198 /// Copy the \c source map to the \c target map. It uses the given iterator 199 /// to iterate on the data structure and it use the \c ref mapping to 200 /// convert the source's keys to the target's keys. 201 template <typename Target, typename Source, 202 typename ItemIt, typename Ref> 203 void copyMap(Target& target, const Source& source, 204 ItemIt it, const Ref& ref) { 205 for (; it != INVALID; ++it) { 206 target[ref[it]] = source[it]; 207 } 208 } 209 210 /// \brief Copy the source map to the target map. 211 /// 212 /// Copy the \c source map to the \c target map. It uses the given iterator 213 /// to iterate on the data structure. 214 template <typename Target, typename Source, 215 typename ItemIt> 216 void copyMap(Target& target, const Source& source, ItemIt it) { 217 for (; it != INVALID; ++it) { 218 target[it] = source[it]; 219 } 220 } 221 222 223 /// \brief Class to copy a graph to an other graph. 224 /// 225 /// Class to copy a graph to an other graph. It can be used easier 226 /// with the \c copyGraph() function. 227 template <typename Target, typename Source> 239 228 class GraphCopy { 240 public: 241 242 typedef _DestinationGraph DestinationGraph; 243 typedef _SourceGraph SourceGraph; 244 245 typedef _NodeBijection NodeBijection; 246 typedef _EdgeBijection EdgeBijection; 247 248 protected: 249 250 NodeBijection node_bijection; 251 EdgeBijection edge_bijection; 252 253 public: 254 255 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) { 256 copyGraph(_d, _s, node_bijection, edge_bijection); 257 } 258 259 const NodeBijection& getNodeBijection() const { 260 return node_bijection; 261 } 262 263 const EdgeBijection& getEdgeBijection() const { 264 return edge_bijection; 265 } 266 267 }; 268 229 public: 230 typedef typename Source::Node Node; 231 typedef typename Source::NodeIt NodeIt; 232 typedef typename Source::Edge Edge; 233 typedef typename Source::EdgeIt EdgeIt; 234 235 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap; 236 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap; 237 238 /// \brief Constructor for the GraphCopy. 239 /// 240 /// It copies the content of the \c _source graph into the 241 /// \c _target graph. It creates also two references, one beetween 242 /// the two nodeset and one beetween the two edgesets. 243 GraphCopy(Target& _target, const Source& _source) 244 : source(_source), target(_target), 245 nodeRefMap(_source), edgeRefMap(_source) { 246 for (NodeIt it(source); it != INVALID; ++it) { 247 nodeRefMap[it] = target.addNode(); 248 } 249 for (EdgeIt it(source); it != INVALID; ++it) { 250 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 251 nodeRefMap[source.target(it)]); 252 } 253 } 254 255 /// \brief Copies the node references into the given map. 256 /// 257 /// Copies the node references into the given map. 258 template <typename NodeRef> 259 const GraphCopy& nodeRef(NodeRef& map) const { 260 for (NodeIt it(source); it != INVALID; ++it) { 261 map.set(it, nodeRefMap[it]); 262 } 263 return *this; 264 } 265 266 /// \brief Reverse and copies the node references into the given map. 267 /// 268 /// Reverse and copies the node references into the given map. 269 template <typename NodeRef> 270 const GraphCopy& nodeCrossRef(NodeRef& map) const { 271 for (NodeIt it(source); it != INVALID; ++it) { 272 map.set(nodeRefMap[it], it); 273 } 274 return *this; 275 } 276 277 /// \brief Copies the edge references into the given map. 278 /// 279 /// Copies the edge references into the given map. 280 template <typename EdgeRef> 281 const GraphCopy& edgeRef(EdgeRef& map) const { 282 for (EdgeIt it(source); it != INVALID; ++it) { 283 map.set(it, edgeRefMap[it]); 284 } 285 return *this; 286 } 287 288 /// \brief Reverse and copies the edge references into the given map. 289 /// 290 /// Reverse and copies the edge references into the given map. 291 template <typename EdgeRef> 292 const GraphCopy& edgeCrossRef(EdgeRef& map) const { 293 for (EdgeIt it(source); it != INVALID; ++it) { 294 map.set(edgeRefMap[it], it); 295 } 296 return *this; 297 } 298 299 /// \brief Make copy of the given map. 300 /// 301 /// Makes copy of the given map for the newly created graph. 302 /// The new map's key type is the target graph's node type, 303 /// and the copied map's key type is the source graph's node 304 /// type. 305 template <typename TargetMap, typename SourceMap> 306 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const { 307 copyMap(tMap, sMap, NodeIt(source), nodeRefMap); 308 return *this; 309 } 310 311 /// \brief Make copy of the given map. 312 /// 313 /// Makes copy of the given map for the newly created graph. 314 /// The new map's key type is the target graph's edge type, 315 /// and the copied map's key type is the source graph's edge 316 /// type. 317 template <typename TargetMap, typename SourceMap> 318 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const { 319 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap); 320 return *this; 321 } 322 323 /// \brief Gives back the stored node references. 324 /// 325 /// Gives back the stored node references. 326 const NodeRefMap& nodeRef() const { 327 return nodeRefMap; 328 } 329 330 /// \brief Gives back the stored edge references. 331 /// 332 /// Gives back the stored edge references. 333 const EdgeRefMap& edgeRef() const { 334 return edgeRefMap; 335 } 336 337 private: 338 339 const Source& source; 340 Target& target; 341 342 NodeRefMap nodeRefMap; 343 EdgeRefMap edgeRefMap; 344 }; 345 346 /// \brief Copy a graph to an other graph. 347 /// 348 /// Copy a graph to an other graph. 349 /// The usage of the function: 350 /// 351 /// \code 352 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); 353 /// \endcode 354 /// 355 /// After the copy the \c nr map will contain the mapping from the 356 /// source graph's nodes to the target graph's nodes and the \c ecr will 357 /// contain the mapping from the target graph's edge to the source's 358 /// edges. 359 template <typename Target, typename Source> 360 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) { 361 return GraphCopy<Target, Source>(target, source); 362 } 269 363 270 364 template <typename _Graph, typename _Item> 
lemon/maps.h
r1456 r1531 207 207 /// @{ 208 208 209 /// \brief Identity mapping. 210 /// 211 /// This mapping gives back the given key as value without any 212 /// modification. 213 template <typename T> 214 class IdentityMap { 215 public: 216 typedef T Key; 217 typedef T Value; 218 219 const Value& operator[](const Key& t) const { 220 return t; 221 } 222 }; 209 223 210 224 ///Convert the \c Value of a maps to another type.
Note: See TracChangeset
for help on using the changeset viewer.