# HG changeset patch
# User jacint
# Date 1082645424 0
# Node ID 259ea2d741a21c4b4fb4e31982e0ba254d49c973
# Parent  e6a156fc186d8b2ab146b3475cd897a96327316d
Changes in the documentation.

diff -r e6a156fc186d -r 259ea2d741a2 src/include/dijkstra.h
--- a/src/include/dijkstra.h	Thu Apr 22 14:11:28 2004 +0000
+++ b/src/include/dijkstra.h	Thu Apr 22 14:50:24 2004 +0000
@@ -1,29 +1,5 @@
 // -*- C++ -*-
 
-/* 
- *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
- *
- *Constructor: 
- *
- *Dijkstra(Graph G, LengthMap length)
- *
- *
- *Methods:
- *
- *void run(Node s)
- *
- *T dist(Node v) : After run(s) was run, it returns the distance from s to v. 
- *   Returns T() if v is not reachable from s.
- *
- *Edge pred(Node v) : After run(s) was run, it returns the last 
- *   edge of a shortest s-v path. It is INVALID for s and for 
- *   the nodes not reachable from s.
- *
- *bool reached(Node v) : After run(s) was run, it is true iff v is 
- *   reachable from s
- *
- */
-
 #ifndef HUGO_DIJKSTRA_H
 #define HUGO_DIJKSTRA_H
 
@@ -36,8 +12,6 @@
 
 namespace hugo {
   
-  //Alpar: Changed the order of the parameters
-  
   ///%Dijkstra algorithm class.
 
   ///This class provides an efficient implementation of %Dijkstra algorithm.
@@ -49,17 +23,14 @@
   ///
   ///It is also possible to change the underlying priority heap.
   ///
-  ///\param Graph The graph type the algorithm runs on.
-  ///\param LengthMap This read-only
-  ///EdgeMap
-  ///determines the
-  ///lengths of the edges. It is read once for each edge, so the map
-  ///may involve in relatively time consuming process to compute the edge
-  ///length if it is necessary. The default map type is
-  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
-  ///\param Heap The heap type used by the %Dijkstra
-  ///algorithm. The default
-  ///is using \ref BinHeap "binary heap".
+  ///\param Graph The graph type the algorithm runs on.  
+  ///\param LengthMap This read-only EdgeMap determines the lengths of
+  ///the edges. It is read once for each edge, so the map may involve
+  ///in relatively time consuming process to compute the edge length
+  ///if it is necessary. The default map type is \ref
+  ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
+  ///\param Heap The heap type used by the %Dijkstra algorithm. The
+  ///default is using \ref BinHeap "binary heap".
   
 #ifdef DOXYGEN
   template <typename Graph,
@@ -103,6 +74,7 @@
     ///\warning If node \c v in unreachable from the source the return value
     ///of this funcion is undefined.
     ValueType dist(Node v) const { return distance[v]; }
+
     ///Returns the edges of the shortest path tree.
 
     ///For a node \c v it returns the last edge of the shortest path
@@ -110,6 +82,7 @@
     ///from the source.
     ///\pre \ref run() must be called before using this function.
     Edge pred(Node v) const { return predecessor[v]; }
+
     ///Returns the nodes of the shortest paths.
 
     ///For a node \c v it returns the last but one node of the shortest path
@@ -123,12 +96,14 @@
     ///\pre \ref run() must be called before using this function.
     ///
     const DistMap &distMap() const { return distance;}
+    
     ///Returns a reference to the shortest path tree map.
 
     ///Returns a reference to the NodeMap of the edges of the
     ///shortest path tree.
     ///\pre \ref run() must be called before using this function.
     const PredMap &predMap() const { return predecessor;}
+    
     ///Returns a reference to the map of nodes of  shortest paths.
 
     ///Returns a reference to the NodeMap of the last but one nodes of the
@@ -142,7 +117,6 @@
     ///\warning the source node is reported to be unreached!
     ///\todo Is this what we want?
     ///\pre \ref run() must be called before using this function.
-    ///
     bool reached(Node v) { return G.valid(predecessor[v]); }
     
   };
@@ -152,14 +126,12 @@
   //  IMPLEMENTATIONS
   // **********************************************************************
 
-  ///Runs %Dijkstra algorithm from node the source.
+  ///Runs %Dijkstra algorithm from source node \c s.
 
   ///This method runs the %Dijkstra algorithm from a source node \c s
-  ///in order to
-  ///compute the
-  ///shortest path to each node. The algorithm computes
-  ///- The shortest path tree.
-  ///- The distance of each node from the source.
+  ///in order to compute the shortest path to each node. The algorithm
+  ///computes - The shortest path tree.  - The distance of each node
+  ///from the source.
   template <typename Graph, typename LengthMap,
 	    template<class,class,class> class Heap >
   void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
