Index: src/lemon/bin_heap.h
===================================================================
--- src/lemon/bin_heap.h	(revision 1191)
+++ src/lemon/bin_heap.h	(revision 1270)
@@ -21,5 +21,4 @@
 ///\file
 ///\brief Binary Heap implementation.
-///\todo It should be documented.
 
 #include <vector>
@@ -32,7 +31,18 @@
   /// @{
 
-   /// 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<Prio>.
   ///
   ///\sa FibHeap
@@ -73,14 +83,35 @@
 
   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(); }
 
@@ -112,5 +143,10 @@
 
   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();
@@ -118,27 +154,62 @@
       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];
@@ -146,5 +217,10 @@
     }
 
-    ///\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];
@@ -160,10 +236,23 @@
     }
 
-    ///\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];
@@ -171,5 +260,12 @@
     }
 
-    ///\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];
