# Changeset 1270:806451fd084b in lemon-0.x

Ignore:
Timestamp:
03/29/05 09:35:09 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1698
Message:

bugfixes in doc

Location:
src/lemon
Files:
6 edited

Unmodified
Removed
• ## src/lemon/bfs.h

 r1236 ///a Bfs traits class. /// ///\author Jacint Szabo and Alpar Juttner ///\author Alpar Juttner ///\todo A compare object would be nice. ///\ref named-templ-param "Named parameter" ///for setting the ProcessedMap type to be Graph::NodeMap. ///If you don't set it explicitely, it will be automatically allocated. ///If you don't set it explicitly, it will be automatically allocated. template class DefProcessedMapToBeDefaultMap : ///Sets the map storing the predecessor edges. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) ///Sets the map indicating the reached nodes. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) ///Sets the map indicating the processed nodes. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) //     ///Sets the map storing the predecessor nodes. //     ///If you don't use this function before calling \ref run(), //     ///it will allocate one. The destuctor deallocates this //     ///it will allocate one. The destructor deallocates this //     ///automatically allocated map, of course. //     ///\return (*this) ///Sets the map storing the distances calculated by the algorithm. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) ///\pre \ref run() must be called before using this function. ///\warning If node \c v in unreachable from the root(s) the return value ///of this funcion is undefined. ///of this function is undefined. int dist(Node v) const { return (*_dist)[v]; } ///Returns \c true if \c v is reachable from the root. ///\warning The source nodes are inditated as unreached. ///\warning The source nodes are indicated as unreached. ///\pre Either \ref run() or \ref start() ///must be called before using this function.
• ## src/lemon/bin_heap.h

 r1191 ///\file ///\brief Binary Heap implementation. ///\todo It should be documented. #include /// @{ /// A Binary Heap implementation. /// A Binary Heap implementation. ///\todo Please document... ///This class implements the \e binary \e heap data structure. A \e heap ///is a data structure for storing items with specified values called \e ///priorities in such a way that finding the item with minimum priority is ///efficient. \c Compare specifies the ordering of the priorities. In a heap ///one can change the priority of an item, add or erase an item, etc. /// ///\param Item Type of the items to be stored. ///\param Prio Type of the priority of the items. ///\param ItemIntMap A read and writable Item int map, used internally ///to handle the cross references. ///\param Compare A class for the ordering of the priorities. The ///default is \c std::less. /// ///\sa FibHeap public: ///\e ///The constructor /** \c _iim should be given to the constructor, since it is used internally to handle the cross references. */ explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} ///\e ///The constructor /** \c _iim should be given to the constructor, since it is used internally to handle the cross references. \c _comp is an object for ordering of the priorities. */ BinHeap(ItemIntMap &_iim, const Compare &_comp) : iim(_iim), comp(_comp) {} ///\e ///The number of items stored in the heap. /** Returns the number of items stored in the heap. */ int size() const { return data.size(); } ///\e ///Checks if the heap stores no items. /** Returns \c true if and only if the heap stores no items. */ bool empty() const { return data.empty(); } public: ///\e ///Adds \c p.first to the heap with priority \c p.second. /** Adds \c p.first to the heap with priority \c p.second. \c p.first must not be stored in the heap. */ void push(const PairType &p) { int n = data.size(); bubble_up(n, p); } ///\e ///Adds \c i to the heap with priority \c p. /** Adds \c i to the heap with priority \c p. \pre \c i must not be stored in the heap. */ void push(const Item &i, const Prio &p) { push(PairType(i,p)); } ///\e ///Returns the item with minimum priority relative to \c Compare. /** This method returns the item with minimum priority relative to \c Compare. \pre The heap must be nonempty. */ Item top() const { return data[0].first; } /// Returns the prio of the top element of the heap. ///Returns the minimum priority relative to \c Compare. /** It returns the minimum priority relative to \c Compare. \pre The heap must be nonempty. */ Prio prio() const { return data[0].second; } ///\e ///Deletes the item with minimum priority relative to \c Compare. /** This method deletes the item with minimum priority relative to \c Compare from the heap. \pre The heap must be non-empty. */ void pop() { rmidx(0); } ///\e ///Deletes \c i from the heap. /** This method deletes item \c i from the heap, if \c i was already stored in the heap. */ void erase(const Item &i) { rmidx(iim[i]); } ///\e ///Returns the priority of \c i. /** This function returns the priority of item \c i. \pre \c i must be in the heap. */ Prio operator[](const Item &i) const { int idx = iim[i]; } ///\e ///\c i gets to the heap with priority \c p independently if \c i was already there. /** This method calls \ref push(\c i, \c p) if \c i is not stored in the heap and sets the priority of \c i to \c p otherwise. */ void set(const Item &i, const Prio &p) { int idx = iim[i]; } ///\e ///Decreases the priority of \c i to \c p. /** This method decreases the priority of item \c i to \c p. \pre \c i must be stored in the heap with priority at least \c p relative to \c Compare. */ void decrease(const Item &i, const Prio &p) { int idx = iim[i]; bubble_up(idx, PairType(i,p)); } ///\e ///Increases the priority of \c i to \c p. /** This method sets the priority of item \c i to \c p. \pre \c i must be stored in the heap with priority at most \c p relative to \c Compare. */ void increase(const Item &i, const Prio &p) { int idx = iim[i]; } ///\e ///Returns if \c item is in, has already been in, or has never been in the heap. /** This method returns PRE_HEAP if \c item has never been in the heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP otherwise. In the latter case it is possible that \c item will get back to the heap again. */ state_enum state(const Item &i) const { int s = iim[i];