@@ -168,28 +140,23 @@
     for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
       predecessor.set(u,INVALID);
       pred_node.set(u,INVALID);
-      // If a node is unreacheable, then why should be the dist=0?
-      // distance.set(u,0);
-      //      reach.set(u,false);
     }
     
     typename Graph::NodeMap<int> heap_map(G,-1);
     
     Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
-    
     heap.push(s,0); 
     
-      while ( !heap.empty() ) {
+    while ( !heap.empty() ) {
+      
+      Node v=heap.top(); 
+      ValueType oldvalue=heap[v];
+      heap.pop();
+      distance.set(v, oldvalue);
 	
-	Node v=heap.top(); 
-	ValueType oldvalue=heap[v];
-	heap.pop();
-	distance.set(v, oldvalue);
-	
-	{ //FIXME this bracket is for e to be local
-	  OutEdgeIt e;
-	for(G.first(e, v);
-	    G.valid(e); G.next(e)) {
+      { //FIXME this bracket is for e to be local
+	OutEdgeIt e;
+	for(G.first(e, v); G.valid(e); G.next(e)) {
 	  Node w=G.head(e); 
 	  
 	  switch(heap.state(w)) {
@@ -209,8 +176,8 @@
 	    break;
 	  }
 	}
-      } //FIXME tis bracket
-      }
+      } //FIXME this bracket
+    }
   }
   
 } //END OF NAMESPACE HUGO
diff -r e6a156fc186d -r 259ea2d741a2 src/include/fib_heap.h
--- a/src/include/fib_heap.h	Thu Apr 22 14:11:28 2004 +0000
+++ b/src/include/fib_heap.h	Thu Apr 22 14:50:24 2004 +0000
@@ -1,55 +1,7 @@
 // -*- C++ -*-
-/*
- *template <typename Item, 
- *          typename Prio, 
- *          typename ItemIntMap, 
- *          typename Compare = std::less<Prio> >
- * 
- *constructors:
- *
- *FibHeap(ItemIntMap),   FibHeap(ItemIntMap, Compare)
- *
- *Member functions:
- *
- *int size() : returns the number of elements in the heap
- *
- *bool empty() : true iff size()=0
- *
- *void set(Item, Prio) : calls push(Item, Prio) if Item is not
- *     in the heap, and calls decrease/increase(Item, Prio) otherwise
- *
- *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
- *     mustn't be in the heap.
- *
- *Item top() : returns the Item with least Prio. 
- *     Must be called only if heap is nonempty.
- *
- *Prio prio() : returns the least Prio
- *     Must be called only if heap is nonempty.
- *
- *Prio get(Item) : returns Prio of Item
- *     Must be called only if Item is in heap.
- *
- *void pop() : deletes the Item with least Prio
- *
- *void erase(Item) : deletes Item from the heap if it was already there
- *
- *void decrease(Item, P) : decreases prio of Item to P. 
- *     Item must be in the heap with prio at least P.
- *
- *void increase(Item, P) : sets prio of Item to P. 
- *
- *state_enum state(Item) : returns PRE_HEAP if Item has not been in the 
- *     heap until now, IN_HEAP if it is in the heap at the moment, and 
- *     POST_HEAP otherwise. In the latter case it is possible that Item
- *     will get back to the heap again. 
- *
- *In Fibonacci heaps, increase and erase are not efficient, in case of
- *many calls to these operations, it is better to use bin_heap.
- */
 
-#ifndef FIB_HEAP_H
-#define FIB_HEAP_H
+#ifndef HUGO_FIB_HEAP_H
+#define HUGO_FIB_HEAP_H
 
 ///\file
 ///\brief Fibonacci Heap implementation.
