Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 236) +++ doc/groups.dox (revision 302) @@ -41,29 +41,7 @@ some graph features like arc/edge or node deletion. -Alteration of standard containers need a very limited number of -operations, these together satisfy the everyday requirements. -In the case of graph structures, different operations are needed which do -not alter the physical graph, but gives another view. If some nodes or -arcs have to be hidden or the reverse oriented graph have to be used, then -this is the case. It also may happen that in a flow implementation -the residual graph can be accessed by another algorithm, or a node-set -is to be shrunk for another algorithm. -LEMON also provides a variety of graphs for these requirements called -\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only -in conjunction with other graph representations. - You are free to use the graph structure that fit your requirements the best, most graph algorithms and auxiliary data structures can be used with any graph structures. -*/ - -/** -@defgroup semi_adaptors Semi-Adaptor Classes for Graphs -@ingroup graphs -\brief Graph types between real graphs and graph adaptors. - -This group describes some graph types between real graphs and graph adaptors. -These classes wrap graphs to give new functionality as the adaptors do it. -On the other hand they are not light-weight structures as the adaptors. */ @@ -153,12 +131,4 @@ /** -@defgroup matrices Matrices -@ingroup datas -\brief Two dimensional data storages implemented in LEMON. - -This group describes two dimensional data storages implemented in LEMON. -*/ - -/** @defgroup paths Path Structures @ingroup datas @@ -214,143 +184,4 @@ /** -@defgroup max_flow Maximum Flow algorithms -@ingroup algs -\brief Algorithms for finding maximum flows. - -This group describes the algorithms for finding maximum flows and -feasible circulations. - -The maximum flow problem is to find a flow between a single source and -a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ -directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity -function and given \f$s, t \in V\f$ source and target node. The -maximum flow is the \f$f_a\f$ solution of the next optimization problem: - -\f[ 0 \le f_a \le c_a \f] -\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} -\qquad \forall u \in V \setminus \{s,t\}\f] -\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] - -LEMON contains several algorithms for solving maximum flow problems: -- \ref lemon::EdmondsKarp "Edmonds-Karp" -- \ref lemon::Preflow "Goldberg's Preflow algorithm" -- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" -- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" - -In most cases the \ref lemon::Preflow "Preflow" algorithm provides the -fastest method to compute the maximum flow. All impelementations -provides functions to query the minimum cut, which is the dual linear -programming problem of the maximum flow. - -*/ - -/** -@defgroup min_cost_flow Minimum Cost Flow algorithms -@ingroup algs - -\brief Algorithms for finding minimum cost flows and circulations. - -This group describes the algorithms for finding minimum cost flows and -circulations. -*/ - -/** -@defgroup min_cut Minimum Cut algorithms -@ingroup algs - -\brief Algorithms for finding minimum cut in graphs. - -This group describes the algorithms for finding minimum cut in graphs. - -The minimum cut problem is to find a non-empty and non-complete -\f$X\f$ subset of the vertices with minimum overall capacity on -outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an -\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum -cut is the \f$X\f$ solution of the next optimization problem: - -\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} -\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] - -LEMON contains several algorithms related to minimum cut problems: - -- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut - in directed graphs -- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to - calculate minimum cut in undirected graphs -- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all - pairs minimum cut in undirected graphs - -If you want to find minimum cut just between two distinict nodes, -please see the \ref max_flow "Maximum Flow page". - -*/ - -/** -@defgroup graph_prop Connectivity and other graph properties -@ingroup algs -\brief Algorithms for discovering the graph properties - -This group describes the algorithms for discovering the graph properties -like connectivity, bipartiteness, euler property, simplicity etc. - -\image html edge_biconnected_components.png -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth -*/ - -/** -@defgroup planar Planarity embedding and drawing -@ingroup algs -\brief Algorithms for planarity checking, embedding and drawing - -This group describes the algorithms for planarity checking, -embedding and drawing. - -\image html planar.png -\image latex planar.eps "Plane graph" width=\textwidth -*/ - -/** -@defgroup matching Matching algorithms -@ingroup algs -\brief Algorithms for finding matchings in graphs and bipartite graphs. - -This group contains algorithm objects and functions to calculate -matchings in graphs and bipartite graphs. The general matching problem is -finding a subset of the arcs which does not shares common endpoints. - -There are several different algorithms for calculate matchings in -graphs. The matching problems in bipartite graphs are generally -easier than in general graphs. The goal of the matching optimization -can be the finding maximum cardinality, maximum weight or minimum cost -matching. The search can be constrained to find perfect or -maximum cardinality matching. - -LEMON contains the next algorithms: -- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp - augmenting path algorithm for calculate maximum cardinality matching in - bipartite graphs -- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel - algorithm for calculate maximum cardinality matching in bipartite graphs -- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" - Successive shortest path algorithm for calculate maximum weighted matching - and maximum weighted bipartite matching in bipartite graph -- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" - Successive shortest path algorithm for calculate minimum cost maximum - matching in bipartite graph -- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm - for calculate maximum cardinality matching in general graph -- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom - shrinking algorithm for calculate maximum weighted matching in general - graph -- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" - Edmond's blossom shrinking algorithm for calculate maximum weighted - perfect matching in general graph - -\image html bipartite_matching.png -\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth - -*/ - -/** @defgroup spantree Minimum Spanning Tree algorithms @ingroup algs @@ -361,60 +192,4 @@ */ - -/** -@defgroup auxalg Auxiliary algorithms -@ingroup algs -\brief Auxiliary algorithms implemented in LEMON. - -This group describes some algorithms implemented in LEMON -in order to make it easier to implement complex algorithms. -*/ - -/** -@defgroup approx Approximation algorithms -\brief Approximation algorithms. - -This group describes the approximation and heuristic algorithms -implemented in LEMON. -*/ - -/** -@defgroup gen_opt_group General Optimization Tools -\brief This group describes some general optimization frameworks -implemented in LEMON. - -This group describes some general optimization frameworks -implemented in LEMON. - -*/ - -/** -@defgroup lp_group Lp and Mip solvers -@ingroup gen_opt_group -\brief Lp and Mip solver interfaces for LEMON. - -This group describes Lp and Mip solver interfaces for LEMON. The -various LP solvers could be used in the same manner with this -interface. - -*/ - -/** -@defgroup lp_utils Tools for Lp and Mip solvers -@ingroup lp_group -\brief Helper tools to the Lp and Mip solvers. - -This group adds some helper tools to general optimization framework -implemented in LEMON. -*/ - -/** -@defgroup metah Metaheuristics -@ingroup gen_opt_group -\brief Metaheuristics for LEMON library. - -This group describes some metaheuristic optimization tools. -*/ - /** @defgroup utils Tools and Utilities @@ -451,13 +226,4 @@ /** -@defgroup graphbits Tools for Graph Implementation -@ingroup utils -\brief Tools to make it easier to create graphs. - -This group describes the tools that makes it easier to create graphs and -the maps that dynamically update with the graph changes. -*/ - -/** @defgroup exceptions Exceptions @ingroup utils @@ -472,6 +238,6 @@ This group describes the tools for importing and exporting graphs -and graph related data. Now it supports the LEMON format, the -\c DIMACS format and the encapsulated postscript (EPS) format. +and graph related data. Now it supports the LEMON format +and the encapsulated postscript (EPS) format. */ @@ -535,10 +301,4 @@ */ -/* --- Unused group -@defgroup experimental Experimental Structures and Algorithms -This group describes some Experimental structures and algorithms. -The stuff here is subject to change. -*/ - /** \anchor demoprograms @@ -552,12 +312,2 @@ build the library. */ - -/** -@defgroup tools Standalone utility applications - -Some utility applications are listed here. - -The standard compilation procedure (./configure;make) will compile -them, as well. -*/ - Index: doc/mainpage.dox =================================================================== --- doc/mainpage.dox (revision 209) +++ doc/mainpage.dox (revision 302) @@ -42,11 +42,4 @@ \subsection howtoread How to read the documentation -If you want to get a quick start and see the most important features then -take a look at our \ref quicktour -"Quick Tour to LEMON" which will guide you along. - -If you already feel like using our library, see the page that tells you -\ref getstart "How to start using LEMON". - If you want to see how LEMON works, see Index: lemon/maps.h =================================================================== --- lemon/maps.h (revision 301) +++ lemon/maps.h (revision 280) @@ -1846,4 +1846,409 @@ InverseMap inverse() const { return InverseMap(*_graph);} + }; + + + /// \brief General invertable graph-map type. + + /// This type provides simple invertable graph-maps. + /// The InvertableMap wraps an arbitrary ReadWriteMap + /// and if a key is set to a new value then store it + /// in the inverse map. + /// + /// The values of the map can be accessed + /// with stl compatible forward iterator. + /// + /// \tparam _Graph The graph type. + /// \tparam _Item The item type of the graph. + /// \tparam _Value The value type of the map. + /// + /// \see IterableValueMap + template + class InvertableMap + : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type { + private: + + typedef typename ItemSetTraits<_Graph, _Item>:: + template Map<_Value>::Type Map; + typedef _Graph Graph; + + typedef std::map<_Value, _Item> Container; + Container _inv_map; + + public: + + /// The key type of InvertableMap (Node, Arc, Edge). + typedef typename Map::Key Key; + /// The value type of the InvertableMap. + typedef typename Map::Value Value; + + + + /// \brief Constructor. + /// + /// Construct a new InvertableMap for the graph. + /// + explicit InvertableMap(const Graph& graph) : Map(graph) {} + + /// \brief Forward iterator for values. + /// + /// This iterator is an stl compatible forward + /// iterator on the values of the map. The values can + /// be accessed in the [beginValue, endValue) range. + /// + class ValueIterator + : public std::iterator { + friend class InvertableMap; + private: + ValueIterator(typename Container::const_iterator _it) + : it(_it) {} + public: + + ValueIterator() {} + + ValueIterator& operator++() { ++it; return *this; } + ValueIterator operator++(int) { + ValueIterator tmp(*this); + operator++(); + return tmp; + } + + const Value& operator*() const { return it->first; } + const Value* operator->() const { return &(it->first); } + + bool operator==(ValueIterator jt) const { return it == jt.it; } + bool operator!=(ValueIterator jt) const { return it != jt.it; } + + private: + typename Container::const_iterator it; + }; + + /// \brief Returns an iterator to the first value. + /// + /// Returns an stl compatible iterator to the + /// first value of the map. The values of the + /// map can be accessed in the [beginValue, endValue) + /// range. + ValueIterator beginValue() const { + return ValueIterator(_inv_map.begin()); + } + + /// \brief Returns an iterator after the last value. + /// + /// Returns an stl compatible iterator after the + /// last value of the map. The values of the + /// map can be accessed in the [beginValue, endValue) + /// range. + ValueIterator endValue() const { + return ValueIterator(_inv_map.end()); + } + + /// \brief The setter function of the map. + /// + /// Sets the mapped value. + void set(const Key& key, const Value& val) { + Value oldval = Map::operator[](key); + typename Container::iterator it = _inv_map.find(oldval); + if (it != _inv_map.end() && it->second == key) { + _inv_map.erase(it); + } + _inv_map.insert(make_pair(val, key)); + Map::set(key, val); + } + + /// \brief The getter function of the map. + /// + /// It gives back the value associated with the key. + typename MapTraits::ConstReturnValue + operator[](const Key& key) const { + return Map::operator[](key); + } + + /// \brief Gives back the item by its value. + /// + /// Gives back the item by its value. + Key operator()(const Value& key) const { + typename Container::const_iterator it = _inv_map.find(key); + return it != _inv_map.end() ? it->second : INVALID; + } + + protected: + + /// \brief Erase the key from the map. + /// + /// Erase the key to the map. It is called by the + /// \c AlterationNotifier. + virtual void erase(const Key& key) { + Value val = Map::operator[](key); + typename Container::iterator it = _inv_map.find(val); + if (it != _inv_map.end() && it->second == key) { + _inv_map.erase(it); + } + Map::erase(key); + } + + /// \brief Erase more keys from the map. + /// + /// Erase more keys from the map. It is called by the + /// \c AlterationNotifier. + virtual void erase(const std::vector& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + Value val = Map::operator[](keys[i]); + typename Container::iterator it = _inv_map.find(val); + if (it != _inv_map.end() && it->second == keys[i]) { + _inv_map.erase(it); + } + } + Map::erase(keys); + } + + /// \brief Clear the keys from the map and inverse map. + /// + /// Clear the keys from the map and inverse map. It is called by the + /// \c AlterationNotifier. + virtual void clear() { + _inv_map.clear(); + Map::clear(); + } + + public: + + /// \brief The inverse map type. + /// + /// The inverse of this map. The subscript operator of the map + /// gives back always the item what was last assigned to the value. + class InverseMap { + public: + /// \brief Constructor of the InverseMap. + /// + /// Constructor of the InverseMap. + explicit InverseMap(const InvertableMap& inverted) + : _inverted(inverted) {} + + /// The value type of the InverseMap. + typedef typename InvertableMap::Key Value; + /// The key type of the InverseMap. + typedef typename InvertableMap::Value Key; + + /// \brief Subscript operator. + /// + /// Subscript operator. It gives back always the item + /// what was last assigned to the value. + Value operator[](const Key& key) const { + return _inverted(key); + } + + private: + const InvertableMap& _inverted; + }; + + /// \brief It gives back the just readable inverse map. + /// + /// It gives back the just readable inverse map. + InverseMap inverse() const { + return InverseMap(*this); + } + + + + }; + + /// \brief Provides a mutable, continuous and unique descriptor for each + /// item in the graph. + /// + /// The DescriptorMap class provides a unique and continuous (but mutable) + /// descriptor (id) for each item of the same type (e.g. node) in the + /// graph. This id is
• \b unique: different items (nodes) get + /// different ids
• \b continuous: the range of the ids is the set of + /// integers between 0 and \c n-1, where \c n is the number of the items of + /// this type (e.g. nodes) (so the id of a node can change if you delete an + /// other node, i.e. this id is mutable).