Index: gtags =================================================================== --- .hgtags (revision 334) +++ (revision ) @@ -1,1 +1,0 @@ -58f1a3144134042f6367fceb7eb29ee8a094d843 r1.0 Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 326) +++ doc/groups.dox (revision 325) @@ -41,4 +41,16 @@ 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 @@ -46,4 +58,14 @@ 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. */ @@ -134,4 +156,12 @@ /** +@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 @@ -185,4 +215,140 @@ /** +@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 @@ -191,4 +357,58 @@ This group describes the algorithms for finding a minimum cost spanning tree in a graph +*/ + +/** +@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. */ @@ -239,6 +459,6 @@ This group describes the tools for importing and exporting graphs -and graph related data. Now it supports the LEMON format -and the encapsulated postscript (EPS) format. +and graph related data. Now it supports the \ref lgf-format +"LEMON Graph Format", the \c DIMACS format and the encapsulated postscript (EPS) format. */ @@ -304,5 +524,5 @@ @ingroup concept \brief Skeleton and concept checking classes for maps - + This group describes the skeletons and concept checking classes of maps. */ @@ -319,2 +539,12 @@ 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 329) +++ doc/mainpage.dox (revision 318) @@ -42,4 +42,15 @@ \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 +some \ref demoprograms "demo programs". + If you know what you are looking for then try to find it under the Modules Index: lemon/dijkstra.h =================================================================== --- lemon/dijkstra.h (revision 317) +++ lemon/dijkstra.h (revision 342) @@ -48,27 +48,4 @@ static Value plus(const Value& left, const Value& right) { return left + right; - } - /// \brief Gives back true only if the first value is less than the second. - static bool less(const Value& left, const Value& right) { - return left < right; - } - }; - - /// \brief Widest path operation traits for the Dijkstra algorithm class. - /// - /// This operation traits class defines all computational operations and - /// constants which are used in the Dijkstra algorithm for widest path - /// computation. - /// - /// \see DijkstraDefaultOperationTraits - template - struct DijkstraWidestPathOperationTraits { - /// \brief Gives back the maximum value of the type. - static Value zero() { - return std::numeric_limits::max(); - } - /// \brief Gives back the minimum of the given two elements. - static Value plus(const Value& left, const Value& right) { - return std::min(left, right); } /// \brief Gives back true only if the first value is less than the second. Index: lemon/maps.h =================================================================== --- lemon/maps.h (revision 320) +++ lemon/maps.h (revision 318) @@ -1856,4 +1856,405 @@ 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).