Changes in / [1343:20f95cd51aba:1341:c199e9976d93] in lemon
- Files:
-
- 1 deleted
- 28 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r1343 r1340 4 4 CMAKE_POLICY(SET CMP0048 OLD) 5 5 ENDIF(POLICY CMP0048) 6 7 IF(POLICY CMP0043)8 CMAKE_POLICY(SET CMP0043 OLD)9 ENDIF(POLICY CMP0043)10 6 11 7 SET(PROJECT_NAME "LEMON") … … 234 230 FORCE ) 235 231 236 SET_DIRECTORY_PROPERTIES(PROPERTIES237 COMPILE_DEFINITIONS_DEBUG "LEMON_ENABLE_DEBUG"238 COMPILE_DEFINITIONS_MAINTAINER "LEMON_ENABLE_DEBUG"239 )240 232 241 233 INCLUDE(CheckTypeSize) … … 266 258 267 259 ENABLE_TESTING() 268 269 270 INCLUDE(CheckCXXCompilerFlag)271 CHECK_CXX_COMPILER_FLAG("-std=c++11" LEMON_CXX11)272 IF(LEMON_CXX11)273 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")274 ENDIF()275 276 260 277 261 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") -
lemon/bellman_ford.h
r1337 r1270 30 30 #include <lemon/maps.h> 31 31 #include <lemon/path.h> 32 #include <lemon/bits/stl_iterators.h>33 32 34 33 #include <limits> … … 691 690 int _index; 692 691 }; 693 694 /// \brief Gets the collection of the active nodes.695 ///696 /// This function can be used for iterating on the active nodes of the697 /// Bellman-Ford algorithm after the last phase.698 /// These nodes should be checked in the next phase to699 /// find augmenting arcs outgoing from them.700 /// It returns a wrapped ActiveIt, which looks701 /// like an STL container (by having begin() and end())702 /// which you can use in range-based for loops, STL algorithms, etc.703 LemonRangeWrapper1<ActiveIt, BellmanFord>704 activeNodes() const {705 return LemonRangeWrapper1<ActiveIt, BellmanFord>(*this);706 }707 708 692 709 693 /// \name Query Functions -
lemon/bits/edge_set_extender.h
r1337 r1270 114 114 }; 115 115 116 LemonRangeWrapper1<NodeIt, Digraph> nodes() const {117 return LemonRangeWrapper1<NodeIt, Digraph>(*this);118 }119 116 120 117 class ArcIt : public Arc { … … 140 137 }; 141 138 142 LemonRangeWrapper1<ArcIt, Digraph> arcs() const {143 return LemonRangeWrapper1<ArcIt, Digraph>(*this);144 }145 139 146 140 class OutArcIt : public Arc { … … 167 161 }; 168 162 169 LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {170 return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);171 }172 163 173 164 class InArcIt : public Arc { … … 193 184 194 185 }; 195 196 LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {197 return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);198 }199 186 200 187 // \brief Base node of the iterator … … 386 373 }; 387 374 388 LemonRangeWrapper1<NodeIt, Graph> nodes() const {389 return LemonRangeWrapper1<NodeIt, Graph>(*this);390 }391 375 392 376 class ArcIt : public Arc { … … 412 396 }; 413 397 414 LemonRangeWrapper1<ArcIt, Graph> arcs() const {415 return LemonRangeWrapper1<ArcIt, Graph>(*this);416 }417 398 418 399 class OutArcIt : public Arc { … … 439 420 }; 440 421 441 LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {442 return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);443 }444 422 445 423 class InArcIt : public Arc { … … 466 444 }; 467 445 468 LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {469 return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);470 }471 446 472 447 class EdgeIt : public Parent::Edge { … … 491 466 492 467 }; 493 494 LemonRangeWrapper1<EdgeIt, Graph> edges() const {495 return LemonRangeWrapper1<EdgeIt, Graph>(*this);496 }497 468 498 469 class IncEdgeIt : public Parent::Edge { … … 520 491 } 521 492 }; 522 523 LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {524 return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);525 }526 493 527 494 // \brief Base node of the iterator -
lemon/bits/graph_adaptor_extender.h
r1337 r1270 86 86 }; 87 87 88 LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {89 return LemonRangeWrapper1<NodeIt, Adaptor>(*this);90 }91 88 92 89 class ArcIt : public Arc { … … 111 108 112 109 }; 113 114 LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {115 return LemonRangeWrapper1<ArcIt, Adaptor>(*this);116 }117 110 118 111 … … 140 133 }; 141 134 142 LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {143 return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);144 }145 146 135 147 136 class InArcIt : public Arc { … … 167 156 168 157 }; 169 170 LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {171 return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);172 }173 158 174 159 Node baseNode(const OutArcIt &e) const { … … 270 255 }; 271 256 272 LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {273 return LemonRangeWrapper1<NodeIt, Adaptor>(*this);274 }275 276 257 277 258 class ArcIt : public Arc { … … 296 277 297 278 }; 298 299 LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {300 return LemonRangeWrapper1<ArcIt, Adaptor>(*this);301 }302 279 303 280 … … 325 302 }; 326 303 327 LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {328 return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);329 }330 331 304 332 305 class InArcIt : public Arc { … … 353 326 }; 354 327 355 LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {356 return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);357 }358 359 328 class EdgeIt : public Parent::Edge { 360 329 const Adaptor* _adaptor; … … 378 347 379 348 }; 380 381 LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {382 return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);383 }384 385 349 386 350 class IncEdgeIt : public Edge { … … 409 373 }; 410 374 411 LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {412 return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);413 }414 415 416 375 Node baseNode(const OutArcIt &a) const { 417 376 return Parent::source(a); -
lemon/bits/graph_extender.h
r1336 r1270 28 28 #include <lemon/concepts/maps.h> 29 29 30 #include <lemon/bits/stl_iterators.h>31 32 30 //\ingroup graphbits 33 31 //\file … … 119 117 }; 120 118 121 LemonRangeWrapper1<NodeIt, Digraph> nodes() const {122 return LemonRangeWrapper1<NodeIt, Digraph>(*this);123 }124 125 119 126 120 class ArcIt : public Arc { … … 145 139 146 140 }; 147 148 LemonRangeWrapper1<ArcIt, Digraph> arcs() const {149 return LemonRangeWrapper1<ArcIt, Digraph>(*this);150 }151 141 152 142 … … 174 164 }; 175 165 176 LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {177 return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);178 }179 180 166 181 167 class InArcIt : public Arc { … … 201 187 202 188 }; 203 204 LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {205 return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);206 }207 189 208 190 // \brief Base node of the iterator … … 455 437 }; 456 438 457 LemonRangeWrapper1<NodeIt, Graph> nodes() const {458 return LemonRangeWrapper1<NodeIt, Graph>(*this);459 }460 461 439 462 440 class ArcIt : public Arc { … … 481 459 482 460 }; 483 484 LemonRangeWrapper1<ArcIt, Graph> arcs() const {485 return LemonRangeWrapper1<ArcIt, Graph>(*this);486 }487 461 488 462 … … 510 484 }; 511 485 512 LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {513 return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);514 }515 516 486 517 487 class InArcIt : public Arc { … … 538 508 }; 539 509 540 LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {541 return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);542 }543 544 510 545 511 class EdgeIt : public Parent::Edge { … … 564 530 565 531 }; 566 567 LemonRangeWrapper1<EdgeIt, Graph> edges() const {568 return LemonRangeWrapper1<EdgeIt, Graph>(*this);569 }570 571 532 572 533 class IncEdgeIt : public Parent::Edge { … … 594 555 } 595 556 }; 596 597 LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {598 return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);599 }600 601 557 602 558 // \brief Base node of the iterator … … 948 904 }; 949 905 950 LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {951 return LemonRangeWrapper1<NodeIt, BpGraph>(*this);952 }953 954 955 906 class RedNodeIt : public RedNode { 956 907 const BpGraph* _graph; … … 975 926 }; 976 927 977 LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {978 return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);979 }980 981 982 928 class BlueNodeIt : public BlueNode { 983 929 const BpGraph* _graph; … … 1002 948 }; 1003 949 1004 LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {1005 return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);1006 }1007 1008 1009 950 1010 951 class ArcIt : public Arc { … … 1029 970 1030 971 }; 1031 1032 LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {1033 return LemonRangeWrapper1<ArcIt, BpGraph>(*this);1034 }1035 972 1036 973 … … 1058 995 }; 1059 996 1060 LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {1061 return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);1062 }1063 1064 997 1065 998 class InArcIt : public Arc { … … 1086 1019 }; 1087 1020 1088 LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {1089 return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);1090 }1091 1092 1021 1093 1022 class EdgeIt : public Parent::Edge { … … 1112 1041 1113 1042 }; 1114 1115 LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {1116 return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);1117 }1118 1119 1043 1120 1044 class IncEdgeIt : public Parent::Edge { … … 1142 1066 } 1143 1067 }; 1144 1145 LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {1146 return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);1147 }1148 1149 1068 1150 1069 // \brief Base node of the iterator -
lemon/bits/path_dump.h
r1338 r1270 62 62 } 63 63 64 operator typename Digraph::Arc() const {64 operator const typename Digraph::Arc() const { 65 65 return path->predMap[current]; 66 66 } -
lemon/cbc.cc
r1336 r1270 112 112 113 113 void CbcMip::_eraseColId(int i) { 114 _cols.eraseIndex(i);114 cols.eraseIndex(i); 115 115 } 116 116 117 117 void CbcMip::_eraseRowId(int i) { 118 _rows.eraseIndex(i);118 rows.eraseIndex(i); 119 119 } 120 120 -
lemon/clp.cc
r1336 r1270 30 30 ClpLp::ClpLp(const ClpLp& other) { 31 31 _prob = new ClpSimplex(*other._prob); 32 _rows = other._rows;33 _cols = other._cols;32 rows = other.rows; 33 cols = other.cols; 34 34 _init_temporals(); 35 35 messageLevel(MESSAGE_NOTHING); … … 104 104 105 105 void ClpLp::_eraseColId(int i) { 106 _cols.eraseIndex(i);107 _cols.shiftIndices(i);106 cols.eraseIndex(i); 107 cols.shiftIndices(i); 108 108 } 109 109 110 110 void ClpLp::_eraseRowId(int i) { 111 _rows.eraseIndex(i);112 _rows.shiftIndices(i);111 rows.eraseIndex(i); 112 rows.shiftIndices(i); 113 113 } 114 114 -
lemon/clp.h
r1336 r1270 152 152 153 153 ///Returns the constraint identifier understood by CLP. 154 int clpRow(Row r) const { return _rows(id(r)); }154 int clpRow(Row r) const { return rows(id(r)); } 155 155 156 156 ///Returns the variable identifier understood by CLP. 157 int clpCol(Col c) const { return _cols(id(c)); }157 int clpCol(Col c) const { return cols(id(c)); } 158 158 159 159 }; -
lemon/concepts/bpgraph.h
r1336 r1270 28 28 #include <lemon/concept_check.h> 29 29 #include <lemon/core.h> 30 #include <lemon/bits/stl_iterators.h>31 30 32 31 namespace lemon { … … 223 222 }; 224 223 225 /// \brief Gets the collection of the red nodes of the graph.226 ///227 /// This function can be used for iterating on228 /// the red nodes of the graph. It returns a wrapped RedNodeIt,229 /// which looks like an STL container (by having begin() and end())230 /// which you can use in range-based for loops, stl algorithms, etc.231 /// For example if g is a BpGraph, you can write:232 ///\code233 /// for(auto v: g.redNodes())234 /// doSomething(v);235 ///\endcode236 LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {237 return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);238 }239 240 241 224 /// Iterator class for the blue nodes. 242 225 … … 282 265 }; 283 266 284 /// \brief Gets the collection of the blue nodes of the graph.285 ///286 /// This function can be used for iterating on287 /// the blue nodes of the graph. It returns a wrapped BlueNodeIt,288 /// which looks like an STL container (by having begin() and end())289 /// which you can use in range-based for loops, stl algorithms, etc.290 /// For example if g is a BpGraph, you can write:291 ///\code292 /// for(auto v: g.blueNodes())293 /// doSomething(v);294 ///\endcode295 LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {296 return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);297 }298 299 300 267 /// Iterator class for the nodes. 301 268 … … 341 308 }; 342 309 343 /// \brief Gets the collection of the nodes of the graph.344 ///345 /// This function can be used for iterating on346 /// the nodes of the graph. It returns a wrapped NodeIt,347 /// which looks like an STL container (by having begin() and end())348 /// which you can use in range-based for loops, stl algorithms, etc.349 /// For example if g is a BpGraph, you can write:350 ///\code351 /// for(auto v: g.nodes())352 /// doSomething(v);353 ///\endcode354 LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {355 return LemonRangeWrapper1<NodeIt, BpGraph>(*this);356 }357 358 359 310 360 311 /// The edge type of the graph … … 445 396 }; 446 397 447 /// \brief Gets the collection of the edges of the graph.448 ///449 /// This function can be used for iterating on the450 /// edges of the graph. It returns a wrapped451 /// EdgeIt, which looks like an STL container452 /// (by having begin() and end()) which you can use in range-based453 /// for loops, stl algorithms, etc.454 /// For example if g is a BpGraph, you can write:455 ///\code456 /// for(auto e: g.edges())457 /// doSomething(e);458 ///\endcode459 LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {460 return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);461 }462 463 464 398 /// Iterator class for the incident edges of a node. 465 399 … … 509 443 IncEdgeIt& operator++() { return *this; } 510 444 }; 511 512 /// \brief Gets the collection of the incident edges513 /// of a certain node of the graph.514 ///515 /// This function can be used for iterating on the516 /// incident undirected edges of a certain node of the graph.517 /// It returns a wrapped518 /// IncEdgeIt, which looks like an STL container519 /// (by having begin() and end()) which you can use in range-based520 /// for loops, stl algorithms, etc.521 /// For example if g is a BpGraph and u is a Node, you can write:522 ///\code523 /// for(auto e: g.incEdges(u))524 /// doSomething(e);525 ///\endcode526 LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {527 return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);528 }529 530 445 531 446 /// The arc type of the graph … … 624 539 ArcIt& operator++() { return *this; } 625 540 }; 626 627 /// \brief Gets the collection of the directed arcs of the graph.628 ///629 /// This function can be used for iterating on the630 /// arcs of the graph. It returns a wrapped631 /// ArcIt, which looks like an STL container632 /// (by having begin() and end()) which you can use in range-based633 /// for loops, stl algorithms, etc.634 /// For example if g is a BpGraph you can write:635 ///\code636 /// for(auto a: g.arcs())637 /// doSomething(a);638 ///\endcode639 LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {640 return LemonRangeWrapper1<ArcIt, BpGraph>(*this);641 }642 643 541 644 542 /// Iterator class for the outgoing arcs of a node. … … 690 588 }; 691 589 692 /// \brief Gets the collection of the outgoing directed arcs of a693 /// certain node of the graph.694 ///695 /// This function can be used for iterating on the696 /// outgoing arcs of a certain node of the graph. It returns a wrapped697 /// OutArcIt, which looks like an STL container698 /// (by having begin() and end()) which you can use in range-based699 /// for loops, stl algorithms, etc.700 /// For example if g is a BpGraph and u is a Node, you can write:701 ///\code702 /// for(auto a: g.outArcs(u))703 /// doSomething(a);704 ///\endcode705 LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {706 return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);707 }708 709 710 590 /// Iterator class for the incoming arcs of a node. 711 591 … … 756 636 }; 757 637 758 /// \brief Gets the collection of the incoming directed arcs of a759 /// certain node of the graph.760 ///761 /// This function can be used for iterating on the762 /// incoming arcs of a certain node of the graph. It returns a wrapped763 /// InArcIt, which looks like an STL container764 /// (by having begin() and end()) which you can use in range-based765 /// for loops, stl algorithms, etc.766 /// For example if g is a BpGraph and u is a Node, you can write:767 ///\code768 /// for(auto a: g.inArcs(u))769 /// doSomething(a);770 ///\endcode771 LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {772 return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);773 }774 775 776 638 /// \brief Standard graph map type for the nodes. 777 639 /// -
lemon/concepts/digraph.h
r1336 r1271 28 28 #include <lemon/concept_check.h> 29 29 #include <lemon/concepts/graph_components.h> 30 #include <lemon/bits/stl_iterators.h>31 30 32 31 namespace lemon { … … 149 148 }; 150 149 151 /// \brief Gets the collection of the nodes of the digraph.152 ///153 /// This function can be used for iterating on154 /// the nodes of the digraph. It returns a wrapped NodeIt, which looks155 /// like an STL container (by having begin() and end())156 /// which you can use in range-based for loops, STL algorithms, etc.157 /// For example you can write:158 ///\code159 /// ListDigraph g;160 /// for(auto v: g.nodes())161 /// doSomething(v);162 ///163 /// //Using an STL algorithm:164 /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());165 ///\endcode166 LemonRangeWrapper1<NodeIt, Digraph> nodes() const {167 return LemonRangeWrapper1<NodeIt, Digraph>(*this);168 }169 170 150 171 151 /// The arc type of the digraph … … 258 238 }; 259 239 260 /// \brief Gets the collection of the outgoing arcs of a certain node261 /// of the digraph.262 ///263 /// This function can be used for iterating on the264 /// outgoing arcs of a certain node of the digraph. It returns a wrapped265 /// OutArcIt, which looks like an STL container266 /// (by having begin() and end()) which you can use in range-based267 /// for loops, STL algorithms, etc.268 /// For example if g is a Digraph and u is a node, you can write:269 ///\code270 /// for(auto a: g.outArcs(u))271 /// doSomething(a);272 ///273 /// //Using an STL algorithm:274 /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());275 ///\endcode276 LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {277 return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);278 }279 280 281 240 /// Iterator class for the incoming arcs of a node. 282 241 … … 324 283 }; 325 284 326 /// \brief Gets the collection of the incoming arcs of a certain node327 /// of the digraph.328 ///329 /// This function can be used for iterating on the330 /// incoming arcs of a certain node of the digraph. It returns a wrapped331 /// InArcIt, which looks like an STL container332 /// (by having begin() and end()) which you can use in range-based333 /// for loops, STL algorithms, etc.334 /// For example if g is a Digraph and u is a node, you can write:335 ///\code336 /// for(auto a: g.inArcs(u))337 /// doSomething(a);338 ///339 /// //Using an STL algorithm:340 /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());341 ///\endcode342 LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {343 return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);344 }345 346 347 285 /// Iterator class for the arcs. 348 286 … … 389 327 ArcIt& operator++() { return *this; } 390 328 }; 391 392 /// \brief Gets the collection of the arcs of the digraph.393 ///394 /// This function can be used for iterating on the395 /// arcs of the digraph. It returns a wrapped396 /// ArcIt, which looks like an STL container397 /// (by having begin() and end()) which you can use in range-based398 /// for loops, STL algorithms, etc.399 /// For example you can write:400 ///\code401 /// ListDigraph g;402 /// for(auto a: g.arcs())403 /// doSomething(a);404 ///405 /// //Using an STL algorithm:406 /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());407 ///\endcode408 LemonRangeWrapper1<ArcIt, Digraph> arcs() const {409 return LemonRangeWrapper1<ArcIt, Digraph>(*this);410 }411 412 329 413 330 /// \brief The source node of the arc. -
lemon/concepts/graph.h
r1336 r1271 28 28 #include <lemon/concept_check.h> 29 29 #include <lemon/core.h> 30 #include <lemon/bits/stl_iterators.h>31 30 32 31 namespace lemon { … … 182 181 }; 183 182 184 /// \brief Gets the collection of the nodes of the graph.185 ///186 /// This function can be used for iterating on187 /// the nodes of the graph. It returns a wrapped NodeIt, which looks188 /// like an STL container (by having begin() and end())189 /// which you can use in range-based for loops, STL algorithms, etc.190 /// For example you can write:191 ///\code192 /// ListGraph g;193 /// for(auto v: g.nodes())194 /// doSomething(v);195 ///196 /// //Using an STL algorithm:197 /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());198 ///\endcode199 LemonRangeWrapper1<NodeIt, Graph> nodes() const {200 return LemonRangeWrapper1<NodeIt, Graph>(*this);201 }202 203 183 204 184 /// The edge type of the graph … … 289 269 }; 290 270 291 /// \brief Gets the collection of the edges of the graph.292 ///293 /// This function can be used for iterating on the294 /// edges of the graph. It returns a wrapped295 /// EdgeIt, which looks like an STL container296 /// (by having begin() and end()) which you can use in range-based297 /// for loops, STL algorithms, etc.298 /// For example you can write:299 ///\code300 /// ListGraph g;301 /// for(auto e: g.edges())302 /// doSomething(e);303 ///304 /// //Using an STL algorithm:305 /// copy(g.edges().begin(), g.edges().end(), vect.begin());306 ///\endcode307 LemonRangeWrapper1<EdgeIt, Graph> edges() const {308 return LemonRangeWrapper1<EdgeIt, Graph>(*this);309 }310 311 312 271 /// Iterator class for the incident edges of a node. 313 272 … … 357 316 IncEdgeIt& operator++() { return *this; } 358 317 }; 359 360 /// \brief Gets the collection of the incident undirected edges361 /// of a certain node of the graph.362 ///363 /// This function can be used for iterating on the364 /// incident undirected edges of a certain node of the graph.365 /// It returns a wrapped366 /// IncEdgeIt, which looks like an STL container367 /// (by having begin() and end()) which you can use in range-based368 /// for loops, STL algorithms, etc.369 /// For example if g is a Graph and u is a Node, you can write:370 ///\code371 /// for(auto e: g.incEdges(u))372 /// doSomething(e);373 ///374 /// //Using an STL algorithm:375 /// copy(g.incEdges(u).begin(), g.incEdges(u).end(), vect.begin());376 ///\endcode377 LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {378 return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);379 }380 381 318 382 319 /// The arc type of the graph … … 474 411 ArcIt& operator++() { return *this; } 475 412 }; 476 477 /// \brief Gets the collection of the directed arcs of the graph.478 ///479 /// This function can be used for iterating on the480 /// arcs of the graph. It returns a wrapped481 /// ArcIt, which looks like an STL container482 /// (by having begin() and end()) which you can use in range-based483 /// for loops, STL algorithms, etc.484 /// For example you can write:485 ///\code486 /// ListGraph g;487 /// for(auto a: g.arcs())488 /// doSomething(a);489 ///490 /// //Using an STL algorithm:491 /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());492 ///\endcode493 LemonRangeWrapper1<ArcIt, Graph> arcs() const {494 return LemonRangeWrapper1<ArcIt, Graph>(*this);495 }496 497 413 498 414 /// Iterator class for the outgoing arcs of a node. … … 544 460 }; 545 461 546 /// \brief Gets the collection of the outgoing directed arcs of a547 /// certain node of the graph.548 ///549 /// This function can be used for iterating on the550 /// outgoing arcs of a certain node of the graph. It returns a wrapped551 /// OutArcIt, which looks like an STL container552 /// (by having begin() and end()) which you can use in range-based553 /// for loops, STL algorithms, etc.554 /// For example if g is a Graph and u is a Node, you can write:555 ///\code556 /// for(auto a: g.outArcs(u))557 /// doSomething(a);558 ///559 /// //Using an STL algorithm:560 /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());561 ///\endcode562 LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {563 return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);564 }565 566 567 462 /// Iterator class for the incoming arcs of a node. 568 463 … … 613 508 }; 614 509 615 /// \brief Gets the collection of the incoming directed arcs of616 /// a certain node of the graph.617 ///618 /// This function can be used for iterating on the619 /// incoming directed arcs of a certain node of the graph. It returns620 /// a wrapped InArcIt, which looks like an STL container621 /// (by having begin() and end()) which you can use in range-based622 /// for loops, STL algorithms, etc.623 /// For example if g is a Graph and u is a Node, you can write:624 ///\code625 /// for(auto a: g.inArcs(u))626 /// doSomething(a);627 ///628 /// //Using an STL algorithm:629 /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());630 ///\endcode631 LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {632 return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);633 }634 635 510 /// \brief Standard graph map type for the nodes. 636 511 /// -
lemon/concepts/path.h
r1336 r1270 27 27 #include <lemon/core.h> 28 28 #include <lemon/concept_check.h> 29 #include <lemon/bits/stl_iterators.h>30 29 31 30 namespace lemon { … … 117 116 }; 118 117 119 /// \brief Gets the collection of the arcs of the path.120 ///121 /// This function can be used for iterating on the122 /// arcs of the path. It returns a wrapped123 /// ArcIt, which looks like an STL container124 /// (by having begin() and end()) which you can use in range-based125 /// for loops, STL algorithms, etc.126 /// For example you can write:127 ///\code128 /// for(auto a: p.arcs())129 /// doSomething(a);130 ///\endcode131 LemonRangeWrapper1<ArcIt, Path> arcs() const {132 return LemonRangeWrapper1<ArcIt, Path>(*this);133 }134 135 136 118 template <typename _Path> 137 119 struct Constraints { … … 282 264 283 265 }; 284 285 /// \brief Gets the collection of the arcs of the path.286 ///287 /// This function can be used for iterating on the288 /// arcs of the path. It returns a wrapped289 /// ArcIt, which looks like an STL container290 /// (by having begin() and end()) which you can use in range-based291 /// for loops, STL algorithms, etc.292 /// For example you can write:293 ///\code294 /// for(auto a: p.arcs())295 /// doSomething(a);296 ///\endcode297 LemonRangeWrapper1<ArcIt, PathDumper> arcs() const {298 return LemonRangeWrapper1<ArcIt, PathDumper>(*this);299 }300 301 266 302 267 /// \brief LEMON style iterator for enumerating the arcs of a path … … 329 294 }; 330 295 331 /// \brief Gets the collection of the arcs of the path332 /// in reverse direction.333 ///334 /// This function can be used for iterating on the335 /// arcs of the path in reverse direction. It returns a wrapped336 /// RevArcIt, which looks like an STL container337 /// (by having begin() and end()) which you can use in range-based338 /// for loops, STL algorithms, etc.339 /// For example you can write:340 ///\code341 /// for(auto a: p.revArcs())342 /// doSomething(a);343 ///\endcode344 LemonRangeWrapper1<RevArcIt, PathDumper> revArcs() const {345 return LemonRangeWrapper1<RevArcIt, PathDumper>(*this);346 }347 348 349 296 template <typename _Path> 350 297 struct Constraints { -
lemon/config.h.in
r1343 r1340 4 4 #define LEMON_VERSION "@PROJECT_VERSION@" 5 5 #cmakedefine LEMON_HAVE_LONG_LONG 1 6 7 #cmakedefine LEMON_CXX11 18 6 9 7 #cmakedefine LEMON_WIN32 1 -
lemon/cplex.cc
r1336 r1270 88 88 int status; 89 89 _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status); 90 _rows = cplex._rows;91 _cols = cplex._cols;90 rows = cplex.rows; 91 cols = cplex.cols; 92 92 messageLevel(MESSAGE_NOTHING); 93 93 } … … 116 116 ExprIterator e, Value ub) { 117 117 int i = CPXgetnumrows(cplexEnv(), _prob); 118 119 int rmatbeg = 0; 120 118 if (lb == -INF) { 119 const char s = 'L'; 120 CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0); 121 } else if (ub == INF) { 122 const char s = 'G'; 123 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); 124 } else if (lb == ub){ 125 const char s = 'E'; 126 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); 127 } else { 128 const char s = 'R'; 129 double len = ub - lb; 130 CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0); 131 } 132 121 133 std::vector<int> indices; 134 std::vector<int> rowlist; 122 135 std::vector<Value> values; 123 136 … … 125 138 indices.push_back(it->first); 126 139 values.push_back(it->second); 127 } 128 129 if (lb == -INF) { 130 const char s = 'L'; 131 CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s, 132 &rmatbeg, &indices.front(), &values.front(), 0, 0); 133 } else if (ub == INF) { 134 const char s = 'G'; 135 CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s, 136 &rmatbeg, &indices.front(), &values.front(), 0, 0); 137 } else if (lb == ub){ 138 const char s = 'E'; 139 CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &lb, &s, 140 &rmatbeg, &indices.front(), &values.front(), 0, 0); 141 } else { 142 const char s = 'R'; 143 double len = ub - lb; 144 CPXaddrows(cplexEnv(), _prob, 0, 1, values.size(), &ub, &s, 145 &rmatbeg, &indices.front(), &values.front(), 0, 0); 146 CPXchgrngval(cplexEnv(), _prob, 1, &i, &len); 147 } 148 140 rowlist.push_back(i); 141 } 142 143 CPXchgcoeflist(cplexEnv(), _prob, values.size(), 144 &rowlist.front(), &indices.front(), &values.front()); 145 149 146 return i; 150 147 } … … 159 156 160 157 void CplexBase::_eraseColId(int i) { 161 _cols.eraseIndex(i);162 _cols.shiftIndices(i);158 cols.eraseIndex(i); 159 cols.shiftIndices(i); 163 160 } 164 161 void CplexBase::_eraseRowId(int i) { 165 _rows.eraseIndex(i);166 _rows.shiftIndices(i);162 rows.eraseIndex(i); 163 rows.shiftIndices(i); 167 164 } 168 165 -
lemon/glpk.cc
r1336 r1270 39 39 glp_copy_prob(lp, other.lp, GLP_ON); 40 40 glp_create_index(lp); 41 _rows = other._rows;42 _cols = other._cols;41 rows = other.rows; 42 cols = other.cols; 43 43 messageLevel(MESSAGE_NOTHING); 44 44 } … … 109 109 110 110 void GlpkBase::_eraseColId(int i) { 111 _cols.eraseIndex(i);112 _cols.shiftIndices(i);111 cols.eraseIndex(i); 112 cols.shiftIndices(i); 113 113 } 114 114 115 115 void GlpkBase::_eraseRowId(int i) { 116 _rows.eraseIndex(i);117 _rows.shiftIndices(i);116 rows.eraseIndex(i); 117 rows.shiftIndices(i); 118 118 } 119 119 -
lemon/glpk.h
r1336 r1270 142 142 143 143 ///Returns the constraint identifier understood by GLPK. 144 int lpxRow(Row r) const { return _rows(id(r)); }144 int lpxRow(Row r) const { return rows(id(r)); } 145 145 146 146 ///Returns the variable identifier understood by GLPK. 147 int lpxCol(Col c) const { return _cols(id(c)); }147 int lpxCol(Col c) const { return cols(id(c)); } 148 148 149 149 #ifdef DOXYGEN -
lemon/list_graph.h
r1337 r1270 49 49 }; 50 50 51 std::vector<NodeT> _nodes;51 std::vector<NodeT> nodes; 52 52 53 53 int first_node; … … 55 55 int first_free_node; 56 56 57 std::vector<ArcT> _arcs;57 std::vector<ArcT> arcs; 58 58 59 59 int first_free_arc; … … 98 98 99 99 ListDigraphBase() 100 : _nodes(), first_node(-1),101 first_free_node(-1), _arcs(), first_free_arc(-1) {}102 103 104 int maxNodeId() const { return _nodes.size()-1; }105 int maxArcId() const { return _arcs.size()-1; }106 107 Node source(Arc e) const { return Node( _arcs[e.id].source); }108 Node target(Arc e) const { return Node( _arcs[e.id].target); }100 : nodes(), first_node(-1), 101 first_free_node(-1), arcs(), first_free_arc(-1) {} 102 103 104 int maxNodeId() const { return nodes.size()-1; } 105 int maxArcId() const { return arcs.size()-1; } 106 107 Node source(Arc e) const { return Node(arcs[e.id].source); } 108 Node target(Arc e) const { return Node(arcs[e.id].target); } 109 109 110 110 … … 114 114 115 115 void next(Node& node) const { 116 node.id = _nodes[node.id].next;116 node.id = nodes[node.id].next; 117 117 } 118 118 … … 121 121 int n; 122 122 for(n = first_node; 123 n != -1 && _nodes[n].first_out == -1;124 n = _nodes[n].next) {}125 arc.id = (n == -1) ? -1 : _nodes[n].first_out;123 n != -1 && nodes[n].first_out == -1; 124 n = nodes[n].next) {} 125 arc.id = (n == -1) ? -1 : nodes[n].first_out; 126 126 } 127 127 128 128 void next(Arc& arc) const { 129 if ( _arcs[arc.id].next_out != -1) {130 arc.id = _arcs[arc.id].next_out;129 if (arcs[arc.id].next_out != -1) { 130 arc.id = arcs[arc.id].next_out; 131 131 } else { 132 132 int n; 133 for(n = _nodes[_arcs[arc.id].source].next;134 n != -1 && _nodes[n].first_out == -1;135 n = _nodes[n].next) {}136 arc.id = (n == -1) ? -1 : _nodes[n].first_out;133 for(n = nodes[arcs[arc.id].source].next; 134 n != -1 && nodes[n].first_out == -1; 135 n = nodes[n].next) {} 136 arc.id = (n == -1) ? -1 : nodes[n].first_out; 137 137 } 138 138 } 139 139 140 140 void firstOut(Arc &e, const Node& v) const { 141 e.id = _nodes[v.id].first_out;141 e.id = nodes[v.id].first_out; 142 142 } 143 143 void nextOut(Arc &e) const { 144 e.id= _arcs[e.id].next_out;144 e.id=arcs[e.id].next_out; 145 145 } 146 146 147 147 void firstIn(Arc &e, const Node& v) const { 148 e.id = _nodes[v.id].first_in;148 e.id = nodes[v.id].first_in; 149 149 } 150 150 void nextIn(Arc &e) const { 151 e.id= _arcs[e.id].next_in;151 e.id=arcs[e.id].next_in; 152 152 } 153 153 … … 160 160 161 161 bool valid(Node n) const { 162 return n.id >= 0 && n.id < static_cast<int>( _nodes.size()) &&163 _nodes[n.id].prev != -2;162 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 163 nodes[n.id].prev != -2; 164 164 } 165 165 166 166 bool valid(Arc a) const { 167 return a.id >= 0 && a.id < static_cast<int>( _arcs.size()) &&168 _arcs[a.id].prev_in != -2;167 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 168 arcs[a.id].prev_in != -2; 169 169 } 170 170 … … 173 173 174 174 if(first_free_node==-1) { 175 n = _nodes.size();176 _nodes.push_back(NodeT());175 n = nodes.size(); 176 nodes.push_back(NodeT()); 177 177 } else { 178 178 n = first_free_node; 179 first_free_node = _nodes[n].next;180 } 181 182 _nodes[n].next = first_node;183 if(first_node != -1) _nodes[first_node].prev = n;179 first_free_node = nodes[n].next; 180 } 181 182 nodes[n].next = first_node; 183 if(first_node != -1) nodes[first_node].prev = n; 184 184 first_node = n; 185 _nodes[n].prev = -1;186 187 _nodes[n].first_in = _nodes[n].first_out = -1;185 nodes[n].prev = -1; 186 187 nodes[n].first_in = nodes[n].first_out = -1; 188 188 189 189 return Node(n); … … 194 194 195 195 if (first_free_arc == -1) { 196 n = _arcs.size();197 _arcs.push_back(ArcT());196 n = arcs.size(); 197 arcs.push_back(ArcT()); 198 198 } else { 199 199 n = first_free_arc; 200 first_free_arc = _arcs[n].next_in;201 } 202 203 _arcs[n].source = u.id;204 _arcs[n].target = v.id;205 206 _arcs[n].next_out = _nodes[u.id].first_out;207 if( _nodes[u.id].first_out != -1) {208 _arcs[_nodes[u.id].first_out].prev_out = n;209 } 210 211 _arcs[n].next_in = _nodes[v.id].first_in;212 if( _nodes[v.id].first_in != -1) {213 _arcs[_nodes[v.id].first_in].prev_in = n;214 } 215 216 _arcs[n].prev_in = _arcs[n].prev_out = -1;217 218 _nodes[u.id].first_out = _nodes[v.id].first_in = n;200 first_free_arc = arcs[n].next_in; 201 } 202 203 arcs[n].source = u.id; 204 arcs[n].target = v.id; 205 206 arcs[n].next_out = nodes[u.id].first_out; 207 if(nodes[u.id].first_out != -1) { 208 arcs[nodes[u.id].first_out].prev_out = n; 209 } 210 211 arcs[n].next_in = nodes[v.id].first_in; 212 if(nodes[v.id].first_in != -1) { 213 arcs[nodes[v.id].first_in].prev_in = n; 214 } 215 216 arcs[n].prev_in = arcs[n].prev_out = -1; 217 218 nodes[u.id].first_out = nodes[v.id].first_in = n; 219 219 220 220 return Arc(n); … … 224 224 int n = node.id; 225 225 226 if( _nodes[n].next != -1) {227 _nodes[_nodes[n].next].prev = _nodes[n].prev;228 } 229 230 if( _nodes[n].prev != -1) {231 _nodes[_nodes[n].prev].next = _nodes[n].next;232 } else { 233 first_node = _nodes[n].next;234 } 235 236 _nodes[n].next = first_free_node;226 if(nodes[n].next != -1) { 227 nodes[nodes[n].next].prev = nodes[n].prev; 228 } 229 230 if(nodes[n].prev != -1) { 231 nodes[nodes[n].prev].next = nodes[n].next; 232 } else { 233 first_node = nodes[n].next; 234 } 235 236 nodes[n].next = first_free_node; 237 237 first_free_node = n; 238 _nodes[n].prev = -2;238 nodes[n].prev = -2; 239 239 240 240 } … … 243 243 int n = arc.id; 244 244 245 if( _arcs[n].next_in!=-1) {246 _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in;247 } 248 249 if( _arcs[n].prev_in!=-1) {250 _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in;251 } else { 252 _nodes[_arcs[n].target].first_in = _arcs[n].next_in;253 } 254 255 256 if( _arcs[n].next_out!=-1) {257 _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;258 } 259 260 if( _arcs[n].prev_out!=-1) {261 _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;262 } else { 263 _nodes[_arcs[n].source].first_out = _arcs[n].next_out;264 } 265 266 _arcs[n].next_in = first_free_arc;245 if(arcs[n].next_in!=-1) { 246 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; 247 } 248 249 if(arcs[n].prev_in!=-1) { 250 arcs[arcs[n].prev_in].next_in = arcs[n].next_in; 251 } else { 252 nodes[arcs[n].target].first_in = arcs[n].next_in; 253 } 254 255 256 if(arcs[n].next_out!=-1) { 257 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 258 } 259 260 if(arcs[n].prev_out!=-1) { 261 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 262 } else { 263 nodes[arcs[n].source].first_out = arcs[n].next_out; 264 } 265 266 arcs[n].next_in = first_free_arc; 267 267 first_free_arc = n; 268 _arcs[n].prev_in = -2;268 arcs[n].prev_in = -2; 269 269 } 270 270 271 271 void clear() { 272 _arcs.clear();273 _nodes.clear();272 arcs.clear(); 273 nodes.clear(); 274 274 first_node = first_free_node = first_free_arc = -1; 275 275 } … … 278 278 void changeTarget(Arc e, Node n) 279 279 { 280 if( _arcs[e.id].next_in != -1)281 _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in;282 if( _arcs[e.id].prev_in != -1)283 _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in;284 else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in;285 if ( _nodes[n.id].first_in != -1) {286 _arcs[_nodes[n.id].first_in].prev_in = e.id;287 } 288 _arcs[e.id].target = n.id;289 _arcs[e.id].prev_in = -1;290 _arcs[e.id].next_in = _nodes[n.id].first_in;291 _nodes[n.id].first_in = e.id;280 if(arcs[e.id].next_in != -1) 281 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in; 282 if(arcs[e.id].prev_in != -1) 283 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in; 284 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in; 285 if (nodes[n.id].first_in != -1) { 286 arcs[nodes[n.id].first_in].prev_in = e.id; 287 } 288 arcs[e.id].target = n.id; 289 arcs[e.id].prev_in = -1; 290 arcs[e.id].next_in = nodes[n.id].first_in; 291 nodes[n.id].first_in = e.id; 292 292 } 293 293 void changeSource(Arc e, Node n) 294 294 { 295 if( _arcs[e.id].next_out != -1)296 _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out;297 if( _arcs[e.id].prev_out != -1)298 _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out;299 else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out;300 if ( _nodes[n.id].first_out != -1) {301 _arcs[_nodes[n.id].first_out].prev_out = e.id;302 } 303 _arcs[e.id].source = n.id;304 _arcs[e.id].prev_out = -1;305 _arcs[e.id].next_out = _nodes[n.id].first_out;306 _nodes[n.id].first_out = e.id;295 if(arcs[e.id].next_out != -1) 296 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out; 297 if(arcs[e.id].prev_out != -1) 298 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out; 299 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out; 300 if (nodes[n.id].first_out != -1) { 301 arcs[nodes[n.id].first_out].prev_out = e.id; 302 } 303 arcs[e.id].source = n.id; 304 arcs[e.id].prev_out = -1; 305 arcs[e.id].next_out = nodes[n.id].first_out; 306 nodes[n.id].first_out = e.id; 307 307 } 308 308 … … 487 487 Node split(Node n, bool connect = true) { 488 488 Node b = addNode(); 489 _nodes[b.id].first_out=_nodes[n.id].first_out;490 _nodes[n.id].first_out=-1;491 for(int i= _nodes[b.id].first_out; i!=-1; i=_arcs[i].next_out) {492 _arcs[i].source=b.id;489 nodes[b.id].first_out=nodes[n.id].first_out; 490 nodes[n.id].first_out=-1; 491 for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) { 492 arcs[i].source=b.id; 493 493 } 494 494 if (connect) addArc(n,b); … … 533 533 /// to build the digraph. 534 534 /// \sa reserveArc() 535 void reserveNode(int n) { _nodes.reserve(n); };535 void reserveNode(int n) { nodes.reserve(n); }; 536 536 537 537 /// Reserve memory for arcs. … … 543 543 /// to build the digraph. 544 544 /// \sa reserveNode() 545 void reserveArc(int m) { _arcs.reserve(m); };545 void reserveArc(int m) { arcs.reserve(m); }; 546 546 547 547 /// \brief Class to make a snapshot of the digraph and restore … … 804 804 }; 805 805 806 std::vector<NodeT> _nodes;806 std::vector<NodeT> nodes; 807 807 808 808 int first_node; … … 810 810 int first_free_node; 811 811 812 std::vector<ArcT> _arcs;812 std::vector<ArcT> arcs; 813 813 814 814 int first_free_arc; … … 868 868 869 869 ListGraphBase() 870 : _nodes(), first_node(-1),871 first_free_node(-1), _arcs(), first_free_arc(-1) {}872 873 874 int maxNodeId() const { return _nodes.size()-1; }875 int maxEdgeId() const { return _arcs.size() / 2 - 1; }876 int maxArcId() const { return _arcs.size()-1; }877 878 Node source(Arc e) const { return Node( _arcs[e.id ^ 1].target); }879 Node target(Arc e) const { return Node( _arcs[e.id].target); }880 881 Node u(Edge e) const { return Node( _arcs[2 * e.id].target); }882 Node v(Edge e) const { return Node( _arcs[2 * e.id + 1].target); }870 : nodes(), first_node(-1), 871 first_free_node(-1), arcs(), first_free_arc(-1) {} 872 873 874 int maxNodeId() const { return nodes.size()-1; } 875 int maxEdgeId() const { return arcs.size() / 2 - 1; } 876 int maxArcId() const { return arcs.size()-1; } 877 878 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } 879 Node target(Arc e) const { return Node(arcs[e.id].target); } 880 881 Node u(Edge e) const { return Node(arcs[2 * e.id].target); } 882 Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); } 883 883 884 884 static bool direction(Arc e) { … … 895 895 896 896 void next(Node& node) const { 897 node.id = _nodes[node.id].next;897 node.id = nodes[node.id].next; 898 898 } 899 899 900 900 void first(Arc& e) const { 901 901 int n = first_node; 902 while (n != -1 && _nodes[n].first_out == -1) {903 n = _nodes[n].next;904 } 905 e.id = (n == -1) ? -1 : _nodes[n].first_out;902 while (n != -1 && nodes[n].first_out == -1) { 903 n = nodes[n].next; 904 } 905 e.id = (n == -1) ? -1 : nodes[n].first_out; 906 906 } 907 907 908 908 void next(Arc& e) const { 909 if ( _arcs[e.id].next_out != -1) {910 e.id = _arcs[e.id].next_out;911 } else { 912 int n = _nodes[_arcs[e.id ^ 1].target].next;913 while(n != -1 && _nodes[n].first_out == -1) {914 n = _nodes[n].next;915 } 916 e.id = (n == -1) ? -1 : _nodes[n].first_out;909 if (arcs[e.id].next_out != -1) { 910 e.id = arcs[e.id].next_out; 911 } else { 912 int n = nodes[arcs[e.id ^ 1].target].next; 913 while(n != -1 && nodes[n].first_out == -1) { 914 n = nodes[n].next; 915 } 916 e.id = (n == -1) ? -1 : nodes[n].first_out; 917 917 } 918 918 } … … 921 921 int n = first_node; 922 922 while (n != -1) { 923 e.id = _nodes[n].first_out;923 e.id = nodes[n].first_out; 924 924 while ((e.id & 1) != 1) { 925 e.id = _arcs[e.id].next_out;925 e.id = arcs[e.id].next_out; 926 926 } 927 927 if (e.id != -1) { … … 929 929 return; 930 930 } 931 n = _nodes[n].next;931 n = nodes[n].next; 932 932 } 933 933 e.id = -1; … … 935 935 936 936 void next(Edge& e) const { 937 int n = _arcs[e.id * 2].target;938 e.id = _arcs[(e.id * 2) | 1].next_out;937 int n = arcs[e.id * 2].target; 938 e.id = arcs[(e.id * 2) | 1].next_out; 939 939 while ((e.id & 1) != 1) { 940 e.id = _arcs[e.id].next_out;940 e.id = arcs[e.id].next_out; 941 941 } 942 942 if (e.id != -1) { … … 944 944 return; 945 945 } 946 n = _nodes[n].next;946 n = nodes[n].next; 947 947 while (n != -1) { 948 e.id = _nodes[n].first_out;948 e.id = nodes[n].first_out; 949 949 while ((e.id & 1) != 1) { 950 e.id = _arcs[e.id].next_out;950 e.id = arcs[e.id].next_out; 951 951 } 952 952 if (e.id != -1) { … … 954 954 return; 955 955 } 956 n = _nodes[n].next;956 n = nodes[n].next; 957 957 } 958 958 e.id = -1; … … 960 960 961 961 void firstOut(Arc &e, const Node& v) const { 962 e.id = _nodes[v.id].first_out;962 e.id = nodes[v.id].first_out; 963 963 } 964 964 void nextOut(Arc &e) const { 965 e.id = _arcs[e.id].next_out;965 e.id = arcs[e.id].next_out; 966 966 } 967 967 968 968 void firstIn(Arc &e, const Node& v) const { 969 e.id = (( _nodes[v.id].first_out) ^ 1);969 e.id = ((nodes[v.id].first_out) ^ 1); 970 970 if (e.id == -2) e.id = -1; 971 971 } 972 972 void nextIn(Arc &e) const { 973 e.id = (( _arcs[e.id ^ 1].next_out) ^ 1);973 e.id = ((arcs[e.id ^ 1].next_out) ^ 1); 974 974 if (e.id == -2) e.id = -1; 975 975 } 976 976 977 977 void firstInc(Edge &e, bool& d, const Node& v) const { 978 int a = _nodes[v.id].first_out;978 int a = nodes[v.id].first_out; 979 979 if (a != -1 ) { 980 980 e.id = a / 2; … … 986 986 } 987 987 void nextInc(Edge &e, bool& d) const { 988 int a = ( _arcs[(e.id * 2) | (d ? 1 : 0)].next_out);988 int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); 989 989 if (a != -1 ) { 990 990 e.id = a / 2; … … 1005 1005 1006 1006 bool valid(Node n) const { 1007 return n.id >= 0 && n.id < static_cast<int>( _nodes.size()) &&1008 _nodes[n.id].prev != -2;1007 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 1008 nodes[n.id].prev != -2; 1009 1009 } 1010 1010 1011 1011 bool valid(Arc a) const { 1012 return a.id >= 0 && a.id < static_cast<int>( _arcs.size()) &&1013 _arcs[a.id].prev_out != -2;1012 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 1013 arcs[a.id].prev_out != -2; 1014 1014 } 1015 1015 1016 1016 bool valid(Edge e) const { 1017 return e.id >= 0 && 2 * e.id < static_cast<int>( _arcs.size()) &&1018 _arcs[2 * e.id].prev_out != -2;1017 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 1018 arcs[2 * e.id].prev_out != -2; 1019 1019 } 1020 1020 … … 1023 1023 1024 1024 if(first_free_node==-1) { 1025 n = _nodes.size();1026 _nodes.push_back(NodeT());1025 n = nodes.size(); 1026 nodes.push_back(NodeT()); 1027 1027 } else { 1028 1028 n = first_free_node; 1029 first_free_node = _nodes[n].next;1030 } 1031 1032 _nodes[n].next = first_node;1033 if (first_node != -1) _nodes[first_node].prev = n;1029 first_free_node = nodes[n].next; 1030 } 1031 1032 nodes[n].next = first_node; 1033 if (first_node != -1) nodes[first_node].prev = n; 1034 1034 first_node = n; 1035 _nodes[n].prev = -1;1036 1037 _nodes[n].first_out = -1;1035 nodes[n].prev = -1; 1036 1037 nodes[n].first_out = -1; 1038 1038 1039 1039 return Node(n); … … 1044 1044 1045 1045 if (first_free_arc == -1) { 1046 n = _arcs.size();1047 _arcs.push_back(ArcT());1048 _arcs.push_back(ArcT());1046 n = arcs.size(); 1047 arcs.push_back(ArcT()); 1048 arcs.push_back(ArcT()); 1049 1049 } else { 1050 1050 n = first_free_arc; 1051 first_free_arc = _arcs[n].next_out;1052 } 1053 1054 _arcs[n].target = u.id;1055 _arcs[n | 1].target = v.id;1056 1057 _arcs[n].next_out = _nodes[v.id].first_out;1058 if ( _nodes[v.id].first_out != -1) {1059 _arcs[_nodes[v.id].first_out].prev_out = n;1060 } 1061 _arcs[n].prev_out = -1;1062 _nodes[v.id].first_out = n;1063 1064 _arcs[n | 1].next_out = _nodes[u.id].first_out;1065 if ( _nodes[u.id].first_out != -1) {1066 _arcs[_nodes[u.id].first_out].prev_out = (n | 1);1067 } 1068 _arcs[n | 1].prev_out = -1;1069 _nodes[u.id].first_out = (n | 1);1051 first_free_arc = arcs[n].next_out; 1052 } 1053 1054 arcs[n].target = u.id; 1055 arcs[n | 1].target = v.id; 1056 1057 arcs[n].next_out = nodes[v.id].first_out; 1058 if (nodes[v.id].first_out != -1) { 1059 arcs[nodes[v.id].first_out].prev_out = n; 1060 } 1061 arcs[n].prev_out = -1; 1062 nodes[v.id].first_out = n; 1063 1064 arcs[n | 1].next_out = nodes[u.id].first_out; 1065 if (nodes[u.id].first_out != -1) { 1066 arcs[nodes[u.id].first_out].prev_out = (n | 1); 1067 } 1068 arcs[n | 1].prev_out = -1; 1069 nodes[u.id].first_out = (n | 1); 1070 1070 1071 1071 return Edge(n / 2); … … 1075 1075 int n = node.id; 1076 1076 1077 if( _nodes[n].next != -1) {1078 _nodes[_nodes[n].next].prev = _nodes[n].prev;1079 } 1080 1081 if( _nodes[n].prev != -1) {1082 _nodes[_nodes[n].prev].next = _nodes[n].next;1083 } else { 1084 first_node = _nodes[n].next;1085 } 1086 1087 _nodes[n].next = first_free_node;1077 if(nodes[n].next != -1) { 1078 nodes[nodes[n].next].prev = nodes[n].prev; 1079 } 1080 1081 if(nodes[n].prev != -1) { 1082 nodes[nodes[n].prev].next = nodes[n].next; 1083 } else { 1084 first_node = nodes[n].next; 1085 } 1086 1087 nodes[n].next = first_free_node; 1088 1088 first_free_node = n; 1089 _nodes[n].prev = -2;1089 nodes[n].prev = -2; 1090 1090 } 1091 1091 … … 1093 1093 int n = edge.id * 2; 1094 1094 1095 if ( _arcs[n].next_out != -1) {1096 _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;1097 } 1098 1099 if ( _arcs[n].prev_out != -1) {1100 _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;1101 } else { 1102 _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;1103 } 1104 1105 if ( _arcs[n | 1].next_out != -1) {1106 _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;1107 } 1108 1109 if ( _arcs[n | 1].prev_out != -1) {1110 _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;1111 } else { 1112 _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;1113 } 1114 1115 _arcs[n].next_out = first_free_arc;1095 if (arcs[n].next_out != -1) { 1096 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 1097 } 1098 1099 if (arcs[n].prev_out != -1) { 1100 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 1101 } else { 1102 nodes[arcs[n | 1].target].first_out = arcs[n].next_out; 1103 } 1104 1105 if (arcs[n | 1].next_out != -1) { 1106 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; 1107 } 1108 1109 if (arcs[n | 1].prev_out != -1) { 1110 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; 1111 } else { 1112 nodes[arcs[n].target].first_out = arcs[n | 1].next_out; 1113 } 1114 1115 arcs[n].next_out = first_free_arc; 1116 1116 first_free_arc = n; 1117 _arcs[n].prev_out = -2;1118 _arcs[n | 1].prev_out = -2;1117 arcs[n].prev_out = -2; 1118 arcs[n | 1].prev_out = -2; 1119 1119 1120 1120 } 1121 1121 1122 1122 void clear() { 1123 _arcs.clear();1124 _nodes.clear();1123 arcs.clear(); 1124 nodes.clear(); 1125 1125 first_node = first_free_node = first_free_arc = -1; 1126 1126 } … … 1129 1129 1130 1130 void changeV(Edge e, Node n) { 1131 if( _arcs[2 * e.id].next_out != -1) {1132 _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;1133 } 1134 if( _arcs[2 * e.id].prev_out != -1) {1135 _arcs[_arcs[2 * e.id].prev_out].next_out =1136 _arcs[2 * e.id].next_out;1137 } else { 1138 _nodes[_arcs[(2 * e.id) | 1].target].first_out =1139 _arcs[2 * e.id].next_out;1140 } 1141 1142 if ( _nodes[n.id].first_out != -1) {1143 _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;1144 } 1145 _arcs[(2 * e.id) | 1].target = n.id;1146 _arcs[2 * e.id].prev_out = -1;1147 _arcs[2 * e.id].next_out = _nodes[n.id].first_out;1148 _nodes[n.id].first_out = 2 * e.id;1131 if(arcs[2 * e.id].next_out != -1) { 1132 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; 1133 } 1134 if(arcs[2 * e.id].prev_out != -1) { 1135 arcs[arcs[2 * e.id].prev_out].next_out = 1136 arcs[2 * e.id].next_out; 1137 } else { 1138 nodes[arcs[(2 * e.id) | 1].target].first_out = 1139 arcs[2 * e.id].next_out; 1140 } 1141 1142 if (nodes[n.id].first_out != -1) { 1143 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; 1144 } 1145 arcs[(2 * e.id) | 1].target = n.id; 1146 arcs[2 * e.id].prev_out = -1; 1147 arcs[2 * e.id].next_out = nodes[n.id].first_out; 1148 nodes[n.id].first_out = 2 * e.id; 1149 1149 } 1150 1150 1151 1151 void changeU(Edge e, Node n) { 1152 if( _arcs[(2 * e.id) | 1].next_out != -1) {1153 _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =1154 _arcs[(2 * e.id) | 1].prev_out;1155 } 1156 if( _arcs[(2 * e.id) | 1].prev_out != -1) {1157 _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =1158 _arcs[(2 * e.id) | 1].next_out;1159 } else { 1160 _nodes[_arcs[2 * e.id].target].first_out =1161 _arcs[(2 * e.id) | 1].next_out;1162 } 1163 1164 if ( _nodes[n.id].first_out != -1) {1165 _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);1166 } 1167 _arcs[2 * e.id].target = n.id;1168 _arcs[(2 * e.id) | 1].prev_out = -1;1169 _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;1170 _nodes[n.id].first_out = ((2 * e.id) | 1);1152 if(arcs[(2 * e.id) | 1].next_out != -1) { 1153 arcs[arcs[(2 * e.id) | 1].next_out].prev_out = 1154 arcs[(2 * e.id) | 1].prev_out; 1155 } 1156 if(arcs[(2 * e.id) | 1].prev_out != -1) { 1157 arcs[arcs[(2 * e.id) | 1].prev_out].next_out = 1158 arcs[(2 * e.id) | 1].next_out; 1159 } else { 1160 nodes[arcs[2 * e.id].target].first_out = 1161 arcs[(2 * e.id) | 1].next_out; 1162 } 1163 1164 if (nodes[n.id].first_out != -1) { 1165 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); 1166 } 1167 arcs[2 * e.id].target = n.id; 1168 arcs[(2 * e.id) | 1].prev_out = -1; 1169 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; 1170 nodes[n.id].first_out = ((2 * e.id) | 1); 1171 1171 } 1172 1172 … … 1210 1210 ListGraph() {} 1211 1211 1212 typedef Parent:: IncEdgeIt IncEdgeIt;1212 typedef Parent::OutArcIt IncEdgeIt; 1213 1213 1214 1214 /// \brief Add a new node to the graph. … … 1345 1345 /// to build the graph. 1346 1346 /// \sa reserveEdge() 1347 void reserveNode(int n) { _nodes.reserve(n); };1347 void reserveNode(int n) { nodes.reserve(n); }; 1348 1348 1349 1349 /// Reserve memory for edges. … … 1355 1355 /// to build the graph. 1356 1356 /// \sa reserveNode() 1357 void reserveEdge(int m) { _arcs.reserve(2 * m); };1357 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1358 1358 1359 1359 /// \brief Class to make a snapshot of the graph and restore … … 1618 1618 }; 1619 1619 1620 std::vector<NodeT> _nodes;1620 std::vector<NodeT> nodes; 1621 1621 1622 1622 int first_node, first_red, first_blue; … … 1625 1625 int first_free_red, first_free_blue; 1626 1626 1627 std::vector<ArcT> _arcs;1627 std::vector<ArcT> arcs; 1628 1628 1629 1629 int first_free_arc; … … 1707 1707 1708 1708 ListBpGraphBase() 1709 : _nodes(), first_node(-1),1709 : nodes(), first_node(-1), 1710 1710 first_red(-1), first_blue(-1), 1711 1711 max_red(-1), max_blue(-1), 1712 1712 first_free_red(-1), first_free_blue(-1), 1713 _arcs(), first_free_arc(-1) {}1714 1715 1716 bool red(Node n) const { return _nodes[n.id].red; }1717 bool blue(Node n) const { return ! _nodes[n.id].red; }1713 arcs(), first_free_arc(-1) {} 1714 1715 1716 bool red(Node n) const { return nodes[n.id].red; } 1717 bool blue(Node n) const { return !nodes[n.id].red; } 1718 1718 1719 1719 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); } 1720 1720 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); } 1721 1721 1722 int maxNodeId() const { return _nodes.size()-1; }1722 int maxNodeId() const { return nodes.size()-1; } 1723 1723 int maxRedId() const { return max_red; } 1724 1724 int maxBlueId() const { return max_blue; } 1725 int maxEdgeId() const { return _arcs.size() / 2 - 1; }1726 int maxArcId() const { return _arcs.size()-1; }1727 1728 Node source(Arc e) const { return Node( _arcs[e.id ^ 1].target); }1729 Node target(Arc e) const { return Node( _arcs[e.id].target); }1725 int maxEdgeId() const { return arcs.size() / 2 - 1; } 1726 int maxArcId() const { return arcs.size()-1; } 1727 1728 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } 1729 Node target(Arc e) const { return Node(arcs[e.id].target); } 1730 1730 1731 1731 RedNode redNode(Edge e) const { 1732 return RedNode( _arcs[2 * e.id].target);1732 return RedNode(arcs[2 * e.id].target); 1733 1733 } 1734 1734 BlueNode blueNode(Edge e) const { 1735 return BlueNode( _arcs[2 * e.id + 1].target);1735 return BlueNode(arcs[2 * e.id + 1].target); 1736 1736 } 1737 1737 … … 1749 1749 1750 1750 void next(Node& node) const { 1751 node.id = _nodes[node.id].next;1751 node.id = nodes[node.id].next; 1752 1752 } 1753 1753 … … 1757 1757 1758 1758 void next(RedNode& node) const { 1759 node.id = _nodes[node.id].partition_next;1759 node.id = nodes[node.id].partition_next; 1760 1760 } 1761 1761 … … 1765 1765 1766 1766 void next(BlueNode& node) const { 1767 node.id = _nodes[node.id].partition_next;1767 node.id = nodes[node.id].partition_next; 1768 1768 } 1769 1769 1770 1770 void first(Arc& e) const { 1771 1771 int n = first_node; 1772 while (n != -1 && _nodes[n].first_out == -1) {1773 n = _nodes[n].next;1774 } 1775 e.id = (n == -1) ? -1 : _nodes[n].first_out;1772 while (n != -1 && nodes[n].first_out == -1) { 1773 n = nodes[n].next; 1774 } 1775 e.id = (n == -1) ? -1 : nodes[n].first_out; 1776 1776 } 1777 1777 1778 1778 void next(Arc& e) const { 1779 if ( _arcs[e.id].next_out != -1) {1780 e.id = _arcs[e.id].next_out;1781 } else { 1782 int n = _nodes[_arcs[e.id ^ 1].target].next;1783 while(n != -1 && _nodes[n].first_out == -1) {1784 n = _nodes[n].next;1785 } 1786 e.id = (n == -1) ? -1 : _nodes[n].first_out;1779 if (arcs[e.id].next_out != -1) { 1780 e.id = arcs[e.id].next_out; 1781 } else { 1782 int n = nodes[arcs[e.id ^ 1].target].next; 1783 while(n != -1 && nodes[n].first_out == -1) { 1784 n = nodes[n].next; 1785 } 1786 e.id = (n == -1) ? -1 : nodes[n].first_out; 1787 1787 } 1788 1788 } … … 1791 1791 int n = first_node; 1792 1792 while (n != -1) { 1793 e.id = _nodes[n].first_out;1793 e.id = nodes[n].first_out; 1794 1794 while ((e.id & 1) != 1) { 1795 e.id = _arcs[e.id].next_out;1795 e.id = arcs[e.id].next_out; 1796 1796 } 1797 1797 if (e.id != -1) { … … 1799 1799 return; 1800 1800 } 1801 n = _nodes[n].next;1801 n = nodes[n].next; 1802 1802 } 1803 1803 e.id = -1; … … 1805 1805 1806 1806 void next(Edge& e) const { 1807 int n = _arcs[e.id * 2].target;1808 e.id = _arcs[(e.id * 2) | 1].next_out;1807 int n = arcs[e.id * 2].target; 1808 e.id = arcs[(e.id * 2) | 1].next_out; 1809 1809 while ((e.id & 1) != 1) { 1810 e.id = _arcs[e.id].next_out;1810 e.id = arcs[e.id].next_out; 1811 1811 } 1812 1812 if (e.id != -1) { … … 1814 1814 return; 1815 1815 } 1816 n = _nodes[n].next;1816 n = nodes[n].next; 1817 1817 while (n != -1) { 1818 e.id = _nodes[n].first_out;1818 e.id = nodes[n].first_out; 1819 1819 while ((e.id & 1) != 1) { 1820 e.id = _arcs[e.id].next_out;1820 e.id = arcs[e.id].next_out; 1821 1821 } 1822 1822 if (e.id != -1) { … … 1824 1824 return; 1825 1825 } 1826 n = _nodes[n].next;1826 n = nodes[n].next; 1827 1827 } 1828 1828 e.id = -1; … … 1830 1830 1831 1831 void firstOut(Arc &e, const Node& v) const { 1832 e.id = _nodes[v.id].first_out;1832 e.id = nodes[v.id].first_out; 1833 1833 } 1834 1834 void nextOut(Arc &e) const { 1835 e.id = _arcs[e.id].next_out;1835 e.id = arcs[e.id].next_out; 1836 1836 } 1837 1837 1838 1838 void firstIn(Arc &e, const Node& v) const { 1839 e.id = (( _nodes[v.id].first_out) ^ 1);1839 e.id = ((nodes[v.id].first_out) ^ 1); 1840 1840 if (e.id == -2) e.id = -1; 1841 1841 } 1842 1842 void nextIn(Arc &e) const { 1843 e.id = (( _arcs[e.id ^ 1].next_out) ^ 1);1843 e.id = ((arcs[e.id ^ 1].next_out) ^ 1); 1844 1844 if (e.id == -2) e.id = -1; 1845 1845 } 1846 1846 1847 1847 void firstInc(Edge &e, bool& d, const Node& v) const { 1848 int a = _nodes[v.id].first_out;1848 int a = nodes[v.id].first_out; 1849 1849 if (a != -1 ) { 1850 1850 e.id = a / 2; … … 1856 1856 } 1857 1857 void nextInc(Edge &e, bool& d) const { 1858 int a = ( _arcs[(e.id * 2) | (d ? 1 : 0)].next_out);1858 int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); 1859 1859 if (a != -1 ) { 1860 1860 e.id = a / 2; … … 1867 1867 1868 1868 static int id(Node v) { return v.id; } 1869 int id(RedNode v) const { return _nodes[v.id].partition_index; }1870 int id(BlueNode v) const { return _nodes[v.id].partition_index; }1869 int id(RedNode v) const { return nodes[v.id].partition_index; } 1870 int id(BlueNode v) const { return nodes[v.id].partition_index; } 1871 1871 static int id(Arc e) { return e.id; } 1872 1872 static int id(Edge e) { return e.id; } … … 1877 1877 1878 1878 bool valid(Node n) const { 1879 return n.id >= 0 && n.id < static_cast<int>( _nodes.size()) &&1880 _nodes[n.id].prev != -2;1879 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 1880 nodes[n.id].prev != -2; 1881 1881 } 1882 1882 1883 1883 bool valid(Arc a) const { 1884 return a.id >= 0 && a.id < static_cast<int>( _arcs.size()) &&1885 _arcs[a.id].prev_out != -2;1884 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 1885 arcs[a.id].prev_out != -2; 1886 1886 } 1887 1887 1888 1888 bool valid(Edge e) const { 1889 return e.id >= 0 && 2 * e.id < static_cast<int>( _arcs.size()) &&1890 _arcs[2 * e.id].prev_out != -2;1889 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 1890 arcs[2 * e.id].prev_out != -2; 1891 1891 } 1892 1892 … … 1895 1895 1896 1896 if(first_free_red==-1) { 1897 n = _nodes.size();1898 _nodes.push_back(NodeT());1899 _nodes[n].partition_index = ++max_red;1900 _nodes[n].red = true;1897 n = nodes.size(); 1898 nodes.push_back(NodeT()); 1899 nodes[n].partition_index = ++max_red; 1900 nodes[n].red = true; 1901 1901 } else { 1902 1902 n = first_free_red; 1903 first_free_red = _nodes[n].next;1904 } 1905 1906 _nodes[n].next = first_node;1907 if (first_node != -1) _nodes[first_node].prev = n;1903 first_free_red = nodes[n].next; 1904 } 1905 1906 nodes[n].next = first_node; 1907 if (first_node != -1) nodes[first_node].prev = n; 1908 1908 first_node = n; 1909 _nodes[n].prev = -1;1910 1911 _nodes[n].partition_next = first_red;1912 if (first_red != -1) _nodes[first_red].partition_prev = n;1909 nodes[n].prev = -1; 1910 1911 nodes[n].partition_next = first_red; 1912 if (first_red != -1) nodes[first_red].partition_prev = n; 1913 1913 first_red = n; 1914 _nodes[n].partition_prev = -1;1915 1916 _nodes[n].first_out = -1;1914 nodes[n].partition_prev = -1; 1915 1916 nodes[n].first_out = -1; 1917 1917 1918 1918 return RedNode(n); … … 1923 1923 1924 1924 if(first_free_blue==-1) { 1925 n = _nodes.size();1926 _nodes.push_back(NodeT());1927 _nodes[n].partition_index = ++max_blue;1928 _nodes[n].red = false;1925 n = nodes.size(); 1926 nodes.push_back(NodeT()); 1927 nodes[n].partition_index = ++max_blue; 1928 nodes[n].red = false; 1929 1929 } else { 1930 1930 n = first_free_blue; 1931 first_free_blue = _nodes[n].next;1932 } 1933 1934 _nodes[n].next = first_node;1935 if (first_node != -1) _nodes[first_node].prev = n;1931 first_free_blue = nodes[n].next; 1932 } 1933 1934 nodes[n].next = first_node; 1935 if (first_node != -1) nodes[first_node].prev = n; 1936 1936 first_node = n; 1937 _nodes[n].prev = -1;1938 1939 _nodes[n].partition_next = first_blue;1940 if (first_blue != -1) _nodes[first_blue].partition_prev = n;1937 nodes[n].prev = -1; 1938 1939 nodes[n].partition_next = first_blue; 1940 if (first_blue != -1) nodes[first_blue].partition_prev = n; 1941 1941 first_blue = n; 1942 _nodes[n].partition_prev = -1;1943 1944 _nodes[n].first_out = -1;1942 nodes[n].partition_prev = -1; 1943 1944 nodes[n].first_out = -1; 1945 1945 1946 1946 return BlueNode(n); … … 1951 1951 1952 1952 if (first_free_arc == -1) { 1953 n = _arcs.size();1954 _arcs.push_back(ArcT());1955 _arcs.push_back(ArcT());1953 n = arcs.size(); 1954 arcs.push_back(ArcT()); 1955 arcs.push_back(ArcT()); 1956 1956 } else { 1957 1957 n = first_free_arc; 1958 first_free_arc = _arcs[n].next_out;1959 } 1960 1961 _arcs[n].target = u.id;1962 _arcs[n | 1].target = v.id;1963 1964 _arcs[n].next_out = _nodes[v.id].first_out;1965 if ( _nodes[v.id].first_out != -1) {1966 _arcs[_nodes[v.id].first_out].prev_out = n;1967 } 1968 _arcs[n].prev_out = -1;1969 _nodes[v.id].first_out = n;1970 1971 _arcs[n | 1].next_out = _nodes[u.id].first_out;1972 if ( _nodes[u.id].first_out != -1) {1973 _arcs[_nodes[u.id].first_out].prev_out = (n | 1);1974 } 1975 _arcs[n | 1].prev_out = -1;1976 _nodes[u.id].first_out = (n | 1);1958 first_free_arc = arcs[n].next_out; 1959 } 1960 1961 arcs[n].target = u.id; 1962 arcs[n | 1].target = v.id; 1963 1964 arcs[n].next_out = nodes[v.id].first_out; 1965 if (nodes[v.id].first_out != -1) { 1966 arcs[nodes[v.id].first_out].prev_out = n; 1967 } 1968 arcs[n].prev_out = -1; 1969 nodes[v.id].first_out = n; 1970 1971 arcs[n | 1].next_out = nodes[u.id].first_out; 1972 if (nodes[u.id].first_out != -1) { 1973 arcs[nodes[u.id].first_out].prev_out = (n | 1); 1974 } 1975 arcs[n | 1].prev_out = -1; 1976 nodes[u.id].first_out = (n | 1); 1977 1977 1978 1978 return Edge(n / 2); … … 1982 1982 int n = node.id; 1983 1983 1984 if( _nodes[n].next != -1) {1985 _nodes[_nodes[n].next].prev = _nodes[n].prev;1986 } 1987 1988 if( _nodes[n].prev != -1) {1989 _nodes[_nodes[n].prev].next = _nodes[n].next;1990 } else { 1991 first_node = _nodes[n].next;1992 } 1993 1994 if ( _nodes[n].partition_next != -1) {1995 _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev;1996 } 1997 1998 if ( _nodes[n].partition_prev != -1) {1999 _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next;2000 } else { 2001 if ( _nodes[n].red) {2002 first_red = _nodes[n].partition_next;1984 if(nodes[n].next != -1) { 1985 nodes[nodes[n].next].prev = nodes[n].prev; 1986 } 1987 1988 if(nodes[n].prev != -1) { 1989 nodes[nodes[n].prev].next = nodes[n].next; 1990 } else { 1991 first_node = nodes[n].next; 1992 } 1993 1994 if (nodes[n].partition_next != -1) { 1995 nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev; 1996 } 1997 1998 if (nodes[n].partition_prev != -1) { 1999 nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next; 2000 } else { 2001 if (nodes[n].red) { 2002 first_red = nodes[n].partition_next; 2003 2003 } else { 2004 first_blue = _nodes[n].partition_next;2005 } 2006 } 2007 2008 if ( _nodes[n].red) {2009 _nodes[n].next = first_free_red;2004 first_blue = nodes[n].partition_next; 2005 } 2006 } 2007 2008 if (nodes[n].red) { 2009 nodes[n].next = first_free_red; 2010 2010 first_free_red = n; 2011 2011 } else { 2012 _nodes[n].next = first_free_blue;2012 nodes[n].next = first_free_blue; 2013 2013 first_free_blue = n; 2014 2014 } 2015 _nodes[n].prev = -2;2015 nodes[n].prev = -2; 2016 2016 } 2017 2017 … … 2019 2019 int n = edge.id * 2; 2020 2020 2021 if ( _arcs[n].next_out != -1) {2022 _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;2023 } 2024 2025 if ( _arcs[n].prev_out != -1) {2026 _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;2027 } else { 2028 _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;2029 } 2030 2031 if ( _arcs[n | 1].next_out != -1) {2032 _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;2033 } 2034 2035 if ( _arcs[n | 1].prev_out != -1) {2036 _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;2037 } else { 2038 _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;2039 } 2040 2041 _arcs[n].next_out = first_free_arc;2021 if (arcs[n].next_out != -1) { 2022 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 2023 } 2024 2025 if (arcs[n].prev_out != -1) { 2026 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 2027 } else { 2028 nodes[arcs[n | 1].target].first_out = arcs[n].next_out; 2029 } 2030 2031 if (arcs[n | 1].next_out != -1) { 2032 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; 2033 } 2034 2035 if (arcs[n | 1].prev_out != -1) { 2036 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; 2037 } else { 2038 nodes[arcs[n].target].first_out = arcs[n | 1].next_out; 2039 } 2040 2041 arcs[n].next_out = first_free_arc; 2042 2042 first_free_arc = n; 2043 _arcs[n].prev_out = -2;2044 _arcs[n | 1].prev_out = -2;2043 arcs[n].prev_out = -2; 2044 arcs[n | 1].prev_out = -2; 2045 2045 2046 2046 } 2047 2047 2048 2048 void clear() { 2049 _arcs.clear();2050 _nodes.clear();2049 arcs.clear(); 2050 nodes.clear(); 2051 2051 first_node = first_free_arc = first_red = first_blue = 2052 2052 max_red = max_blue = first_free_red = first_free_blue = -1; … … 2056 2056 2057 2057 void changeRed(Edge e, RedNode n) { 2058 if( _arcs[(2 * e.id) | 1].next_out != -1) {2059 _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =2060 _arcs[(2 * e.id) | 1].prev_out;2061 } 2062 if( _arcs[(2 * e.id) | 1].prev_out != -1) {2063 _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =2064 _arcs[(2 * e.id) | 1].next_out;2065 } else { 2066 _nodes[_arcs[2 * e.id].target].first_out =2067 _arcs[(2 * e.id) | 1].next_out;2068 } 2069 2070 if ( _nodes[n.id].first_out != -1) {2071 _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);2072 } 2073 _arcs[2 * e.id].target = n.id;2074 _arcs[(2 * e.id) | 1].prev_out = -1;2075 _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;2076 _nodes[n.id].first_out = ((2 * e.id) | 1);2058 if(arcs[(2 * e.id) | 1].next_out != -1) { 2059 arcs[arcs[(2 * e.id) | 1].next_out].prev_out = 2060 arcs[(2 * e.id) | 1].prev_out; 2061 } 2062 if(arcs[(2 * e.id) | 1].prev_out != -1) { 2063 arcs[arcs[(2 * e.id) | 1].prev_out].next_out = 2064 arcs[(2 * e.id) | 1].next_out; 2065 } else { 2066 nodes[arcs[2 * e.id].target].first_out = 2067 arcs[(2 * e.id) | 1].next_out; 2068 } 2069 2070 if (nodes[n.id].first_out != -1) { 2071 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); 2072 } 2073 arcs[2 * e.id].target = n.id; 2074 arcs[(2 * e.id) | 1].prev_out = -1; 2075 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; 2076 nodes[n.id].first_out = ((2 * e.id) | 1); 2077 2077 } 2078 2078 2079 2079 void changeBlue(Edge e, BlueNode n) { 2080 if( _arcs[2 * e.id].next_out != -1) {2081 _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;2082 } 2083 if( _arcs[2 * e.id].prev_out != -1) {2084 _arcs[_arcs[2 * e.id].prev_out].next_out =2085 _arcs[2 * e.id].next_out;2086 } else { 2087 _nodes[_arcs[(2 * e.id) | 1].target].first_out =2088 _arcs[2 * e.id].next_out;2089 } 2090 2091 if ( _nodes[n.id].first_out != -1) {2092 _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;2093 } 2094 _arcs[(2 * e.id) | 1].target = n.id;2095 _arcs[2 * e.id].prev_out = -1;2096 _arcs[2 * e.id].next_out = _nodes[n.id].first_out;2097 _nodes[n.id].first_out = 2 * e.id;2080 if(arcs[2 * e.id].next_out != -1) { 2081 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; 2082 } 2083 if(arcs[2 * e.id].prev_out != -1) { 2084 arcs[arcs[2 * e.id].prev_out].next_out = 2085 arcs[2 * e.id].next_out; 2086 } else { 2087 nodes[arcs[(2 * e.id) | 1].target].first_out = 2088 arcs[2 * e.id].next_out; 2089 } 2090 2091 if (nodes[n.id].first_out != -1) { 2092 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; 2093 } 2094 arcs[(2 * e.id) | 1].target = n.id; 2095 arcs[2 * e.id].prev_out = -1; 2096 arcs[2 * e.id].next_out = nodes[n.id].first_out; 2097 nodes[n.id].first_out = 2 * e.id; 2098 2098 } 2099 2099 … … 2137 2137 ListBpGraph() {} 2138 2138 2139 typedef Parent:: IncEdgeIt IncEdgeIt;2139 typedef Parent::OutArcIt IncEdgeIt; 2140 2140 2141 2141 /// \brief Add a new red node to the graph. … … 2250 2250 /// to build the graph. 2251 2251 /// \sa reserveEdge() 2252 void reserveNode(int n) { _nodes.reserve(n); };2252 void reserveNode(int n) { nodes.reserve(n); }; 2253 2253 2254 2254 /// Reserve memory for edges. … … 2260 2260 /// to build the graph. 2261 2261 /// \sa reserveNode() 2262 void reserveEdge(int m) { _arcs.reserve(2 * m); };2262 void reserveEdge(int m) { arcs.reserve(2 * m); }; 2263 2263 2264 2264 /// \brief Class to make a snapshot of the graph and restore -
lemon/lp_base.h
r1336 r1270 32 32 #include<lemon/bits/solver_bits.h> 33 33 34 #include<lemon/bits/stl_iterators.h>35 36 34 ///\file 37 35 ///\brief The interface of the LP solver interface. … … 48 46 protected: 49 47 50 _solver_bits::VarIndex _rows;51 _solver_bits::VarIndex _cols;48 _solver_bits::VarIndex rows; 49 _solver_bits::VarIndex cols; 52 50 53 51 public: … … 169 167 ColIt(const LpBase &solver) : _solver(&solver) 170 168 { 171 _solver-> _cols.firstItem(_id);169 _solver->cols.firstItem(_id); 172 170 } 173 171 /// Invalid constructor \& conversion … … 182 180 ColIt &operator++() 183 181 { 184 _solver-> _cols.nextItem(_id);182 _solver->cols.nextItem(_id); 185 183 return *this; 186 184 } 187 185 }; 188 189 /// \brief Gets the collection of the columns of the LP problem.190 ///191 /// This function can be used for iterating on192 /// the columns of the LP problem. It returns a wrapped ColIt, which looks193 /// like an STL container (by having begin() and end())194 /// which you can use in range-based for loops, STL algorithms, etc.195 /// For example you can write:196 ///\code197 /// for(auto c: lp.cols())198 /// doSomething(c);199 LemonRangeWrapper1<ColIt, LpBase> cols() {200 return LemonRangeWrapper1<ColIt, LpBase>(*this);201 }202 203 186 204 187 /// \brief Returns the ID of the column. … … 279 262 RowIt(const LpBase &solver) : _solver(&solver) 280 263 { 281 _solver-> _rows.firstItem(_id);264 _solver->rows.firstItem(_id); 282 265 } 283 266 /// Invalid constructor \& conversion … … 292 275 RowIt &operator++() 293 276 { 294 _solver-> _rows.nextItem(_id);277 _solver->rows.nextItem(_id); 295 278 return *this; 296 279 } 297 280 }; 298 299 /// \brief Gets the collection of the rows of the LP problem.300 ///301 /// This function can be used for iterating on302 /// the rows of the LP problem. It returns a wrapped RowIt, which looks303 /// like an STL container (by having begin() and end())304 /// which you can use in range-based for loops, STL algorithms, etc.305 /// For example you can write:306 ///\code307 /// for(auto c: lp.rows())308 /// doSomething(c);309 LemonRangeWrapper1<RowIt, LpBase> rows() {310 return LemonRangeWrapper1<RowIt, LpBase>(*this);311 }312 313 281 314 282 /// \brief Returns the ID of the row. … … 967 935 //Abstract virtual functions 968 936 969 virtual int _addColId(int col) { return _cols.addIndex(col); }970 virtual int _addRowId(int row) { return _rows.addIndex(row); }971 972 virtual void _eraseColId(int col) { _cols.eraseIndex(col); }973 virtual void _eraseRowId(int row) { _rows.eraseIndex(row); }937 virtual int _addColId(int col) { return cols.addIndex(col); } 938 virtual int _addRowId(int row) { return rows.addIndex(row); } 939 940 virtual void _eraseColId(int col) { cols.eraseIndex(col); } 941 virtual void _eraseRowId(int row) { rows.eraseIndex(row); } 974 942 975 943 virtual int _addCol() = 0; … … 1036 1004 Value obj_const_comp; 1037 1005 1038 LpBase() : _rows(), _cols(), obj_const_comp(0) {}1006 LpBase() : rows(), cols(), obj_const_comp(0) {} 1039 1007 1040 1008 public: … … 1148 1116 void col(Col c, const DualExpr &e) { 1149 1117 e.simplify(); 1150 _setColCoeffs( _cols(id(c)), ExprIterator(e.comps.begin(), _rows),1151 ExprIterator(e.comps.end(), _rows));1118 _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows), 1119 ExprIterator(e.comps.end(), rows)); 1152 1120 } 1153 1121 … … 1158 1126 DualExpr col(Col c) const { 1159 1127 DualExpr e; 1160 _getColCoeffs( _cols(id(c)), InsertIterator(e.comps, _rows));1128 _getColCoeffs(cols(id(c)), InsertIterator(e.comps, rows)); 1161 1129 return e; 1162 1130 } … … 1245 1213 void row(Row r, Value l, const Expr &e, Value u) { 1246 1214 e.simplify(); 1247 _setRowCoeffs( _rows(id(r)), ExprIterator(e.comps.begin(), _cols),1248 ExprIterator(e.comps.end(), _cols));1249 _setRowLowerBound( _rows(id(r)),l - *e);1250 _setRowUpperBound( _rows(id(r)),u - *e);1215 _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols), 1216 ExprIterator(e.comps.end(), cols)); 1217 _setRowLowerBound(rows(id(r)),l - *e); 1218 _setRowUpperBound(rows(id(r)),u - *e); 1251 1219 } 1252 1220 … … 1267 1235 Expr row(Row r) const { 1268 1236 Expr e; 1269 _getRowCoeffs( _rows(id(r)), InsertIterator(e.comps, _cols));1237 _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols)); 1270 1238 return e; 1271 1239 } … … 1280 1248 Row r; 1281 1249 e.simplify(); 1282 r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), _cols),1283 ExprIterator(e.comps.end(), _cols), u - *e));1250 r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols), 1251 ExprIterator(e.comps.end(), cols), u - *e)); 1284 1252 return r; 1285 1253 } … … 1293 1261 c.expr().simplify(); 1294 1262 r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, 1295 ExprIterator(c.expr().comps.begin(), _cols),1296 ExprIterator(c.expr().comps.end(), _cols),1263 ExprIterator(c.expr().comps.begin(), cols), 1264 ExprIterator(c.expr().comps.end(), cols), 1297 1265 c.upperBounded()?c.upperBound()-*c.expr():INF)); 1298 1266 return r; … … 1302 1270 ///\param c is the column to be deleted 1303 1271 void erase(Col c) { 1304 _eraseCol( _cols(id(c)));1305 _eraseColId( _cols(id(c)));1272 _eraseCol(cols(id(c))); 1273 _eraseColId(cols(id(c))); 1306 1274 } 1307 1275 ///Erase a row (i.e a constraint) from the LP … … 1309 1277 ///\param r is the row to be deleted 1310 1278 void erase(Row r) { 1311 _eraseRow( _rows(id(r)));1312 _eraseRowId( _rows(id(r)));1279 _eraseRow(rows(id(r))); 1280 _eraseRowId(rows(id(r))); 1313 1281 } 1314 1282 … … 1319 1287 std::string colName(Col c) const { 1320 1288 std::string name; 1321 _getColName( _cols(id(c)), name);1289 _getColName(cols(id(c)), name); 1322 1290 return name; 1323 1291 } … … 1328 1296 ///\param name The name to be given 1329 1297 void colName(Col c, const std::string& name) { 1330 _setColName( _cols(id(c)), name);1298 _setColName(cols(id(c)), name); 1331 1299 } 1332 1300 … … 1337 1305 Col colByName(const std::string& name) const { 1338 1306 int k = _colByName(name); 1339 return k != -1 ? Col( _cols[k]) : Col(INVALID);1307 return k != -1 ? Col(cols[k]) : Col(INVALID); 1340 1308 } 1341 1309 … … 1346 1314 std::string rowName(Row r) const { 1347 1315 std::string name; 1348 _getRowName( _rows(id(r)), name);1316 _getRowName(rows(id(r)), name); 1349 1317 return name; 1350 1318 } … … 1355 1323 ///\param name The name to be given 1356 1324 void rowName(Row r, const std::string& name) { 1357 _setRowName( _rows(id(r)), name);1325 _setRowName(rows(id(r)), name); 1358 1326 } 1359 1327 … … 1364 1332 Row rowByName(const std::string& name) const { 1365 1333 int k = _rowByName(name); 1366 return k != -1 ? Row( _rows[k]) : Row(INVALID);1334 return k != -1 ? Row(rows[k]) : Row(INVALID); 1367 1335 } 1368 1336 … … 1373 1341 ///\param val is the new value of the coefficient 1374 1342 void coeff(Row r, Col c, Value val) { 1375 _setCoeff( _rows(id(r)),_cols(id(c)), val);1343 _setCoeff(rows(id(r)),cols(id(c)), val); 1376 1344 } 1377 1345 … … 1382 1350 ///\return the corresponding coefficient 1383 1351 Value coeff(Row r, Col c) const { 1384 return _getCoeff( _rows(id(r)),_cols(id(c)));1352 return _getCoeff(rows(id(r)),cols(id(c))); 1385 1353 } 1386 1354 … … 1391 1359 /// Value or -\ref INF. 1392 1360 void colLowerBound(Col c, Value value) { 1393 _setColLowerBound( _cols(id(c)),value);1361 _setColLowerBound(cols(id(c)),value); 1394 1362 } 1395 1363 … … 1400 1368 ///\return The lower bound for column \c c 1401 1369 Value colLowerBound(Col c) const { 1402 return _getColLowerBound( _cols(id(c)));1370 return _getColLowerBound(cols(id(c))); 1403 1371 } 1404 1372 … … 1446 1414 /// Value or \ref INF. 1447 1415 void colUpperBound(Col c, Value value) { 1448 _setColUpperBound( _cols(id(c)),value);1416 _setColUpperBound(cols(id(c)),value); 1449 1417 }; 1450 1418 … … 1455 1423 /// \return The upper bound for column \c c 1456 1424 Value colUpperBound(Col c) const { 1457 return _getColUpperBound( _cols(id(c)));1425 return _getColUpperBound(cols(id(c))); 1458 1426 } 1459 1427 … … 1502 1470 /// Value, -\ref INF or \ref INF. 1503 1471 void colBounds(Col c, Value lower, Value upper) { 1504 _setColLowerBound( _cols(id(c)),lower);1505 _setColUpperBound( _cols(id(c)),upper);1472 _setColLowerBound(cols(id(c)),lower); 1473 _setColUpperBound(cols(id(c)),upper); 1506 1474 } 1507 1475 … … 1548 1516 /// Value or -\ref INF. 1549 1517 void rowLowerBound(Row r, Value value) { 1550 _setRowLowerBound( _rows(id(r)),value);1518 _setRowLowerBound(rows(id(r)),value); 1551 1519 } 1552 1520 … … 1557 1525 ///\return The lower bound for row \c r 1558 1526 Value rowLowerBound(Row r) const { 1559 return _getRowLowerBound( _rows(id(r)));1527 return _getRowLowerBound(rows(id(r))); 1560 1528 } 1561 1529 … … 1566 1534 /// Value or -\ref INF. 1567 1535 void rowUpperBound(Row r, Value value) { 1568 _setRowUpperBound( _rows(id(r)),value);1536 _setRowUpperBound(rows(id(r)),value); 1569 1537 } 1570 1538 … … 1575 1543 ///\return The upper bound for row \c r 1576 1544 Value rowUpperBound(Row r) const { 1577 return _getRowUpperBound( _rows(id(r)));1545 return _getRowUpperBound(rows(id(r))); 1578 1546 } 1579 1547 1580 1548 ///Set an element of the objective function 1581 void objCoeff(Col c, Value v) {_setObjCoeff( _cols(id(c)),v); };1549 void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); }; 1582 1550 1583 1551 ///Get an element of the objective function 1584 Value objCoeff(Col c) const { return _getObjCoeff( _cols(id(c))); };1552 Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); }; 1585 1553 1586 1554 ///Set the objective function … … 1589 1557 /// 1590 1558 void obj(const Expr& e) { 1591 _setObjCoeffs(ExprIterator(e.comps.begin(), _cols),1592 ExprIterator(e.comps.end(), _cols));1559 _setObjCoeffs(ExprIterator(e.comps.begin(), cols), 1560 ExprIterator(e.comps.end(), cols)); 1593 1561 obj_const_comp = *e; 1594 1562 } … … 1600 1568 Expr obj() const { 1601 1569 Expr e; 1602 _getObjCoeffs(InsertIterator(e.comps, _cols));1570 _getObjCoeffs(InsertIterator(e.comps, cols)); 1603 1571 *e = obj_const_comp; 1604 1572 return e; … … 1619 1587 1620 1588 ///Clear the problem 1621 void clear() { _clear(); _rows.clear(); _cols.clear(); }1589 void clear() { _clear(); rows.clear(); cols.clear(); } 1622 1590 1623 1591 /// Set the message level of the solver … … 1962 1930 /// Return the primal value of the column. 1963 1931 /// \pre The problem is solved. 1964 Value primal(Col c) const { return _getPrimal( _cols(id(c))); }1932 Value primal(Col c) const { return _getPrimal(cols(id(c))); } 1965 1933 1966 1934 /// Return the primal value of the expression … … 1989 1957 /// \note Some solvers does not provide primal ray calculation 1990 1958 /// functions. 1991 Value primalRay(Col c) const { return _getPrimalRay( _cols(id(c))); }1959 Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); } 1992 1960 1993 1961 /// Return the dual value of the row … … 1995 1963 /// Return the dual value of the row. 1996 1964 /// \pre The problem is solved. 1997 Value dual(Row r) const { return _getDual( _rows(id(r))); }1965 Value dual(Row r) const { return _getDual(rows(id(r))); } 1998 1966 1999 1967 /// Return the dual value of the dual expression … … 2023 1991 /// \note Some solvers does not provide dual ray calculation 2024 1992 /// functions. 2025 Value dualRay(Row r) const { return _getDualRay( _rows(id(r))); }1993 Value dualRay(Row r) const { return _getDualRay(rows(id(r))); } 2026 1994 2027 1995 /// Return the basis status of the column 2028 1996 2029 1997 /// \see VarStatus 2030 VarStatus colStatus(Col c) const { return _getColStatus( _cols(id(c))); }1998 VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); } 2031 1999 2032 2000 /// Return the basis status of the row 2033 2001 2034 2002 /// \see VarStatus 2035 VarStatus rowStatus(Row r) const { return _getRowStatus( _rows(id(r))); }2003 VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); } 2036 2004 2037 2005 ///The value of the objective function … … 2113 2081 /// 2114 2082 void colType(Col c, ColTypes col_type) { 2115 _setColType( _cols(id(c)),col_type);2083 _setColType(cols(id(c)),col_type); 2116 2084 } 2117 2085 … … 2121 2089 /// 2122 2090 ColTypes colType(Col c) const { 2123 return _getColType( _cols(id(c)));2091 return _getColType(cols(id(c))); 2124 2092 } 2125 2093 ///@} … … 2138 2106 /// Return the value of the row in the solution. 2139 2107 /// \pre The problem is solved. 2140 Value sol(Col c) const { return _getSol( _cols(id(c))); }2108 Value sol(Col c) const { return _getSol(cols(id(c))); } 2141 2109 2142 2110 /// Return the value of the expression in the solution -
lemon/maps.h
r1336 r1270 26 26 27 27 #include <lemon/core.h> 28 #include <lemon/bits/stl_iterators.h>29 28 30 29 ///\file … … 2583 2582 }; 2584 2583 2585 /// \brief STL style iterator for the keys mapped to \c true.2586 ///2587 /// This is an STL style wrapper for \ref TrueIt.2588 /// It can be used in range-based for loops, STL algorithms, etc.2589 LemonRangeWrapper1<TrueIt, IterableBoolMap>2590 trueKeys() {2591 return LemonRangeWrapper1<TrueIt, IterableBoolMap>(*this);2592 }2593 2594 2595 2584 /// \brief Iterator for the keys mapped to \c false. 2596 2585 /// … … 2631 2620 const IterableBoolMap* _map; 2632 2621 }; 2633 2634 /// \brief STL style iterator for the keys mapped to \c false.2635 ///2636 /// This is an STL style wrapper for \ref FalseIt.2637 /// It can be used in range-based for loops, STL algorithms, etc.2638 LemonRangeWrapper1<FalseIt, IterableBoolMap>2639 falseKeys() {2640 return LemonRangeWrapper1<FalseIt, IterableBoolMap>(*this);2641 }2642 2643 2622 2644 2623 /// \brief Iterator for the keys mapped to a given value. … … 2685 2664 const IterableBoolMap* _map; 2686 2665 }; 2687 2688 /// \brief STL style iterator for the keys mapped to a given value.2689 ///2690 /// This is an STL style wrapper for \ref ItemIt.2691 /// It can be used in range-based for loops, STL algorithms, etc.2692 LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>2693 items(bool value) {2694 return LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>(*this, value);2695 }2696 2666 2697 2667 protected: … … 3036 3006 }; 3037 3007 3038 /// \brief STL style iterator for the keys with the same value.3039 ///3040 /// This is an STL style wrapper for \ref ItemIt.3041 /// It can be used in range-based for loops, STL algorithms, etc.3042 LemonRangeWrapper2<ItemIt, IterableIntMap, int>3043 items(int value) {3044 return LemonRangeWrapper2<ItemIt, IterableIntMap, int>(*this, value);3045 }3046 3047 3048 3008 protected: 3049 3009 … … 3289 3249 }; 3290 3250 3291 /// \brief STL style iterator for the keys with the same value.3292 ///3293 /// This is an STL style wrapper for \ref ItemIt.3294 /// It can be used in range-based for loops, STL algorithms, etc.3295 LemonRangeWrapper2<ItemIt, IterableValueMap, V>3296 items(const V& value) {3297 return LemonRangeWrapper2<ItemIt, IterableValueMap, V>(*this, value);3298 }3299 3300 3301 3251 protected: 3302 3252 -
lemon/path.h
r1336 r1270 31 31 #include <lemon/core.h> 32 32 #include <lemon/concepts/path.h> 33 #include <lemon/bits/stl_iterators.h>34 33 35 34 namespace lemon { … … 141 140 int idx; 142 141 }; 143 144 /// \brief Gets the collection of the arcs of the path.145 ///146 /// This function can be used for iterating on the147 /// arcs of the path. It returns a wrapped148 /// ArcIt, which looks like an STL container149 /// (by having begin() and end()) which you can use in range-based150 /// for loops, STL algorithms, etc.151 /// For example you can write:152 ///\code153 /// for(auto a: p.arcs())154 /// doSomething(a);155 ///\endcode156 LemonRangeWrapper1<ArcIt, Path> arcs() const {157 return LemonRangeWrapper1<ArcIt, Path>(*this);158 }159 160 142 161 143 /// \brief Length of the path. … … 364 346 }; 365 347 366 /// \brief Gets the collection of the arcs of the path.367 ///368 /// This function can be used for iterating on the369 /// arcs of the path. It returns a wrapped370 /// ArcIt, which looks like an STL container371 /// (by having begin() and end()) which you can use in range-based372 /// for loops, STL algorithms, etc.373 /// For example you can write:374 ///\code375 /// for(auto a: p.arcs())376 /// doSomething(a);377 ///\endcode378 LemonRangeWrapper1<ArcIt, SimplePath> arcs() const {379 return LemonRangeWrapper1<ArcIt, SimplePath>(*this);380 }381 382 383 348 /// \brief Length of the path. 384 349 int length() const { return data.size(); } … … 578 543 Node *node; 579 544 }; 580 581 /// \brief Gets the collection of the arcs of the path.582 ///583 /// This function can be used for iterating on the584 /// arcs of the path. It returns a wrapped585 /// ArcIt, which looks like an STL container586 /// (by having begin() and end()) which you can use in range-based587 /// for loops, STL algorithms, etc.588 /// For example you can write:589 ///\code590 /// for(auto a: p.arcs())591 /// doSomething(a);592 ///\endcode593 LemonRangeWrapper1<ArcIt, ListPath> arcs() const {594 return LemonRangeWrapper1<ArcIt, ListPath>(*this);595 }596 597 545 598 546 /// \brief The n-th arc. … … 848 796 /// 849 797 /// Default constructor 850 StaticPath() : len(0), _arcs(0) {}798 StaticPath() : len(0), arcs(0) {} 851 799 852 800 /// \brief Copy constructor 853 801 /// 854 StaticPath(const StaticPath& cpath) : _arcs(0) {802 StaticPath(const StaticPath& cpath) : arcs(0) { 855 803 pathCopy(cpath, *this); 856 804 } … … 860 808 /// This path can be initialized from any other path type. 861 809 template <typename CPath> 862 StaticPath(const CPath& cpath) : _arcs(0) {810 StaticPath(const CPath& cpath) : arcs(0) { 863 811 pathCopy(cpath, *this); 864 812 } … … 868 816 /// Destructor of the path 869 817 ~StaticPath() { 870 if ( _arcs) delete[] _arcs;818 if (arcs) delete[] arcs; 871 819 } 872 820 … … 935 883 int idx; 936 884 }; 937 938 /// \brief Gets the collection of the arcs of the path.939 ///940 /// This function can be used for iterating on the941 /// arcs of the path. It returns a wrapped942 /// ArcIt, which looks like an STL container943 /// (by having begin() and end()) which you can use in range-based944 /// for loops, STL algorithms, etc.945 /// For example you can write:946 ///\code947 /// for(auto a: p.arcs())948 /// doSomething(a);949 ///\endcode950 LemonRangeWrapper1<ArcIt, StaticPath> arcs() const {951 return LemonRangeWrapper1<ArcIt, StaticPath>(*this);952 }953 954 885 955 886 /// \brief The n-th arc. … … 957 888 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range. 958 889 const Arc& nth(int n) const { 959 return _arcs[n];890 return arcs[n]; 960 891 } 961 892 … … 974 905 void clear() { 975 906 len = 0; 976 if ( _arcs) delete[] _arcs;977 _arcs = 0;907 if (arcs) delete[] arcs; 908 arcs = 0; 978 909 } 979 910 980 911 /// \brief The first arc of the path. 981 912 const Arc& front() const { 982 return _arcs[0];913 return arcs[0]; 983 914 } 984 915 985 916 /// \brief The last arc of the path. 986 917 const Arc& back() const { 987 return _arcs[len - 1];918 return arcs[len - 1]; 988 919 } 989 920 … … 994 925 void build(const CPath& path) { 995 926 len = path.length(); 996 _arcs = new Arc[len];927 arcs = new Arc[len]; 997 928 int index = 0; 998 929 for (typename CPath::ArcIt it(path); it != INVALID; ++it) { 999 _arcs[index] = it;930 arcs[index] = it; 1000 931 ++index; 1001 932 } … … 1005 936 void buildRev(const CPath& path) { 1006 937 len = path.length(); 1007 _arcs = new Arc[len];938 arcs = new Arc[len]; 1008 939 int index = len; 1009 940 for (typename CPath::RevArcIt it(path); it != INVALID; ++it) { 1010 941 --index; 1011 _arcs[index] = it;942 arcs[index] = it; 1012 943 } 1013 944 } … … 1015 946 private: 1016 947 int len; 1017 Arc* _arcs;948 Arc* arcs; 1018 949 }; 1019 950 … … 1227 1158 }; 1228 1159 1229 /// \brief Gets the collection of the nodes of the path.1230 ///1231 /// This function can be used for iterating on the1232 /// nodes of the path. It returns a wrapped1233 /// PathNodeIt, which looks like an STL container1234 /// (by having begin() and end()) which you can use in range-based1235 /// for loops, STL algorithms, etc.1236 /// For example you can write:1237 ///\code1238 /// for(auto u: pathNodes(g,p))1239 /// doSomething(u);1240 ///\endcode1241 template<typename Path>1242 LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>1243 pathNodes(const typename Path::Digraph &g, const Path &p) {1244 return1245 LemonRangeWrapper2<PathNodeIt<Path>, typename Path::Digraph, Path>(g,p);1246 }1247 1248 1160 ///@} 1249 1161 -
lemon/random.h
r1343 r1340 252 252 current = state + length; 253 253 254 Word *curr = state + length - 1;255 long num;254 register Word *curr = state + length - 1; 255 register long num; 256 256 257 257 num = length - shift; -
lemon/smart_graph.h
r1336 r1270 48 48 }; 49 49 50 std::vector<NodeT> _nodes;51 std::vector<ArcT> _arcs;50 std::vector<NodeT> nodes; 51 std::vector<ArcT> arcs; 52 52 53 53 public: … … 60 60 public: 61 61 62 SmartDigraphBase() : _nodes(), _arcs() { }62 SmartDigraphBase() : nodes(), arcs() { } 63 63 SmartDigraphBase(const SmartDigraphBase &_g) 64 : _nodes(_g._nodes), _arcs(_g._arcs) { }64 : nodes(_g.nodes), arcs(_g.arcs) { } 65 65 66 66 typedef True NodeNumTag; 67 67 typedef True ArcNumTag; 68 68 69 int nodeNum() const { return _nodes.size(); }70 int arcNum() const { return _arcs.size(); }71 72 int maxNodeId() const { return _nodes.size()-1; }73 int maxArcId() const { return _arcs.size()-1; }69 int nodeNum() const { return nodes.size(); } 70 int arcNum() const { return arcs.size(); } 71 72 int maxNodeId() const { return nodes.size()-1; } 73 int maxArcId() const { return arcs.size()-1; } 74 74 75 75 Node addNode() { 76 int n = _nodes.size();77 _nodes.push_back(NodeT());78 _nodes[n].first_in = -1;79 _nodes[n].first_out = -1;76 int n = nodes.size(); 77 nodes.push_back(NodeT()); 78 nodes[n].first_in = -1; 79 nodes[n].first_out = -1; 80 80 return Node(n); 81 81 } 82 82 83 83 Arc addArc(Node u, Node v) { 84 int n = _arcs.size();85 _arcs.push_back(ArcT());86 _arcs[n].source = u._id;87 _arcs[n].target = v._id;88 _arcs[n].next_out = _nodes[u._id].first_out;89 _arcs[n].next_in = _nodes[v._id].first_in;90 _nodes[u._id].first_out = _nodes[v._id].first_in = n;84 int n = arcs.size(); 85 arcs.push_back(ArcT()); 86 arcs[n].source = u._id; 87 arcs[n].target = v._id; 88 arcs[n].next_out = nodes[u._id].first_out; 89 arcs[n].next_in = nodes[v._id].first_in; 90 nodes[u._id].first_out = nodes[v._id].first_in = n; 91 91 92 92 return Arc(n); … … 94 94 95 95 void clear() { 96 _arcs.clear();97 _nodes.clear();98 } 99 100 Node source(Arc a) const { return Node( _arcs[a._id].source); }101 Node target(Arc a) const { return Node( _arcs[a._id].target); }96 arcs.clear(); 97 nodes.clear(); 98 } 99 100 Node source(Arc a) const { return Node(arcs[a._id].source); } 101 Node target(Arc a) const { return Node(arcs[a._id].target); } 102 102 103 103 static int id(Node v) { return v._id; } … … 108 108 109 109 bool valid(Node n) const { 110 return n._id >= 0 && n._id < static_cast<int>( _nodes.size());110 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 111 111 } 112 112 bool valid(Arc a) const { 113 return a._id >= 0 && a._id < static_cast<int>( _arcs.size());113 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 114 114 } 115 115 … … 146 146 147 147 void first(Node& node) const { 148 node._id = _nodes.size() - 1;148 node._id = nodes.size() - 1; 149 149 } 150 150 … … 154 154 155 155 void first(Arc& arc) const { 156 arc._id = _arcs.size() - 1;156 arc._id = arcs.size() - 1; 157 157 } 158 158 … … 162 162 163 163 void firstOut(Arc& arc, const Node& node) const { 164 arc._id = _nodes[node._id].first_out;164 arc._id = nodes[node._id].first_out; 165 165 } 166 166 167 167 void nextOut(Arc& arc) const { 168 arc._id = _arcs[arc._id].next_out;168 arc._id = arcs[arc._id].next_out; 169 169 } 170 170 171 171 void firstIn(Arc& arc, const Node& node) const { 172 arc._id = _nodes[node._id].first_in;172 arc._id = nodes[node._id].first_in; 173 173 } 174 174 175 175 void nextIn(Arc& arc) const { 176 arc._id = _arcs[arc._id].next_in;176 arc._id = arcs[arc._id].next_in; 177 177 } 178 178 … … 267 267 { 268 268 Node b = addNode(); 269 _nodes[b._id].first_out=_nodes[n._id].first_out;270 _nodes[n._id].first_out=-1;271 for(int i= _nodes[b._id].first_out; i!=-1; i=_arcs[i].next_out) {272 _arcs[i].source=b._id;269 nodes[b._id].first_out=nodes[n._id].first_out; 270 nodes[n._id].first_out=-1; 271 for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) { 272 arcs[i].source=b._id; 273 273 } 274 274 if(connect) addArc(n,b); … … 292 292 /// to build the digraph. 293 293 /// \sa reserveArc() 294 void reserveNode(int n) { _nodes.reserve(n); };294 void reserveNode(int n) { nodes.reserve(n); }; 295 295 296 296 /// Reserve memory for arcs. … … 302 302 /// to build the digraph. 303 303 /// \sa reserveNode() 304 void reserveArc(int m) { _arcs.reserve(m); };304 void reserveArc(int m) { arcs.reserve(m); }; 305 305 306 306 public: … … 312 312 void restoreSnapshot(const Snapshot &s) 313 313 { 314 while(s.arc_num< _arcs.size()) {315 Arc arc = arcFromId( _arcs.size()-1);314 while(s.arc_num<arcs.size()) { 315 Arc arc = arcFromId(arcs.size()-1); 316 316 Parent::notifier(Arc()).erase(arc); 317 _nodes[_arcs.back().source].first_out=_arcs.back().next_out;318 _nodes[_arcs.back().target].first_in=_arcs.back().next_in;319 _arcs.pop_back();320 } 321 while(s.node_num< _nodes.size()) {322 Node node = nodeFromId( _nodes.size()-1);317 nodes[arcs.back().source].first_out=arcs.back().next_out; 318 nodes[arcs.back().target].first_in=arcs.back().next_in; 319 arcs.pop_back(); 320 } 321 while(s.node_num<nodes.size()) { 322 Node node = nodeFromId(nodes.size()-1); 323 323 Parent::notifier(Node()).erase(node); 324 _nodes.pop_back();324 nodes.pop_back(); 325 325 } 326 326 } … … 363 363 /// 364 364 Snapshot(SmartDigraph &gr) : _graph(&gr) { 365 node_num=_graph-> _nodes.size();366 arc_num=_graph-> _arcs.size();365 node_num=_graph->nodes.size(); 366 arc_num=_graph->arcs.size(); 367 367 } 368 368 … … 374 374 void save(SmartDigraph &gr) { 375 375 _graph=&gr; 376 node_num=_graph-> _nodes.size();377 arc_num=_graph-> _arcs.size();376 node_num=_graph->nodes.size(); 377 arc_num=_graph->arcs.size(); 378 378 } 379 379 … … 403 403 }; 404 404 405 std::vector<NodeT> _nodes;406 std::vector<ArcT> _arcs;405 std::vector<NodeT> nodes; 406 std::vector<ArcT> arcs; 407 407 408 408 public: … … 466 466 467 467 SmartGraphBase() 468 : _nodes(), _arcs() {}468 : nodes(), arcs() {} 469 469 470 470 typedef True NodeNumTag; … … 472 472 typedef True ArcNumTag; 473 473 474 int nodeNum() const { return _nodes.size(); }475 int edgeNum() const { return _arcs.size() / 2; }476 int arcNum() const { return _arcs.size(); }477 478 int maxNodeId() const { return _nodes.size()-1; }479 int maxEdgeId() const { return _arcs.size() / 2 - 1; }480 int maxArcId() const { return _arcs.size()-1; }481 482 Node source(Arc e) const { return Node( _arcs[e._id ^ 1].target); }483 Node target(Arc e) const { return Node( _arcs[e._id].target); }484 485 Node u(Edge e) const { return Node( _arcs[2 * e._id].target); }486 Node v(Edge e) const { return Node( _arcs[2 * e._id + 1].target); }474 int nodeNum() const { return nodes.size(); } 475 int edgeNum() const { return arcs.size() / 2; } 476 int arcNum() const { return arcs.size(); } 477 478 int maxNodeId() const { return nodes.size()-1; } 479 int maxEdgeId() const { return arcs.size() / 2 - 1; } 480 int maxArcId() const { return arcs.size()-1; } 481 482 Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); } 483 Node target(Arc e) const { return Node(arcs[e._id].target); } 484 485 Node u(Edge e) const { return Node(arcs[2 * e._id].target); } 486 Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); } 487 487 488 488 static bool direction(Arc e) { … … 495 495 496 496 void first(Node& node) const { 497 node._id = _nodes.size() - 1;497 node._id = nodes.size() - 1; 498 498 } 499 499 … … 503 503 504 504 void first(Arc& arc) const { 505 arc._id = _arcs.size() - 1;505 arc._id = arcs.size() - 1; 506 506 } 507 507 … … 511 511 512 512 void first(Edge& arc) const { 513 arc._id = _arcs.size() / 2 - 1;513 arc._id = arcs.size() / 2 - 1; 514 514 } 515 515 … … 519 519 520 520 void firstOut(Arc &arc, const Node& v) const { 521 arc._id = _nodes[v._id].first_out;521 arc._id = nodes[v._id].first_out; 522 522 } 523 523 void nextOut(Arc &arc) const { 524 arc._id = _arcs[arc._id].next_out;524 arc._id = arcs[arc._id].next_out; 525 525 } 526 526 527 527 void firstIn(Arc &arc, const Node& v) const { 528 arc._id = (( _nodes[v._id].first_out) ^ 1);528 arc._id = ((nodes[v._id].first_out) ^ 1); 529 529 if (arc._id == -2) arc._id = -1; 530 530 } 531 531 void nextIn(Arc &arc) const { 532 arc._id = (( _arcs[arc._id ^ 1].next_out) ^ 1);532 arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); 533 533 if (arc._id == -2) arc._id = -1; 534 534 } 535 535 536 536 void firstInc(Edge &arc, bool& d, const Node& v) const { 537 int de = _nodes[v._id].first_out;537 int de = nodes[v._id].first_out; 538 538 if (de != -1) { 539 539 arc._id = de / 2; … … 545 545 } 546 546 void nextInc(Edge &arc, bool& d) const { 547 int de = ( _arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);547 int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); 548 548 if (de != -1) { 549 549 arc._id = de / 2; … … 564 564 565 565 bool valid(Node n) const { 566 return n._id >= 0 && n._id < static_cast<int>( _nodes.size());566 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 567 567 } 568 568 bool valid(Arc a) const { 569 return a._id >= 0 && a._id < static_cast<int>( _arcs.size());569 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 570 570 } 571 571 bool valid(Edge e) const { 572 return e._id >= 0 && 2 * e._id < static_cast<int>( _arcs.size());572 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 573 573 } 574 574 575 575 Node addNode() { 576 int n = _nodes.size();577 _nodes.push_back(NodeT());578 _nodes[n].first_out = -1;576 int n = nodes.size(); 577 nodes.push_back(NodeT()); 578 nodes[n].first_out = -1; 579 579 580 580 return Node(n); … … 582 582 583 583 Edge addEdge(Node u, Node v) { 584 int n = _arcs.size();585 _arcs.push_back(ArcT());586 _arcs.push_back(ArcT());587 588 _arcs[n].target = u._id;589 _arcs[n | 1].target = v._id;590 591 _arcs[n].next_out = _nodes[v._id].first_out;592 _nodes[v._id].first_out = n;593 594 _arcs[n | 1].next_out = _nodes[u._id].first_out;595 _nodes[u._id].first_out = (n | 1);584 int n = arcs.size(); 585 arcs.push_back(ArcT()); 586 arcs.push_back(ArcT()); 587 588 arcs[n].target = u._id; 589 arcs[n | 1].target = v._id; 590 591 arcs[n].next_out = nodes[v._id].first_out; 592 nodes[v._id].first_out = n; 593 594 arcs[n | 1].next_out = nodes[u._id].first_out; 595 nodes[u._id].first_out = (n | 1); 596 596 597 597 return Edge(n / 2); … … 599 599 600 600 void clear() { 601 _arcs.clear();602 _nodes.clear();601 arcs.clear(); 602 nodes.clear(); 603 603 } 604 604 … … 702 702 /// to build the graph. 703 703 /// \sa reserveEdge() 704 void reserveNode(int n) { _nodes.reserve(n); };704 void reserveNode(int n) { nodes.reserve(n); }; 705 705 706 706 /// Reserve memory for edges. … … 712 712 /// to build the graph. 713 713 /// \sa reserveNode() 714 void reserveEdge(int m) { _arcs.reserve(2 * m); };714 void reserveEdge(int m) { arcs.reserve(2 * m); }; 715 715 716 716 public: … … 723 723 { 724 724 s._graph = this; 725 s.node_num = _nodes.size();726 s.arc_num = _arcs.size();725 s.node_num = nodes.size(); 726 s.arc_num = arcs.size(); 727 727 } 728 728 729 729 void restoreSnapshot(const Snapshot &s) 730 730 { 731 while(s.arc_num< _arcs.size()) {732 int n= _arcs.size()-1;731 while(s.arc_num<arcs.size()) { 732 int n=arcs.size()-1; 733 733 Edge arc=edgeFromId(n/2); 734 734 Parent::notifier(Edge()).erase(arc); … … 737 737 dir.push_back(arcFromId(n-1)); 738 738 Parent::notifier(Arc()).erase(dir); 739 _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;740 _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;741 _arcs.pop_back();742 _arcs.pop_back();743 } 744 while(s.node_num< _nodes.size()) {745 int n= _nodes.size()-1;739 nodes[arcs[n-1].target].first_out=arcs[n].next_out; 740 nodes[arcs[n].target].first_out=arcs[n-1].next_out; 741 arcs.pop_back(); 742 arcs.pop_back(); 743 } 744 while(s.node_num<nodes.size()) { 745 int n=nodes.size()-1; 746 746 Node node = nodeFromId(n); 747 747 Parent::notifier(Node()).erase(node); 748 _nodes.pop_back();748 nodes.pop_back(); 749 749 } 750 750 } … … 826 826 }; 827 827 828 std::vector<NodeT> _nodes;829 std::vector<ArcT> _arcs;828 std::vector<NodeT> nodes; 829 std::vector<ArcT> arcs; 830 830 831 831 int first_red, first_blue; … … 916 916 917 917 SmartBpGraphBase() 918 : _nodes(), _arcs(), first_red(-1), first_blue(-1),918 : nodes(), arcs(), first_red(-1), first_blue(-1), 919 919 max_red(-1), max_blue(-1) {} 920 920 … … 923 923 typedef True ArcNumTag; 924 924 925 int nodeNum() const { return _nodes.size(); }925 int nodeNum() const { return nodes.size(); } 926 926 int redNum() const { return max_red + 1; } 927 927 int blueNum() const { return max_blue + 1; } 928 int edgeNum() const { return _arcs.size() / 2; }929 int arcNum() const { return _arcs.size(); }930 931 int maxNodeId() const { return _nodes.size()-1; }928 int edgeNum() const { return arcs.size() / 2; } 929 int arcNum() const { return arcs.size(); } 930 931 int maxNodeId() const { return nodes.size()-1; } 932 932 int maxRedId() const { return max_red; } 933 933 int maxBlueId() const { return max_blue; } 934 int maxEdgeId() const { return _arcs.size() / 2 - 1; }935 int maxArcId() const { return _arcs.size()-1; }936 937 bool red(Node n) const { return _nodes[n._id].red; }938 bool blue(Node n) const { return ! _nodes[n._id].red; }934 int maxEdgeId() const { return arcs.size() / 2 - 1; } 935 int maxArcId() const { return arcs.size()-1; } 936 937 bool red(Node n) const { return nodes[n._id].red; } 938 bool blue(Node n) const { return !nodes[n._id].red; } 939 939 940 940 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } 941 941 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } 942 942 943 Node source(Arc a) const { return Node( _arcs[a._id ^ 1].target); }944 Node target(Arc a) const { return Node( _arcs[a._id].target); }943 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } 944 Node target(Arc a) const { return Node(arcs[a._id].target); } 945 945 946 946 RedNode redNode(Edge e) const { 947 return RedNode( _arcs[2 * e._id].target);947 return RedNode(arcs[2 * e._id].target); 948 948 } 949 949 BlueNode blueNode(Edge e) const { 950 return BlueNode( _arcs[2 * e._id + 1].target);950 return BlueNode(arcs[2 * e._id + 1].target); 951 951 } 952 952 … … 960 960 961 961 void first(Node& node) const { 962 node._id = _nodes.size() - 1;962 node._id = nodes.size() - 1; 963 963 } 964 964 … … 972 972 973 973 void next(RedNode& node) const { 974 node._id = _nodes[node._id].partition_next;974 node._id = nodes[node._id].partition_next; 975 975 } 976 976 … … 980 980 981 981 void next(BlueNode& node) const { 982 node._id = _nodes[node._id].partition_next;982 node._id = nodes[node._id].partition_next; 983 983 } 984 984 985 985 void first(Arc& arc) const { 986 arc._id = _arcs.size() - 1;986 arc._id = arcs.size() - 1; 987 987 } 988 988 … … 992 992 993 993 void first(Edge& arc) const { 994 arc._id = _arcs.size() / 2 - 1;994 arc._id = arcs.size() / 2 - 1; 995 995 } 996 996 … … 1000 1000 1001 1001 void firstOut(Arc &arc, const Node& v) const { 1002 arc._id = _nodes[v._id].first_out;1002 arc._id = nodes[v._id].first_out; 1003 1003 } 1004 1004 void nextOut(Arc &arc) const { 1005 arc._id = _arcs[arc._id].next_out;1005 arc._id = arcs[arc._id].next_out; 1006 1006 } 1007 1007 1008 1008 void firstIn(Arc &arc, const Node& v) const { 1009 arc._id = (( _nodes[v._id].first_out) ^ 1);1009 arc._id = ((nodes[v._id].first_out) ^ 1); 1010 1010 if (arc._id == -2) arc._id = -1; 1011 1011 } 1012 1012 void nextIn(Arc &arc) const { 1013 arc._id = (( _arcs[arc._id ^ 1].next_out) ^ 1);1013 arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); 1014 1014 if (arc._id == -2) arc._id = -1; 1015 1015 } 1016 1016 1017 1017 void firstInc(Edge &arc, bool& d, const Node& v) const { 1018 int de = _nodes[v._id].first_out;1018 int de = nodes[v._id].first_out; 1019 1019 if (de != -1) { 1020 1020 arc._id = de / 2; … … 1026 1026 } 1027 1027 void nextInc(Edge &arc, bool& d) const { 1028 int de = ( _arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);1028 int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); 1029 1029 if (de != -1) { 1030 1030 arc._id = de / 2; … … 1037 1037 1038 1038 static int id(Node v) { return v._id; } 1039 int id(RedNode v) const { return _nodes[v._id].partition_index; }1040 int id(BlueNode v) const { return _nodes[v._id].partition_index; }1039 int id(RedNode v) const { return nodes[v._id].partition_index; } 1040 int id(BlueNode v) const { return nodes[v._id].partition_index; } 1041 1041 static int id(Arc e) { return e._id; } 1042 1042 static int id(Edge e) { return e._id; } … … 1047 1047 1048 1048 bool valid(Node n) const { 1049 return n._id >= 0 && n._id < static_cast<int>( _nodes.size());1049 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 1050 1050 } 1051 1051 bool valid(Arc a) const { 1052 return a._id >= 0 && a._id < static_cast<int>( _arcs.size());1052 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 1053 1053 } 1054 1054 bool valid(Edge e) const { 1055 return e._id >= 0 && 2 * e._id < static_cast<int>( _arcs.size());1055 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 1056 1056 } 1057 1057 1058 1058 RedNode addRedNode() { 1059 int n = _nodes.size();1060 _nodes.push_back(NodeT());1061 _nodes[n].first_out = -1;1062 _nodes[n].red = true;1063 _nodes[n].partition_index = ++max_red;1064 _nodes[n].partition_next = first_red;1059 int n = nodes.size(); 1060 nodes.push_back(NodeT()); 1061 nodes[n].first_out = -1; 1062 nodes[n].red = true; 1063 nodes[n].partition_index = ++max_red; 1064 nodes[n].partition_next = first_red; 1065 1065 first_red = n; 1066 1066 … … 1069 1069 1070 1070 BlueNode addBlueNode() { 1071 int n = _nodes.size();1072 _nodes.push_back(NodeT());1073 _nodes[n].first_out = -1;1074 _nodes[n].red = false;1075 _nodes[n].partition_index = ++max_blue;1076 _nodes[n].partition_next = first_blue;1071 int n = nodes.size(); 1072 nodes.push_back(NodeT()); 1073 nodes[n].first_out = -1; 1074 nodes[n].red = false; 1075 nodes[n].partition_index = ++max_blue; 1076 nodes[n].partition_next = first_blue; 1077 1077 first_blue = n; 1078 1078 … … 1081 1081 1082 1082 Edge addEdge(RedNode u, BlueNode v) { 1083 int n = _arcs.size();1084 _arcs.push_back(ArcT());1085 _arcs.push_back(ArcT());1086 1087 _arcs[n].target = u._id;1088 _arcs[n | 1].target = v._id;1089 1090 _arcs[n].next_out = _nodes[v._id].first_out;1091 _nodes[v._id].first_out = n;1092 1093 _arcs[n | 1].next_out = _nodes[u._id].first_out;1094 _nodes[u._id].first_out = (n | 1);1083 int n = arcs.size(); 1084 arcs.push_back(ArcT()); 1085 arcs.push_back(ArcT()); 1086 1087 arcs[n].target = u._id; 1088 arcs[n | 1].target = v._id; 1089 1090 arcs[n].next_out = nodes[v._id].first_out; 1091 nodes[v._id].first_out = n; 1092 1093 arcs[n | 1].next_out = nodes[u._id].first_out; 1094 nodes[u._id].first_out = (n | 1); 1095 1095 1096 1096 return Edge(n / 2); … … 1098 1098 1099 1099 void clear() { 1100 _arcs.clear();1101 _nodes.clear();1100 arcs.clear(); 1101 nodes.clear(); 1102 1102 first_red = -1; 1103 1103 first_blue = -1; … … 1214 1214 /// to build the graph. 1215 1215 /// \sa reserveEdge() 1216 void reserveNode(int n) { _nodes.reserve(n); };1216 void reserveNode(int n) { nodes.reserve(n); }; 1217 1217 1218 1218 /// Reserve memory for edges. … … 1224 1224 /// to build the graph. 1225 1225 /// \sa reserveNode() 1226 void reserveEdge(int m) { _arcs.reserve(2 * m); };1226 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1227 1227 1228 1228 public: … … 1235 1235 { 1236 1236 s._graph = this; 1237 s.node_num = _nodes.size();1238 s.arc_num = _arcs.size();1237 s.node_num = nodes.size(); 1238 s.arc_num = arcs.size(); 1239 1239 } 1240 1240 1241 1241 void restoreSnapshot(const Snapshot &s) 1242 1242 { 1243 while(s.arc_num< _arcs.size()) {1244 int n= _arcs.size()-1;1243 while(s.arc_num<arcs.size()) { 1244 int n=arcs.size()-1; 1245 1245 Edge arc=edgeFromId(n/2); 1246 1246 Parent::notifier(Edge()).erase(arc); … … 1249 1249 dir.push_back(arcFromId(n-1)); 1250 1250 Parent::notifier(Arc()).erase(dir); 1251 _nodes[_arcs[n-1].target].first_out=_arcs[n].next_out;1252 _nodes[_arcs[n].target].first_out=_arcs[n-1].next_out;1253 _arcs.pop_back();1254 _arcs.pop_back();1255 } 1256 while(s.node_num< _nodes.size()) {1257 int n= _nodes.size()-1;1251 nodes[arcs[n-1].target].first_out=arcs[n].next_out; 1252 nodes[arcs[n].target].first_out=arcs[n-1].next_out; 1253 arcs.pop_back(); 1254 arcs.pop_back(); 1255 } 1256 while(s.node_num<nodes.size()) { 1257 int n=nodes.size()-1; 1258 1258 Node node = nodeFromId(n); 1259 1259 if (Parent::red(node)) { 1260 first_red = _nodes[n].partition_next;1260 first_red = nodes[n].partition_next; 1261 1261 if (first_red != -1) { 1262 max_red = _nodes[first_red].partition_index;1262 max_red = nodes[first_red].partition_index; 1263 1263 } else { 1264 1264 max_red = -1; … … 1266 1266 Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node)); 1267 1267 } else { 1268 first_blue = _nodes[n].partition_next;1268 first_blue = nodes[n].partition_next; 1269 1269 if (first_blue != -1) { 1270 max_blue = _nodes[first_blue].partition_index;1270 max_blue = nodes[first_blue].partition_index; 1271 1271 } else { 1272 1272 max_blue = -1; … … 1275 1275 } 1276 1276 Parent::notifier(Node()).erase(node); 1277 _nodes.pop_back();1277 nodes.pop_back(); 1278 1278 } 1279 1279 } -
lemon/soplex.cc
r1336 r1270 38 38 39 39 SoplexLp::SoplexLp(const SoplexLp& lp) { 40 _rows = lp._rows;41 _cols = lp._cols;40 rows = lp.rows; 41 cols = lp.cols; 42 42 43 43 soplex = new soplex::SoPlex; … … 123 123 124 124 void SoplexLp::_eraseColId(int i) { 125 _cols.eraseIndex(i);126 _cols.relocateIndex(i, _cols.maxIndex());125 cols.eraseIndex(i); 126 cols.relocateIndex(i, cols.maxIndex()); 127 127 } 128 128 void SoplexLp::_eraseRowId(int i) { 129 _rows.eraseIndex(i);130 _rows.relocateIndex(i, _rows.maxIndex());129 rows.eraseIndex(i); 130 rows.relocateIndex(i, rows.maxIndex()); 131 131 } 132 132 … … 433 433 _row_names.clear(); 434 434 _row_names_ref.clear(); 435 _cols.clear();436 _rows.clear();435 cols.clear(); 436 rows.clear(); 437 437 _clear_temporals(); 438 438 } -
test/bellman_ford_test.cc
r1337 r1270 102 102 103 103 for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} 104 for (auto n: const_bf_test.activeNodes()) { ::lemon::ignore_unused_variable_warning(n); }105 for (Digraph::Node n: const_bf_test.activeNodes()) {106 ::lemon::ignore_unused_variable_warning(n);107 }108 104 } 109 105 { -
test/graph_test.h
r1337 r1270 39 39 check(n==INVALID,"Wrong Node list linking."); 40 40 check(countNodes(G)==cnt,"Wrong Node number."); 41 42 #ifdef LEMON_CXX1143 {44 typename Graph::NodeIt n(G);45 for(auto u: G.nodes())46 {47 check(n==u,"Wrong STL Node iterator.");48 ++n;49 }50 check(n==INVALID,"Wrong STL Node iterator.");51 }52 {53 typename Graph::NodeIt n(G);54 for(typename Graph::Node u: G.nodes())55 {56 check(n==u,"Wrong STL Node iterator.");57 ++n;58 }59 check(n==INVALID,"Wrong STL Node iterator.");60 }61 #endif62 41 } 63 42 … … 78 57 check(n==INVALID,"Wrong red Node list linking."); 79 58 check(countRedNodes(G)==cnt,"Wrong red Node number."); 80 #ifdef LEMON_CXX1181 {82 typename Graph::RedNodeIt n(G);83 for(auto u: G.redNodes())84 {85 check(n==u,"Wrong STL RedNode iterator.");86 ++n;87 }88 check(n==INVALID,"Wrong STL RedNode iterator.");89 }90 {91 typename Graph::RedNodeIt n(G);92 for(typename Graph::RedNode u: G.redNodes())93 {94 check(n==u,"Wrong STL RedNode iterator.");95 ++n;96 }97 check(n==INVALID,"Wrong STL RedNode iterator.");98 }99 #endif100 59 } 101 60 … … 116 75 check(n==INVALID,"Wrong blue Node list linking."); 117 76 check(countBlueNodes(G)==cnt,"Wrong blue Node number."); 118 #ifdef LEMON_CXX11119 {120 typename Graph::BlueNodeIt n(G);121 for(auto u: G.blueNodes())122 {123 check(n==u,"Wrong STL BlueNode iterator.");124 ++n;125 }126 check(n==INVALID,"Wrong STL BlueNode iterator.");127 }128 {129 typename Graph::BlueNodeIt n(G);130 for(typename Graph::BlueNode u: G.blueNodes())131 {132 check(n==u,"Wrong STL BlueNode iterator.");133 ++n;134 }135 check(n==INVALID,"Wrong STL BlueNode iterator.");136 }137 #endif138 139 77 } 140 78 … … 153 91 check(e==INVALID,"Wrong Arc list linking."); 154 92 check(countArcs(G)==cnt,"Wrong Arc number."); 155 #ifdef LEMON_CXX11156 {157 typename Graph::ArcIt a(G);158 for(auto e: G.arcs())159 {160 check(a==e,"Wrong STL Arc iterator.");161 ++a;162 }163 check(a==INVALID,"Wrong STL Arc iterator.");164 }165 {166 typename Graph::ArcIt a(G);167 for(typename Graph::Arc e: G.arcs())168 {169 check(a==e,"Wrong STL Arc iterator.");170 ++a;171 }172 check(a==INVALID,"Wrong STL Arc iterator.");173 }174 #endif175 176 93 } 177 94 … … 189 106 check(e==INVALID,"Wrong OutArc list linking."); 190 107 check(countOutArcs(G,n)==cnt,"Wrong OutArc number."); 191 #ifdef LEMON_CXX11192 {193 typename Graph::OutArcIt a(G,n);194 for(auto e: G.outArcs(n))195 {196 check(a==e,"Wrong STL OutArc iterator.");197 ++a;198 }199 check(a==INVALID,"Wrong STL OutArc iterator.");200 }201 {202 typename Graph::OutArcIt a(G,n);203 for(typename Graph::Arc e: G.outArcs(n))204 {205 check(a==e,"Wrong STL OutArc iterator.");206 ++a;207 }208 check(a==INVALID,"Wrong STL OutArc iterator.");209 }210 #endif211 212 108 } 213 109 … … 225 121 check(e==INVALID,"Wrong InArc list linking."); 226 122 check(countInArcs(G,n)==cnt,"Wrong InArc number."); 227 #ifdef LEMON_CXX11228 {229 typename Graph::InArcIt a(G,n);230 for(auto e: G.inArcs(n))231 {232 check(a==e,"Wrong STL InArc iterator.");233 ++a;234 }235 check(a==INVALID,"Wrong STL InArc iterator.");236 }237 {238 typename Graph::InArcIt a(G,n);239 for(typename Graph::Arc e: G.inArcs(n))240 {241 check(a==e,"Wrong STL InArc iterator.");242 ++a;243 }244 check(a==INVALID,"Wrong STL InArc iterator.");245 }246 #endif247 123 } 248 124 … … 259 135 check(e==INVALID,"Wrong Edge list linking."); 260 136 check(countEdges(G)==cnt,"Wrong Edge number."); 261 #ifdef LEMON_CXX11262 {263 typename Graph::EdgeIt a(G);264 for(auto e: G.edges())265 {266 check(a==e,"Wrong STL Edge iterator.");267 ++a;268 }269 check(a==INVALID,"Wrong STL Edge iterator.");270 }271 {272 typename Graph::EdgeIt a(G);273 for(typename Graph::Edge e: G.edges())274 {275 check(a==e,"Wrong STL Edge iterator.");276 ++a;277 }278 check(a==INVALID,"Wrong STL Edge iterator.");279 }280 #endif281 282 137 } 283 138 … … 296 151 check(e==INVALID,"Wrong IncEdge list linking."); 297 152 check(countIncEdges(G,n)==cnt,"Wrong IncEdge number."); 298 #ifdef LEMON_CXX11299 {300 typename Graph::IncEdgeIt a(G,n);301 for(auto e: G.incEdges(n))302 {303 check(a==e,"Wrong STL IncEdge iterator.");304 ++a;305 }306 check(a==INVALID,"Wrong STL IncEdge iterator.");307 }308 {309 typename Graph::IncEdgeIt a(G,n);310 for(typename Graph::Edge e: G.incEdges(n))311 {312 check(a==e,"Wrong STL IncEdge iterator.");313 ++a;314 }315 check(a==INVALID,"Wrong STL IncEdge iterator.");316 }317 #endif318 319 153 } 320 154 -
test/lp_test.cc
r1337 r1300 21 21 #include "test_tools.h" 22 22 #include <lemon/tolerance.h> 23 #include <lemon/concept_check.h> 23 24 24 #include <lemon/config.h> 25 25 … … 48 48 int count=0; 49 49 for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count; 50 #ifdef LEMON_CXX1151 int cnt = 0;52 for(auto c: lp.cols()) { cnt++; ::lemon::ignore_unused_variable_warning(c); }53 check(count == cnt, "Wrong STL iterator");54 #endif55 50 return count; 56 51 } … … 59 54 int count=0; 60 55 for (LpBase::RowIt r(lp); r!=INVALID; ++r) ++count; 61 #ifdef LEMON_CXX1162 int cnt = 0;63 for(auto r: lp.rows()) { cnt++; ::lemon::ignore_unused_variable_warning(r); }64 check(count == cnt, "Wrong STL iterator");65 #endif66 56 return count; 67 57 } -
test/maps_test.cc
r1337 r1270 731 731 check(n == 3, "Wrong number"); 732 732 check(map1.falseNum() == 3, "Wrong number"); 733 734 #ifdef LEMON_CXX11735 {736 int c = 0;737 for(auto v: map1.items(false)) { c++; ::lemon::ignore_unused_variable_warning(v); }738 check(c == map1.falseNum(), "Wrong number");739 }740 {741 int c = 0;742 for(auto v: map1.items(true)) { c++; ::lemon::ignore_unused_variable_warning(v); }743 check(c == map1.trueNum(), "Wrong number");744 }745 {746 int c = 0;747 for(auto v: map1.falseKeys()) { c++; ::lemon::ignore_unused_variable_warning(v); }748 check(c == map1.falseNum(), "Wrong number");749 }750 {751 int c = 0;752 for(auto v: map1.trueKeys()) { c++; ::lemon::ignore_unused_variable_warning(v); }753 check(c == map1.trueNum(), "Wrong number");754 }755 #endif756 757 733 } 758 734 … … 805 781 } 806 782 check(n == num, "Wrong number"); 807 #ifdef LEMON_CXX11808 {809 int c = 0;810 for(auto v: map1.items(0)) { c++; ::lemon::ignore_unused_variable_warning(v); }811 check(c == (num + 1) / 2, "Wrong number");812 for(auto v: map1.items(1)) { c++; ::lemon::ignore_unused_variable_warning(v); }813 check(c == num, "Wrong number");814 }815 #endif816 783 817 784 } … … 872 839 } 873 840 check(n == num, "Wrong number"); 874 875 #ifdef LEMON_CXX11876 {877 int c = 0;878 for(auto v: map1.items(0.0)) { c++; ::lemon::ignore_unused_variable_warning(v); }879 check(c == (num + 1) / 2, "Wrong number");880 for(auto v: map1.items(1.0)) { c++; ::lemon::ignore_unused_variable_warning(v); }881 check(c == num, "Wrong number");882 }883 #endif884 841 885 842 }
Note: See TracChangeset
for help on using the changeset viewer.