COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 373:259ea2d741a2 in lemon-0.x for src


Ignore:
Timestamp:
04/22/04 16:50:24 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@503
Message:

Changes in the documentation.

Location:
src/include
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/include/dijkstra.h

    r335 r373  
    11// -*- C++ -*-
    2 
    3 /*
    4  *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
    5  *
    6  *Constructor:
    7  *
    8  *Dijkstra(Graph G, LengthMap length)
    9  *
    10  *
    11  *Methods:
    12  *
    13  *void run(Node s)
    14  *
    15  *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
    16  *   Returns T() if v is not reachable from s.
    17  *
    18  *Edge pred(Node v) : After run(s) was run, it returns the last
    19  *   edge of a shortest s-v path. It is INVALID for s and for
    20  *   the nodes not reachable from s.
    21  *
    22  *bool reached(Node v) : After run(s) was run, it is true iff v is
    23  *   reachable from s
    24  *
    25  */
    262
    273#ifndef HUGO_DIJKSTRA_H
    … …  
    3713namespace hugo {
    3814 
    39   //Alpar: Changed the order of the parameters
    40  
    4115  ///%Dijkstra algorithm class.
    4216
    … …  
    5024  ///It is also possible to change the underlying priority heap.
    5125  ///
    52   ///\param Graph The graph type the algorithm runs on.
    53   ///\param LengthMap This read-only
    54   ///EdgeMap
    55   ///determines the
    56   ///lengths of the edges. It is read once for each edge, so the map
    57   ///may involve in relatively time consuming process to compute the edge
    58   ///length if it is necessary. The default map type is
    59   ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
    60   ///\param Heap The heap type used by the %Dijkstra
    61   ///algorithm. The default
    62   ///is using \ref BinHeap "binary heap".
     26  ///\param Graph The graph type the algorithm runs on. 
     27  ///\param LengthMap This read-only EdgeMap determines the lengths of
     28  ///the edges. It is read once for each edge, so the map may involve
     29  ///in relatively time consuming process to compute the edge length
     30  ///if it is necessary. The default map type is \ref
     31  ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
     32  ///\param Heap The heap type used by the %Dijkstra algorithm. The
     33  ///default is using \ref BinHeap "binary heap".
    6334 
    6435#ifdef DOXYGEN
    … …  
    10475    ///of this funcion is undefined.
    10576    ValueType dist(Node v) const { return distance[v]; }
     77
    10678    ///Returns the edges of the shortest path tree.
    10779
    … …  
    11183    ///\pre \ref run() must be called before using this function.
    11284    Edge pred(Node v) const { return predecessor[v]; }
     85
    11386    ///Returns the nodes of the shortest paths.
    11487
    … …  
    12497    ///
    12598    const DistMap &distMap() const { return distance;}
     99   
    126100    ///Returns a reference to the shortest path tree map.
    127101
    … …  
    130104    ///\pre \ref run() must be called before using this function.
    131105    const PredMap &predMap() const { return predecessor;}
     106   
    132107    ///Returns a reference to the map of nodes of  shortest paths.
    133108
    … …  
    143118    ///\todo Is this what we want?
    144119    ///\pre \ref run() must be called before using this function.
    145     ///
    146120    bool reached(Node v) { return G.valid(predecessor[v]); }
    147121   
    … …  
    153127  // **********************************************************************
    154128
    155   ///Runs %Dijkstra algorithm from node the source.
     129  ///Runs %Dijkstra algorithm from source node \c s.
    156130
    157131  ///This method runs the %Dijkstra algorithm from a source node \c s
    158   ///in order to
    159   ///compute the
    160   ///shortest path to each node. The algorithm computes
    161   ///- The shortest path tree.
    162   ///- The distance of each node from the source.
     132  ///in order to compute the shortest path to each node. The algorithm
     133  ///computes - The shortest path tree.  - The distance of each node
     134  ///from the source.
    163135  template <typename Graph, typename LengthMap,
    164136            template<class,class,class> class Heap >
    … …  
    169141      predecessor.set(u,INVALID);
    170142      pred_node.set(u,INVALID);
    171       // If a node is unreacheable, then why should be the dist=0?
    172       // distance.set(u,0);
    173       //      reach.set(u,false);
    174143    }
    175144   
    … …  
    177146   
    178147    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
    179    
    180148    heap.push(s,0);
    181149   
    182       while ( !heap.empty() ) {
     150    while ( !heap.empty() ) {
     151     
     152      Node v=heap.top();
     153      ValueType oldvalue=heap[v];
     154      heap.pop();
     155      distance.set(v, oldvalue);
    183156       
    184         Node v=heap.top();
    185         ValueType oldvalue=heap[v];
    186         heap.pop();
    187         distance.set(v, oldvalue);
    188        
    189         { //FIXME this bracket is for e to be local
    190           OutEdgeIt e;
    191         for(G.first(e, v);
    192             G.valid(e); G.next(e)) {
     157      { //FIXME this bracket is for e to be local
     158        OutEdgeIt e;
     159        for(G.first(e, v); G.valid(e); G.next(e)) {
    193160          Node w=G.head(e);
    194161         
    … …  
    210177          }
    211178        }
    212       } //FIXME tis bracket
    213       }
     179      } //FIXME this bracket
     180    }
    214181  }
    215182 

  • src/include/fib_heap.h

    r255 r373  
    11// -*- C++ -*-
    2 /*
    3  *template <typename Item,
    4  *          typename Prio,
    5  *          typename ItemIntMap,
    6  *          typename Compare = std::less<Prio> >
    7  *
    8  *constructors:
    9  *
    10  *FibHeap(ItemIntMap),   FibHeap(ItemIntMap, Compare)
    11  *
    12  *Member functions:
    13  *
    14  *int size() : returns the number of elements in the heap
    15  *
    16  *bool empty() : true iff size()=0
    17  *
    18  *void set(Item, Prio) : calls push(Item, Prio) if Item is not
    19  *     in the heap, and calls decrease/increase(Item, Prio) otherwise
    20  *
    21  *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
    22  *     mustn't be in the heap.
    23  *
    24  *Item top() : returns the Item with least Prio.
    25  *     Must be called only if heap is nonempty.
    26  *
    27  *Prio prio() : returns the least Prio
    28  *     Must be called only if heap is nonempty.
    29  *
    30  *Prio get(Item) : returns Prio of Item
    31  *     Must be called only if Item is in heap.
    32  *
    33  *void pop() : deletes the Item with least Prio
    34  *
    35  *void erase(Item) : deletes Item from the heap if it was already there
    36  *
    37  *void decrease(Item, P) : decreases prio of Item to P.
    38  *     Item must be in the heap with prio at least P.
    39  *
    40  *void increase(Item, P) : sets prio of Item to P.
    41  *
    42  *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
    43  *     heap until now, IN_HEAP if it is in the heap at the moment, and
    44  *     POST_HEAP otherwise. In the latter case it is possible that Item
    45  *     will get back to the heap again.
    46  *
    47  *In Fibonacci heaps, increase and erase are not efficient, in case of
    48  *many calls to these operations, it is better to use bin_heap.
    49  */
    50 
    51 #ifndef FIB_HEAP_H
    52 #define FIB_HEAP_H
     2
     3#ifndef HUGO_FIB_HEAP_H
     4#define HUGO_FIB_HEAP_H
    535
    546///\file
    … …  
    6113namespace hugo {
    6214 
    63   /// A Fibonacci Heap implementation.
    64   template <typename Item, typename Prio, typename ItemIntMap,
     15  /// An implementation of the Fibonacci Heap.
     16
     17  /**
     18     This class implements the \e Fibonacci \e heap data structure. A \e
     19     heap is a data structure for storing items with specified priorities,
     20     such that finding the item with minimum priority is efficient. In a
     21     heap one can change the priority of an item, and to add or erase an
     22     item.
     23
     24     The methods \ref increase and \ref erase are not efficient, in
     25     case of many calls to these operations, it is better to use
     26     a binary heap.
     27     
     28     /param Item The type of the items to be stored. 
     29     /param Prio The type of the priority of the items.
     30     /param ItemIntMap A read and writable Item int map, for the usage of
     31     the heap.
     32     /param Compare A class for the comparison of the priorities. The
     33     default is \c std::less<Prio>.
     34
     35  */
     36
     37#ifdef DOXYGEN
     38  template <typename Item,
     39            typename Prio,
     40            typename ItemIntMap,
     41            typename Compare>
     42#else
     43  template <typename Item,
     44            typename Prio,
     45            typename ItemIntMap,
    6546            typename Compare = std::less<Prio> >
     47#endif
    6648  class FibHeap {
    67    
     49  public:
    6850    typedef Prio PrioType;
    6951   
     52  private:
    7053    class store;
    7154   
    … …  
    7558    Compare comp;
    7659    int num_items;
    77 
     60   
    7861    ///\todo It is use nowhere
    7962    ///\todo It doesn't conform to the naming conventions.
    … …  
    8770  public :
    8871   
    89     FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
    90     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
     72    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
     73    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
    9174      iimap(_iimap), comp(_comp), num_items() {}
    9275   
    93    
    94     int size() const {
    95       return num_items;
    96     }
    97 
    98 
     76    ///The number of items stored in the heap.
     77
     78    /**
     79    Returns the number of items stored in the heap.
     80    */
     81    int size() const { return num_items; }
     82
     83    ///Checks if the heap stores no items.
     84   
     85    /**
     86       Returns true iff the heap stores no items.
     87    */
    9988    bool empty() const { return num_items==0; }
    10089
     90    ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
     91
     92    /**
     93       This method calls \ref push(item, value) if \c item is not
     94       stored in the heap, and it calls \ref decrease(it, \c value) or
     95       \ref increase(it, \c value) otherwise.
     96    */
     97    void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
     98   
     99    ///Adds \c item to the heap with priority \c value.
     100   
     101    /**
     102       Adds \c item to the heap with priority \c value.
     103       \pre \c item must not be stored in the heap.
     104    */
     105    void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
     106   
     107   
     108    ///Returns the item having the minimum priority w.r.t.  Compare.
     109   
     110    /**
     111       This method returns the item having the minimum priority w.r.t.  Compare.
     112       \pre The heap must be nonempty.
     113    */
     114    Item top() const { return container[minimum].name; }
     115   
     116
     117    ///Returns the minimum priority w.r.t.  Compare.
     118
     119    /**
     120       It returns the minimum priority w.r.t.  Compare.
     121       \pre The heap must be nonempty.
     122    */
     123    PrioType prio() const { return container[minimum].prio; }
     124   
     125
     126    ///Returns the priority of \c item.
     127
     128    /**
     129       It returns the priority of \c item.
     130       \pre \c item must be in the heap.
     131    */
     132    PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
     133   
     134    ///Returns the priority of \c item.
     135   
     136    /**
     137       It returns the priority of \c item.
     138       \pre \c item must be in the heap.
     139    */
     140    const PrioType& operator[](const Item& it) const {
     141      return container[iimap[it]].prio;
     142    }
     143
     144
     145    ///Deletes the item with minimum priority w.r.t.  Compare.
     146
     147    /**
     148    This method deletes the item with minimum priority w.r.t.
     149    Compare from the heap.
     150    \pre The heap must be non-empty.
     151    */
     152    void pop();
     153
     154    ///Deletes \c item from the heap.
     155
     156    /**
     157       This method deletes \c item from the heap, if \c item was already
     158       stored in the heap. It is quite inefficient in Fibonacci heaps.
     159    */
     160    void erase (const Item& item); /*vigyazat: az implementacioban it van*/
     161
     162    ///Decreases the priority of \c item to \c value.
     163
     164    /**
     165       This method decreases the priority of \c item to \c value.
     166       \pre \c item must be stored in the heap with priority at least \c
     167       value w.r.t.  Compare.
     168    */
     169    void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
     170
     171
     172    ///Increases the priority of \c item to \c value.
     173
     174    /**
     175       This method sets the priority of \c item to \c value. Though
     176       there is no precondition on the priority of \c item, this
     177       method should be used only if one wants to \e increase
     178       (w.r.t.  Compare) the priority of \c item, because this
     179       method is inefficient.
     180    */
     181    void increase (Item it, PrioType const value) {
     182      erase(it);
     183      push(it, value);
     184    }
     185
     186
     187    ///Tells if \c item is in, was in, or has not been in the heap.
     188
     189    /**
     190       This method returns PRE_HEAP if \c item has never been in the
     191       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     192       otherwise. In the latter case it is possible that \c item will
     193       get back to the heap again.
     194    */
     195    state_enum state(const Item &it);  /*vigyazat: az implementacioban it van*/
     196
     197
     198
     199    // **********************************************************************
     200    //  IMPLEMENTATIONS
     201    // **********************************************************************
     202   
    101203
    102204    void set (Item const it, PrioType const value) {
    … …  
    139241    }
    140242   
    141 
    142     Item top() const {
    143       return container[minimum].name;
    144     }
    145    
    146    
    147     PrioType prio() const {
    148       return container[minimum].prio;
    149     }
    150    
    151 
    152 
    153 
    154     PrioType& operator[](const Item& it) {
    155       return container[iimap[it]].prio;
    156     }
    157    
    158     const PrioType& operator[](const Item& it) const {
    159       return container[iimap[it]].prio;
    160     }
    161 
    162 //     const PrioType get(const Item& it) const {
    163 //       return container[iimap[it]].prio;
    164 //     }
    165243
    166244    void pop() {
    … …  
    224302   
    225303
    226     void increase (Item it, PrioType const value) {
    227       erase(it);
    228       push(it, value);
    229     }
    230 
    231 
    232304    state_enum state(const Item &it) const {
    233305      int i=iimap[it];
Note: See TracChangeset for help on using the changeset viewer.