@@ -60,13 +12,44 @@
 
 namespace hugo {
   
-  /// A Fibonacci Heap implementation.
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  /// An implementation of the Fibonacci Heap.
+
+  /**
+     This class implements the \e Fibonacci \e heap data structure. A \e
+     heap is a data structure for storing items with specified priorities,
+     such that finding the item with minimum priority is efficient. In a
+     heap one can change the priority of an item, and to add or erase an
+     item.
+
+     The methods \ref increase and \ref erase are not efficient, in
+     case of many calls to these operations, it is better to use
+     a binary heap.
+     
+     /param Item The type of the items to be stored.  
+     /param Prio The type of the priority of the items.
+     /param ItemIntMap A read and writable Item int map, for the usage of
+     the heap.
+     /param Compare A class for the comparison of the priorities. The
+     default is \c std::less<Prio>.
+
+  */
+
+#ifdef DOXYGEN
+  template <typename Item, 
+	    typename Prio, 
+	    typename ItemIntMap, 
+	    typename Compare>
+#else
+  template <typename Item, 
+	    typename Prio, 
+	    typename ItemIntMap, 
 	    typename Compare = std::less<Prio> >
+#endif
   class FibHeap {
-    
+  public: 
     typedef Prio PrioType;
     
+  private:
     class store;
     
     std::vector<store> container;
@@ -74,7 +57,7 @@
     ItemIntMap &iimap;
     Compare comp;
     int num_items;
-
+    
     ///\todo It is use nowhere
     ///\todo It doesn't conform to the naming conventions.
   public:
@@ -86,18 +69,137 @@
     
   public :
     
-    FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} 
-    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 
+    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
+    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
       iimap(_iimap), comp(_comp), num_items() {}
     
+    ///The number of items stored in the heap.
+
+    /**
+    Returns the number of items stored in the heap.
+    */
+    int size() const { return num_items; }
+
+    ///Checks if the heap stores no items.
     
-    int size() const {
-      return num_items; 
+    /**
+       Returns true iff the heap stores no items.
+    */
+    bool empty() const { return num_items==0; }
+
+    ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
+
+    /**
+       This method calls \ref push(item, value) if \c item is not
+       stored in the heap, and it calls \ref decrease(it, \c value) or
+       \ref increase(it, \c value) otherwise.
+    */
+    void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
+    
+    ///Adds \c item to the heap with priority \c value. 
+    
+    /**
+       Adds \c item to the heap with priority \c value. 
+       \pre \c item must not be stored in the heap. 
+    */
+    void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
+    
+    
+    ///Returns the item having the minimum priority w.r.t.  Compare.
+    
+    /**
+       This method returns the item having the minimum priority w.r.t.  Compare. 
+       \pre The heap must be nonempty.
+    */
+    Item top() const { return container[minimum].name; }
+    
+
+    ///Returns the minimum priority w.r.t.  Compare.
+
+    /**
+       It returns the minimum priority w.r.t.  Compare.
+       \pre The heap must be nonempty.
+    */
+    PrioType prio() const { return container[minimum].prio; }
+    
+
+    ///Returns the priority of \c item.
+
+    /**
+       It returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
+    
+    ///Returns the priority of \c item.
+    
+    /**
+       It returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    const PrioType& operator[](const Item& it) const { 
+      return container[iimap[it]].prio; 
     }
 
 
-    bool empty() const { return num_items==0; }
+    ///Deletes the item with minimum priority w.r.t.  Compare.
 
+    /**
+    This method deletes the item with minimum priority w.r.t. 
+    Compare from the heap.
+    \pre The heap must be non-empty.
+    */
+    void pop();
+
+    ///Deletes \c item from the heap.
+
+    /**
+       This method deletes \c item from the heap, if \c item was already
+       stored in the heap. It is quite inefficient in Fibonacci heaps.
+    */
+    void erase (const Item& item); /*vigyazat: az implementacioban it van*/
+
+    ///Decreases the priority of \c item to \c value.
+
+    /**
+       This method decreases the priority of \c item to \c value.
+       \pre \c item must be stored in the heap with priority at least \c
+       value w.r.t.  Compare.
+    */
+    void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
+
+
+    ///Increases the priority of \c item to \c value.
+
+    /**
+       This method sets the priority of \c item to \c value. Though
+       there is no precondition on the priority of \c item, this
+       method should be used only if one wants to \e increase
+       (w.r.t.  Compare) the priority of \c item, because this
+       method is inefficient.
+    */
+    void increase (Item it, PrioType const value) {
+      erase(it);
+      push(it, value);
+    }
+
+
+    ///Tells if \c item is in, was in, or has not 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 &it);  /*vigyazat: az implementacioban it van*/
+
+
+
+    // **********************************************************************
+    //  IMPLEMENTATIONS
+    // **********************************************************************
+    
 
     void set (Item const it, PrioType const value) {
       int i=iimap[it];
@@ -139,30 +241,6 @@
     }
     
 
-    Item top() const {
-      return container[minimum].name;
-    }
-    
-    
-    PrioType prio() const {
-      return container[minimum].prio;
-    }
-    
-
-
-
-    PrioType& operator[](const Item& it) {
-      return container[iimap[it]].prio;
-    }
-    
-    const PrioType& operator[](const Item& it) const {
-      return container[iimap[it]].prio;
-    }
-
-//     const PrioType get(const Item& it) const {
-//       return container[iimap[it]].prio;
-//     }
-
     void pop() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
@@ -223,12 +301,6 @@
     }
    
 
-    void increase (Item it, PrioType const value) {
-      erase(it);
-      push(it, value);
-    }
-
-
     state_enum state(const Item &it) const {
       int i=iimap[it];
       if( i>=0 ) {