Changeset 416:76287c8caa26 in lemon-1.2
- Timestamp:
- 11/30/08 19:18:32 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 1 deleted
- 5 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r388 r416 58 58 59 59 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". 60 */ 61 62 /** 63 @defgroup graph_adaptors Adaptor Classes for graphs 64 @ingroup graphs 65 \brief This group contains several adaptor classes for digraphs and graphs 66 67 The main parts of LEMON are the different graph structures, generic 68 graph algorithms, graph concepts which couple these, and graph 69 adaptors. While the previous notions are more or less clear, the 70 latter one needs further explanation. Graph adaptors are graph classes 71 which serve for considering graph structures in different ways. 72 73 A short example makes this much clearer. Suppose that we have an 74 instance \c g of a directed graph type say ListDigraph and an algorithm 75 \code 76 template <typename Digraph> 77 int algorithm(const Digraph&); 78 \endcode 79 is needed to run on the reverse oriented graph. It may be expensive 80 (in time or in memory usage) to copy \c g with the reversed 81 arcs. In this case, an adaptor class is used, which (according 82 to LEMON digraph concepts) works as a digraph. The adaptor uses the 83 original digraph structure and digraph operations when methods of the 84 reversed oriented graph are called. This means that the adaptor have 85 minor memory usage, and do not perform sophisticated algorithmic 86 actions. The purpose of it is to give a tool for the cases when a 87 graph have to be used in a specific alteration. If this alteration is 88 obtained by a usual construction like filtering the arc-set or 89 considering a new orientation, then an adaptor is worthwhile to use. 90 To come back to the reverse oriented graph, in this situation 91 \code 92 template<typename Digraph> class ReverseDigraph; 93 \endcode 94 template class can be used. The code looks as follows 95 \code 96 ListDigraph g; 97 ReverseDigraph<ListGraph> rg(g); 98 int result = algorithm(rg); 99 \endcode 100 After running the algorithm, the original graph \c g is untouched. 101 This techniques gives rise to an elegant code, and based on stable 102 graph adaptors, complex algorithms can be implemented easily. 103 104 In flow, circulation and bipartite matching problems, the residual 105 graph is of particular importance. Combining an adaptor implementing 106 this, shortest path algorithms and minimum mean cycle algorithms, 107 a range of weighted and cardinality optimization algorithms can be 108 obtained. For other examples, the interested user is referred to the 109 detailed documentation of particular adaptors. 110 111 The behavior of graph adaptors can be very different. Some of them keep 112 capabilities of the original graph while in other cases this would be 113 meaningless. This means that the concepts that they are models of depend 114 on the graph adaptor, and the wrapped graph(s). 115 If an arc of \c rg is deleted, this is carried out by deleting the 116 corresponding arc of \c g, thus the adaptor modifies the original graph. 117 118 But for a residual graph, this operation has no sense. 119 Let us stand one more example here to simplify your work. 120 RevGraphAdaptor has constructor 121 \code 122 ReverseDigraph(Digraph& digraph); 123 \endcode 124 This means that in a situation, when a <tt>const ListDigraph&</tt> 125 reference to a graph is given, then it have to be instantiated with 126 <tt>Digraph=const ListDigraph</tt>. 127 \code 128 int algorithm1(const ListDigraph& g) { 129 RevGraphAdaptor<const ListDigraph> rg(g); 130 return algorithm2(rg); 131 } 132 \endcode 60 133 */ 61 134 -
lemon/Makefile.am
r414 r416 17 17 18 18 lemon_HEADERS += \ 19 lemon/adaptors.h \ 19 20 lemon/arg_parser.h \ 20 21 lemon/assert.h \ -
lemon/adaptors.h
r415 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 17 17 */ 18 18 19 #ifndef LEMON_ DIGRAPH_ADAPTOR_H20 #define LEMON_ DIGRAPH_ADAPTOR_H21 22 /// \ingroup graph_adaptors23 /// \file24 /// \brief Several digraph adaptors.19 #ifndef LEMON_ADAPTORS_H 20 #define LEMON_ADAPTORS_H 21 22 /// \ingroup graph_adaptors 23 /// \file 24 /// \brief Several graph adaptors 25 25 /// 26 /// This file contains several useful digraph adaptor classes.26 /// This file contains several useful adaptors for digraphs and graphs. 27 27 28 28 #include <lemon/core.h> … … 30 30 #include <lemon/bits/variant.h> 31 31 32 #include <lemon/bits/base_extender.h>33 32 #include <lemon/bits/graph_adaptor_extender.h> 34 #include <lemon/bits/graph_extender.h>35 33 #include <lemon/tolerance.h> 36 34 … … 56 54 typedef typename Digraph::Node Node; 57 55 typedef typename Digraph::Arc Arc; 58 56 59 57 void first(Node& i) const { _digraph->first(i); } 60 58 void first(Arc& i) const { _digraph->first(i); } … … 72 70 typedef NodeNumTagIndicator<Digraph> NodeNumTag; 73 71 int nodeNum() const { return _digraph->nodeNum(); } 74 72 75 73 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 76 74 int arcNum() const { return _digraph->arcNum(); } … … 80 78 return _digraph->findArc(u, v, prev); 81 79 } 82 80 83 81 Node addNode() { return _digraph->addNode(); } 84 82 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } … … 86 84 void erase(const Node& n) const { _digraph->erase(n); } 87 85 void erase(const Arc& a) const { _digraph->erase(a); } 88 86 89 87 void clear() const { _digraph->clear(); } 90 88 91 89 int id(const Node& n) const { return _digraph->id(n); } 92 90 int id(const Arc& a) const { return _digraph->id(a); } … … 99 97 100 98 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 101 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 99 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 102 100 103 101 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier; 104 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 105 102 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 103 106 104 template <typename _Value> 107 105 class NodeMap : public Digraph::template NodeMap<_Value> { … … 110 108 typedef typename Digraph::template NodeMap<_Value> Parent; 111 109 112 explicit NodeMap(const Adaptor& adaptor) 113 110 explicit NodeMap(const Adaptor& adaptor) 111 : Parent(*adaptor._digraph) {} 114 112 115 113 NodeMap(const Adaptor& adaptor, const _Value& value) 116 114 : Parent(*adaptor._digraph, value) { } 117 115 118 116 private: … … 126 124 return *this; 127 125 } 128 126 129 127 }; 130 128 … … 132 130 class ArcMap : public Digraph::template ArcMap<_Value> { 133 131 public: 134 132 135 133 typedef typename Digraph::template ArcMap<_Value> Parent; 136 137 explicit ArcMap(const Adaptor& adaptor) 138 134 135 explicit ArcMap(const Adaptor& adaptor) 136 : Parent(*adaptor._digraph) {} 139 137 140 138 ArcMap(const Adaptor& adaptor, const _Value& value) 141 139 : Parent(*adaptor._digraph, value) {} 142 140 143 141 private: … … 156 154 }; 157 155 156 template<typename _Graph> 157 class GraphAdaptorBase { 158 public: 159 typedef _Graph Graph; 160 typedef Graph ParentGraph; 161 162 protected: 163 Graph* _graph; 164 165 GraphAdaptorBase() : _graph(0) {} 166 167 void setGraph(Graph& graph) { _graph = &graph; } 168 169 public: 170 GraphAdaptorBase(Graph& graph) : _graph(&graph) {} 171 172 typedef typename Graph::Node Node; 173 typedef typename Graph::Arc Arc; 174 typedef typename Graph::Edge Edge; 175 176 void first(Node& i) const { _graph->first(i); } 177 void first(Arc& i) const { _graph->first(i); } 178 void first(Edge& i) const { _graph->first(i); } 179 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); } 180 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); } 181 void firstInc(Edge &i, bool &d, const Node &n) const { 182 _graph->firstInc(i, d, n); 183 } 184 185 void next(Node& i) const { _graph->next(i); } 186 void next(Arc& i) const { _graph->next(i); } 187 void next(Edge& i) const { _graph->next(i); } 188 void nextIn(Arc& i) const { _graph->nextIn(i); } 189 void nextOut(Arc& i) const { _graph->nextOut(i); } 190 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); } 191 192 Node u(const Edge& e) const { return _graph->u(e); } 193 Node v(const Edge& e) const { return _graph->v(e); } 194 195 Node source(const Arc& a) const { return _graph->source(a); } 196 Node target(const Arc& a) const { return _graph->target(a); } 197 198 typedef NodeNumTagIndicator<Graph> NodeNumTag; 199 int nodeNum() const { return _graph->nodeNum(); } 200 201 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 202 int arcNum() const { return _graph->arcNum(); } 203 int edgeNum() const { return _graph->edgeNum(); } 204 205 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 206 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 207 return _graph->findArc(u, v, prev); 208 } 209 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { 210 return _graph->findEdge(u, v, prev); 211 } 212 213 Node addNode() { return _graph->addNode(); } 214 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); } 215 216 void erase(const Node& i) { _graph->erase(i); } 217 void erase(const Edge& i) { _graph->erase(i); } 218 219 void clear() { _graph->clear(); } 220 221 bool direction(const Arc& a) const { return _graph->direction(a); } 222 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); } 223 224 int id(const Node& v) const { return _graph->id(v); } 225 int id(const Arc& a) const { return _graph->id(a); } 226 int id(const Edge& e) const { return _graph->id(e); } 227 228 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); } 229 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); } 230 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); } 231 232 int maxNodeId() const { return _graph->maxNodeId(); } 233 int maxArcId() const { return _graph->maxArcId(); } 234 int maxEdgeId() const { return _graph->maxEdgeId(); } 235 236 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 237 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 238 239 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 240 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 241 242 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 243 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 244 245 template <typename _Value> 246 class NodeMap : public Graph::template NodeMap<_Value> { 247 public: 248 typedef typename Graph::template NodeMap<_Value> Parent; 249 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 250 : Parent(*adapter._graph) {} 251 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 252 : Parent(*adapter._graph, value) {} 253 254 private: 255 NodeMap& operator=(const NodeMap& cmap) { 256 return operator=<NodeMap>(cmap); 257 } 258 259 template <typename CMap> 260 NodeMap& operator=(const CMap& cmap) { 261 Parent::operator=(cmap); 262 return *this; 263 } 264 265 }; 266 267 template <typename _Value> 268 class ArcMap : public Graph::template ArcMap<_Value> { 269 public: 270 typedef typename Graph::template ArcMap<_Value> Parent; 271 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 272 : Parent(*adapter._graph) {} 273 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 274 : Parent(*adapter._graph, value) {} 275 276 private: 277 ArcMap& operator=(const ArcMap& cmap) { 278 return operator=<ArcMap>(cmap); 279 } 280 281 template <typename CMap> 282 ArcMap& operator=(const CMap& cmap) { 283 Parent::operator=(cmap); 284 return *this; 285 } 286 }; 287 288 template <typename _Value> 289 class EdgeMap : public Graph::template EdgeMap<_Value> { 290 public: 291 typedef typename Graph::template EdgeMap<_Value> Parent; 292 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 293 : Parent(*adapter._graph) {} 294 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 295 : Parent(*adapter._graph, value) {} 296 297 private: 298 EdgeMap& operator=(const EdgeMap& cmap) { 299 return operator=<EdgeMap>(cmap); 300 } 301 302 template <typename CMap> 303 EdgeMap& operator=(const CMap& cmap) { 304 Parent::operator=(cmap); 305 return *this; 306 } 307 }; 308 309 }; 158 310 159 311 template <typename _Digraph> 160 class Rev DigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {312 class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> { 161 313 public: 162 314 typedef _Digraph Digraph; 163 315 typedef DigraphAdaptorBase<_Digraph> Parent; 164 316 protected: 165 Rev DigraphAdaptorBase() : Parent() { }317 ReverseDigraphBase() : Parent() { } 166 318 public: 167 319 typedef typename Parent::Node Node; … … 177 329 Node target(const Arc& a) const { return Parent::source(a); } 178 330 331 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 332 179 333 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 180 Arc findArc(const Node& u, const Node& v, 181 334 Arc findArc(const Node& u, const Node& v, 335 const Arc& prev = INVALID) { 182 336 return Parent::findArc(v, u, prev); 183 337 } 184 338 185 339 }; 186 187 188 ///\ingroup graph_adaptors 189 /// 190 ///\brief A digraph adaptor which reverses the orientation of the arcs. 191 /// 192 /// If \c g is defined as 193 ///\code 194 /// ListDigraph dg; 195 ///\endcode 196 /// then 197 ///\code 198 /// RevDigraphAdaptor<ListDigraph> dga(dg); 199 ///\endcode 200 /// implements the digraph obtained from \c dg by 201 /// reversing the orientation of its arcs. 202 /// 203 /// A good example of using RevDigraphAdaptor is to decide whether 204 /// the directed graph is strongly connected or not. The digraph is 205 /// strongly connected iff each node is reachable from one node and 206 /// this node is reachable from the others. Instead of this 207 /// condition we use a slightly different, from one node each node 208 /// is reachable both in the digraph and the reversed digraph. Now 209 /// this condition can be checked with the Dfs algorithm and the 210 /// RevDigraphAdaptor class. 211 /// 212 /// The implementation: 213 ///\code 214 /// bool stronglyConnected(const Digraph& digraph) { 215 /// if (NodeIt(digraph) == INVALID) return true; 216 /// Dfs<Digraph> dfs(digraph); 217 /// dfs.run(NodeIt(digraph)); 218 /// for (NodeIt it(digraph); it != INVALID; ++it) { 219 /// if (!dfs.reached(it)) { 220 /// return false; 221 /// } 222 /// } 223 /// typedef RevDigraphAdaptor<const Digraph> RDigraph; 224 /// RDigraph rdigraph(digraph); 225 /// DfsVisit<RDigraph> rdfs(rdigraph); 226 /// rdfs.run(NodeIt(digraph)); 227 /// for (NodeIt it(digraph); it != INVALID; ++it) { 228 /// if (!rdfs.reached(it)) { 229 /// return false; 230 /// } 231 /// } 232 /// return true; 233 /// } 234 ///\endcode 340 341 /// \ingroup graph_adaptors 342 /// 343 /// \brief A digraph adaptor which reverses the orientation of the arcs. 344 /// 345 /// ReverseDigraph reverses the arcs in the adapted digraph. The 346 /// SubDigraph is conform to the \ref concepts::Digraph 347 /// "Digraph concept". 348 /// 349 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 350 /// "Digraph concept". The type can be specified to be const. 235 351 template<typename _Digraph> 236 class Rev DigraphAdaptor :237 public DigraphAdaptorExtender<Rev DigraphAdaptorBase<_Digraph> > {352 class ReverseDigraph : 353 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { 238 354 public: 239 355 typedef _Digraph Digraph; 240 356 typedef DigraphAdaptorExtender< 241 Rev DigraphAdaptorBase<_Digraph> > Parent;357 ReverseDigraphBase<_Digraph> > Parent; 242 358 protected: 243 Rev DigraphAdaptor() { }359 ReverseDigraph() { } 244 360 public: 245 361 246 362 /// \brief Constructor 247 363 /// 248 /// Creates a reverse graph adaptor for the given digraph249 explicit Rev DigraphAdaptor(Digraph& digraph) {250 Parent::setDigraph(digraph); 364 /// Creates a reverse digraph adaptor for the given digraph 365 explicit ReverseDigraph(Digraph& digraph) { 366 Parent::setDigraph(digraph); 251 367 } 252 368 }; … … 256 372 /// Just gives back a reverse digraph adaptor 257 373 template<typename Digraph> 258 RevDigraphAdaptor<const Digraph> 259 revDigraphAdaptor(const Digraph& digraph) { 260 return RevDigraphAdaptor<const Digraph>(digraph); 374 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { 375 return ReverseDigraph<const Digraph>(digraph); 261 376 } 262 377 263 template <typename _Digraph, typename _NodeFilterMap, 264 typename _ArcFilterMap, boolchecked = true>265 class SubDigraph AdaptorBase : public DigraphAdaptorBase<_Digraph> {378 template <typename _Digraph, typename _NodeFilterMap, 379 typename _ArcFilterMap, bool _checked = true> 380 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { 266 381 public: 267 382 typedef _Digraph Digraph; … … 269 384 typedef _ArcFilterMap ArcFilterMap; 270 385 271 typedef SubDigraph AdaptorBase Adaptor;386 typedef SubDigraphBase Adaptor; 272 387 typedef DigraphAdaptorBase<_Digraph> Parent; 273 388 protected: 274 389 NodeFilterMap* _node_filter; 275 390 ArcFilterMap* _arc_filter; 276 SubDigraph AdaptorBase()391 SubDigraphBase() 277 392 : Parent(), _node_filter(0), _arc_filter(0) { } 278 393 … … 289 404 typedef typename Parent::Arc Arc; 290 405 291 void first(Node& i) const { 292 Parent::first(i); 293 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 294 } 295 296 void first(Arc& i) const { 297 Parent::first(i); 298 while (i != INVALID && (!(*_arc_filter)[i] 299 || !(*_node_filter)[Parent::source(i)] 300 || !(*_node_filter)[Parent::target(i)])) Parent::next(i); 301 } 302 303 void firstIn(Arc& i, const Node& n) const { 304 Parent::firstIn(i, n); 305 while (i != INVALID && (!(*_arc_filter)[i] 306 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); 307 } 308 309 void firstOut(Arc& i, const Node& n) const { 310 Parent::firstOut(i, n); 311 while (i != INVALID && (!(*_arc_filter)[i] 312 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); 313 } 314 315 void next(Node& i) const { 316 Parent::next(i); 317 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 318 } 319 320 void next(Arc& i) const { 321 Parent::next(i); 322 while (i != INVALID && (!(*_arc_filter)[i] 323 || !(*_node_filter)[Parent::source(i)] 324 || !(*_node_filter)[Parent::target(i)])) Parent::next(i); 325 } 326 327 void nextIn(Arc& i) const { 328 Parent::nextIn(i); 329 while (i != INVALID && (!(*_arc_filter)[i] 330 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); 331 } 332 333 void nextOut(Arc& i) const { 334 Parent::nextOut(i); 335 while (i != INVALID && (!(*_arc_filter)[i] 336 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); 406 void first(Node& i) const { 407 Parent::first(i); 408 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 409 } 410 411 void first(Arc& i) const { 412 Parent::first(i); 413 while (i != INVALID && (!(*_arc_filter)[i] 414 || !(*_node_filter)[Parent::source(i)] 415 || !(*_node_filter)[Parent::target(i)])) 416 Parent::next(i); 417 } 418 419 void firstIn(Arc& i, const Node& n) const { 420 Parent::firstIn(i, n); 421 while (i != INVALID && (!(*_arc_filter)[i] 422 || !(*_node_filter)[Parent::source(i)])) 423 Parent::nextIn(i); 424 } 425 426 void firstOut(Arc& i, const Node& n) const { 427 Parent::firstOut(i, n); 428 while (i != INVALID && (!(*_arc_filter)[i] 429 || !(*_node_filter)[Parent::target(i)])) 430 Parent::nextOut(i); 431 } 432 433 void next(Node& i) const { 434 Parent::next(i); 435 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 436 } 437 438 void next(Arc& i) const { 439 Parent::next(i); 440 while (i != INVALID && (!(*_arc_filter)[i] 441 || !(*_node_filter)[Parent::source(i)] 442 || !(*_node_filter)[Parent::target(i)])) 443 Parent::next(i); 444 } 445 446 void nextIn(Arc& i) const { 447 Parent::nextIn(i); 448 while (i != INVALID && (!(*_arc_filter)[i] 449 || !(*_node_filter)[Parent::source(i)])) 450 Parent::nextIn(i); 451 } 452 453 void nextOut(Arc& i) const { 454 Parent::nextOut(i); 455 while (i != INVALID && (!(*_arc_filter)[i] 456 || !(*_node_filter)[Parent::target(i)])) 457 Parent::nextOut(i); 337 458 } 338 459 … … 350 471 351 472 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 352 Arc findArc(const Node& source, const Node& target, 353 473 Arc findArc(const Node& source, const Node& target, 474 const Arc& prev = INVALID) { 354 475 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 355 476 return INVALID; … … 363 484 364 485 template <typename _Value> 365 class NodeMap : public SubMapExtender<Adaptor, 366 486 class NodeMap : public SubMapExtender<Adaptor, 487 typename Parent::template NodeMap<_Value> > { 367 488 public: 368 489 typedef _Value Value; 369 490 typedef SubMapExtender<Adaptor, typename Parent:: 370 491 template NodeMap<Value> > MapParent; 371 372 NodeMap(const Adaptor& adaptor) 373 374 NodeMap(const Adaptor& adaptor, const Value& value) 375 376 492 493 NodeMap(const Adaptor& adaptor) 494 : MapParent(adaptor) {} 495 NodeMap(const Adaptor& adaptor, const Value& value) 496 : MapParent(adaptor, value) {} 497 377 498 private: 378 499 NodeMap& operator=(const NodeMap& cmap) { 379 380 } 381 500 return operator=<NodeMap>(cmap); 501 } 502 382 503 template <typename CMap> 383 504 NodeMap& operator=(const CMap& cmap) { 384 505 MapParent::operator=(cmap); 385 506 return *this; 386 507 } 387 508 }; 388 509 389 510 template <typename _Value> 390 class ArcMap : public SubMapExtender<Adaptor, 391 511 class ArcMap : public SubMapExtender<Adaptor, 512 typename Parent::template ArcMap<_Value> > { 392 513 public: 393 514 typedef _Value Value; 394 515 typedef SubMapExtender<Adaptor, typename Parent:: 395 516 template ArcMap<Value> > MapParent; 396 397 ArcMap(const Adaptor& adaptor) 398 399 ArcMap(const Adaptor& adaptor, const Value& value) 400 401 517 518 ArcMap(const Adaptor& adaptor) 519 : MapParent(adaptor) {} 520 ArcMap(const Adaptor& adaptor, const Value& value) 521 : MapParent(adaptor, value) {} 522 402 523 private: 403 524 ArcMap& operator=(const ArcMap& cmap) { 404 405 } 406 525 return operator=<ArcMap>(cmap); 526 } 527 407 528 template <typename CMap> 408 529 ArcMap& operator=(const CMap& cmap) { 409 530 MapParent::operator=(cmap); 410 531 return *this; 411 532 } 412 533 }; … … 415 536 416 537 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap> 417 class SubDigraph AdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>538 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> 418 539 : public DigraphAdaptorBase<_Digraph> { 419 540 public: … … 422 543 typedef _ArcFilterMap ArcFilterMap; 423 544 424 typedef SubDigraph AdaptorBase Adaptor;545 typedef SubDigraphBase Adaptor; 425 546 typedef DigraphAdaptorBase<Digraph> Parent; 426 547 protected: 427 548 NodeFilterMap* _node_filter; 428 549 ArcFilterMap* _arc_filter; 429 SubDigraph AdaptorBase()550 SubDigraphBase() 430 551 : Parent(), _node_filter(0), _arc_filter(0) { } 431 552 … … 442 563 typedef typename Parent::Arc Arc; 443 564 444 void first(Node& i) const { 445 Parent::first(i); 446 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 447 } 448 449 void first(Arc& i) const { 450 Parent::first(i); 451 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 452 } 453 454 void firstIn(Arc& i, const Node& n) const { 455 Parent::firstIn(i, n); 456 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 457 } 458 459 void firstOut(Arc& i, const Node& n) const { 460 Parent::firstOut(i, n); 461 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 462 } 463 464 void next(Node& i) const { 465 Parent::next(i); 466 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 467 } 468 void next(Arc& i) const { 469 Parent::next(i); 470 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 471 } 472 void nextIn(Arc& i) const { 473 Parent::nextIn(i); 474 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 475 } 476 477 void nextOut(Arc& i) const { 478 Parent::nextOut(i); 479 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 565 void first(Node& i) const { 566 Parent::first(i); 567 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 568 } 569 570 void first(Arc& i) const { 571 Parent::first(i); 572 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 573 } 574 575 void firstIn(Arc& i, const Node& n) const { 576 Parent::firstIn(i, n); 577 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 578 } 579 580 void firstOut(Arc& i, const Node& n) const { 581 Parent::firstOut(i, n); 582 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 583 } 584 585 void next(Node& i) const { 586 Parent::next(i); 587 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 588 } 589 void next(Arc& i) const { 590 Parent::next(i); 591 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 592 } 593 void nextIn(Arc& i) const { 594 Parent::nextIn(i); 595 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 596 } 597 598 void nextOut(Arc& i) const { 599 Parent::nextOut(i); 600 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 480 601 } 481 602 … … 493 614 494 615 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 495 Arc findArc(const Node& source, const Node& target, 496 616 Arc findArc(const Node& source, const Node& target, 617 const Arc& prev = INVALID) { 497 618 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 498 619 return INVALID; … … 506 627 507 628 template <typename _Value> 508 class NodeMap : public SubMapExtender<Adaptor, 509 629 class NodeMap : public SubMapExtender<Adaptor, 630 typename Parent::template NodeMap<_Value> > { 510 631 public: 511 632 typedef _Value Value; 512 633 typedef SubMapExtender<Adaptor, typename Parent:: 513 634 template NodeMap<Value> > MapParent; 514 515 NodeMap(const Adaptor& adaptor) 516 517 NodeMap(const Adaptor& adaptor, const Value& value) 518 519 635 636 NodeMap(const Adaptor& adaptor) 637 : MapParent(adaptor) {} 638 NodeMap(const Adaptor& adaptor, const Value& value) 639 : MapParent(adaptor, value) {} 640 520 641 private: 521 642 NodeMap& operator=(const NodeMap& cmap) { 522 523 } 524 643 return operator=<NodeMap>(cmap); 644 } 645 525 646 template <typename CMap> 526 647 NodeMap& operator=(const CMap& cmap) { 527 648 MapParent::operator=(cmap); 528 649 return *this; 529 650 } 530 651 }; 531 652 532 653 template <typename _Value> 533 class ArcMap : public SubMapExtender<Adaptor, 534 654 class ArcMap : public SubMapExtender<Adaptor, 655 typename Parent::template ArcMap<_Value> > { 535 656 public: 536 657 typedef _Value Value; 537 658 typedef SubMapExtender<Adaptor, typename Parent:: 538 659 template ArcMap<Value> > MapParent; 539 540 ArcMap(const Adaptor& adaptor) 541 542 ArcMap(const Adaptor& adaptor, const Value& value) 543 544 660 661 ArcMap(const Adaptor& adaptor) 662 : MapParent(adaptor) {} 663 ArcMap(const Adaptor& adaptor, const Value& value) 664 : MapParent(adaptor, value) {} 665 545 666 private: 546 667 ArcMap& operator=(const ArcMap& cmap) { 547 548 } 549 668 return operator=<ArcMap>(cmap); 669 } 670 550 671 template <typename CMap> 551 672 ArcMap& operator=(const CMap& cmap) { 552 673 MapParent::operator=(cmap); 553 674 return *this; 554 675 } 555 676 }; … … 559 680 /// \ingroup graph_adaptors 560 681 /// 561 /// \brief A digraph adaptor for hiding nodes and arcs from a digraph. 562 /// 563 /// SubDigraphAdaptor shows the digraph with filtered node-set and 564 /// arc-set. If the \c checked parameter is true then it filters the arc-set 565 /// respect to the source and target. 566 /// 567 /// If the \c checked template parameter is false then the 568 /// node-iterator cares only the filter on the node-set, and the 569 /// arc-iterator cares only the filter on the arc-set. Therefore 570 /// the arc-map have to filter all arcs which's source or target is 571 /// filtered by the node-filter. 572 ///\code 573 /// typedef ListDigraph Digraph; 574 /// DIGRAPH_TYPEDEFS(Digraph); 575 /// Digraph g; 576 /// Node u=g.addNode(); //node of id 0 577 /// Node v=g.addNode(); //node of id 1 578 /// Arc a=g.addArc(u, v); //arc of id 0 579 /// Arc f=g.addArc(v, u); //arc of id 1 580 /// BoolNodeMap nm(g, true); 581 /// nm.set(u, false); 582 /// BoolArcMap am(g, true); 583 /// am.set(a, false); 584 /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA; 585 /// SubDGA ga(g, nm, am); 586 /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n) 587 /// std::cout << g.id(n) << std::endl; 588 /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a) 589 /// std::cout << g.id(a) << std::endl; 590 ///\endcode 591 /// The output of the above code is the following. 592 ///\code 593 /// 1 594 /// 1 595 ///\endcode 596 /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to 597 /// \c Digraph::Node that is why \c g.id(n) can be applied. 598 /// 599 /// For other examples see also the documentation of 600 /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor. 601 template<typename _Digraph, 602 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 603 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 604 bool checked = true> 605 class SubDigraphAdaptor : 606 public DigraphAdaptorExtender< 607 SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > { 682 /// \brief An adaptor for hiding nodes and arcs in a digraph 683 /// 684 /// SubDigraph hides nodes and arcs in a digraph. A bool node map 685 /// and a bool arc map must be specified, which define the filters 686 /// for nodes and arcs. Just the nodes and arcs with true value are 687 /// shown in the subdigraph. The SubDigraph is conform to the \ref 688 /// concepts::Digraph "Digraph concept". If the \c _checked parameter 689 /// is true, then the arcs incident to filtered nodes are also 690 /// filtered out. 691 /// 692 /// \tparam _Digraph It must be conform to the \ref 693 /// concepts::Digraph "Digraph concept". The type can be specified 694 /// to const. 695 /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph. 696 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph. 697 /// \tparam _checked If the parameter is false then the arc filtering 698 /// is not checked with respect to node filter. Otherwise, each arc 699 /// is automatically filtered, which is incident to a filtered node. 700 /// 701 /// \see FilterNodes 702 /// \see FilterArcs 703 template<typename _Digraph, 704 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 705 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 706 bool _checked = true> 707 class SubDigraph 708 : public DigraphAdaptorExtender< 709 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { 608 710 public: 609 711 typedef _Digraph Digraph; … … 612 714 613 715 typedef DigraphAdaptorExtender< 614 SubDigraph AdaptorBase<Digraph, NodeFilterMap, ArcFilterMap,checked> >716 SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> > 615 717 Parent; 616 718 … … 619 721 620 722 protected: 621 SubDigraph Adaptor() { }723 SubDigraph() { } 622 724 public: 623 725 624 726 /// \brief Constructor 625 727 /// 626 /// Creates a sub -digraph-adaptorfor the given digraph with728 /// Creates a subdigraph for the given digraph with 627 729 /// given node and arc map filters. 628 SubDigraph Adaptor(Digraph& digraph, NodeFilterMap& node_filter,629 ArcFilterMap& arc_filter) { 730 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 731 ArcFilterMap& arc_filter) { 630 732 setDigraph(digraph); 631 733 setNodeFilterMap(node_filter); … … 635 737 /// \brief Hides the node of the graph 636 738 /// 637 /// This function hides \c n in the digraph, i.e. the iteration 638 /// jumps over it. This is done by simply setting the value of \c n 739 /// This function hides \c n in the digraph, i.e. the iteration 740 /// jumps over it. This is done by simply setting the value of \c n 639 741 /// to be false in the corresponding node-map. 640 742 void hide(const Node& n) const { Parent::hide(n); } … … 642 744 /// \brief Hides the arc of the graph 643 745 /// 644 /// This function hides \c a in the digraph, i.e. the iteration 746 /// This function hides \c a in the digraph, i.e. the iteration 645 747 /// jumps over it. This is done by simply setting the value of \c a 646 748 /// to be false in the corresponding arc-map. … … 649 751 /// \brief Unhides the node of the graph 650 752 /// 651 /// The value of \c n is set to be true in the node-map which stores 652 /// hide information. If \c n was hidden previuosly, then it is shown 753 /// The value of \c n is set to be true in the node-map which stores 754 /// hide information. If \c n was hidden previuosly, then it is shown 653 755 /// again 654 756 void unHide(const Node& n) const { Parent::unHide(n); } … … 656 758 /// \brief Unhides the arc of the graph 657 759 /// 658 /// The value of \c a is set to be true in the arc-map which stores 659 /// hide information. If \c a was hidden previuosly, then it is shown 760 /// The value of \c a is set to be true in the arc-map which stores 761 /// hide information. If \c a was hidden previuosly, then it is shown 660 762 /// again 661 763 void unHide(const Arc& a) const { Parent::unHide(a); } … … 675 777 }; 676 778 677 /// \brief Just gives back a sub -digraph-adaptor678 /// 679 /// Just gives back a sub -digraph-adaptor779 /// \brief Just gives back a subdigraph 780 /// 781 /// Just gives back a subdigraph 680 782 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 681 SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap> 682 subDigraphAdaptor(const Digraph& digraph, 683 NodeFilterMap& nfm, ArcFilterMap& afm) { 684 return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap> 783 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 784 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { 785 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 685 786 (digraph, nfm, afm); 686 787 } 687 788 688 789 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 689 SubDigraph Adaptor<const Digraph, const NodeFilterMap, ArcFilterMap>690 subDigraph Adaptor(const Digraph& digraph,691 692 return SubDigraph Adaptor<const Digraph, const NodeFilterMap, ArcFilterMap>790 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 791 subDigraph(const Digraph& digraph, 792 const NodeFilterMap& nfm, ArcFilterMap& afm) { 793 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 693 794 (digraph, nfm, afm); 694 795 } 695 796 696 797 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 697 SubDigraph Adaptor<const Digraph, NodeFilterMap, const ArcFilterMap>698 subDigraph Adaptor(const Digraph& digraph,699 NodeFilterMap& nfm,ArcFilterMap& afm) {700 return SubDigraph Adaptor<const Digraph, NodeFilterMap, const ArcFilterMap>798 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 799 subDigraph(const Digraph& digraph, 800 NodeFilterMap& nfm, const ArcFilterMap& afm) { 801 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 701 802 (digraph, nfm, afm); 702 803 } 703 804 704 805 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 705 SubDigraph Adaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>706 subDigraph Adaptor(const Digraph& digraph,707 NodeFilterMap& nfm,ArcFilterMap& afm) {708 return SubDigraph Adaptor<const Digraph, const NodeFilterMap,806 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap> 807 subDigraph(const Digraph& digraph, 808 const NodeFilterMap& nfm, const ArcFilterMap& afm) { 809 return SubDigraph<const Digraph, const NodeFilterMap, 709 810 const ArcFilterMap>(digraph, nfm, afm); 710 711 811 } 712 812 713 813 714 715 ///\ingroup graph_adaptors 716 /// 717 ///\brief An adaptor for hiding nodes from a digraph. 718 /// 719 ///An adaptor for hiding nodes from a digraph. This adaptor 720 ///specializes SubDigraphAdaptor in the way that only the node-set 721 ///can be filtered. In usual case the checked parameter is true, we 722 ///get the induced subgraph. But if the checked parameter is false 723 ///then we can filter only isolated nodes. 724 template<typename _Digraph, 725 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 726 bool checked = true> 727 class NodeSubDigraphAdaptor : 728 public SubDigraphAdaptor<_Digraph, _NodeFilterMap, 729 ConstMap<typename _Digraph::Arc, bool>, checked> { 814 template <typename _Graph, typename NodeFilterMap, 815 typename EdgeFilterMap, bool _checked = true> 816 class SubGraphBase : public GraphAdaptorBase<_Graph> { 817 public: 818 typedef _Graph Graph; 819 typedef SubGraphBase Adaptor; 820 typedef GraphAdaptorBase<_Graph> Parent; 821 protected: 822 823 NodeFilterMap* _node_filter_map; 824 EdgeFilterMap* _edge_filter_map; 825 826 SubGraphBase() 827 : Parent(), _node_filter_map(0), _edge_filter_map(0) { } 828 829 void setNodeFilterMap(NodeFilterMap& node_filter_map) { 830 _node_filter_map=&node_filter_map; 831 } 832 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 833 _edge_filter_map=&edge_filter_map; 834 } 835 836 public: 837 838 typedef typename Parent::Node Node; 839 typedef typename Parent::Arc Arc; 840 typedef typename Parent::Edge Edge; 841 842 void first(Node& i) const { 843 Parent::first(i); 844 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 845 } 846 847 void first(Arc& i) const { 848 Parent::first(i); 849 while (i!=INVALID && (!(*_edge_filter_map)[i] 850 || !(*_node_filter_map)[Parent::source(i)] 851 || !(*_node_filter_map)[Parent::target(i)])) 852 Parent::next(i); 853 } 854 855 void first(Edge& i) const { 856 Parent::first(i); 857 while (i!=INVALID && (!(*_edge_filter_map)[i] 858 || !(*_node_filter_map)[Parent::u(i)] 859 || !(*_node_filter_map)[Parent::v(i)])) 860 Parent::next(i); 861 } 862 863 void firstIn(Arc& i, const Node& n) const { 864 Parent::firstIn(i, n); 865 while (i!=INVALID && (!(*_edge_filter_map)[i] 866 || !(*_node_filter_map)[Parent::source(i)])) 867 Parent::nextIn(i); 868 } 869 870 void firstOut(Arc& i, const Node& n) const { 871 Parent::firstOut(i, n); 872 while (i!=INVALID && (!(*_edge_filter_map)[i] 873 || !(*_node_filter_map)[Parent::target(i)])) 874 Parent::nextOut(i); 875 } 876 877 void firstInc(Edge& i, bool& d, const Node& n) const { 878 Parent::firstInc(i, d, n); 879 while (i!=INVALID && (!(*_edge_filter_map)[i] 880 || !(*_node_filter_map)[Parent::u(i)] 881 || !(*_node_filter_map)[Parent::v(i)])) 882 Parent::nextInc(i, d); 883 } 884 885 void next(Node& i) const { 886 Parent::next(i); 887 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 888 } 889 890 void next(Arc& i) const { 891 Parent::next(i); 892 while (i!=INVALID && (!(*_edge_filter_map)[i] 893 || !(*_node_filter_map)[Parent::source(i)] 894 || !(*_node_filter_map)[Parent::target(i)])) 895 Parent::next(i); 896 } 897 898 void next(Edge& i) const { 899 Parent::next(i); 900 while (i!=INVALID && (!(*_edge_filter_map)[i] 901 || !(*_node_filter_map)[Parent::u(i)] 902 || !(*_node_filter_map)[Parent::v(i)])) 903 Parent::next(i); 904 } 905 906 void nextIn(Arc& i) const { 907 Parent::nextIn(i); 908 while (i!=INVALID && (!(*_edge_filter_map)[i] 909 || !(*_node_filter_map)[Parent::source(i)])) 910 Parent::nextIn(i); 911 } 912 913 void nextOut(Arc& i) const { 914 Parent::nextOut(i); 915 while (i!=INVALID && (!(*_edge_filter_map)[i] 916 || !(*_node_filter_map)[Parent::target(i)])) 917 Parent::nextOut(i); 918 } 919 920 void nextInc(Edge& i, bool& d) const { 921 Parent::nextInc(i, d); 922 while (i!=INVALID && (!(*_edge_filter_map)[i] 923 || !(*_node_filter_map)[Parent::u(i)] 924 || !(*_node_filter_map)[Parent::v(i)])) 925 Parent::nextInc(i, d); 926 } 927 928 void hide(const Node& n) const { _node_filter_map->set(n, false); } 929 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } 930 931 void unHide(const Node& n) const { _node_filter_map->set(n, true); } 932 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } 933 934 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 935 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 936 937 typedef False NodeNumTag; 938 typedef False EdgeNumTag; 939 940 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 941 Arc findArc(const Node& u, const Node& v, 942 const Arc& prev = INVALID) { 943 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 944 return INVALID; 945 } 946 Arc arc = Parent::findArc(u, v, prev); 947 while (arc != INVALID && !(*_edge_filter_map)[arc]) { 948 arc = Parent::findArc(u, v, arc); 949 } 950 return arc; 951 } 952 Edge findEdge(const Node& u, const Node& v, 953 const Edge& prev = INVALID) { 954 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 955 return INVALID; 956 } 957 Edge edge = Parent::findEdge(u, v, prev); 958 while (edge != INVALID && !(*_edge_filter_map)[edge]) { 959 edge = Parent::findEdge(u, v, edge); 960 } 961 return edge; 962 } 963 964 template <typename _Value> 965 class NodeMap : public SubMapExtender<Adaptor, 966 typename Parent::template NodeMap<_Value> > { 967 public: 968 typedef _Value Value; 969 typedef SubMapExtender<Adaptor, typename Parent:: 970 template NodeMap<Value> > MapParent; 971 972 NodeMap(const Adaptor& adaptor) 973 : MapParent(adaptor) {} 974 NodeMap(const Adaptor& adaptor, const Value& value) 975 : MapParent(adaptor, value) {} 976 977 private: 978 NodeMap& operator=(const NodeMap& cmap) { 979 return operator=<NodeMap>(cmap); 980 } 981 982 template <typename CMap> 983 NodeMap& operator=(const CMap& cmap) { 984 MapParent::operator=(cmap); 985 return *this; 986 } 987 }; 988 989 template <typename _Value> 990 class ArcMap : public SubMapExtender<Adaptor, 991 typename Parent::template ArcMap<_Value> > { 992 public: 993 typedef _Value Value; 994 typedef SubMapExtender<Adaptor, typename Parent:: 995 template ArcMap<Value> > MapParent; 996 997 ArcMap(const Adaptor& adaptor) 998 : MapParent(adaptor) {} 999 ArcMap(const Adaptor& adaptor, const Value& value) 1000 : MapParent(adaptor, value) {} 1001 1002 private: 1003 ArcMap& operator=(const ArcMap& cmap) { 1004 return operator=<ArcMap>(cmap); 1005 } 1006 1007 template <typename CMap> 1008 ArcMap& operator=(const CMap& cmap) { 1009 MapParent::operator=(cmap); 1010 return *this; 1011 } 1012 }; 1013 1014 template <typename _Value> 1015 class EdgeMap : public SubMapExtender<Adaptor, 1016 typename Parent::template EdgeMap<_Value> > { 1017 public: 1018 typedef _Value Value; 1019 typedef SubMapExtender<Adaptor, typename Parent:: 1020 template EdgeMap<Value> > MapParent; 1021 1022 EdgeMap(const Adaptor& adaptor) 1023 : MapParent(adaptor) {} 1024 1025 EdgeMap(const Adaptor& adaptor, const Value& value) 1026 : MapParent(adaptor, value) {} 1027 1028 private: 1029 EdgeMap& operator=(const EdgeMap& cmap) { 1030 return operator=<EdgeMap>(cmap); 1031 } 1032 1033 template <typename CMap> 1034 EdgeMap& operator=(const CMap& cmap) { 1035 MapParent::operator=(cmap); 1036 return *this; 1037 } 1038 }; 1039 1040 }; 1041 1042 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 1043 class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 1044 : public GraphAdaptorBase<_Graph> { 1045 public: 1046 typedef _Graph Graph; 1047 typedef SubGraphBase Adaptor; 1048 typedef GraphAdaptorBase<_Graph> Parent; 1049 protected: 1050 NodeFilterMap* _node_filter_map; 1051 EdgeFilterMap* _edge_filter_map; 1052 SubGraphBase() : Parent(), 1053 _node_filter_map(0), _edge_filter_map(0) { } 1054 1055 void setNodeFilterMap(NodeFilterMap& node_filter_map) { 1056 _node_filter_map=&node_filter_map; 1057 } 1058 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 1059 _edge_filter_map=&edge_filter_map; 1060 } 1061 1062 public: 1063 1064 typedef typename Parent::Node Node; 1065 typedef typename Parent::Arc Arc; 1066 typedef typename Parent::Edge Edge; 1067 1068 void first(Node& i) const { 1069 Parent::first(i); 1070 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 1071 } 1072 1073 void first(Arc& i) const { 1074 Parent::first(i); 1075 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1076 } 1077 1078 void first(Edge& i) const { 1079 Parent::first(i); 1080 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1081 } 1082 1083 void firstIn(Arc& i, const Node& n) const { 1084 Parent::firstIn(i, n); 1085 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 1086 } 1087 1088 void firstOut(Arc& i, const Node& n) const { 1089 Parent::firstOut(i, n); 1090 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 1091 } 1092 1093 void firstInc(Edge& i, bool& d, const Node& n) const { 1094 Parent::firstInc(i, d, n); 1095 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 1096 } 1097 1098 void next(Node& i) const { 1099 Parent::next(i); 1100 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 1101 } 1102 void next(Arc& i) const { 1103 Parent::next(i); 1104 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1105 } 1106 void next(Edge& i) const { 1107 Parent::next(i); 1108 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1109 } 1110 void nextIn(Arc& i) const { 1111 Parent::nextIn(i); 1112 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 1113 } 1114 1115 void nextOut(Arc& i) const { 1116 Parent::nextOut(i); 1117 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 1118 } 1119 void nextInc(Edge& i, bool& d) const { 1120 Parent::nextInc(i, d); 1121 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 1122 } 1123 1124 void hide(const Node& n) const { _node_filter_map->set(n, false); } 1125 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } 1126 1127 void unHide(const Node& n) const { _node_filter_map->set(n, true); } 1128 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } 1129 1130 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 1131 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 1132 1133 typedef False NodeNumTag; 1134 typedef False EdgeNumTag; 1135 1136 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 1137 Arc findArc(const Node& u, const Node& v, 1138 const Arc& prev = INVALID) { 1139 Arc arc = Parent::findArc(u, v, prev); 1140 while (arc != INVALID && !(*_edge_filter_map)[arc]) { 1141 arc = Parent::findArc(u, v, arc); 1142 } 1143 return arc; 1144 } 1145 Edge findEdge(const Node& u, const Node& v, 1146 const Edge& prev = INVALID) { 1147 Edge edge = Parent::findEdge(u, v, prev); 1148 while (edge != INVALID && !(*_edge_filter_map)[edge]) { 1149 edge = Parent::findEdge(u, v, edge); 1150 } 1151 return edge; 1152 } 1153 1154 template <typename _Value> 1155 class NodeMap : public SubMapExtender<Adaptor, 1156 typename Parent::template NodeMap<_Value> > { 1157 public: 1158 typedef _Value Value; 1159 typedef SubMapExtender<Adaptor, typename Parent:: 1160 template NodeMap<Value> > MapParent; 1161 1162 NodeMap(const Adaptor& adaptor) 1163 : MapParent(adaptor) {} 1164 NodeMap(const Adaptor& adaptor, const Value& value) 1165 : MapParent(adaptor, value) {} 1166 1167 private: 1168 NodeMap& operator=(const NodeMap& cmap) { 1169 return operator=<NodeMap>(cmap); 1170 } 1171 1172 template <typename CMap> 1173 NodeMap& operator=(const CMap& cmap) { 1174 MapParent::operator=(cmap); 1175 return *this; 1176 } 1177 }; 1178 1179 template <typename _Value> 1180 class ArcMap : public SubMapExtender<Adaptor, 1181 typename Parent::template ArcMap<_Value> > { 1182 public: 1183 typedef _Value Value; 1184 typedef SubMapExtender<Adaptor, typename Parent:: 1185 template ArcMap<Value> > MapParent; 1186 1187 ArcMap(const Adaptor& adaptor) 1188 : MapParent(adaptor) {} 1189 ArcMap(const Adaptor& adaptor, const Value& value) 1190 : MapParent(adaptor, value) {} 1191 1192 private: 1193 ArcMap& operator=(const ArcMap& cmap) { 1194 return operator=<ArcMap>(cmap); 1195 } 1196 1197 template <typename CMap> 1198 ArcMap& operator=(const CMap& cmap) { 1199 MapParent::operator=(cmap); 1200 return *this; 1201 } 1202 }; 1203 1204 template <typename _Value> 1205 class EdgeMap : public SubMapExtender<Adaptor, 1206 typename Parent::template EdgeMap<_Value> > { 1207 public: 1208 typedef _Value Value; 1209 typedef SubMapExtender<Adaptor, typename Parent:: 1210 template EdgeMap<Value> > MapParent; 1211 1212 EdgeMap(const Adaptor& adaptor) 1213 : MapParent(adaptor) {} 1214 1215 EdgeMap(const Adaptor& adaptor, const _Value& value) 1216 : MapParent(adaptor, value) {} 1217 1218 private: 1219 EdgeMap& operator=(const EdgeMap& cmap) { 1220 return operator=<EdgeMap>(cmap); 1221 } 1222 1223 template <typename CMap> 1224 EdgeMap& operator=(const CMap& cmap) { 1225 MapParent::operator=(cmap); 1226 return *this; 1227 } 1228 }; 1229 1230 }; 1231 1232 /// \ingroup graph_adaptors 1233 /// 1234 /// \brief A graph adaptor for hiding nodes and edges in an 1235 /// undirected graph. 1236 /// 1237 /// SubGraph hides nodes and edges in a graph. A bool node map and a 1238 /// bool edge map must be specified, which define the filters for 1239 /// nodes and edges. Just the nodes and edges with true value are 1240 /// shown in the subgraph. The SubGraph is conform to the \ref 1241 /// concepts::Graph "Graph concept". If the \c _checked parameter is 1242 /// true, then the edges incident to filtered nodes are also 1243 /// filtered out. 1244 /// 1245 /// \tparam _Graph It must be conform to the \ref 1246 /// concepts::Graph "Graph concept". The type can be specified 1247 /// to const. 1248 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1249 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph. 1250 /// \tparam _checked If the parameter is false then the edge filtering 1251 /// is not checked with respect to node filter. Otherwise, each edge 1252 /// is automatically filtered, which is incident to a filtered node. 1253 /// 1254 /// \see FilterNodes 1255 /// \see FilterEdges 1256 template<typename _Graph, typename NodeFilterMap, 1257 typename EdgeFilterMap, bool _checked = true> 1258 class SubGraph 1259 : public GraphAdaptorExtender< 1260 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > { 1261 public: 1262 typedef _Graph Graph; 1263 typedef GraphAdaptorExtender< 1264 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 1265 1266 typedef typename Parent::Node Node; 1267 typedef typename Parent::Edge Edge; 1268 1269 protected: 1270 SubGraph() { } 1271 public: 1272 1273 /// \brief Constructor 1274 /// 1275 /// Creates a subgraph for the given graph with given node and 1276 /// edge map filters. 1277 SubGraph(Graph& _graph, NodeFilterMap& node_filter_map, 1278 EdgeFilterMap& edge_filter_map) { 1279 setGraph(_graph); 1280 setNodeFilterMap(node_filter_map); 1281 setEdgeFilterMap(edge_filter_map); 1282 } 1283 1284 /// \brief Hides the node of the graph 1285 /// 1286 /// This function hides \c n in the graph, i.e. the iteration 1287 /// jumps over it. This is done by simply setting the value of \c n 1288 /// to be false in the corresponding node-map. 1289 void hide(const Node& n) const { Parent::hide(n); } 1290 1291 /// \brief Hides the edge of the graph 1292 /// 1293 /// This function hides \c e in the graph, i.e. the iteration 1294 /// jumps over it. This is done by simply setting the value of \c e 1295 /// to be false in the corresponding edge-map. 1296 void hide(const Edge& e) const { Parent::hide(e); } 1297 1298 /// \brief Unhides the node of the graph 1299 /// 1300 /// The value of \c n is set to be true in the node-map which stores 1301 /// hide information. If \c n was hidden previuosly, then it is shown 1302 /// again 1303 void unHide(const Node& n) const { Parent::unHide(n); } 1304 1305 /// \brief Unhides the edge of the graph 1306 /// 1307 /// The value of \c e is set to be true in the edge-map which stores 1308 /// hide information. If \c e was hidden previuosly, then it is shown 1309 /// again 1310 void unHide(const Edge& e) const { Parent::unHide(e); } 1311 1312 /// \brief Returns true if \c n is hidden. 1313 /// 1314 /// Returns true if \c n is hidden. 1315 /// 1316 bool hidden(const Node& n) const { return Parent::hidden(n); } 1317 1318 /// \brief Returns true if \c e is hidden. 1319 /// 1320 /// Returns true if \c e is hidden. 1321 /// 1322 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1323 }; 1324 1325 /// \brief Just gives back a subgraph 1326 /// 1327 /// Just gives back a subgraph 1328 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1329 SubGraph<const Graph, NodeFilterMap, ArcFilterMap> 1330 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { 1331 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); 1332 } 1333 1334 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1335 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 1336 subGraph(const Graph& graph, 1337 const NodeFilterMap& nfm, ArcFilterMap& efm) { 1338 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 1339 (graph, nfm, efm); 1340 } 1341 1342 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1343 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 1344 subGraph(const Graph& graph, 1345 NodeFilterMap& nfm, const ArcFilterMap& efm) { 1346 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 1347 (graph, nfm, efm); 1348 } 1349 1350 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1351 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 1352 subGraph(const Graph& graph, 1353 const NodeFilterMap& nfm, const ArcFilterMap& efm) { 1354 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 1355 (graph, nfm, efm); 1356 } 1357 1358 /// \ingroup graph_adaptors 1359 /// 1360 /// \brief An adaptor for hiding nodes from a digraph or a graph. 1361 /// 1362 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool 1363 /// node map must be specified, which defines the filters for 1364 /// nodes. Just the unfiltered nodes and the arcs or edges incident 1365 /// to unfiltered nodes are shown in the subdigraph or subgraph. The 1366 /// FilterNodes is conform to the \ref concepts::Digraph 1367 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending 1368 /// on the \c _Digraph template parameter. If the \c _checked 1369 /// parameter is true, then the arc or edges incident to filtered nodes 1370 /// are also filtered out. 1371 /// 1372 /// \tparam _Digraph It must be conform to the \ref 1373 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph 1374 /// "Graph concept". The type can be specified to be const. 1375 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1376 /// \tparam _checked If the parameter is false then the arc or edge 1377 /// filtering is not checked with respect to node filter. In this 1378 /// case just isolated nodes can be filtered out from the 1379 /// graph. 1380 #ifdef DOXYGEN 1381 template<typename _Digraph, 1382 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1383 bool _checked = true> 1384 #else 1385 template<typename _Digraph, 1386 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1387 bool _checked = true, 1388 typename Enable = void> 1389 #endif 1390 class FilterNodes 1391 : public SubDigraph<_Digraph, _NodeFilterMap, 1392 ConstMap<typename _Digraph::Arc, bool>, _checked> { 730 1393 public: 731 1394 … … 733 1396 typedef _NodeFilterMap NodeFilterMap; 734 1397 735 typedef SubDigraph Adaptor<Digraph, NodeFilterMap,736 ConstMap<typename Digraph::Arc, bool>, checked> 1398 typedef SubDigraph<Digraph, NodeFilterMap, 1399 ConstMap<typename Digraph::Arc, bool>, _checked> 737 1400 Parent; 738 1401 … … 742 1405 ConstMap<typename Digraph::Arc, bool> const_true_map; 743 1406 744 NodeSubDigraphAdaptor() : const_true_map(true) {1407 FilterNodes() : const_true_map(true) { 745 1408 Parent::setArcFilterMap(const_true_map); 746 1409 } … … 750 1413 /// \brief Constructor 751 1414 /// 752 /// Creates a node-sub-digraph-adaptor for the given digraph with753 /// given node map filter.754 NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :755 Parent(), const_true_map(true) { 1415 /// Creates an adaptor for the given digraph or graph with 1416 /// given node filter map. 1417 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : 1418 Parent(), const_true_map(true) { 756 1419 Parent::setDigraph(_digraph); 757 1420 Parent::setNodeFilterMap(node_filter); … … 761 1424 /// \brief Hides the node of the graph 762 1425 /// 763 /// This function hides \c n in the digraph , i.e. the iteration764 /// jumps over it. This is done by simply setting the value of \c n 765 /// to be false in the corresponding node -map.1426 /// This function hides \c n in the digraph or graph, i.e. the iteration 1427 /// jumps over it. This is done by simply setting the value of \c n 1428 /// to be false in the corresponding node map. 766 1429 void hide(const Node& n) const { Parent::hide(n); } 767 1430 768 1431 /// \brief Unhides the node of the graph 769 1432 /// 770 /// The value of \c n is set to be true in the node-map which stores 771 /// hide information. If \c n was hidden previuosly, then it is shown 1433 /// The value of \c n is set to be true in the node-map which stores 1434 /// hide information. If \c n was hidden previuosly, then it is shown 772 1435 /// again 773 1436 void unHide(const Node& n) const { Parent::unHide(n); } … … 781 1444 }; 782 1445 783 784 /// \brief Just gives back a node-sub-digraph adaptor 785 /// 786 /// Just gives back a node-sub-digraph adaptor 1446 template<typename _Graph, typename _NodeFilterMap, bool _checked> 1447 class FilterNodes<_Graph, _NodeFilterMap, _checked, 1448 typename enable_if<UndirectedTagIndicator<_Graph> >::type> 1449 : public SubGraph<_Graph, _NodeFilterMap, 1450 ConstMap<typename _Graph::Edge, bool>, _checked> { 1451 public: 1452 typedef _Graph Graph; 1453 typedef _NodeFilterMap NodeFilterMap; 1454 typedef SubGraph<Graph, NodeFilterMap, 1455 ConstMap<typename Graph::Edge, bool> > Parent; 1456 1457 typedef typename Parent::Node Node; 1458 protected: 1459 ConstMap<typename Graph::Edge, bool> const_true_map; 1460 1461 FilterNodes() : const_true_map(true) { 1462 Parent::setEdgeFilterMap(const_true_map); 1463 } 1464 1465 public: 1466 1467 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) : 1468 Parent(), const_true_map(true) { 1469 Parent::setGraph(_graph); 1470 Parent::setNodeFilterMap(node_filter_map); 1471 Parent::setEdgeFilterMap(const_true_map); 1472 } 1473 1474 void hide(const Node& n) const { Parent::hide(n); } 1475 void unHide(const Node& n) const { Parent::unHide(n); } 1476 bool hidden(const Node& n) const { return Parent::hidden(n); } 1477 1478 }; 1479 1480 1481 /// \brief Just gives back a FilterNodes adaptor 1482 /// 1483 /// Just gives back a FilterNodes adaptor 787 1484 template<typename Digraph, typename NodeFilterMap> 788 NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>789 nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {790 return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);1485 FilterNodes<const Digraph, NodeFilterMap> 1486 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { 1487 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); 791 1488 } 792 1489 793 1490 template<typename Digraph, typename NodeFilterMap> 794 NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap> 795 nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) { 796 return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap> 797 (digraph, nfm); 1491 FilterNodes<const Digraph, const NodeFilterMap> 1492 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) { 1493 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm); 798 1494 } 799 1495 800 ///\ingroup graph_adaptors 801 /// 802 ///\brief An adaptor for hiding arcs from a digraph. 803 /// 804 ///An adaptor for hiding arcs from a digraph. This adaptor 805 ///specializes SubDigraphAdaptor in the way that only the arc-set 806 ///can be filtered. The usefulness of this adaptor is demonstrated 807 ///in the problem of searching a maximum number of arc-disjoint 808 ///shortest paths between two nodes \c s and \c t. Shortest here 809 ///means being shortest with respect to non-negative 810 ///arc-lengths. Note that the comprehension of the presented 811 ///solution need's some elementary knowledge from combinatorial 812 ///optimization. 813 /// 814 ///If a single shortest path is to be searched between \c s and \c 815 ///t, then this can be done easily by applying the Dijkstra 816 ///algorithm. What happens, if a maximum number of arc-disjoint 817 ///shortest paths is to be computed. It can be proved that an arc 818 ///can be in a shortest path if and only if it is tight with respect 819 ///to the potential function computed by Dijkstra. Moreover, any 820 ///path containing only such arcs is a shortest one. Thus we have 821 ///to compute a maximum number of arc-disjoint paths between \c s 822 ///and \c t in the digraph which has arc-set all the tight arcs. The 823 ///computation will be demonstrated on the following digraph, which 824 ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim. 825 ///The full source code is available in \ref 826 ///sub_digraph_adaptor_demo.cc. If you are interested in more demo 827 ///programs, you can use \ref dim_to_dot.cc to generate .dot files 828 ///from dimacs files. The .dot file of the following figure was 829 ///generated by the demo program \ref dim_to_dot.cc. 830 /// 831 ///\dot 832 ///digraph lemon_dot_example { 833 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 834 ///n0 [ label="0 (s)" ]; 835 ///n1 [ label="1" ]; 836 ///n2 [ label="2" ]; 837 ///n3 [ label="3" ]; 838 ///n4 [ label="4" ]; 839 ///n5 [ label="5" ]; 840 ///n6 [ label="6 (t)" ]; 841 ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 842 ///n5 -> n6 [ label="9, length:4" ]; 843 ///n4 -> n6 [ label="8, length:2" ]; 844 ///n3 -> n5 [ label="7, length:1" ]; 845 ///n2 -> n5 [ label="6, length:3" ]; 846 ///n2 -> n6 [ label="5, length:5" ]; 847 ///n2 -> n4 [ label="4, length:2" ]; 848 ///n1 -> n4 [ label="3, length:3" ]; 849 ///n0 -> n3 [ label="2, length:1" ]; 850 ///n0 -> n2 [ label="1, length:2" ]; 851 ///n0 -> n1 [ label="0, length:3" ]; 852 ///} 853 ///\enddot 854 /// 855 ///\code 856 ///Digraph g; 857 ///Node s, t; 858 ///LengthMap length(g); 859 /// 860 ///readDimacs(std::cin, g, length, s, t); 861 /// 862 ///cout << "arcs with lengths (of form id, source--length->target): " << endl; 863 ///for(ArcIt e(g); e!=INVALID; ++e) 864 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 865 /// << length[e] << "->" << g.id(g.target(e)) << endl; 866 /// 867 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 868 ///\endcode 869 ///Next, the potential function is computed with Dijkstra. 870 ///\code 871 ///typedef Dijkstra<Digraph, LengthMap> Dijkstra; 872 ///Dijkstra dijkstra(g, length); 873 ///dijkstra.run(s); 874 ///\endcode 875 ///Next, we consrtruct a map which filters the arc-set to the tight arcs. 876 ///\code 877 ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap> 878 /// TightArcFilter; 879 ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length); 880 /// 881 ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA; 882 ///SubGA ga(g, tight_arc_filter); 883 ///\endcode 884 ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed 885 ///with a max flow algorithm Preflow. 886 ///\code 887 ///ConstMap<Arc, int> const_1_map(1); 888 ///Digraph::ArcMap<int> flow(g, 0); 889 /// 890 ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> > 891 /// preflow(ga, const_1_map, s, t); 892 ///preflow.run(); 893 ///\endcode 894 ///Last, the output is: 895 ///\code 896 ///cout << "maximum number of arc-disjoint shortest path: " 897 /// << preflow.flowValue() << endl; 898 ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: " 899 /// << endl; 900 ///for(ArcIt e(g); e!=INVALID; ++e) 901 /// if (preflow.flow(e)) 902 /// cout << " " << g.id(g.source(e)) << "--" 903 /// << length[e] << "->" << g.id(g.target(e)) << endl; 904 ///\endcode 905 ///The program has the following (expected :-)) output: 906 ///\code 907 ///arcs with lengths (of form id, source--length->target): 908 /// 9, 5--4->6 909 /// 8, 4--2->6 910 /// 7, 3--1->5 911 /// 6, 2--3->5 912 /// 5, 2--5->6 913 /// 4, 2--2->4 914 /// 3, 1--3->4 915 /// 2, 0--1->3 916 /// 1, 0--2->2 917 /// 0, 0--3->1 918 ///s: 0 t: 6 919 ///maximum number of arc-disjoint shortest path: 2 920 ///arcs of the maximum number of arc-disjoint shortest s-t paths: 921 /// 9, 5--4->6 922 /// 8, 4--2->6 923 /// 7, 3--1->5 924 /// 4, 2--2->4 925 /// 2, 0--1->3 926 /// 1, 0--2->2 927 ///\endcode 1496 /// \ingroup graph_adaptors 1497 /// 1498 /// \brief An adaptor for hiding arcs from a digraph. 1499 /// 1500 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must 1501 /// be specified, which defines the filters for arcs. Just the 1502 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is 1503 /// conform to the \ref concepts::Digraph "Digraph concept". 1504 /// 1505 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 1506 /// "Digraph concept". The type can be specified to be const. 1507 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted 1508 /// graph. 928 1509 template<typename _Digraph, typename _ArcFilterMap> 929 class ArcSubDigraphAdaptor :930 public SubDigraph Adaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,931 1510 class FilterArcs : 1511 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, 1512 _ArcFilterMap, false> { 932 1513 public: 933 1514 typedef _Digraph Digraph; 934 1515 typedef _ArcFilterMap ArcFilterMap; 935 1516 936 typedef SubDigraph Adaptor<Digraph, ConstMap<typename Digraph::Node, bool>,937 1517 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, 1518 ArcFilterMap, false> Parent; 938 1519 939 1520 typedef typename Parent::Arc Arc; … … 942 1523 ConstMap<typename Digraph::Node, bool> const_true_map; 943 1524 944 ArcSubDigraphAdaptor() : const_true_map(true) {1525 FilterArcs() : const_true_map(true) { 945 1526 Parent::setNodeFilterMap(const_true_map); 946 1527 } … … 950 1531 /// \brief Constructor 951 1532 /// 952 /// Creates a arc-sub-digraph-adaptor for the given digraph with1533 /// Creates a FilterArcs adaptor for the given graph with 953 1534 /// given arc map filter. 954 ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)955 : Parent(), const_true_map(true) { 1535 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 1536 : Parent(), const_true_map(true) { 956 1537 Parent::setDigraph(digraph); 957 1538 Parent::setNodeFilterMap(const_true_map); … … 961 1542 /// \brief Hides the arc of the graph 962 1543 /// 963 /// This function hides \c a in the digraph, i.e. the iteration1544 /// This function hides \c a in the graph, i.e. the iteration 964 1545 /// jumps over it. This is done by simply setting the value of \c a 965 /// to be false in the corresponding arc -map.1546 /// to be false in the corresponding arc map. 966 1547 void hide(const Arc& a) const { Parent::hide(a); } 967 1548 968 1549 /// \brief Unhides the arc of the graph 969 1550 /// 970 /// The value of \c a is set to be true in the arc-map which stores 971 /// hide information. If \c a was hidden previuosly, then it is shown 1551 /// The value of \c a is set to be true in the arc-map which stores 1552 /// hide information. If \c a was hidden previuosly, then it is shown 972 1553 /// again 973 1554 void unHide(const Arc& a) const { Parent::unHide(a); } … … 981 1562 }; 982 1563 983 /// \brief Just gives back an arc-sub-digraphadaptor984 /// 985 /// Just gives back an arc-sub-digraphadaptor1564 /// \brief Just gives back an FilterArcs adaptor 1565 /// 1566 /// Just gives back an FilterArcs adaptor 986 1567 template<typename Digraph, typename ArcFilterMap> 987 ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>988 arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {989 return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);1568 FilterArcs<const Digraph, ArcFilterMap> 1569 filterArcs(const Digraph& digraph, ArcFilterMap& afm) { 1570 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); 990 1571 } 991 1572 992 1573 template<typename Digraph, typename ArcFilterMap> 993 ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap> 994 arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) { 995 return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap> 996 (digraph, afm); 1574 FilterArcs<const Digraph, const ArcFilterMap> 1575 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) { 1576 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm); 997 1577 } 998 1578 1579 /// \ingroup graph_adaptors 1580 /// 1581 /// \brief An adaptor for hiding edges from a graph. 1582 /// 1583 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must 1584 /// be specified, which defines the filters for edges. Just the 1585 /// unfiltered edges are shown in the subdigraph. The FilterEdges is 1586 /// conform to the \ref concepts::Graph "Graph concept". 1587 /// 1588 /// \tparam _Graph It must be conform to the \ref concepts::Graph 1589 /// "Graph concept". The type can be specified to be const. 1590 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted 1591 /// graph. 1592 template<typename _Graph, typename _EdgeFilterMap> 1593 class FilterEdges : 1594 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, 1595 _EdgeFilterMap, false> { 1596 public: 1597 typedef _Graph Graph; 1598 typedef _EdgeFilterMap EdgeFilterMap; 1599 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, 1600 EdgeFilterMap, false> Parent; 1601 typedef typename Parent::Edge Edge; 1602 protected: 1603 ConstMap<typename Graph::Node, bool> const_true_map; 1604 1605 FilterEdges() : const_true_map(true) { 1606 Parent::setNodeFilterMap(const_true_map); 1607 } 1608 1609 public: 1610 1611 /// \brief Constructor 1612 /// 1613 /// Creates a FilterEdges adaptor for the given graph with 1614 /// given edge map filters. 1615 FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) : 1616 Parent(), const_true_map(true) { 1617 Parent::setGraph(_graph); 1618 Parent::setNodeFilterMap(const_true_map); 1619 Parent::setEdgeFilterMap(edge_filter_map); 1620 } 1621 1622 /// \brief Hides the edge of the graph 1623 /// 1624 /// This function hides \c e in the graph, i.e. the iteration 1625 /// jumps over it. This is done by simply setting the value of \c e 1626 /// to be false in the corresponding edge-map. 1627 void hide(const Edge& e) const { Parent::hide(e); } 1628 1629 /// \brief Unhides the edge of the graph 1630 /// 1631 /// The value of \c e is set to be true in the edge-map which stores 1632 /// hide information. If \c e was hidden previuosly, then it is shown 1633 /// again 1634 void unHide(const Edge& e) const { Parent::unHide(e); } 1635 1636 /// \brief Returns true if \c e is hidden. 1637 /// 1638 /// Returns true if \c e is hidden. 1639 /// 1640 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1641 1642 }; 1643 1644 /// \brief Just gives back a FilterEdges adaptor 1645 /// 1646 /// Just gives back a FilterEdges adaptor 1647 template<typename Graph, typename EdgeFilterMap> 1648 FilterEdges<const Graph, EdgeFilterMap> 1649 filterEdges(const Graph& graph, EdgeFilterMap& efm) { 1650 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm); 1651 } 1652 1653 template<typename Graph, typename EdgeFilterMap> 1654 FilterEdges<const Graph, const EdgeFilterMap> 1655 filterEdges(const Graph& graph, const EdgeFilterMap& efm) { 1656 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm); 1657 } 1658 999 1659 template <typename _Digraph> 1000 class Undir DigraphAdaptorBase {1660 class UndirectorBase { 1001 1661 public: 1002 1662 typedef _Digraph Digraph; 1003 typedef Undir DigraphAdaptorBase Adaptor;1663 typedef UndirectorBase Adaptor; 1004 1664 1005 1665 typedef True UndirectedTag; … … 1009 1669 1010 1670 class Arc : public Edge { 1011 friend class Undir DigraphAdaptorBase;1671 friend class UndirectorBase; 1012 1672 protected: 1013 1673 bool _forward; … … 1022 1682 1023 1683 bool operator==(const Arc &other) const { 1024 return _forward == other._forward && 1025 1684 return _forward == other._forward && 1685 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); 1026 1686 } 1027 1687 bool operator!=(const Arc &other) const { 1028 return _forward != other._forward || 1029 1688 return _forward != other._forward || 1689 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); 1030 1690 } 1031 1691 bool operator<(const Arc &other) const { 1032 1033 1034 1692 return _forward < other._forward || 1693 (_forward == other._forward && 1694 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); 1035 1695 } 1036 1696 }; … … 1053 1713 void next(Arc& a) const { 1054 1714 if (a._forward) { 1055 1715 a._forward = false; 1056 1716 } else { 1057 1058 1717 _digraph->next(a); 1718 a._forward = true; 1059 1719 } 1060 1720 } … … 1071 1731 _digraph->firstIn(a, n); 1072 1732 if( static_cast<const Edge&>(a) != INVALID ) { 1073 1733 a._forward = false; 1074 1734 } else { 1075 1076 1735 _digraph->firstOut(a, n); 1736 a._forward = true; 1077 1737 } 1078 1738 } 1079 1739 void nextOut(Arc &a) const { 1080 1740 if (!a._forward) { 1081 1082 1083 1084 1085 1086 1741 Node n = _digraph->target(a); 1742 _digraph->nextIn(a); 1743 if (static_cast<const Edge&>(a) == INVALID ) { 1744 _digraph->firstOut(a, n); 1745 a._forward = true; 1746 } 1087 1747 } 1088 1748 else { 1089 1749 _digraph->nextOut(a); 1090 1750 } 1091 1751 } … … 1094 1754 _digraph->firstOut(a, n); 1095 1755 if (static_cast<const Edge&>(a) != INVALID ) { 1096 1756 a._forward = false; 1097 1757 } else { 1098 1099 1758 _digraph->firstIn(a, n); 1759 a._forward = true; 1100 1760 } 1101 1761 } 1102 1762 void nextIn(Arc &a) const { 1103 1763 if (!a._forward) { 1104 1105 1106 1107 1108 1109 1764 Node n = _digraph->source(a); 1765 _digraph->nextOut(a); 1766 if( static_cast<const Edge&>(a) == INVALID ) { 1767 _digraph->firstIn(a, n); 1768 a._forward = true; 1769 } 1110 1770 } 1111 1771 else { 1112 1772 _digraph->nextIn(a); 1113 1773 } 1114 1774 } … … 1124 1784 void nextInc(Edge &e, bool &d) const { 1125 1785 if (d) { 1126 1127 1128 1129 1130 1786 Node s = _digraph->source(e); 1787 _digraph->nextOut(e); 1788 if (e != INVALID) return; 1789 d = false; 1790 _digraph->firstIn(e, s); 1131 1791 } else { 1132 1792 _digraph->nextIn(e); 1133 1793 } 1134 1794 } … … 1176 1836 1177 1837 Node addNode() { return _digraph->addNode(); } 1178 Edge addEdge(const Node& u, const Node& v) { 1179 return _digraph->addArc(u, v); 1838 Edge addEdge(const Node& u, const Node& v) { 1839 return _digraph->addArc(u, v); 1180 1840 } 1181 1841 1182 1842 void erase(const Node& i) { _digraph->erase(i); } 1183 1843 void erase(const Edge& i) { _digraph->erase(i); } 1184 1844 1185 1845 void clear() { _digraph->clear(); } 1186 1846 … … 1194 1854 Arc findArc(Node s, Node t, Arc p = INVALID) const { 1195 1855 if (p == INVALID) { 1196 1197 1198 1199 1856 Edge arc = _digraph->findArc(s, t); 1857 if (arc != INVALID) return direct(arc, true); 1858 arc = _digraph->findArc(t, s); 1859 if (arc != INVALID) return direct(arc, false); 1200 1860 } else if (direction(p)) { 1201 1202 1203 1204 if (arc != INVALID) return direct(arc, false); 1861 Edge arc = _digraph->findArc(s, t, p); 1862 if (arc != INVALID) return direct(arc, true); 1863 arc = _digraph->findArc(t, s); 1864 if (arc != INVALID) return direct(arc, false); 1205 1865 } else { 1206 1207 if (arc != INVALID) return direct(arc, false); 1866 Edge arc = _digraph->findArc(t, s, p); 1867 if (arc != INVALID) return direct(arc, false); 1208 1868 } 1209 1869 return INVALID; … … 1221 1881 if (arc != INVALID) return arc; 1222 1882 arc = _digraph->findArc(t, s); 1223 if (arc != INVALID) return arc; 1883 if (arc != INVALID) return arc; 1224 1884 } else { 1225 1885 Edge arc = _digraph->findArc(t, s, p); 1226 if (arc != INVALID) return arc; 1886 if (arc != INVALID) return arc; 1227 1887 } 1228 1888 } else { … … 1233 1893 1234 1894 private: 1235 1895 1236 1896 template <typename _Value> 1237 1897 class ArcMapBase { 1238 1898 private: 1239 1899 1240 1900 typedef typename Digraph::template ArcMap<_Value> MapImpl; 1241 1901 1242 1902 public: 1243 1903 … … 1246 1906 typedef _Value Value; 1247 1907 typedef Arc Key; 1248 1908 1249 1909 ArcMapBase(const Adaptor& adaptor) : 1250 1251 1252 ArcMapBase(const Adaptor& adaptor, const Value& v) 1910 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 1911 1912 ArcMapBase(const Adaptor& adaptor, const Value& v) 1253 1913 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {} 1254 1255 void set(const Arc& a, const Value& v) { 1256 if (direction(a)) { 1257 _forward.set(a, v); 1258 } else { 1259 _backward.set(a, v); 1260 } 1261 } 1262 1263 typename MapTraits<MapImpl>::ConstReturnValue 1264 operator[](const Arc& a) const { 1265 if (direction(a)) { 1266 return _forward[a]; 1267 } else { 1268 return _backward[a]; 1914 1915 void set(const Arc& a, const Value& v) { 1916 if (direction(a)) { 1917 _forward.set(a, v); 1918 } else { 1919 _backward.set(a, v); 1269 1920 } 1270 1921 } 1271 1922 1272 typename MapTraits<MapImpl>:: ReturnValue1273 operator[](const Arc& a) {1274 1275 return _forward[a]; 1276 } else { 1277 return _backward[a]; 1923 typename MapTraits<MapImpl>::ConstReturnValue 1924 operator[](const Arc& a) const { 1925 if (direction(a)) { 1926 return _forward[a]; 1927 } else { 1928 return _backward[a]; 1278 1929 } 1279 1930 } 1280 1931 1932 typename MapTraits<MapImpl>::ReturnValue 1933 operator[](const Arc& a) { 1934 if (direction(a)) { 1935 return _forward[a]; 1936 } else { 1937 return _backward[a]; 1938 } 1939 } 1940 1281 1941 protected: 1282 1942 1283 MapImpl _forward, _backward; 1943 MapImpl _forward, _backward; 1284 1944 1285 1945 }; … … 1294 1954 typedef typename Digraph::template NodeMap<Value> Parent; 1295 1955 1296 explicit NodeMap(const Adaptor& adaptor) 1297 1956 explicit NodeMap(const Adaptor& adaptor) 1957 : Parent(*adaptor._digraph) {} 1298 1958 1299 1959 NodeMap(const Adaptor& adaptor, const _Value& value) 1300 1960 : Parent(*adaptor._digraph, value) { } 1301 1961 1302 1962 private: … … 1310 1970 return *this; 1311 1971 } 1312 1972 1313 1973 }; 1314 1974 1315 1975 template <typename _Value> 1316 class ArcMap 1317 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 1976 class ArcMap 1977 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 1318 1978 { 1319 1979 public: 1320 1980 typedef _Value Value; 1321 1981 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 1322 1323 ArcMap(const Adaptor& adaptor) 1324 1325 1326 ArcMap(const Adaptor& adaptor, const Value& value) 1327 1328 1982 1983 ArcMap(const Adaptor& adaptor) 1984 : Parent(adaptor) {} 1985 1986 ArcMap(const Adaptor& adaptor, const Value& value) 1987 : Parent(adaptor, value) {} 1988 1329 1989 private: 1330 1990 ArcMap& operator=(const ArcMap& cmap) { 1331 1332 } 1333 1991 return operator=<ArcMap>(cmap); 1992 } 1993 1334 1994 template <typename CMap> 1335 1995 ArcMap& operator=(const CMap& cmap) { 1336 1996 Parent::operator=(cmap); 1337 1997 return *this; 1338 1998 } 1339 1999 }; 1340 2000 1341 2001 template <typename _Value> 1342 2002 class EdgeMap : public Digraph::template ArcMap<_Value> { 1343 2003 public: 1344 2004 1345 2005 typedef _Value Value; 1346 2006 typedef typename Digraph::template ArcMap<Value> Parent; 1347 1348 explicit EdgeMap(const Adaptor& adaptor) 1349 2007 2008 explicit EdgeMap(const Adaptor& adaptor) 2009 : Parent(*adaptor._digraph) {} 1350 2010 1351 2011 EdgeMap(const Adaptor& adaptor, const Value& value) 1352 2012 : Parent(*adaptor._digraph, value) {} 1353 2013 1354 2014 private: … … 1366 2026 1367 2027 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 1368 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 2028 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 1369 2029 1370 2030 protected: 1371 2031 1372 Undir DigraphAdaptorBase() : _digraph(0) {}2032 UndirectorBase() : _digraph(0) {} 1373 2033 1374 2034 Digraph* _digraph; … … 1377 2037 _digraph = &digraph; 1378 2038 } 1379 2039 1380 2040 }; 1381 2041 1382 /// \ingroup graph_adaptors1383 /// 1384 /// \brief A graph is made from a directed digraph by an adaptor2042 /// \ingroup graph_adaptors 2043 /// 2044 /// \brief Undirect the graph 1385 2045 /// 1386 2046 /// This adaptor makes an undirected graph from a directed 1387 /// graph. All arc of the underlying digraph will be showed in the 1388 /// adaptor as an edge. Let's see an informal example about using 1389 /// this adaptor. 1390 /// 1391 /// There is a network of the streets of a town. Of course there are 1392 /// some one-way street in the town hence the network is a directed 1393 /// one. There is a crazy driver who go oppositely in the one-way 1394 /// street without moral sense. Of course he can pass this streets 1395 /// slower than the regular way, in fact his speed is half of the 1396 /// normal speed. How long should he drive to get from a source 1397 /// point to the target? Let see the example code which calculate it: 1398 /// 1399 /// \todo BadCode, SimpleMap does no exists 1400 ///\code 1401 /// typedef UndirDigraphAdaptor<Digraph> Graph; 1402 /// Graph graph(digraph); 1403 /// 1404 /// typedef SimpleMap<LengthMap> FLengthMap; 1405 /// FLengthMap flength(length); 1406 /// 1407 /// typedef ScaleMap<LengthMap> RLengthMap; 1408 /// RLengthMap rlength(length, 2.0); 1409 /// 1410 /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap; 1411 /// ULengthMap ulength(flength, rlength); 1412 /// 1413 /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength); 1414 /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl; 1415 ///\endcode 1416 /// 1417 /// The combined arc map makes the length map for the undirected 1418 /// graph. It is created from a forward and reverse map. The forward 1419 /// map is created from the original length map with a SimpleMap 1420 /// adaptor which just makes a read-write map from the reference map 1421 /// i.e. it forgets that it can be return reference to values. The 1422 /// reverse map is just the scaled original map with the ScaleMap 1423 /// adaptor. The combination solves that passing the reverse way 1424 /// takes double time than the original. To get the driving time we 1425 /// run the dijkstra algorithm on the graph. 2047 /// graph. All arcs of the underlying digraph will be showed in the 2048 /// adaptor as an edge. The Orienter adaptor is conform to the \ref 2049 /// concepts::Graph "Graph concept". 2050 /// 2051 /// \tparam _Digraph It must be conform to the \ref 2052 /// concepts::Digraph "Digraph concept". The type can be specified 2053 /// to const. 1426 2054 template<typename _Digraph> 1427 class Undir DigraphAdaptor1428 : public GraphAdaptorExtender<Undir DigraphAdaptorBase<_Digraph> > {2055 class Undirector 2056 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > { 1429 2057 public: 1430 2058 typedef _Digraph Digraph; 1431 typedef GraphAdaptorExtender<Undir DigraphAdaptorBase<Digraph> > Parent;2059 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent; 1432 2060 protected: 1433 Undir DigraphAdaptor() { }2061 Undirector() { } 1434 2062 public: 1435 2063 1436 2064 /// \brief Constructor 1437 2065 /// 1438 /// C onstructor1439 Undir DigraphAdaptor(_Digraph& _digraph) {1440 setDigraph( _digraph);2066 /// Creates a undirected graph from the given digraph 2067 Undirector(_Digraph& digraph) { 2068 setDigraph(digraph); 1441 2069 } 1442 2070 … … 1444 2072 /// 1445 2073 /// This class adapts two original digraph ArcMap to 1446 /// get an arc map on the adaptor.2074 /// get an arc map on the undirected graph. 1447 2075 template <typename _ForwardMap, typename _BackwardMap> 1448 2076 class CombinedArcMap { 1449 2077 public: 1450 2078 1451 2079 typedef _ForwardMap ForwardMap; 1452 2080 typedef _BackwardMap BackwardMap; … … 1457 2085 typedef typename Parent::Arc Key; 1458 2086 1459 /// \brief Constructor 2087 /// \brief Constructor 1460 2088 /// 1461 /// Constructor 1462 CombinedArcMap() : _forward(0), _backward(0) {} 1463 1464 /// \brief Constructor 1465 /// 1466 /// Constructor 1467 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 2089 /// Constructor 2090 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 1468 2091 : _forward(&forward), _backward(&backward) {} 1469 2092 1470 2093 1471 2094 /// \brief Sets the value associated with a key. 1472 2095 /// 1473 2096 /// Sets the value associated with a key. 1474 void set(const Key& e, const Value& a) { 1475 1476 _forward->set(e, a); 1477 } else { 1478 1479 } 2097 void set(const Key& e, const Value& a) { 2098 if (Parent::direction(e)) { 2099 _forward->set(e, a); 2100 } else { 2101 _backward->set(e, a); 2102 } 1480 2103 } 1481 2104 … … 1483 2106 /// 1484 2107 /// Returns the value associated with a key. 1485 typename MapTraits<ForwardMap>::ConstReturnValue 1486 operator[](const Key& e) const { 1487 1488 return (*_forward)[e]; 1489 } else { 1490 return (*_backward)[e]; 2108 typename MapTraits<ForwardMap>::ConstReturnValue 2109 operator[](const Key& e) const { 2110 if (Parent::direction(e)) { 2111 return (*_forward)[e]; 2112 } else { 2113 return (*_backward)[e]; 1491 2114 } 1492 2115 } … … 1495 2118 /// 1496 2119 /// Returns the value associated with a key. 1497 typename MapTraits<ForwardMap>::ReturnValue 1498 operator[](const Key& e) { 1499 1500 return (*_forward)[e]; 1501 } else { 1502 return (*_backward)[e]; 2120 typename MapTraits<ForwardMap>::ReturnValue 2121 operator[](const Key& e) { 2122 if (Parent::direction(e)) { 2123 return (*_forward)[e]; 2124 } else { 2125 return (*_backward)[e]; 1503 2126 } 1504 2127 } 1505 2128 1506 /// \brief Sets the forward map1507 ///1508 /// Sets the forward map1509 void setForwardMap(ForwardMap& forward) {1510 _forward = &forward;1511 }1512 1513 /// \brief Sets the backward map1514 ///1515 /// Sets the backward map1516 void setBackwardMap(BackwardMap& backward) {1517 _backward = &backward;1518 }1519 1520 2129 protected: 1521 2130 1522 2131 ForwardMap* _forward; 1523 BackwardMap* _backward; 2132 BackwardMap* _backward; 1524 2133 1525 2134 }; 1526 2135 2136 /// \brief Just gives back a combined arc map 2137 /// 2138 /// Just gives back a combined arc map 2139 template <typename ForwardMap, typename BackwardMap> 2140 static CombinedArcMap<ForwardMap, BackwardMap> 2141 combinedArcMap(ForwardMap& forward, BackwardMap& backward) { 2142 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward); 2143 } 2144 2145 template <typename ForwardMap, typename BackwardMap> 2146 static CombinedArcMap<const ForwardMap, BackwardMap> 2147 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { 2148 return CombinedArcMap<const ForwardMap, 2149 BackwardMap>(forward, backward); 2150 } 2151 2152 template <typename ForwardMap, typename BackwardMap> 2153 static CombinedArcMap<ForwardMap, const BackwardMap> 2154 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { 2155 return CombinedArcMap<ForwardMap, 2156 const BackwardMap>(forward, backward); 2157 } 2158 2159 template <typename ForwardMap, typename BackwardMap> 2160 static CombinedArcMap<const ForwardMap, const BackwardMap> 2161 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { 2162 return CombinedArcMap<const ForwardMap, 2163 const BackwardMap>(forward, backward); 2164 } 2165 1527 2166 }; 1528 2167 1529 /// \brief Just gives back an undir digraph adaptor1530 /// 1531 /// Just gives back an undir digraph adaptor2168 /// \brief Just gives back an undirected view of the given digraph 2169 /// 2170 /// Just gives back an undirected view of the given digraph 1532 2171 template<typename Digraph> 1533 Undir DigraphAdaptor<const Digraph>1534 undir DigraphAdaptor(const Digraph& digraph) {1535 return Undir DigraphAdaptor<const Digraph>(digraph);2172 Undirector<const Digraph> 2173 undirector(const Digraph& digraph) { 2174 return Undirector<const Digraph>(digraph); 1536 2175 } 1537 2176 1538 template<typename _Digraph, 1539 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 1540 typename _FlowMap = _CapacityMap, 2177 template <typename _Graph, typename _DirectionMap> 2178 class OrienterBase { 2179 public: 2180 2181 typedef _Graph Graph; 2182 typedef _DirectionMap DirectionMap; 2183 2184 typedef typename Graph::Node Node; 2185 typedef typename Graph::Edge Arc; 2186 2187 void reverseArc(const Arc& arc) { 2188 _direction->set(arc, !(*_direction)[arc]); 2189 } 2190 2191 void first(Node& i) const { _graph->first(i); } 2192 void first(Arc& i) const { _graph->first(i); } 2193 void firstIn(Arc& i, const Node& n) const { 2194 bool d; 2195 _graph->firstInc(i, d, n); 2196 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 2197 } 2198 void firstOut(Arc& i, const Node& n ) const { 2199 bool d; 2200 _graph->firstInc(i, d, n); 2201 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); 2202 } 2203 2204 void next(Node& i) const { _graph->next(i); } 2205 void next(Arc& i) const { _graph->next(i); } 2206 void nextIn(Arc& i) const { 2207 bool d = !(*_direction)[i]; 2208 _graph->nextInc(i, d); 2209 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 2210 } 2211 void nextOut(Arc& i) const { 2212 bool d = (*_direction)[i]; 2213 _graph->nextInc(i, d); 2214 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); 2215 } 2216 2217 Node source(const Arc& e) const { 2218 return (*_direction)[e] ? _graph->u(e) : _graph->v(e); 2219 } 2220 Node target(const Arc& e) const { 2221 return (*_direction)[e] ? _graph->v(e) : _graph->u(e); 2222 } 2223 2224 typedef NodeNumTagIndicator<Graph> NodeNumTag; 2225 int nodeNum() const { return _graph->nodeNum(); } 2226 2227 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 2228 int arcNum() const { return _graph->edgeNum(); } 2229 2230 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 2231 Arc findArc(const Node& u, const Node& v, 2232 const Arc& prev = INVALID) { 2233 Arc arc = prev; 2234 bool d = arc == INVALID ? true : (*_direction)[arc]; 2235 if (d) { 2236 arc = _graph->findEdge(u, v, arc); 2237 while (arc != INVALID && !(*_direction)[arc]) { 2238 _graph->findEdge(u, v, arc); 2239 } 2240 if (arc != INVALID) return arc; 2241 } 2242 _graph->findEdge(v, u, arc); 2243 while (arc != INVALID && (*_direction)[arc]) { 2244 _graph->findEdge(u, v, arc); 2245 } 2246 return arc; 2247 } 2248 2249 Node addNode() { 2250 return Node(_graph->addNode()); 2251 } 2252 2253 Arc addArc(const Node& u, const Node& v) { 2254 Arc arc = _graph->addArc(u, v); 2255 _direction->set(arc, _graph->source(arc) == u); 2256 return arc; 2257 } 2258 2259 void erase(const Node& i) { _graph->erase(i); } 2260 void erase(const Arc& i) { _graph->erase(i); } 2261 2262 void clear() { _graph->clear(); } 2263 2264 int id(const Node& v) const { return _graph->id(v); } 2265 int id(const Arc& e) const { return _graph->id(e); } 2266 2267 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); } 2268 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); } 2269 2270 int maxNodeId() const { return _graph->maxNodeId(); } 2271 int maxArcId() const { return _graph->maxEdgeId(); } 2272 2273 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 2274 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 2275 2276 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 2277 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 2278 2279 template <typename _Value> 2280 class NodeMap : public _Graph::template NodeMap<_Value> { 2281 public: 2282 2283 typedef typename _Graph::template NodeMap<_Value> Parent; 2284 2285 explicit NodeMap(const OrienterBase& adapter) 2286 : Parent(*adapter._graph) {} 2287 2288 NodeMap(const OrienterBase& adapter, const _Value& value) 2289 : Parent(*adapter._graph, value) {} 2290 2291 private: 2292 NodeMap& operator=(const NodeMap& cmap) { 2293 return operator=<NodeMap>(cmap); 2294 } 2295 2296 template <typename CMap> 2297 NodeMap& operator=(const CMap& cmap) { 2298 Parent::operator=(cmap); 2299 return *this; 2300 } 2301 2302 }; 2303 2304 template <typename _Value> 2305 class ArcMap : public _Graph::template EdgeMap<_Value> { 2306 public: 2307 2308 typedef typename Graph::template EdgeMap<_Value> Parent; 2309 2310 explicit ArcMap(const OrienterBase& adapter) 2311 : Parent(*adapter._graph) { } 2312 2313 ArcMap(const OrienterBase& adapter, const _Value& value) 2314 : Parent(*adapter._graph, value) { } 2315 2316 private: 2317 ArcMap& operator=(const ArcMap& cmap) { 2318 return operator=<ArcMap>(cmap); 2319 } 2320 2321 template <typename CMap> 2322 ArcMap& operator=(const CMap& cmap) { 2323 Parent::operator=(cmap); 2324 return *this; 2325 } 2326 }; 2327 2328 2329 2330 protected: 2331 Graph* _graph; 2332 DirectionMap* _direction; 2333 2334 void setDirectionMap(DirectionMap& direction) { 2335 _direction = &direction; 2336 } 2337 2338 void setGraph(Graph& graph) { 2339 _graph = &graph; 2340 } 2341 2342 }; 2343 2344 /// \ingroup graph_adaptors 2345 /// 2346 /// \brief Orients the edges of the graph to get a digraph 2347 /// 2348 /// This adaptor orients each edge in the undirected graph. The 2349 /// direction of the arcs stored in an edge node map. The arcs can 2350 /// be easily reverted by the \c reverseArc() member function in the 2351 /// adaptor. The Orienter adaptor is conform to the \ref 2352 /// concepts::Digraph "Digraph concept". 2353 /// 2354 /// \tparam _Graph It must be conform to the \ref concepts::Graph 2355 /// "Graph concept". The type can be specified to be const. 2356 /// \tparam _DirectionMap A bool valued edge map of the the adapted 2357 /// graph. 2358 /// 2359 /// \sa orienter 2360 template<typename _Graph, 2361 typename DirectionMap = typename _Graph::template EdgeMap<bool> > 2362 class Orienter : 2363 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 2364 public: 2365 typedef _Graph Graph; 2366 typedef DigraphAdaptorExtender< 2367 OrienterBase<_Graph, DirectionMap> > Parent; 2368 typedef typename Parent::Arc Arc; 2369 protected: 2370 Orienter() { } 2371 public: 2372 2373 /// \brief Constructor of the adaptor 2374 /// 2375 /// Constructor of the adaptor 2376 Orienter(Graph& graph, DirectionMap& direction) { 2377 setGraph(graph); 2378 setDirectionMap(direction); 2379 } 2380 2381 /// \brief Reverse arc 2382 /// 2383 /// It reverse the given arc. It simply negate the direction in the map. 2384 void reverseArc(const Arc& a) { 2385 Parent::reverseArc(a); 2386 } 2387 }; 2388 2389 /// \brief Just gives back a Orienter 2390 /// 2391 /// Just gives back a Orienter 2392 template<typename Graph, typename DirectionMap> 2393 Orienter<const Graph, DirectionMap> 2394 orienter(const Graph& graph, DirectionMap& dm) { 2395 return Orienter<const Graph, DirectionMap>(graph, dm); 2396 } 2397 2398 template<typename Graph, typename DirectionMap> 2399 Orienter<const Graph, const DirectionMap> 2400 orienter(const Graph& graph, const DirectionMap& dm) { 2401 return Orienter<const Graph, const DirectionMap>(graph, dm); 2402 } 2403 2404 namespace _adaptor_bits { 2405 2406 template<typename _Digraph, 2407 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2408 typename _FlowMap = _CapacityMap, 2409 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2410 class ResForwardFilter { 2411 public: 2412 2413 typedef _Digraph Digraph; 2414 typedef _CapacityMap CapacityMap; 2415 typedef _FlowMap FlowMap; 2416 typedef _Tolerance Tolerance; 2417 2418 typedef typename Digraph::Arc Key; 2419 typedef bool Value; 2420 2421 private: 2422 2423 const CapacityMap* _capacity; 2424 const FlowMap* _flow; 2425 Tolerance _tolerance; 2426 public: 2427 2428 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow, 2429 const Tolerance& tolerance = Tolerance()) 2430 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2431 2432 bool operator[](const typename Digraph::Arc& a) const { 2433 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 2434 } 2435 }; 2436 2437 template<typename _Digraph, 2438 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2439 typename _FlowMap = _CapacityMap, 2440 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2441 class ResBackwardFilter { 2442 public: 2443 2444 typedef _Digraph Digraph; 2445 typedef _CapacityMap CapacityMap; 2446 typedef _FlowMap FlowMap; 2447 typedef _Tolerance Tolerance; 2448 2449 typedef typename Digraph::Arc Key; 2450 typedef bool Value; 2451 2452 private: 2453 2454 const CapacityMap* _capacity; 2455 const FlowMap* _flow; 2456 Tolerance _tolerance; 2457 2458 public: 2459 2460 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow, 2461 const Tolerance& tolerance = Tolerance()) 2462 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2463 2464 bool operator[](const typename Digraph::Arc& a) const { 2465 return _tolerance.positive((*_flow)[a]); 2466 } 2467 }; 2468 2469 } 2470 2471 /// \ingroup graph_adaptors 2472 /// 2473 /// \brief An adaptor for composing the residual graph for directed 2474 /// flow and circulation problems. 2475 /// 2476 /// An adaptor for composing the residual graph for directed flow and 2477 /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph 2478 /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$, 2479 /// be functions on the arc-set. 2480 /// 2481 /// Then Residual implements the digraph structure with 2482 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$, 2483 /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 2484 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so 2485 /// called residual graph. When we take the union 2486 /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted, 2487 /// i.e. if an arc is in both \f$ A_{forward} \f$ and 2488 /// \f$ A_{backward} \f$, then in the adaptor it appears in both 2489 /// orientation. 2490 /// 2491 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 2492 /// "Digraph concept". The type is implicitly const. 2493 /// \tparam _CapacityMap An arc map of some numeric type, it defines 2494 /// the capacities in the flow problem. The map is implicitly const. 2495 /// \tparam _FlowMap An arc map of some numeric type, it defines 2496 /// the capacities in the flow problem. 2497 /// \tparam _Tolerance Handler for inexact computation. 2498 template<typename _Digraph, 2499 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2500 typename _FlowMap = _CapacityMap, 1541 2501 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 1542 class ResForwardFilter { 2502 class Residual : 2503 public FilterArcs< 2504 Undirector<const _Digraph>, 2505 typename Undirector<const _Digraph>::template CombinedArcMap< 2506 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap, 2507 _FlowMap, _Tolerance>, 2508 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap, 2509 _FlowMap, _Tolerance> > > 2510 { 1543 2511 public: 1544 2512 … … 1548 2516 typedef _Tolerance Tolerance; 1549 2517 1550 typedef typename Digraph::Arc Key;1551 typedef bool Value;1552 1553 private:1554 1555 const CapacityMap* _capacity;1556 const FlowMap* _flow;1557 Tolerance _tolerance;1558 public:1559 1560 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,1561 const Tolerance& tolerance = Tolerance())1562 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }1563 1564 ResForwardFilter(const Tolerance& tolerance = Tolerance())1565 : _capacity(0), _flow(0), _tolerance(tolerance) { }1566 1567 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }1568 void setFlow(const FlowMap& flow) { _flow = &flow; }1569 1570 bool operator[](const typename Digraph::Arc& a) const {1571 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);1572 }1573 };1574 1575 template<typename _Digraph,1576 typename _CapacityMap = typename _Digraph::template ArcMap<int>,1577 typename _FlowMap = _CapacityMap,1578 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >1579 class ResBackwardFilter {1580 public:1581 1582 typedef _Digraph Digraph;1583 typedef _CapacityMap CapacityMap;1584 typedef _FlowMap FlowMap;1585 typedef _Tolerance Tolerance;1586 1587 typedef typename Digraph::Arc Key;1588 typedef bool Value;1589 1590 private:1591 1592 const CapacityMap* _capacity;1593 const FlowMap* _flow;1594 Tolerance _tolerance;1595 1596 public:1597 1598 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,1599 const Tolerance& tolerance = Tolerance())1600 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }1601 ResBackwardFilter(const Tolerance& tolerance = Tolerance())1602 : _capacity(0), _flow(0), _tolerance(tolerance) { }1603 1604 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }1605 void setFlow(const FlowMap& flow) { _flow = &flow; }1606 1607 bool operator[](const typename Digraph::Arc& a) const {1608 return _tolerance.positive((*_flow)[a]);1609 }1610 };1611 1612 1613 ///\ingroup graph_adaptors1614 ///1615 ///\brief An adaptor for composing the residual graph for directed1616 ///flow and circulation problems.1617 ///1618 ///An adaptor for composing the residual graph for directed flow and1619 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph1620 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F1621 ///\f$, be functions on the arc-set.1622 ///1623 ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands1624 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a1625 ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.1626 ///1627 ///\code1628 /// ListDigraph g;1629 ///\endcode1630 ///1631 ///Then ResDigraphAdaptor implements the digraph structure with1632 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}1633 /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and1634 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so1635 /// called residual graph. When we take the union \f$1636 /// A_{forward}\cup A_{backward} \f$, multilicities are counted,1637 /// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$1638 /// A_{backward} \f$, then in the adaptor it appears twice. The1639 /// following code shows how such an instance can be constructed.1640 ///1641 ///\code1642 /// typedef ListDigraph Digraph;1643 /// IntArcMap f(g), c(g);1644 /// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);1645 ///\endcode1646 template<typename _Digraph,1647 typename _CapacityMap = typename _Digraph::template ArcMap<int>,1648 typename _FlowMap = _CapacityMap,1649 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >1650 class ResDigraphAdaptor :1651 public ArcSubDigraphAdaptor<1652 UndirDigraphAdaptor<const _Digraph>,1653 typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<1654 ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,1655 ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {1656 public:1657 1658 typedef _Digraph Digraph;1659 typedef _CapacityMap CapacityMap;1660 typedef _FlowMap FlowMap;1661 typedef _Tolerance Tolerance;1662 1663 2518 typedef typename CapacityMap::Value Value; 1664 typedef Res DigraphAdaptorAdaptor;2519 typedef Residual Adaptor; 1665 2520 1666 2521 protected: 1667 2522 1668 typedef Undir DigraphAdaptor<const Digraph> UndirDigraph;1669 1670 typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>1671 ForwardFilter;1672 1673 typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>1674 BackwardFilter;1675 1676 typedef typename Undir Digraph::2523 typedef Undirector<const Digraph> Undirected; 2524 2525 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap, 2526 FlowMap, Tolerance> ForwardFilter; 2527 2528 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap, 2529 FlowMap, Tolerance> BackwardFilter; 2530 2531 typedef typename Undirected:: 1677 2532 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 1678 2533 1679 typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;2534 typedef FilterArcs<Undirected, ArcFilter> Parent; 1680 2535 1681 2536 const CapacityMap* _capacity; 1682 2537 FlowMap* _flow; 1683 2538 1684 Undir Digraph_graph;2539 Undirected _graph; 1685 2540 ForwardFilter _forward_filter; 1686 2541 BackwardFilter _backward_filter; 1687 2542 ArcFilter _arc_filter; 1688 2543 1689 void setCapacityMap(const CapacityMap& capacity) {1690 _capacity = &capacity;1691 _forward_filter.setCapacity(capacity);1692 _backward_filter.setCapacity(capacity);1693 }1694 1695 void setFlowMap(FlowMap& flow) {1696 _flow = &flow;1697 _forward_filter.setFlow(flow);1698 _backward_filter.setFlow(flow);1699 }1700 1701 2544 public: 1702 2545 1703 2546 /// \brief Constructor of the residual digraph. 1704 2547 /// 1705 /// Constructor of the residual graph. The parameters are the digraph type,2548 /// Constructor of the residual graph. The parameters are the digraph, 1706 2549 /// the flow map, the capacity map and a tolerance object. 1707 Res DigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,1708 FlowMap& flow, const Tolerance& tolerance = Tolerance())2550 Residual(const Digraph& digraph, const CapacityMap& capacity, 2551 FlowMap& flow, const Tolerance& tolerance = Tolerance()) 1709 2552 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), 1710 _forward_filter(capacity, flow, tolerance), 2553 _forward_filter(capacity, flow, tolerance), 1711 2554 _backward_filter(capacity, flow, tolerance), 1712 2555 _arc_filter(_forward_filter, _backward_filter) … … 1721 2564 /// 1722 2565 /// Gives back the residual capacity of the arc. 1723 Value res cap(const Arc& arc) const {1724 if (Undir Digraph::direction(arc)) {1725 return (*_capacity)[a rc] - (*_flow)[arc];2566 Value residualCapacity(const Arc& a) const { 2567 if (Undirected::direction(a)) { 2568 return (*_capacity)[a] - (*_flow)[a]; 1726 2569 } else { 1727 return (*_flow)[a rc];1728 } 1729 } 1730 1731 /// \brief Augment on the given arc in the residual digraph.1732 /// 1733 /// Augment on the given arc in the residual digraph. It increase2570 return (*_flow)[a]; 2571 } 2572 } 2573 2574 /// \brief Augment on the given arc in the residual graph. 2575 /// 2576 /// Augment on the given arc in the residual graph. It increase 1734 2577 /// or decrease the flow on the original arc depend on the direction 1735 2578 /// of the residual arc. 1736 void augment(const Arc& e, const Value& a) const {1737 if (Undir Digraph::direction(e)) {1738 _flow->set( e, (*_flow)[e] + a);1739 } else { 1740 _flow->set( e, (*_flow)[e] - a);2579 void augment(const Arc& a, const Value& v) const { 2580 if (Undirected::direction(a)) { 2581 _flow->set(a, (*_flow)[a] + v); 2582 } else { 2583 _flow->set(a, (*_flow)[a] - v); 1741 2584 } 1742 2585 } … … 1745 2588 /// 1746 2589 /// Returns true when the arc is same oriented as the original arc. 1747 static bool forward(const Arc& e) {1748 return Undir Digraph::direction(e);2590 static bool forward(const Arc& a) { 2591 return Undirected::direction(a); 1749 2592 } 1750 2593 … … 1752 2595 /// 1753 2596 /// Returns true when the arc is opposite oriented as the original arc. 1754 static bool backward(const Arc& e) {1755 return !Undir Digraph::direction(e);2597 static bool backward(const Arc& a) { 2598 return !Undirected::direction(a); 1756 2599 } 1757 2600 … … 1759 2602 /// 1760 2603 /// Gives back the forward oriented residual arc. 1761 static Arc forward(const typename Digraph::Arc& e) {1762 return Undir Digraph::direct(e, true);2604 static Arc forward(const typename Digraph::Arc& a) { 2605 return Undirected::direct(a, true); 1763 2606 } 1764 2607 … … 1766 2609 /// 1767 2610 /// Gives back the backward oriented residual arc. 1768 static Arc backward(const typename Digraph::Arc& e) {1769 return Undir Digraph::direct(e, false);2611 static Arc backward(const typename Digraph::Arc& a) { 2612 return Undirected::direct(a, false); 1770 2613 } 1771 2614 1772 2615 /// \brief Residual capacity map. 1773 2616 /// 1774 /// In generic residual digraphs the residual capacity can be obtained1775 /// as a map. 1776 class Res Cap{2617 /// In generic residual graph the residual capacity can be obtained 2618 /// as a map. 2619 class ResidualCapacity { 1777 2620 protected: 1778 2621 const Adaptor* _adaptor; 1779 2622 public: 2623 /// The Key type 1780 2624 typedef Arc Key; 2625 /// The Value type 1781 2626 typedef typename _CapacityMap::Value Value; 1782 2627 1783 ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {} 1784 1785 Value operator[](const Arc& e) const { 1786 return _adaptor->rescap(e); 1787 } 1788 2628 /// Constructor 2629 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2630 2631 /// \e 2632 Value operator[](const Arc& a) const { 2633 return _adaptor->residualCapacity(a); 2634 } 2635 1789 2636 }; 1790 2637 … … 1792 2639 1793 2640 template <typename _Digraph> 1794 class Split DigraphAdaptorBase {2641 class SplitNodesBase { 1795 2642 public: 1796 2643 1797 2644 typedef _Digraph Digraph; 1798 2645 typedef DigraphAdaptorBase<const _Digraph> Parent; 1799 typedef Split DigraphAdaptorBase Adaptor;2646 typedef SplitNodesBase Adaptor; 1800 2647 1801 2648 typedef typename Digraph::Node DigraphNode; … … 1811 2658 1812 2659 public: 1813 2660 1814 2661 class Node : public DigraphNode { 1815 friend class Split DigraphAdaptorBase;2662 friend class SplitNodesBase; 1816 2663 template <typename T> friend class NodeMapBase; 1817 2664 private: … … 1819 2666 bool _in; 1820 2667 Node(DigraphNode node, bool in) 1821 1822 2668 : DigraphNode(node), _in(in) {} 2669 1823 2670 public: 1824 2671 … … 1827 2674 1828 2675 bool operator==(const Node& node) const { 1829 1830 } 1831 2676 return DigraphNode::operator==(node) && _in == node._in; 2677 } 2678 1832 2679 bool operator!=(const Node& node) const { 1833 1834 } 1835 2680 return !(*this == node); 2681 } 2682 1836 2683 bool operator<(const Node& node) const { 1837 return DigraphNode::operator<(node) || 1838 2684 return DigraphNode::operator<(node) || 2685 (DigraphNode::operator==(node) && _in < node._in); 1839 2686 } 1840 2687 }; 1841 2688 1842 2689 class Arc { 1843 friend class Split DigraphAdaptorBase;2690 friend class SplitNodesBase; 1844 2691 template <typename T> friend class ArcMapBase; 1845 2692 private: … … 1848 2695 explicit Arc(const DigraphArc& arc) : _item(arc) {} 1849 2696 explicit Arc(const DigraphNode& node) : _item(node) {} 1850 2697 1851 2698 ArcImpl _item; 1852 2699 … … 1867 2714 return false; 1868 2715 } 1869 2716 1870 2717 bool operator!=(const Arc& arc) const { 1871 1872 } 1873 2718 return !(*this == arc); 2719 } 2720 1874 2721 bool operator<(const Arc& arc) const { 1875 2722 if (_item.firstState()) { … … 1898 2745 void next(Node& n) const { 1899 2746 if (n._in) { 1900 2747 n._in = false; 1901 2748 } else { 1902 1903 2749 n._in = true; 2750 _digraph->next(n); 1904 2751 } 1905 2752 } … … 1910 2757 if (e._item.second() == INVALID) { 1911 2758 e._item.setFirst(); 1912 2759 _digraph->first(e._item.first()); 1913 2760 } 1914 2761 } … … 1916 2763 void next(Arc& e) const { 1917 2764 if (e._item.secondState()) { 1918 2765 _digraph->next(e._item.second()); 1919 2766 if (e._item.second() == INVALID) { 1920 2767 e._item.setFirst(); … … 1922 2769 } 1923 2770 } else { 1924 1925 } 2771 _digraph->next(e._item.first()); 2772 } 1926 2773 } 1927 2774 … … 1931 2778 } else { 1932 2779 e._item.setFirst(); 1933 2780 _digraph->firstOut(e._item.first(), n); 1934 2781 } 1935 2782 } … … 1937 2784 void nextOut(Arc& e) const { 1938 2785 if (!e._item.firstState()) { 1939 2786 e._item.setFirst(INVALID); 1940 2787 } else { 1941 1942 } 2788 _digraph->nextOut(e._item.first()); 2789 } 1943 2790 } 1944 2791 1945 2792 void firstIn(Arc& e, const Node& n) const { 1946 2793 if (!n._in) { 1947 e._item.setSecond(n); 2794 e._item.setSecond(n); 1948 2795 } else { 1949 2796 e._item.setFirst(); 1950 2797 _digraph->firstIn(e._item.first(), n); 1951 2798 } 1952 2799 } … … 1954 2801 void nextIn(Arc& e) const { 1955 2802 if (!e._item.firstState()) { 1956 2803 e._item.setFirst(INVALID); 1957 2804 } else { 1958 2805 _digraph->nextIn(e._item.first()); 1959 2806 } 1960 2807 } … … 1962 2809 Node source(const Arc& e) const { 1963 2810 if (e._item.firstState()) { 1964 2811 return Node(_digraph->source(e._item.first()), false); 1965 2812 } else { 1966 2813 return Node(e._item.second(), true); 1967 2814 } 1968 2815 } … … 1970 2817 Node target(const Arc& e) const { 1971 2818 if (e._item.firstState()) { 1972 2819 return Node(_digraph->target(e._item.first()), true); 1973 2820 } else { 1974 2821 return Node(e._item.second(), false); 1975 2822 } 1976 2823 } … … 2001 2848 } 2002 2849 int maxArcId() const { 2003 return std::max(_digraph->maxNodeId() << 1, 2850 return std::max(_digraph->maxNodeId() << 1, 2004 2851 (_digraph->maxArcId() << 1) | 1); 2005 2852 } … … 2049 2896 2050 2897 typedef True FindEdgeTag; 2051 Arc findArc(const Node& u, const Node& v, 2052 2898 Arc findArc(const Node& u, const Node& v, 2899 const Arc& prev = INVALID) const { 2053 2900 if (inNode(u)) { 2054 2901 if (outNode(v)) { 2055 if (static_cast<const DigraphNode&>(u) == 2902 if (static_cast<const DigraphNode&>(u) == 2056 2903 static_cast<const DigraphNode&>(v) && prev == INVALID) { 2057 2904 return Arc(u); … … 2067 2914 2068 2915 private: 2069 2916 2070 2917 template <typename _Value> 2071 class NodeMapBase 2918 class NodeMapBase 2072 2919 : public MapTraits<typename Parent::template NodeMap<_Value> > { 2073 2920 typedef typename Parent::template NodeMap<_Value> NodeImpl; … … 2075 2922 typedef Node Key; 2076 2923 typedef _Value Value; 2077 2078 NodeMapBase(const Adaptor& adaptor) 2079 2080 NodeMapBase(const Adaptor& adaptor, const Value& value) 2081 : _in_map(*adaptor._digraph, value), 2082 2924 2925 NodeMapBase(const Adaptor& adaptor) 2926 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 2927 NodeMapBase(const Adaptor& adaptor, const Value& value) 2928 : _in_map(*adaptor._digraph, value), 2929 _out_map(*adaptor._digraph, value) {} 2083 2930 2084 2931 void set(const Node& key, const Value& val) { 2085 2086 2087 } 2088 2089 typename MapTraits<NodeImpl>::ReturnValue 2932 if (Adaptor::inNode(key)) { _in_map.set(key, val); } 2933 else {_out_map.set(key, val); } 2934 } 2935 2936 typename MapTraits<NodeImpl>::ReturnValue 2090 2937 operator[](const Node& key) { 2091 2092 2938 if (Adaptor::inNode(key)) { return _in_map[key]; } 2939 else { return _out_map[key]; } 2093 2940 } 2094 2941 2095 2942 typename MapTraits<NodeImpl>::ConstReturnValue 2096 2943 operator[](const Node& key) const { 2097 2098 2944 if (Adaptor::inNode(key)) { return _in_map[key]; } 2945 else { return _out_map[key]; } 2099 2946 } 2100 2947 … … 2104 2951 2105 2952 template <typename _Value> 2106 class ArcMapBase 2953 class ArcMapBase 2107 2954 : public MapTraits<typename Parent::template ArcMap<_Value> > { 2108 2955 typedef typename Parent::template ArcMap<_Value> ArcImpl; … … 2112 2959 typedef _Value Value; 2113 2960 2114 ArcMapBase(const Adaptor& adaptor) 2115 2116 ArcMapBase(const Adaptor& adaptor, const Value& value) 2117 : _arc_map(*adaptor._digraph, value), 2118 2961 ArcMapBase(const Adaptor& adaptor) 2962 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 2963 ArcMapBase(const Adaptor& adaptor, const Value& value) 2964 : _arc_map(*adaptor._digraph, value), 2965 _node_map(*adaptor._digraph, value) {} 2119 2966 2120 2967 void set(const Arc& key, const Value& val) { 2121 if (Adaptor::origArc(key)) { 2122 _arc_map.set(key._item.first(), val); 2968 if (Adaptor::origArc(key)) { 2969 _arc_map.set(key._item.first(), val); 2123 2970 } else { 2124 _node_map.set(key._item.second(), val); 2971 _node_map.set(key._item.second(), val); 2125 2972 } 2126 2973 } 2127 2974 2128 2975 typename MapTraits<ArcImpl>::ReturnValue 2129 2976 operator[](const Arc& key) { 2130 if (Adaptor::origArc(key)) { 2977 if (Adaptor::origArc(key)) { 2131 2978 return _arc_map[key._item.first()]; 2132 2979 } else { … … 2137 2984 typename MapTraits<ArcImpl>::ConstReturnValue 2138 2985 operator[](const Arc& key) const { 2139 if (Adaptor::origArc(key)) { 2986 if (Adaptor::origArc(key)) { 2140 2987 return _arc_map[key._item.first()]; 2141 2988 } else { … … 2152 2999 2153 3000 template <typename _Value> 2154 class NodeMap 2155 : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 3001 class NodeMap 3002 : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 2156 3003 { 2157 3004 public: 2158 3005 typedef _Value Value; 2159 3006 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent; 2160 2161 NodeMap(const Adaptor& adaptor) 2162 2163 2164 NodeMap(const Adaptor& adaptor, const Value& value) 2165 2166 3007 3008 NodeMap(const Adaptor& adaptor) 3009 : Parent(adaptor) {} 3010 3011 NodeMap(const Adaptor& adaptor, const Value& value) 3012 : Parent(adaptor, value) {} 3013 2167 3014 private: 2168 3015 NodeMap& operator=(const NodeMap& cmap) { 2169 2170 } 2171 3016 return operator=<NodeMap>(cmap); 3017 } 3018 2172 3019 template <typename CMap> 2173 3020 NodeMap& operator=(const CMap& cmap) { 2174 3021 Parent::operator=(cmap); 2175 3022 return *this; 2176 3023 } 2177 3024 }; 2178 3025 2179 3026 template <typename _Value> 2180 class ArcMap 2181 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 3027 class ArcMap 3028 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 2182 3029 { 2183 3030 public: 2184 3031 typedef _Value Value; 2185 3032 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 2186 2187 ArcMap(const Adaptor& adaptor) 2188 2189 2190 ArcMap(const Adaptor& adaptor, const Value& value) 2191 2192 3033 3034 ArcMap(const Adaptor& adaptor) 3035 : Parent(adaptor) {} 3036 3037 ArcMap(const Adaptor& adaptor, const Value& value) 3038 : Parent(adaptor, value) {} 3039 2193 3040 private: 2194 3041 ArcMap& operator=(const ArcMap& cmap) { 2195 2196 } 2197 3042 return operator=<ArcMap>(cmap); 3043 } 3044 2198 3045 template <typename CMap> 2199 3046 ArcMap& operator=(const CMap& cmap) { 2200 3047 Parent::operator=(cmap); 2201 3048 return *this; 2202 3049 } 2203 3050 }; … … 2205 3052 protected: 2206 3053 2207 Split DigraphAdaptorBase() : _digraph(0) {}3054 SplitNodesBase() : _digraph(0) {} 2208 3055 2209 3056 Digraph* _digraph; … … 2212 3059 _digraph = &digraph; 2213 3060 } 2214 3061 2215 3062 }; 2216 3063 2217 3064 /// \ingroup graph_adaptors 2218 3065 /// 2219 /// \brief Split digraph adaptor class2220 /// 2221 /// Th is is an digraph adaptor which splits all node into an in-node2222 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$2223 /// node in the digraph with two node, \f$ u_{in} \f$ node and2224 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the2225 /// original digraph the new target of the arc will be \f$ u_{in} \f$ and2226 /// similarly the source of the original \f$ (u, v) \f$ arc will be2227 /// \f$ u_{out} \f$. The adaptor will add for each node in the2228 /// original digraph an additional arc which will connect3066 /// \brief Split the nodes of a directed graph 3067 /// 3068 /// The SplitNodes adaptor splits each node into an in-node and an 3069 /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in 3070 /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node 3071 /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the 3072 /// original digraph the new target of the arc will be \f$ u_{in} \f$ 3073 /// and similarly the source of the original \f$ (u, v) \f$ arc 3074 /// will be \f$ u_{out} \f$. The adaptor will add for each node in 3075 /// the original digraph an additional arc which connects 2229 3076 /// \f$ (u_{in}, u_{out}) \f$. 2230 3077 /// 2231 /// The aim of this class is to run algorithm with node costs if the 3078 /// The aim of this class is to run algorithm with node costs if the 2232 3079 /// algorithm can use directly just arc costs. In this case we should use 2233 /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the 2234 /// bind arc in the adapted digraph. 2235 /// 2236 /// For example a maximum flow algorithm can compute how many arc 2237 /// disjoint paths are in the digraph. But we would like to know how 2238 /// many node disjoint paths are in the digraph. First we have to 2239 /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow 2240 /// algorithm on the adapted digraph. The bottleneck of the flow will 2241 /// be the bind arcs which bounds the flow with the count of the 2242 /// node disjoint paths. 2243 /// 2244 ///\code 2245 /// 2246 /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph; 2247 /// 2248 /// SDigraph sdigraph(digraph); 2249 /// 2250 /// typedef ConstMap<SDigraph::Arc, int> SCapacity; 2251 /// SCapacity scapacity(1); 2252 /// 2253 /// SDigraph::ArcMap<int> sflow(sdigraph); 2254 /// 2255 /// Preflow<SDigraph, SCapacity> 2256 /// spreflow(sdigraph, scapacity, 2257 /// SDigraph::outNode(source), SDigraph::inNode(target)); 2258 /// 2259 /// spreflow.run(); 2260 /// 2261 ///\endcode 2262 /// 2263 /// The result of the mamixum flow on the original digraph 2264 /// shows the next figure: 2265 /// 2266 /// \image html arc_disjoint.png 2267 /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth 2268 /// 2269 /// And the maximum flow on the adapted digraph: 2270 /// 2271 /// \image html node_disjoint.png 2272 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth 2273 /// 2274 /// The second solution contains just 3 disjoint paths while the first 4. 2275 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file. 2276 /// 2277 /// This digraph adaptor is fully conform to the 2278 /// \ref concepts::Digraph "Digraph" concept and 2279 /// contains some additional member functions and types. The 2280 /// documentation of some member functions may be found just in the 2281 /// SplitDigraphAdaptorBase class. 2282 /// 2283 /// \sa SplitDigraphAdaptorBase 3080 /// a \c SplitNodes and set the node cost of the graph to the 3081 /// bind arc in the adapted graph. 3082 /// 3083 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3084 /// "Digraph concept". The type can be specified to be const. 2284 3085 template <typename _Digraph> 2285 class Split DigraphAdaptor2286 : public DigraphAdaptorExtender<Split DigraphAdaptorBase<_Digraph> > {3086 class SplitNodes 3087 : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > { 2287 3088 public: 2288 3089 typedef _Digraph Digraph; 2289 typedef DigraphAdaptorExtender<Split DigraphAdaptorBase<Digraph> > Parent;3090 typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent; 2290 3091 2291 3092 typedef typename Digraph::Node DigraphNode; … … 2298 3099 /// 2299 3100 /// Constructor of the adaptor. 2300 Split DigraphAdaptor(Digraph& g) {3101 SplitNodes(Digraph& g) { 2301 3102 Parent::setDigraph(g); 2302 3103 } … … 2345 3146 2346 3147 /// \brief Gives back the arc binds the two part of the node. 2347 /// 3148 /// 2348 3149 /// Gives back the arc binds the two part of the node. 2349 3150 static Arc arc(const DigraphNode& n) { … … 2352 3153 2353 3154 /// \brief Gives back the arc of the original arc. 2354 /// 3155 /// 2355 3156 /// Gives back the arc of the original arc. 2356 3157 static Arc arc(const DigraphArc& a) { … … 2372 3173 /// 2373 3174 /// Constructor. 2374 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 2375 3175 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 3176 : _in_map(in_map), _out_map(out_map) {} 2376 3177 2377 3178 /// \brief The subscript operator. … … 2379 3180 /// The subscript operator. 2380 3181 Value& operator[](const Key& key) { 2381 2382 2383 2384 2385 3182 if (Parent::inNode(key)) { 3183 return _in_map[key]; 3184 } else { 3185 return _out_map[key]; 3186 } 2386 3187 } 2387 3188 … … 2390 3191 /// The const subscript operator. 2391 3192 Value operator[](const Key& key) const { 2392 2393 2394 2395 2396 3193 if (Parent::inNode(key)) { 3194 return _in_map[key]; 3195 } else { 3196 return _out_map[key]; 3197 } 2397 3198 } 2398 3199 2399 3200 /// \brief The setter function of the map. 2400 /// 3201 /// 2401 3202 /// The setter function of the map. 2402 3203 void set(const Key& key, const Value& value) { 2403 2404 2405 2406 2407 2408 } 2409 3204 if (Parent::inNode(key)) { 3205 _in_map.set(key, value); 3206 } else { 3207 _out_map.set(key, value); 3208 } 3209 } 3210 2410 3211 private: 2411 3212 2412 3213 InNodeMap& _in_map; 2413 3214 OutNodeMap& _out_map; 2414 3215 2415 3216 }; 2416 3217 2417 3218 2418 /// \brief Just gives back a combined node map .2419 /// 2420 /// Just gives back a combined node map .3219 /// \brief Just gives back a combined node map 3220 /// 3221 /// Just gives back a combined node map 2421 3222 template <typename InNodeMap, typename OutNodeMap> 2422 static CombinedNodeMap<InNodeMap, OutNodeMap> 3223 static CombinedNodeMap<InNodeMap, OutNodeMap> 2423 3224 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { 2424 3225 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map); … … 2426 3227 2427 3228 template <typename InNodeMap, typename OutNodeMap> 2428 static CombinedNodeMap<const InNodeMap, OutNodeMap> 3229 static CombinedNodeMap<const InNodeMap, OutNodeMap> 2429 3230 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { 2430 3231 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map); … … 2432 3233 2433 3234 template <typename InNodeMap, typename OutNodeMap> 2434 static CombinedNodeMap<InNodeMap, const OutNodeMap> 3235 static CombinedNodeMap<InNodeMap, const OutNodeMap> 2435 3236 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { 2436 3237 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map); … … 2438 3239 2439 3240 template <typename InNodeMap, typename OutNodeMap> 2440 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 3241 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 2441 3242 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { 2442 return CombinedNodeMap<const InNodeMap, 3243 return CombinedNodeMap<const InNodeMap, 2443 3244 const OutNodeMap>(in_map, out_map); 2444 3245 } 2445 3246 2446 /// \brief ArcMap combined from an original ArcMap and NodeMap2447 /// 2448 /// This class adapt an original digraph ArcMap and NodeMap to2449 /// get an arc map on the adapted digraph.3247 /// \brief ArcMap combined from an original ArcMap and a NodeMap 3248 /// 3249 /// This class adapt an original ArcMap and a NodeMap to get an 3250 /// arc map on the adapted digraph 2450 3251 template <typename DigraphArcMap, typename DigraphNodeMap> 2451 3252 class CombinedArcMap { 2452 3253 public: 2453 3254 2454 3255 typedef Arc Key; 2455 3256 typedef typename DigraphArcMap::Value Value; 2456 3257 2457 3258 /// \brief Constructor 2458 3259 /// 2459 3260 /// Constructor. 2460 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 2461 3261 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 3262 : _arc_map(arc_map), _node_map(node_map) {} 2462 3263 2463 3264 /// \brief The subscript operator. … … 2465 3266 /// The subscript operator. 2466 3267 void set(const Arc& arc, const Value& val) { 2467 2468 2469 2470 2471 3268 if (Parent::origArc(arc)) { 3269 _arc_map.set(arc, val); 3270 } else { 3271 _node_map.set(arc, val); 3272 } 2472 3273 } 2473 3274 … … 2476 3277 /// The const subscript operator. 2477 3278 Value operator[](const Key& arc) const { 2478 2479 2480 2481 2482 2483 } 3279 if (Parent::origArc(arc)) { 3280 return _arc_map[arc]; 3281 } else { 3282 return _node_map[arc]; 3283 } 3284 } 2484 3285 2485 3286 /// \brief The const subscript operator. … … 2487 3288 /// The const subscript operator. 2488 3289 Value& operator[](const Key& arc) { 2489 2490 2491 2492 2493 2494 } 2495 3290 if (Parent::origArc(arc)) { 3291 return _arc_map[arc]; 3292 } else { 3293 return _node_map[arc]; 3294 } 3295 } 3296 2496 3297 private: 2497 3298 DigraphArcMap& _arc_map; 2498 3299 DigraphNodeMap& _node_map; 2499 3300 }; 2500 2501 /// \brief Just gives back a combined arc map .2502 /// 2503 /// Just gives back a combined arc map .3301 3302 /// \brief Just gives back a combined arc map 3303 /// 3304 /// Just gives back a combined arc map 2504 3305 template <typename DigraphArcMap, typename DigraphNodeMap> 2505 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 3306 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 2506 3307 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 2507 3308 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map); … … 2509 3310 2510 3311 template <typename DigraphArcMap, typename DigraphNodeMap> 2511 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 3312 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 2512 3313 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 2513 return CombinedArcMap<const DigraphArcMap, 3314 return CombinedArcMap<const DigraphArcMap, 2514 3315 DigraphNodeMap>(arc_map, node_map); 2515 3316 } 2516 3317 2517 3318 template <typename DigraphArcMap, typename DigraphNodeMap> 2518 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 3319 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 2519 3320 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) { 2520 return CombinedArcMap<DigraphArcMap, 3321 return CombinedArcMap<DigraphArcMap, 2521 3322 const DigraphNodeMap>(arc_map, node_map); 2522 3323 } 2523 3324 2524 3325 template <typename DigraphArcMap, typename DigraphNodeMap> 2525 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 2526 combinedArcMap(const DigraphArcMap& arc_map, 2527 2528 return CombinedArcMap<const DigraphArcMap, 3326 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 3327 combinedArcMap(const DigraphArcMap& arc_map, 3328 const DigraphNodeMap& node_map) { 3329 return CombinedArcMap<const DigraphArcMap, 2529 3330 const DigraphNodeMap>(arc_map, node_map); 2530 3331 } … … 2532 3333 }; 2533 3334 2534 /// \brief Just gives back a split digraph adaptor2535 /// 2536 /// Just gives back a split digraph adaptor3335 /// \brief Just gives back a node splitter 3336 /// 3337 /// Just gives back a node splitter 2537 3338 template<typename Digraph> 2538 Split DigraphAdaptor<Digraph>2539 split DigraphAdaptor(const Digraph& digraph) {2540 return Split DigraphAdaptor<Digraph>(digraph);3339 SplitNodes<Digraph> 3340 splitNodes(const Digraph& digraph) { 3341 return SplitNodes<Digraph>(digraph); 2541 3342 } 2542 3343 … … 2544 3345 } //namespace lemon 2545 3346 2546 #endif //LEMON_DIGRAPH_ADAPTOR_H 2547 3347 #endif //LEMON_ADAPTORS_H -
lemon/bits/graph_adaptor_extender.h
r414 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 25 25 #include <lemon/bits/default_map.h> 26 26 27 28 ///\ingroup digraphbits29 ///\file30 ///\brief Extenders for the digraph adaptor types31 27 namespace lemon { 32 28 33 /// \ingroup digraphbits34 ///35 /// \brief Extender for the DigraphAdaptors36 29 template <typename _Digraph> 37 30 class DigraphAdaptorExtender : public _Digraph { … … 65 58 Node oppositeNode(const Node &n, const Arc &e) const { 66 59 if (n == Parent::source(e)) 67 60 return Parent::target(e); 68 61 else if(n==Parent::target(e)) 69 62 return Parent::source(e); 70 63 else 71 72 } 73 74 class NodeIt : public Node { 64 return INVALID; 65 } 66 67 class NodeIt : public Node { 75 68 const Adaptor* _adaptor; 76 69 public: … … 81 74 82 75 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 83 84 } 85 86 NodeIt(const Adaptor& adaptor, const Node& node) 87 88 89 NodeIt& operator++() { 90 91 return *this; 92 } 93 94 }; 95 96 97 class ArcIt : public Arc { 76 _adaptor->first(static_cast<Node&>(*this)); 77 } 78 79 NodeIt(const Adaptor& adaptor, const Node& node) 80 : Node(node), _adaptor(&adaptor) {} 81 82 NodeIt& operator++() { 83 _adaptor->next(*this); 84 return *this; 85 } 86 87 }; 88 89 90 class ArcIt : public Arc { 98 91 const Adaptor* _adaptor; 99 92 public: … … 104 97 105 98 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 106 107 } 108 109 ArcIt(const Adaptor& adaptor, const Arc& e) : 110 111 112 ArcIt& operator++() { 113 114 return *this; 115 } 116 117 }; 118 119 120 class OutArcIt : public Arc { 99 _adaptor->first(static_cast<Arc&>(*this)); 100 } 101 102 ArcIt(const Adaptor& adaptor, const Arc& e) : 103 Arc(e), _adaptor(&adaptor) { } 104 105 ArcIt& operator++() { 106 _adaptor->next(*this); 107 return *this; 108 } 109 110 }; 111 112 113 class OutArcIt : public Arc { 121 114 const Adaptor* _adaptor; 122 115 public: … … 126 119 OutArcIt(Invalid i) : Arc(i) { } 127 120 128 OutArcIt(const Adaptor& adaptor, const Node& node) 129 130 131 } 132 133 OutArcIt(const Adaptor& adaptor, const Arc& arc) 134 135 136 OutArcIt& operator++() { 137 138 return *this; 139 } 140 141 }; 142 143 144 class InArcIt : public Arc { 121 OutArcIt(const Adaptor& adaptor, const Node& node) 122 : _adaptor(&adaptor) { 123 _adaptor->firstOut(*this, node); 124 } 125 126 OutArcIt(const Adaptor& adaptor, const Arc& arc) 127 : Arc(arc), _adaptor(&adaptor) {} 128 129 OutArcIt& operator++() { 130 _adaptor->nextOut(*this); 131 return *this; 132 } 133 134 }; 135 136 137 class InArcIt : public Arc { 145 138 const Adaptor* _adaptor; 146 139 public: … … 150 143 InArcIt(Invalid i) : Arc(i) { } 151 144 152 InArcIt(const Adaptor& adaptor, const Node& node) 153 : _adaptor(&adaptor) { 154 _adaptor->firstIn(*this, node); 155 } 156 157 InArcIt(const Adaptor& adaptor, const Arc& arc) : 158 Arc(arc), _adaptor(&adaptor) {} 159 160 InArcIt& operator++() { 161 _adaptor->nextIn(*this); 162 return *this; 163 } 164 165 }; 166 167 /// \brief Base node of the iterator 168 /// 169 /// Returns the base node (ie. the source in this case) of the iterator 145 InArcIt(const Adaptor& adaptor, const Node& node) 146 : _adaptor(&adaptor) { 147 _adaptor->firstIn(*this, node); 148 } 149 150 InArcIt(const Adaptor& adaptor, const Arc& arc) : 151 Arc(arc), _adaptor(&adaptor) {} 152 153 InArcIt& operator++() { 154 _adaptor->nextIn(*this); 155 return *this; 156 } 157 158 }; 159 170 160 Node baseNode(const OutArcIt &e) const { 171 161 return Parent::source(e); 172 162 } 173 /// \brief Running node of the iterator174 ///175 /// Returns the running node (ie. the target in this case) of the176 /// iterator177 163 Node runningNode(const OutArcIt &e) const { 178 164 return Parent::target(e); 179 165 } 180 166 181 /// \brief Base node of the iterator182 ///183 /// Returns the base node (ie. the target in this case) of the iterator184 167 Node baseNode(const InArcIt &e) const { 185 168 return Parent::target(e); 186 169 } 187 /// \brief Running node of the iterator188 ///189 /// Returns the running node (ie. the source in this case) of the190 /// iterator191 170 Node runningNode(const InArcIt &e) const { 192 171 return Parent::source(e); … … 199 178 /// 200 179 /// \brief Extender for the GraphAdaptors 201 template <typename _Graph> 180 template <typename _Graph> 202 181 class GraphAdaptorExtender : public _Graph { 203 182 public: 204 183 205 184 typedef _Graph Parent; 206 185 typedef _Graph Graph; … … 211 190 typedef typename Parent::Edge Edge; 212 191 213 // Graph extension 192 // Graph extension 214 193 215 194 int maxId(Node) const { … … 239 218 Node oppositeNode(const Node &n, const Edge &e) const { 240 219 if( n == Parent::u(e)) 241 220 return Parent::v(e); 242 221 else if( n == Parent::v(e)) 243 222 return Parent::u(e); 244 223 else 245 224 return INVALID; 246 225 } 247 226 … … 256 235 257 236 258 class NodeIt : public Node { 237 class NodeIt : public Node { 259 238 const Adaptor* _adaptor; 260 239 public: … … 265 244 266 245 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 267 268 } 269 270 NodeIt(const Adaptor& adaptor, const Node& node) 271 272 273 NodeIt& operator++() { 274 275 return *this; 276 } 277 278 }; 279 280 281 class ArcIt : public Arc { 246 _adaptor->first(static_cast<Node&>(*this)); 247 } 248 249 NodeIt(const Adaptor& adaptor, const Node& node) 250 : Node(node), _adaptor(&adaptor) {} 251 252 NodeIt& operator++() { 253 _adaptor->next(*this); 254 return *this; 255 } 256 257 }; 258 259 260 class ArcIt : public Arc { 282 261 const Adaptor* _adaptor; 283 262 public: … … 288 267 289 268 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 290 291 } 292 293 ArcIt(const Adaptor& adaptor, const Arc& e) : 294 295 296 ArcIt& operator++() { 297 298 return *this; 299 } 300 301 }; 302 303 304 class OutArcIt : public Arc { 269 _adaptor->first(static_cast<Arc&>(*this)); 270 } 271 272 ArcIt(const Adaptor& adaptor, const Arc& e) : 273 Arc(e), _adaptor(&adaptor) { } 274 275 ArcIt& operator++() { 276 _adaptor->next(*this); 277 return *this; 278 } 279 280 }; 281 282 283 class OutArcIt : public Arc { 305 284 const Adaptor* _adaptor; 306 285 public: … … 310 289 OutArcIt(Invalid i) : Arc(i) { } 311 290 312 OutArcIt(const Adaptor& adaptor, const Node& node) 313 314 315 } 316 317 OutArcIt(const Adaptor& adaptor, const Arc& arc) 318 319 320 OutArcIt& operator++() { 321 322 return *this; 323 } 324 325 }; 326 327 328 class InArcIt : public Arc { 291 OutArcIt(const Adaptor& adaptor, const Node& node) 292 : _adaptor(&adaptor) { 293 _adaptor->firstOut(*this, node); 294 } 295 296 OutArcIt(const Adaptor& adaptor, const Arc& arc) 297 : Arc(arc), _adaptor(&adaptor) {} 298 299 OutArcIt& operator++() { 300 _adaptor->nextOut(*this); 301 return *this; 302 } 303 304 }; 305 306 307 class InArcIt : public Arc { 329 308 const Adaptor* _adaptor; 330 309 public: … … 334 313 InArcIt(Invalid i) : Arc(i) { } 335 314 336 InArcIt(const Adaptor& adaptor, const Node& node) 337 338 339 } 340 341 InArcIt(const Adaptor& adaptor, const Arc& arc) : 342 343 344 InArcIt& operator++() { 345 346 return *this; 347 } 348 349 }; 350 351 class EdgeIt : public Parent::Edge { 315 InArcIt(const Adaptor& adaptor, const Node& node) 316 : _adaptor(&adaptor) { 317 _adaptor->firstIn(*this, node); 318 } 319 320 InArcIt(const Adaptor& adaptor, const Arc& arc) : 321 Arc(arc), _adaptor(&adaptor) {} 322 323 InArcIt& operator++() { 324 _adaptor->nextIn(*this); 325 return *this; 326 } 327 328 }; 329 330 class EdgeIt : public Parent::Edge { 352 331 const Adaptor* _adaptor; 353 332 public: … … 358 337 359 338 explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 360 361 } 362 363 EdgeIt(const Adaptor& adaptor, const Edge& e) : 364 365 366 EdgeIt& operator++() { 367 368 return *this; 369 } 370 371 }; 372 373 class IncEdgeIt : public Edge { 339 _adaptor->first(static_cast<Edge&>(*this)); 340 } 341 342 EdgeIt(const Adaptor& adaptor, const Edge& e) : 343 Edge(e), _adaptor(&adaptor) { } 344 345 EdgeIt& operator++() { 346 _adaptor->next(*this); 347 return *this; 348 } 349 350 }; 351 352 class IncEdgeIt : public Edge { 374 353 friend class GraphAdaptorExtender; 375 354 const Adaptor* _adaptor; … … 382 361 383 362 IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) { 384 363 _adaptor->firstInc(static_cast<Edge&>(*this), direction, n); 385 364 } 386 365 387 366 IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n) 388 389 367 : _adaptor(&adaptor), Edge(e) { 368 direction = (_adaptor->u(e) == n); 390 369 } 391 370 392 371 IncEdgeIt& operator++() { 393 _adaptor->nextInc(*this, direction); 394 return *this; 395 } 396 }; 397 398 /// \brief Base node of the iterator 399 /// 400 /// Returns the base node (ie. the source in this case) of the iterator 372 _adaptor->nextInc(*this, direction); 373 return *this; 374 } 375 }; 376 401 377 Node baseNode(const OutArcIt &a) const { 402 378 return Parent::source(a); 403 379 } 404 /// \brief Running node of the iterator405 ///406 /// Returns the running node (ie. the target in this case) of the407 /// iterator408 380 Node runningNode(const OutArcIt &a) const { 409 381 return Parent::target(a); 410 382 } 411 383 412 /// \brief Base node of the iterator413 ///414 /// Returns the base node (ie. the target in this case) of the iterator415 384 Node baseNode(const InArcIt &a) const { 416 385 return Parent::target(a); 417 386 } 418 /// \brief Running node of the iterator419 ///420 /// Returns the running node (ie. the source in this case) of the421 /// iterator422 387 Node runningNode(const InArcIt &a) const { 423 388 return Parent::source(a); 424 389 } 425 390 426 /// Base node of the iterator427 ///428 /// Returns the base node of the iterator429 391 Node baseNode(const IncEdgeIt &e) const { 430 392 return e.direction ? Parent::u(e) : Parent::v(e); 431 393 } 432 /// Running node of the iterator433 ///434 /// Returns the running node of the iterator435 394 Node runningNode(const IncEdgeIt &e) const { 436 395 return e.direction ? Parent::v(e) : Parent::u(e); -
lemon/bits/variant.h
r414 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 28 28 29 29 namespace _variant_bits { 30 30 31 31 template <int left, int right> 32 32 struct CTMax { … … 87 87 flag = bivariant.flag; 88 88 if (flag) { 89 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 89 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 90 90 } else { 91 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 91 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 92 92 } 93 93 } … … 107 107 destroy(); 108 108 flag = true; 109 new(reinterpret_cast<First*>(data)) First(); 109 new(reinterpret_cast<First*>(data)) First(); 110 110 return *this; 111 111 } … … 118 118 destroy(); 119 119 flag = true; 120 new(reinterpret_cast<First*>(data)) First(f); 120 new(reinterpret_cast<First*>(data)) First(f); 121 121 return *this; 122 122 } … … 129 129 destroy(); 130 130 flag = false; 131 new(reinterpret_cast<Second*>(data)) Second(); 131 new(reinterpret_cast<Second*>(data)) Second(); 132 132 return *this; 133 133 } … … 140 140 destroy(); 141 141 flag = false; 142 new(reinterpret_cast<Second*>(data)) Second(s); 142 new(reinterpret_cast<Second*>(data)) Second(s); 143 143 return *this; 144 144 } … … 160 160 flag = bivariant.flag; 161 161 if (flag) { 162 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 162 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 163 163 } else { 164 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 164 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 165 165 } 166 166 return *this; … … 232 232 } 233 233 } 234 234 235 235 char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value]; 236 236 bool flag; … … 238 238 239 239 namespace _variant_bits { 240 240 241 241 template <int _idx, typename _TypeMap> 242 242 struct Memory { … … 277 277 template <int _idx, typename _TypeMap> 278 278 struct Size { 279 static const int value = 280 CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type), 279 static const int value = 280 CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type), 281 281 Size<_idx - 1, _TypeMap>::value>::value; 282 282 }; … … 284 284 template <typename _TypeMap> 285 285 struct Size<0, _TypeMap> { 286 static const int value = 286 static const int value = 287 287 sizeof(typename _TypeMap::template Map<0>::Type); 288 288 }; … … 302 302 /// variant type. 303 303 /// \param _TypeMap This class describes the types of the Variant. The 304 /// _TypeMap::Map<index>::Type should be a valid type for each index 304 /// _TypeMap::Map<index>::Type should be a valid type for each index 305 305 /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper 306 306 /// class to define such type mappings up to 10 types. … … 338 338 Variant() { 339 339 flag = 0; 340 new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data)) 340 new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data)) 341 341 typename TypeMap::template Map<0>::Type(); 342 342 } … … 379 379 _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); 380 380 flag = _idx; 381 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 381 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 382 382 typename TypeMap::template Map<_idx>::Type(); 383 383 return *this; … … 392 392 _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); 393 393 flag = _idx; 394 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 394 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 395 395 typename TypeMap::template Map<_idx>::Type(init); 396 396 return *this; … … 404 404 LEMON_DEBUG(_idx == flag, "Variant wrong index"); 405 405 return *reinterpret_cast<const typename TypeMap:: 406 template Map<_idx>::Type*>(data); 406 template Map<_idx>::Type*>(data); 407 407 } 408 408 … … 414 414 LEMON_DEBUG(_idx == flag, "Variant wrong index"); 415 415 return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*> 416 (data); 416 (data); 417 417 } 418 418 … … 425 425 426 426 private: 427 427 428 428 char data[_variant_bits::Size<num - 1, TypeMap>::value]; 429 429 int flag; … … 443 443 444 444 struct List {}; 445 445 446 446 template <typename _Type, typename _List> 447 447 struct Insert { … … 450 450 }; 451 451 452 template <int _idx, typename _T0, typename _T1, typename _T2, 452 template <int _idx, typename _T0, typename _T1, typename _T2, 453 453 typename _T3, typename _T5, typename _T4, typename _T6, 454 454 typename _T7, typename _T8, typename _T9> … … 467 467 typedef typename Get<_idx, L0>::Type Type; 468 468 }; 469 469 470 470 } 471 471 … … 476 476 /// \see Variant 477 477 template < 478 typename _T0, 478 typename _T0, 479 479 typename _T1 = void, typename _T2 = void, typename _T3 = void, 480 480 typename _T5 = void, typename _T4 = void, typename _T6 = void, … … 488 488 }; 489 489 }; 490 490 491 491 } 492 492 -
test/graph_adaptor_test.cc
r415 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 26 26 #include<lemon/concepts/graph.h> 27 27 28 #include<lemon/digraph_adaptor.h> 29 #include<lemon/graph_adaptor.h> 28 #include<lemon/adaptors.h> 30 29 31 30 #include <limits> … … 38 37 using namespace lemon; 39 38 40 void checkRev DigraphAdaptor() {41 checkConcept<concepts::Digraph, Rev DigraphAdaptor<concepts::Digraph> >();39 void checkReverseDigraph() { 40 checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >(); 42 41 43 42 typedef ListDigraph Digraph; 44 typedef Rev DigraphAdaptor<Digraph> Adaptor;43 typedef ReverseDigraph<Digraph> Adaptor; 45 44 46 45 Digraph digraph; … … 54 53 Digraph::Arc a2 = digraph.addArc(n1, n3); 55 54 Digraph::Arc a3 = digraph.addArc(n2, n3); 56 55 57 56 checkGraphNodeList(adaptor, 3); 58 57 checkGraphArcList(adaptor, 3); … … 79 78 } 80 79 81 void checkSubDigraph Adaptor() {82 checkConcept<concepts::Digraph, 83 SubDigraph Adaptor<concepts::Digraph,80 void checkSubDigraph() { 81 checkConcept<concepts::Digraph, 82 SubDigraph<concepts::Digraph, 84 83 concepts::Digraph::NodeMap<bool>, 85 84 concepts::Digraph::ArcMap<bool> > >(); … … 88 87 typedef Digraph::NodeMap<bool> NodeFilter; 89 88 typedef Digraph::ArcMap<bool> ArcFilter; 90 typedef SubDigraph Adaptor<Digraph, NodeFilter, ArcFilter> Adaptor;89 typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor; 91 90 92 91 Digraph digraph; … … 124 123 checkGraphArcMap(adaptor); 125 124 126 arc_filter[a2] = false; 125 arc_filter[a2] = false; 127 126 128 127 checkGraphNodeList(adaptor, 3); … … 144 143 checkGraphArcMap(adaptor); 145 144 146 node_filter[n1] = false; 145 node_filter[n1] = false; 147 146 148 147 checkGraphNodeList(adaptor, 2); … … 176 175 } 177 176 178 void check NodeSubDigraphAdaptor() {179 checkConcept<concepts::Digraph, 180 NodeSubDigraphAdaptor<concepts::Digraph,177 void checkFilterNodes1() { 178 checkConcept<concepts::Digraph, 179 FilterNodes<concepts::Digraph, 181 180 concepts::Digraph::NodeMap<bool> > >(); 182 181 183 182 typedef ListDigraph Digraph; 184 183 typedef Digraph::NodeMap<bool> NodeFilter; 185 typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;184 typedef FilterNodes<Digraph, NodeFilter> Adaptor; 186 185 187 186 Digraph digraph; … … 217 216 checkGraphArcMap(adaptor); 218 217 219 node_filter[n1] = false; 218 node_filter[n1] = false; 220 219 221 220 checkGraphNodeList(adaptor, 2); … … 248 247 } 249 248 250 void check ArcSubDigraphAdaptor() {251 checkConcept<concepts::Digraph, 252 ArcSubDigraphAdaptor<concepts::Digraph,249 void checkFilterArcs() { 250 checkConcept<concepts::Digraph, 251 FilterArcs<concepts::Digraph, 253 252 concepts::Digraph::ArcMap<bool> > >(); 254 253 255 254 typedef ListDigraph Digraph; 256 255 typedef Digraph::ArcMap<bool> ArcFilter; 257 typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;256 typedef FilterArcs<Digraph, ArcFilter> Adaptor; 258 257 259 258 Digraph digraph; … … 289 288 checkGraphArcMap(adaptor); 290 289 291 arc_filter[a2] = false; 290 arc_filter[a2] = false; 292 291 293 292 checkGraphNodeList(adaptor, 3); … … 322 321 } 323 322 324 void checkUndir DigraphAdaptor() {325 checkConcept<concepts::Graph, Undir DigraphAdaptor<concepts::Digraph> >();323 void checkUndirector() { 324 checkConcept<concepts::Graph, Undirector<concepts::Digraph> >(); 326 325 327 326 typedef ListDigraph Digraph; 328 typedef Undir DigraphAdaptor<Digraph> Adaptor;327 typedef Undirector<Digraph> Adaptor; 329 328 330 329 Digraph digraph; … … 338 337 Digraph::Arc a2 = digraph.addArc(n1, n3); 339 338 Digraph::Arc a3 = digraph.addArc(n2, n3); 340 339 341 340 checkGraphNodeList(adaptor, 3); 342 341 checkGraphArcList(adaptor, 6); … … 372 371 } 373 372 374 void checkRes DigraphAdaptor() {375 checkConcept<concepts::Digraph, 376 Res DigraphAdaptor<concepts::Digraph,377 concepts::Digraph::ArcMap<int>, 373 void checkResidual() { 374 checkConcept<concepts::Digraph, 375 Residual<concepts::Digraph, 376 concepts::Digraph::ArcMap<int>, 378 377 concepts::Digraph::ArcMap<int> > >(); 379 378 380 379 typedef ListDigraph Digraph; 381 380 typedef Digraph::ArcMap<int> IntArcMap; 382 typedef Res DigraphAdaptor<Digraph, IntArcMap> Adaptor;381 typedef Residual<Digraph, IntArcMap> Adaptor; 383 382 384 383 Digraph digraph; … … 408 407 flow[a] = 0; 409 408 } 410 409 411 410 checkGraphNodeList(adaptor, 4); 412 411 checkGraphArcList(adaptor, 6); … … 426 425 flow[a] = capacity[a] / 2; 427 426 } 428 427 429 428 checkGraphNodeList(adaptor, 4); 430 429 checkGraphArcList(adaptor, 12); … … 450 449 flow[a] = capacity[a]; 451 450 } 452 451 453 452 checkGraphNodeList(adaptor, 4); 454 453 checkGraphArcList(adaptor, 6); … … 471 470 int flow_value = 0; 472 471 while (true) { 473 472 474 473 Bfs<Adaptor> bfs(adaptor); 475 474 bfs.run(n1, n4); 476 475 477 476 if (!bfs.reached(n4)) break; 478 477 479 478 Path<Adaptor> p = bfs.path(n4); 480 479 481 480 int min = std::numeric_limits<int>::max(); 482 481 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { 483 if (adaptor.rescap(a) < min) min = adaptor.rescap(a); 482 if (adaptor.residualCapacity(a) < min) 483 min = adaptor.residualCapacity(a); 484 484 } 485 485 … … 494 494 } 495 495 496 void checkSplit DigraphAdaptor() {497 checkConcept<concepts::Digraph, Split DigraphAdaptor<concepts::Digraph> >();496 void checkSplitNodes() { 497 checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >(); 498 498 499 499 typedef ListDigraph Digraph; 500 typedef Split DigraphAdaptor<Digraph> Adaptor;500 typedef SplitNodes<Digraph> Adaptor; 501 501 502 502 Digraph digraph; … … 510 510 Digraph::Arc a2 = digraph.addArc(n1, n3); 511 511 Digraph::Arc a3 = digraph.addArc(n2, n3); 512 512 513 513 checkGraphNodeList(adaptor, 6); 514 514 checkGraphArcList(adaptor, 6); … … 531 531 checkNodeIds(adaptor); 532 532 checkArcIds(adaptor); 533 533 534 534 checkGraphNodeMap(adaptor); 535 535 checkGraphArcMap(adaptor); … … 538 538 if (adaptor.origArc(a)) { 539 539 Digraph::Arc oa = a; 540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 541 542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 543 "Wrong split"); 540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 541 "Wrong split"); 542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 543 "Wrong split"); 544 544 } else { 545 545 Digraph::Node on = a; … … 550 550 } 551 551 552 void checkSubGraph Adaptor() {553 checkConcept<concepts::Graph, 554 SubGraph Adaptor<concepts::Graph,552 void checkSubGraph() { 553 checkConcept<concepts::Graph, 554 SubGraph<concepts::Graph, 555 555 concepts::Graph::NodeMap<bool>, 556 556 concepts::Graph::EdgeMap<bool> > >(); … … 559 559 typedef Graph::NodeMap<bool> NodeFilter; 560 560 typedef Graph::EdgeMap<bool> EdgeFilter; 561 typedef SubGraph Adaptor<Graph, NodeFilter, EdgeFilter> Adaptor;561 typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor; 562 562 563 563 Graph graph; … … 608 608 checkGraphEdgeMap(adaptor); 609 609 610 edge_filter[e2] = false; 610 edge_filter[e2] = false; 611 611 612 612 checkGraphNodeList(adaptor, 4); … … 639 639 checkGraphEdgeMap(adaptor); 640 640 641 node_filter[n1] = false; 641 node_filter[n1] = false; 642 642 643 643 checkGraphNodeList(adaptor, 3); … … 685 685 } 686 686 687 void check NodeSubGraphAdaptor() {688 checkConcept<concepts::Graph, 689 NodeSubGraphAdaptor<concepts::Graph,687 void checkFilterNodes2() { 688 checkConcept<concepts::Graph, 689 FilterNodes<concepts::Graph, 690 690 concepts::Graph::NodeMap<bool> > >(); 691 691 692 692 typedef ListGraph Graph; 693 693 typedef Graph::NodeMap<bool> NodeFilter; 694 typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;694 typedef FilterNodes<Graph, NodeFilter> Adaptor; 695 695 696 696 Graph graph; … … 739 739 checkGraphEdgeMap(adaptor); 740 740 741 node_filter[n1] = false; 741 node_filter[n1] = false; 742 742 743 743 checkGraphNodeList(adaptor, 3); … … 784 784 } 785 785 786 void check EdgeSubGraphAdaptor() {787 checkConcept<concepts::Graph, 788 EdgeSubGraphAdaptor<concepts::Graph,786 void checkFilterEdges() { 787 checkConcept<concepts::Graph, 788 FilterEdges<concepts::Graph, 789 789 concepts::Graph::EdgeMap<bool> > >(); 790 790 791 791 typedef ListGraph Graph; 792 792 typedef Graph::EdgeMap<bool> EdgeFilter; 793 typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;793 typedef FilterEdges<Graph, EdgeFilter> Adaptor; 794 794 795 795 Graph graph; … … 838 838 checkGraphEdgeMap(adaptor); 839 839 840 edge_filter[e2] = false; 840 edge_filter[e2] = false; 841 841 842 842 checkGraphNodeList(adaptor, 4); … … 886 886 } 887 887 888 void check DirGraphAdaptor() {889 checkConcept<concepts::Digraph, 890 DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();888 void checkOrienter() { 889 checkConcept<concepts::Digraph, 890 Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >(); 891 891 892 892 typedef ListGraph Graph; 893 893 typedef ListGraph::EdgeMap<bool> DirMap; 894 typedef DirGraphAdaptor<Graph> Adaptor;894 typedef Orienter<Graph> Adaptor; 895 895 896 896 Graph graph; … … 905 905 Graph::Edge e2 = graph.addEdge(n1, n3); 906 906 Graph::Edge e3 = graph.addEdge(n2, n3); 907 907 908 908 checkGraphNodeList(adaptor, 3); 909 909 checkGraphArcList(adaptor, 3); 910 910 checkGraphConArcList(adaptor, 3); 911 911 912 912 { 913 913 dir[e1] = true; 914 914 Adaptor::Node u = adaptor.source(e1); 915 915 Adaptor::Node v = adaptor.target(e1); 916 916 917 917 dir[e1] = false; 918 918 check (u == adaptor.target(e1), "Wrong dir"); … … 927 927 Adaptor::Node u = adaptor.source(e2); 928 928 Adaptor::Node v = adaptor.target(e2); 929 929 930 930 dir[e2] = false; 931 931 check (u == adaptor.target(e2), "Wrong dir"); … … 940 940 Adaptor::Node u = adaptor.source(e3); 941 941 Adaptor::Node v = adaptor.target(e3); 942 942 943 943 dir[e3] = false; 944 944 check (u == adaptor.target(e3), "Wrong dir"); … … 968 968 int main(int, const char **) { 969 969 970 checkRev DigraphAdaptor();971 checkSubDigraph Adaptor();972 check NodeSubDigraphAdaptor();973 check ArcSubDigraphAdaptor();974 checkUndir DigraphAdaptor();975 checkRes DigraphAdaptor();976 checkSplit DigraphAdaptor();977 978 checkSubGraph Adaptor();979 check NodeSubGraphAdaptor();980 check EdgeSubGraphAdaptor();981 check DirGraphAdaptor();970 checkReverseDigraph(); 971 checkSubDigraph(); 972 checkFilterNodes1(); 973 checkFilterArcs(); 974 checkUndirector(); 975 checkResidual(); 976 checkSplitNodes(); 977 978 checkSubGraph(); 979 checkFilterNodes2(); 980 checkFilterEdges(); 981 checkOrienter(); 982 982 983 983 return 0;
Note: See TracChangeset
for help on using the changeset viewer.