Changes in / [904:b9b2e8abe70b:903:207ba6c0f2e4] in lemon
- Files:
-
- 4 deleted
- 22 edited
Legend:
- Unmodified
- Added
- Removed
-
INSTALL
r890 r615 174 174 175 175 Disable COIN-OR support. 176 177 178 Makefile Variables179 ==================180 181 Some Makefile variables are reserved by the GNU Coding Standards for182 the use of the "user" - the person building the package. For instance,183 CXX and CXXFLAGS are such variables, and have the same meaning as184 explained in the previous section. These variables can be set on the185 command line when invoking `make' like this:186 `make [VARIABLE=VALUE]...'187 188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us189 to hold several compiler flags related to warnings. Its default value190 can be overridden when invoking `make'. For example to disable all191 warning flags use `make WARNINGCXXFLAGS='.192 193 In order to turn off a single flag from the default set of warning194 flags, you can use the CXXFLAGS variable, since this is passed after195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is196 used by default when g++ is detected) you can use197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'. -
doc/CMakeLists.txt
r895 r791 27 27 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 28 28 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps30 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 31 30 COMMAND ${CMAKE_COMMAND} -E remove_directory html -
doc/Makefile.am
r895 r791 29 29 edge_biconnected_components.eps \ 30 30 node_biconnected_components.eps \ 31 planar.eps \32 31 strongly_connected_components.eps 33 32 -
doc/groups.dox
r879 r818 407 407 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 409 - \ref CostScaling Cost Scaling algorithm based on push/augment and410 relabel operations\ref goldberg90approximation, \ref goldberg97efficient,409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, 411 411 \ref bunnagel98efficient. 412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 413 shortest path method \ref edmondskarp72theoretical. 414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 415 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 413 capacity scaling \ref edmondskarp72theoretical. 414 - \ref CancelAndTighten The Cancel and Tighten algorithm 415 \ref goldberg89cyclecanceling. 416 - \ref CycleCanceling Cycle-Canceling algorithms 417 \ref klein67primal, \ref goldberg89cyclecanceling. 416 418 417 419 In general NetworkSimplex is the most efficient implementation, -
lemon/Makefile.am
r888 r863 63 63 lemon/binom_heap.h \ 64 64 lemon/bucket_heap.h \ 65 lemon/capacity_scaling.h \66 65 lemon/cbc.h \ 67 66 lemon/circulation.h \ … … 70 69 lemon/concept_check.h \ 71 70 lemon/connectivity.h \ 71 lemon/counter.h \ 72 72 lemon/core.h \ 73 lemon/cost_scaling.h \74 lemon/counter.h \75 73 lemon/cplex.h \ 76 lemon/cycle_canceling.h \77 74 lemon/dfs.h \ 78 75 lemon/dijkstra.h \ -
lemon/bellman_ford.h
r891 r835 172 172 /// the lengths of the arcs. The default map type is 173 173 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 174 /// \tparam TR The traits class that defines various types used by the175 /// algorithm. By default, it is \ref BellmanFordDefaultTraits176 /// "BellmanFordDefaultTraits<GR, LEN>".177 /// In most cases, this parameter should not be set directly,178 /// consider to use the named template parameters instead.179 174 #ifdef DOXYGEN 180 175 template <typename GR, typename LEN, typename TR> … … 243 238 _dist = Traits::createDistMap(*_gr); 244 239 } 245 if(!_mask) { 246 _mask = new MaskMap(*_gr); 247 } 240 _mask = new MaskMap(*_gr, false); 248 241 } 249 242 … … 411 404 _process.push_back(it); 412 405 _mask->set(it, true); 413 }414 } else {415 for (NodeIt it(*_gr); it != INVALID; ++it) {416 _mask->set(it, false);417 406 } 418 407 } … … 939 928 /// This class should only be used through the \ref bellmanFord() 940 929 /// function, which makes it easier to use the algorithm. 941 ///942 /// \tparam TR The traits class that defines various types used by the943 /// algorithm.944 930 template<class TR> 945 931 class BellmanFordWizard : public TR { -
lemon/bfs.h
r891 r835 122 122 ///\tparam GR The type of the digraph the algorithm runs on. 123 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the125 ///algorithm. By default, it is \ref BfsDefaultTraits126 ///"BfsDefaultTraits<GR>".127 ///In most cases, this parameter should not be set directly,128 ///consider to use the named template parameters instead.129 124 #ifdef DOXYGEN 130 125 template <typename GR, … … 963 958 /// This class should only be used through the \ref bfs() function, 964 959 /// which makes it easier to use the algorithm. 965 ///966 /// \tparam TR The traits class that defines various types used by the967 /// algorithm.968 960 template<class TR> 969 961 class BfsWizard : public TR … … 1304 1296 /// does not observe the BFS events. If you want to observe the BFS 1305 1297 /// events, you should implement your own visitor class. 1306 /// \tparam TR T he traits class that defines varioustypes used by the1307 /// algorithm. By default, it is \ref BfsVisitDefaultTraits1308 /// "BfsVisitDefaultTraits<GR>".1309 /// In most cases, this parameter should not be set directly,1310 /// consider to use the named template parameters instead.1298 /// \tparam TR Traits class to set various data types used by the 1299 /// algorithm. The default traits class is 1300 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>". 1301 /// See \ref BfsVisitDefaultTraits for the documentation of 1302 /// a BFS visit traits class. 1311 1303 #ifdef DOXYGEN 1312 1304 template <typename GR, typename VS, typename TR> -
lemon/bits/map_extender.h
r867 r765 85 85 typedef typename Map::Value Value; 86 86 87 MapIt() : map(NULL){}88 89 MapIt(Invalid i) : Parent(i) , map(NULL) {}90 91 explicit MapIt(Map& _map) : map( &_map) {92 map ->notifier()->first(*this);87 MapIt() {} 88 89 MapIt(Invalid i) : Parent(i) { } 90 91 explicit MapIt(Map& _map) : map(_map) { 92 map.notifier()->first(*this); 93 93 } 94 94 95 95 MapIt(const Map& _map, const Item& item) 96 : Parent(item), map( &_map) {}96 : Parent(item), map(_map) {} 97 97 98 98 MapIt& operator++() { 99 map ->notifier()->next(*this);99 map.notifier()->next(*this); 100 100 return *this; 101 101 } 102 102 103 103 typename MapTraits<Map>::ConstReturnValue operator*() const { 104 return (*map)[*this];104 return map[*this]; 105 105 } 106 106 107 107 typename MapTraits<Map>::ReturnValue operator*() { 108 return (*map)[*this];108 return map[*this]; 109 109 } 110 110 111 111 void set(const Value& value) { 112 map ->set(*this, value);113 } 114 115 protected: 116 Map *map;112 map.set(*this, value); 113 } 114 115 protected: 116 Map& map; 117 117 118 118 }; … … 125 125 typedef typename Map::Value Value; 126 126 127 ConstMapIt() : map(NULL){}128 129 ConstMapIt(Invalid i) : Parent(i) , map(NULL) {}130 131 explicit ConstMapIt(Map& _map) : map( &_map) {132 map ->notifier()->first(*this);127 ConstMapIt() {} 128 129 ConstMapIt(Invalid i) : Parent(i) { } 130 131 explicit ConstMapIt(Map& _map) : map(_map) { 132 map.notifier()->first(*this); 133 133 } 134 134 … … 137 137 138 138 ConstMapIt& operator++() { 139 map ->notifier()->next(*this);139 map.notifier()->next(*this); 140 140 return *this; 141 141 } … … 146 146 147 147 protected: 148 const Map *map;148 const Map& map; 149 149 }; 150 150 … … 153 153 154 154 public: 155 ItemIt() : map(NULL) {} 156 157 158 ItemIt(Invalid i) : Parent(i) , map(NULL) {}159 160 explicit ItemIt(Map& _map) : map( &_map) {161 map ->notifier()->first(*this);155 156 ItemIt() {} 157 158 ItemIt(Invalid i) : Parent(i) { } 159 160 explicit ItemIt(Map& _map) : map(_map) { 161 map.notifier()->first(*this); 162 162 } 163 163 164 164 ItemIt(const Map& _map, const Item& item) 165 : Parent(item), map( &_map) {}165 : Parent(item), map(_map) {} 166 166 167 167 ItemIt& operator++() { 168 map ->notifier()->next(*this);169 return *this; 170 } 171 172 protected: 173 const Map *map;168 map.notifier()->next(*this); 169 return *this; 170 } 171 172 protected: 173 const Map& map; 174 174 175 175 }; … … 232 232 typedef typename Map::Value Value; 233 233 234 MapIt() : map(NULL){}235 236 MapIt(Invalid i) : Parent(i) , map(NULL){ }237 238 explicit MapIt(Map& _map) : map( &_map) {239 map ->graph.first(*this);234 MapIt() {} 235 236 MapIt(Invalid i) : Parent(i) { } 237 238 explicit MapIt(Map& _map) : map(_map) { 239 map.graph.first(*this); 240 240 } 241 241 242 242 MapIt(const Map& _map, const Item& item) 243 : Parent(item), map( &_map) {}243 : Parent(item), map(_map) {} 244 244 245 245 MapIt& operator++() { 246 map ->graph.next(*this);246 map.graph.next(*this); 247 247 return *this; 248 248 } 249 249 250 250 typename MapTraits<Map>::ConstReturnValue operator*() const { 251 return (*map)[*this];251 return map[*this]; 252 252 } 253 253 254 254 typename MapTraits<Map>::ReturnValue operator*() { 255 return (*map)[*this];255 return map[*this]; 256 256 } 257 257 258 258 void set(const Value& value) { 259 map ->set(*this, value);260 } 261 262 protected: 263 Map *map;259 map.set(*this, value); 260 } 261 262 protected: 263 Map& map; 264 264 265 265 }; … … 272 272 typedef typename Map::Value Value; 273 273 274 ConstMapIt() : map(NULL){}275 276 ConstMapIt(Invalid i) : Parent(i) , map(NULL){ }277 278 explicit ConstMapIt(Map& _map) : map( &_map) {279 map ->graph.first(*this);274 ConstMapIt() {} 275 276 ConstMapIt(Invalid i) : Parent(i) { } 277 278 explicit ConstMapIt(Map& _map) : map(_map) { 279 map.graph.first(*this); 280 280 } 281 281 282 282 ConstMapIt(const Map& _map, const Item& item) 283 : Parent(item), map( &_map) {}283 : Parent(item), map(_map) {} 284 284 285 285 ConstMapIt& operator++() { 286 map ->graph.next(*this);286 map.graph.next(*this); 287 287 return *this; 288 288 } 289 289 290 290 typename MapTraits<Map>::ConstReturnValue operator*() const { 291 return (*map)[*this];292 } 293 294 protected: 295 const Map *map;291 return map[*this]; 292 } 293 294 protected: 295 const Map& map; 296 296 }; 297 297 … … 300 300 301 301 public: 302 ItemIt() : map(NULL) {} 303 304 305 ItemIt(Invalid i) : Parent(i) , map(NULL){ }306 307 explicit ItemIt(Map& _map) : map( &_map) {308 map ->graph.first(*this);302 303 ItemIt() {} 304 305 ItemIt(Invalid i) : Parent(i) { } 306 307 explicit ItemIt(Map& _map) : map(_map) { 308 map.graph.first(*this); 309 309 } 310 310 311 311 ItemIt(const Map& _map, const Item& item) 312 : Parent(item), map( &_map) {}312 : Parent(item), map(_map) {} 313 313 314 314 ItemIt& operator++() { 315 map ->graph.next(*this);316 return *this; 317 } 318 319 protected: 320 const Map *map;315 map.graph.next(*this); 316 return *this; 317 } 318 319 protected: 320 const Map& map; 321 321 322 322 }; -
lemon/circulation.h
r891 r833 174 174 \tparam SM The type of the supply map. The default map type is 175 175 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". 176 \tparam TR The traits class that defines various types used by the177 algorithm. By default, it is \ref CirculationDefaultTraits178 "CirculationDefaultTraits<GR, LM, UM, SM>".179 In most cases, this parameter should not be set directly,180 consider to use the named template parameters instead.181 176 */ 182 177 #ifdef DOXYGEN -
lemon/concepts/heap.h
r883 r757 89 89 /// handle the cross references. The assigned value must be 90 90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 91 #ifdef DOXYGEN92 91 explicit Heap(ItemIntMap &map) {} 93 #else94 explicit Heap(ItemIntMap&) {}95 #endif96 92 97 93 /// \brief Constructor. … … 103 99 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 104 100 /// \param comp The function object used for comparing the priorities. 105 #ifdef DOXYGEN106 101 explicit Heap(ItemIntMap &map, const CMP &comp) {} 107 #else108 explicit Heap(ItemIntMap&, const CMP&) {}109 #endif110 102 111 103 /// \brief The number of items stored in the heap. … … 135 127 /// \param p The priority of the item. 136 128 /// \pre \e i must not be stored in the heap. 137 #ifdef DOXYGEN138 129 void push(const Item &i, const Prio &p) {} 139 #else140 void push(const Item&, const Prio&) {}141 #endif142 130 143 131 /// \brief Return the item having minimum priority. … … 145 133 /// This function returns the item having minimum priority. 146 134 /// \pre The heap must be non-empty. 147 Item top() const { return Item();}135 Item top() const {} 148 136 149 137 /// \brief The minimum priority. … … 151 139 /// This function returns the minimum priority. 152 140 /// \pre The heap must be non-empty. 153 Prio prio() const { return Prio();}141 Prio prio() const {} 154 142 155 143 /// \brief Remove the item having minimum priority. … … 165 153 /// \param i The item to delete. 166 154 /// \pre \e i must be in the heap. 167 #ifdef DOXYGEN168 155 void erase(const Item &i) {} 169 #else170 void erase(const Item&) {}171 #endif172 156 173 157 /// \brief The priority of the given item. … … 176 160 /// \param i The item. 177 161 /// \pre \e i must be in the heap. 178 #ifdef DOXYGEN179 162 Prio operator[](const Item &i) const {} 180 #else181 Prio operator[](const Item&) const { return Prio(); }182 #endif183 163 184 164 /// \brief Set the priority of an item or insert it, if it is … … 191 171 /// \param i The item. 192 172 /// \param p The priority. 193 #ifdef DOXYGEN194 173 void set(const Item &i, const Prio &p) {} 195 #else196 void set(const Item&, const Prio&) {}197 #endif198 174 199 175 /// \brief Decrease the priority of an item to the given value. … … 203 179 /// \param p The priority. 204 180 /// \pre \e i must be stored in the heap with priority at least \e p. 205 #ifdef DOXYGEN206 181 void decrease(const Item &i, const Prio &p) {} 207 #else208 void decrease(const Item&, const Prio&) {}209 #endif210 182 211 183 /// \brief Increase the priority of an item to the given value. … … 215 187 /// \param p The priority. 216 188 /// \pre \e i must be stored in the heap with priority at most \e p. 217 #ifdef DOXYGEN218 189 void increase(const Item &i, const Prio &p) {} 219 #else220 void increase(const Item&, const Prio&) {}221 #endif222 190 223 191 /// \brief Return the state of an item. … … 229 197 /// to the heap again. 230 198 /// \param i The item. 231 #ifdef DOXYGEN232 199 State state(const Item &i) const {} 233 #else234 State state(const Item&) const { return PRE_HEAP; }235 #endif236 200 237 201 /// \brief Set the state of an item in the heap. … … 242 206 /// \param i The item. 243 207 /// \param st The state. It should not be \c IN_HEAP. 244 #ifdef DOXYGEN245 208 void state(const Item& i, State st) {} 246 #else247 void state(const Item&, State) {}248 #endif249 209 250 210 -
lemon/dfs.h
r891 r835 122 122 ///\tparam GR The type of the digraph the algorithm runs on. 123 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the125 ///algorithm. By default, it is \ref DfsDefaultTraits126 ///"DfsDefaultTraits<GR>".127 ///In most cases, this parameter should not be set directly,128 ///consider to use the named template parameters instead.129 124 #ifdef DOXYGEN 130 125 template <typename GR, … … 893 888 /// This class should only be used through the \ref dfs() function, 894 889 /// which makes it easier to use the algorithm. 895 ///896 /// \tparam TR The traits class that defines various types used by the897 /// algorithm.898 890 template<class TR> 899 891 class DfsWizard : public TR … … 1246 1238 /// does not observe the DFS events. If you want to observe the DFS 1247 1239 /// events, you should implement your own visitor class. 1248 /// \tparam TR T he traits class that defines varioustypes used by the1249 /// algorithm. By default, it is \ref DfsVisitDefaultTraits1250 /// "DfsVisitDefaultTraits<GR>".1251 /// In most cases, this parameter should not be set directly,1252 /// consider to use the named template parameters instead.1240 /// \tparam TR Traits class to set various data types used by the 1241 /// algorithm. The default traits class is 1242 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>". 1243 /// See \ref DfsVisitDefaultTraits for the documentation of 1244 /// a DFS visit traits class. 1253 1245 #ifdef DOXYGEN 1254 1246 template <typename GR, typename VS, typename TR> -
lemon/dijkstra.h
r891 r835 193 193 ///it is necessary. The default map type is \ref 194 194 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 195 ///\tparam TR The traits class that defines various types used by the196 ///algorithm. By default, it is \ref DijkstraDefaultTraits197 ///"DijkstraDefaultTraits<GR, LEN>".198 ///In most cases, this parameter should not be set directly,199 ///consider to use the named template parameters instead.200 195 #ifdef DOXYGEN 201 196 template <typename GR, typename LEN, typename TR> … … 1098 1093 /// This class should only be used through the \ref dijkstra() function, 1099 1094 /// which makes it easier to use the algorithm. 1100 ///1101 /// \tparam TR The traits class that defines various types used by the1102 /// algorithm.1103 1095 template<class TR> 1104 1096 class DijkstraWizard : public TR -
lemon/glpk.h
r902 r793 26 26 #include <lemon/lp_base.h> 27 27 28 // forward declaration 29 #if !defined _GLP_PROB && !defined GLP_PROB 30 #define _GLP_PROB 31 #define GLP_PROB 32 typedef struct { double _opaque_prob; } glp_prob; 33 /* LP/MIP problem object */ 34 #endif 35 28 36 namespace lemon { 29 37 30 namespace _solver_bits {31 class VoidPtr {32 private:33 void *_ptr;34 public:35 VoidPtr() : _ptr(0) {}36 37 template <typename T>38 VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}39 40 template <typename T>41 VoidPtr& operator=(T* ptr) {42 _ptr = reinterpret_cast<void*>(ptr);43 return *this;44 }45 46 template <typename T>47 operator T*() const { return reinterpret_cast<T*>(_ptr); }48 };49 }50 38 51 39 /// \brief Base interface for the GLPK LP and MIP solver … … 56 44 protected: 57 45 58 _solver_bits::VoidPtr lp; 46 typedef glp_prob LPX; 47 glp_prob* lp; 59 48 60 49 GlpkBase(); … … 135 124 136 125 ///Pointer to the underlying GLPK data structure. 137 _solver_bits::VoidPtrlpx() {return lp;}126 LPX *lpx() {return lp;} 138 127 ///Const pointer to the underlying GLPK data structure. 139 _solver_bits::VoidPtrlpx() const {return lp;}128 const LPX *lpx() const {return lp;} 140 129 141 130 ///Returns the constraint identifier understood by GLPK. -
lemon/hartmann_orlin.h
r891 r859 107 107 /// \tparam LEN The type of the length map. The default 108 108 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 109 /// \tparam TR The traits class that defines various types used by the110 /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits111 /// "HartmannOrlinDefaultTraits<GR, LEN>".112 /// In most cases, this parameter should not be set directly,113 /// consider to use the named template parameters instead.114 109 #ifdef DOXYGEN 115 110 template <typename GR, typename LEN, typename TR> … … 133 128 /// 134 129 /// The large value type used for internal computations. 135 /// By default, it is \c long \c long if the \c Value type is integer, 130 /// Using the \ref HartmannOrlinDefaultTraits "default traits class", 131 /// it is \c long \c long if the \c Value type is integer, 136 132 /// otherwise it is \c double. 137 133 typedef typename TR::LargeValue LargeValue; -
lemon/howard.h
r891 r818 107 107 /// \tparam LEN The type of the length map. The default 108 108 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 109 /// \tparam TR The traits class that defines various types used by the110 /// algorithm. By default, it is \ref HowardDefaultTraits111 /// "HowardDefaultTraits<GR, LEN>".112 /// In most cases, this parameter should not be set directly,113 /// consider to use the named template parameters instead.114 109 #ifdef DOXYGEN 115 110 template <typename GR, typename LEN, typename TR> … … 133 128 /// 134 129 /// The large value type used for internal computations. 135 /// By default, it is \c long \c long if the \c Value type is integer, 130 /// Using the \ref HowardDefaultTraits "default traits class", 131 /// it is \c long \c long if the \c Value type is integer, 136 132 /// otherwise it is \c double. 137 133 typedef typename TR::LargeValue LargeValue; -
lemon/karp.h
r891 r819 105 105 /// \tparam LEN The type of the length map. The default 106 106 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 107 /// \tparam TR The traits class that defines various types used by the108 /// algorithm. By default, it is \ref KarpDefaultTraits109 /// "KarpDefaultTraits<GR, LEN>".110 /// In most cases, this parameter should not be set directly,111 /// consider to use the named template parameters instead.112 107 #ifdef DOXYGEN 113 108 template <typename GR, typename LEN, typename TR> … … 131 126 /// 132 127 /// The large value type used for internal computations. 133 /// By default, it is \c long \c long if the \c Value type is integer, 128 /// Using the \ref KarpDefaultTraits "default traits class", 129 /// it is \c long \c long if the \c Value type is integer, 134 130 /// otherwise it is \c double. 135 131 typedef typename TR::LargeValue LargeValue; -
lemon/min_cost_arborescence.h
r891 r760 113 113 /// it is necessary. The default map type is \ref 114 114 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 115 /// \tparam TR The traits class that defines various types used by the 116 /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits 115 /// \param TR Traits class to set various data types used 116 /// by the algorithm. The default traits class is 117 /// \ref MinCostArborescenceDefaultTraits 117 118 /// "MinCostArborescenceDefaultTraits<GR, CM>". 118 /// In most cases, this parameter should not be set directly,119 /// consider to use the named template parameters instead.120 119 #ifndef DOXYGEN 121 120 template <typename GR, … … 124 123 MinCostArborescenceDefaultTraits<GR, CM> > 125 124 #else 126 template <typename GR, typename CM, type nameTR>125 template <typename GR, typename CM, typedef TR> 127 126 #endif 128 127 class MinCostArborescence { -
lemon/network_simplex.h
r898 r835 44 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 45 /// \ref kellyoneill91netsimplex. 46 /// This algorithm is a highly efficient specialized version of the47 /// linear programming simplex method directly for the minimum cost48 /// flow problem.46 /// This algorithm is a specialized version of the linear programming 47 /// simplex method directly for the minimum cost flow problem. 48 /// It is one of the most efficient solution methods. 49 49 /// 50 /// In general , %NetworkSimplexis the fastest implementation available51 /// in LEMON for th isproblem.52 /// Moreover ,it supports both directions of the supply/demand inequality50 /// In general this class is the fastest implementation available 51 /// in LEMON for the minimum cost flow problem. 52 /// Moreover it supports both directions of the supply/demand inequality 53 53 /// constraints. For more information, see \ref SupplyType. 54 54 /// … … 59 59 /// 60 60 /// \tparam GR The digraph type the algorithm runs on. 61 /// \tparam V The numbertype used for flow amounts, capacity bounds61 /// \tparam V The value type used for flow amounts, capacity bounds 62 62 /// and supply values in the algorithm. By default, it is \c int. 63 /// \tparam C The numbertype used for costs and potentials in the63 /// \tparam C The value type used for costs and potentials in the 64 64 /// algorithm. By default, it is the same as \c V. 65 65 /// 66 /// \warning Both numbertypes must be signed and all input data must66 /// \warning Both value types must be signed and all input data must 67 67 /// be integer. 68 68 /// … … 127 127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 128 /// proved to be the most efficient and the most robust on various 129 /// test inputs .129 /// test inputs according to our benchmark tests. 130 130 /// However, another pivot rule can be selected using the \ref run() 131 131 /// function with the proper parameter. … … 165 165 166 166 typedef std::vector<int> IntVector; 167 typedef std::vector< char> CharVector;167 typedef std::vector<bool> BoolVector; 168 168 typedef std::vector<Value> ValueVector; 169 169 typedef std::vector<Cost> CostVector; … … 195 195 IntVector _source; 196 196 IntVector _target; 197 bool _arc_mixing;198 197 199 198 // Node and arc data … … 214 213 IntVector _last_succ; 215 214 IntVector _dirty_revs; 216 CharVector _forward;217 CharVector _state;215 BoolVector _forward; 216 IntVector _state; 218 217 int _root; 219 218 … … 223 222 int stem, par_stem, new_stem; 224 223 Value delta; 225 226 const Value MAX;227 224 228 225 public: … … 246 243 const IntVector &_target; 247 244 const CostVector &_cost; 248 const CharVector&_state;245 const IntVector &_state; 249 246 const CostVector &_pi; 250 247 int &_in_arc; … … 298 295 const IntVector &_target; 299 296 const CostVector &_cost; 300 const CharVector&_state;297 const IntVector &_state; 301 298 const CostVector &_pi; 302 299 int &_in_arc; … … 337 334 const IntVector &_target; 338 335 const CostVector &_cost; 339 const CharVector&_state;336 const IntVector &_state; 340 337 const CostVector &_pi; 341 338 int &_in_arc; … … 410 407 const IntVector &_target; 411 408 const CostVector &_cost; 412 const CharVector&_state;409 const IntVector &_state; 413 410 const CostVector &_pi; 414 411 int &_in_arc; … … 513 510 const IntVector &_target; 514 511 const CostVector &_cost; 515 const CharVector&_state;512 const IntVector &_state; 516 513 const CostVector &_pi; 517 514 int &_in_arc; … … 635 632 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 636 633 _graph(graph), _node_id(graph), _arc_id(graph), 637 _arc_mixing(arc_mixing),638 MAX(std::numeric_limits<Value>::max()),639 634 INF(std::numeric_limits<Value>::has_infinity ? 640 std::numeric_limits<Value>::infinity() : MAX) 635 std::numeric_limits<Value>::infinity() : 636 std::numeric_limits<Value>::max()) 641 637 { 642 // Check the numbertypes638 // Check the value types 643 639 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 644 640 "The flow type of NetworkSimplex must be signed"); … … 646 642 "The cost type of NetworkSimplex must be signed"); 647 643 648 // Reset data structures 644 // Resize vectors 645 _node_num = countNodes(_graph); 646 _arc_num = countArcs(_graph); 647 int all_node_num = _node_num + 1; 648 int max_arc_num = _arc_num + 2 * _node_num; 649 650 _source.resize(max_arc_num); 651 _target.resize(max_arc_num); 652 653 _lower.resize(_arc_num); 654 _upper.resize(_arc_num); 655 _cap.resize(max_arc_num); 656 _cost.resize(max_arc_num); 657 _supply.resize(all_node_num); 658 _flow.resize(max_arc_num); 659 _pi.resize(all_node_num); 660 661 _parent.resize(all_node_num); 662 _pred.resize(all_node_num); 663 _forward.resize(all_node_num); 664 _thread.resize(all_node_num); 665 _rev_thread.resize(all_node_num); 666 _succ_num.resize(all_node_num); 667 _last_succ.resize(all_node_num); 668 _state.resize(max_arc_num); 669 670 // Copy the graph 671 int i = 0; 672 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 673 _node_id[n] = i; 674 } 675 if (arc_mixing) { 676 // Store the arcs in a mixed order 677 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 678 int i = 0, j = 0; 679 for (ArcIt a(_graph); a != INVALID; ++a) { 680 _arc_id[a] = i; 681 _source[i] = _node_id[_graph.source(a)]; 682 _target[i] = _node_id[_graph.target(a)]; 683 if ((i += k) >= _arc_num) i = ++j; 684 } 685 } else { 686 // Store the arcs in the original order 687 int i = 0; 688 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 689 _arc_id[a] = i; 690 _source[i] = _node_id[_graph.source(a)]; 691 _target[i] = _node_id[_graph.target(a)]; 692 } 693 } 694 695 // Reset parameters 649 696 reset(); 650 697 } … … 681 728 /// If it is not used before calling \ref run(), the upper bounds 682 729 /// will be set to \ref INF on all arcs (i.e. the flow value will be 683 /// unbounded from above ).730 /// unbounded from above on each arc). 684 731 /// 685 732 /// \param map An arc map storing the upper bounds. … … 794 841 /// \endcode 795 842 /// 796 /// This function can be called more than once. All the givenparameters797 /// are kept for the next call, unless \ref resetParams() or \ref reset()798 /// is used, thus only the modified parameters have to be set again.799 /// If the underlying digraph was also modified after the construction800 /// of the class (or the last \ref reset() call), then the \ref reset()801 /// function must be called.843 /// This function can be called more than once. All the parameters 844 /// that have been given are kept for the next call, unless 845 /// \ref reset() is called, thus only the modified parameters 846 /// have to be set again. See \ref reset() for examples. 847 /// However, the underlying digraph must not be modified after this 848 /// class have been constructed, since it copies and extends the graph. 802 849 /// 803 850 /// \param pivot_rule The pivot rule that will be used during the … … 813 860 /// 814 861 /// \see ProblemType, PivotRule 815 /// \see resetParams(), reset()816 862 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 817 863 if (!init()) return INFEASIBLE; … … 825 871 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 826 872 /// 827 /// It is useful for multiple \ref run() calls. Basically, all the given 828 /// parameters are kept for the next \ref run() call, unless 829 /// \ref resetParams() or \ref reset() is used. 830 /// If the underlying digraph was also modified after the construction 831 /// of the class or the last \ref reset() call, then the \ref reset() 832 /// function must be used, otherwise \ref resetParams() is sufficient. 873 /// It is useful for multiple run() calls. If this function is not 874 /// used, all the parameters given before are kept for the next 875 /// \ref run() call. 876 /// However, the underlying digraph must not be modified after this 877 /// class have been constructed, since it copies and extends the graph. 833 878 /// 834 879 /// For example, … … 840 885 /// .supplyMap(sup).run(); 841 886 /// 842 /// // Run again with modified cost map (reset Params() is not called,887 /// // Run again with modified cost map (reset() is not called, 843 888 /// // so only the cost map have to be set again) 844 889 /// cost[e] += 100; 845 890 /// ns.costMap(cost).run(); 846 891 /// 847 /// // Run again from scratch using reset Params()892 /// // Run again from scratch using reset() 848 893 /// // (the lower bounds will be set to zero on all arcs) 849 /// ns.reset Params();894 /// ns.reset(); 850 895 /// ns.upperMap(capacity).costMap(cost) 851 896 /// .supplyMap(sup).run(); … … 853 898 /// 854 899 /// \return <tt>(*this)</tt> 855 /// 856 /// \see reset(), run() 857 NetworkSimplex& resetParams() { 900 NetworkSimplex& reset() { 858 901 for (int i = 0; i != _node_num; ++i) { 859 902 _supply[i] = 0; … … 869 912 } 870 913 871 /// \brief Reset the internal data structures and all the parameters872 /// that have been given before.873 ///874 /// This function resets the internal data structures and all the875 /// paramaters that have been given before using functions \ref lowerMap(),876 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),877 /// \ref supplyType().878 ///879 /// It is useful for multiple \ref run() calls. Basically, all the given880 /// parameters are kept for the next \ref run() call, unless881 /// \ref resetParams() or \ref reset() is used.882 /// If the underlying digraph was also modified after the construction883 /// of the class or the last \ref reset() call, then the \ref reset()884 /// function must be used, otherwise \ref resetParams() is sufficient.885 ///886 /// See \ref resetParams() for examples.887 ///888 /// \return <tt>(*this)</tt>889 ///890 /// \see resetParams(), run()891 NetworkSimplex& reset() {892 // Resize vectors893 _node_num = countNodes(_graph);894 _arc_num = countArcs(_graph);895 int all_node_num = _node_num + 1;896 int max_arc_num = _arc_num + 2 * _node_num;897 898 _source.resize(max_arc_num);899 _target.resize(max_arc_num);900 901 _lower.resize(_arc_num);902 _upper.resize(_arc_num);903 _cap.resize(max_arc_num);904 _cost.resize(max_arc_num);905 _supply.resize(all_node_num);906 _flow.resize(max_arc_num);907 _pi.resize(all_node_num);908 909 _parent.resize(all_node_num);910 _pred.resize(all_node_num);911 _forward.resize(all_node_num);912 _thread.resize(all_node_num);913 _rev_thread.resize(all_node_num);914 _succ_num.resize(all_node_num);915 _last_succ.resize(all_node_num);916 _state.resize(max_arc_num);917 918 // Copy the graph919 int i = 0;920 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {921 _node_id[n] = i;922 }923 if (_arc_mixing) {924 // Store the arcs in a mixed order925 int k = std::max(int(std::sqrt(double(_arc_num))), 10);926 int i = 0, j = 0;927 for (ArcIt a(_graph); a != INVALID; ++a) {928 _arc_id[a] = i;929 _source[i] = _node_id[_graph.source(a)];930 _target[i] = _node_id[_graph.target(a)];931 if ((i += k) >= _arc_num) i = ++j;932 }933 } else {934 // Store the arcs in the original order935 int i = 0;936 for (ArcIt a(_graph); a != INVALID; ++a, ++i) {937 _arc_id[a] = i;938 _source[i] = _node_id[_graph.source(a)];939 _target[i] = _node_id[_graph.target(a)];940 }941 }942 943 // Reset parameters944 resetParams();945 return *this;946 }947 948 914 /// @} 949 915 … … 1055 1021 Value c = _lower[i]; 1056 1022 if (c >= 0) { 1057 _cap[i] = _upper[i] < MAX? _upper[i] - c : INF;1023 _cap[i] = _upper[i] < INF ? _upper[i] - c : INF; 1058 1024 } else { 1059 _cap[i] = _upper[i] < MAX+ c ? _upper[i] - c : INF;1025 _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF; 1060 1026 } 1061 1027 _supply[_source[i]] -= c; … … 1249 1215 e = _pred[u]; 1250 1216 d = _forward[u] ? 1251 _flow[e] : (_cap[e] >= MAX? INF : _cap[e] - _flow[e]);1217 _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]); 1252 1218 if (d < delta) { 1253 1219 delta = d; … … 1260 1226 e = _pred[u]; 1261 1227 d = _forward[u] ? 1262 (_cap[e] >= MAX? INF : _cap[e] - _flow[e]) : _flow[e];1228 (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e]; 1263 1229 if (d <= delta) { 1264 1230 delta = d; … … 1459 1425 findJoinNode(); 1460 1426 bool change = findLeavingArc(); 1461 if (delta >= MAX) return UNBOUNDED;1427 if (delta >= INF) return UNBOUNDED; 1462 1428 changeFlow(change); 1463 1429 if (change) { -
lemon/planarity.h
r896 r862 519 519 /// 520 520 /// This function implements the Boyer-Myrvold algorithm for 521 /// planarity checking of an undirected simplegraph. It is a simplified521 /// planarity checking of an undirected graph. It is a simplified 522 522 /// version of the PlanarEmbedding algorithm class because neither 523 /// the embedding nor the Kuratowski subdivisons arecomputed.523 /// the embedding nor the kuratowski subdivisons are not computed. 524 524 template <typename GR> 525 525 bool checkPlanarity(const GR& graph) { … … 533 533 /// 534 534 /// This class implements the Boyer-Myrvold algorithm for planar 535 /// embedding of an undirected simplegraph. The planar embedding is an535 /// embedding of an undirected graph. The planar embedding is an 536 536 /// ordering of the outgoing edges of the nodes, which is a possible 537 537 /// configuration to draw the graph in the plane. If there is not 538 /// such ordering then the graph contains a K<sub>5</sub>(full graph539 /// with 5 nodes) or a K<sub>3,3</sub>(complete bipartite graph on540 /// 3 Red and 3 Blue nodes) subdivision.538 /// such ordering then the graph contains a \f$ K_5 \f$ (full graph 539 /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on 540 /// 3 ANode and 3 BNode) subdivision. 541 541 /// 542 542 /// The current implementation calculates either an embedding or a 543 /// Kuratowski subdivision. The running time of the algorithm is O(n). 544 /// 545 /// \see PlanarDrawing, checkPlanarity() 543 /// Kuratowski subdivision. The running time of the algorithm is 544 /// \f$ O(n) \f$. 546 545 template <typename Graph> 547 546 class PlanarEmbedding { … … 593 592 public: 594 593 595 /// \brief The map type for storing the embedding 596 /// 597 /// The map type for storing the embedding. 598 /// \see embeddingMap() 594 /// \brief The map for store of embedding 599 595 typedef typename Graph::template ArcMap<Arc> EmbeddingMap; 600 596 601 597 /// \brief Constructor 602 598 /// 603 /// Constructor. 604 /// \pre The graph must be simple, i.e. it should not 605 /// contain parallel or loop arcs. 599 /// \note The graph should be simple, i.e. parallel and loop arc 600 /// free. 606 601 PlanarEmbedding(const Graph& graph) 607 602 : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {} 608 603 609 /// \brief Run the algorithm.604 /// \brief Runs the algorithm. 610 605 /// 611 /// This function runs the algorithm.612 /// \param kuratowski If th is parameter is set to \cfalse, then the606 /// Runs the algorithm. 607 /// \param kuratowski If the parameter is false, then the 613 608 /// algorithm does not compute a Kuratowski subdivision. 614 /// \return \c true ifthe graph is planar.609 ///\return %True when the graph is planar. 615 610 bool run(bool kuratowski = true) { 616 611 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; … … 705 700 } 706 701 707 /// \brief Give back the successor of an arc702 /// \brief Gives back the successor of an arc 708 703 /// 709 /// This function gives back the successor of an arc. Itmakes704 /// Gives back the successor of an arc. This function makes 710 705 /// possible to query the cyclic order of the outgoing arcs from 711 706 /// a node. … … 714 709 } 715 710 716 /// \brief Give back the calculated embedding map711 /// \brief Gives back the calculated embedding map 717 712 /// 718 /// This function gives back the calculated embedding map, which 719 /// contains the successor of each arc in the cyclic order of the 720 /// outgoing arcs of its source node. 713 /// The returned map contains the successor of each arc in the 714 /// graph. 721 715 const EmbeddingMap& embeddingMap() const { 722 716 return _embedding; 723 717 } 724 718 725 /// \brief Give back \c true if the given edge is in the Kuratowski 719 /// \brief Gives back true if the undirected arc is in the 720 /// kuratowski subdivision 721 /// 722 /// Gives back true if the undirected arc is in the kuratowski 726 723 /// subdivision 727 /// 728 /// This function gives back \c true if the given edge is in the found 729 /// Kuratowski subdivision. 730 /// \pre The \c run() function must be called with \c true parameter 731 /// before using this function. 732 bool kuratowski(const Edge& edge) const { 724 /// \note The \c run() had to be called with true value. 725 bool kuratowski(const Edge& edge) { 733 726 return _kuratowski[edge]; 734 727 } … … 2067 2060 /// 2068 2061 /// The planar drawing algorithm calculates positions for the nodes 2069 /// in the plane . These coordinates satisfy that if the edges are2070 /// represented with straight lines ,then they will not intersect2062 /// in the plane which coordinates satisfy that if the arcs are 2063 /// represented with straight lines then they will not intersect 2071 2064 /// each other. 2072 2065 /// 2073 /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,2074 /// i.e. each node will be located in the \c [0 ..n-2]x[0..n-2] square.2066 /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid, 2067 /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square. 2075 2068 /// The time complexity of the algorithm is O(n). 2076 ///2077 /// \see PlanarEmbedding2078 2069 template <typename Graph> 2079 2070 class PlanarDrawing { … … 2082 2073 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2083 2074 2084 /// \brief The point type for stor ingcoordinates2075 /// \brief The point type for store coordinates 2085 2076 typedef dim2::Point<int> Point; 2086 /// \brief The map type for stor ing the coordinates of the nodes2077 /// \brief The map type for store coordinates 2087 2078 typedef typename Graph::template NodeMap<Point> PointMap; 2088 2079 … … 2091 2082 /// 2092 2083 /// Constructor 2093 /// \pre The graph must be simple, i.e. it should not 2094 /// contain parallel or loop arcs. 2084 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2095 2085 PlanarDrawing(const Graph& graph) 2096 2086 : _graph(graph), _point_map(graph) {} … … 2377 2367 public: 2378 2368 2379 /// \brief Calculate the node positions2369 /// \brief Calculates the node positions 2380 2370 /// 2381 /// This function calculates the node positions on the plane.2382 /// \return \c true if the graph is planar.2371 /// This function calculates the node positions. 2372 /// \return %True if the graph is planar. 2383 2373 bool run() { 2384 2374 PlanarEmbedding<Graph> pe(_graph); … … 2389 2379 } 2390 2380 2391 /// \brief Calculate the node positions according to a2381 /// \brief Calculates the node positions according to a 2392 2382 /// combinatorical embedding 2393 2383 /// 2394 /// This function calculates the node positions on the plane. 2395 /// The given \c embedding map should contain a valid combinatorical 2396 /// embedding, i.e. a valid cyclic order of the arcs. 2397 /// It can be computed using PlanarEmbedding. 2384 /// This function calculates the node locations. The \c embedding 2385 /// parameter should contain a valid combinatorical embedding, i.e. 2386 /// a valid cyclic order of the arcs. 2398 2387 template <typename EmbeddingMap> 2399 2388 void run(const EmbeddingMap& embedding) { … … 2435 2424 /// \brief The coordinate of the given node 2436 2425 /// 2437 /// Th is function returns the coordinate of the given node.2426 /// The coordinate of the given node. 2438 2427 Point operator[](const Node& node) const { 2439 2428 return _point_map[node]; 2440 2429 } 2441 2430 2442 /// \brief Return the grid embedding in a node map2431 /// \brief Returns the grid embedding in a \e NodeMap. 2443 2432 /// 2444 /// This function returns the grid embedding in a node map of 2445 /// \c dim2::Point<int> coordinates. 2433 /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> . 2446 2434 const PointMap& coords() const { 2447 2435 return _point_map; … … 2483 2471 /// 2484 2472 /// The graph coloring problem is the coloring of the graph nodes 2485 /// so that there are noadjacent nodes with the same color. The2486 /// planar graphs can always be colored with four colors, whichis2487 /// proved by Appel and Haken . Their proofs provide a quadratic2473 /// that there are not adjacent nodes with the same color. The 2474 /// planar graphs can be always colored with four colors, it is 2475 /// proved by Appel and Haken and their proofs provide a quadratic 2488 2476 /// time algorithm for four coloring, but it could not be used to 2489 /// implement anefficient algorithm. The five and six coloring can be2490 /// made in linear time, but in this class ,the five coloring has2477 /// implement efficient algorithm. The five and six coloring can be 2478 /// made in linear time, but in this class the five coloring has 2491 2479 /// quadratic worst case time complexity. The two coloring (if 2492 2480 /// possible) is solvable with a graph search algorithm and it is 2493 2481 /// implemented in \ref bipartitePartitions() function in LEMON. To 2494 /// decide whether a planar graph is three colorable is NP-complete. 2482 /// decide whether the planar graph is three colorable is 2483 /// NP-complete. 2495 2484 /// 2496 2485 /// This class contains member functions for calculate colorings 2497 2486 /// with five and six colors. The six coloring algorithm is a simple 2498 2487 /// greedy coloring on the backward minimum outgoing order of nodes. 2499 /// This order can be computed by selectingthe node with least2500 /// outgoing arcs to unprocessed nodes i n each phase. This order2488 /// This order can be computed as in each phase the node with least 2489 /// outgoing arcs to unprocessed nodes is chosen. This order 2501 2490 /// guarantees that when a node is chosen for coloring it has at 2502 2491 /// most five already colored adjacents. The five coloring algorithm … … 2511 2500 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2512 2501 2513 /// \brief The map type for stor ing color indices2502 /// \brief The map type for store color indexes 2514 2503 typedef typename Graph::template NodeMap<int> IndexMap; 2515 /// \brief The map type for storing colors 2516 /// 2517 /// The map type for storing colors. 2518 /// \see Palette, Color 2504 /// \brief The map type for store colors 2519 2505 typedef ComposeMap<Palette, IndexMap> ColorMap; 2520 2506 2521 2507 /// \brief Constructor 2522 2508 /// 2523 /// Constructor. 2524 /// \pre The graph must be simple, i.e. it should not 2525 /// contain parallel or loop arcs. 2509 /// Constructor 2510 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2526 2511 PlanarColoring(const Graph& graph) 2527 2512 : _graph(graph), _color_map(graph), _palette(0) { … … 2534 2519 } 2535 2520 2536 /// \brief Return the node map of color indices2521 /// \brief Returns the \e NodeMap of color indexes 2537 2522 /// 2538 /// This function returns the node map of color indices. The values are2539 /// in therange \c [0..4] or \c [0..5] according to the coloring method.2523 /// Returns the \e NodeMap of color indexes. The values are in the 2524 /// range \c [0..4] or \c [0..5] according to the coloring method. 2540 2525 IndexMap colorIndexMap() const { 2541 2526 return _color_map; 2542 2527 } 2543 2528 2544 /// \brief Return the node map of colors2529 /// \brief Returns the \e NodeMap of colors 2545 2530 /// 2546 /// This function returns the node map of colors. The values are among2547 /// five or sixdistinct \ref lemon::Color "colors".2531 /// Returns the \e NodeMap of colors. The values are five or six 2532 /// distinct \ref lemon::Color "colors". 2548 2533 ColorMap colorMap() const { 2549 2534 return composeMap(_palette, _color_map); 2550 2535 } 2551 2536 2552 /// \brief Return the color index of the node2537 /// \brief Returns the color index of the node 2553 2538 /// 2554 /// This function returns the color index of the given node. The value is2555 /// in therange \c [0..4] or \c [0..5] according to the coloring method.2539 /// Returns the color index of the node. The values are in the 2540 /// range \c [0..4] or \c [0..5] according to the coloring method. 2556 2541 int colorIndex(const Node& node) const { 2557 2542 return _color_map[node]; 2558 2543 } 2559 2544 2560 /// \brief Return the color of the node2545 /// \brief Returns the color of the node 2561 2546 /// 2562 /// This function returns the color of the given node. The value is among2563 /// five or sixdistinct \ref lemon::Color "colors".2547 /// Returns the color of the node. The values are five or six 2548 /// distinct \ref lemon::Color "colors". 2564 2549 Color color(const Node& node) const { 2565 2550 return _palette[_color_map[node]]; … … 2567 2552 2568 2553 2569 /// \brief Calculate a coloring with at most six colors2554 /// \brief Calculates a coloring with at most six colors 2570 2555 /// 2571 2556 /// This function calculates a coloring with at most six colors. The time 2572 2557 /// complexity of this variant is linear in the size of the graph. 2573 /// \return \c true if the algorithm could color the graph with six colors.2574 /// If the algorithm fails, then the graph is notplanar.2575 /// \note This function can return \ctrue if the graph is not2576 /// planar , but it can be colored with at most sixcolors.2558 /// \return %True when the algorithm could color the graph with six color. 2559 /// If the algorithm fails, then the graph could not be planar. 2560 /// \note This function can return true if the graph is not 2561 /// planar but it can be colored with 6 colors. 2577 2562 bool runSixColoring() { 2578 2563 … … 2676 2661 public: 2677 2662 2678 /// \brief Calculate a coloring with at most five colors2663 /// \brief Calculates a coloring with at most five colors 2679 2664 /// 2680 2665 /// This function calculates a coloring with at most five 2681 2666 /// colors. The worst case time complexity of this variant is 2682 2667 /// quadratic in the size of the graph. 2683 /// \param embedding This map should contain a valid combinatorical2684 /// embedding, i.e. a valid cyclic order of the arcs.2685 /// It can be computed using PlanarEmbedding.2686 2668 template <typename EmbeddingMap> 2687 2669 void runFiveColoring(const EmbeddingMap& embedding) { … … 2730 2712 } 2731 2713 2732 /// \brief Calculate a coloring with at most five colors2714 /// \brief Calculates a coloring with at most five colors 2733 2715 /// 2734 2716 /// This function calculates a coloring with at most five 2735 2717 /// colors. The worst case time complexity of this variant is 2736 2718 /// quadratic in the size of the graph. 2737 /// \return \c true ifthe graph is planar.2719 /// \return %True when the graph is planar. 2738 2720 bool runFiveColoring() { 2739 2721 PlanarEmbedding<Graph> pe(_graph); -
lemon/preflow.h
r891 r835 114 114 /// second phase constructs a feasible maximum flow on each arc. 115 115 /// 116 /// \warning This implementation cannot handle infinite or very large117 /// capacities (e.g. the maximum value of \c CAP::Value).118 ///119 116 /// \tparam GR The type of the digraph the algorithm runs on. 120 117 /// \tparam CAP The type of the capacity map. The default map 121 118 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 122 /// \tparam TR The traits class that defines various types used by the123 /// algorithm. By default, it is \ref PreflowDefaultTraits124 /// "PreflowDefaultTraits<GR, CAP>".125 /// In most cases, this parameter should not be set directly,126 /// consider to use the named template parameters instead.127 119 #ifdef DOXYGEN 128 120 template <typename GR, typename CAP, typename TR> -
lemon/unionfind.h
r864 r833 740 740 void clear() { 741 741 items.clear(); 742 classes.clear ();742 classes.clear; 743 743 firstClass = firstFreeClass = firstFreeItem = -1; 744 744 } -
test/min_cost_flow_test.cc
r898 r716 25 25 26 26 #include <lemon/network_simplex.h> 27 #include <lemon/capacity_scaling.h>28 #include <lemon/cost_scaling.h>29 #include <lemon/cycle_canceling.h>30 27 31 28 #include <lemon/concepts/digraph.h> 32 #include <lemon/concepts/heap.h>33 29 #include <lemon/concept_check.h> 34 30 … … 37 33 using namespace lemon; 38 34 39 // Test networks40 35 char test_lgf[] = 41 36 "@nodes\n" … … 82 77 "target 12\n"; 83 78 84 char test_neg1_lgf[] =85 "@nodes\n"86 "label sup\n"87 " 1 100\n"88 " 2 0\n"89 " 3 0\n"90 " 4 -100\n"91 " 5 0\n"92 " 6 0\n"93 " 7 0\n"94 "@arcs\n"95 " cost low1 low2\n"96 "1 2 100 0 0\n"97 "1 3 30 0 0\n"98 "2 4 20 0 0\n"99 "3 4 80 0 0\n"100 "3 2 50 0 0\n"101 "5 3 10 0 0\n"102 "5 6 80 0 1000\n"103 "6 7 30 0 -1000\n"104 "7 5 -120 0 0\n";105 106 char test_neg2_lgf[] =107 "@nodes\n"108 "label sup\n"109 " 1 100\n"110 " 2 -300\n"111 "@arcs\n"112 " cost\n"113 "1 2 -1\n";114 115 116 // Test data117 typedef ListDigraph Digraph;118 DIGRAPH_TYPEDEFS(ListDigraph);119 120 Digraph gr;121 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);122 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);123 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());124 Node v, w;125 126 Digraph neg1_gr;127 Digraph::ArcMap<int> neg1_c(neg1_gr), neg1_l1(neg1_gr), neg1_l2(neg1_gr);128 ConstMap<Arc, int> neg1_u1(std::numeric_limits<int>::max()), neg1_u2(5000);129 Digraph::NodeMap<int> neg1_s(neg1_gr);130 131 Digraph neg2_gr;132 Digraph::ArcMap<int> neg2_c(neg2_gr);133 ConstMap<Arc, int> neg2_l(0), neg2_u(1000);134 Digraph::NodeMap<int> neg2_s(neg2_gr);135 136 79 137 80 enum SupplyType { … … 140 83 LEQ 141 84 }; 142 143 85 144 86 // Check the interface of an MCF algorithm … … 158 100 const MCF& const_mcf = mcf; 159 101 160 b = mcf.reset() .resetParams()102 b = mcf.reset() 161 103 .lowerMap(me.lower) 162 104 .upperMap(me.upper) … … 327 269 } 328 270 329 template < typename MCF, typename Param >330 void runMcfGeqTests( Param param,331 const std::string &test_str = "",332 bool full_neg_cost_support = false )333 {334 MCF mcf1(gr), mcf2(neg1_gr), mcf3(neg2_gr);335 336 // Basic tests337 mcf1.upperMap(u).costMap(c).supplyMap(s1);338 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s1,339 mcf1.OPTIMAL, true, 5240, test_str + "-1");340 mcf1.stSupply(v, w, 27);341 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s2,342 mcf1.OPTIMAL, true, 7620, test_str + "-2");343 mcf1.lowerMap(l2).supplyMap(s1);344 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s1,345 mcf1.OPTIMAL, true, 5970, test_str + "-3");346 mcf1.stSupply(v, w, 27);347 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,348 mcf1.OPTIMAL, true, 8010, test_str + "-4");349 mcf1.resetParams().supplyMap(s1);350 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,351 mcf1.OPTIMAL, true, 74, test_str + "-5");352 mcf1.lowerMap(l2).stSupply(v, w, 27);353 checkMcf(mcf1, mcf1.run(param), gr, l2, cu, cc, s2,354 mcf1.OPTIMAL, true, 94, test_str + "-6");355 mcf1.reset();356 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s3,357 mcf1.OPTIMAL, true, 0, test_str + "-7");358 mcf1.lowerMap(l2).upperMap(u);359 checkMcf(mcf1, mcf1.run(param), gr, l2, u, cc, s3,360 mcf1.INFEASIBLE, false, 0, test_str + "-8");361 mcf1.lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);362 checkMcf(mcf1, mcf1.run(param), gr, l3, u, c, s4,363 mcf1.OPTIMAL, true, 6360, test_str + "-9");364 365 // Tests for the GEQ form366 mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);367 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,368 mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ);369 mcf1.lowerMap(l2);370 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,371 mcf1.OPTIMAL, true, 4540, test_str + "-11", GEQ);372 mcf1.supplyMap(s6);373 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,374 mcf1.INFEASIBLE, false, 0, test_str + "-12", GEQ);375 376 // Tests with negative costs377 mcf2.lowerMap(neg1_l1).costMap(neg1_c).supplyMap(neg1_s);378 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u1, neg1_c, neg1_s,379 mcf2.UNBOUNDED, false, 0, test_str + "-13");380 mcf2.upperMap(neg1_u2);381 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,382 mcf2.OPTIMAL, true, -40000, test_str + "-14");383 mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);384 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,385 mcf2.UNBOUNDED, false, 0, test_str + "-15");386 387 mcf3.costMap(neg2_c).supplyMap(neg2_s);388 if (full_neg_cost_support) {389 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,390 mcf3.OPTIMAL, true, -300, test_str + "-16", GEQ);391 } else {392 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,393 mcf3.UNBOUNDED, false, 0, test_str + "-17", GEQ);394 }395 mcf3.upperMap(neg2_u);396 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,397 mcf3.OPTIMAL, true, -300, test_str + "-18", GEQ);398 }399 400 template < typename MCF, typename Param >401 void runMcfLeqTests( Param param,402 const std::string &test_str = "" )403 {404 // Tests for the LEQ form405 MCF mcf1(gr);406 mcf1.supplyType(mcf1.LEQ);407 mcf1.upperMap(u).costMap(c).supplyMap(s6);408 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s6,409 mcf1.OPTIMAL, true, 5080, test_str + "-19", LEQ);410 mcf1.lowerMap(l2);411 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s6,412 mcf1.OPTIMAL, true, 5930, test_str + "-20", LEQ);413 mcf1.supplyMap(s5);414 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s5,415 mcf1.INFEASIBLE, false, 0, test_str + "-21", LEQ);416 }417 418 419 271 int main() 420 272 { 421 // Read the test networks 273 // Check the interfaces 274 { 275 typedef concepts::Digraph GR; 276 checkConcept< McfClassConcept<GR, int, int>, 277 NetworkSimplex<GR> >(); 278 checkConcept< McfClassConcept<GR, double, double>, 279 NetworkSimplex<GR, double> >(); 280 checkConcept< McfClassConcept<GR, int, double>, 281 NetworkSimplex<GR, int, double> >(); 282 } 283 284 // Run various MCF tests 285 typedef ListDigraph Digraph; 286 DIGRAPH_TYPEDEFS(ListDigraph); 287 288 // Read the test digraph 289 Digraph gr; 290 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr); 291 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr); 292 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 293 Node v, w; 294 422 295 std::istringstream input(test_lgf); 423 296 DigraphReader<Digraph>(gr, input) … … 437 310 .run(); 438 311 439 std::istringstream neg_inp1(test_neg1_lgf); 440 DigraphReader<Digraph>(neg1_gr, neg_inp1) 441 .arcMap("cost", neg1_c) 442 .arcMap("low1", neg1_l1) 443 .arcMap("low2", neg1_l2) 444 .nodeMap("sup", neg1_s) 445 .run(); 446 447 std::istringstream neg_inp2(test_neg2_lgf); 448 DigraphReader<Digraph>(neg2_gr, neg_inp2) 449 .arcMap("cost", neg2_c) 450 .nodeMap("sup", neg2_s) 451 .run(); 452 453 // Check the interface of NetworkSimplex 312 // Build test digraphs with negative costs 313 Digraph neg_gr; 314 Node n1 = neg_gr.addNode(); 315 Node n2 = neg_gr.addNode(); 316 Node n3 = neg_gr.addNode(); 317 Node n4 = neg_gr.addNode(); 318 Node n5 = neg_gr.addNode(); 319 Node n6 = neg_gr.addNode(); 320 Node n7 = neg_gr.addNode(); 321 322 Arc a1 = neg_gr.addArc(n1, n2); 323 Arc a2 = neg_gr.addArc(n1, n3); 324 Arc a3 = neg_gr.addArc(n2, n4); 325 Arc a4 = neg_gr.addArc(n3, n4); 326 Arc a5 = neg_gr.addArc(n3, n2); 327 Arc a6 = neg_gr.addArc(n5, n3); 328 Arc a7 = neg_gr.addArc(n5, n6); 329 Arc a8 = neg_gr.addArc(n6, n7); 330 Arc a9 = neg_gr.addArc(n7, n5); 331 332 Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0); 333 ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000); 334 Digraph::NodeMap<int> neg_s(neg_gr, 0); 335 336 neg_l2[a7] = 1000; 337 neg_l2[a8] = -1000; 338 339 neg_s[n1] = 100; 340 neg_s[n4] = -100; 341 342 neg_c[a1] = 100; 343 neg_c[a2] = 30; 344 neg_c[a3] = 20; 345 neg_c[a4] = 80; 346 neg_c[a5] = 50; 347 neg_c[a6] = 10; 348 neg_c[a7] = 80; 349 neg_c[a8] = 30; 350 neg_c[a9] = -120; 351 352 Digraph negs_gr; 353 Digraph::NodeMap<int> negs_s(negs_gr); 354 Digraph::ArcMap<int> negs_c(negs_gr); 355 ConstMap<Arc, int> negs_l(0), negs_u(1000); 356 n1 = negs_gr.addNode(); 357 n2 = negs_gr.addNode(); 358 negs_s[n1] = 100; 359 negs_s[n2] = -300; 360 negs_c[negs_gr.addArc(n1, n2)] = -1; 361 362 363 // A. Test NetworkSimplex with the default pivot rule 454 364 { 455 typedef concepts::Digraph GR; 456 checkConcept< McfClassConcept<GR, int, int>, 457 NetworkSimplex<GR> >(); 458 checkConcept< McfClassConcept<GR, double, double>, 459 NetworkSimplex<GR, double> >(); 460 checkConcept< McfClassConcept<GR, int, double>, 461 NetworkSimplex<GR, int, double> >(); 462 } 463 464 // Check the interface of CapacityScaling 365 NetworkSimplex<Digraph> mcf(gr); 366 367 // Check the equality form 368 mcf.upperMap(u).costMap(c); 369 checkMcf(mcf, mcf.supplyMap(s1).run(), 370 gr, l1, u, c, s1, mcf.OPTIMAL, true, 5240, "#A1"); 371 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 372 gr, l1, u, c, s2, mcf.OPTIMAL, true, 7620, "#A2"); 373 mcf.lowerMap(l2); 374 checkMcf(mcf, mcf.supplyMap(s1).run(), 375 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#A3"); 376 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 377 gr, l2, u, c, s2, mcf.OPTIMAL, true, 8010, "#A4"); 378 mcf.reset(); 379 checkMcf(mcf, mcf.supplyMap(s1).run(), 380 gr, l1, cu, cc, s1, mcf.OPTIMAL, true, 74, "#A5"); 381 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), 382 gr, l2, cu, cc, s2, mcf.OPTIMAL, true, 94, "#A6"); 383 mcf.reset(); 384 checkMcf(mcf, mcf.run(), 385 gr, l1, cu, cc, s3, mcf.OPTIMAL, true, 0, "#A7"); 386 checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(), 387 gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8"); 388 mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4); 389 checkMcf(mcf, mcf.run(), 390 gr, l3, u, c, s4, mcf.OPTIMAL, true, 6360, "#A9"); 391 392 // Check the GEQ form 393 mcf.reset().upperMap(u).costMap(c).supplyMap(s5); 394 checkMcf(mcf, mcf.run(), 395 gr, l1, u, c, s5, mcf.OPTIMAL, true, 3530, "#A10", GEQ); 396 mcf.supplyType(mcf.GEQ); 397 checkMcf(mcf, mcf.lowerMap(l2).run(), 398 gr, l2, u, c, s5, mcf.OPTIMAL, true, 4540, "#A11", GEQ); 399 mcf.supplyMap(s6); 400 checkMcf(mcf, mcf.run(), 401 gr, l2, u, c, s6, mcf.INFEASIBLE, false, 0, "#A12", GEQ); 402 403 // Check the LEQ form 404 mcf.reset().supplyType(mcf.LEQ); 405 mcf.upperMap(u).costMap(c).supplyMap(s6); 406 checkMcf(mcf, mcf.run(), 407 gr, l1, u, c, s6, mcf.OPTIMAL, true, 5080, "#A13", LEQ); 408 checkMcf(mcf, mcf.lowerMap(l2).run(), 409 gr, l2, u, c, s6, mcf.OPTIMAL, true, 5930, "#A14", LEQ); 410 mcf.supplyMap(s5); 411 checkMcf(mcf, mcf.run(), 412 gr, l2, u, c, s5, mcf.INFEASIBLE, false, 0, "#A15", LEQ); 413 414 // Check negative costs 415 NetworkSimplex<Digraph> neg_mcf(neg_gr); 416 neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s); 417 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1, 418 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A16"); 419 neg_mcf.upperMap(neg_u2); 420 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2, 421 neg_c, neg_s, neg_mcf.OPTIMAL, true, -40000, "#A17"); 422 neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s); 423 checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1, 424 neg_c, neg_s, neg_mcf.UNBOUNDED, false, 0, "#A18"); 425 426 NetworkSimplex<Digraph> negs_mcf(negs_gr); 427 negs_mcf.costMap(negs_c).supplyMap(negs_s); 428 checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u, 429 negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ); 430 } 431 432 // B. Test NetworkSimplex with each pivot rule 465 433 { 466 typedef concepts::Digraph GR; 467 checkConcept< McfClassConcept<GR, int, int>, 468 CapacityScaling<GR> >(); 469 checkConcept< McfClassConcept<GR, double, double>, 470 CapacityScaling<GR, double> >(); 471 checkConcept< McfClassConcept<GR, int, double>, 472 CapacityScaling<GR, int, double> >(); 473 typedef CapacityScaling<GR>:: 474 SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS; 475 checkConcept< McfClassConcept<GR, int, int>, CAS >(); 476 } 477 478 // Check the interface of CostScaling 479 { 480 typedef concepts::Digraph GR; 481 checkConcept< McfClassConcept<GR, int, int>, 482 CostScaling<GR> >(); 483 checkConcept< McfClassConcept<GR, double, double>, 484 CostScaling<GR, double> >(); 485 checkConcept< McfClassConcept<GR, int, double>, 486 CostScaling<GR, int, double> >(); 487 typedef CostScaling<GR>:: 488 SetLargeCost<double>::Create COS; 489 checkConcept< McfClassConcept<GR, int, int>, COS >(); 490 } 491 492 // Check the interface of CycleCanceling 493 { 494 typedef concepts::Digraph GR; 495 checkConcept< McfClassConcept<GR, int, int>, 496 CycleCanceling<GR> >(); 497 checkConcept< McfClassConcept<GR, double, double>, 498 CycleCanceling<GR, double> >(); 499 checkConcept< McfClassConcept<GR, int, double>, 500 CycleCanceling<GR, int, double> >(); 501 } 502 503 // Test NetworkSimplex 504 { 505 typedef NetworkSimplex<Digraph> MCF; 506 runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true); 507 runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE"); 508 runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE", true); 509 runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE, "NS-BE"); 510 runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS", true); 511 runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH, "NS-BS"); 512 runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true); 513 runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL"); 514 runMcfGeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL", true); 515 runMcfLeqTests<MCF>(MCF::ALTERING_LIST, "NS-AL"); 516 } 517 518 // Test CapacityScaling 519 { 520 typedef CapacityScaling<Digraph> MCF; 521 runMcfGeqTests<MCF>(0, "SSP"); 522 runMcfGeqTests<MCF>(2, "CAS"); 523 } 524 525 // Test CostScaling 526 { 527 typedef CostScaling<Digraph> MCF; 528 runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR"); 529 runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR"); 530 runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR"); 531 } 532 533 // Test CycleCanceling 534 { 535 typedef CycleCanceling<Digraph> MCF; 536 runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC"); 537 runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC"); 538 runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT"); 434 NetworkSimplex<Digraph> mcf(gr); 435 mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2); 436 437 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), 438 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B1"); 439 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), 440 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B2"); 441 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), 442 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B3"); 443 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), 444 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B4"); 445 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), 446 gr, l2, u, c, s1, mcf.OPTIMAL, true, 5970, "#B5"); 539 447 } 540 448
Note: See TracChangeset
for help on using the changeset viewer.