1.1 --- a/src/lemon/bin_heap.h	Mon Nov 08 08:40:37 2004 +0000
     1.2 +++ b/src/lemon/bin_heap.h	Mon Nov 08 15:22:39 2004 +0000
     1.3 @@ -32,6 +32,11 @@
     1.4    /// @{
     1.5  
     1.6     /// A Binary Heap implementation.
     1.7 +  
     1.8 +  ///\todo Please document...
     1.9 +  ///
    1.10 +  ///\sa FibHeap
    1.11 +  ///\sa Dijkstra
    1.12    template <typename Item, typename Prio, typename ItemIntMap,
    1.13  	    typename Compare = std::less<Prio> >
    1.14    class BinHeap {
    1.15 @@ -67,11 +72,15 @@
    1.16      ItemIntMap &iim;
    1.17  
    1.18    public:
    1.19 +    ///\e
    1.20      BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    1.21 +    ///\e
    1.22      BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
    1.23  
    1.24  
    1.25 +    ///\e
    1.26      int size() const { return data.size(); }
    1.27 +    ///\e
    1.28      bool empty() const { return data.empty(); }
    1.29  
    1.30    private:
    1.31 @@ -101,13 +110,16 @@
    1.32      }
    1.33  
    1.34    public:
    1.35 +    ///\e
    1.36      void push(const PairType &p) {
    1.37        int n = data.size();
    1.38        data.resize(n+1);
    1.39        bubble_up(n, p);
    1.40      }
    1.41 +    ///\e
    1.42      void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
    1.43  
    1.44 +    ///\e
    1.45      Item top() const {
    1.46        return data[0].first;
    1.47      }
    1.48 @@ -116,19 +128,23 @@
    1.49        return data[0].second;
    1.50      }
    1.51  
    1.52 +    ///\e
    1.53      void pop() {
    1.54        rmidx(0);
    1.55      }
    1.56  
    1.57 +    ///\e
    1.58      void erase(const Item &i) {
    1.59        rmidx(iim[i]);
    1.60      }
    1.61  
    1.62 +    ///\e
    1.63      Prio operator[](const Item &i) const {
    1.64        int idx = iim[i];
    1.65        return data[idx].second;
    1.66      }
    1.67  
    1.68 +    ///\e
    1.69      void set(const Item &i, const Prio &p) {
    1.70        int idx = iim[i];
    1.71        if( idx < 0 ) {
    1.72 @@ -142,15 +158,18 @@
    1.73        }
    1.74      }
    1.75  
    1.76 +    ///\e
    1.77      void decrease(const Item &i, const Prio &p) {
    1.78        int idx = iim[i];
    1.79        bubble_up(idx, PairType(i,p));
    1.80      }
    1.81 +    ///\e
    1.82      void increase(const Item &i, const Prio &p) {
    1.83        int idx = iim[i];
    1.84        bubble_down(idx, PairType(i,p), data.size());
    1.85      }
    1.86  
    1.87 +    ///\e
    1.88      state_enum state(const Item &i) const {
    1.89        int s = iim[i];
    1.90        if( s>=0 )

     2.1 --- a/src/lemon/concept/path.h	Mon Nov 08 08:40:37 2004 +0000
     2.2 +++ b/src/lemon/concept/path.h	Mon Nov 08 15:22:39 2004 +0000
     2.3 @@ -29,7 +29,7 @@
     2.4      /// @{
     2.5  
     2.6  
     2.7 -    //! \brief A skeletom structure for representing directed paths in a graph.
     2.8 +    //! \brief A skeleton structure for representing directed paths in a graph.
     2.9      //!
    2.10      //! A skeleton structure for representing directed paths in a graph.
    2.11      //! \param GR The graph type in which the path is.

     3.1 --- a/src/lemon/fib_heap.h	Mon Nov 08 08:40:37 2004 +0000
     3.2 +++ b/src/lemon/fib_heap.h	Mon Nov 08 15:22:39 2004 +0000
     3.3 @@ -49,6 +49,8 @@
     3.4    ///\param Compare A class for the ordering of the priorities. The
     3.5    ///default is \c std::less<Prio>.
     3.6    ///
     3.7 +  ///\sa BinHeap
     3.8 +  ///\sa Dijkstra
     3.9    ///\author Jacint Szabo 
    3.10   
    3.11  #ifdef DOXYGEN

     4.1 --- a/src/lemon/graph_utils.h	Mon Nov 08 08:40:37 2004 +0000
     4.2 +++ b/src/lemon/graph_utils.h	Mon Nov 08 15:22:39 2004 +0000
     4.3 @@ -90,6 +90,36 @@
     4.4      }
     4.5      return num;
     4.6    }
     4.7 +
     4.8 +  /// Finds an edge between two nodes of a graph.
     4.9 +
    4.10 +  /// Finds an edge from node \c u to node \c v in graph \c g.
    4.11 +  ///
    4.12 +  /// If \c prev is \ref INVALID (this is the default value), then
    4.13 +  /// it finds the first edge from \c u to \c v. Otherwise it looks for
    4.14 +  /// the next edge from \c u to \c v after \c prev.
    4.15 +  /// \return The found edge or \ref INVALID if there is no such an edge.
    4.16 +  ///
    4.17 +  /// Thus you can iterate through each edge from \c u to \c v as it follows.
    4.18 +  /// \code
    4.19 +  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
    4.20 +  ///   ...
    4.21 +  /// }
    4.22 +  /// \endcode
    4.23 +  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
    4.24 +  /// interface here...
    4.25 +  /// \bug Untested ...
    4.26 +  template <typename Graph>
    4.27 +  typename Graph::Edge findEdge(const Graph &g,
    4.28 +		typename Graph::Node u, typename Graph::Node v,
    4.29 +		typename Graph::Edge prev = INVALID) 
    4.30 +  {
    4.31 +    typename Graph::OutEdgeIt e(g,prev);
    4.32 +    if(prev==INVALID) g.first(e,u);
    4.33 +    else ++e;
    4.34 +    while(e!=INVALID && g.tail(e)!=v) ++e;
    4.35 +    return e;
    4.36 +  }
    4.37    
    4.38    ///\e
    4.39  

     5.1 --- a/src/lemon/xy.h	Mon Nov 08 08:40:37 2004 +0000
     5.2 +++ b/src/lemon/xy.h	Mon Nov 08 15:22:39 2004 +0000
     5.3 @@ -137,6 +137,7 @@
     5.4  
     5.5    ///Read a plainvector from a stream
     5.6  
     5.7 +  ///Read a plainvector from a stream
     5.8    ///\relates xy
     5.9    ///
    5.10    template<typename T>
    5.11 @@ -150,6 +151,7 @@
    5.12  
    5.13    ///Write a plainvector to a stream
    5.14  
    5.15 +  ///Write a plainvector to a stream
    5.16    ///\relates xy
    5.17    ///
    5.18    template<typename T>

     6.1 --- a/src/work/alpar/dijkstra.h	Mon Nov 08 08:40:37 2004 +0000
     6.2 +++ b/src/work/alpar/dijkstra.h	Mon Nov 08 15:22:39 2004 +0000
     6.3 @@ -42,12 +42,17 @@
     6.4      typedef GR Graph;
     6.5      ///The type of the map that stores the edge lengths.
     6.6  
     6.7 -    ///It must meet the \ref ReadMap concept.
     6.8 +    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
     6.9      ///
    6.10      typedef LM LengthMap;
    6.11      //The type of the length of the edges.
    6.12      typedef typename LM::ValueType ValueType;
    6.13      ///The heap type used by Dijkstra algorithm.
    6.14 +
    6.15 +    ///The heap type used by Dijkstra algorithm.
    6.16 +    ///
    6.17 +    ///\sa BinHeap
    6.18 +    ///\sa Dijkstra
    6.19      typedef BinHeap<typename Graph::Node,
    6.20  		    typename LM::ValueType,
    6.21  		    typename GR::template NodeMap<int>,
    6.22 @@ -56,7 +61,7 @@
    6.23      ///\brief The type of the map that stores the last
    6.24      ///edges of the shortest paths.
    6.25      /// 
    6.26 -    ///It must meet the \ref WriteMap concept.
    6.27 +    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    6.28      ///
    6.29      typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
    6.30      ///Instantiates a PredMap.
    6.31 @@ -70,20 +75,20 @@
    6.32      ///\brief The type of the map that stores the last but one
    6.33      ///nodes of the shortest paths.
    6.34      ///
    6.35 -    ///It must meet the \ref WriteMap concept.
    6.36 +    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    6.37      ///
    6.38      typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
    6.39      ///Instantiates a PredNodeMap.
    6.40   
    6.41      ///\todo Please document...
    6.42 -    /// 
    6.43 +    ///
    6.44      static PredNodeMap *createPredNodeMap(const GR &G)
    6.45      {
    6.46        return new PredNodeMap(G);
    6.47      }
    6.48      ///The type of the map that stores the dists of the nodes.
    6.49   
    6.50 -    ///It must meet the \ref WriteMap concept.
    6.51 +    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    6.52      ///
    6.53      typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
    6.54      ///Instantiates a DistMap.
    6.55 @@ -166,7 +171,6 @@
    6.56      typedef typename TR::DistMap DistMap;
    6.57      ///The heap type used by the dijkstra algorithm.
    6.58      typedef typename TR::Heap Heap;
    6.59 -
    6.60    private:
    6.61      /// Pointer to the underlying graph.
    6.62      const Graph *G;
    6.63 @@ -224,6 +228,7 @@
    6.64      };
    6.65      ///\ref named-templ-param "Named parameter" for setting PredMap type
    6.66  
    6.67 +    ///\relates Dijkstra
    6.68      ///\ingroup flowalgs 
    6.69      ///\ref named-templ-param "Named parameter" for setting PredMap type
    6.70      template <class T>