COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
8 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r712 r853  
     12009-10-03 Version 1.1.1 released
     2
     3        Bugfix release.
     4
     5        #295: Suppress MSVC warnings using pragmas
     6        ----: Various CMAKE related improvements
     7              * Remove duplications from doc/CMakeLists.txt
     8              * Rename documentation install folder from 'docs' to 'html'
     9              * Add tools/CMakeLists.txt to the tarball
     10              * Generate and install LEMONConfig.cmake
     11              * Change the label of the html project in Visual Studio
     12              * Fix the check for the 'long long' type
     13              * Put the version string into config.h
     14              * Minor CMake improvements
     15              * Set the version to 'hg-tip' if everything fails
     16        #311: Add missing 'explicit' keywords
     17        #302: Fix the implementation and doc of CrossRefMap
     18        #308: Remove duplicate list_graph.h entry from source list
     19        #307: Bug fix in Preflow and Circulation
     20
    1212009-05-13 Version 1.1 released
    222
  • doc/groups.dox

    r710 r844  
    227227
    228228/**
    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 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    284276This group contains the algorithms for finding shortest paths in digraphs.
    285277
    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.
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
    296280 - \ref Suurballe A successive shortest path algorithm for finding
    297281   arc-disjoint paths between two nodes having minimum total length.
     
    318302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319303
    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.
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
    330308
    331309\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    345323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    346324
    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).
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    361328*/
    362329
     
    382349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383350  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387352  all-pairs minimum cut in undirected graphs.
     
    404369
    405370/**
    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 /**
    418371@defgroup matching Matching Algorithms
    419372@ingroup algs
    420373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    421374
    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.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    426378
    427379There are several different algorithms for calculate matchings in
    428 graphs.  The matching problems in bipartite graphs are generally
    429 easier than in general graphs. The goal of the matching optimization
     380graphs. The goal of the matching optimization
    430381can be finding maximum cardinality, maximum weight or minimum cost
    431382matching. The search can be constrained to find perfect or
     
    433384
    434385The 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.
    445386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446387  maximum cardinality matching in general graphs.
     
    474415
    475416/**
    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 /**
    485417@defgroup gen_opt_group General Optimization Tools
    486418\brief This group contains some general optimization frameworks
     
    499431various LP solvers could be used in the same manner with this
    500432interface.
    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.
    518433*/
    519434
  • lemon/Makefile.am

    r714 r850  
    9191        lemon/lp_base.h \
    9292        lemon/lp_skeleton.h \
    93         lemon/list_graph.h \
    9493        lemon/maps.h \
    9594        lemon/matching.h \
  • lemon/bits/edge_set_extender.h

    r664 r732  
    538538
    539539    public:
    540       ArcMap(const Graph& _g)
     540      explicit ArcMap(const Graph& _g)
    541541        : Parent(_g) {}
    542542      ArcMap(const Graph& _g, const _Value& _v)
     
    562562
    563563    public:
    564       EdgeMap(const Graph& _g)
     564      explicit EdgeMap(const Graph& _g)
    565565        : Parent(_g) {}
    566566
  • lemon/bits/graph_extender.h

    r664 r732  
    605605
    606606    public:
    607       NodeMap(const Graph& graph)
     607      explicit NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
     
    629629
    630630    public:
    631       ArcMap(const Graph& graph)
     631      explicit ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
     
    653653
    654654    public:
    655       EdgeMap(const Graph& graph)
     655      explicit EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657
  • lemon/maps.h

    r664 r731  
    19031903
    19041904  /// This class provides simple invertable graph maps.
    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   ///
     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.
    19091907  /// The values of the map can be accessed
    19101908  /// with stl compatible forward iterator.
     1909  ///
     1910  /// This type is not reference map, so it cannot be modified with
     1911  /// the subscript operator.
    19111912  ///
    19121913  /// \tparam GR The graph type.
     
    19241925      template Map<V>::Type Map;
    19251926
    1926     typedef std::map<V, K> Container;
     1927    typedef std::multimap<V, K> Container;
    19271928    Container _inv_map;
    19281929
     
    19491950    /// iterator on the values of the map. The values can
    19501951    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     1952    /// They are considered with multiplicity, so each value is
     1953    /// traversed for each item it is assigned to.
    19511954    class ValueIterator
    19521955      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20012004    void set(const Key& key, const Value& val) {
    20022005      Value oldval = Map::operator[](key);
    2003       typename Container::iterator it = _inv_map.find(oldval);
    2004       if (it != _inv_map.end() && it->second == key) {
    2005         _inv_map.erase(it);
     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        }
    20062013      }
    2007       _inv_map.insert(make_pair(val, key));
     2014      _inv_map.insert(std::make_pair(val, key));
    20082015      Map::set(key, val);
    20092016    }
     
    20172024    }
    20182025
    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);
     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);
    20242034      return it != _inv_map.end() ? it->second : INVALID;
    20252035    }
     
    20332043    virtual void erase(const Key& key) {
    20342044      Value val = Map::operator[](key);
    2035       typename Container::iterator it = _inv_map.find(val);
    2036       if (it != _inv_map.end() && it->second == key) {
    2037         _inv_map.erase(it);
     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        }
    20382052      }
    20392053      Map::erase(key);
     
    20472061      for (int i = 0; i < int(keys.size()); ++i) {
    20482062        Value val = Map::operator[](keys[i]);
    2049         typename Container::iterator it = _inv_map.find(val);
    2050         if (it != _inv_map.end() && it->second == keys[i]) {
    2051           _inv_map.erase(it);
     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          }
    20522070        }
    20532071      }
     
    20852103      /// \brief Subscript operator.
    20862104      ///
    2087       /// Subscript operator. It gives back the item
    2088       /// that was last assigned to the given value.
     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.
    20892108      Value operator[](const Key& key) const {
    20902109        return _inverted(key);
  • lemon/suurballe.h

    r670 r843  
    4646  /// Note that this problem is a special case of the \ref min_cost_flow
    4747  /// "minimum cost flow problem". This implementation is actually an
    48   /// efficient specialized version of the \ref CapacityScaling
    49   /// "Successive Shortest Path" algorithm directly for this problem.
     48  /// efficient specialized version of the Successive Shortest Path
     49  /// algorithm directly for this problem.
    5050  /// Therefore this class provides query functions for flow values and
    5151  /// node potentials (the dual solution) just like the minimum cost flow
  • test/maps_test.cc

    r554 r731  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/list_graph.h>
    2526
    2627#include "test_tools.h"
     
    349350      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    350351  }
     352 
     353  // CrossRefMap
     354  {
     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  }
    351386
    352387  return 0;
Note: See TracChangeset for help on using the changeset viewer.