Changes in / [857:989c6629d045:799:71f9c1f0d808] in lemon
- Files:
-
- 1 deleted
- 9 edited
Legend:
- Unmodified
- Added
- Removed
-
NEWS
r853 r712 1 2009-10-03 Version 1.1.1 released2 3 Bugfix release.4 5 #295: Suppress MSVC warnings using pragmas6 ----: Various CMAKE related improvements7 * Remove duplications from doc/CMakeLists.txt8 * Rename documentation install folder from 'docs' to 'html'9 * Add tools/CMakeLists.txt to the tarball10 * Generate and install LEMONConfig.cmake11 * Change the label of the html project in Visual Studio12 * Fix the check for the 'long long' type13 * Put the version string into config.h14 * Minor CMake improvements15 * Set the version to 'hg-tip' if everything fails16 #311: Add missing 'explicit' keywords17 #302: Fix the implementation and doc of CrossRefMap18 #308: Remove duplicate list_graph.h entry from source list19 #307: Bug fix in Preflow and Circulation20 21 1 2009-05-13 Version 1.1 released 22 2 -
doc/groups.dox
r844 r710 227 227 228 228 /** 229 @defgroup matrices Matrices 230 @ingroup datas 231 \brief Two dimensional data storages implemented in LEMON. 232 233 This group contains two dimensional data storages implemented in LEMON. 234 */ 235 236 /** 229 237 @defgroup paths Path Structures 230 238 @ingroup datas … … 276 284 This group contains the algorithms for finding shortest paths in digraphs. 277 285 278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 279 source node when all arc lengths are non-negative. 286 - \ref Dijkstra algorithm for finding shortest paths from a source node 287 when all arc lengths are non-negative. 288 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths 289 from a source node when arc lenghts can be either positive or negative, 290 but the digraph should not contain directed cycles with negative total 291 length. 292 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms 293 for solving the \e all-pairs \e shortest \e paths \e problem when arc 294 lenghts can be either positive or negative, but the digraph should 295 not contain directed cycles with negative total length. 280 296 - \ref Suurballe A successive shortest path algorithm for finding 281 297 arc-disjoint paths between two nodes having minimum total length. … … 302 318 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 303 319 304 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and 305 Tarjan for solving this problem. It also provides functions to query the 306 minimum cut, which is the dual problem of maximum flow. 307 320 LEMON contains several algorithms for solving maximum flow problems: 321 - \ref EdmondsKarp Edmonds-Karp algorithm. 322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 325 326 In most cases the \ref Preflow "Preflow" algorithm provides the 327 fastest method for computing a maximum flow. All implementations 328 also provide functions to query the minimum cut, which is the dual 329 problem of maximum flow. 308 330 309 331 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 323 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 324 346 325 \ref NetworkSimplex is an efficient implementation of the primal Network 326 Simplex algorithm for finding minimum cost flows. It also provides dual 327 solution (node potentials), if an optimal flow is found. 347 LEMON contains several algorithms for this problem. 348 - \ref NetworkSimplex Primal Network Simplex algorithm with various 349 pivot strategies. 350 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 351 cost scaling. 352 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 353 capacity scaling. 354 - \ref CancelAndTighten The Cancel and Tighten algorithm. 355 - \ref CycleCanceling Cycle-Canceling algorithms. 356 357 In general NetworkSimplex is the most efficient implementation, 358 but in special cases other algorithms could be faster. 359 For example, if the total supply and/or capacities are rather small, 360 CapacityScaling is usually the fastest algorithm (without effective scaling). 328 361 */ 329 362 … … 349 382 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 350 383 in directed graphs. 384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 385 calculating minimum cut in undirected graphs. 351 386 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 352 387 all-pairs minimum cut in undirected graphs. … … 369 404 370 405 /** 406 @defgroup planar Planarity Embedding and Drawing 407 @ingroup algs 408 \brief Algorithms for planarity checking, embedding and drawing 409 410 This group contains the algorithms for planarity checking, 411 embedding and drawing. 412 413 \image html planar.png 414 \image latex planar.eps "Plane graph" width=\textwidth 415 */ 416 417 /** 371 418 @defgroup matching Matching Algorithms 372 419 @ingroup algs 373 420 \brief Algorithms for finding matchings in graphs and bipartite graphs. 374 421 375 This group contains the algorithms for calculating matchings in graphs. 376 The general matching problem is finding a subset of the edges for which 377 each node has at most one incident edge. 422 This group contains the algorithms for calculating 423 matchings in graphs and bipartite graphs. The general matching problem is 424 finding a subset of the edges for which each node has at most one incident 425 edge. 378 426 379 427 There are several different algorithms for calculate matchings in 380 graphs. The goal of the matching optimization 428 graphs. The matching problems in bipartite graphs are generally 429 easier than in general graphs. The goal of the matching optimization 381 430 can be finding maximum cardinality, maximum weight or minimum cost 382 431 matching. The search can be constrained to find perfect or … … 384 433 385 434 The matching algorithms implemented in LEMON: 435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm 436 for calculating maximum cardinality matching in bipartite graphs. 437 - \ref PrBipartiteMatching Push-relabel algorithm 438 for calculating maximum cardinality matching in bipartite graphs. 439 - \ref MaxWeightedBipartiteMatching 440 Successive shortest path algorithm for calculating maximum weighted 441 matching and maximum weighted bipartite matching in bipartite graphs. 442 - \ref MinCostMaxBipartiteMatching 443 Successive shortest path algorithm for calculating minimum cost maximum 444 matching in bipartite graphs. 386 445 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 387 446 maximum cardinality matching in general graphs. … … 415 474 416 475 /** 476 @defgroup approx Approximation Algorithms 477 @ingroup algs 478 \brief Approximation algorithms. 479 480 This group contains the approximation and heuristic algorithms 481 implemented in LEMON. 482 */ 483 484 /** 417 485 @defgroup gen_opt_group General Optimization Tools 418 486 \brief This group contains some general optimization frameworks … … 431 499 various LP solvers could be used in the same manner with this 432 500 interface. 501 */ 502 503 /** 504 @defgroup lp_utils Tools for Lp and Mip Solvers 505 @ingroup lp_group 506 \brief Helper tools to the Lp and Mip solvers. 507 508 This group adds some helper tools to general optimization framework 509 implemented in LEMON. 510 */ 511 512 /** 513 @defgroup metah Metaheuristics 514 @ingroup gen_opt_group 515 \brief Metaheuristics for LEMON library. 516 517 This group contains some metaheuristic optimization tools. 433 518 */ 434 519 -
lemon/Makefile.am
r850 r714 91 91 lemon/lp_base.h \ 92 92 lemon/lp_skeleton.h \ 93 lemon/list_graph.h \ 93 94 lemon/maps.h \ 94 95 lemon/matching.h \ -
lemon/bits/edge_set_extender.h
r732 r664 538 538 539 539 public: 540 explicitArcMap(const Graph& _g)540 ArcMap(const Graph& _g) 541 541 : Parent(_g) {} 542 542 ArcMap(const Graph& _g, const _Value& _v) … … 562 562 563 563 public: 564 explicitEdgeMap(const Graph& _g)564 EdgeMap(const Graph& _g) 565 565 : Parent(_g) {} 566 566 -
lemon/bits/graph_extender.h
r732 r664 605 605 606 606 public: 607 explicitNodeMap(const Graph& graph)607 NodeMap(const Graph& graph) 608 608 : Parent(graph) {} 609 609 NodeMap(const Graph& graph, const _Value& value) … … 629 629 630 630 public: 631 explicitArcMap(const Graph& graph)631 ArcMap(const Graph& graph) 632 632 : Parent(graph) {} 633 633 ArcMap(const Graph& graph, const _Value& value) … … 653 653 654 654 public: 655 explicitEdgeMap(const Graph& graph)655 EdgeMap(const Graph& graph) 656 656 : Parent(graph) {} 657 657 -
lemon/maps.h
r731 r664 1903 1903 1904 1904 /// This class provides simple invertable graph maps. 1905 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) 1906 /// and if a key is set to a new value, then stores it in the inverse map. 1905 /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" 1906 /// and if a key is set to a new value then store it 1907 /// in the inverse map. 1908 /// 1907 1909 /// The values of the map can be accessed 1908 1910 /// with stl compatible forward iterator. 1909 ///1910 /// This type is not reference map, so it cannot be modified with1911 /// the subscript operator.1912 1911 /// 1913 1912 /// \tparam GR The graph type. … … 1925 1924 template Map<V>::Type Map; 1926 1925 1927 typedef std::m ultimap<V, K> Container;1926 typedef std::map<V, K> Container; 1928 1927 Container _inv_map; 1929 1928 … … 1950 1949 /// iterator on the values of the map. The values can 1951 1950 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1952 /// They are considered with multiplicity, so each value is1953 /// traversed for each item it is assigned to.1954 1951 class ValueIterator 1955 1952 : public std::iterator<std::forward_iterator_tag, Value> { … … 2004 2001 void set(const Key& key, const Value& val) { 2005 2002 Value oldval = Map::operator[](key); 2006 typename Container::iterator it; 2007 for (it = _inv_map.equal_range(oldval).first; 2008 it != _inv_map.equal_range(oldval).second; ++it) { 2009 if (it->second == key) { 2010 _inv_map.erase(it); 2011 break; 2012 } 2003 typename Container::iterator it = _inv_map.find(oldval); 2004 if (it != _inv_map.end() && it->second == key) { 2005 _inv_map.erase(it); 2013 2006 } 2014 _inv_map.insert( std::make_pair(val, key));2007 _inv_map.insert(make_pair(val, key)); 2015 2008 Map::set(key, val); 2016 2009 } … … 2024 2017 } 2025 2018 2026 /// \brief Gives back an item by its value. 2027 /// 2028 /// This function gives back an item that is assigned to 2029 /// the given value or \c INVALID if no such item exists. 2030 /// If there are more items with the same associated value, 2031 /// only one of them is returned. 2032 Key operator()(const Value& val) const { 2033 typename Container::const_iterator it = _inv_map.find(val); 2019 /// \brief Gives back the item by its value. 2020 /// 2021 /// Gives back the item by its value. 2022 Key operator()(const Value& key) const { 2023 typename Container::const_iterator it = _inv_map.find(key); 2034 2024 return it != _inv_map.end() ? it->second : INVALID; 2035 2025 } … … 2043 2033 virtual void erase(const Key& key) { 2044 2034 Value val = Map::operator[](key); 2045 typename Container::iterator it; 2046 for (it = _inv_map.equal_range(val).first; 2047 it != _inv_map.equal_range(val).second; ++it) { 2048 if (it->second == key) { 2049 _inv_map.erase(it); 2050 break; 2051 } 2035 typename Container::iterator it = _inv_map.find(val); 2036 if (it != _inv_map.end() && it->second == key) { 2037 _inv_map.erase(it); 2052 2038 } 2053 2039 Map::erase(key); … … 2061 2047 for (int i = 0; i < int(keys.size()); ++i) { 2062 2048 Value val = Map::operator[](keys[i]); 2063 typename Container::iterator it; 2064 for (it = _inv_map.equal_range(val).first; 2065 it != _inv_map.equal_range(val).second; ++it) { 2066 if (it->second == keys[i]) { 2067 _inv_map.erase(it); 2068 break; 2069 } 2049 typename Container::iterator it = _inv_map.find(val); 2050 if (it != _inv_map.end() && it->second == keys[i]) { 2051 _inv_map.erase(it); 2070 2052 } 2071 2053 } … … 2103 2085 /// \brief Subscript operator. 2104 2086 /// 2105 /// Subscript operator. It gives back an item 2106 /// that is assigned to the given value or \c INVALID 2107 /// if no such item exists. 2087 /// Subscript operator. It gives back the item 2088 /// that was last assigned to the given value. 2108 2089 Value operator[](const Key& key) const { 2109 2090 return _inverted(key); -
lemon/path.h
r798 r606 1016 1016 /// \brief The source of a path 1017 1017 /// 1018 /// This function returns the source node of the given path. 1019 /// If the path is empty, then it returns \c INVALID. 1018 /// This function returns the source of the given path. 1020 1019 template <typename Digraph, typename Path> 1021 1020 typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) { 1022 return path.empty() ? INVALID :digraph.source(path.front());1021 return digraph.source(path.front()); 1023 1022 } 1024 1023 1025 1024 /// \brief The target of a path 1026 1025 /// 1027 /// This function returns the target node of the given path. 1028 /// If the path is empty, then it returns \c INVALID. 1026 /// This function returns the target of the given path. 1029 1027 template <typename Digraph, typename Path> 1030 1028 typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) { 1031 return path.empty() ? INVALID :digraph.target(path.back());1029 return digraph.target(path.back()); 1032 1030 } 1033 1031 -
lemon/suurballe.h
r843 r670 46 46 /// Note that this problem is a special case of the \ref min_cost_flow 47 47 /// "minimum cost flow problem". This implementation is actually an 48 /// efficient specialized version of the Successive Shortest Path49 /// algorithm directly for this problem.48 /// efficient specialized version of the \ref CapacityScaling 49 /// "Successive Shortest Path" algorithm directly for this problem. 50 50 /// Therefore this class provides query functions for flow values and 51 51 /// node potentials (the dual solution) just like the minimum cost flow -
test/maps_test.cc
r731 r554 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/list_graph.h>26 25 27 26 #include "test_tools.h" … … 350 349 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 351 350 } 352 353 // CrossRefMap354 {355 typedef ListDigraph Graph;356 DIGRAPH_TYPEDEFS(Graph);357 358 checkConcept<ReadWriteMap<Node, int>,359 CrossRefMap<Graph, Node, int> >();360 361 Graph gr;362 typedef CrossRefMap<Graph, Node, char> CRMap;363 typedef CRMap::ValueIterator ValueIt;364 CRMap map(gr);365 366 Node n0 = gr.addNode();367 Node n1 = gr.addNode();368 Node n2 = gr.addNode();369 370 map.set(n0, 'A');371 map.set(n1, 'B');372 map.set(n2, 'C');373 map.set(n2, 'A');374 map.set(n0, 'C');375 376 check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',377 "Wrong CrossRefMap");378 check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");379 check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");380 check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");381 382 ValueIt it = map.beginValue();383 check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&384 it == map.endValue(), "Wrong value iterator");385 }386 351 387 352 return 0;
Note: See TracChangeset
for help on using the changeset viewer.