COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
9 deleted
22 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r762 r710  
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
    … …  
    239247any kind of path structure.
    240248
    241 \sa \ref concepts::Path "Path concept"
    242 */
    243 
    244 /**
    245 @defgroup heaps Heap Structures
    246 @ingroup datas
    247 \brief %Heap structures implemented in LEMON.
    248 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used easily in such algorithms.
    261 
    262 \sa \ref concepts::Heap "Heap concept"
    263 */
    264 
    265 /**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
     249\sa lemon::concepts::Path
    271250*/
    272251
    … …  
    278257This group contains some data structures implemented in LEMON in
    279258order to make it easier to implement combinatorial algorithms.
    280 */
    281 
    282 /**
    283 @defgroup geomdat Geometric Data Structures
    284 @ingroup auxdat
    285 \brief Geometric data structures implemented in LEMON.
    286 
    287 This group contains geometric data structures implemented in LEMON.
    288 
    289  - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
    290    vector with the usual operations.
    291  - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
    292    rectangular bounding box of a set of \ref lemon::dim2::Point
    293    "dim2::Point"'s.
    294 */
    295 
    296 /**
    297 @defgroup matrices Matrices
    298 @ingroup auxdat
    299 \brief Two dimensional data storages implemented in LEMON.
    300 
    301 This group contains two dimensional data storages implemented in LEMON.
    302259*/
    303260
    … …  
    342299
    343300/**
    344 @defgroup spantree Minimum Spanning Tree Algorithms
    345 @ingroup algs
    346 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    347 
    348 This group contains the algorithms for finding minimum cost spanning
    349 trees and arborescences.
    350 */
    351 
    352 /**
    353301@defgroup max_flow Maximum Flow Algorithms
    354302@ingroup algs
    … …  
    428376
    429377\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    430     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
     378    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    431379
    432380LEMON contains several algorithms related to minimum cut problems:
    … …  
    441389If you want to find minimum cut just between two distinict nodes,
    442390see the \ref max_flow "maximum flow problem".
     391*/
     392
     393/**
     394@defgroup graph_properties Connectivity and Other Graph Properties
     395@ingroup algs
     396\brief Algorithms for discovering the graph properties
     397
     398This group contains the algorithms for discovering the graph properties
     399like connectivity, bipartiteness, euler property, simplicity etc.
     400
     401\image html edge_biconnected_components.png
     402\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     403*/
     404
     405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
    443415*/
    444416
    … …  
    484456
    485457/**
    486 @defgroup graph_properties Connectivity and Other Graph Properties
    487 @ingroup algs
    488 \brief Algorithms for discovering the graph properties
    489 
    490 This group contains the algorithms for discovering the graph properties
    491 like connectivity, bipartiteness, euler property, simplicity etc.
    492 
    493 \image html connected_components.png
    494 \image latex connected_components.eps "Connected components" width=\textwidth
    495 */
    496 
    497 /**
    498 @defgroup planar Planarity Embedding and Drawing
    499 @ingroup algs
    500 \brief Algorithms for planarity checking, embedding and drawing
    501 
    502 This group contains the algorithms for planarity checking,
    503 embedding and drawing.
    504 
    505 \image html planar.png
    506 \image latex planar.eps "Plane graph" width=\textwidth
     458@defgroup spantree Minimum Spanning Tree Algorithms
     459@ingroup algs
     460\brief Algorithms for finding minimum cost spanning trees and arborescences.
     461
     462This group contains the algorithms for finding minimum cost spanning
     463trees and arborescences.
     464*/
     465
     466/**
     467@defgroup auxalg Auxiliary Algorithms
     468@ingroup algs
     469\brief Auxiliary algorithms implemented in LEMON.
     470
     471This group contains some algorithms implemented in LEMON
     472in order to make it easier to implement complex algorithms.
    507473*/
    508474
    … …  
    514480This group contains the approximation and heuristic algorithms
    515481implemented in LEMON.
    516 */
    517 
    518 /**
    519 @defgroup auxalg Auxiliary Algorithms
    520 @ingroup algs
    521 \brief Auxiliary algorithms implemented in LEMON.
    522 
    523 This group contains some algorithms implemented in LEMON
    524 in order to make it easier to implement complex algorithms.
    525482*/
    526483
    … …  
    631588
    632589/**
    633 @defgroup dimacs_group DIMACS Format
     590@defgroup dimacs_group DIMACS format
    634591@ingroup io_group
    635592\brief Read and write files in DIMACS format
    … …  
    693650
    694651/**
     652\anchor demoprograms
     653
     654@defgroup demos Demo Programs
     655
     656Some demo programs are listed here. Their full source codes can be found in
     657the \c demo subdirectory of the source tree.
     658
     659In order to compile them, use the <tt>make demo</tt> or the
     660<tt>make check</tt> commands.
     661*/
     662
     663/**
    695664@defgroup tools Standalone Utility Applications
    696665
    … …  
    701670*/
    702671
    703 /**
    704 \anchor demoprograms
    705 
    706 @defgroup demos Demo Programs
    707 
    708 Some demo programs are listed here. Their full source codes can be found in
    709 the \c demo subdirectory of the source tree.
    710 
    711 In order to compile them, use the <tt>make demo</tt> or the
    712 <tt>make check</tt> commands.
    713 */
    714 
    715672}

  • lemon/Makefile.am

    r755 r714  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
    60         lemon/bellman_ford.h \
    6160        lemon/bfs.h \
    6261        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
    64         lemon/bucket_heap.h \
    6562        lemon/cbc.h \
    6663        lemon/circulation.h \
    … …  
    8077        lemon/error.h \
    8178        lemon/euler.h \
    82         lemon/fib_heap.h \
    83         lemon/fourary_heap.h \
    8479        lemon/full_graph.h \
    8580        lemon/glpk.h \
    … …  
    8883        lemon/grid_graph.h \
    8984        lemon/hypercube_graph.h \
    90         lemon/kary_heap.h \
    9185        lemon/kruskal.h \
    9286        lemon/hao_orlin.h \
    … …  
    9791        lemon/lp_base.h \
    9892        lemon/lp_skeleton.h \
     93        lemon/list_graph.h \
    9994        lemon/maps.h \
    10095        lemon/matching.h \
    … …  
    10398        lemon/nauty_reader.h \
    10499        lemon/network_simplex.h \
    105         lemon/pairing_heap.h \
    106100        lemon/path.h \
    107101        lemon/preflow.h \
    108         lemon/radix_heap.h \
    109102        lemon/radix_sort.h \
    110103        lemon/random.h \

  • lemon/bfs.h

    r764 r763  
    415415    ///The simplest way to execute the BFS algorithm is to use one of the
    416416    ///member functions called \ref run(Node) "run()".\n
    417     ///If you need better control on the execution, you have to call
    418     ///\ref init() first, then you can add several source nodes with
     417    ///If you need more control on the execution, first you have to call
     418    ///\ref init(), then you can add several source nodes with
    419419    ///\ref addSource(). Finally the actual path computation can be
    420420    ///performed with one of the \ref start() functions.
    … …  
    14231423    /// The simplest way to execute the BFS algorithm is to use one of the
    14241424    /// member functions called \ref run(Node) "run()".\n
    1425     /// If you need better control on the execution, you have to call
    1426     /// \ref init() first, then you can add several source nodes with
     1425    /// If you need more control on the execution, first you have to call
     1426    /// \ref init(), then you can add several source nodes with
    14271427    /// \ref addSource(). Finally the actual path computation can be
    14281428    /// performed with one of the \ref start() functions.

  • lemon/bin_heap.h

    r758 r631  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Binary heap implementation.
     24///\brief Binary Heap implementation.
    2525
    2626#include <vector>
    … …  
    3030namespace lemon {
    3131
    32   /// \ingroup heaps
     32  ///\ingroup auxdat
    3333  ///
    34   /// \brief Binary heap data structure.
     34  ///\brief A Binary Heap implementation.
    3535  ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
    3843  ///
    39   /// \tparam PR Type of the priorities of the items.
    40   /// \tparam IM A read-writable item map with \c int values, used
    41   /// internally to handle the cross references.
    42   /// \tparam CMP A functor class for comparing the priorities.
    43   /// The default is \c std::less<PR>.
    44 #ifdef DOXYGEN
    45   template <typename PR, typename IM, typename CMP>
    46 #else
    47   template <typename PR, typename IM, typename CMP = std::less<PR> >
    48 #endif
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
     46  ///to handle the cross references.
     47  ///\tparam Comp A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
     49  ///
     50  ///\sa FibHeap
     51  ///\sa Dijkstra
     52  template <typename PR, typename IM, typename Comp = std::less<PR> >
    4953  class BinHeap {
     54
    5055  public:
    51 
    52     /// Type of the item-int map.
     56    ///\e
    5357    typedef IM ItemIntMap;
    54     /// Type of the priorities.
     58    ///\e
    5559    typedef PR Prio;
    56     /// Type of the items stored in the heap.
     60    ///\e
    5761    typedef typename ItemIntMap::Key Item;
    58     /// Type of the item-priority pairs.
     62    ///\e
    5963    typedef std::pair<Item,Prio> Pair;
    60     /// Functor type for comparing the priorities.
    61     typedef CMP Compare;
    62 
    63     /// \brief Type to represent the states of the items.
    64     ///
    65     /// Each item has a state associated to it. It can be "in heap",
    66     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     64    ///\e
     65    typedef Comp Compare;
     66
     67    /// \brief Type to represent the items states.
     68    ///
     69    /// Each Item element have a state associated to it. It may be "in heap",
     70    /// "pre heap" or "post heap". The latter two are indifferent from the
    6771    /// heap's point of view, but may be useful to the user.
    6872    ///
    … …  
    8185
    8286  public:
    83 
    84     /// \brief Constructor.
    85     ///
    86     /// Constructor.
    87     /// \param map A map that assigns \c int values to the items.
    88     /// It is used internally to handle the cross references.
    89     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     87    /// \brief The constructor.
     88    ///
     89    /// The constructor.
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
    9093    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9194
    92     /// \brief Constructor.
    93     ///
    94     /// Constructor.
    95     /// \param map A map that assigns \c int values to the items.
    96     /// It is used internally to handle the cross references.
    97     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     /// \param comp The function object used for comparing the priorities.
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
     99    /// internally to handle the cross references. The value of the map
     100    /// should be PRE_HEAP (-1) for each element.
     101    ///
     102    /// \param comp The comparator function object.
    99103    BinHeap(ItemIntMap &map, const Compare &comp)
    100104      : _iim(map), _comp(comp) {}
    101105
    102106
    103     /// \brief The number of items stored in the heap.
    104     ///
    105     /// This function returns the number of items stored in the heap.
     107    /// The number of items stored in the heap.
     108    ///
     109    /// \brief Returns the number of items stored in the heap.
    106110    int size() const { return _data.size(); }
    107111
    108     /// \brief Check if the heap is empty.
    109     ///
    110     /// This function returns \c true if the heap is empty.
     112    /// \brief Checks if the heap stores no items.
     113    ///
     114    /// Returns \c true if and only if the heap stores no items.
    111115    bool empty() const { return _data.empty(); }
    112116
    113     /// \brief Make the heap empty.
    114     ///
    115     /// This functon makes the heap empty.
    116     /// It does not change the cross reference map. If you want to reuse
    117     /// a heap that is not surely empty, you should first clear it and
    118     /// then you should set the cross reference map to \c PRE_HEAP
    119     /// for each item.
     117    /// \brief Make empty this heap.
     118    ///
     119    /// Make empty this heap. It does not change the cross reference map.
     120    /// If you want to reuse what is not surely empty you should first clear
     121    /// the heap and after that you should set the cross reference map for
     122    /// each item to \c PRE_HEAP.
    120123    void clear() {
    121124      _data.clear();
    … …  
    125128    static int parent(int i) { return (i-1)/2; }
    126129
    127     static int secondChild(int i) { return 2*i+2; }
     130    static int second_child(int i) { return 2*i+2; }
    128131    bool less(const Pair &p1, const Pair &p2) const {
    129132      return _comp(p1.second, p2.second);
    130133    }
    131134
    132     int bubbleUp(int hole, Pair p) {
     135    int bubble_up(int hole, Pair p) {
    133136      int par = parent(hole);
    134137      while( hole>0 && less(p,_data[par]) ) {
    … …  
    141144    }
    142145
    143     int bubbleDown(int hole, Pair p, int length) {
    144       int child = secondChild(hole);
     146    int bubble_down(int hole, Pair p, int length) {
     147      int child = second_child(hole);
    145148      while(child < length) {
    146149        if( less(_data[child-1], _data[child]) ) {
    … …  
    151154        move(_data[child], hole);
    152155        hole = child;
    153         child = secondChild(hole);
     156        child = second_child(hole);
    154157      }
    155158      child--;
    … …  
    169172
    170173  public:
    171 
    172174    /// \brief Insert a pair of item and priority into the heap.
    173175    ///
    174     /// This function inserts \c p.first to the heap with priority
    175     /// \c p.second.
     176    /// Adds \c p.first to the heap with priority \c p.second.
    176177    /// \param p The pair to insert.
    177     /// \pre \c p.first must not be stored in the heap.
    178178    void push(const Pair &p) {
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubbleUp(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given priority.
    185     ///
    186     /// This function inserts the given item into the heap with the
    187     /// given priority.
     181      bubble_up(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given heap.
     185    ///
     186    /// Adds \c i to the heap with priority \c p.
    188187    /// \param i The item to insert.
    189188    /// \param p The priority of the item.
    190     /// \pre \e i must not be stored in the heap.
    191189    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    192190
    193     /// \brief Return the item having minimum priority.
    194     ///
    195     /// This function returns the item having minimum priority.
    196     /// \pre The heap must be non-empty.
     191    /// \brief Returns the item with minimum priority relative to \c Compare.
     192    ///
     193    /// This method returns the item with minimum priority relative to \c
     194    /// Compare.
     195    /// \pre The heap must be nonempty.
    197196    Item top() const {
    198197      return _data[0].first;
    199198    }
    200199
    201     /// \brief The minimum priority.
    202     ///
    203     /// This function returns the minimum priority.
    204     /// \pre The heap must be non-empty.
     200    /// \brief Returns the minimum priority relative to \c Compare.
     201    ///
     202    /// It returns the minimum priority relative to \c Compare.
     203    /// \pre The heap must be nonempty.
    205204    Prio prio() const {
    206205      return _data[0].second;
    207206    }
    208207
    209     /// \brief Remove the item having minimum priority.
    210     ///
    211     /// This function removes the item having minimum priority.
     208    /// \brief Deletes the item with minimum priority relative to \c Compare.
     209    ///
     210    /// This method deletes the item with minimum priority relative to \c
     211    /// Compare from the heap.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
    … …  
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubbleDown(0, _data[n], n);
     217        bubble_down(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Remove the given item from the heap.
    223     ///
    224     /// This function removes the given item from the heap if it is
    225     /// already stored.
    226     /// \param i The item to delete.
    227     /// \pre \e i must be in the heap.
     222    /// \brief Deletes \c i from the heap.
     223    ///
     224    /// This method deletes item \c i from the heap.
     225    /// \param i The item to erase.
     226    /// \pre The item should be in the heap.
    228227    void erase(const Item &i) {
    229228      int h = _iim[i];
    … …  
    231230      _iim.set(_data[h].first, POST_HEAP);
    232231      if( h < n ) {
    233         if ( bubbleUp(h, _data[n]) == h) {
    234           bubbleDown(h, _data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    235234        }
    236235      }
    … …  
    238237    }
    239238
    240     /// \brief The priority of the given item.
    241     ///
    242     /// This function returns the priority of the given item.
    243     /// \param i The item.
    244     /// \pre \e i must be in the heap.
     239
     240    /// \brief Returns the priority of \c i.
     241    ///
     242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
     244    /// \pre \c i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
    … …  
    248248    }
    249249
    250     /// \brief Set the priority of an item or insert it, if it is
    251     /// not stored in the heap.
    252     ///
    253     /// This method sets the priority of the given item if it is
    254     /// already stored in the heap. Otherwise it inserts the given
    255     /// item into the heap with the given priority.
     250    /// \brief \c i gets to the heap with priority \c p independently
     251    /// if \c i was already there.
     252    ///
     253    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     254    /// in the heap and sets the priority of \c i to \c p otherwise.
    256255    /// \param i The item.
    257256    /// \param p The priority.
    … …  
    262261      }
    263262      else if( _comp(p, _data[idx].second) ) {
    264         bubbleUp(idx, Pair(i,p));
     263        bubble_up(idx, Pair(i,p));
    265264      }
    266265      else {
    267         bubbleDown(idx, Pair(i,p), _data.size());
    268       }
    269     }
    270 
    271     /// \brief Decrease the priority of an item to the given value.
    272     ///
    273     /// This function decreases the priority of an item to the given value.
     266        bubble_down(idx, Pair(i,p), _data.size());
     267      }
     268    }
     269
     270    /// \brief Decreases the priority of \c i to \c p.
     271    ///
     272    /// This method decreases the priority of item \c i to \c p.
    274273    /// \param i The item.
    275274    /// \param p The priority.
    276     /// \pre \e i must be stored in the heap with priority at least \e p.
     275    /// \pre \c i must be stored in the heap with priority at least \c
     276    /// p relative to \c Compare.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubbleUp(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increase the priority of an item to the given value.
    283     ///
    284     /// This function increases the priority of an item to the given value.
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \e i must be stored in the heap with priority at most \e p.
     287    /// \pre \c i must be stored in the heap with priority at most \c
     288    /// p relative to \c Compare.
    288289    void increase(const Item &i, const Prio &p) {
    289290      int idx = _iim[i];
    290       bubbleDown(idx, Pair(i,p), _data.size());
    291     }
    292 
    293     /// \brief Return the state of an item.
    294     ///
    295     /// This method returns \c PRE_HEAP if the given item has never
    296     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    297     /// and \c POST_HEAP otherwise.
    298     /// In the latter case it is possible that the item will get back
    299     /// to the heap again.
     291      bubble_down(idx, Pair(i,p), _data.size());
     292    }
     293
     294    /// \brief Returns if \c item is in, has already been in, or has
     295    /// never been in the heap.
     296    ///
     297    /// This method returns PRE_HEAP if \c item has never been in the
     298    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     299    /// otherwise. In the latter case it is possible that \c item will
     300    /// get back to the heap again.
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
    … …  
    306307    }
    307308
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     309    /// \brief Sets the state of the \c item in the heap.
     310    ///
     311    /// Sets the state of the \c item in the heap. It can be used to
     312    /// manually clear the heap when it is important to achive the
     313    /// better time complexity.
    313314    /// \param i The item.
    314315    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    327328    }
    328329
    329     /// \brief Replace an item in the heap.
    330     ///
    331     /// This function replaces item \c i with item \c j.
    332     /// Item \c i must be in the heap, while \c j must be out of the heap.
    333     /// After calling this method, item \c i will be out of the
    334     /// heap and \c j will be in the heap with the same prioriority
    335     /// as item \c i had before.
     330    /// \brief Replaces an item in the heap.
     331    ///
     332    /// The \c i item is replaced with \c j item. The \c i item should
     333    /// be in the heap, while the \c j should be out of the heap. The
     334    /// \c i item will out of the heap and \c j will be in the heap
     335    /// with the same prioriority as prevoiusly the \c i item.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];

  • lemon/bits/edge_set_extender.h

    r732 r664  
    538538
    539539    public:
    540       explicit ArcMap(const Graph& _g)
     540      ArcMap(const Graph& _g)
    541541        : Parent(_g) {}
    542542      ArcMap(const Graph& _g, const _Value& _v)
    … …  
    562562
    563563    public:
    564       explicit EdgeMap(const Graph& _g)
     564      EdgeMap(const Graph& _g)
    565565        : Parent(_g) {}
    566566

  • lemon/bits/graph_extender.h

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

  • lemon/circulation.h

    r762 r688  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
    75 #ifdef DOXYGEN
    76     typedef GR::ArcMap<Value> FlowMap;
    77 #else
    7875    typedef typename Digraph::template ArcMap<Value> FlowMap;
    79 #endif
    8076
    8177    /// \brief Instantiates a FlowMap.
    … …  
    9288    /// The elevator type used by the algorithm.
    9389    ///
    94     /// \sa Elevator, LinkedElevator
    95 #ifdef DOXYGEN
    96     typedef lemon::Elevator<GR, GR::Node> Elevator;
    97 #else
     90    /// \sa Elevator
     91    /// \sa LinkedElevator
    9892    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    99 #endif
    10093
    10194    /// \brief Instantiates an Elevator.
    … …  
    458451    }
    459452
    460     /// \brief Sets the tolerance used by the algorithm.
    461     ///
    462     /// Sets the tolerance object used by the algorithm.
    463     /// \return <tt>(*this)</tt>
    464     Circulation& tolerance(const Tolerance& tolerance) {
     453    /// \brief Sets the tolerance used by algorithm.
     454    ///
     455    /// Sets the tolerance used by algorithm.
     456    Circulation& tolerance(const Tolerance& tolerance) const {
    465457      _tol = tolerance;
    466458      return *this;
    … …  
    469461    /// \brief Returns a const reference to the tolerance.
    470462    ///
    471     /// Returns a const reference to the tolerance object used by
    472     /// the algorithm.
     463    /// Returns a const reference to the tolerance.
    473464    const Tolerance& tolerance() const {
    474       return _tol;
     465      return tolerance;
    475466    }
    476467
    477468    /// \name Execution Control
    478469    /// The simplest way to execute the algorithm is to call \ref run().\n
    479     /// If you need better control on the initial solution or the execution,
    480     /// you have to call one of the \ref init() functions first, then
     470    /// If you need more control on the initial solution or the execution,
     471    /// first you have to call one of the \ref init() functions, then
    481472    /// the \ref start() function.
    482473

  • lemon/concepts/heap.h

    r757 r631  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_HEAP_H
    20 #define LEMON_CONCEPTS_HEAP_H
    21 
    2219///\ingroup concept
    2320///\file
    2421///\brief The concept of heaps.
    2522
     23#ifndef LEMON_CONCEPTS_HEAP_H
     24#define LEMON_CONCEPTS_HEAP_H
     25
    2626#include <lemon/core.h>
    2727#include <lemon/concept_check.h>
    … …  
    3636    /// \brief The heap concept.
    3737    ///
    38     /// This concept class describes the main interface of heaps.
    39     /// The various \ref heaps "heap structures" are efficient
    40     /// implementations of the abstract data type \e priority \e queue.
    41     /// They store items with specified values called \e priorities
    42     /// in such a way that finding and removing the item with minimum
    43     /// priority are efficient. The basic operations are adding and
    44     /// erasing items, changing the priority of an item, etc.
     38    /// Concept class describing the main interface of heaps. A \e heap
     39    /// is a data structure for storing items with specified values called
     40    /// \e priorities in such a way that finding the item with minimum
     41    /// priority is efficient. In a heap one can change the priority of an
     42    /// item, add or erase an item, etc.
    4543    ///
    46     /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    47     /// Any class that conforms to this concept can be used easily in such
    48     /// algorithms.
    49     ///
    50     /// \tparam PR Type of the priorities of the items.
    51     /// \tparam IM A read-writable item map with \c int values, used
     44    /// \tparam PR Type of the priority of the items.
     45    /// \tparam IM A read and writable item map with int values, used
    5246    /// internally to handle the cross references.
    53     /// \tparam CMP A functor class for comparing the priorities.
     47    /// \tparam Comp A functor class for the ordering of the priorities.
    5448    /// The default is \c std::less<PR>.
    5549#ifdef DOXYGEN
    56     template <typename PR, typename IM, typename CMP>
     50    template <typename PR, typename IM, typename Comp = std::less<PR> >
    5751#else
    58     template <typename PR, typename IM, typename CMP = std::less<PR> >
     52    template <typename PR, typename IM>
    5953#endif
    6054    class Heap {
    … …  
    7165      ///
    7266      /// Each item has a state associated to it. It can be "in heap",
    73       /// "pre-heap" or "post-heap". The latter two are indifferent from the
    74       /// heap's point of view, but may be useful to the user.
     67      /// "pre heap" or "post heap". The later two are indifferent
     68      /// from the point of view of the heap, but may be useful for
     69      /// the user.
    7570      ///
    7671      /// The item-int map must be initialized in such way that it assigns
    … …  
    7873      enum State {
    7974        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    80         PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
    81         POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
     75        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
     76        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
    8277      };
    8378
    84       /// \brief Constructor.
    85       ///
    86       /// Constructor.
     79      /// \brief The constructor.
     80      ///
     81      /// The constructor.
    8782      /// \param map A map that assigns \c int values to keys of type
    8883      /// \c Item. It is used internally by the heap implementations to
    8984      /// handle the cross references. The assigned value must be
    90       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     85      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
    9186      explicit Heap(ItemIntMap &map) {}
    9287
    93       /// \brief Constructor.
    94       ///
    95       /// Constructor.
    96       /// \param map A map that assigns \c int values to keys of type
    97       /// \c Item. It is used internally by the heap implementations to
    98       /// handle the cross references. The assigned value must be
    99       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    100       /// \param comp The function object used for comparing the priorities.
    101       explicit Heap(ItemIntMap &map, const CMP &comp) {}
    102 
    10388      /// \brief The number of items stored in the heap.
    10489      ///
    105       /// This function returns the number of items stored in the heap.
     90      /// Returns the number of items stored in the heap.
    10691      int size() const { return 0; }
    10792
    108       /// \brief Check if the heap is empty.
    109       ///
    110       /// This function returns \c true if the heap is empty.
     93      /// \brief Checks if the heap is empty.
     94      ///
     95      /// Returns \c true if the heap is empty.
    11196      bool empty() const { return false; }
    11297
    113       /// \brief Make the heap empty.
    114       ///
    115       /// This functon makes the heap empty.
    116       /// It does not change the cross reference map. If you want to reuse
    117       /// a heap that is not surely empty, you should first clear it and
    118       /// then you should set the cross reference map to \c PRE_HEAP
    119       /// for each item.
    120       void clear() {}
    121 
    122       /// \brief Insert an item into the heap with the given priority.
    123       ///
    124       /// This function inserts the given item into the heap with the
    125       /// given priority.
     98      /// \brief Makes the heap empty.
     99      ///
     100      /// Makes the heap empty.
     101      void clear();
     102
     103      /// \brief Inserts an item into the heap with the given priority.
     104      ///
     105      /// Inserts the given item into the heap with the given priority.
    126106      /// \param i The item to insert.
    127107      /// \param p The priority of the item.
    128       /// \pre \e i must not be stored in the heap.
    129108      void push(const Item &i, const Prio &p) {}
    130109
    131       /// \brief Return the item having minimum priority.
    132       ///
    133       /// This function returns the item having minimum priority.
     110      /// \brief Returns the item having minimum priority.
     111      ///
     112      /// Returns the item having minimum priority.
    134113      /// \pre The heap must be non-empty.
    135114      Item top() const {}
    … …  
    137116      /// \brief The minimum priority.
    138117      ///
    139       /// This function returns the minimum priority.
     118      /// Returns the minimum priority.
    140119      /// \pre The heap must be non-empty.
    141120      Prio prio() const {}
    142121
    143       /// \brief Remove the item having minimum priority.
    144       ///
    145       /// This function removes the item having minimum priority.
     122      /// \brief Removes the item having minimum priority.
     123      ///
     124      /// Removes the item having minimum priority.
    146125      /// \pre The heap must be non-empty.
    147126      void pop() {}
    148127
    149       /// \brief Remove the given item from the heap.
    150       ///
    151       /// This function removes the given item from the heap if it is
    152       /// already stored.
     128      /// \brief Removes an item from the heap.
     129      ///
     130      /// Removes the given item from the heap if it is already stored.
    153131      /// \param i The item to delete.
    154       /// \pre \e i must be in the heap.
    155132      void erase(const Item &i) {}
    156133
    157       /// \brief The priority of the given item.
    158       ///
    159       /// This function returns the priority of the given item.
    160       /// \param i The item.
    161       /// \pre \e i must be in the heap.
     134      /// \brief The priority of an item.
     135      ///
     136      /// Returns the priority of the given item.
     137      /// \param i The item.
     138      /// \pre \c i must be in the heap.
    162139      Prio operator[](const Item &i) const {}
    163140
    164       /// \brief Set the priority of an item or insert it, if it is
     141      /// \brief Sets the priority of an item or inserts it, if it is
    165142      /// not stored in the heap.
    166143      ///
    167144      /// This method sets the priority of the given item if it is
    168       /// already stored in the heap. Otherwise it inserts the given
    169       /// item into the heap with the given priority.
     145      /// already stored in the heap.
     146      /// Otherwise it inserts the given item with the given priority.
    170147      ///
    171148      /// \param i The item.
    … …  
    173150      void set(const Item &i, const Prio &p) {}
    174151
    175       /// \brief Decrease the priority of an item to the given value.
    176       ///
    177       /// This function decreases the priority of an item to the given value.
     152      /// \brief Decreases the priority of an item to the given value.
     153      ///
     154      /// Decreases the priority of an item to the given value.
    178155      /// \param i The item.
    179156      /// \param p The priority.
    180       /// \pre \e i must be stored in the heap with priority at least \e p.
     157      /// \pre \c i must be stored in the heap with priority at least \c p.
    181158      void decrease(const Item &i, const Prio &p) {}
    182159
    183       /// \brief Increase the priority of an item to the given value.
    184       ///
    185       /// This function increases the priority of an item to the given value.
     160      /// \brief Increases the priority of an item to the given value.
     161      ///
     162      /// Increases the priority of an item to the given value.
    186163      /// \param i The item.
    187164      /// \param p The priority.
    188       /// \pre \e i must be stored in the heap with priority at most \e p.
     165      /// \pre \c i must be stored in the heap with priority at most \c p.
    189166      void increase(const Item &i, const Prio &p) {}
    190167
    191       /// \brief Return the state of an item.
     168      /// \brief Returns if an item is in, has already been in, or has
     169      /// never been in the heap.
    192170      ///
    193171      /// This method returns \c PRE_HEAP if the given item has never
    … …  
    199177      State state(const Item &i) const {}
    200178
    201       /// \brief Set the state of an item in the heap.
    202       ///
    203       /// This function sets the state of the given item in the heap.
    204       /// It can be used to manually clear the heap when it is important
    205       /// to achive better time complexity.
     179      /// \brief Sets the state of an item in the heap.
     180      ///
     181      /// Sets the state of the given item in the heap. It can be used
     182      /// to manually clear the heap when it is important to achive the
     183      /// better time complexity.
    206184      /// \param i The item.
    207185      /// \param st The state. It should not be \c IN_HEAP.

  • lemon/dfs.h

    r764 r763  
    413413    ///The simplest way to execute the DFS algorithm is to use one of the
    414414    ///member functions called \ref run(Node) "run()".\n
    415     ///If you need better control on the execution, you have to call
    416     ///\ref init() first, then you can add a source node with \ref addSource()
     415    ///If you need more control on the execution, first you have to call
     416    ///\ref init(), then you can add a source node with \ref addSource()
    417417    ///and perform the actual computation with \ref start().
    418418    ///This procedure can be repeated if there are nodes that have not
    … …  
    13651365    /// The simplest way to execute the DFS algorithm is to use one of the
    13661366    /// member functions called \ref run(Node) "run()".\n
    1367     /// If you need better control on the execution, you have to call
    1368     /// \ref init() first, then you can add a source node with \ref addSource()
     1367    /// If you need more control on the execution, first you have to call
     1368    /// \ref init(), then you can add a source node with \ref addSource()
    13691369    /// and perform the actual computation with \ref start().
    13701370    /// This procedure can be repeated if there are nodes that have not

  • lemon/dijkstra.h

    r764 r763  
    590590    ///The simplest way to execute the %Dijkstra algorithm is to use
    591591    ///one of the member functions called \ref run(Node) "run()".\n
    592     ///If you need better control on the execution, you have to call
    593     ///\ref init() first, then you can add several source nodes with
     592    ///If you need more control on the execution, first you have to call
     593    ///\ref init(), then you can add several source nodes with
    594594    ///\ref addSource(). Finally the actual path computation can be
    595595    ///performed with one of the \ref start() functions.

  • lemon/dim2.h

    r761 r463  
    2222#include <iostream>
    2323
    24 ///\ingroup geomdat
     24///\ingroup misc
    2525///\file
    2626///\brief A simple two dimensional vector and a bounding box implementation
     27///
     28/// The class \ref lemon::dim2::Point "dim2::Point" implements
     29/// a two dimensional vector with the usual operations.
     30///
     31/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
     32/// the rectangular bounding box of a set of
     33/// \ref lemon::dim2::Point "dim2::Point"'s.
    2734
    2835namespace lemon {
    … …  
    3441  namespace dim2 {
    3542
    36   /// \addtogroup geomdat
     43  /// \addtogroup misc
    3744  /// @{
    3845

  • lemon/gomory_hu.h

    r760 r643  
    360360    /// \c t.
    361361    /// \code
    362     /// GomoryHu<Graph> gom(g, capacities);
     362    /// GomoruHu<Graph> gom(g, capacities);
    363363    /// gom.run();
    364364    /// int cnt=0;
    365     /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
     365    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
    366366    /// \endcode
    367367    class MinCutNodeIt
    … …  
    457457    /// \c t.
    458458    /// \code
    459     /// GomoryHu<Graph> gom(g, capacities);
     459    /// GomoruHu<Graph> gom(g, capacities);
    460460    /// gom.run();
    461461    /// int value=0;
    462     /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
     462    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
    463463    ///   value+=capacities[e];
    464464    /// \endcode

  • lemon/maps.h

    r764 r763  
    2323#include <functional>
    2424#include <vector>
    25 #include <map>
    2625
    2726#include <lemon/core.h>
    … …  
    3029///\ingroup maps
    3130///\brief Miscellaneous property maps
     31
     32#include <map>
    3233
    3334namespace lemon {
    … …  
    18181819  ///
    18191820  /// IdMap provides a unique and immutable id for each item of the
    1820   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
     1821  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
    18211822  ///  - \b unique: different items get different ids,
    18221823  ///  - \b immutable: the id of an item does not change (even if you
    … …  
    19021903
    19031904  /// This class provides simple invertable graph maps.
    1904   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
    1905   /// 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  ///
    19061909  /// The values of the map can be accessed
    19071910  /// with stl compatible forward iterator.
    1908   ///
    1909   /// This type is not reference map, so it cannot be modified with
    1910   /// the subscript operator.
    19111911  ///
    19121912  /// \tparam GR The graph type.
    … …  
    19241924      template Map<V>::Type Map;
    19251925
    1926     typedef std::multimap<V, K> Container;
     1926    typedef std::map<V, K> Container;
    19271927    Container _inv_map;
    19281928
    … …  
    19491949    /// iterator on the values of the map. The values can
    19501950    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    1951     /// They are considered with multiplicity, so each value is
    1952     /// traversed for each item it is assigned to.
    19531951    class ValueIterator
    19541952      : public std::iterator<std::forward_iterator_tag, Value> {
    … …  
    20032001    void set(const Key& key, const Value& val) {
    20042002      Value oldval = Map::operator[](key);
    2005       typename Container::iterator it;
    2006       for (it = _inv_map.equal_range(oldval).first;
    2007            it != _inv_map.equal_range(oldval).second; ++it) {
    2008         if (it->second == key) {
    2009           _inv_map.erase(it);
    2010           break;
    2011         }
     2003      typename Container::iterator it = _inv_map.find(oldval);
     2004      if (it != _inv_map.end() && it->second == key) {
     2005        _inv_map.erase(it);
    20122006      }
    2013       _inv_map.insert(std::make_pair(val, key));
     2007      _inv_map.insert(make_pair(val, key));
    20142008      Map::set(key, val);
    20152009    }
    … …  
    20232017    }
    20242018
    2025     /// \brief Gives back an item by its value.
    2026     ///
    2027     /// This function gives back an item that is assigned to
    2028     /// the given value or \c INVALID if no such item exists.
    2029     /// If there are more items with the same associated value,
    2030     /// only one of them is returned.
    2031     Key operator()(const Value& val) const {
    2032       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);
    20332024      return it != _inv_map.end() ? it->second : INVALID;
    20342025    }
    … …  
    20422033    virtual void erase(const Key& key) {
    20432034      Value val = Map::operator[](key);
    2044       typename Container::iterator it;
    2045       for (it = _inv_map.equal_range(val).first;
    2046            it != _inv_map.equal_range(val).second; ++it) {
    2047         if (it->second == key) {
    2048           _inv_map.erase(it);
    2049           break;
    2050         }
     2035      typename Container::iterator it = _inv_map.find(val);
     2036      if (it != _inv_map.end() && it->second == key) {
     2037        _inv_map.erase(it);
    20512038      }
    20522039      Map::erase(key);
    … …  
    20602047      for (int i = 0; i < int(keys.size()); ++i) {
    20612048        Value val = Map::operator[](keys[i]);
    2062         typename Container::iterator it;
    2063         for (it = _inv_map.equal_range(val).first;
    2064              it != _inv_map.equal_range(val).second; ++it) {
    2065           if (it->second == keys[i]) {
    2066             _inv_map.erase(it);
    2067             break;
    2068           }
     2049        typename Container::iterator it = _inv_map.find(val);
     2050        if (it != _inv_map.end() && it->second == keys[i]) {
     2051          _inv_map.erase(it);
    20692052        }
    20702053      }
    … …  
    21022085      /// \brief Subscript operator.
    21032086      ///
    2104       /// Subscript operator. It gives back an item
    2105       /// that is assigned to the given value or \c INVALID
    2106       /// if no such item exists.
     2087      /// Subscript operator. It gives back the item
     2088      /// that was last assigned to the given value.
    21072089      Value operator[](const Key& key) const {
    21082090        return _inverted(key);
    … …  
    22732255
    22742256    /// \brief Gives back the item belonging to a \e RangeId
    2275     ///
     2257    /// 
    22762258    /// Gives back the item belonging to a \e RangeId.
    22772259    Item operator()(int id) const {
    … …  
    23302312  };
    23312313
    2332   /// \brief Dynamic iterable \c bool map.
    2333   ///
    2334   /// This class provides a special graph map type which can store a
    2335   /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
    2336   /// For both \c true and \c false values it is possible to iterate on
    2337   /// the keys.
    2338   ///
    2339   /// This type is a reference map, so it can be modified with the
    2340   /// subscript operator.
    2341   ///
    2342   /// \tparam GR The graph type.
    2343   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
    2344   /// \c GR::Edge).
    2345   ///
    2346   /// \see IterableIntMap, IterableValueMap
    2347   /// \see CrossRefMap
    2348   template <typename GR, typename K>
    2349   class IterableBoolMap
    2350     : protected ItemSetTraits<GR, K>::template Map<int>::Type {
    2351   private:
    2352     typedef GR Graph;
    2353 
    2354     typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
    2355     typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
    2356 
    2357     std::vector<K> _array;
    2358     int _sep;
    2359 
    2360   public:
    2361 
    2362     /// Indicates that the map is reference map.
    2363     typedef True ReferenceMapTag;
    2364 
    2365     /// The key type
    2366     typedef K Key;
    2367     /// The value type
    2368     typedef bool Value;
    2369     /// The const reference type.
    2370     typedef const Value& ConstReference;
    2371 
    2372   private:
    2373 
    2374     int position(const Key& key) const {
    2375       return Parent::operator[](key);
    2376     }
    2377 
    2378   public:
    2379 
    2380     /// \brief Reference to the value of the map.
    2381     ///
    2382     /// This class is similar to the \c bool type. It can be converted to
    2383     /// \c bool and it provides the same operators.
    2384     class Reference {
    2385       friend class IterableBoolMap;
    2386     private:
    2387       Reference(IterableBoolMap& map, const Key& key)
    2388         : _key(key), _map(map) {}
    2389     public:
    2390 
    2391       Reference& operator=(const Reference& value) {
    2392         _map.set(_key, static_cast<bool>(value));
    2393          return *this;
    2394       }
    2395 
    2396       operator bool() const {
    2397         return static_cast<const IterableBoolMap&>(_map)[_key];
    2398       }
    2399 
    2400       Reference& operator=(bool value) {
    2401         _map.set(_key, value);
    2402         return *this;
    2403       }
    2404       Reference& operator&=(bool value) {
    2405         _map.set(_key, _map[_key] & value);
    2406         return *this;
    2407       }
    2408       Reference& operator|=(bool value) {
    2409         _map.set(_key, _map[_key] | value);
    2410         return *this;
    2411       }
    2412       Reference& operator^=(bool value) {
    2413         _map.set(_key, _map[_key] ^ value);
    2414         return *this;
    2415       }
    2416     private:
    2417       Key _key;
    2418       IterableBoolMap& _map;
    2419     };
    2420 
    2421     /// \brief Constructor of the map with a default value.
    2422     ///
    2423     /// Constructor of the map with a default value.
    2424     explicit IterableBoolMap(const Graph& graph, bool def = false)
    2425       : Parent(graph) {
    2426       typename Parent::Notifier* nf = Parent::notifier();
    2427       Key it;
    2428       for (nf->first(it); it != INVALID; nf->next(it)) {
    2429         Parent::set(it, _array.size());
    2430         _array.push_back(it);
    2431       }
    2432       _sep = (def ? _array.size() : 0);
    2433     }
    2434 
    2435     /// \brief Const subscript operator of the map.
    2436     ///
    2437     /// Const subscript operator of the map.
    2438     bool operator[](const Key& key) const {
    2439       return position(key) < _sep;
    2440     }
    2441 
    2442     /// \brief Subscript operator of the map.
    2443     ///
    2444     /// Subscript operator of the map.
    2445     Reference operator[](const Key& key) {
    2446       return Reference(*this, key);
    2447     }
    2448 
    2449     /// \brief Set operation of the map.
    2450     ///
    2451     /// Set operation of the map.
    2452     void set(const Key& key, bool value) {
    2453       int pos = position(key);
    2454       if (value) {
    2455         if (pos < _sep) return;
    2456         Key tmp = _array[_sep];
    2457         _array[_sep] = key;
    2458         Parent::set(key, _sep);
    2459         _array[pos] = tmp;
    2460         Parent::set(tmp, pos);
    2461         ++_sep;
    2462       } else {
    2463         if (pos >= _sep) return;
    2464         --_sep;
    2465         Key tmp = _array[_sep];
    2466         _array[_sep] = key;
    2467         Parent::set(key, _sep);
    2468         _array[pos] = tmp;
    2469         Parent::set(tmp, pos);
    2470       }
    2471     }
    2472 
    2473     /// \brief Set all items.
    2474     ///
    2475     /// Set all items in the map.
    2476     /// \note Constant time operation.
    2477     void setAll(bool value) {
    2478       _sep = (value ? _array.size() : 0);
    2479     }
    2480 
    2481     /// \brief Returns the number of the keys mapped to \c true.
    2482     ///
    2483     /// Returns the number of the keys mapped to \c true.
    2484     int trueNum() const {
    2485       return _sep;
    2486     }
    2487 
    2488     /// \brief Returns the number of the keys mapped to \c false.
    2489     ///
    2490     /// Returns the number of the keys mapped to \c false.
    2491     int falseNum() const {
    2492       return _array.size() - _sep;
    2493     }
    2494 
    2495     /// \brief Iterator for the keys mapped to \c true.
    2496     ///
    2497     /// Iterator for the keys mapped to \c true. It works
    2498     /// like a graph item iterator, it can be converted to
    2499     /// the key type of the map, incremented with \c ++ operator, and
    2500     /// if the iterator leaves the last valid key, it will be equal to
    2501     /// \c INVALID.
    2502     class TrueIt : public Key {
    2503     public:
    2504       typedef Key Parent;
    2505 
    2506       /// \brief Creates an iterator.
    2507       ///
    2508       /// Creates an iterator. It iterates on the
    2509       /// keys mapped to \c true.
    2510       /// \param map The IterableBoolMap.
    2511       explicit TrueIt(const IterableBoolMap& map)
    2512         : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
    2513           _map(&map) {}
    2514 
    2515       /// \brief Invalid constructor \& conversion.
    2516       ///
    2517       /// This constructor initializes the iterator to be invalid.
    2518       /// \sa Invalid for more details.
    2519       TrueIt(Invalid) : Parent(INVALID), _map(0) {}
    2520 
    2521       /// \brief Increment operator.
    2522       ///
    2523       /// Increment operator.
    2524       TrueIt& operator++() {
    2525         int pos = _map->position(*this);
    2526         Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
    2527         return *this;
    2528       }
    2529 
    2530     private:
    2531       const IterableBoolMap* _map;
    2532     };
    2533 
    2534     /// \brief Iterator for the keys mapped to \c false.
    2535     ///
    2536     /// Iterator for the keys mapped to \c false. It works
    2537     /// like a graph item iterator, it can be converted to
    2538     /// the key type of the map, incremented with \c ++ operator, and
    2539     /// if the iterator leaves the last valid key, it will be equal to
    2540     /// \c INVALID.
    2541     class FalseIt : public Key {
    2542     public:
    2543       typedef Key Parent;
    2544 
    2545       /// \brief Creates an iterator.
    2546       ///
    2547       /// Creates an iterator. It iterates on the
    2548       /// keys mapped to \c false.
    2549       /// \param map The IterableBoolMap.
    2550       explicit FalseIt(const IterableBoolMap& map)
    2551         : Parent(map._sep < int(map._array.size()) ?
    2552                  map._array.back() : INVALID), _map(&map) {}
    2553 
    2554       /// \brief Invalid constructor \& conversion.
    2555       ///
    2556       /// This constructor initializes the iterator to be invalid.
    2557       /// \sa Invalid for more details.
    2558       FalseIt(Invalid) : Parent(INVALID), _map(0) {}
    2559 
    2560       /// \brief Increment operator.
    2561       ///
    2562       /// Increment operator.
    2563       FalseIt& operator++() {
    2564         int pos = _map->position(*this);
    2565         Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
    2566         return *this;
    2567       }
    2568 
    2569     private:
    2570       const IterableBoolMap* _map;
    2571     };
    2572 
    2573     /// \brief Iterator for the keys mapped to a given value.
    2574     ///
    2575     /// Iterator for the keys mapped to a given value. It works
    2576     /// like a graph item iterator, it can be converted to
    2577     /// the key type of the map, incremented with \c ++ operator, and
    2578     /// if the iterator leaves the last valid key, it will be equal to
    2579     /// \c INVALID.
    2580     class ItemIt : public Key {
    2581     public:
    2582       typedef Key Parent;
    2583 
    2584       /// \brief Creates an iterator with a value.
    2585       ///
    2586       /// Creates an iterator with a value. It iterates on the
    2587       /// keys mapped to the given value.
    2588       /// \param map The IterableBoolMap.
    2589       /// \param value The value.
    2590       ItemIt(const IterableBoolMap& map, bool value)
    2591         : Parent(value ?
    2592                  (map._sep > 0 ?
    2593                   map._array[map._sep - 1] : INVALID) :
    2594                  (map._sep < int(map._array.size()) ?
    2595                   map._array.back() : INVALID)), _map(&map) {}
    2596 
    2597       /// \brief Invalid constructor \& conversion.
    2598       ///
    2599       /// This constructor initializes the iterator to be invalid.
    2600       /// \sa Invalid for more details.
    2601       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
    2602 
    2603       /// \brief Increment operator.
    2604       ///
    2605       /// Increment operator.
    2606       ItemIt& operator++() {
    2607         int pos = _map->position(*this);
    2608         int _sep = pos >= _map->_sep ? _map->_sep : 0;
    2609         Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
    2610         return *this;
    2611       }
    2612 
    2613     private:
    2614       const IterableBoolMap* _map;
    2615     };
    2616 
    2617   protected:
    2618 
    2619     virtual void add(const Key& key) {
    2620       Parent::add(key);
    2621       Parent::set(key, _array.size());
    2622       _array.push_back(key);
    2623     }
    2624 
    2625     virtual void add(const std::vector<Key>& keys) {
    2626       Parent::add(keys);
    2627       for (int i = 0; i < int(keys.size()); ++i) {
    2628         Parent::set(keys[i], _array.size());
    2629         _array.push_back(keys[i]);
    2630       }
    2631     }
    2632 
    2633     virtual void erase(const Key& key) {
    2634       int pos = position(key);
    2635       if (pos < _sep) {
    2636         --_sep;
    2637         Parent::set(_array[_sep], pos);
    2638         _array[pos] = _array[_sep];
    2639         Parent::set(_array.back(), _sep);
    2640         _array[_sep] = _array.back();
    2641         _array.pop_back();
    2642       } else {
    2643         Parent::set(_array.back(), pos);
    2644         _array[pos] = _array.back();
    2645         _array.pop_back();
    2646       }
    2647       Parent::erase(key);
    2648     }
    2649 
    2650     virtual void erase(const std::vector<Key>& keys) {
    2651       for (int i = 0; i < int(keys.size()); ++i) {
    2652         int pos = position(keys[i]);
    2653         if (pos < _sep) {
    2654           --_sep;
    2655           Parent::set(_array[_sep], pos);
    2656           _array[pos] = _array[_sep];
    2657           Parent::set(_array.back(), _sep);
    2658           _array[_sep] = _array.back();
    2659           _array.pop_back();
    2660         } else {
    2661           Parent::set(_array.back(), pos);
    2662           _array[pos] = _array.back();
    2663           _array.pop_back();
    2664         }
    2665       }
    2666       Parent::erase(keys);
    2667     }
    2668 
    2669     virtual void build() {
    2670       Parent::build();
    2671       typename Parent::Notifier* nf = Parent::notifier();
    2672       Key it;
    2673       for (nf->first(it); it != INVALID; nf->next(it)) {
    2674         Parent::set(it, _array.size());
    2675         _array.push_back(it);
    2676       }
    2677       _sep = 0;
    2678     }
    2679 
    2680     virtual void clear() {
    2681       _array.clear();
    2682       _sep = 0;
    2683       Parent::clear();
    2684     }
    2685 
    2686   };
    2687 
    2688 
    2689   namespace _maps_bits {
    2690     template <typename Item>
    2691     struct IterableIntMapNode {
    2692       IterableIntMapNode() : value(-1) {}
    2693       IterableIntMapNode(int _value) : value(_value) {}
    2694       Item prev, next;
    2695       int value;
    2696     };
    2697   }
    2698 
    2699   /// \brief Dynamic iterable integer map.
    2700   ///
    2701   /// This class provides a special graph map type which can store an
    2702   /// integer value for graph items (\c Node, \c Arc or \c Edge).
    2703   /// For each non-negative value it is possible to iterate on the keys
    2704   /// mapped to the value.
    2705   ///
    2706   /// This type is a reference map, so it can be modified with the
    2707   /// subscript operator.
    2708   ///
    2709   /// \note The size of the data structure depends on the largest
    2710   /// value in the map.
    2711   ///
    2712   /// \tparam GR The graph type.
    2713   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
    2714   /// \c GR::Edge).
    2715   ///
    2716   /// \see IterableBoolMap, IterableValueMap
    2717   /// \see CrossRefMap
    2718   template <typename GR, typename K>
    2719   class IterableIntMap
    2720     : protected ItemSetTraits<GR, K>::
    2721         template Map<_maps_bits::IterableIntMapNode<K> >::Type {
    2722   public:
    2723     typedef typename ItemSetTraits<GR, K>::
    2724       template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
    2725 
    2726     /// The key type
    2727     typedef K Key;
    2728     /// The value type
    2729     typedef int Value;
    2730     /// The graph type
    2731     typedef GR Graph;
    2732 
    2733     /// \brief Constructor of the map.
    2734     ///
    2735     /// Constructor of the map. It sets all values to -1.
    2736     explicit IterableIntMap(const Graph& graph)
    2737       : Parent(graph) {}
    2738 
    2739     /// \brief Constructor of the map with a given value.
    2740     ///
    2741     /// Constructor of the map with a given value.
    2742     explicit IterableIntMap(const Graph& graph, int value)
    2743       : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
    2744       if (value >= 0) {
    2745         for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
    2746           lace(it);
    2747         }
    2748       }
    2749     }
    2750 
    2751   private:
    2752 
    2753     void unlace(const Key& key) {
    2754       typename Parent::Value& node = Parent::operator[](key);
    2755       if (node.value < 0) return;
    2756       if (node.prev != INVALID) {
    2757         Parent::operator[](node.prev).next = node.next;
    2758       } else {
    2759         _first[node.value] = node.next;
    2760       }
    2761       if (node.next != INVALID) {
    2762         Parent::operator[](node.next).prev = node.prev;
    2763       }
    2764       while (!_first.empty() && _first.back() == INVALID) {
    2765         _first.pop_back();
    2766       }
    2767     }
    2768 
    2769     void lace(const Key& key) {
    2770       typename Parent::Value& node = Parent::operator[](key);
    2771       if (node.value < 0) return;
    2772       if (node.value >= int(_first.size())) {
    2773         _first.resize(node.value + 1, INVALID);
    2774       }
    2775       node.prev = INVALID;
    2776       node.next = _first[node.value];
    2777       if (node.next != INVALID) {
    2778         Parent::operator[](node.next).prev = key;
    2779       }
    2780       _first[node.value] = key;
    2781     }
    2782 
    2783   public:
    2784 
    2785     /// Indicates that the map is reference map.
    2786     typedef True ReferenceMapTag;
    2787 
    2788     /// \brief Reference to the value of the map.
    2789     ///
    2790     /// This class is similar to the \c int type. It can
    2791     /// be converted to \c int and it has the same operators.
    2792     class Reference {
    2793       friend class IterableIntMap;
    2794     private:
    2795       Reference(IterableIntMap& map, const Key& key)
    2796         : _key(key), _map(map) {}
    2797     public:
    2798 
    2799       Reference& operator=(const Reference& value) {
    2800         _map.set(_key, static_cast<const int&>(value));
    2801          return *this;
    2802       }
    2803 
    2804       operator const int&() const {
    2805         return static_cast<const IterableIntMap&>(_map)[_key];
    2806       }
    2807 
    2808       Reference& operator=(int value) {
    2809         _map.set(_key, value);
    2810         return *this;
    2811       }
    2812       Reference& operator++() {
    2813         _map.set(_key, _map[_key] + 1);
    2814         return *this;
    2815       }
    2816       int operator++(int) {
    2817         int value = _map[_key];
    2818         _map.set(_key, value + 1);
    2819         return value;
    2820       }
    2821       Reference& operator--() {
    2822         _map.set(_key, _map[_key] - 1);
    2823         return *this;
    2824       }
    2825       int operator--(int) {
    2826         int value = _map[_key];
    2827         _map.set(_key, value - 1);
    2828         return value;
    2829       }
    2830       Reference& operator+=(int value) {
    2831         _map.set(_key, _map[_key] + value);
    2832         return *this;
    2833       }
    2834       Reference& operator-=(int value) {
    2835         _map.set(_key, _map[_key] - value);
    2836         return *this;
    2837       }
    2838       Reference& operator*=(int value) {
    2839         _map.set(_key, _map[_key] * value);
    2840         return *this;
    2841       }
    2842       Reference& operator/=(int value) {
    2843         _map.set(_key, _map[_key] / value);
    2844         return *this;
    2845       }
    2846       Reference& operator%=(int value) {
    2847         _map.set(_key, _map[_key] % value);
    2848         return *this;
    2849       }
    2850       Reference& operator&=(int value) {
    2851         _map.set(_key, _map[_key] & value);
    2852         return *this;
    2853       }
    2854       Reference& operator|=(int value) {
    2855         _map.set(_key, _map[_key] | value);
    2856         return *this;
    2857       }
    2858       Reference& operator^=(int value) {
    2859         _map.set(_key, _map[_key] ^ value);
    2860         return *this;
    2861       }
    2862       Reference& operator<<=(int value) {
    2863         _map.set(_key, _map[_key] << value);
    2864         return *this;
    2865       }
    2866       Reference& operator>>=(int value) {
    2867         _map.set(_key, _map[_key] >> value);
    2868         return *this;
    2869       }
    2870 
    2871     private:
    2872       Key _key;
    2873       IterableIntMap& _map;
    2874     };
    2875 
    2876     /// The const reference type.
    2877     typedef const Value& ConstReference;
    2878 
    2879     /// \brief Gives back the maximal value plus one.
    2880     ///
    2881     /// Gives back the maximal value plus one.
    2882     int size() const {
    2883       return _first.size();
    2884     }
    2885 
    2886     /// \brief Set operation of the map.
    2887     ///
    2888     /// Set operation of the map.
    2889     void set(const Key& key, const Value& value) {
    2890       unlace(key);
    2891       Parent::operator[](key).value = value;
    2892       lace(key);
    2893     }
    2894 
    2895     /// \brief Const subscript operator of the map.
    2896     ///
    2897     /// Const subscript operator of the map.
    2898     const Value& operator[](const Key& key) const {
    2899       return Parent::operator[](key).value;
    2900     }
    2901 
    2902     /// \brief Subscript operator of the map.
    2903     ///
    2904     /// Subscript operator of the map.
    2905     Reference operator[](const Key& key) {
    2906       return Reference(*this, key);
    2907     }
    2908 
    2909     /// \brief Iterator for the keys with the same value.
    2910     ///
    2911     /// Iterator for the keys with the same value. It works
    2912     /// like a graph item iterator, it can be converted to
    2913     /// the item type of the map, incremented with \c ++ operator, and
    2914     /// if the iterator leaves the last valid item, it will be equal to
    2915     /// \c INVALID.
    2916     class ItemIt : public Key {
    2917     public:
    2918       typedef Key Parent;
    2919 
    2920       /// \brief Invalid constructor \& conversion.
    2921       ///
    2922       /// This constructor initializes the iterator to be invalid.
    2923       /// \sa Invalid for more details.
    2924       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
    2925 
    2926       /// \brief Creates an iterator with a value.
    2927       ///
    2928       /// Creates an iterator with a value. It iterates on the
    2929       /// keys mapped to the given value.
    2930       /// \param map The IterableIntMap.
    2931       /// \param value The value.
    2932       ItemIt(const IterableIntMap& map, int value) : _map(&map) {
    2933         if (value < 0 || value >= int(_map->_first.size())) {
    2934           Parent::operator=(INVALID);
    2935         } else {
    2936           Parent::operator=(_map->_first[value]);
    2937         }
    2938       }
    2939 
    2940       /// \brief Increment operator.
    2941       ///
    2942       /// Increment operator.
    2943       ItemIt& operator++() {
    2944         Parent::operator=(_map->IterableIntMap::Parent::
    2945                           operator[](static_cast<Parent&>(*this)).next);
    2946         return *this;
    2947       }
    2948 
    2949     private:
    2950       const IterableIntMap* _map;
    2951     };
    2952 
    2953   protected:
    2954 
    2955     virtual void erase(const Key& key) {
    2956       unlace(key);
    2957       Parent::erase(key);
    2958     }
    2959 
    2960     virtual void erase(const std::vector<Key>& keys) {
    2961       for (int i = 0; i < int(keys.size()); ++i) {
    2962         unlace(keys[i]);
    2963       }
    2964       Parent::erase(keys);
    2965     }
    2966 
    2967     virtual void clear() {
    2968       _first.clear();
    2969       Parent::clear();
    2970     }
    2971 
    2972   private:
    2973     std::vector<Key> _first;
    2974   };
    2975 
    2976   namespace _maps_bits {
    2977     template <typename Item, typename Value>
    2978     struct IterableValueMapNode {
    2979       IterableValueMapNode(Value _value = Value()) : value(_value) {}
    2980       Item prev, next;
    2981       Value value;
    2982     };
    2983   }
    2984 
    2985   /// \brief Dynamic iterable map for comparable values.
    2986   ///
    2987   /// This class provides a special graph map type which can store an
    2988   /// comparable value for graph items (\c Node, \c Arc or \c Edge).
    2989   /// For each value it is possible to iterate on the keys mapped to
    2990   /// the value.
    2991   ///
    2992   /// The map stores for each value a linked list with
    2993   /// the items which mapped to the value, and the values are stored
    2994   /// in balanced binary tree. The values of the map can be accessed
    2995   /// with stl compatible forward iterator.
    2996   ///
    2997   /// This type is not reference map, so it cannot be modified with
    2998   /// the subscript operator.
    2999   ///
    3000   /// \tparam GR The graph type.
    3001   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
    3002   /// \c GR::Edge).
    3003   /// \tparam V The value type of the map. It can be any comparable
    3004   /// value type.
    3005   ///
    3006   /// \see IterableBoolMap, IterableIntMap
    3007   /// \see CrossRefMap
    3008   template <typename GR, typename K, typename V>
    3009   class IterableValueMap
    3010     : protected ItemSetTraits<GR, K>::
    3011         template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
    3012   public:
    3013     typedef typename ItemSetTraits<GR, K>::
    3014       template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
    3015 
    3016     /// The key type
    3017     typedef K Key;
    3018     /// The value type
    3019     typedef V Value;
    3020     /// The graph type
    3021     typedef GR Graph;
    3022 
    3023   public:
    3024 
    3025     /// \brief Constructor of the map with a given value.
    3026     ///
    3027     /// Constructor of the map with a given value.
    3028     explicit IterableValueMap(const Graph& graph,
    3029                               const Value& value = Value())
    3030       : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
    3031       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
    3032         lace(it);
    3033       }
    3034     }
    3035 
    3036   protected:
    3037 
    3038     void unlace(const Key& key) {
    3039       typename Parent::Value& node = Parent::operator[](key);
    3040       if (node.prev != INVALID) {
    3041         Parent::operator[](node.prev).next = node.next;
    3042       } else {
    3043         if (node.next != INVALID) {
    3044           _first[node.value] = node.next;
    3045         } else {
    3046           _first.erase(node.value);
    3047         }
    3048       }
    3049       if (node.next != INVALID) {
    3050         Parent::operator[](node.next).prev = node.prev;
    3051       }
    3052     }
    3053 
    3054     void lace(const Key& key) {
    3055       typename Parent::Value& node = Parent::operator[](key);
    3056       typename std::map<Value, Key>::iterator it = _first.find(node.value);
    3057       if (it == _first.end()) {
    3058         node.prev = node.next = INVALID;
    3059         _first.insert(std::make_pair(node.value, key));
    3060       } else {
    3061         node.prev = INVALID;
    3062         node.next = it->second;
    3063         if (node.next != INVALID) {
    3064           Parent::operator[](node.next).prev = key;
    3065         }
    3066         it->second = key;
    3067       }
    3068     }
    3069 
    3070   public:
    3071 
    3072     /// \brief Forward iterator for values.
    3073     ///
    3074     /// This iterator is an stl compatible forward
    3075     /// iterator on the values of the map. The values can
    3076     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    3077     class ValueIterator
    3078       : public std::iterator<std::forward_iterator_tag, Value> {
    3079       friend class IterableValueMap;
    3080     private:
    3081       ValueIterator(typename std::map<Value, Key>::const_iterator _it)
    3082         : it(_it) {}
    3083     public:
    3084 
    3085       ValueIterator() {}
    3086 
    3087       ValueIterator& operator++() { ++it; return *this; }
    3088       ValueIterator operator++(int) {
    3089         ValueIterator tmp(*this);
    3090         operator++();
    3091         return tmp;
    3092       }
    3093 
    3094       const Value& operator*() const { return it->first; }
    3095       const Value* operator->() const { return &(it->first); }
    3096 
    3097       bool operator==(ValueIterator jt) const { return it == jt.it; }
    3098       bool operator!=(ValueIterator jt) const { return it != jt.it; }
    3099 
    3100     private:
    3101       typename std::map<Value, Key>::const_iterator it;
    3102     };
    3103 
    3104     /// \brief Returns an iterator to the first value.
    3105     ///
    3106     /// Returns an stl compatible iterator to the
    3107     /// first value of the map. The values of the
    3108     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    3109     /// range.
    3110     ValueIterator beginValue() const {
    3111       return ValueIterator(_first.begin());
    3112     }
    3113 
    3114     /// \brief Returns an iterator after the last value.
    3115     ///
    3116     /// Returns an stl compatible iterator after the
    3117     /// last value of the map. The values of the
    3118     /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    3119     /// range.
    3120     ValueIterator endValue() const {
    3121       return ValueIterator(_first.end());
    3122     }
    3123 
    3124     /// \brief Set operation of the map.
    3125     ///
    3126     /// Set operation of the map.
    3127     void set(const Key& key, const Value& value) {
    3128       unlace(key);
    3129       Parent::operator[](key).value = value;
    3130       lace(key);
    3131     }
    3132 
    3133     /// \brief Const subscript operator of the map.
    3134     ///
    3135     /// Const subscript operator of the map.
    3136     const Value& operator[](const Key& key) const {
    3137       return Parent::operator[](key).value;
    3138     }
    3139 
    3140     /// \brief Iterator for the keys with the same value.
    3141     ///
    3142     /// Iterator for the keys with the same value. It works
    3143     /// like a graph item iterator, it can be converted to
    3144     /// the item type of the map, incremented with \c ++ operator, and
    3145     /// if the iterator leaves the last valid item, it will be equal to
    3146     /// \c INVALID.
    3147     class ItemIt : public Key {
    3148     public:
    3149       typedef Key Parent;
    3150 
    3151       /// \brief Invalid constructor \& conversion.
    3152       ///
    3153       /// This constructor initializes the iterator to be invalid.
    3154       /// \sa Invalid for more details.
    3155       ItemIt(Invalid) : Parent(INVALID), _map(0) {}
    3156 
    3157       /// \brief Creates an iterator with a value.
    3158       ///
    3159       /// Creates an iterator with a value. It iterates on the
    3160       /// keys which have the given value.
    3161       /// \param map The IterableValueMap
    3162       /// \param value The value
    3163       ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
    3164         typename std::map<Value, Key>::const_iterator it =
    3165           map._first.find(value);
    3166         if (it == map._first.end()) {
    3167           Parent::operator=(INVALID);
    3168         } else {
    3169           Parent::operator=(it->second);
    3170         }
    3171       }
    3172 
    3173       /// \brief Increment operator.
    3174       ///
    3175       /// Increment Operator.
    3176       ItemIt& operator++() {
    3177         Parent::operator=(_map->IterableValueMap::Parent::
    3178                           operator[](static_cast<Parent&>(*this)).next);
    3179         return *this;
    3180       }
    3181 
    3182 
    3183     private:
    3184       const IterableValueMap* _map;
    3185     };
    3186 
    3187   protected:
    3188 
    3189     virtual void add(const Key& key) {
    3190       Parent::add(key);
    3191       unlace(key);
    3192     }
    3193 
    3194     virtual void add(const std::vector<Key>& keys) {
    3195       Parent::add(keys);
    3196       for (int i = 0; i < int(keys.size()); ++i) {
    3197         lace(keys[i]);
    3198       }
    3199     }
    3200 
    3201     virtual void erase(const Key& key) {
    3202       unlace(key);
    3203       Parent::erase(key);
    3204     }
    3205 
    3206     virtual void erase(const std::vector<Key>& keys) {
    3207       for (int i = 0; i < int(keys.size()); ++i) {
    3208         unlace(keys[i]);
    3209       }
    3210       Parent::erase(keys);
    3211     }
    3212 
    3213     virtual void build() {
    3214       Parent::build();
    3215       for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
    3216         lace(it);
    3217       }
    3218     }
    3219 
    3220     virtual void clear() {
    3221       _first.clear();
    3222       Parent::clear();
    3223     }
    3224 
    3225   private:
    3226     std::map<Value, Key> _first;
    3227   };
    3228 
    32292314  /// \brief Map of the source nodes of arcs in a digraph.
    32302315  ///
    … …  
    33962481  /// whenever the digraph changes.
    33972482  ///
    3398   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2483  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    33992484  /// may provide alternative ways to modify the digraph.
    34002485  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    34122497
    34132498  public:
    3414 
     2499   
    34152500    /// The graph type of InDegMap
    34162501    typedef GR Graph;
    … …  
    35262611  /// whenever the digraph changes.
    35272612  ///
    3528   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2613  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    35292614  /// may provide alternative ways to modify the digraph.
    35302615  /// The correct behavior of OutDegMap is not guarantied if these additional

  • lemon/min_cost_arborescence.h

    r760 r672  
    489489    /// The simplest way to execute the algorithm is to use
    490490    /// one of the member functions called \c run(...). \n
    491     /// If you need better control on the execution,
    492     /// you have to call \ref init() first, then you can add several
     491    /// If you need more control on the execution,
     492    /// first you must call \ref init(), then you can add several
    493493    /// source nodes with \ref addSource().
    494494    /// Finally \ref start() will perform the arborescence

  • lemon/preflow.h

    r762 r688  
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55 #ifdef DOXYGEN
    56     typedef GR::ArcMap<Value> FlowMap;
    57 #else
    5855    typedef typename Digraph::template ArcMap<Value> FlowMap;
    59 #endif
    6056
    6157    /// \brief Instantiates a FlowMap.
    … …  
    7268    /// The elevator type used by Preflow algorithm.
    7369    ///
    74     /// \sa Elevator, LinkedElevator
    75 #ifdef DOXYGEN
    76     typedef lemon::Elevator<GR, GR::Node> Elevator;
    77 #else
    78     typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    79 #endif
     70    /// \sa Elevator
     71    /// \sa LinkedElevator
     72    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    8073
    8174    /// \brief Instantiates an Elevator.
    … …  
    10598  /// "flow of maximum value" in a digraph.
    10699  /// The preflow algorithms are the fastest known maximum
    107   /// flow algorithms. The current implementation uses a mixture of the
     100  /// flow algorithms. The current implementation use a mixture of the
    108101  /// \e "highest label" and the \e "bound decrease" heuristics.
    109102  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    … …  
    379372    }
    380373
    381     /// \brief Sets the tolerance used by the algorithm.
    382     ///
    383     /// Sets the tolerance object used by the algorithm.
    384     /// \return <tt>(*this)</tt>
    385     Preflow& tolerance(const Tolerance& tolerance) {
     374    /// \brief Sets the tolerance used by algorithm.
     375    ///
     376    /// Sets the tolerance used by algorithm.
     377    Preflow& tolerance(const Tolerance& tolerance) const {
    386378      _tolerance = tolerance;
    387379      return *this;
    … …  
    390382    /// \brief Returns a const reference to the tolerance.
    391383    ///
    392     /// Returns a const reference to the tolerance object used by
    393     /// the algorithm.
     384    /// Returns a const reference to the tolerance.
    394385    const Tolerance& tolerance() const {
    395       return _tolerance;
     386      return tolerance;
    396387    }
    397388
    … …  
    399390    /// The simplest way to execute the preflow algorithm is to use
    400391    /// \ref run() or \ref runMinCut().\n
    401     /// If you need better control on the initial solution or the execution,
    402     /// you have to call one of the \ref init() functions first, then
     392    /// If you need more control on the initial solution or the execution,
     393    /// first you have to call one of the \ref init() functions, then
    403394    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
    404395

  • test/CMakeLists.txt

    r745 r726  
    1010SET(TESTS
    1111  adaptors_test
    12   bellman_ford_test
    1312  bfs_test
    1413  circulation_test

  • test/Makefile.am

    r745 r696  
    88check_PROGRAMS += \
    99        test/adaptors_test \
    10         test/bellman_ford_test \
    1110        test/bfs_test \
    1211        test/circulation_test \
    … …  
    5453
    5554test_adaptors_test_SOURCES = test/adaptors_test.cc
    56 test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5755test_bfs_test_SOURCES = test/bfs_test.cc
    5856test_circulation_test_SOURCES = test/circulation_test.cc

  • test/circulation_test.cc

    r736 r658  
    8888    .supplyMap(supply)
    8989    .flowMap(flow);
    90  
    91   const CirculationType::Elevator& elev = const_circ_test.elevator();
    92   circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
    93   CirculationType::Tolerance tol = const_circ_test.tolerance();
    94   circ_test.tolerance(tol);
    9590
    9691  circ_test.init();

  • test/heap_test.cc

    r749 r463  
    2626
    2727#include <lemon/smart_graph.h>
     28
    2829#include <lemon/lgf_reader.h>
    2930#include <lemon/dijkstra.h>
    … …  
    3132
    3233#include <lemon/bin_heap.h>
    33 #include <lemon/fourary_heap.h>
    34 #include <lemon/kary_heap.h>
    35 #include <lemon/fib_heap.h>
    36 #include <lemon/pairing_heap.h>
    37 #include <lemon/radix_heap.h>
    38 #include <lemon/binom_heap.h>
    39 #include <lemon/bucket_heap.h>
    4034
    4135#include "test_tools.h"
    … …  
    9387void heapSortTest() {
    9488  RangeMap<int> map(test_len, -1);
     89
    9590  Heap heap(map);
    9691
    9792  std::vector<int> v(test_len);
     93
    9894  for (int i = 0; i < test_len; ++i) {
    9995    v[i] = test_seq[i];
    … …  
    10298  std::sort(v.begin(), v.end());
    10399  for (int i = 0; i < test_len; ++i) {
    104     check(v[i] == heap.prio(), "Wrong order in heap sort.");
     100    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
    105101    heap.pop();
    106102  }
    … …  
    114110
    115111  std::vector<int> v(test_len);
     112
    116113  for (int i = 0; i < test_len; ++i) {
    117114    v[i] = test_seq[i];
    … …  
    124121  std::sort(v.begin(), v.end());
    125122  for (int i = 0; i < test_len; ++i) {
    126     check(v[i] == heap.prio(), "Wrong order in heap increase test.");
     123    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
    127124    heap.pop();
    128125  }
    129126}
     127
     128
    130129
    131130template <typename Heap>
    … …  
    143142    if (dijkstra.reached(s)) {
    144143      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
    145              "Error in shortest path tree.");
     144             "Error in a shortest path tree!");
    146145    }
    147146  }
    … …  
    152151      Node s = digraph.source(a);
    153152      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
    154              "Error in shortest path tree.");
     153             "Error in a shortest path tree!");
    155154    }
    156155  }
    … …  
    174173    run();
    175174
    176   // BinHeap
    177175  {
    178176    typedef BinHeap<Prio, ItemIntMap> IntHeap;
    … …  
    186184  }
    187185
    188   // FouraryHeap
    189   {
    190     typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
    191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    192     heapSortTest<IntHeap>();
    193     heapIncreaseTest<IntHeap>();
    194 
    195     typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
    196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    198   }
    199 
    200   // KaryHeap
    201   {
    202     typedef KaryHeap<Prio, ItemIntMap> IntHeap;
    203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    204     heapSortTest<IntHeap>();
    205     heapIncreaseTest<IntHeap>();
    206 
    207     typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
    208     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    209     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    210   }
    211 
    212   // FibHeap
    213   {
    214     typedef FibHeap<Prio, ItemIntMap> IntHeap;
    215     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    216     heapSortTest<IntHeap>();
    217     heapIncreaseTest<IntHeap>();
    218 
    219     typedef FibHeap<Prio, IntNodeMap > NodeHeap;
    220     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    221     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    222   }
    223 
    224   // PairingHeap
    225   {
    226     typedef PairingHeap<Prio, ItemIntMap> IntHeap;
    227     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    228     heapSortTest<IntHeap>();
    229     heapIncreaseTest<IntHeap>();
    230 
    231     typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
    232     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    233     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    234   }
    235 
    236   // RadixHeap
    237   {
    238     typedef RadixHeap<ItemIntMap> IntHeap;
    239     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    240     heapSortTest<IntHeap>();
    241     heapIncreaseTest<IntHeap>();
    242 
    243     typedef RadixHeap<IntNodeMap > NodeHeap;
    244     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    245     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    246   }
    247 
    248   // BinomHeap
    249   {
    250     typedef BinomHeap<Prio, ItemIntMap> IntHeap;
    251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    252     heapSortTest<IntHeap>();
    253     heapIncreaseTest<IntHeap>();
    254 
    255     typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
    256     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    257     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    258   }
    259 
    260   // BucketHeap, SimpleBucketHeap
    261   {
    262     typedef BucketHeap<ItemIntMap> IntHeap;
    263     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    264     heapSortTest<IntHeap>();
    265     heapIncreaseTest<IntHeap>();
    266 
    267     typedef BucketHeap<IntNodeMap > NodeHeap;
    268     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    269     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    270 
    271     typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
    272     heapSortTest<SimpleIntHeap>();
    273   }
    274 
    275186  return 0;
    276187}

  • test/maps_test.cc

    r742 r554  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
    25 #include <lemon/smart_graph.h>
    2625
    2726#include "test_tools.h"
    … …  
    351350  }
    352351
    353   // CrossRefMap
    354   {
    355     typedef SmartDigraph 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  
    387   // Iterable bool map
    388   {
    389     typedef SmartGraph Graph;
    390     typedef SmartGraph::Node Item;
    391 
    392     typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
    393     checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
    394 
    395     const int num = 10;
    396     Graph g;
    397     std::vector<Item> items;
    398     for (int i = 0; i < num; ++i) {
    399       items.push_back(g.addNode());
    400     }
    401 
    402     Ibm map1(g, true);
    403     int n = 0;
    404     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    405       check(map1[static_cast<Item>(it)], "Wrong TrueIt");
    406       ++n;
    407     }
    408     check(n == num, "Wrong number");
    409 
    410     n = 0;
    411     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    412         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    413         ++n;
    414     }
    415     check(n == num, "Wrong number");
    416     check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
    417     check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
    418 
    419     map1[items[5]] = true;
    420 
    421     n = 0;
    422     for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
    423         check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
    424         ++n;
    425     }
    426     check(n == num, "Wrong number");
    427 
    428     map1[items[num / 2]] = false;
    429     check(map1[items[num / 2]] == false, "Wrong map value");
    430 
    431     n = 0;
    432     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    433         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    434         ++n;
    435     }
    436     check(n == num - 1, "Wrong number");
    437 
    438     n = 0;
    439     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    440         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    441         ++n;
    442     }
    443     check(n == 1, "Wrong number");
    444 
    445     map1[items[0]] = false;
    446     check(map1[items[0]] == false, "Wrong map value");
    447 
    448     map1[items[num - 1]] = false;
    449     check(map1[items[num - 1]] == false, "Wrong map value");
    450 
    451     n = 0;
    452     for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
    453         check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
    454         ++n;
    455     }
    456     check(n == num - 3, "Wrong number");
    457     check(map1.trueNum() == num - 3, "Wrong number");
    458 
    459     n = 0;
    460     for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
    461         check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
    462         ++n;
    463     }
    464     check(n == 3, "Wrong number");
    465     check(map1.falseNum() == 3, "Wrong number");
    466   }
    467 
    468   // Iterable int map
    469   {
    470     typedef SmartGraph Graph;
    471     typedef SmartGraph::Node Item;
    472     typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
    473 
    474     checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
    475 
    476     const int num = 10;
    477     Graph g;
    478     std::vector<Item> items;
    479     for (int i = 0; i < num; ++i) {
    480       items.push_back(g.addNode());
    481     }
    482 
    483     Iim map1(g);
    484     check(map1.size() == 0, "Wrong size");
    485 
    486     for (int i = 0; i < num; ++i) {
    487       map1[items[i]] = i;
    488     }
    489     check(map1.size() == num, "Wrong size");
    490 
    491     for (int i = 0; i < num; ++i) {
    492       Iim::ItemIt it(map1, i);
    493       check(static_cast<Item>(it) == items[i], "Wrong value");
    494       ++it;
    495       check(static_cast<Item>(it) == INVALID, "Wrong value");
    496     }
    497 
    498     for (int i = 0; i < num; ++i) {
    499       map1[items[i]] = i % 2;
    500     }
    501     check(map1.size() == 2, "Wrong size");
    502 
    503     int n = 0;
    504     for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
    505       check(map1[static_cast<Item>(it)] == 0, "Wrong value");
    506       ++n;
    507     }
    508     check(n == (num + 1) / 2, "Wrong number");
    509 
    510     for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
    511       check(map1[static_cast<Item>(it)] == 1, "Wrong value");
    512       ++n;
    513     }
    514     check(n == num, "Wrong number");
    515 
    516   }
    517 
    518   // Iterable value map
    519   {
    520     typedef SmartGraph Graph;
    521     typedef SmartGraph::Node Item;
    522     typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
    523 
    524     checkConcept<ReadWriteMap<Item, double>, Ivm>();
    525 
    526     const int num = 10;
    527     Graph g;
    528     std::vector<Item> items;
    529     for (int i = 0; i < num; ++i) {
    530       items.push_back(g.addNode());
    531     }
    532 
    533     Ivm map1(g, 0.0);
    534     check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
    535     check(*map1.beginValue() == 0.0, "Wrong value");
    536 
    537     for (int i = 0; i < num; ++i) {
    538       map1.set(items[i], static_cast<double>(i));
    539     }
    540     check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
    541 
    542     for (int i = 0; i < num; ++i) {
    543       Ivm::ItemIt it(map1, static_cast<double>(i));
    544       check(static_cast<Item>(it) == items[i], "Wrong value");
    545       ++it;
    546       check(static_cast<Item>(it) == INVALID, "Wrong value");
    547     }
    548 
    549     for (Ivm::ValueIterator vit = map1.beginValue();
    550          vit != map1.endValue(); ++vit) {
    551       check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
    552             "Wrong ValueIterator");
    553     }
    554 
    555     for (int i = 0; i < num; ++i) {
    556       map1.set(items[i], static_cast<double>(i % 2));
    557     }
    558     check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
    559 
    560     int n = 0;
    561     for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
    562       check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
    563       ++n;
    564     }
    565     check(n == (num + 1) / 2, "Wrong number");
    566 
    567     for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
    568       check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
    569       ++n;
    570     }
    571     check(n == num, "Wrong number");
    572 
    573   }
    574352  return 0;
    575353}

  • test/preflow_test.cc

    r736 r632  
    9595  PreflowType preflow_test(g, cap, n, n);
    9696  const PreflowType& const_preflow_test = preflow_test;
    97  
    98   const PreflowType::Elevator& elev = const_preflow_test.elevator();
    99   preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
    100   PreflowType::Tolerance tol = const_preflow_test.tolerance();
    101   preflow_test.tolerance(tol);
    10297
    10398  preflow_test

  • tools/lemon-0.x-to-1.x.sh

    r738 r621  
    3636        -e "s/Edge\>/_Ar_c_label_/g"\
    3737        -e "s/\<edge\>/_ar_c_label_/g"\
    38         -e "s/_edge\>/__ar_c_label_/g"\
     38        -e "s/_edge\>/_ar_c_label_/g"\
    3939        -e "s/Edges\>/_Ar_c_label_s/g"\
    4040        -e "s/\<edges\>/_ar_c_label_s/g"\
    41         -e "s/_edges\>/__ar_c_label_s/g"\
     41        -e "s/_edges\>/_ar_c_label_s/g"\
    4242        -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\
    4343        -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\
    … …  
    6969        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
    7070        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
    71         -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\
    72         -e "s/\<digraph_utils\.h\>/core.h/g"\
    73         -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\
    74         -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\
    75         -e "s/\<topology\.h\>/connectivity.h/g"\
    7671        -e "s/DigraphToEps/GraphToEps/g"\
    7772        -e "s/digraphToEps/graphToEps/g"\
Note: See TracChangeset for help on using the changeset viewer.