Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 318) +++ doc/groups.dox (revision 320) @@ -41,16 +41,4 @@ 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 @@ -58,14 +46,4 @@ See also: \ref graph_concepts "Graph Structure Concepts". -*/ - -/** -@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. */ @@ -156,12 +134,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 @@ -215,140 +185,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 @@ -359,58 +193,5 @@ */ -/** -@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 -@ingroup algs -\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 @@ -459,6 +240,6 @@ This group describes the tools for importing and exporting graphs -and graph related data. Now it supports the \ref lgf-format -"LEMON Graph Format", the \c DIMACS format and the encapsulated +and graph related data. Now it supports the LEMON format +and the encapsulated postscript (EPS) format. postscript (EPS) format. */ @@ -520,12 +301,6 @@ */ -/** -@defgroup map_concepts Map Concepts -@ingroup concept -\brief Skeleton and concept checking classes for maps This group describes the skeletons and concept checking classes of maps. -*/ - /** \anchor demoprograms @@ -539,12 +314,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 318) +++ doc/mainpage.dox (revision 320) @@ -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 318) +++ lemon/maps.h (revision 320) @@ -1856,405 +1856,4 @@ 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).