COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 320:12626fc94ccf in lemon-1.0


Ignore:
Timestamp:
10/09/08 15:37:44 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.0
Parents:
303:de38fca76780 (diff), 319:c175e387da19 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge from trunk

Files:
1 deleted
6 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r302 r320  
    4343You are free to use the graph structure that fit your requirements
    4444the best, most graph algorithms and auxiliary data structures can be used
    45 with any graph structures.
     45with any graph structure.
     46
     47<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    4648*/
    4749
    … …  
    5355This group describes the map structures implemented in LEMON.
    5456
    55 LEMON provides several special purpose maps that e.g. combine
     57LEMON provides several special purpose maps and map adaptors that e.g. combine
    5658new maps from existing ones.
     59
     60<b>See also:</b> \ref map_concepts "Map Concepts".
    5761*/
    5862
    … …  
    6569values to the nodes and arcs of graphs.
    6670*/
    67 
    6871
    6972/**
    … …  
    8386algorithms.  If a function type algorithm is called then the function
    8487type map adaptors can be used comfortable. For example let's see the
    85 usage of map adaptors with the \c digraphToEps() function.
     88usage of map adaptors with the \c graphToEps() function.
    8689\code
    8790  Color nodeColor(int deg) {
    … …  
    97100  Digraph::NodeMap<int> degree_map(graph);
    98101
    99   digraphToEps(graph, "graph.eps")
     102  graphToEps(graph, "graph.eps")
    100103    .coords(coords).scaleToA4().undirected()
    101104    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
    … …  
    103106\endcode
    104107The \c functorToMap() function makes an \c int to \c Color map from the
    105 \e nodeColor() function. The \c composeMap() compose the \e degree_map
     108\c nodeColor() function. The \c composeMap() compose the \c degree_map
    106109and the previously created map. The composed map is a proper function to
    107110get the color of each node.
    … …  
    144147
    145148\sa lemon::concepts::Path
    146 
    147149*/
    148150
    … …  
    156158*/
    157159
    158 
    159160/**
    160161@defgroup algs Algorithms
    … …  
    172173
    173174This group describes the common graph search algorithms like
    174 Breadth-first search (Bfs) and Depth-first search (Dfs).
    175 */
    176 
    177 /**
    178 @defgroup shortest_path Shortest Path algorithms
     175Breadth-First Search (BFS) and Depth-First Search (DFS).
     176*/
     177
     178/**
     179@defgroup shortest_path Shortest Path Algorithms
    179180@ingroup algs
    180181\brief Algorithms for finding shortest paths.
    … …  
    184185
    185186/**
    186 @defgroup spantree Minimum Spanning Tree algorithms
     187@defgroup spantree Minimum Spanning Tree Algorithms
    187188@ingroup algs
    188189\brief Algorithms for finding a minimum cost spanning tree in a graph.
    … …  
    192193*/
    193194
     195@ingroup algs
    194196/**
    195197@defgroup utils Tools and Utilities
    … …  
    217219
    218220/**
    219 @defgroup timecount Time measuring and Counting
     221@defgroup timecount Time Measuring and Counting
    220222@ingroup misc
    221223\brief Simple tools for measuring the performance of algorithms.
    … …  
    240242and graph related data. Now it supports the LEMON format
    241243and the encapsulated postscript (EPS) format.
     244postscript (EPS) format.
    242245*/
    243246
    … …  
    245248@defgroup lemon_io LEMON Input-Output
    246249@ingroup io_group
    247 \brief Reading and writing \ref lgf-format "LEMON Graph Format".
     250\brief Reading and writing LEMON Graph Format.
    248251
    249252This group describes methods for reading and writing
    … …  
    252255
    253256/**
    254 @defgroup eps_io Postscript exporting
     257@defgroup eps_io Postscript Exporting
    255258@ingroup io_group
    256259\brief General \c EPS drawer and graph exporter
    … …  
    259262graph exporting tools.
    260263*/
    261 
    262264
    263265/**
    … …  
    288290
    289291- Finally, They can serve as a skeleton of a new implementation of a concept.
    290 
    291 */
    292 
     292*/
    293293
    294294/**
    … …  
    301301*/
    302302
     303
     304This group describes the skeletons and concept checking classes of maps.
    303305/**
    304306\anchor demoprograms

  • doc/groups.dox

    r318 r320  
    4141some graph features like arc/edge or node deletion.
    4242
    43 Alteration of standard containers need a very limited number of
    44 operations, these together satisfy the everyday requirements.
    45 In the case of graph structures, different operations are needed which do
    46 not alter the physical graph, but gives another view. If some nodes or
    47 arcs have to be hidden or the reverse oriented graph have to be used, then
    48 this is the case. It also may happen that in a flow implementation
    49 the residual graph can be accessed by another algorithm, or a node-set
    50 is to be shrunk for another algorithm.
    51 LEMON also provides a variety of graphs for these requirements called
    52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    53 in conjunction with other graph representations.
    54 
    5543You are free to use the graph structure that fit your requirements
    5644the best, most graph algorithms and auxiliary data structures can be used
    … …  
    5846
    5947<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    60 */
    61 
    62 /**
    63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64 @ingroup graphs
    65 \brief Graph types between real graphs and graph adaptors.
    66 
    67 This group describes some graph types between real graphs and graph adaptors.
    68 These classes wrap graphs to give new functionality as the adaptors do it.
    69 On the other hand they are not light-weight structures as the adaptors.
    7048*/
    7149
    … …  
    156134
    157135/**
    158 @defgroup matrices Matrices
    159 @ingroup datas
    160 \brief Two dimensional data storages implemented in LEMON.
    161 
    162 This group describes two dimensional data storages implemented in LEMON.
    163 */
    164 
    165 /**
    166136@defgroup paths Path Structures
    167137@ingroup datas
    … …  
    215185
    216186/**
    217 @defgroup max_flow Maximum Flow Algorithms
    218 @ingroup algs
    219 \brief Algorithms for finding maximum flows.
    220 
    221 This group describes the algorithms for finding maximum flows and
    222 feasible circulations.
    223 
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    234 
    235 LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
    249 @ingroup algs
    250 
    251 \brief Algorithms for finding minimum cost flows and circulations.
    252 
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
    255 */
    256 
    257 /**
    258 @defgroup min_cut Minimum Cut Algorithms
    259 @ingroup algs
    260 
    261 \brief Algorithms for finding minimum cut in graphs.
    262 
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269 cut is the \f$X\f$ solution of the next optimization problem:
    270 
    271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    273 
    274 LEMON contains several algorithms related to minimum cut problems:
    275 
    276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    277   in directed graphs
    278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    279   calculate minimum cut in undirected graphs
    280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    281   pairs minimum cut in undirected graphs
    282 
    283 If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
    285 */
    286 
    287 /**
    288 @defgroup graph_prop Connectivity and Other Graph Properties
    289 @ingroup algs
    290 \brief Algorithms for discovering the graph properties
    291 
    292 This group describes the algorithms for discovering the graph properties
    293 like connectivity, bipartiteness, euler property, simplicity etc.
    294 
    295 \image html edge_biconnected_components.png
    296 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    297 */
    298 
    299 /**
    300 @defgroup planar Planarity Embedding and Drawing
    301 @ingroup algs
    302 \brief Algorithms for planarity checking, embedding and drawing
    303 
    304 This group describes the algorithms for planarity checking,
    305 embedding and drawing.
    306 
    307 \image html planar.png
    308 \image latex planar.eps "Plane graph" width=\textwidth
    309 */
    310 
    311 /**
    312 @defgroup matching Matching Algorithms
    313 @ingroup algs
    314 \brief Algorithms for finding matchings in graphs and bipartite graphs.
    315 
    316 This group contains algorithm objects and functions to calculate
    317 matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
    319 
    320 There are several different algorithms for calculate matchings in
    321 graphs.  The matching problems in bipartite graphs are generally
    322 easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
    324 matching. The search can be constrained to find perfect or
    325 maximum cardinality matching.
    326 
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
    347 
    348 \image html bipartite_matching.png
    349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    350 */
    351 
    352 /**
    353187@defgroup spantree Minimum Spanning Tree Algorithms
    354188@ingroup algs
    … …  
    359193*/
    360194
    361 /**
    362 @defgroup auxalg Auxiliary Algorithms
    363195@ingroup algs
    364 \brief Auxiliary algorithms implemented in LEMON.
    365 
    366 This group describes some algorithms implemented in LEMON
    367 in order to make it easier to implement complex algorithms.
    368 */
    369 
    370 /**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
    376 implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
    382 implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
    385 implemented in LEMON.
    386 */
    387 
    388 /**
    389 @defgroup lp_group Lp and Mip Solvers
    390 @ingroup gen_opt_group
    391 \brief Lp and Mip solver interfaces for LEMON.
    392 
    393 This group describes Lp and Mip solver interfaces for LEMON. The
    394 various LP solvers could be used in the same manner with this
    395 interface.
    396 */
    397 
    398 /**
    399 @defgroup lp_utils Tools for Lp and Mip Solvers
    400 @ingroup lp_group
    401 \brief Helper tools to the Lp and Mip solvers.
    402 
    403 This group adds some helper tools to general optimization framework
    404 implemented in LEMON.
    405 */
    406 
    407 /**
    408 @defgroup metah Metaheuristics
    409 @ingroup gen_opt_group
    410 \brief Metaheuristics for LEMON library.
    411 
    412 This group describes some metaheuristic optimization tools.
    413 */
    414 
    415196/**
    416197@defgroup utils Tools and Utilities
    … …  
    459240
    460241This group describes the tools for importing and exporting graphs
    461 and graph related data. Now it supports the \ref lgf-format
    462 "LEMON Graph Format", the \c DIMACS format and the encapsulated
     242and graph related data. Now it supports the LEMON format
     243and the encapsulated postscript (EPS) format.
    463244postscript (EPS) format.
    464245*/
    … …  
    520301*/
    521302
    522 /**
    523 @defgroup map_concepts Map Concepts
    524 @ingroup concept
    525 \brief Skeleton and concept checking classes for maps
    526303
    527304This group describes the skeletons and concept checking classes of maps.
    528 */
    529 
    530305/**
    531306\anchor demoprograms
    … …  
    539314build the library.
    540315*/
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
    544 
    545 Some utility applications are listed here.
    546 
    547 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    548 them, as well.
    549 */
    550 

  • doc/mainpage.dox

    r302 r320  
    4444If you
    4545want to see how LEMON works, see
    46 some \ref demoprograms "demo programs"!
     46some \ref demoprograms "demo programs".
    4747
    4848If you know what you are looking for then try to find it under the
    … …  
    5050section.
    5151
    52 
     52If you are a user of the old (0.x) series of LEMON, please check out the
     53\ref migration "Migration Guide" for the backward incompatibilities.
    5354*/

  • doc/mainpage.dox

    r318 r320  
    4242\subsection howtoread How to read the documentation
    4343
    44 If you want to get a quick start and see the most important features then
    45 take a look at our \ref quicktour
    46 "Quick Tour to LEMON" which will guide you along.
    47 
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    5144If you
    5245want to see how LEMON works, see

  • lemon/maps.h

    r301 r320  
    4444  class MapBase {
    4545  public:
    46     /// \biref The key type of the map.
     46    /// \brief The key type of the map.
    4747    typedef K Key;
    4848    /// \brief The value type of the map.
    … …  
    7474  };
    7575
    76   /// Returns a \ref NullMap class
    77 
    78   /// This function just returns a \ref NullMap class.
     76  /// Returns a \c NullMap class
     77
     78  /// This function just returns a \c NullMap class.
    7979  /// \relates NullMap
    8080  template <typename K, typename V>
    … …  
    8989  /// value to each key.
    9090  ///
    91   /// In other aspects it is equivalent to \ref NullMap.
     91  /// In other aspects it is equivalent to \c NullMap.
    9292  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    9393  /// concept, but it absorbs the data written to it.
    … …  
    134134  };
    135135
    136   /// Returns a \ref ConstMap class
    137 
    138   /// This function just returns a \ref ConstMap class.
     136  /// Returns a \c ConstMap class
     137
     138  /// This function just returns a \c ConstMap class.
    139139  /// \relates ConstMap
    140140  template<typename K, typename V>
    … …  
    157157  /// value to each key.
    158158  ///
    159   /// In other aspects it is equivalent to \ref NullMap.
     159  /// In other aspects it is equivalent to \c NullMap.
    160160  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
    161161  /// concept, but it absorbs the data written to it.
    … …  
    183183  };
    184184
    185   /// Returns a \ref ConstMap class with inlined constant value
    186 
    187   /// This function just returns a \ref ConstMap class with inlined
     185  /// Returns a \c ConstMap class with inlined constant value
     186
     187  /// This function just returns a \c ConstMap class with inlined
    188188  /// constant value.
    189189  /// \relates ConstMap
    … …  
    213213  };
    214214
    215   /// Returns an \ref IdentityMap class
    216 
    217   /// This function just returns an \ref IdentityMap class.
     215  /// Returns an \c IdentityMap class
     216
     217  /// This function just returns an \c IdentityMap class.
    218218  /// \relates IdentityMap
    219219  template<typename T>
    … …  
    229229  /// values to integer keys from the range <tt>[0..size-1]</tt>.
    230230  /// It can be used with some data structures, for example
    231   /// \ref UnionFind, \ref BinHeap, when the used items are small
     231  /// \c UnionFind, \c BinHeap, when the used items are small
    232232  /// integers. This map conforms the \ref concepts::ReferenceMap
    233233  /// "ReferenceMap" concept.
    … …  
    269269      : _vector(vector.begin(), vector.end()) {}
    270270
    271     /// Constructs the map from another \ref RangeMap.
     271    /// Constructs the map from another \c RangeMap.
    272272    template <typename V1>
    273273    RangeMap(const RangeMap<V1> &c)
    … …  
    312312  };
    313313
    314   /// Returns a \ref RangeMap class
    315 
    316   /// This function just returns a \ref RangeMap class.
     314  /// Returns a \c RangeMap class
     315
     316  /// This function just returns a \c RangeMap class.
    317317  /// \relates RangeMap
    318318  template<typename V>
    … …  
    321321  }
    322322
    323   /// \brief Returns a \ref RangeMap class created from an appropriate
     323  /// \brief Returns a \c RangeMap class created from an appropriate
    324324  /// \c std::vector
    325325
    326   /// This function just returns a \ref RangeMap class created from an
     326  /// This function just returns a \c RangeMap class created from an
    327327  /// appropriate \c std::vector.
    328328  /// \relates RangeMap
    … …  
    389389      : _map(map.begin(), map.end()), _value(value) {}
    390390
    391     /// \brief Constructs the map from another \ref SparseMap.
     391    /// \brief Constructs the map from another \c SparseMap.
    392392    template<typename V1, typename Comp1>
    393393    SparseMap(const SparseMap<Key, V1, Comp1> &c)
    … …  
    434434  };
    435435
    436   /// Returns a \ref SparseMap class
    437 
    438   /// This function just returns a \ref SparseMap class with specified
     436  /// Returns a \c SparseMap class
     437
     438  /// This function just returns a \c SparseMap class with specified
    439439  /// default value.
    440440  /// \relates SparseMap
    … …  
    449449  }
    450450
    451   /// \brief Returns a \ref SparseMap class created from an appropriate
     451  /// \brief Returns a \c SparseMap class created from an appropriate
    452452  /// \c std::map
    453453
    454   /// This function just returns a \ref SparseMap class created from an
     454  /// This function just returns a \c SparseMap class created from an
    455455  /// appropriate \c std::map.
    456456  /// \relates SparseMap
    … …  
    502502  };
    503503
    504   /// Returns a \ref ComposeMap class
    505 
    506   /// This function just returns a \ref ComposeMap class.
     504  /// Returns a \c ComposeMap class
     505
     506  /// This function just returns a \c ComposeMap class.
    507507  ///
    508508  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
    … …  
    557557  };
    558558
    559   /// Returns a \ref CombineMap class
    560 
    561   /// This function just returns a \ref CombineMap class.
     559  /// Returns a \c CombineMap class
     560
     561  /// This function just returns a \c CombineMap class.
    562562  ///
    563563  /// For example, if \c m1 and \c m2 are both maps with \c double
    … …  
    626626  };
    627627
    628   /// Returns a \ref FunctorToMap class
    629 
    630   /// This function just returns a \ref FunctorToMap class.
     628  /// Returns a \c FunctorToMap class
     629
     630  /// This function just returns a \c FunctorToMap class.
    631631  ///
    632632  /// This function is specialized for adaptable binary function
    … …  
    685685  };
    686686
    687   /// Returns a \ref MapToFunctor class
    688 
    689   /// This function just returns a \ref MapToFunctor class.
     687  /// Returns a \c MapToFunctor class
     688
     689  /// This function just returns a \c MapToFunctor class.
    690690  /// \relates MapToFunctor
    691691  template<typename M>
    … …  
    724724  };
    725725
    726   /// Returns a \ref ConvertMap class
    727 
    728   /// This function just returns a \ref ConvertMap class.
     726  /// Returns a \c ConvertMap class
     727
     728  /// This function just returns a \c ConvertMap class.
    729729  /// \relates ConvertMap
    730730  template<typename V, typename M>
    … …  
    764764  };
    765765
    766   /// Returns a \ref ForkMap class
    767 
    768   /// This function just returns a \ref ForkMap class.
     766  /// Returns a \c ForkMap class
     767
     768  /// This function just returns a \c ForkMap class.
    769769  /// \relates ForkMap
    770770  template <typename M1, typename M2>
    … …  
    808808  };
    809809
    810   /// Returns an \ref AddMap class
    811 
    812   /// This function just returns an \ref AddMap class.
     810  /// Returns an \c AddMap class
     811
     812  /// This function just returns an \c AddMap class.
    813813  ///
    814814  /// For example, if \c m1 and \c m2 are both maps with \c double
    … …  
    856856  };
    857857
    858   /// Returns a \ref SubMap class
    859 
    860   /// This function just returns a \ref SubMap class.
     858  /// Returns a \c SubMap class
     859
     860  /// This function just returns a \c SubMap class.
    861861  ///
    862862  /// For example, if \c m1 and \c m2 are both maps with \c double
    … …  
    905905  };
    906906
    907   /// Returns a \ref MulMap class
    908 
    909   /// This function just returns a \ref MulMap class.
     907  /// Returns a \c MulMap class
     908
     909  /// This function just returns a \c MulMap class.
    910910  ///
    911911  /// For example, if \c m1 and \c m2 are both maps with \c double
    … …  
    953953  };
    954954
    955   /// Returns a \ref DivMap class
    956 
    957   /// This function just returns a \ref DivMap class.
     955  /// Returns a \c DivMap class
     956
     957  /// This function just returns a \c DivMap class.
    958958  ///
    959959  /// For example, if \c m1 and \c m2 are both maps with \c double
    … …  
    10391039  };
    10401040
    1041   /// Returns a \ref ShiftMap class
    1042 
    1043   /// This function just returns a \ref ShiftMap class.
     1041  /// Returns a \c ShiftMap class
     1042
     1043  /// This function just returns a \c ShiftMap class.
    10441044  ///
    10451045  /// For example, if \c m is a map with \c double values and \c v is
    … …  
    10531053  }
    10541054
    1055   /// Returns a \ref ShiftWriteMap class
    1056 
    1057   /// This function just returns a \ref ShiftWriteMap class.
     1055  /// Returns a \c ShiftWriteMap class
     1056
     1057  /// This function just returns a \c ShiftWriteMap class.
    10581058  ///
    10591059  /// For example, if \c m is a map with \c double values and \c v is
    … …  
    11411141  };
    11421142
    1143   /// Returns a \ref ScaleMap class
    1144 
    1145   /// This function just returns a \ref ScaleMap class.
     1143  /// Returns a \c ScaleMap class
     1144
     1145  /// This function just returns a \c ScaleMap class.
    11461146  ///
    11471147  /// For example, if \c m is a map with \c double values and \c v is
    … …  
    11551155  }
    11561156
    1157   /// Returns a \ref ScaleWriteMap class
    1158 
    1159   /// This function just returns a \ref ScaleWriteMap class.
     1157  /// Returns a \c ScaleWriteMap class
     1158
     1159  /// This function just returns a \c ScaleWriteMap class.
    11601160  ///
    11611161  /// For example, if \c m is a map with \c double values and \c v is
    … …  
    12411241  };
    12421242
    1243   /// Returns a \ref NegMap class
    1244 
    1245   /// This function just returns a \ref NegMap class.
     1243  /// Returns a \c NegMap class
     1244
     1245  /// This function just returns a \c NegMap class.
    12461246  ///
    12471247  /// For example, if \c m is a map with \c double values, then
    … …  
    12541254  }
    12551255
    1256   /// Returns a \ref NegWriteMap class
    1257 
    1258   /// This function just returns a \ref NegWriteMap class.
     1256  /// Returns a \c NegWriteMap class
     1257
     1258  /// This function just returns a \c NegWriteMap class.
    12591259  ///
    12601260  /// For example, if \c m is a map with \c double values, then
    … …  
    12971297  };
    12981298
    1299   /// Returns an \ref AbsMap class
    1300 
    1301   /// This function just returns an \ref AbsMap class.
     1299  /// Returns an \c AbsMap class
     1300
     1301  /// This function just returns an \c AbsMap class.
    13021302  ///
    13031303  /// For example, if \c m is a map with \c double values, then
    … …  
    13461346  };
    13471347
    1348   /// Returns a \ref TrueMap class
    1349 
    1350   /// This function just returns a \ref TrueMap class.
     1348  /// Returns a \c TrueMap class
     1349
     1350  /// This function just returns a \c TrueMap class.
    13511351  /// \relates TrueMap
    13521352  template<typename K>
    … …  
    13831383  };
    13841384
    1385   /// Returns a \ref FalseMap class
    1386 
    1387   /// This function just returns a \ref FalseMap class.
     1385  /// Returns a \c FalseMap class
     1386
     1387  /// This function just returns a \c FalseMap class.
    13881388  /// \relates FalseMap
    13891389  template<typename K>
    … …  
    14301430  };
    14311431
    1432   /// Returns an \ref AndMap class
    1433 
    1434   /// This function just returns an \ref AndMap class.
     1432  /// Returns an \c AndMap class
     1433
     1434  /// This function just returns an \c AndMap class.
    14351435  ///
    14361436  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
    … …  
    14781478  };
    14791479
    1480   /// Returns an \ref OrMap class
    1481 
    1482   /// This function just returns an \ref OrMap class.
     1480  /// Returns an \c OrMap class
     1481
     1482  /// This function just returns an \c OrMap class.
    14831483  ///
    14841484  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
    … …  
    15451545  };
    15461546
    1547   /// Returns a \ref NotMap class
    1548 
    1549   /// This function just returns a \ref NotMap class.
     1547  /// Returns a \c NotMap class
     1548
     1549  /// This function just returns a \c NotMap class.
    15501550  ///
    15511551  /// For example, if \c m is a map with \c bool values, then
    … …  
    15581558  }
    15591559
    1560   /// Returns a \ref NotWriteMap class
    1561 
    1562   /// This function just returns a \ref NotWriteMap class.
     1560  /// Returns a \c NotWriteMap class
     1561
     1562  /// This function just returns a \c NotWriteMap class.
    15631563  ///
    15641564  /// For example, if \c m is a map with \c bool values, then
    … …  
    16061606  };
    16071607
    1608   /// Returns an \ref EqualMap class
    1609 
    1610   /// This function just returns an \ref EqualMap class.
     1608  /// Returns an \c EqualMap class
     1609
     1610  /// This function just returns an \c EqualMap class.
    16111611  ///
    16121612  /// For example, if \c m1 and \c m2 are maps with keys and values of
    … …  
    16541654  };
    16551655
    1656   /// Returns an \ref LessMap class
    1657 
    1658   /// This function just returns an \ref LessMap class.
     1656  /// Returns an \c LessMap class
     1657
     1658  /// This function just returns an \c LessMap class.
    16591659  ///
    16601660  /// For example, if \c m1 and \c m2 are maps with keys and values of
    … …  
    16831683
    16841684  }
     1685
     1686  /// @}
     1687
     1688  /// \addtogroup maps
     1689  /// @{
    16851690
    16861691  /// \brief Writable bool map for logging each \c true assigned element
    … …  
    17461751  };
    17471752
    1748   /// Returns a \ref LoggerBoolMap class
    1749 
    1750   /// This function just returns a \ref LoggerBoolMap class.
     1753  /// Returns a \c LoggerBoolMap class
     1754
     1755  /// This function just returns a \c LoggerBoolMap class.
    17511756  ///
    17521757  /// The most important usage of it is storing certain nodes or arcs
    … …  
    17681773  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
    17691774  /// it cannot be used when a readable map is needed, for example as
    1770   /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
     1775  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
    17711776  ///
    17721777  /// \relates LoggerBoolMap
    … …  
    17751780    return LoggerBoolMap<Iterator>(it);
    17761781  }
     1782
     1783  /// @}
     1784
     1785  /// \addtogroup graph_maps
     1786  /// @{
    17771787
    17781788  /// Provides an immutable and unique id for each item in the graph.
    … …  
    18621872    ///
    18631873    /// Constructor
    1864     /// \param _digraph The digraph that the map belongs to.
     1874    /// \param digraph The digraph that the map belongs to.
    18651875    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
    18661876
    … …  
    18781888  };
    18791889
    1880   /// \brief Returns a \ref SourceMap class.
    1881   ///
    1882   /// This function just returns an \ref SourceMap class.
     1890  /// \brief Returns a \c SourceMap class.
     1891  ///
     1892  /// This function just returns an \c SourceMap class.
    18831893  /// \relates SourceMap
    18841894  template <typename Digraph>
    … …  
    19011911    ///
    19021912    /// Constructor
    1903     /// \param _digraph The digraph that the map belongs to.
     1913    /// \param digraph The digraph that the map belongs to.
    19041914    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
    19051915
    … …  
    19171927  };
    19181928
    1919   /// \brief Returns a \ref TargetMap class.
    1920   ///
    1921   /// This function just returns a \ref TargetMap class.
     1929  /// \brief Returns a \c TargetMap class.
     1930  ///
     1931  /// This function just returns a \c TargetMap class.
    19221932  /// \relates TargetMap
    19231933  template <typename Digraph>
    … …  
    19401950    ///
    19411951    /// Constructor
    1942     /// \param _graph The graph that the map belongs to.
     1952    /// \param graph The graph that the map belongs to.
    19431953    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
    19441954
    … …  
    19561966  };
    19571967
    1958   /// \brief Returns a \ref ForwardMap class.
    1959   ///
    1960   /// This function just returns an \ref ForwardMap class.
     1968  /// \brief Returns a \c ForwardMap class.
     1969  ///
     1970  /// This function just returns an \c ForwardMap class.
    19611971  /// \relates ForwardMap
    19621972  template <typename Graph>
    … …  
    19791989    ///
    19801990    /// Constructor
    1981     /// \param _graph The graph that the map belongs to.
     1991    /// \param graph The graph that the map belongs to.
    19821992    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
    19831993
    … …  
    19952005  };
    19962006
    1997   /// \brief Returns a \ref BackwardMap class
    1998 
    1999   /// This function just returns a \ref BackwardMap class.
     2007  /// \brief Returns a \c BackwardMap class
     2008
     2009  /// This function just returns a \c BackwardMap class.
    20002010  /// \relates BackwardMap
    20012011  template <typename Graph>

  • lemon/maps.h

    r318 r320  
    18561856    InverseMap inverse() const { return InverseMap(*_graph);}
    18571857
    1858   };
    1859 
    1860 
    1861   /// \brief General invertable graph-map type.
    1862 
    1863   /// This type provides simple invertable graph-maps.
    1864   /// The InvertableMap wraps an arbitrary ReadWriteMap
    1865   /// and if a key is set to a new value then store it
    1866   /// in the inverse map.
    1867   ///
    1868   /// The values of the map can be accessed
    1869   /// with stl compatible forward iterator.
    1870   ///
    1871   /// \tparam _Graph The graph type.
    1872   /// \tparam _Item The item type of the graph.
    1873   /// \tparam _Value The value type of the map.
    1874   ///
    1875   /// \see IterableValueMap
    1876   template <typename _Graph, typename _Item, typename _Value>
    1877   class InvertableMap
    1878     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
    1879   private:
    1880 
    1881     typedef typename ItemSetTraits<_Graph, _Item>::
    1882     template Map<_Value>::Type Map;
    1883     typedef _Graph Graph;
    1884 
    1885     typedef std::map<_Value, _Item> Container;
    1886     Container _inv_map;
    1887 
    1888   public:
    1889 
    1890     /// The key type of InvertableMap (Node, Arc, Edge).
    1891     typedef typename Map::Key Key;
    1892     /// The value type of the InvertableMap.
    1893     typedef typename Map::Value Value;
    1894 
    1895     /// \brief Constructor.
    1896     ///
    1897     /// Construct a new InvertableMap for the graph.
    1898     ///
    1899     explicit InvertableMap(const Graph& graph) : Map(graph) {}
    1900 
    1901     /// \brief Forward iterator for values.
    1902     ///
    1903     /// This iterator is an stl compatible forward
    1904     /// iterator on the values of the map. The values can
    1905     /// be accessed in the [beginValue, endValue) range.
    1906     ///
    1907     class ValueIterator
    1908       : public std::iterator<std::forward_iterator_tag, Value> {
    1909       friend class InvertableMap;
    1910     private:
    1911       ValueIterator(typename Container::const_iterator _it)
    1912         : it(_it) {}
    1913     public:
    1914 
    1915       ValueIterator() {}
    1916 
    1917       ValueIterator& operator++() { ++it; return *this; }
    1918       ValueIterator operator++(int) {
    1919         ValueIterator tmp(*this);
    1920         operator++();
    1921         return tmp;
    1922       }
    1923 
    1924       const Value& operator*() const { return it->first; }
    1925       const Value* operator->() const { return &(it->first); }
    1926 
    1927       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1928       bool operator!=(ValueIterator jt) const { return it != jt.it; }
    1929 
    1930     private:
    1931       typename Container::const_iterator it;
    1932     };
    1933 
    1934     /// \brief Returns an iterator to the first value.
    1935     ///
    1936     /// Returns an stl compatible iterator to the
    1937     /// first value of the map. The values of the
    1938     /// map can be accessed in the [beginValue, endValue)
    1939     /// range.
    1940     ValueIterator beginValue() const {
    1941       return ValueIterator(_inv_map.begin());
    1942     }
    1943 
    1944     /// \brief Returns an iterator after the last value.
    1945     ///
    1946     /// Returns an stl compatible iterator after the
    1947     /// last value of the map. The values of the
    1948     /// map can be accessed in the [beginValue, endValue)
    1949     /// range.
    1950     ValueIterator endValue() const {
    1951       return ValueIterator(_inv_map.end());
    1952     }
    1953 
    1954     /// \brief The setter function of the map.
    1955     ///
    1956     /// Sets the mapped value.
    1957     void set(const Key& key, const Value& val) {
    1958       Value oldval = Map::operator[](key);
    1959       typename Container::iterator it = _inv_map.find(oldval);
    1960       if (it != _inv_map.end() && it->second == key) {
    1961         _inv_map.erase(it);
    1962       }
    1963       _inv_map.insert(make_pair(val, key));
    1964       Map::set(key, val);
    1965     }
    1966 
    1967     /// \brief The getter function of the map.
    1968     ///
    1969     /// It gives back the value associated with the key.
    1970     typename MapTraits<Map>::ConstReturnValue
    1971     operator[](const Key& key) const {
    1972       return Map::operator[](key);
    1973     }
    1974 
    1975     /// \brief Gives back the item by its value.
    1976     ///
    1977     /// Gives back the item by its value.
    1978     Key operator()(const Value& key) const {
    1979       typename Container::const_iterator it = _inv_map.find(key);
    1980       return it != _inv_map.end() ? it->second : INVALID;
    1981     }
    1982 
    1983   protected:
    1984 
    1985     /// \brief Erase the key from the map.
    1986     ///
    1987     /// Erase the key to the map. It is called by the
    1988     /// \c AlterationNotifier.
    1989     virtual void erase(const Key& key) {
    1990       Value val = Map::operator[](key);
    1991       typename Container::iterator it = _inv_map.find(val);
    1992       if (it != _inv_map.end() && it->second == key) {
    1993         _inv_map.erase(it);
    1994       }
    1995       Map::erase(key);
    1996     }
    1997 
    1998     /// \brief Erase more keys from the map.
    1999     ///
    2000     /// Erase more keys from the map. It is called by the
    2001     /// \c AlterationNotifier.
    2002     virtual void erase(const std::vector<Key>& keys) {
    2003       for (int i = 0; i < int(keys.size()); ++i) {
    2004         Value val = Map::operator[](keys[i]);
    2005         typename Container::iterator it = _inv_map.find(val);
    2006         if (it != _inv_map.end() && it->second == keys[i]) {
    2007           _inv_map.erase(it);
    2008         }
    2009       }
    2010       Map::erase(keys);
    2011     }
    2012 
    2013     /// \brief Clear the keys from the map and inverse map.
    2014     ///
    2015     /// Clear the keys from the map and inverse map. It is called by the
    2016     /// \c AlterationNotifier.
    2017     virtual void clear() {
    2018       _inv_map.clear();
    2019       Map::clear();
    2020     }
    2021 
    2022   public:
    2023 
    2024     /// \brief The inverse map type.
    2025     ///
    2026     /// The inverse of this map. The subscript operator of the map
    2027     /// gives back always the item what was last assigned to the value.
    2028     class InverseMap {
    2029     public:
    2030       /// \brief Constructor of the InverseMap.
    2031       ///
    2032       /// Constructor of the InverseMap.
    2033       explicit InverseMap(const InvertableMap& inverted)
    2034         : _inverted(inverted) {}
    2035 
    2036       /// The value type of the InverseMap.
    2037       typedef typename InvertableMap::Key Value;
    2038       /// The key type of the InverseMap.
    2039       typedef typename InvertableMap::Value Key;
    2040 
    2041       /// \brief Subscript operator.
    2042       ///
    2043       /// Subscript operator. It gives back always the item
    2044       /// what was last assigned to the value.
    2045       Value operator[](const Key& key) const {
    2046         return _inverted(key);
    2047       }
    2048 
    2049     private:
    2050       const InvertableMap& _inverted;
    2051     };
    2052 
    2053     /// \brief It gives back the just readable inverse map.
    2054     ///
    2055     /// It gives back the just readable inverse map.
    2056     InverseMap inverse() const {
    2057       return InverseMap(*this);
    2058     }
    2059 
    2060   };
    2061 
    2062   /// \brief Provides a mutable, continuous and unique descriptor for each
    2063   /// item in the graph.
    2064   ///
    2065   /// The DescriptorMap class provides a unique and continuous (but mutable)
    2066   /// descriptor (id) for each item of the same type (e.g. node) in the
    2067   /// graph. This id is <ul><li>\b unique: different items (nodes) get
    2068   /// different ids <li>\b continuous: the range of the ids is the set of
    2069   /// integers between 0 and \c n-1, where \c n is the number of the items of
    2070   /// this type (e.g. nodes) (so the id of a node can change if you delete an
    2071   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    2072   /// with its member class \c InverseMap, or with the \c operator() member.
    2073   ///
    2074   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
    2075   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
    2076   /// Edge.
    2077   template <typename _Graph, typename _Item>
    2078   class DescriptorMap
    2079     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
    2080 
    2081     typedef _Item Item;
    2082     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
    2083 
    2084   public:
    2085     /// The graph class of DescriptorMap.
    2086     typedef _Graph Graph;
    2087 
    2088     /// The key type of DescriptorMap (Node, Arc, Edge).
    2089     typedef typename Map::Key Key;
    2090     /// The value type of DescriptorMap.
    2091     typedef typename Map::Value Value;
    2092 
    2093     /// \brief Constructor.
    2094     ///
    2095     /// Constructor for descriptor map.
    2096     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    2097       Item it;
    2098       const typename Map::Notifier* nf = Map::notifier();
    2099       for (nf->first(it); it != INVALID; nf->next(it)) {
    2100         Map::set(it, _inv_map.size());
    2101         _inv_map.push_back(it);
    2102       }
    2103     }
    2104 
    2105   protected:
    2106 
    2107     /// \brief Add a new key to the map.
    2108     ///
    2109     /// Add a new key to the map. It is called by the
    2110     /// \c AlterationNotifier.
    2111     virtual void add(const Item& item) {
    2112       Map::add(item);
    2113       Map::set(item, _inv_map.size());
    2114       _inv_map.push_back(item);
    2115     }
    2116 
    2117     /// \brief Add more new keys to the map.
    2118     ///
    2119     /// Add more new keys to the map. It is called by the
    2120     /// \c AlterationNotifier.
    2121     virtual void add(const std::vector<Item>& items) {
    2122       Map::add(items);
    2123       for (int i = 0; i < int(items.size()); ++i) {
    2124         Map::set(items[i], _inv_map.size());
    2125         _inv_map.push_back(items[i]);
    2126       }
    2127     }
    2128 
    2129     /// \brief Erase the key from the map.
    2130     ///
    2131     /// Erase the key from the map. It is called by the
    2132     /// \c AlterationNotifier.
    2133     virtual void erase(const Item& item) {
    2134       Map::set(_inv_map.back(), Map::operator[](item));
    2135       _inv_map[Map::operator[](item)] = _inv_map.back();
    2136       _inv_map.pop_back();
    2137       Map::erase(item);
    2138     }
    2139 
    2140     /// \brief Erase more keys from the map.
    2141     ///
    2142     /// Erase more keys from the map. It is called by the
    2143     /// \c AlterationNotifier.
    2144     virtual void erase(const std::vector<Item>& items) {
    2145       for (int i = 0; i < int(items.size()); ++i) {
    2146         Map::set(_inv_map.back(), Map::operator[](items[i]));
    2147         _inv_map[Map::operator[](items[i])] = _inv_map.back();
    2148         _inv_map.pop_back();
    2149       }
    2150       Map::erase(items);
    2151     }
    2152 
    2153     /// \brief Build the unique map.
    2154     ///
    2155     /// Build the unique map. It is called by the
    2156     /// \c AlterationNotifier.
    2157     virtual void build() {
    2158       Map::build();
    2159       Item it;
    2160       const typename Map::Notifier* nf = Map::notifier();
    2161       for (nf->first(it); it != INVALID; nf->next(it)) {
    2162         Map::set(it, _inv_map.size());
    2163         _inv_map.push_back(it);
    2164       }
    2165     }
    2166 
    2167     /// \brief Clear the keys from the map.
    2168     ///
    2169     /// Clear the keys from the map. It is called by the
    2170     /// \c AlterationNotifier.
    2171     virtual void clear() {
    2172       _inv_map.clear();
    2173       Map::clear();
    2174     }
    2175 
    2176   public:
    2177 
    2178     /// \brief Returns the maximal value plus one.
    2179     ///
    2180     /// Returns the maximal value plus one in the map.
    2181     unsigned int size() const {
    2182       return _inv_map.size();
    2183     }
    2184 
    2185     /// \brief Swaps the position of the two items in the map.
    2186     ///
    2187     /// Swaps the position of the two items in the map.
    2188     void swap(const Item& p, const Item& q) {
    2189       int pi = Map::operator[](p);
    2190       int qi = Map::operator[](q);
    2191       Map::set(p, qi);
    2192       _inv_map[qi] = p;
    2193       Map::set(q, pi);
    2194       _inv_map[pi] = q;
    2195     }
    2196 
    2197     /// \brief Gives back the \e descriptor of the item.
    2198     ///
    2199     /// Gives back the mutable and unique \e descriptor of the map.
    2200     int operator[](const Item& item) const {
    2201       return Map::operator[](item);
    2202     }
    2203 
    2204     /// \brief Gives back the item by its descriptor.
    2205     ///
    2206     /// Gives back th item by its descriptor.
    2207     Item operator()(int id) const {
    2208       return _inv_map[id];
    2209     }
    2210 
    2211   private:
    2212 
    2213     typedef std::vector<Item> Container;
    2214     Container _inv_map;
    2215 
    2216   public:
    2217     /// \brief The inverse map type of DescriptorMap.
    2218     ///
    2219     /// The inverse map type of DescriptorMap.
    2220     class InverseMap {
    2221     public:
    2222       /// \brief Constructor of the InverseMap.
    2223       ///
    2224       /// Constructor of the InverseMap.
    2225       explicit InverseMap(const DescriptorMap& inverted)
    2226         : _inverted(inverted) {}
    2227 
    2228 
    2229       /// The value type of the InverseMap.
    2230       typedef typename DescriptorMap::Key Value;
    2231       /// The key type of the InverseMap.
    2232       typedef typename DescriptorMap::Value Key;
    2233 
    2234       /// \brief Subscript operator.
    2235       ///
    2236       /// Subscript operator. It gives back the item
    2237       /// that the descriptor belongs to currently.
    2238       Value operator[](const Key& key) const {
    2239         return _inverted(key);
    2240       }
    2241 
    2242       /// \brief Size of the map.
    2243       ///
    2244       /// Returns the size of the map.
    2245       unsigned int size() const {
    2246         return _inverted.size();
    2247       }
    2248 
    2249     private:
    2250       const DescriptorMap& _inverted;
    2251     };
    2252 
    2253     /// \brief Gives back the inverse of the map.
    2254     ///
    2255     /// Gives back the inverse of the map.
    2256     const InverseMap inverse() const {
    2257       return InverseMap(*this);
    2258     }
    22591858  };
    22601859
Note: See TracChangeset for help on using the changeset viewer.