Changes in / [578:a2e6b1dd487e:583:99a31b399b59] in lemon-1.2
- Files:
-
- 20 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/adaptors.h
r559 r579 2193 2193 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier; 2194 2194 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } 2195 2196 typedef EdgeNotifier ArcNotifier; 2197 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); } 2195 2198 2196 2199 protected: -
lemon/bits/graph_adaptor_extender.h
r455 r580 22 22 #include <lemon/core.h> 23 23 #include <lemon/error.h> 24 25 #include <lemon/bits/default_map.h>26 24 27 25 namespace lemon { -
lemon/bits/map_extender.h
r440 r580 48 48 typedef typename Parent::Key Key; 49 49 typedef typename Parent::Value Value; 50 typedef typename Parent::Reference Reference; 51 typedef typename Parent::ConstReference ConstReference; 50 52 51 53 class MapIt; … … 188 190 typedef typename Parent::Key Key; 189 191 typedef typename Parent::Value Value; 192 typedef typename Parent::Reference Reference; 193 typedef typename Parent::ConstReference ConstReference; 190 194 191 195 class MapIt; -
lemon/circulation.h
r559 r581 454 454 455 455 for(NodeIt n(_g);n!=INVALID;++n) { 456 _excess->set(n, (*_delta)[n]);456 (*_excess)[n] = (*_delta)[n]; 457 457 } 458 458 459 459 for (ArcIt e(_g);e!=INVALID;++e) { 460 460 _flow->set(e, (*_lo)[e]); 461 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);462 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);461 (*_excess)[_g.target(e)] += (*_flow)[e]; 462 (*_excess)[_g.source(e)] -= (*_flow)[e]; 463 463 } 464 464 … … 483 483 484 484 for(NodeIt n(_g);n!=INVALID;++n) { 485 _excess->set(n, (*_delta)[n]);485 (*_excess)[n] = (*_delta)[n]; 486 486 } 487 487 … … 489 489 if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { 490 490 _flow->set(e, (*_up)[e]); 491 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);492 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);491 (*_excess)[_g.target(e)] += (*_up)[e]; 492 (*_excess)[_g.source(e)] -= (*_up)[e]; 493 493 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { 494 494 _flow->set(e, (*_lo)[e]); 495 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);496 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);495 (*_excess)[_g.target(e)] += (*_lo)[e]; 496 (*_excess)[_g.source(e)] -= (*_lo)[e]; 497 497 } else { 498 498 Value fc = -(*_excess)[_g.target(e)]; 499 499 _flow->set(e, fc); 500 _excess->set(_g.target(e), 0);501 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);500 (*_excess)[_g.target(e)] = 0; 501 (*_excess)[_g.source(e)] -= fc; 502 502 } 503 503 } … … 538 538 if(!_tol.less(fc, exc)) { 539 539 _flow->set(e, (*_flow)[e] + exc); 540 _excess->set(v, (*_excess)[v] + exc);540 (*_excess)[v] += exc; 541 541 if(!_level->active(v) && _tol.positive((*_excess)[v])) 542 542 _level->activate(v); 543 _excess->set(act,0);543 (*_excess)[act] = 0; 544 544 _level->deactivate(act); 545 545 goto next_l; … … 547 547 else { 548 548 _flow->set(e, (*_up)[e]); 549 _excess->set(v, (*_excess)[v] + fc);549 (*_excess)[v] += fc; 550 550 if(!_level->active(v) && _tol.positive((*_excess)[v])) 551 551 _level->activate(v); … … 562 562 if(!_tol.less(fc, exc)) { 563 563 _flow->set(e, (*_flow)[e] - exc); 564 _excess->set(v, (*_excess)[v] + exc);564 (*_excess)[v] += exc; 565 565 if(!_level->active(v) && _tol.positive((*_excess)[v])) 566 566 _level->activate(v); 567 _excess->set(act,0);567 (*_excess)[act] = 0; 568 568 _level->deactivate(act); 569 569 goto next_l; … … 571 571 else { 572 572 _flow->set(e, (*_lo)[e]); 573 _excess->set(v, (*_excess)[v] + fc);573 (*_excess)[v] += fc; 574 574 if(!_level->active(v) && _tol.positive((*_excess)[v])) 575 575 _level->activate(v); … … 580 580 } 581 581 582 _excess->set(act, exc);582 (*_excess)[act] = exc; 583 583 if(!_tol.positive(exc)) _level->deactivate(act); 584 584 else if(mlevel==_node_num) { -
lemon/concepts/digraph.h
r529 r580 422 422 Node oppositeNode(const Node&, const Arc&) const { return INVALID; } 423 423 424 /// \brief Read write map of the nodes to type \c T. 425 /// 426 /// ReadWrite map of the nodes to type \c T. 427 /// \sa Reference 424 /// \brief Reference map of the nodes to type \c T. 425 /// 426 /// Reference map of the nodes to type \c T. 428 427 template<class T> 429 class NodeMap : public Re adWriteMap< Node, T> {428 class NodeMap : public ReferenceMap<Node, T, T&, const T&> { 430 429 public: 431 430 … … 437 436 private: 438 437 ///Copy constructor 439 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } 438 NodeMap(const NodeMap& nm) : 439 ReferenceMap<Node, T, T&, const T&>(nm) { } 440 440 ///Assignment operator 441 441 template <typename CMap> … … 446 446 }; 447 447 448 /// \brief Re ad write map of the arcs to type \c T.448 /// \brief Reference map of the arcs to type \c T. 449 449 /// 450 450 /// Reference map of the arcs to type \c T. 451 /// \sa Reference452 451 template<class T> 453 class ArcMap : public Re adWriteMap<Arc,T> {452 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> { 454 453 public: 455 454 … … 460 459 private: 461 460 ///Copy constructor 462 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { } 461 ArcMap(const ArcMap& em) : 462 ReferenceMap<Arc, T, T&, const T&>(em) { } 463 463 ///Assignment operator 464 464 template <typename CMap> … … 472 472 struct Constraints { 473 473 void constraints() { 474 checkConcept<BaseDigraphComponent, _Digraph>(); 474 475 checkConcept<IterableDigraphComponent<>, _Digraph>(); 475 476 checkConcept<IDableDigraphComponent<>, _Digraph>(); -
lemon/concepts/graph.h
r559 r580 498 498 }; 499 499 500 /// \brief Read write map of the nodes to type \c T. 501 /// 502 /// ReadWrite map of the nodes to type \c T. 503 /// \sa Reference 500 /// \brief Reference map of the nodes to type \c T. 501 /// 502 /// Reference map of the nodes to type \c T. 504 503 template<class T> 505 class NodeMap : public Re adWriteMap< Node, T>504 class NodeMap : public ReferenceMap<Node, T, T&, const T&> 506 505 { 507 506 public: … … 514 513 private: 515 514 ///Copy constructor 516 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } 515 NodeMap(const NodeMap& nm) : 516 ReferenceMap<Node, T, T&, const T&>(nm) { } 517 517 ///Assignment operator 518 518 template <typename CMap> … … 523 523 }; 524 524 525 /// \brief Read write map of the directed arcs to type \c T. 526 /// 527 /// Reference map of the directed arcs to type \c T. 528 /// \sa Reference 525 /// \brief Reference map of the arcs to type \c T. 526 /// 527 /// Reference map of the arcs to type \c T. 529 528 template<class T> 530 class ArcMap : public Re adWriteMap<Arc,T>529 class ArcMap : public ReferenceMap<Arc, T, T&, const T&> 531 530 { 532 531 public: … … 538 537 private: 539 538 ///Copy constructor 540 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { } 539 ArcMap(const ArcMap& em) : 540 ReferenceMap<Arc, T, T&, const T&>(em) { } 541 541 ///Assignment operator 542 542 template <typename CMap> … … 547 547 }; 548 548 549 /// Read write map of the edges to type \c T. 550 551 /// Reference map of the arcs to type \c T. 552 /// \sa Reference 549 /// Reference map of the edges to type \c T. 550 551 /// Reference map of the edges to type \c T. 553 552 template<class T> 554 class EdgeMap : public Re adWriteMap<Edge,T>553 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&> 555 554 { 556 555 public: … … 562 561 private: 563 562 ///Copy constructor 564 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {} 563 EdgeMap(const EdgeMap& em) : 564 ReferenceMap<Edge, T, T&, const T&>(em) {} 565 565 ///Assignment operator 566 566 template <typename CMap> … … 749 749 struct Constraints { 750 750 void constraints() { 751 checkConcept<BaseGraphComponent, _Graph>(); 751 752 checkConcept<IterableGraphComponent<>, _Graph>(); 752 753 checkConcept<IDableGraphComponent<>, _Graph>(); -
lemon/concepts/graph_components.h
r559 r580 32 32 namespace concepts { 33 33 34 /// \brief Skeleton class for graph Node and Arc types35 /// 36 /// This class describes the interface of Node and Arc (andEdge37 /// in undirected graphs) subtypes ofgraph types.34 /// \brief Concept class for \c Node, \c Arc and \c Edge types. 35 /// 36 /// This class describes the concept of \c Node, \c Arc and \c Edge 37 /// subtypes of digraph and graph types. 38 38 /// 39 39 /// \note This class is a template class so that we can use it to 40 /// create graph skeleton classes. The reason for this is than Node 41 /// and Arc types should \em not derive from the same base class. 42 /// For Node you should instantiate it with character 'n' and for Arc 43 /// with 'a'. 44 40 /// create graph skeleton classes. The reason for this is that \c Node 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 42 /// base class. For \c Node you should instantiate it with character 43 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. 45 44 #ifndef DOXYGEN 46 45 template <char sel = '0'> … … 50 49 /// \brief Default constructor. 51 50 /// 51 /// Default constructor. 52 52 /// \warning The default constructor is not required to set 53 53 /// the item to some well-defined value. So you should consider it 54 54 /// as uninitialized. 55 55 GraphItem() {} 56 56 57 /// \brief Copy constructor. 57 58 /// 58 59 /// Copy constructor. 59 ///60 60 GraphItem(const GraphItem &) {} 61 /// \brief Invalid constructor \& conversion. 62 /// 63 /// This constructor initializes the item to be invalid. 61 62 /// \brief Constructor for conversion from \c INVALID. 63 /// 64 /// Constructor for conversion from \c INVALID. 65 /// It initializes the item to be invalid. 64 66 /// \sa Invalid for more details. 65 67 GraphItem(Invalid) {} 66 /// \brief Assign operator for nodes. 67 /// 68 /// The nodes are assignable. 69 /// 70 GraphItem& operator=(GraphItem const&) { return *this; } 68 69 /// \brief Assignment operator. 70 /// 71 /// Assignment operator for the item. 72 GraphItem& operator=(const GraphItem&) { return *this; } 73 71 74 /// \brief Equality operator. 72 75 /// 73 /// Two iterators are equal if and only if they represents the74 /// same node in the graph or both are invalid.75 bool operator==(GraphItem) const { return false; } 76 /// Equality operator. 77 bool operator==(const GraphItem&) const { return false; } 78 76 79 /// \brief Inequality operator. 77 80 /// 78 /// \sa operator==(const Node& n)79 ///80 bool operator!=(GraphItem) const { return false; } 81 82 /// \brief Artificial ordering operator.83 /// 84 /// To allow the use of graph descriptors as key type in std::map or85 /// similar associative container we require this.81 /// Inequality operator. 82 bool operator!=(const GraphItem&) const { return false; } 83 84 /// \brief Ordering operator. 85 /// 86 /// This operator defines an ordering of the items. 87 /// It makes possible to use graph item types as key types in 88 /// associative containers (e.g. \c std::map). 86 89 /// 87 90 /// \note This operator only have to define some strict ordering of 88 91 /// the items; this order has nothing to do with the iteration 89 92 /// ordering of the items. 90 bool operator<( GraphItem) const { return false; }93 bool operator<(const GraphItem&) const { return false; } 91 94 92 95 template<typename _GraphItem> … … 100 103 101 104 bool b; 102 // b = (ia == ib) && (ia != ib) && (ia < ib);103 105 b = (ia == ib) && (ia != ib); 104 106 b = (ia == INVALID) && (ib != INVALID); … … 111 113 }; 112 114 113 /// \brief An empty base directed graph class. 114 /// 115 /// This class provides the minimal set of features needed for a 116 /// directed graph structure. All digraph concepts have to 117 /// conform to this base directed graph. It just provides types 118 /// for nodes and arcs and functions to get the source and the 119 /// target of the arcs. 115 /// \brief Base skeleton class for directed graphs. 116 /// 117 /// This class describes the base interface of directed graph types. 118 /// All digraph %concepts have to conform to this class. 119 /// It just provides types for nodes and arcs and functions 120 /// to get the source and the target nodes of arcs. 120 121 class BaseDigraphComponent { 121 122 public: … … 125 126 /// \brief Node class of the digraph. 126 127 /// 127 /// This class represents the Nodes of the digraph. 128 /// 128 /// This class represents the nodes of the digraph. 129 129 typedef GraphItem<'n'> Node; 130 130 131 131 /// \brief Arc class of the digraph. 132 132 /// 133 /// This class represents the Arcs of the digraph. 134 /// 135 typedef GraphItem<'e'> Arc; 136 137 /// \brief Gives back the target node of an arc. 138 /// 139 /// Gives back the target node of an arc. 140 /// 141 Node target(const Arc&) const { return INVALID;} 142 143 /// \brief Gives back the source node of an arc. 144 /// 145 /// Gives back the source node of an arc. 146 /// 147 Node source(const Arc&) const { return INVALID;} 148 149 /// \brief Gives back the opposite node on the given arc. 150 /// 151 /// Gives back the opposite node on the given arc. 133 /// This class represents the arcs of the digraph. 134 typedef GraphItem<'a'> Arc; 135 136 /// \brief Return the source node of an arc. 137 /// 138 /// This function returns the source node of an arc. 139 Node source(const Arc&) const { return INVALID; } 140 141 /// \brief Return the target node of an arc. 142 /// 143 /// This function returns the target node of an arc. 144 Node target(const Arc&) const { return INVALID; } 145 146 /// \brief Return the opposite node on the given arc. 147 /// 148 /// This function returns the opposite node on the given arc. 152 149 Node oppositeNode(const Node&, const Arc&) const { 153 150 return INVALID; … … 175 172 }; 176 173 177 /// \brief An empty base undirected graph class. 178 /// 179 /// This class provides the minimal set of features needed for an 180 /// undirected graph structure. All undirected graph concepts have 181 /// to conform to this base graph. It just provides types for 182 /// nodes, arcs and edges and functions to get the 183 /// source and the target of the arcs and edges, 184 /// conversion from arcs to edges and function to get 185 /// both direction of the edges. 174 /// \brief Base skeleton class for undirected graphs. 175 /// 176 /// This class describes the base interface of undirected graph types. 177 /// All graph %concepts have to conform to this class. 178 /// It extends the interface of \ref BaseDigraphComponent with an 179 /// \c Edge type and functions to get the end nodes of edges, 180 /// to convert from arcs to edges and to get both direction of edges. 186 181 class BaseGraphComponent : public BaseDigraphComponent { 187 182 public: 188 183 typedef BaseDigraphComponent::Node Node; 189 184 typedef BaseDigraphComponent::Arc Arc; 190 /// \brief Undirected arc class of the graph. 191 /// 192 /// This class represents the edges of the graph. 193 /// The undirected graphs can be used as a directed graph which 194 /// for each arc contains the opposite arc too so the graph is 195 /// bidirected. The edge represents two opposite 196 /// directed arcs. 197 class Edge : public GraphItem<'u'> { 185 186 /// \brief Undirected edge class of the graph. 187 /// 188 /// This class represents the undirected edges of the graph. 189 /// Undirected graphs can be used as directed graphs, each edge is 190 /// represented by two opposite directed arcs. 191 class Edge : public GraphItem<'e'> { 198 192 public: 199 typedef GraphItem<'u'> Parent; 193 typedef GraphItem<'e'> Parent; 194 200 195 /// \brief Default constructor. 201 196 /// 197 /// Default constructor. 202 198 /// \warning The default constructor is not required to set 203 199 /// the item to some well-defined value. So you should consider it 204 200 /// as uninitialized. 205 201 Edge() {} 202 206 203 /// \brief Copy constructor. 207 204 /// 208 205 /// Copy constructor. 209 ///210 206 Edge(const Edge &) : Parent() {} 211 /// \brief Invalid constructor \& conversion. 212 /// 213 /// This constructor initializes the item to be invalid. 207 208 /// \brief Constructor for conversion from \c INVALID. 209 /// 210 /// Constructor for conversion from \c INVALID. 211 /// It initializes the item to be invalid. 214 212 /// \sa Invalid for more details. 215 213 Edge(Invalid) {} 216 /// \brief Converter from arc to edge. 217 /// 214 215 /// \brief Constructor for conversion from an arc. 216 /// 217 /// Constructor for conversion from an arc. 218 218 /// Besides the core graph item functionality each arc should 219 219 /// be convertible to the represented edge. 220 220 Edge(const Arc&) {} 221 /// \brief Assign arc to edge. 222 /// 221 222 /// \brief Assign an arc to an edge. 223 /// 224 /// This function assigns an arc to an edge. 223 225 /// Besides the core graph item functionality each arc should 224 226 /// be convertible to the represented edge. … … 226 228 }; 227 229 228 /// \brief Returns the direction of the arc. 230 /// \brief Return one end node of an edge. 231 /// 232 /// This function returns one end node of an edge. 233 Node u(const Edge&) const { return INVALID; } 234 235 /// \brief Return the other end node of an edge. 236 /// 237 /// This function returns the other end node of an edge. 238 Node v(const Edge&) const { return INVALID; } 239 240 /// \brief Return a directed arc related to an edge. 241 /// 242 /// This function returns a directed arc from its direction and the 243 /// represented edge. 244 Arc direct(const Edge&, bool) const { return INVALID; } 245 246 /// \brief Return a directed arc related to an edge. 247 /// 248 /// This function returns a directed arc from its source node and the 249 /// represented edge. 250 Arc direct(const Edge&, const Node&) const { return INVALID; } 251 252 /// \brief Return the direction of the arc. 229 253 /// 230 254 /// Returns the direction of the arc. Each arc represents an … … 233 257 bool direction(const Arc&) const { return true; } 234 258 235 /// \brief Returns the directed arc. 236 /// 237 /// Returns the directed arc from its direction and the 238 /// represented edge. 239 Arc direct(const Edge&, bool) const { return INVALID;} 240 241 /// \brief Returns the directed arc. 242 /// 243 /// Returns the directed arc from its source and the 244 /// represented edge. 245 Arc direct(const Edge&, const Node&) const { return INVALID;} 246 247 /// \brief Returns the opposite arc. 248 /// 249 /// Returns the opposite arc. It is the arc representing the 250 /// same edge and has opposite direction. 251 Arc oppositeArc(const Arc&) const { return INVALID;} 252 253 /// \brief Gives back one ending of an edge. 254 /// 255 /// Gives back one ending of an edge. 256 Node u(const Edge&) const { return INVALID;} 257 258 /// \brief Gives back the other ending of an edge. 259 /// 260 /// Gives back the other ending of an edge. 261 Node v(const Edge&) const { return INVALID;} 259 /// \brief Return the opposite arc. 260 /// 261 /// This function returns the opposite arc, i.e. the arc representing 262 /// the same edge and has opposite direction. 263 Arc oppositeArc(const Arc&) const { return INVALID; } 262 264 263 265 template <typename _Graph> … … 269 271 void constraints() { 270 272 checkConcept<BaseDigraphComponent, _Graph>(); 271 checkConcept<GraphItem<' u'>, Edge>();273 checkConcept<GraphItem<'e'>, Edge>(); 272 274 { 273 275 Node n; … … 277 279 n = graph.v(ue); 278 280 e = graph.direct(ue, true); 281 e = graph.direct(ue, false); 279 282 e = graph.direct(ue, n); 280 283 e = graph.oppositeArc(e); … … 290 293 }; 291 294 292 /// \brief An empty idable base digraph class.293 /// 294 /// This class provides beside the core digraph features295 /// core id functions for the digraph structure.296 /// The most of the base digraphs should conform to this concept.297 /// Th e id's are unique and immutable.295 /// \brief Skeleton class for \e idable directed graphs. 296 /// 297 /// This class describes the interface of \e idable directed graphs. 298 /// It extends \ref BaseDigraphComponent with the core ID functions. 299 /// The ids of the items must be unique and immutable. 300 /// This concept is part of the Digraph concept. 298 301 template <typename BAS = BaseDigraphComponent> 299 302 class IDableDigraphComponent : public BAS { … … 304 307 typedef typename Base::Arc Arc; 305 308 306 /// \brief Gives back an unique integer id for the Node. 307 /// 308 /// Gives back an unique integer id for the Node. 309 /// 310 int id(const Node&) const { return -1;} 311 312 /// \brief Gives back the node by the unique id. 313 /// 314 /// Gives back the node by the unique id. 315 /// If the digraph does not contain node with the given id 316 /// then the result of the function is undetermined. 317 Node nodeFromId(int) const { return INVALID;} 318 319 /// \brief Gives back an unique integer id for the Arc. 320 /// 321 /// Gives back an unique integer id for the Arc. 322 /// 323 int id(const Arc&) const { return -1;} 324 325 /// \brief Gives back the arc by the unique id. 326 /// 327 /// Gives back the arc by the unique id. 328 /// If the digraph does not contain arc with the given id 329 /// then the result of the function is undetermined. 330 Arc arcFromId(int) const { return INVALID;} 331 332 /// \brief Gives back an integer greater or equal to the maximum 333 /// Node id. 334 /// 335 /// Gives back an integer greater or equal to the maximum Node 336 /// id. 337 int maxNodeId() const { return -1;} 338 339 /// \brief Gives back an integer greater or equal to the maximum 340 /// Arc id. 341 /// 342 /// Gives back an integer greater or equal to the maximum Arc 343 /// id. 344 int maxArcId() const { return -1;} 309 /// \brief Return a unique integer id for the given node. 310 /// 311 /// This function returns a unique integer id for the given node. 312 int id(const Node&) const { return -1; } 313 314 /// \brief Return the node by its unique id. 315 /// 316 /// This function returns the node by its unique id. 317 /// If the digraph does not contain a node with the given id, 318 /// then the result of the function is undefined. 319 Node nodeFromId(int) const { return INVALID; } 320 321 /// \brief Return a unique integer id for the given arc. 322 /// 323 /// This function returns a unique integer id for the given arc. 324 int id(const Arc&) const { return -1; } 325 326 /// \brief Return the arc by its unique id. 327 /// 328 /// This function returns the arc by its unique id. 329 /// If the digraph does not contain an arc with the given id, 330 /// then the result of the function is undefined. 331 Arc arcFromId(int) const { return INVALID; } 332 333 /// \brief Return an integer greater or equal to the maximum 334 /// node id. 335 /// 336 /// This function returns an integer greater or equal to the 337 /// maximum node id. 338 int maxNodeId() const { return -1; } 339 340 /// \brief Return an integer greater or equal to the maximum 341 /// arc id. 342 /// 343 /// This function returns an integer greater or equal to the 344 /// maximum arc id. 345 int maxArcId() const { return -1; } 345 346 346 347 template <typename _Digraph> … … 368 369 }; 369 370 370 /// \brief An empty idable base undirected graph class. 371 /// 372 /// This class provides beside the core undirected graph features 373 /// core id functions for the undirected graph structure. The 374 /// most of the base undirected graphs should conform to this 375 /// concept. The id's are unique and immutable. 371 /// \brief Skeleton class for \e idable undirected graphs. 372 /// 373 /// This class describes the interface of \e idable undirected 374 /// graphs. It extends \ref IDableDigraphComponent with the core ID 375 /// functions of undirected graphs. 376 /// The ids of the items must be unique and immutable. 377 /// This concept is part of the Graph concept. 376 378 template <typename BAS = BaseGraphComponent> 377 379 class IDableGraphComponent : public IDableDigraphComponent<BAS> { … … 383 385 using IDableDigraphComponent<Base>::id; 384 386 385 /// \brief Gives back an unique integer id for the Edge. 386 /// 387 /// Gives back an unique integer id for the Edge. 388 /// 389 int id(const Edge&) const { return -1;} 390 391 /// \brief Gives back the edge by the unique id. 392 /// 393 /// Gives back the edge by the unique id. If the 394 /// graph does not contain arc with the given id then the 395 /// result of the function is undetermined. 396 Edge edgeFromId(int) const { return INVALID;} 397 398 /// \brief Gives back an integer greater or equal to the maximum 399 /// Edge id. 400 /// 401 /// Gives back an integer greater or equal to the maximum Edge 402 /// id. 403 int maxEdgeId() const { return -1;} 387 /// \brief Return a unique integer id for the given edge. 388 /// 389 /// This function returns a unique integer id for the given edge. 390 int id(const Edge&) const { return -1; } 391 392 /// \brief Return the edge by its unique id. 393 /// 394 /// This function returns the edge by its unique id. 395 /// If the graph does not contain an edge with the given id, 396 /// then the result of the function is undefined. 397 Edge edgeFromId(int) const { return INVALID; } 398 399 /// \brief Return an integer greater or equal to the maximum 400 /// edge id. 401 /// 402 /// This function returns an integer greater or equal to the 403 /// maximum edge id. 404 int maxEdgeId() const { return -1; } 404 405 405 406 template <typename _Graph> … … 407 408 408 409 void constraints() { 409 checkConcept<Base, _Graph >();410 410 checkConcept<IDableDigraphComponent<Base>, _Graph >(); 411 411 typename _Graph::Edge edge; … … 421 421 }; 422 422 423 /// \brief Skeleton class for graph NodeIt and ArcIt424 /// 425 /// Skeleton class for graph NodeIt and ArcIt.426 /// 423 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. 424 /// 425 /// This class describes the concept of \c NodeIt, \c ArcIt and 426 /// \c EdgeIt subtypes of digraph and graph types. 427 427 template <typename GR, typename Item> 428 428 class GraphItemIt : public Item { … … 430 430 /// \brief Default constructor. 431 431 /// 432 /// @warning The default constructor sets the iterator 433 /// to an undefined value. 432 /// Default constructor. 433 /// \warning The default constructor is not required to set 434 /// the iterator to some well-defined value. So you should consider it 435 /// as uninitialized. 434 436 GraphItemIt() {} 437 435 438 /// \brief Copy constructor. 436 439 /// 437 440 /// Copy constructor. 438 /// 439 GraphItemIt(const GraphItemIt& ) {} 440 /// \brief Sets the iterator to the first item. 441 /// 442 /// Sets the iterator to the first item of \c the graph. 443 /// 441 GraphItemIt(const GraphItemIt& it) : Item(it) {} 442 443 /// \brief Constructor that sets the iterator to the first item. 444 /// 445 /// Constructor that sets the iterator to the first item. 444 446 explicit GraphItemIt(const GR&) {} 445 /// \brief Invalid constructor \& conversion. 446 /// 447 /// This constructor initializes the item to be invalid. 447 448 /// \brief Constructor for conversion from \c INVALID. 449 /// 450 /// Constructor for conversion from \c INVALID. 451 /// It initializes the iterator to be invalid. 448 452 /// \sa Invalid for more details. 449 453 GraphItemIt(Invalid) {} 450 /// \brief Assign operator for items. 451 /// 452 /// The items are assignable.453 /// 454 455 /// \brief Assignment operator. 456 /// 457 /// Assignment operator for the iterator. 454 458 GraphItemIt& operator=(const GraphItemIt&) { return *this; } 455 /// \brief Next item. 456 /// 457 /// Assign the iterator to the next item. 458 /// 459 460 /// \brief Increment the iterator. 461 /// 462 /// This operator increments the iterator, i.e. assigns it to the 463 /// next item. 459 464 GraphItemIt& operator++() { return *this; } 465 460 466 /// \brief Equality operator 461 467 /// 468 /// Equality operator. 462 469 /// Two iterators are equal if and only if they point to the 463 470 /// same object or both are invalid. 464 471 bool operator==(const GraphItemIt&) const { return true;} 472 465 473 /// \brief Inequality operator 466 474 /// 467 /// \sa operator==(Node n) 468 /// 475 /// Inequality operator. 476 /// Two iterators are equal if and only if they point to the 477 /// same object or both are invalid. 469 478 bool operator!=(const GraphItemIt&) const { return true;} 470 479 … … 472 481 struct Constraints { 473 482 void constraints() { 483 checkConcept<GraphItem<>, _GraphItemIt>(); 474 484 _GraphItemIt it1(g); 475 485 _GraphItemIt it2; 486 _GraphItemIt it3 = it1; 487 _GraphItemIt it4 = INVALID; 476 488 477 489 it2 = ++it1; … … 482 494 bi = it2; 483 495 } 484 GR& g; 485 }; 486 }; 487 488 /// \brief Skeleton class for graph InArcIt and OutArcIt 489 /// 490 /// \note Because InArcIt and OutArcIt may not inherit from the same 491 /// base class, the \c sel is a additional template parameter (selector). 492 /// For InArcIt you should instantiate it with character 'i' and for 493 /// OutArcIt with 'o'. 496 const GR& g; 497 }; 498 }; 499 500 /// \brief Concept class for \c InArcIt, \c OutArcIt and 501 /// \c IncEdgeIt types. 502 /// 503 /// This class describes the concept of \c InArcIt, \c OutArcIt 504 /// and \c IncEdgeIt subtypes of digraph and graph types. 505 /// 506 /// \note Since these iterator classes do not inherit from the same 507 /// base class, there is an additional template parameter (selector) 508 /// \c sel. For \c InArcIt you should instantiate it with character 509 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 494 510 template <typename GR, 495 511 typename Item = typename GR::Arc, … … 500 516 /// \brief Default constructor. 501 517 /// 502 /// @warning The default constructor sets the iterator 503 /// to an undefined value. 518 /// Default constructor. 519 /// \warning The default constructor is not required to set 520 /// the iterator to some well-defined value. So you should consider it 521 /// as uninitialized. 504 522 GraphIncIt() {} 523 505 524 /// \brief Copy constructor. 506 525 /// 507 526 /// Copy constructor. 508 /// 509 GraphIncIt(GraphIncIt const& gi) : Item(gi) {} 510 /// \brief Sets the iterator to the first arc incoming into or outgoing 511 /// from the node. 512 /// 513 /// Sets the iterator to the first arc incoming into or outgoing 514 /// from the node. 515 /// 527 GraphIncIt(const GraphIncIt& it) : Item(it) {} 528 529 /// \brief Constructor that sets the iterator to the first 530 /// incoming or outgoing arc. 531 /// 532 /// Constructor that sets the iterator to the first arc 533 /// incoming to or outgoing from the given node. 516 534 explicit GraphIncIt(const GR&, const Base&) {} 517 /// \brief Invalid constructor \& conversion. 518 /// 519 /// This constructor initializes the item to be invalid. 535 536 /// \brief Constructor for conversion from \c INVALID. 537 /// 538 /// Constructor for conversion from \c INVALID. 539 /// It initializes the iterator to be invalid. 520 540 /// \sa Invalid for more details. 521 541 GraphIncIt(Invalid) {} 522 /// \brief Assign operator for iterators. 523 /// 524 /// The iterators are assignable. 525 /// 526 GraphIncIt& operator=(GraphIncIt const&) { return *this; } 527 /// \brief Next item. 528 /// 529 /// Assign the iterator to the next item. 530 /// 542 543 /// \brief Assignment operator. 544 /// 545 /// Assignment operator for the iterator. 546 GraphIncIt& operator=(const GraphIncIt&) { return *this; } 547 548 /// \brief Increment the iterator. 549 /// 550 /// This operator increments the iterator, i.e. assigns it to the 551 /// next arc incoming to or outgoing from the given node. 531 552 GraphIncIt& operator++() { return *this; } 532 553 533 554 /// \brief Equality operator 534 555 /// 556 /// Equality operator. 535 557 /// Two iterators are equal if and only if they point to the 536 558 /// same object or both are invalid. … … 539 561 /// \brief Inequality operator 540 562 /// 541 /// \sa operator==(Node n) 542 /// 563 /// Inequality operator. 564 /// Two iterators are equal if and only if they point to the 565 /// same object or both are invalid. 543 566 bool operator!=(const GraphIncIt&) const { return true;} 544 567 … … 549 572 _GraphIncIt it1(graph, node); 550 573 _GraphIncIt it2; 574 _GraphIncIt it3 = it1; 575 _GraphIncIt it4 = INVALID; 551 576 552 577 it2 = ++it1; … … 555 580 Item e = it1; 556 581 e = it2; 557 558 } 559 560 Item arc; 561 Base node; 562 GR graph; 563 _GraphIncIt it; 564 }; 565 }; 566 567 568 /// \brief An empty iterable digraph class. 569 /// 570 /// This class provides beside the core digraph features 571 /// iterator based iterable interface for the digraph structure. 582 } 583 const Base& node; 584 const GR& graph; 585 }; 586 }; 587 588 /// \brief Skeleton class for iterable directed graphs. 589 /// 590 /// This class describes the interface of iterable directed 591 /// graphs. It extends \ref BaseDigraphComponent with the core 592 /// iterable interface. 572 593 /// This concept is part of the Digraph concept. 573 594 template <typename BAS = BaseDigraphComponent> … … 584 605 /// \name Base iteration 585 606 /// 586 /// This interface provides functions for iteration on digraph items 607 /// This interface provides functions for iteration on digraph items. 587 608 /// 588 609 /// @{ 589 610 590 /// \brief Gives back the first node in the iterating order. 591 /// 592 /// Gives back the first node in the iterating order. 593 /// 611 /// \brief Return the first node. 612 /// 613 /// This function gives back the first node in the iteration order. 594 614 void first(Node&) const {} 595 615 596 /// \brief Gives back the next node in the iterating order. 597 /// 598 /// Gives back the next node in the iterating order. 599 /// 616 /// \brief Return the next node. 617 /// 618 /// This function gives back the next node in the iteration order. 600 619 void next(Node&) const {} 601 620 602 /// \brief Gives back the first arc in the iterating order. 603 /// 604 /// Gives back the first arc in the iterating order. 605 /// 621 /// \brief Return the first arc. 622 /// 623 /// This function gives back the first arc in the iteration order. 606 624 void first(Arc&) const {} 607 625 608 /// \brief Gives back the next arc in the iterating order. 609 /// 610 /// Gives back the next arc in the iterating order. 611 /// 626 /// \brief Return the next arc. 627 /// 628 /// This function gives back the next arc in the iteration order. 612 629 void next(Arc&) const {} 613 630 614 615 /// \brief Gives back the first of the arcs point to the given 616 /// node. 617 /// 618 /// Gives back the first of the arcs point to the given node. 619 /// 631 /// \brief Return the first arc incomming to the given node. 632 /// 633 /// This function gives back the first arc incomming to the 634 /// given node. 620 635 void firstIn(Arc&, const Node&) const {} 621 636 622 /// \brief Gives back the next of the arcs points to the given 623 /// node. 624 /// 625 /// Gives back the next of the arcs points to the given node. 626 /// 637 /// \brief Return the next arc incomming to the given node. 638 /// 639 /// This function gives back the next arc incomming to the 640 /// given node. 627 641 void nextIn(Arc&) const {} 628 642 629 /// \brief Gives back the first of the arcs start from the 643 /// \brief Return the first arc outgoing form the given node. 644 /// 645 /// This function gives back the first arc outgoing form the 630 646 /// given node. 631 ///632 /// Gives back the first of the arcs start from the given node.633 ///634 647 void firstOut(Arc&, const Node&) const {} 635 648 636 /// \brief Gives back the next of the arcs start from the given 637 /// node. 638 /// 639 /// Gives back the next of the arcs start from the given node. 640 /// 649 /// \brief Return the next arc outgoing form the given node. 650 /// 651 /// This function gives back the next arc outgoing form the 652 /// given node. 641 653 void nextOut(Arc&) const {} 642 654 … … 645 657 /// \name Class based iteration 646 658 /// 647 /// This interface provides functions for iteration on digraph items659 /// This interface provides iterator classes for digraph items. 648 660 /// 649 661 /// @{ … … 655 667 typedef GraphItemIt<Digraph, Node> NodeIt; 656 668 657 /// \brief This iterator goes through each node.658 /// 659 /// This iterator goes through each node.669 /// \brief This iterator goes through each arc. 670 /// 671 /// This iterator goes through each arc. 660 672 /// 661 673 typedef GraphItemIt<Digraph, Arc> ArcIt; … … 663 675 /// \brief This iterator goes trough the incoming arcs of a node. 664 676 /// 665 /// This iterator goes trough the \e inc coming arcs of a certain node677 /// This iterator goes trough the \e incoming arcs of a certain node 666 678 /// of a digraph. 667 679 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt; … … 675 687 /// \brief The base node of the iterator. 676 688 /// 677 /// Gives back the base node of the iterator.678 /// It is always the target of the pointed arc.689 /// This function gives back the base node of the iterator. 690 /// It is always the target node of the pointed arc. 679 691 Node baseNode(const InArcIt&) const { return INVALID; } 680 692 681 693 /// \brief The running node of the iterator. 682 694 /// 683 /// Gives back the running node of the iterator.684 /// It is always the source of the pointed arc.695 /// This function gives back the running node of the iterator. 696 /// It is always the source node of the pointed arc. 685 697 Node runningNode(const InArcIt&) const { return INVALID; } 686 698 687 699 /// \brief The base node of the iterator. 688 700 /// 689 /// Gives back the base node of the iterator.690 /// It is always the source of the pointed arc.701 /// This function gives back the base node of the iterator. 702 /// It is always the source node of the pointed arc. 691 703 Node baseNode(const OutArcIt&) const { return INVALID; } 692 704 693 705 /// \brief The running node of the iterator. 694 706 /// 695 /// Gives back the running node of the iterator.696 /// It is always the target of the pointed arc.707 /// This function gives back the running node of the iterator. 708 /// It is always the target node of the pointed arc. 697 709 Node runningNode(const OutArcIt&) const { return INVALID; } 698 710 … … 736 748 737 749 typename _Digraph::Node n; 738 typename _Digraph::InArcIt ieit(INVALID);739 typename _Digraph::OutArcIt oeit(INVALID);740 n = digraph.baseNode(i eit);741 n = digraph.runningNode(i eit);742 n = digraph.baseNode(o eit);743 n = digraph.runningNode(o eit);750 const typename _Digraph::InArcIt iait(INVALID); 751 const typename _Digraph::OutArcIt oait(INVALID); 752 n = digraph.baseNode(iait); 753 n = digraph.runningNode(iait); 754 n = digraph.baseNode(oait); 755 n = digraph.runningNode(oait); 744 756 ignore_unused_variable_warning(n); 745 757 } … … 747 759 748 760 const _Digraph& digraph; 749 750 751 }; 752 753 /// \brief An empty iterable undirected graph class.754 /// 755 /// This class provides beside the core graph features iterator756 /// based iterable interface for the undirected graph structure.761 }; 762 }; 763 764 /// \brief Skeleton class for iterable undirected graphs. 765 /// 766 /// This class describes the interface of iterable undirected 767 /// graphs. It extends \ref IterableDigraphComponent with the core 768 /// iterable interface of undirected graphs. 757 769 /// This concept is part of the Graph concept. 758 770 template <typename BAS = BaseGraphComponent> … … 770 782 /// \name Base iteration 771 783 /// 772 /// This interface provides functions for iteration on graph items 784 /// This interface provides functions for iteration on edges. 785 /// 773 786 /// @{ 774 787 … … 776 789 using IterableDigraphComponent<Base>::next; 777 790 778 /// \brief Gives back the first edge in the iterating 779 /// order. 780 /// 781 /// Gives back the first edge in the iterating order. 782 /// 791 /// \brief Return the first edge. 792 /// 793 /// This function gives back the first edge in the iteration order. 783 794 void first(Edge&) const {} 784 795 785 /// \brief Gives back the next edge in the iterating 786 /// order. 787 /// 788 /// Gives back the next edge in the iterating order. 789 /// 796 /// \brief Return the next edge. 797 /// 798 /// This function gives back the next edge in the iteration order. 790 799 void next(Edge&) const {} 791 800 792 793 /// \brief Gives back the first of the edges from the 801 /// \brief Return the first edge incident to the given node. 802 /// 803 /// This function gives back the first edge incident to the given 804 /// node. The bool parameter gives back the direction for which the 805 /// source node of the directed arc representing the edge is the 794 806 /// given node. 795 ///796 /// Gives back the first of the edges from the given797 /// node. The bool parameter gives back that direction which798 /// gives a good direction of the edge so the source of the799 /// directed arc is the given node.800 807 void firstInc(Edge&, bool&, const Node&) const {} 801 808 … … 803 810 /// given node. 804 811 /// 805 /// Gives back the next of the edges from the given 806 /// node. The bool parameter should be used as the \c firstInc() 807 /// use it. 812 /// This function gives back the next edge incident to the given 813 /// node. The bool parameter should be used as \c firstInc() use it. 808 814 void nextInc(Edge&, bool&) const {} 809 815 … … 815 821 /// \name Class based iteration 816 822 /// 817 /// This interface provides functions for iteration on graph items823 /// This interface provides iterator classes for edges. 818 824 /// 819 825 /// @{ 820 826 821 /// \brief This iterator goes through each node.822 /// 823 /// This iterator goes through each node.827 /// \brief This iterator goes through each edge. 828 /// 829 /// This iterator goes through each edge. 824 830 typedef GraphItemIt<Graph, Edge> EdgeIt; 825 /// \brief This iterator goes trough the incident arcs of a 831 832 /// \brief This iterator goes trough the incident edges of a 826 833 /// node. 827 834 /// 828 /// This iterator goes trough the incident arcs of a certain835 /// This iterator goes trough the incident edges of a certain 829 836 /// node of a graph. 830 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 837 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt; 838 831 839 /// \brief The base node of the iterator. 832 840 /// 833 /// Gives back the base node of the iterator.841 /// This function gives back the base node of the iterator. 834 842 Node baseNode(const IncEdgeIt&) const { return INVALID; } 835 843 836 844 /// \brief The running node of the iterator. 837 845 /// 838 /// Gives back the running node of the iterator.846 /// This function gives back the running node of the iterator. 839 847 Node runningNode(const IncEdgeIt&) const { return INVALID; } 840 848 … … 865 873 typename _Graph::EdgeIt >(); 866 874 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 867 typename _Graph::Node, ' u'>, typename _Graph::IncEdgeIt>();875 typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>(); 868 876 869 877 typename _Graph::Node n; 870 typename _Graph::IncEdgeIt ueit(INVALID);871 n = graph.baseNode( ueit);872 n = graph.runningNode( ueit);878 const typename _Graph::IncEdgeIt ieit(INVALID); 879 n = graph.baseNode(ieit); 880 n = graph.runningNode(ieit); 873 881 } 874 882 } … … 878 886 }; 879 887 880 /// \brief An empty alteration notifier digraph class. 881 /// 882 /// This class provides beside the core digraph features alteration 883 /// notifier interface for the digraph structure. This implements 888 /// \brief Skeleton class for alterable directed graphs. 889 /// 890 /// This class describes the interface of alterable directed 891 /// graphs. It extends \ref BaseDigraphComponent with the alteration 892 /// notifier interface. It implements 884 893 /// an observer-notifier pattern for each digraph item. More 885 894 /// obsevers can be registered into the notifier and whenever an 886 /// alteration occured in the digraph all the observers will 895 /// alteration occured in the digraph all the observers will be 887 896 /// notified about it. 888 897 template <typename BAS = BaseDigraphComponent> … … 895 904 896 905 897 /// The node observer registry.906 /// Node alteration notifier class. 898 907 typedef AlterationNotifier<AlterableDigraphComponent, Node> 899 908 NodeNotifier; 900 /// The arc observer registry.909 /// Arc alteration notifier class. 901 910 typedef AlterationNotifier<AlterableDigraphComponent, Arc> 902 911 ArcNotifier; 903 912 904 /// \brief Gives backthe node alteration notifier.905 /// 906 /// Gives back the node alteration notifier.913 /// \brief Return the node alteration notifier. 914 /// 915 /// This function gives back the node alteration notifier. 907 916 NodeNotifier& notifier(Node) const { 908 return NodeNotifier();917 return NodeNotifier(); 909 918 } 910 919 911 /// \brief Gives backthe arc alteration notifier.912 /// 913 /// Gives back the arc alteration notifier.920 /// \brief Return the arc alteration notifier. 921 /// 922 /// This function gives back the arc alteration notifier. 914 923 ArcNotifier& notifier(Arc) const { 915 924 return ArcNotifier(); … … 931 940 932 941 const _Digraph& digraph; 933 934 }; 935 936 }; 937 938 /// \brief An empty alteration notifier undirected graph class. 939 /// 940 /// This class provides beside the core graph features alteration 941 /// notifier interface for the graph structure. This implements 942 /// an observer-notifier pattern for each graph item. More 942 }; 943 }; 944 945 /// \brief Skeleton class for alterable undirected graphs. 946 /// 947 /// This class describes the interface of alterable undirected 948 /// graphs. It extends \ref AlterableDigraphComponent with the alteration 949 /// notifier interface of undirected graphs. It implements 950 /// an observer-notifier pattern for the edges. More 943 951 /// obsevers can be registered into the notifier and whenever an 944 /// alteration occured in the graph all the observers will 952 /// alteration occured in the graph all the observers will be 945 953 /// notified about it. 946 954 template <typename BAS = BaseGraphComponent> … … 952 960 953 961 954 /// The arc observer registry.962 /// Edge alteration notifier class. 955 963 typedef AlterationNotifier<AlterableGraphComponent, Edge> 956 964 EdgeNotifier; 957 965 958 /// \brief Gives back the arcalteration notifier.959 /// 960 /// Gives back the arcalteration notifier.966 /// \brief Return the edge alteration notifier. 967 /// 968 /// This function gives back the edge alteration notifier. 961 969 EdgeNotifier& notifier(Edge) const { 962 970 return EdgeNotifier(); … … 966 974 struct Constraints { 967 975 void constraints() { 968 checkConcept<Alterable GraphComponent<Base>, _Graph>();976 checkConcept<AlterableDigraphComponent<Base>, _Graph>(); 969 977 typename _Graph::EdgeNotifier& uen 970 978 = graph.notifier(typename _Graph::Edge()); … … 976 984 }; 977 985 978 /// \brief Class describing the concept of graph maps 979 /// 980 /// This class describes the common interface of the graph maps 981 /// (NodeMap, ArcMap), that is maps that can be used to 982 /// associate data to graph descriptors (nodes or arcs). 986 /// \brief Concept class for standard graph maps. 987 /// 988 /// This class describes the concept of standard graph maps, i.e. 989 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 990 /// graph types, which can be used for associating data to graph items. 991 /// The standard graph maps must conform to the ReferenceMap concept. 983 992 template <typename GR, typename K, typename V> 984 class GraphMap : public Re adWriteMap<K, V> {993 class GraphMap : public ReferenceMap<K, V, V&, const V&> { 985 994 public: 986 995 … … 993 1002 /// The value type of the map. 994 1003 typedef V Value; 1004 /// The reference type of the map. 1005 typedef Value& Reference; 1006 /// The const reference type of the map. 1007 typedef const Value& ConstReference; 1008 1009 // The reference map tag. 1010 typedef True ReferenceMapTag; 995 1011 996 1012 /// \brief Construct a new map. … … 1000 1016 /// \brief Construct a new map with default value. 1001 1017 /// 1002 /// Construct a new map for the graph and initali se the values.1018 /// Construct a new map for the graph and initalize the values. 1003 1019 GraphMap(const Graph&, const Value&) {} 1004 1020 … … 1009 1025 GraphMap(const GraphMap&) : Parent() {} 1010 1026 1011 /// \brief Assign operator.1012 /// 1013 /// Assign operator. It does not mofify the underlying graph,1027 /// \brief Assignment operator. 1028 /// 1029 /// Assignment operator. It does not mofify the underlying graph, 1014 1030 /// it just iterates on the current item set and set the map 1015 1031 /// with the value returned by the assigned map. … … 1024 1040 struct Constraints { 1025 1041 void constraints() { 1026 checkConcept<ReadWriteMap<Key, Value>, _Map >(); 1027 // Construction with a graph parameter 1028 _Map a(g); 1029 // Constructor with a graph and a default value parameter 1030 _Map a2(g,t); 1031 // Copy constructor. 1032 // _Map b(c); 1033 1042 checkConcept 1043 <ReferenceMap<Key, Value, Value&, const Value&>, _Map>(); 1044 _Map m1(g); 1045 _Map m2(g,t); 1046 1047 // Copy constructor 1048 // _Map m3(m); 1049 1050 // Assignment operator 1034 1051 // ReadMap<Key, Value> cmap; 1035 // b= cmap;1036 1037 ignore_unused_variable_warning( a);1038 ignore_unused_variable_warning( a2);1039 // ignore_unused_variable_warning( b);1040 } 1041 1042 const _Map & c;1052 // m3 = cmap; 1053 1054 ignore_unused_variable_warning(m1); 1055 ignore_unused_variable_warning(m2); 1056 // ignore_unused_variable_warning(m3); 1057 } 1058 1059 const _Map &m; 1043 1060 const Graph &g; 1044 1061 const typename GraphMap::Value &t; … … 1047 1064 }; 1048 1065 1049 /// \brief An empty mappable digraph class. 1050 /// 1051 /// This class provides beside the core digraph features 1052 /// map interface for the digraph structure. 1066 /// \brief Skeleton class for mappable directed graphs. 1067 /// 1068 /// This class describes the interface of mappable directed graphs. 1069 /// It extends \ref BaseDigraphComponent with the standard digraph 1070 /// map classes, namely \c NodeMap and \c ArcMap. 1053 1071 /// This concept is part of the Digraph concept. 1054 1072 template <typename BAS = BaseDigraphComponent> … … 1062 1080 typedef MappableDigraphComponent Digraph; 1063 1081 1064 /// \brief ReadWrite map ofthe nodes.1065 /// 1066 /// ReadWrite map ofthe nodes.1067 /// 1082 /// \brief Standard graph map for the nodes. 1083 /// 1084 /// Standard graph map for the nodes. 1085 /// It conforms to the ReferenceMap concept. 1068 1086 template <typename V> 1069 class NodeMap : public GraphMap< Digraph, Node, V> {1087 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> { 1070 1088 public: 1071 1089 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; … … 1079 1097 /// \brief Construct a new map with default value. 1080 1098 /// 1081 /// Construct a new map for the digraph and initali se the values.1099 /// Construct a new map for the digraph and initalize the values. 1082 1100 NodeMap(const MappableDigraphComponent& digraph, const V& value) 1083 1101 : Parent(digraph, value) {} … … 1089 1107 NodeMap(const NodeMap& nm) : Parent(nm) {} 1090 1108 1091 /// \brief Assign operator.1092 /// 1093 /// Assign operator.1109 /// \brief Assignment operator. 1110 /// 1111 /// Assignment operator. 1094 1112 template <typename CMap> 1095 1113 NodeMap& operator=(const CMap&) { … … 1100 1118 }; 1101 1119 1102 /// \brief ReadWrite map ofthe arcs.1103 /// 1104 /// ReadWrite map ofthe arcs.1105 /// 1120 /// \brief Standard graph map for the arcs. 1121 /// 1122 /// Standard graph map for the arcs. 1123 /// It conforms to the ReferenceMap concept. 1106 1124 template <typename V> 1107 class ArcMap : public GraphMap< Digraph, Arc, V> {1125 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> { 1108 1126 public: 1109 1127 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; … … 1117 1135 /// \brief Construct a new map with default value. 1118 1136 /// 1119 /// Construct a new map for the digraph and initali se the values.1137 /// Construct a new map for the digraph and initalize the values. 1120 1138 ArcMap(const MappableDigraphComponent& digraph, const V& value) 1121 1139 : Parent(digraph, value) {} … … 1127 1145 ArcMap(const ArcMap& nm) : Parent(nm) {} 1128 1146 1129 /// \brief Assign operator.1130 /// 1131 /// Assign operator.1147 /// \brief Assignment operator. 1148 /// 1149 /// Assignment operator. 1132 1150 template <typename CMap> 1133 1151 ArcMap& operator=(const CMap&) { … … 1179 1197 } 1180 1198 1181 _Digraph& digraph; 1182 }; 1183 }; 1184 1185 /// \brief An empty mappable base bipartite graph class. 1186 /// 1187 /// This class provides beside the core graph features 1188 /// map interface for the graph structure. 1199 const _Digraph& digraph; 1200 }; 1201 }; 1202 1203 /// \brief Skeleton class for mappable undirected graphs. 1204 /// 1205 /// This class describes the interface of mappable undirected graphs. 1206 /// It extends \ref MappableDigraphComponent with the standard graph 1207 /// map class for edges (\c EdgeMap). 1189 1208 /// This concept is part of the Graph concept. 1190 1209 template <typename BAS = BaseGraphComponent> … … 1197 1216 typedef MappableGraphComponent Graph; 1198 1217 1199 /// \brief ReadWrite map ofthe edges.1200 /// 1201 /// ReadWrite map ofthe edges.1202 /// 1218 /// \brief Standard graph map for the edges. 1219 /// 1220 /// Standard graph map for the edges. 1221 /// It conforms to the ReferenceMap concept. 1203 1222 template <typename V> 1204 class EdgeMap : public GraphMap< Graph, Edge, V> {1223 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> { 1205 1224 public: 1206 1225 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; … … 1214 1233 /// \brief Construct a new map with default value. 1215 1234 /// 1216 /// Construct a new map for the graph and initali se the values.1235 /// Construct a new map for the graph and initalize the values. 1217 1236 EdgeMap(const MappableGraphComponent& graph, const V& value) 1218 1237 : Parent(graph, value) {} … … 1224 1243 EdgeMap(const EdgeMap& nm) : Parent(nm) {} 1225 1244 1226 /// \brief Assign operator.1227 /// 1228 /// Assign operator.1245 /// \brief Assignment operator. 1246 /// 1247 /// Assignment operator. 1229 1248 template <typename CMap> 1230 1249 EdgeMap& operator=(const CMap&) { … … 1246 1265 1247 1266 void constraints() { 1248 checkConcept<Mappable GraphComponent<Base>, _Graph>();1267 checkConcept<MappableDigraphComponent<Base>, _Graph>(); 1249 1268 1250 1269 { // int map test … … 1263 1282 } 1264 1283 1265 _Graph& graph;1266 }; 1267 }; 1268 1269 /// \brief An empty extendable digraph class.1270 /// 1271 /// This class provides beside the core digraph features digraph1272 /// extendable interface for the digraph structure. The main1273 /// difference between the base and this interface is that the1274 /// digraph alterations should handled already on this level.1284 const _Graph& graph; 1285 }; 1286 }; 1287 1288 /// \brief Skeleton class for extendable directed graphs. 1289 /// 1290 /// This class describes the interface of extendable directed graphs. 1291 /// It extends \ref BaseDigraphComponent with functions for adding 1292 /// nodes and arcs to the digraph. 1293 /// This concept requires \ref AlterableDigraphComponent. 1275 1294 template <typename BAS = BaseDigraphComponent> 1276 1295 class ExtendableDigraphComponent : public BAS { … … 1281 1300 typedef typename Base::Arc Arc; 1282 1301 1283 /// \brief Adds a new node to the digraph. 1284 /// 1285 /// Adds a new node to the digraph. 1286 /// 1302 /// \brief Add a new node to the digraph. 1303 /// 1304 /// This function adds a new node to the digraph. 1287 1305 Node addNode() { 1288 1306 return INVALID; 1289 1307 } 1290 1308 1291 /// \brief Adds a new arc connects the given two nodes. 1292 /// 1293 /// Adds a new arc connects the the given two nodes. 1309 /// \brief Add a new arc connecting the given two nodes. 1310 /// 1311 /// This function adds a new arc connecting the given two nodes 1312 /// of the digraph. 1294 1313 Arc addArc(const Node&, const Node&) { 1295 1314 return INVALID; … … 1311 1330 }; 1312 1331 1313 /// \brief An empty extendable base undirected graph class. 1314 /// 1315 /// This class provides beside the core undirected graph features 1316 /// core undircted graph extend interface for the graph structure. 1317 /// The main difference between the base and this interface is 1318 /// that the graph alterations should handled already on this 1319 /// level. 1332 /// \brief Skeleton class for extendable undirected graphs. 1333 /// 1334 /// This class describes the interface of extendable undirected graphs. 1335 /// It extends \ref BaseGraphComponent with functions for adding 1336 /// nodes and edges to the graph. 1337 /// This concept requires \ref AlterableGraphComponent. 1320 1338 template <typename BAS = BaseGraphComponent> 1321 1339 class ExtendableGraphComponent : public BAS { … … 1326 1344 typedef typename Base::Edge Edge; 1327 1345 1328 /// \brief Adds a new node to the graph. 1329 /// 1330 /// Adds a new node to the graph. 1331 /// 1346 /// \brief Add a new node to the digraph. 1347 /// 1348 /// This function adds a new node to the digraph. 1332 1349 Node addNode() { 1333 1350 return INVALID; 1334 1351 } 1335 1352 1336 /// \brief Adds a new arc connects the given two nodes. 1337 /// 1338 /// Adds a new arc connects the the given two nodes. 1339 Edge addArc(const Node&, const Node&) { 1353 /// \brief Add a new edge connecting the given two nodes. 1354 /// 1355 /// This function adds a new edge connecting the given two nodes 1356 /// of the graph. 1357 Edge addEdge(const Node&, const Node&) { 1340 1358 return INVALID; 1341 1359 } … … 1356 1374 }; 1357 1375 1358 /// \brief An empty erasable digraph class.1359 /// 1360 /// This class provides beside the core digraph features core erase1361 /// functions for the digraph structure. The main difference between1362 /// the base and this interface is that the digraph alterations1363 /// should handled already on this level.1376 /// \brief Skeleton class for erasable directed graphs. 1377 /// 1378 /// This class describes the interface of erasable directed graphs. 1379 /// It extends \ref BaseDigraphComponent with functions for removing 1380 /// nodes and arcs from the digraph. 1381 /// This concept requires \ref AlterableDigraphComponent. 1364 1382 template <typename BAS = BaseDigraphComponent> 1365 1383 class ErasableDigraphComponent : public BAS { … … 1372 1390 /// \brief Erase a node from the digraph. 1373 1391 /// 1374 /// Erase a node from the digraph. This function should1375 /// erase all arcs connectingto the node.1392 /// This function erases the given node from the digraph and all arcs 1393 /// connected to the node. 1376 1394 void erase(const Node&) {} 1377 1395 1378 1396 /// \brief Erase an arc from the digraph. 1379 1397 /// 1380 /// Erase an arc from the digraph. 1381 /// 1398 /// This function erases the given arc from the digraph. 1382 1399 void erase(const Arc&) {} 1383 1400 … … 1386 1403 void constraints() { 1387 1404 checkConcept<Base, _Digraph>(); 1388 typename _Digraph::Node node;1405 const typename _Digraph::Node node(INVALID); 1389 1406 digraph.erase(node); 1390 typename _Digraph::Arc arc;1407 const typename _Digraph::Arc arc(INVALID); 1391 1408 digraph.erase(arc); 1392 1409 } … … 1396 1413 }; 1397 1414 1398 /// \brief An empty erasable base undirected graph class.1399 /// 1400 /// This class provides beside the core undirected graph features1401 /// core erase functions for the undirceted graph structure. The1402 /// main difference between the base and this interface is that1403 /// the graph alterations should handled already on this level.1415 /// \brief Skeleton class for erasable undirected graphs. 1416 /// 1417 /// This class describes the interface of erasable undirected graphs. 1418 /// It extends \ref BaseGraphComponent with functions for removing 1419 /// nodes and edges from the graph. 1420 /// This concept requires \ref AlterableGraphComponent. 1404 1421 template <typename BAS = BaseGraphComponent> 1405 1422 class ErasableGraphComponent : public BAS { … … 1412 1429 /// \brief Erase a node from the graph. 1413 1430 /// 1414 /// Erase a node from the graph. This function should erase1415 /// arcs connectingto the node.1431 /// This function erases the given node from the graph and all edges 1432 /// connected to the node. 1416 1433 void erase(const Node&) {} 1417 1434 1418 /// \brief Erase an arc from the graph. 1419 /// 1420 /// Erase an arc from the graph. 1421 /// 1435 /// \brief Erase an edge from the digraph. 1436 /// 1437 /// This function erases the given edge from the digraph. 1422 1438 void erase(const Edge&) {} 1423 1439 … … 1426 1442 void constraints() { 1427 1443 checkConcept<Base, _Graph>(); 1428 typename _Graph::Node node;1444 const typename _Graph::Node node(INVALID); 1429 1445 graph.erase(node); 1430 typename _Graph::Edge edge;1446 const typename _Graph::Edge edge(INVALID); 1431 1447 graph.erase(edge); 1432 1448 } … … 1436 1452 }; 1437 1453 1438 /// \brief An empty clearable base digraph class.1439 /// 1440 /// This class provides beside the core digraph features core clear1441 /// functions for the digraph structure. The main difference between1442 /// the base and this interface is that the digraph alterations1443 /// should handled already on this level.1454 /// \brief Skeleton class for clearable directed graphs. 1455 /// 1456 /// This class describes the interface of clearable directed graphs. 1457 /// It extends \ref BaseDigraphComponent with a function for clearing 1458 /// the digraph. 1459 /// This concept requires \ref AlterableDigraphComponent. 1444 1460 template <typename BAS = BaseDigraphComponent> 1445 1461 class ClearableDigraphComponent : public BAS { … … 1450 1466 /// \brief Erase all nodes and arcs from the digraph. 1451 1467 /// 1452 /// Erase all nodes and arcs from the digraph. 1453 /// 1468 /// This function erases all nodes and arcs from the digraph. 1454 1469 void clear() {} 1455 1470 … … 1461 1476 } 1462 1477 1463 _Digraph digraph;1464 }; 1465 }; 1466 1467 /// \brief An empty clearable base undirected graph class.1468 /// 1469 /// This class provides beside the core undirected graph features1470 /// core clear functions for the undirected graph structure. The1471 /// main difference between the base and this interface is that1472 /// the graph alterations should handled already on this level.1478 _Digraph& digraph; 1479 }; 1480 }; 1481 1482 /// \brief Skeleton class for clearable undirected graphs. 1483 /// 1484 /// This class describes the interface of clearable undirected graphs. 1485 /// It extends \ref BaseGraphComponent with a function for clearing 1486 /// the graph. 1487 /// This concept requires \ref AlterableGraphComponent. 1473 1488 template <typename BAS = BaseGraphComponent> 1474 1489 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> { … … 1477 1492 typedef BAS Base; 1478 1493 1494 /// \brief Erase all nodes and edges from the graph. 1495 /// 1496 /// This function erases all nodes and edges from the graph. 1497 void clear() {} 1498 1479 1499 template <typename _Graph> 1480 1500 struct Constraints { 1481 1501 void constraints() { 1482 checkConcept<ClearableGraphComponent<Base>, _Graph>(); 1483 } 1484 1485 _Graph graph; 1502 checkConcept<Base, _Graph>(); 1503 graph.clear(); 1504 } 1505 1506 _Graph& graph; 1486 1507 }; 1487 1508 }; -
lemon/core.h
r559 r581 1316 1316 virtual void clear() { 1317 1317 for(NodeIt n(_g);n!=INVALID;++n) { 1318 _head .set(n, INVALID);1318 _head[n] = INVALID; 1319 1319 } 1320 1320 } … … 1323 1323 Node s = _g.source(arc); 1324 1324 Node t = _g.target(arc); 1325 _left .set(arc, INVALID);1326 _right .set(arc, INVALID);1325 _left[arc] = INVALID; 1326 _right[arc] = INVALID; 1327 1327 1328 1328 Arc e = _head[s]; 1329 1329 if (e == INVALID) { 1330 _head .set(s, arc);1331 _parent .set(arc, INVALID);1330 _head[s] = arc; 1331 _parent[arc] = INVALID; 1332 1332 return; 1333 1333 } … … 1335 1335 if (t < _g.target(e)) { 1336 1336 if (_left[e] == INVALID) { 1337 _left .set(e, arc);1338 _parent .set(arc, e);1337 _left[e] = arc; 1338 _parent[arc] = e; 1339 1339 splay(arc); 1340 1340 return; … … 1344 1344 } else { 1345 1345 if (_right[e] == INVALID) { 1346 _right .set(e, arc);1347 _parent .set(arc, e);1346 _right[e] = arc; 1347 _parent[arc] = e; 1348 1348 splay(arc); 1349 1349 return; … … 1358 1358 if (_left[arc] == INVALID) { 1359 1359 if (_right[arc] != INVALID) { 1360 _parent .set(_right[arc], _parent[arc]);1360 _parent[_right[arc]] = _parent[arc]; 1361 1361 } 1362 1362 if (_parent[arc] != INVALID) { 1363 1363 if (_left[_parent[arc]] == arc) { 1364 _left .set(_parent[arc], _right[arc]);1364 _left[_parent[arc]] = _right[arc]; 1365 1365 } else { 1366 _right .set(_parent[arc], _right[arc]);1366 _right[_parent[arc]] = _right[arc]; 1367 1367 } 1368 1368 } else { 1369 _head .set(_g.source(arc), _right[arc]);1369 _head[_g.source(arc)] = _right[arc]; 1370 1370 } 1371 1371 } else if (_right[arc] == INVALID) { 1372 _parent .set(_left[arc], _parent[arc]);1372 _parent[_left[arc]] = _parent[arc]; 1373 1373 if (_parent[arc] != INVALID) { 1374 1374 if (_left[_parent[arc]] == arc) { 1375 _left .set(_parent[arc], _left[arc]);1375 _left[_parent[arc]] = _left[arc]; 1376 1376 } else { 1377 _right .set(_parent[arc], _left[arc]);1377 _right[_parent[arc]] = _left[arc]; 1378 1378 } 1379 1379 } else { 1380 _head .set(_g.source(arc), _left[arc]);1380 _head[_g.source(arc)] = _left[arc]; 1381 1381 } 1382 1382 } else { … … 1388 1388 } 1389 1389 Arc s = _parent[e]; 1390 _right .set(_parent[e], _left[e]);1390 _right[_parent[e]] = _left[e]; 1391 1391 if (_left[e] != INVALID) { 1392 _parent .set(_left[e], _parent[e]);1392 _parent[_left[e]] = _parent[e]; 1393 1393 } 1394 1394 1395 _left .set(e, _left[arc]);1396 _parent .set(_left[arc], e);1397 _right .set(e, _right[arc]);1398 _parent .set(_right[arc], e);1399 1400 _parent .set(e, _parent[arc]);1395 _left[e] = _left[arc]; 1396 _parent[_left[arc]] = e; 1397 _right[e] = _right[arc]; 1398 _parent[_right[arc]] = e; 1399 1400 _parent[e] = _parent[arc]; 1401 1401 if (_parent[arc] != INVALID) { 1402 1402 if (_left[_parent[arc]] == arc) { 1403 _left .set(_parent[arc], e);1403 _left[_parent[arc]] = e; 1404 1404 } else { 1405 _right .set(_parent[arc], e);1405 _right[_parent[arc]] = e; 1406 1406 } 1407 1407 } 1408 1408 splay(s); 1409 1409 } else { 1410 _right .set(e, _right[arc]);1411 _parent .set(_right[arc], e);1412 _parent .set(e, _parent[arc]);1410 _right[e] = _right[arc]; 1411 _parent[_right[arc]] = e; 1412 _parent[e] = _parent[arc]; 1413 1413 1414 1414 if (_parent[arc] != INVALID) { 1415 1415 if (_left[_parent[arc]] == arc) { 1416 _left .set(_parent[arc], e);1416 _left[_parent[arc]] = e; 1417 1417 } else { 1418 _right .set(_parent[arc], e);1418 _right[_parent[arc]] = e; 1419 1419 } 1420 1420 } else { 1421 _head .set(_g.source(arc), e);1421 _head[_g.source(arc)] = e; 1422 1422 } 1423 1423 } … … 1431 1431 if (a < m) { 1432 1432 Arc left = refreshRec(v,a,m-1); 1433 _left .set(me, left);1434 _parent .set(left, me);1433 _left[me] = left; 1434 _parent[left] = me; 1435 1435 } else { 1436 _left .set(me, INVALID);1436 _left[me] = INVALID; 1437 1437 } 1438 1438 if (m < b) { 1439 1439 Arc right = refreshRec(v,m+1,b); 1440 _right .set(me, right);1441 _parent .set(right, me);1440 _right[me] = right; 1441 _parent[right] = me; 1442 1442 } else { 1443 _right .set(me, INVALID);1443 _right[me] = INVALID; 1444 1444 } 1445 1445 return me; … … 1453 1453 std::sort(v.begin(),v.end(),ArcLess(_g)); 1454 1454 Arc head = refreshRec(v,0,v.size()-1); 1455 _head .set(n, head);1456 _parent .set(head, INVALID);1457 } 1458 else _head .set(n, INVALID);1455 _head[n] = head; 1456 _parent[head] = INVALID; 1457 } 1458 else _head[n] = INVALID; 1459 1459 } 1460 1460 } … … 1462 1462 void zig(Arc v) { 1463 1463 Arc w = _parent[v]; 1464 _parent .set(v, _parent[w]);1465 _parent .set(w, v);1466 _left .set(w, _right[v]);1467 _right .set(v, w);1464 _parent[v] = _parent[w]; 1465 _parent[w] = v; 1466 _left[w] = _right[v]; 1467 _right[v] = w; 1468 1468 if (_parent[v] != INVALID) { 1469 1469 if (_right[_parent[v]] == w) { 1470 _right .set(_parent[v], v);1470 _right[_parent[v]] = v; 1471 1471 } else { 1472 _left .set(_parent[v], v);1472 _left[_parent[v]] = v; 1473 1473 } 1474 1474 } 1475 1475 if (_left[w] != INVALID){ 1476 _parent .set(_left[w], w);1476 _parent[_left[w]] = w; 1477 1477 } 1478 1478 } … … 1480 1480 void zag(Arc v) { 1481 1481 Arc w = _parent[v]; 1482 _parent .set(v, _parent[w]);1483 _parent .set(w, v);1484 _right .set(w, _left[v]);1485 _left .set(v, w);1482 _parent[v] = _parent[w]; 1483 _parent[w] = v; 1484 _right[w] = _left[v]; 1485 _left[v] = w; 1486 1486 if (_parent[v] != INVALID){ 1487 1487 if (_left[_parent[v]] == w) { 1488 _left .set(_parent[v], v);1488 _left[_parent[v]] = v; 1489 1489 } else { 1490 _right .set(_parent[v], v);1490 _right[_parent[v]] = v; 1491 1491 } 1492 1492 } 1493 1493 if (_right[w] != INVALID){ 1494 _parent .set(_right[w], w);1494 _parent[_right[w]] = w; 1495 1495 } 1496 1496 } -
lemon/elevator.h
r559 r581 77 77 void copy(Item i, Vit p) 78 78 { 79 _where .set(*p=i,p);79 _where[*p=i] = p; 80 80 } 81 81 void copy(Vit s, Vit p) … … 85 85 Item i=*s; 86 86 *p=i; 87 _where .set(i,p);87 _where[i] = p; 88 88 } 89 89 } … … 92 92 Item ti=*i; 93 93 Vit ct = _where[ti]; 94 _where .set(ti,_where[*i=*j]);95 _where .set(*j,ct);94 _where[ti] = _where[*i=*j]; 95 _where[*j] = ct; 96 96 *j=ti; 97 97 } … … 227 227 { 228 228 Item it = *_last_active[_highest_active]; 229 _level.set(it,_level[it]+1);229 ++_level[it]; 230 230 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); 231 231 --_first[++_highest_active]; … … 250 250 } 251 251 copy(li,_first[new_level]); 252 _level .set(li,new_level);252 _level[li] = new_level; 253 253 _highest_active=new_level; 254 254 } … … 270 270 copy(li,_first[_max_level]); 271 271 --_last_active[_max_level]; 272 _level .set(li,_max_level);272 _level[li] = _max_level; 273 273 274 274 while(_highest_active>=0 && … … 300 300 { 301 301 Item it =*_last_active[level]; 302 _level.set(it,_level[it]+1);302 ++_level[it]; 303 303 swap(_last_active[level]--, --_first[level+1]); 304 304 if (level+1>_highest_active) ++_highest_active; … … 320 320 } 321 321 copy(ai,_first[new_level]); 322 _level .set(ai,new_level);322 _level[ai] = new_level; 323 323 if (new_level>_highest_active) _highest_active=new_level; 324 324 } … … 340 340 copy(ai,_first[_max_level]); 341 341 --_last_active[_max_level]; 342 _level .set(ai,_max_level);342 _level[ai] = _max_level; 343 343 344 344 if (_highest_active==level) { … … 371 371 } 372 372 copy(i,_first[new_level]); 373 _level .set(i,new_level);373 _level[i] = new_level; 374 374 if(new_level>_highest_active) _highest_active=new_level; 375 375 } … … 383 383 ///\pre The item is on the top level. 384 384 void dirtyTopButOne(Item i) { 385 _level .set(i,_max_level - 1);385 _level[i] = _max_level - 1; 386 386 } 387 387 … … 395 395 const Vit tl=_first[_max_level]; 396 396 for(Vit i=f;i!=tl;++i) 397 _level .set(*i,_max_level);397 _level[*i] = _max_level; 398 398 for(int i=l;i<=_max_level;i++) 399 399 { … … 434 434 { 435 435 *n=i; 436 _where .set(i,n);437 _level .set(i,_max_level);436 _where[i] = n; 437 _level[i] = _max_level; 438 438 ++n; 439 439 } … … 444 444 { 445 445 swap(_where[i],_init_num); 446 _level .set(i,_init_lev);446 _level[i] = _init_lev; 447 447 ++_init_num; 448 448 } … … 552 552 ///\pre Item \c i shouldn't be active before. 553 553 void activate(Item i) { 554 _active .set(i, true);554 _active[i] = true; 555 555 556 556 int level = _level[i]; … … 561 561 if (_prev[i] == INVALID || _active[_prev[i]]) return; 562 562 //unlace 563 _next .set(_prev[i], _next[i]);563 _next[_prev[i]] = _next[i]; 564 564 if (_next[i] != INVALID) { 565 _prev .set(_next[i], _prev[i]);565 _prev[_next[i]] = _prev[i]; 566 566 } else { 567 567 _last[level] = _prev[i]; 568 568 } 569 569 //lace 570 _next .set(i, _first[level]);571 _prev .set(_first[level], i);572 _prev .set(i, INVALID);570 _next[i] = _first[level]; 571 _prev[_first[level]] = i; 572 _prev[i] = INVALID; 573 573 _first[level] = i; 574 574 … … 580 580 ///\pre Item \c i must be active before. 581 581 void deactivate(Item i) { 582 _active .set(i, false);582 _active[i] = false; 583 583 int level = _level[i]; 584 584 … … 587 587 588 588 //unlace 589 _prev .set(_next[i], _prev[i]);589 _prev[_next[i]] = _prev[i]; 590 590 if (_prev[i] != INVALID) { 591 _next .set(_prev[i], _next[i]);591 _next[_prev[i]] = _next[i]; 592 592 } else { 593 593 _first[_level[i]] = _next[i]; 594 594 } 595 595 //lace 596 _prev .set(i, _last[level]);597 _next .set(_last[level], i);598 _next .set(i, INVALID);596 _prev[i] = _last[level]; 597 _next[_last[level]] = i; 598 _next[i] = INVALID; 599 599 _last[level] = i; 600 600 … … 686 686 Item i = _first[_highest_active]; 687 687 if (_next[i] != INVALID) { 688 _prev .set(_next[i], INVALID);688 _prev[_next[i]] = INVALID; 689 689 _first[_highest_active] = _next[i]; 690 690 } else { … … 692 692 _last[_highest_active] = INVALID; 693 693 } 694 _level .set(i, ++_highest_active);694 _level[i] = ++_highest_active; 695 695 if (_first[_highest_active] == INVALID) { 696 696 _first[_highest_active] = i; 697 697 _last[_highest_active] = i; 698 _prev .set(i, INVALID);699 _next .set(i, INVALID);700 } else { 701 _prev .set(_first[_highest_active], i);702 _next .set(i, _first[_highest_active]);698 _prev[i] = INVALID; 699 _next[i] = INVALID; 700 } else { 701 _prev[_first[_highest_active]] = i; 702 _next[i] = _first[_highest_active]; 703 703 _first[_highest_active] = i; 704 704 } … … 715 715 Item i = _first[_highest_active]; 716 716 if (_next[i] != INVALID) { 717 _prev .set(_next[i], INVALID);717 _prev[_next[i]] = INVALID; 718 718 _first[_highest_active] = _next[i]; 719 719 } else { … … 721 721 _last[_highest_active] = INVALID; 722 722 } 723 _level .set(i, _highest_active = new_level);723 _level[i] = _highest_active = new_level; 724 724 if (_first[_highest_active] == INVALID) { 725 725 _first[_highest_active] = _last[_highest_active] = i; 726 _prev .set(i, INVALID);727 _next .set(i, INVALID);728 } else { 729 _prev .set(_first[_highest_active], i);730 _next .set(i, _first[_highest_active]);726 _prev[i] = INVALID; 727 _next[i] = INVALID; 728 } else { 729 _prev[_first[_highest_active]] = i; 730 _next[i] = _first[_highest_active]; 731 731 _first[_highest_active] = i; 732 732 } … … 739 739 void liftHighestActiveToTop() { 740 740 Item i = _first[_highest_active]; 741 _level .set(i, _max_level);741 _level[i] = _max_level; 742 742 if (_next[i] != INVALID) { 743 _prev .set(_next[i], INVALID);743 _prev[_next[i]] = INVALID; 744 744 _first[_highest_active] = _next[i]; 745 745 } else { … … 775 775 Item i = _first[l]; 776 776 if (_next[i] != INVALID) { 777 _prev .set(_next[i], INVALID);777 _prev[_next[i]] = INVALID; 778 778 _first[l] = _next[i]; 779 779 } else { … … 781 781 _last[l] = INVALID; 782 782 } 783 _level .set(i, ++l);783 _level[i] = ++l; 784 784 if (_first[l] == INVALID) { 785 785 _first[l] = _last[l] = i; 786 _prev .set(i, INVALID);787 _next .set(i, INVALID);788 } else { 789 _prev .set(_first[l], i);790 _next .set(i, _first[l]);786 _prev[i] = INVALID; 787 _next[i] = INVALID; 788 } else { 789 _prev[_first[l]] = i; 790 _next[i] = _first[l]; 791 791 _first[l] = i; 792 792 } … … 804 804 Item i = _first[l]; 805 805 if (_next[i] != INVALID) { 806 _prev .set(_next[i], INVALID);806 _prev[_next[i]] = INVALID; 807 807 _first[l] = _next[i]; 808 808 } else { … … 810 810 _last[l] = INVALID; 811 811 } 812 _level .set(i, l = new_level);812 _level[i] = l = new_level; 813 813 if (_first[l] == INVALID) { 814 814 _first[l] = _last[l] = i; 815 _prev .set(i, INVALID);816 _next .set(i, INVALID);817 } else { 818 _prev .set(_first[l], i);819 _next .set(i, _first[l]);815 _prev[i] = INVALID; 816 _next[i] = INVALID; 817 } else { 818 _prev[_first[l]] = i; 819 _next[i] = _first[l]; 820 820 _first[l] = i; 821 821 } … … 833 833 Item i = _first[l]; 834 834 if (_next[i] != INVALID) { 835 _prev .set(_next[i], INVALID);835 _prev[_next[i]] = INVALID; 836 836 _first[l] = _next[i]; 837 837 } else { … … 839 839 _last[l] = INVALID; 840 840 } 841 _level .set(i, _max_level);841 _level[i] = _max_level; 842 842 if (l == _highest_active) { 843 843 while (_highest_active >= 0 && activeFree(_highest_active)) … … 857 857 void lift(Item i, int new_level) { 858 858 if (_next[i] != INVALID) { 859 _prev .set(_next[i], _prev[i]);859 _prev[_next[i]] = _prev[i]; 860 860 } else { 861 861 _last[new_level] = _prev[i]; 862 862 } 863 863 if (_prev[i] != INVALID) { 864 _next .set(_prev[i], _next[i]);864 _next[_prev[i]] = _next[i]; 865 865 } else { 866 866 _first[new_level] = _next[i]; 867 867 } 868 _level .set(i, new_level);868 _level[i] = new_level; 869 869 if (_first[new_level] == INVALID) { 870 870 _first[new_level] = _last[new_level] = i; 871 _prev .set(i, INVALID);872 _next .set(i, INVALID);873 } else { 874 _prev .set(_first[new_level], i);875 _next .set(i, _first[new_level]);871 _prev[i] = INVALID; 872 _next[i] = INVALID; 873 } else { 874 _prev[_first[new_level]] = i; 875 _next[i] = _first[new_level]; 876 876 _first[new_level] = i; 877 877 } … … 889 889 ///\pre The item is on the top level. 890 890 void dirtyTopButOne(Item i) { 891 _level .set(i, _max_level - 1);891 _level[i] = _max_level - 1; 892 892 } 893 893 … … 900 900 Item n = _first[i]; 901 901 while (n != INVALID) { 902 _level .set(n, _max_level);902 _level[n] = _max_level; 903 903 n = _next[n]; 904 904 } … … 938 938 for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph); 939 939 i != INVALID; ++i) { 940 _level .set(i, _max_level);941 _active .set(i, false);940 _level[i] = _max_level; 941 _active[i] = false; 942 942 } 943 943 } … … 945 945 ///Add an item to the current level. 946 946 void initAddItem(Item i) { 947 _level .set(i, _init_level);947 _level[i] = _init_level; 948 948 if (_last[_init_level] == INVALID) { 949 949 _first[_init_level] = i; 950 950 _last[_init_level] = i; 951 _prev .set(i, INVALID);952 _next .set(i, INVALID);953 } else { 954 _prev .set(i, _last[_init_level]);955 _next .set(i, INVALID);956 _next .set(_last[_init_level], i);951 _prev[i] = INVALID; 952 _next[i] = INVALID; 953 } else { 954 _prev[i] = _last[_init_level]; 955 _next[i] = INVALID; 956 _next[_last[_init_level]] = i; 957 957 _last[_init_level] = i; 958 958 } -
lemon/full_graph.h
r440 r582 158 158 /// constant space in memory. 159 159 /// 160 /// This class conforms to the \ref concepts::Digraph "Digraph" concept 161 /// and it also has an important extra feature that its maps are 162 /// real \ref concepts::ReferenceMap "reference map"s. 160 /// This class fully conforms to the \ref concepts::Digraph 161 /// "Digraph concept". 163 162 /// 164 163 /// The \c FullDigraph and \c FullGraph classes are very similar, … … 528 527 /// space in memory. 529 528 /// 530 /// This class conforms to the \ref concepts::Graph "Graph" concept 531 /// and it also has an important extra feature that its maps are 532 /// real \ref concepts::ReferenceMap "reference map"s. 529 /// This class fully conforms to the \ref concepts::Graph "Graph concept". 533 530 /// 534 531 /// The \c FullGraph and \c FullDigraph classes are very similar, -
lemon/gomory_hu.h
r546 r581 144 144 _root = NodeIt(_graph); 145 145 for (NodeIt n(_graph); n != INVALID; ++n) { 146 _pred->set(n, _root);147 _order->set(n, -1);148 } 149 _pred->set(_root, INVALID);150 _weight->set(_root, std::numeric_limits<Value>::max());146 (*_pred)[n] = _root; 147 (*_order)[n] = -1; 148 } 149 (*_pred)[_root] = INVALID; 150 (*_weight)[_root] = std::numeric_limits<Value>::max(); 151 151 } 152 152 … … 165 165 fa.runMinCut(); 166 166 167 _weight->set(n, fa.flowValue());167 (*_weight)[n] = fa.flowValue(); 168 168 169 169 for (NodeIt nn(_graph); nn != INVALID; ++nn) { 170 170 if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { 171 _pred->set(nn, n);171 (*_pred)[nn] = n; 172 172 } 173 173 } 174 174 if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { 175 _pred->set(n, (*_pred)[pn]);176 _pred->set(pn, n);177 _weight->set(n, (*_weight)[pn]);178 _weight->set(pn, fa.flowValue());179 } 180 } 181 182 _order->set(_root, 0);175 (*_pred)[n] = (*_pred)[pn]; 176 (*_pred)[pn] = n; 177 (*_weight)[n] = (*_weight)[pn]; 178 (*_weight)[pn] = fa.flowValue(); 179 } 180 } 181 182 (*_order)[_root] = 0; 183 183 int index = 1; 184 184 … … 191 191 } 192 192 while (!st.empty()) { 193 _order->set(st.back(), index++);193 (*_order)[st.back()] = index++; 194 194 st.pop_back(); 195 195 } … … 310 310 311 311 typename Graph::template NodeMap<bool> reached(_graph, false); 312 reached .set(_root, true);312 reached[_root] = true; 313 313 cutMap.set(_root, !s_root); 314 reached .set(rn, true);314 reached[rn] = true; 315 315 cutMap.set(rn, s_root); 316 316 -
lemon/grid_graph.h
r559 r582 498 498 /// 499 499 /// This graph type fully conforms to the \ref concepts::Graph 500 /// "Graph" concept, and it also has an important extra feature 501 /// that its maps are real \ref concepts::ReferenceMap 502 /// "reference map"s. 500 /// "Graph concept". 503 501 class GridGraph : public ExtendedGridGraphBase { 504 502 public: -
lemon/hao_orlin.h
r559 r581 162 162 163 163 void activate(const Node& i) { 164 _active->set(i, true);164 (*_active)[i] = true; 165 165 166 166 int bucket = (*_bucket)[i]; … … 168 168 if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; 169 169 //unlace 170 _next->set((*_prev)[i], (*_next)[i]);170 (*_next)[(*_prev)[i]] = (*_next)[i]; 171 171 if ((*_next)[i] != INVALID) { 172 _prev->set((*_next)[i], (*_prev)[i]);172 (*_prev)[(*_next)[i]] = (*_prev)[i]; 173 173 } else { 174 174 _last[bucket] = (*_prev)[i]; 175 175 } 176 176 //lace 177 _next->set(i, _first[bucket]);178 _prev->set(_first[bucket], i);179 _prev->set(i, INVALID);177 (*_next)[i] = _first[bucket]; 178 (*_prev)[_first[bucket]] = i; 179 (*_prev)[i] = INVALID; 180 180 _first[bucket] = i; 181 181 } 182 182 183 183 void deactivate(const Node& i) { 184 _active->set(i, false);184 (*_active)[i] = false; 185 185 int bucket = (*_bucket)[i]; 186 186 … … 188 188 189 189 //unlace 190 _prev->set((*_next)[i], (*_prev)[i]);190 (*_prev)[(*_next)[i]] = (*_prev)[i]; 191 191 if ((*_prev)[i] != INVALID) { 192 _next->set((*_prev)[i], (*_next)[i]);192 (*_next)[(*_prev)[i]] = (*_next)[i]; 193 193 } else { 194 194 _first[bucket] = (*_next)[i]; 195 195 } 196 196 //lace 197 _prev->set(i, _last[bucket]);198 _next->set(_last[bucket], i);199 _next->set(i, INVALID);197 (*_prev)[i] = _last[bucket]; 198 (*_next)[_last[bucket]] = i; 199 (*_next)[i] = INVALID; 200 200 _last[bucket] = i; 201 201 } … … 204 204 (*_bucket)[i] = bucket; 205 205 if (_last[bucket] != INVALID) { 206 _prev->set(i, _last[bucket]);207 _next->set(_last[bucket], i);208 _next->set(i, INVALID);206 (*_prev)[i] = _last[bucket]; 207 (*_next)[_last[bucket]] = i; 208 (*_next)[i] = INVALID; 209 209 _last[bucket] = i; 210 210 } else { 211 _prev->set(i, INVALID);211 (*_prev)[i] = INVALID; 212 212 _first[bucket] = i; 213 _next->set(i, INVALID);213 (*_next)[i] = INVALID; 214 214 _last[bucket] = i; 215 215 } … … 219 219 220 220 for (NodeIt n(_graph); n != INVALID; ++n) { 221 _excess->set(n, 0);221 (*_excess)[n] = 0; 222 222 } 223 223 224 224 for (ArcIt a(_graph); a != INVALID; ++a) { 225 _flow->set(a, 0);225 (*_flow)[a] = 0; 226 226 } 227 227 … … 233 233 typename Digraph::template NodeMap<bool> reached(_graph, false); 234 234 235 reached .set(_source, true);235 reached[_source] = true; 236 236 bool first_set = true; 237 237 … … 241 241 242 242 queue[qlast++] = t; 243 reached .set(t, true);243 reached[t] = true; 244 244 245 245 while (qfirst != qlast) { … … 258 258 Node u = _graph.source(a); 259 259 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 260 reached .set(u, true);260 reached[u] = true; 261 261 queue[qlast++] = u; 262 262 } … … 267 267 268 268 ++bucket_num; 269 _bucket->set(_source, 0);269 (*_bucket)[_source] = 0; 270 270 _dormant[0] = true; 271 271 } 272 _source_set->set(_source, true);272 (*_source_set)[_source] = true; 273 273 274 274 Node target = _last[_sets.back().back()]; … … 277 277 if (_tolerance.positive((*_capacity)[a])) { 278 278 Node u = _graph.target(a); 279 _flow->set(a, (*_capacity)[a]);280 _excess->set(u, (*_excess)[u] + (*_capacity)[a]);279 (*_flow)[a] = (*_capacity)[a]; 280 (*_excess)[u] += (*_capacity)[a]; 281 281 if (!(*_active)[u] && u != _source) { 282 282 activate(u); … … 319 319 } 320 320 if (!_tolerance.less(rem, excess)) { 321 _flow->set(a, (*_flow)[a] + excess);322 _excess->set(v, (*_excess)[v] + excess);321 (*_flow)[a] += excess; 322 (*_excess)[v] += excess; 323 323 excess = 0; 324 324 goto no_more_push; 325 325 } else { 326 326 excess -= rem; 327 _excess->set(v, (*_excess)[v] + rem);328 _flow->set(a, (*_capacity)[a]);327 (*_excess)[v] += rem; 328 (*_flow)[a] = (*_capacity)[a]; 329 329 } 330 330 } else if (next_bucket > (*_bucket)[v]) { … … 343 343 } 344 344 if (!_tolerance.less(rem, excess)) { 345 _flow->set(a, (*_flow)[a] - excess);346 _excess->set(v, (*_excess)[v] + excess);345 (*_flow)[a] -= excess; 346 (*_excess)[v] += excess; 347 347 excess = 0; 348 348 goto no_more_push; 349 349 } else { 350 350 excess -= rem; 351 _excess->set(v, (*_excess)[v] + rem);352 _flow->set(a, 0);351 (*_excess)[v] += rem; 352 (*_flow)[a] = 0; 353 353 } 354 354 } else if (next_bucket > (*_bucket)[v]) { … … 359 359 no_more_push: 360 360 361 _excess->set(n, excess);361 (*_excess)[n] = excess; 362 362 363 363 if (excess != 0) { … … 377 377 } else if (next_bucket == _node_num) { 378 378 _first[(*_bucket)[n]] = (*_next)[n]; 379 _prev->set((*_next)[n], INVALID);379 (*_prev)[(*_next)[n]] = INVALID; 380 380 381 381 std::list<std::list<int> >::iterator new_set = … … 383 383 384 384 new_set->push_front(bucket_num); 385 _bucket->set(n, bucket_num);385 (*_bucket)[n] = bucket_num; 386 386 _first[bucket_num] = _last[bucket_num] = n; 387 _next->set(n, INVALID);388 _prev->set(n, INVALID);387 (*_next)[n] = INVALID; 388 (*_prev)[n] = INVALID; 389 389 _dormant[bucket_num] = true; 390 390 ++bucket_num; … … 396 396 } else { 397 397 _first[*_highest] = (*_next)[n]; 398 _prev->set((*_next)[n], INVALID);398 (*_prev)[(*_next)[n]] = INVALID; 399 399 400 400 while (next_bucket != *_highest) { … … 410 410 --_highest; 411 411 412 _bucket->set(n, *_highest);413 _next->set(n, _first[*_highest]);412 (*_bucket)[n] = *_highest; 413 (*_next)[n] = _first[*_highest]; 414 414 if (_first[*_highest] != INVALID) { 415 _prev->set(_first[*_highest], n);415 (*_prev)[_first[*_highest]] = n; 416 416 } else { 417 417 _last[*_highest] = n; … … 435 435 _min_cut = (*_excess)[target]; 436 436 for (NodeIt i(_graph); i != INVALID; ++i) { 437 _min_cut_map->set(i, true);437 (*_min_cut_map)[i] = true; 438 438 } 439 439 for (std::list<int>::iterator it = _sets.back().begin(); … … 441 441 Node n = _first[*it]; 442 442 while (n != INVALID) { 443 _min_cut_map->set(n, false);443 (*_min_cut_map)[n] = false; 444 444 n = (*_next)[n]; 445 445 } … … 454 454 new_target = (*_prev)[target]; 455 455 } else { 456 _prev->set((*_next)[target], (*_prev)[target]);456 (*_prev)[(*_next)[target]] = (*_prev)[target]; 457 457 new_target = (*_next)[target]; 458 458 } … … 460 460 _first[(*_bucket)[target]] = (*_next)[target]; 461 461 } else { 462 _next->set((*_prev)[target], (*_next)[target]);462 (*_next)[(*_prev)[target]] = (*_next)[target]; 463 463 } 464 464 } else { … … 476 476 } 477 477 478 _bucket->set(target, 0);479 480 _source_set->set(target, true);478 (*_bucket)[target] = 0; 479 480 (*_source_set)[target] = true; 481 481 for (OutArcIt a(_graph, target); a != INVALID; ++a) { 482 482 Value rem = (*_capacity)[a] - (*_flow)[a]; … … 486 486 activate(v); 487 487 } 488 _excess->set(v, (*_excess)[v] + rem);489 _flow->set(a, (*_capacity)[a]);488 (*_excess)[v] += rem; 489 (*_flow)[a] = (*_capacity)[a]; 490 490 } 491 491 … … 497 497 activate(v); 498 498 } 499 _excess->set(v, (*_excess)[v] + rem);500 _flow->set(a, 0);499 (*_excess)[v] += rem; 500 (*_flow)[a] = 0; 501 501 } 502 502 … … 518 518 519 519 for (NodeIt n(_graph); n != INVALID; ++n) { 520 _excess->set(n, 0);520 (*_excess)[n] = 0; 521 521 } 522 522 523 523 for (ArcIt a(_graph); a != INVALID; ++a) { 524 _flow->set(a, 0);524 (*_flow)[a] = 0; 525 525 } 526 526 … … 532 532 typename Digraph::template NodeMap<bool> reached(_graph, false); 533 533 534 reached .set(_source, true);534 reached[_source] = true; 535 535 536 536 bool first_set = true; … … 541 541 542 542 queue[qlast++] = t; 543 reached .set(t, true);543 reached[t] = true; 544 544 545 545 while (qfirst != qlast) { … … 558 558 Node u = _graph.target(a); 559 559 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 560 reached .set(u, true);560 reached[u] = true; 561 561 queue[qlast++] = u; 562 562 } … … 567 567 568 568 ++bucket_num; 569 _bucket->set(_source, 0);569 (*_bucket)[_source] = 0; 570 570 _dormant[0] = true; 571 571 } 572 _source_set->set(_source, true);572 (*_source_set)[_source] = true; 573 573 574 574 Node target = _last[_sets.back().back()]; … … 577 577 if (_tolerance.positive((*_capacity)[a])) { 578 578 Node u = _graph.source(a); 579 _flow->set(a, (*_capacity)[a]);580 _excess->set(u, (*_excess)[u] + (*_capacity)[a]);579 (*_flow)[a] = (*_capacity)[a]; 580 (*_excess)[u] += (*_capacity)[a]; 581 581 if (!(*_active)[u] && u != _source) { 582 582 activate(u); … … 619 619 } 620 620 if (!_tolerance.less(rem, excess)) { 621 _flow->set(a, (*_flow)[a] + excess);622 _excess->set(v, (*_excess)[v] + excess);621 (*_flow)[a] += excess; 622 (*_excess)[v] += excess; 623 623 excess = 0; 624 624 goto no_more_push; 625 625 } else { 626 626 excess -= rem; 627 _excess->set(v, (*_excess)[v] + rem);628 _flow->set(a, (*_capacity)[a]);627 (*_excess)[v] += rem; 628 (*_flow)[a] = (*_capacity)[a]; 629 629 } 630 630 } else if (next_bucket > (*_bucket)[v]) { … … 643 643 } 644 644 if (!_tolerance.less(rem, excess)) { 645 _flow->set(a, (*_flow)[a] - excess);646 _excess->set(v, (*_excess)[v] + excess);645 (*_flow)[a] -= excess; 646 (*_excess)[v] += excess; 647 647 excess = 0; 648 648 goto no_more_push; 649 649 } else { 650 650 excess -= rem; 651 _excess->set(v, (*_excess)[v] + rem);652 _flow->set(a, 0);651 (*_excess)[v] += rem; 652 (*_flow)[a] = 0; 653 653 } 654 654 } else if (next_bucket > (*_bucket)[v]) { … … 659 659 no_more_push: 660 660 661 _excess->set(n, excess);661 (*_excess)[n] = excess; 662 662 663 663 if (excess != 0) { … … 677 677 } else if (next_bucket == _node_num) { 678 678 _first[(*_bucket)[n]] = (*_next)[n]; 679 _prev->set((*_next)[n], INVALID);679 (*_prev)[(*_next)[n]] = INVALID; 680 680 681 681 std::list<std::list<int> >::iterator new_set = … … 683 683 684 684 new_set->push_front(bucket_num); 685 _bucket->set(n, bucket_num);685 (*_bucket)[n] = bucket_num; 686 686 _first[bucket_num] = _last[bucket_num] = n; 687 _next->set(n, INVALID);688 _prev->set(n, INVALID);687 (*_next)[n] = INVALID; 688 (*_prev)[n] = INVALID; 689 689 _dormant[bucket_num] = true; 690 690 ++bucket_num; … … 696 696 } else { 697 697 _first[*_highest] = (*_next)[n]; 698 _prev->set((*_next)[n], INVALID);698 (*_prev)[(*_next)[n]] = INVALID; 699 699 700 700 while (next_bucket != *_highest) { … … 709 709 --_highest; 710 710 711 _bucket->set(n, *_highest);712 _next->set(n, _first[*_highest]);711 (*_bucket)[n] = *_highest; 712 (*_next)[n] = _first[*_highest]; 713 713 if (_first[*_highest] != INVALID) { 714 _prev->set(_first[*_highest], n);714 (*_prev)[_first[*_highest]] = n; 715 715 } else { 716 716 _last[*_highest] = n; … … 734 734 _min_cut = (*_excess)[target]; 735 735 for (NodeIt i(_graph); i != INVALID; ++i) { 736 _min_cut_map->set(i, false);736 (*_min_cut_map)[i] = false; 737 737 } 738 738 for (std::list<int>::iterator it = _sets.back().begin(); … … 740 740 Node n = _first[*it]; 741 741 while (n != INVALID) { 742 _min_cut_map->set(n, true);742 (*_min_cut_map)[n] = true; 743 743 n = (*_next)[n]; 744 744 } … … 753 753 new_target = (*_prev)[target]; 754 754 } else { 755 _prev->set((*_next)[target], (*_prev)[target]);755 (*_prev)[(*_next)[target]] = (*_prev)[target]; 756 756 new_target = (*_next)[target]; 757 757 } … … 759 759 _first[(*_bucket)[target]] = (*_next)[target]; 760 760 } else { 761 _next->set((*_prev)[target], (*_next)[target]);761 (*_next)[(*_prev)[target]] = (*_next)[target]; 762 762 } 763 763 } else { … … 775 775 } 776 776 777 _bucket->set(target, 0);778 779 _source_set->set(target, true);777 (*_bucket)[target] = 0; 778 779 (*_source_set)[target] = true; 780 780 for (InArcIt a(_graph, target); a != INVALID; ++a) { 781 781 Value rem = (*_capacity)[a] - (*_flow)[a]; … … 785 785 activate(v); 786 786 } 787 _excess->set(v, (*_excess)[v] + rem);788 _flow->set(a, (*_capacity)[a]);787 (*_excess)[v] += rem; 788 (*_flow)[a] = (*_capacity)[a]; 789 789 } 790 790 … … 796 796 activate(v); 797 797 } 798 _excess->set(v, (*_excess)[v] + rem);799 _flow->set(a, 0);798 (*_excess)[v] += rem; 799 (*_flow)[a] = 0; 800 800 } 801 801 -
lemon/hypercube_graph.h
r559 r582 293 293 /// 294 294 /// This graph type fully conforms to the \ref concepts::Graph 295 /// "Graph" concept, and it also has an important extra feature 296 /// that its maps are real \ref concepts::ReferenceMap 297 /// "reference map"s. 295 /// "Graph concept". 298 296 class HypercubeGraph : public ExtendedHypercubeGraphBase { 299 297 public: -
lemon/list_graph.h
r559 r582 321 321 ///only in the concept class. 322 322 /// 323 ///An important extra feature of this digraph implementation is that324 ///its maps are real \ref concepts::ReferenceMap "reference map"s.325 ///326 323 ///\sa concepts::Digraph 327 324 … … 1177 1174 ///only in the concept class. 1178 1175 /// 1179 ///An important extra feature of this graph implementation is that1180 ///its maps are real \ref concepts::ReferenceMap "reference map"s.1181 ///1182 1176 ///\sa concepts::Graph 1183 1177 -
lemon/max_matching.h
r559 r581 283 283 284 284 while (base != nca) { 285 _ear->set(node, arc);285 (*_ear)[node] = arc; 286 286 287 287 Node n = node; … … 290 290 Arc a = (*_ear)[n]; 291 291 n = _graph.target(a); 292 _ear->set(n, _graph.oppositeArc(a));292 (*_ear)[n] = _graph.oppositeArc(a); 293 293 } 294 294 node = _graph.target((*_matching)[base]); … … 296 296 _tree_set->erase(node); 297 297 _blossom_set->insert(node, _blossom_set->find(base)); 298 _status->set(node, EVEN);298 (*_status)[node] = EVEN; 299 299 _node_queue[_last++] = node; 300 300 arc = _graph.oppositeArc((*_ear)[node]); … … 305 305 } 306 306 307 _blossom_rep->set(_blossom_set->find(nca), nca);307 (*_blossom_rep)[_blossom_set->find(nca)] = nca; 308 308 309 309 { … … 314 314 315 315 while (base != nca) { 316 _ear->set(node, arc);316 (*_ear)[node] = arc; 317 317 318 318 Node n = node; … … 321 321 Arc a = (*_ear)[n]; 322 322 n = _graph.target(a); 323 _ear->set(n, _graph.oppositeArc(a));323 (*_ear)[n] = _graph.oppositeArc(a); 324 324 } 325 325 node = _graph.target((*_matching)[base]); … … 327 327 _tree_set->erase(node); 328 328 _blossom_set->insert(node, _blossom_set->find(base)); 329 _status->set(node, EVEN);329 (*_status)[node] = EVEN; 330 330 _node_queue[_last++] = node; 331 331 arc = _graph.oppositeArc((*_ear)[node]); … … 336 336 } 337 337 338 _blossom_rep->set(_blossom_set->find(nca), nca);338 (*_blossom_rep)[_blossom_set->find(nca)] = nca; 339 339 } 340 340 … … 345 345 Node odd = _graph.target(a); 346 346 347 _ear->set(odd, _graph.oppositeArc(a));347 (*_ear)[odd] = _graph.oppositeArc(a); 348 348 Node even = _graph.target((*_matching)[odd]); 349 _blossom_rep->set(_blossom_set->insert(even), even);350 _status->set(odd, ODD);351 _status->set(even, EVEN);349 (*_blossom_rep)[_blossom_set->insert(even)] = even; 350 (*_status)[odd] = ODD; 351 (*_status)[even] = EVEN; 352 352 int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]); 353 353 _tree_set->insert(odd, tree); … … 363 363 int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]); 364 364 365 _matching->set(odd, _graph.oppositeArc(a));366 _status->set(odd, MATCHED);365 (*_matching)[odd] = _graph.oppositeArc(a); 366 (*_status)[odd] = MATCHED; 367 367 368 368 Arc arc = (*_matching)[even]; 369 _matching->set(even, a);369 (*_matching)[even] = a; 370 370 371 371 while (arc != INVALID) { … … 373 373 arc = (*_ear)[odd]; 374 374 even = _graph.target(arc); 375 _matching->set(odd, arc);375 (*_matching)[odd] = arc; 376 376 arc = (*_matching)[even]; 377 _matching->set(even, _graph.oppositeArc((*_matching)[odd]));377 (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]); 378 378 } 379 379 … … 381 381 it != INVALID; ++it) { 382 382 if ((*_status)[it] == ODD) { 383 _status->set(it, MATCHED);383 (*_status)[it] = MATCHED; 384 384 } else { 385 385 int blossom = _blossom_set->find(it); 386 386 for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom); 387 387 jt != INVALID; ++jt) { 388 _status->set(jt, MATCHED);388 (*_status)[jt] = MATCHED; 389 389 } 390 390 _blossom_set->eraseClass(blossom); … … 428 428 createStructures(); 429 429 for(NodeIt n(_graph); n != INVALID; ++n) { 430 _matching->set(n, INVALID);431 _status->set(n, UNMATCHED);430 (*_matching)[n] = INVALID; 431 (*_status)[n] = UNMATCHED; 432 432 } 433 433 } … … 439 439 createStructures(); 440 440 for (NodeIt n(_graph); n != INVALID; ++n) { 441 _matching->set(n, INVALID);442 _status->set(n, UNMATCHED);441 (*_matching)[n] = INVALID; 442 (*_status)[n] = UNMATCHED; 443 443 } 444 444 for (NodeIt n(_graph); n != INVALID; ++n) { … … 447 447 Node v = _graph.target(a); 448 448 if ((*_matching)[v] == INVALID && v != n) { 449 _matching->set(n, a);450 _status->set(n, MATCHED);451 _matching->set(v, _graph.oppositeArc(a));452 _status->set(v, MATCHED);449 (*_matching)[n] = a; 450 (*_status)[n] = MATCHED; 451 (*_matching)[v] = _graph.oppositeArc(a); 452 (*_status)[v] = MATCHED; 453 453 break; 454 454 } … … 470 470 471 471 for (NodeIt n(_graph); n != INVALID; ++n) { 472 _matching->set(n, INVALID);473 _status->set(n, UNMATCHED);472 (*_matching)[n] = INVALID; 473 (*_status)[n] = UNMATCHED; 474 474 } 475 475 for(EdgeIt e(_graph); e!=INVALID; ++e) { … … 478 478 Node u = _graph.u(e); 479 479 if ((*_matching)[u] != INVALID) return false; 480 _matching->set(u, _graph.direct(e, true));481 _status->set(u, MATCHED);480 (*_matching)[u] = _graph.direct(e, true); 481 (*_status)[u] = MATCHED; 482 482 483 483 Node v = _graph.v(e); 484 484 if ((*_matching)[v] != INVALID) return false; 485 _matching->set(v, _graph.direct(e, false));486 _status->set(v, MATCHED);485 (*_matching)[v] = _graph.direct(e, false); 486 (*_status)[v] = MATCHED; 487 487 } 488 488 } … … 498 498 (*_blossom_rep)[_blossom_set->insert(n)] = n; 499 499 _tree_set->insert(n); 500 _status->set(n, EVEN);500 (*_status)[n] = EVEN; 501 501 processSparse(n); 502 502 } … … 513 513 (*_blossom_rep)[_blossom_set->insert(n)] = n; 514 514 _tree_set->insert(n); 515 _status->set(n, EVEN);515 (*_status)[n] = EVEN; 516 516 processDense(n); 517 517 } … … 1549 1549 Value pot = (*_node_data)[bi].pot; 1550 1550 1551 _matching->set(base, matching);1551 (*_matching)[base] = matching; 1552 1552 _blossom_node_list.push_back(base); 1553 _node_potential->set(base, pot);1553 (*_node_potential)[base] = pot; 1554 1554 } else { 1555 1555 … … 1645 1645 1646 1646 for (ArcIt e(_graph); e != INVALID; ++e) { 1647 _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);1647 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; 1648 1648 } 1649 1649 for (NodeIt n(_graph); n != INVALID; ++n) { 1650 _delta1_index->set(n, _delta1->PRE_HEAP);1650 (*_delta1_index)[n] = _delta1->PRE_HEAP; 1651 1651 } 1652 1652 for (EdgeIt e(_graph); e != INVALID; ++e) { 1653 _delta3_index->set(e, _delta3->PRE_HEAP);1653 (*_delta3_index)[e] = _delta3->PRE_HEAP; 1654 1654 } 1655 1655 for (int i = 0; i < _blossom_num; ++i) { 1656 _delta2_index->set(i, _delta2->PRE_HEAP);1657 _delta4_index->set(i, _delta4->PRE_HEAP);1656 (*_delta2_index)[i] = _delta2->PRE_HEAP; 1657 (*_delta4_index)[i] = _delta4->PRE_HEAP; 1658 1658 } 1659 1659 … … 1667 1667 } 1668 1668 } 1669 _node_index->set(n, index);1669 (*_node_index)[n] = index; 1670 1670 (*_node_data)[index].pot = max; 1671 1671 _delta1->push(n, max); … … 2742 2742 Value pot = (*_node_data)[bi].pot; 2743 2743 2744 _matching->set(base, matching);2744 (*_matching)[base] = matching; 2745 2745 _blossom_node_list.push_back(base); 2746 _node_potential->set(base, pot);2746 (*_node_potential)[base] = pot; 2747 2747 } else { 2748 2748 … … 2832 2832 2833 2833 for (ArcIt e(_graph); e != INVALID; ++e) { 2834 _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);2834 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; 2835 2835 } 2836 2836 for (EdgeIt e(_graph); e != INVALID; ++e) { 2837 _delta3_index->set(e, _delta3->PRE_HEAP);2837 (*_delta3_index)[e] = _delta3->PRE_HEAP; 2838 2838 } 2839 2839 for (int i = 0; i < _blossom_num; ++i) { 2840 _delta2_index->set(i, _delta2->PRE_HEAP);2841 _delta4_index->set(i, _delta4->PRE_HEAP);2840 (*_delta2_index)[i] = _delta2->PRE_HEAP; 2841 (*_delta4_index)[i] = _delta4->PRE_HEAP; 2842 2842 } 2843 2843 … … 2851 2851 } 2852 2852 } 2853 _node_index->set(n, index);2853 (*_node_index)[n] = index; 2854 2854 (*_node_data)[index].pot = max; 2855 2855 int blossom = -
lemon/min_cost_arborescence.h
r559 r581 294 294 } 295 295 } 296 _arc_order->set(minimum.arc, _dual_variables.size());296 (*_arc_order)[minimum.arc] = _dual_variables.size(); 297 297 DualVariable var(_dual_node_list.size() - 1, 298 298 _dual_node_list.size(), minimum.value); … … 336 336 } 337 337 } 338 _arc_order->set(minimum.arc, _dual_variables.size());338 (*_arc_order)[minimum.arc] = _dual_variables.size(); 339 339 DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); 340 340 _dual_variables.push_back(var); … … 365 365 Node source = _heap->top(); 366 366 _heap->pop(); 367 _node_order->set(source, -1);367 (*_node_order)[source] = -1; 368 368 for (OutArcIt it(*_digraph, source); it != INVALID; ++it) { 369 369 if ((*_arc_order)[it] < 0) continue; … … 651 651 for (NodeIt it(*_digraph); it != INVALID; ++it) { 652 652 (*_cost_arcs)[it].arc = INVALID; 653 _node_order->set(it, -3);654 _heap_cross_ref->set(it, Heap::PRE_HEAP);653 (*_node_order)[it] = -3; 654 (*_heap_cross_ref)[it] = Heap::PRE_HEAP; 655 655 _pred->set(it, INVALID); 656 656 } 657 657 for (ArcIt it(*_digraph); it != INVALID; ++it) { 658 658 _arborescence->set(it, false); 659 _arc_order->set(it, -1);659 (*_arc_order)[it] = -1; 660 660 } 661 661 _dual_node_list.clear(); -
lemon/preflow.h
r559 r581 405 405 _phase = true; 406 406 for (NodeIt n(_graph); n != INVALID; ++n) { 407 _excess->set(n, 0);407 (*_excess)[n] = 0; 408 408 } 409 409 … … 418 418 419 419 std::vector<Node> queue; 420 reached .set(_source, true);420 reached[_source] = true; 421 421 422 422 queue.push_back(_target); 423 reached .set(_target, true);423 reached[_target] = true; 424 424 while (!queue.empty()) { 425 425 _level->initNewLevel(); … … 430 430 Node u = _graph.source(e); 431 431 if (!reached[u] && _tolerance.positive((*_capacity)[e])) { 432 reached .set(u, true);432 reached[u] = true; 433 433 _level->initAddItem(u); 434 434 nqueue.push_back(u); … … 445 445 if ((*_level)[u] == _level->maxLevel()) continue; 446 446 _flow->set(e, (*_capacity)[e]); 447 _excess->set(u, (*_excess)[u] + (*_capacity)[e]);447 (*_excess)[u] += (*_capacity)[e]; 448 448 if (u != _target && !_level->active(u)) { 449 449 _level->activate(u); … … 479 479 } 480 480 if (excess < 0 && n != _source) return false; 481 _excess->set(n, excess);481 (*_excess)[n] = excess; 482 482 } 483 483 … … 488 488 489 489 std::vector<Node> queue; 490 reached .set(_source, true);490 reached[_source] = true; 491 491 492 492 queue.push_back(_target); 493 reached .set(_target, true);493 reached[_target] = true; 494 494 while (!queue.empty()) { 495 495 _level->initNewLevel(); … … 501 501 if (!reached[u] && 502 502 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { 503 reached .set(u, true);503 reached[u] = true; 504 504 _level->initAddItem(u); 505 505 nqueue.push_back(u); … … 509 509 Node v = _graph.target(e); 510 510 if (!reached[v] && _tolerance.positive((*_flow)[e])) { 511 reached .set(v, true);511 reached[v] = true; 512 512 _level->initAddItem(v); 513 513 nqueue.push_back(v); … … 525 525 if ((*_level)[u] == _level->maxLevel()) continue; 526 526 _flow->set(e, (*_capacity)[e]); 527 _excess->set(u, (*_excess)[u] + rem);527 (*_excess)[u] += rem; 528 528 if (u != _target && !_level->active(u)) { 529 529 _level->activate(u); … … 537 537 if ((*_level)[v] == _level->maxLevel()) continue; 538 538 _flow->set(e, 0); 539 _excess->set(v, (*_excess)[v] + rem);539 (*_excess)[v] += rem; 540 540 if (v != _target && !_level->active(v)) { 541 541 _level->activate(v); … … 578 578 if (!_tolerance.less(rem, excess)) { 579 579 _flow->set(e, (*_flow)[e] + excess); 580 _excess->set(v, (*_excess)[v] + excess);580 (*_excess)[v] += excess; 581 581 excess = 0; 582 582 goto no_more_push_1; 583 583 } else { 584 584 excess -= rem; 585 _excess->set(v, (*_excess)[v] + rem);585 (*_excess)[v] += rem; 586 586 _flow->set(e, (*_capacity)[e]); 587 587 } … … 601 601 if (!_tolerance.less(rem, excess)) { 602 602 _flow->set(e, (*_flow)[e] - excess); 603 _excess->set(v, (*_excess)[v] + excess);603 (*_excess)[v] += excess; 604 604 excess = 0; 605 605 goto no_more_push_1; 606 606 } else { 607 607 excess -= rem; 608 _excess->set(v, (*_excess)[v] + rem);608 (*_excess)[v] += rem; 609 609 _flow->set(e, 0); 610 610 } … … 616 616 no_more_push_1: 617 617 618 _excess->set(n, excess);618 (*_excess)[n] = excess; 619 619 620 620 if (excess != 0) { … … 651 651 if (!_tolerance.less(rem, excess)) { 652 652 _flow->set(e, (*_flow)[e] + excess); 653 _excess->set(v, (*_excess)[v] + excess);653 (*_excess)[v] += excess; 654 654 excess = 0; 655 655 goto no_more_push_2; 656 656 } else { 657 657 excess -= rem; 658 _excess->set(v, (*_excess)[v] + rem);658 (*_excess)[v] += rem; 659 659 _flow->set(e, (*_capacity)[e]); 660 660 } … … 674 674 if (!_tolerance.less(rem, excess)) { 675 675 _flow->set(e, (*_flow)[e] - excess); 676 _excess->set(v, (*_excess)[v] + excess);676 (*_excess)[v] += excess; 677 677 excess = 0; 678 678 goto no_more_push_2; 679 679 } else { 680 680 excess -= rem; 681 _excess->set(v, (*_excess)[v] + rem);681 (*_excess)[v] += rem; 682 682 _flow->set(e, 0); 683 683 } … … 689 689 no_more_push_2: 690 690 691 _excess->set(n, excess);691 (*_excess)[n] = excess; 692 692 693 693 if (excess != 0) { … … 732 732 typename Digraph::template NodeMap<bool> reached(_graph); 733 733 for (NodeIt n(_graph); n != INVALID; ++n) { 734 reached .set(n, (*_level)[n] < _level->maxLevel());734 reached[n] = (*_level)[n] < _level->maxLevel(); 735 735 } 736 736 … … 740 740 std::vector<Node> queue; 741 741 queue.push_back(_source); 742 reached .set(_source, true);742 reached[_source] = true; 743 743 744 744 while (!queue.empty()) { … … 750 750 Node v = _graph.target(e); 751 751 if (!reached[v] && _tolerance.positive((*_flow)[e])) { 752 reached .set(v, true);752 reached[v] = true; 753 753 _level->initAddItem(v); 754 754 nqueue.push_back(v); … … 759 759 if (!reached[u] && 760 760 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { 761 reached .set(u, true);761 reached[u] = true; 762 762 _level->initAddItem(u); 763 763 nqueue.push_back(u); … … 793 793 if (!_tolerance.less(rem, excess)) { 794 794 _flow->set(e, (*_flow)[e] + excess); 795 _excess->set(v, (*_excess)[v] + excess);795 (*_excess)[v] += excess; 796 796 excess = 0; 797 797 goto no_more_push; 798 798 } else { 799 799 excess -= rem; 800 _excess->set(v, (*_excess)[v] + rem);800 (*_excess)[v] += rem; 801 801 _flow->set(e, (*_capacity)[e]); 802 802 } … … 816 816 if (!_tolerance.less(rem, excess)) { 817 817 _flow->set(e, (*_flow)[e] - excess); 818 _excess->set(v, (*_excess)[v] + excess);818 (*_excess)[v] += excess; 819 819 excess = 0; 820 820 goto no_more_push; 821 821 } else { 822 822 excess -= rem; 823 _excess->set(v, (*_excess)[v] + rem);823 (*_excess)[v] += rem; 824 824 _flow->set(e, 0); 825 825 } … … 831 831 no_more_push: 832 832 833 _excess->set(n, excess);833 (*_excess)[n] = excess; 834 834 835 835 if (excess != 0) { -
lemon/smart_graph.h
r559 r582 192 192 ///that <b> it does support only limited (only stack-like) 193 193 ///node and arc deletions</b>. 194 ///It conforms to the \ref concepts::Digraph "Digraph concept" with 195 ///an important extra feature that its maps are real \ref 196 ///concepts::ReferenceMap "reference map"s. 194 ///It fully conforms to the \ref concepts::Digraph "Digraph concept". 197 195 /// 198 196 ///\sa concepts::Digraph. … … 630 628 /// that <b> it does support only limited (only stack-like) 631 629 /// node and arc deletions</b>. 632 /// Except from this it conforms to 633 /// the \ref concepts::Graph "Graph concept". 634 /// 635 /// It also has an 636 /// important extra feature that 637 /// its maps are real \ref concepts::ReferenceMap "reference map"s. 630 /// It fully conforms to the \ref concepts::Graph "Graph concept". 638 631 /// 639 632 /// \sa concepts::Graph. 640 ///641 633 class SmartGraph : public ExtendedSmartGraphBase { 642 634 private: -
test/kruskal_test.cc
r440 r581 100 100 "Total cost should be 10"); 101 101 102 edge_cost_map .set(e1, -10);103 edge_cost_map .set(e2, -9);104 edge_cost_map .set(e3, -8);105 edge_cost_map .set(e4, -7);106 edge_cost_map .set(e5, -6);107 edge_cost_map .set(e6, -5);108 edge_cost_map .set(e7, -4);109 edge_cost_map .set(e8, -3);110 edge_cost_map .set(e9, -2);111 edge_cost_map .set(e10, -1);102 edge_cost_map[e1] = -10; 103 edge_cost_map[e2] = -9; 104 edge_cost_map[e3] = -8; 105 edge_cost_map[e4] = -7; 106 edge_cost_map[e5] = -6; 107 edge_cost_map[e6] = -5; 108 edge_cost_map[e7] = -4; 109 edge_cost_map[e8] = -3; 110 edge_cost_map[e9] = -2; 111 edge_cost_map[e10] = -1; 112 112 113 113 vector<Edge> tree_edge_vec(5);
Note: See TracChangeset
for help on using the changeset viewer.