• ## src/lemon/concept/path.h

 r1228 //! \param GR The graph type in which the path is. //! //! In a sense, the path can be treated as a graph, for is has \c NodeIt //! In a sense, the path can be treated as a graph, for it has \c NodeIt //! and \c EdgeIt with the same usage. These types converts to the \c Node //! and \c Edge of the original graph. * * While the builder is active (after the first modifying * operation and until the call of \ref commit()) * the underlining Path is in a * "transitional" state (operations on it have undefined result). * operation and until the call of \ref commit()) the * underlining Path is in a "transitional" state (operations on * it have undefined result). */ class Builder { /// Sets the starting node of the path. Edge added to the path /// afterwards have to be incident to this node. /// You \em must start building an empry path with this functions. /// You \em must start building an empty path with these functions. /// (And you \em must \em not use it later). /// \sa pushFront() ///Reserve (front) storage for the builder in advance. ///If you know an reasonable upper bound of the number of the edges ///If you know a reasonable upper bound on the number of the edges ///to add to the front of the path, ///using this function you may speed up the building. ///Reserve (back) storage for the builder in advance. ///If you know an reasonable upper bound of the number of the edges ///If you know a reasonable upper bound on the number of the edges ///to add to the back of the path, ///using this function you may speed up the building.
• ## src/lemon/fib_heap.h

 r1204 }; ///The constructor /** \c _iimap should be given to the constructor, since it is used internally to handle the cross references. */ explicit FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} ///The constructor /** \c _iimap should be given to the constructor, since it is used internally to handle the cross references. \c _comp is an object for ordering of the priorities. */ FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), iimap(_iimap), comp(_comp), num_items() {} iimap(_iimap), comp(_comp), num_items() {} ///The number of items stored in the heap.
• ## src/lemon/min_cost_flow.h

 r1164 /// /// /// The class \ref lemon::MinCostFlow "MinCostFlow" implements /// an algorithm for finding a flow of value \c k /// having minimal total cost /// from a given source node to a given target node in an /// edge-weighted directed graph. To this end, /// the edge-capacities and edge-weitghs have to be nonnegative. /// The edge-capacities should be integers, but the edge-weights can be /// integers, reals or of other comparable numeric type. /// This algorithm is intended to use only for small values of \c k, /// since it is only polynomial in k, /// not in the length of k (which is log k). /// In order to find the minimum cost flow of value \c k it /// finds the minimum cost flow of value \c i for every /// \c i between 0 and \c k. /// The class \ref lemon::MinCostFlow "MinCostFlow" implements an /// algorithm for finding a flow of value \c k having minimal total /// cost from a given source node to a given target node in an /// edge-weighted directed graph. To this end, the edge-capacities /// and edge-weights have to be nonnegative.  The edge-capacities /// should be integers, but the edge-weights can be integers, reals /// or of other comparable numeric type.  This algorithm is intended /// to be used only for small values of \c k, since it is only /// polynomial in k, not in the length of k (which is log k):  in /// order to find the minimum cost flow of value \c k it finds the /// minimum cost flow of value \c i for every \c i between 0 and \c /// k. /// ///\param Graph The directed graph type the algorithm runs on. potential.set(n, potential[n]+dijkstra.distMap()[n]); //Augmenting on the sortest path //Augmenting on the shortest path Node n=t; ResGraphEdge e; This function checks, whether the given flow and potential satisfiy the complementary slackness cnditions (i.e. these are optimal). satisfy the complementary slackness conditions (i.e. these are optimal). This function only checks optimality, doesn't bother with feasibility. For testing purpose.
• ## src/lemon/utility.h

 r1256 { /// Basic type for defining "tags". A "YES" condidion for enable_if. /// Basic type for defining "tags". A "YES" condition for enable_if. /// \todo This should go to a separate "basic_types.h" (or something) }; /// Basic type for defining "tags". A "NO" condidion for enable_if. /// Basic type for defining "tags". A "NO" condition for enable_if. struct False { static const bool value = false;
Note: See TracChangeset for help on using the changeset viewer.