Changeset 967:6563019430ba in lemon-0.x for src

Timestamp:

11/08/04 16:22:39 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1354

Message:

Several changes in doc.

Location:

src

Files:

• lemon/bin_heap.h (modified) (8 diffs)
• lemon/concept/path.h (modified) (1 diff)
• lemon/fib_heap.h (modified) (1 diff)
• lemon/graph_utils.h (modified) (1 diff)
• lemon/xy.h (modified) (2 diffs)
• work/alpar/dijkstra.h (modified) (8 diffs)

src/lemon/bin_heap.h

@@ -33 +33 @@
 
    /// A Binary Heap implementation.
+  
+  ///\todo Please document...
+  ///
+  ///\sa FibHeap
+  ///\sa Dijkstra
   template <typename Item, typename Prio, typename ItemIntMap,
             typename Compare = std::less<Prio> >
@@ -68 +73 @@
 
   public:
+    ///\e
     BinHeap(ItemIntMap &_iim) : iim(_iim) {}
+    ///\e
     BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
 
 
+    ///\e
     int size() const { return data.size(); }
+    ///\e
     bool empty() const { return data.empty(); }
 
@@ -102 +111 @@
 
   public:
+    ///\e
     void push(const PairType &p) {
       int n = data.size();
@@ -107 +117 @@
       bubble_up(n, p);
     }
+    ///\e
     void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
 
+    ///\e
     Item top() const {
       return data[0].first;
@@ -117 +129 @@
     }
 
+    ///\e
     void pop() {
       rmidx(0);
     }
 
+    ///\e
     void erase(const Item &i) {
       rmidx(iim[i]);
     }
 
+    ///\e
     Prio operator[](const Item &i) const {
       int idx = iim[i];
@@ -130 +145 @@
     }
 
+    ///\e
     void set(const Item &i, const Prio &p) {
       int idx = iim[i];
@@ -143 +159 @@
     }
 
+    ///\e
     void decrease(const Item &i, const Prio &p) {
       int idx = iim[i];
       bubble_up(idx, PairType(i,p));
     }
+    ///\e
     void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
@@ -152 +170 @@
     }
 
+    ///\e
     state_enum state(const Item &i) const {
       int s = iim[i];

src/lemon/concept/path.h

@@ -30 +30 @@
 
 
-    //! \brief A skeletom structure for representing directed paths in a graph.
+    //! \brief A skeleton structure for representing directed paths in a graph.
     //!
     //! A skeleton structure for representing directed paths in a graph.

src/lemon/fib_heap.h

@@ -50 +50 @@
   ///default is \c std::less<Prio>.
   ///
+  ///\sa BinHeap
+  ///\sa Dijkstra
   ///\author Jacint Szabo 
  

src/lemon/graph_utils.h

@@ -90 +90 @@
     }
     return num;
+  }
+
+  /// Finds an edge between two nodes of a graph.
+
+  /// Finds an edge from node \c u to node \c v in graph \c g.
+  ///
+  /// If \c prev is \ref INVALID (this is the default value), then
+  /// it finds the first edge from \c u to \c v. Otherwise it looks for
+  /// the next edge from \c u to \c v after \c prev.
+  /// \return The found edge or \ref INVALID if there is no such an edge.
+  ///
+  /// Thus you can iterate through each edge from \c u to \c v as it follows.
+  /// \code
+  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
+  ///   ...
+  /// }
+  /// \endcode
+  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
+  /// interface here...
+  /// \bug Untested ...
+  template <typename Graph>
+  typename Graph::Edge findEdge(const Graph &g,
+                typename Graph::Node u, typename Graph::Node v,
+                typename Graph::Edge prev = INVALID) 
+  {
+    typename Graph::OutEdgeIt e(g,prev);
+    if(prev==INVALID) g.first(e,u);
+    else ++e;
+    while(e!=INVALID && g.tail(e)!=v) ++e;
+    return e;
   }
   

src/lemon/xy.h

@@ -138 +138 @@
   ///Read a plainvector from a stream
 
+  ///Read a plainvector from a stream
   ///\relates xy
   ///
@@ -151 +152 @@
   ///Write a plainvector to a stream
 
+  ///Write a plainvector to a stream
   ///\relates xy
   ///

src/work/alpar/dijkstra.h

@@ -43 +43 @@
     ///The type of the map that stores the edge lengths.
 
-    ///It must meet the \ref ReadMap concept.
+    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
     ///
     typedef LM LengthMap;
@@ -49 +49 @@
     typedef typename LM::ValueType ValueType;
     ///The heap type used by Dijkstra algorithm.
+
+    ///The heap type used by Dijkstra algorithm.
+    ///
+    ///\sa BinHeap
+    ///\sa Dijkstra
     typedef BinHeap<typename Graph::Node,
                     typename LM::ValueType,
@@ -57 +62 @@
     ///edges of the shortest paths.
     /// 
-    ///It must meet the \ref WriteMap concept.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     ///
     typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
@@ -71 +76 @@
     ///nodes of the shortest paths.
     ///
-    ///It must meet the \ref WriteMap concept.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     ///
     typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
@@ -77 +82 @@
  
     ///\todo Please document...
-    /// 
+    ///
     static PredNodeMap *createPredNodeMap(const GR &G)
     {
@@ -84 +89 @@
     ///The type of the map that stores the dists of the nodes.
  
-    ///It must meet the \ref WriteMap concept.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     ///
     typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
@@ -167 +172 @@
     ///The heap type used by the dijkstra algorithm.
     typedef typename TR::Heap Heap;
-
   private:
     /// Pointer to the underlying graph.
@@ -225 +229 @@
     ///\ref named-templ-param "Named parameter" for setting PredMap type
 
+    ///\relates Dijkstra
     ///\ingroup flowalgs 
     ///\ref named-templ-param "Named parameter" for setting PredMap type