COIN-OR::LEMON - Graph Library

Changeset 1721:c0f5e8401373 in lemon-0.x


Ignore:
Timestamp:
10/14/05 12:52:15 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2248
Message:

Named parameter for heap and cross ref
It needs some redesign

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r1710 r1721  
    5151    //The type of the length of the edges.
    5252    typedef typename LM::Value Value;
     53    /// The cross reference type used by heap.
     54
     55    /// The cross reference type used by heap.
     56    /// Usually it is \c Graph::NodeMap<int>.
     57    typedef typename Graph::template NodeMap<int> HeapCrossRef;
     58    ///Instantiates a HeapCrossRef.
     59
     60    ///This function instantiates a \ref HeapCrossRef.
     61    /// \param G is the graph, to which we would like to define the
     62    /// HeapCrossRef.
     63    /// \todo The graph alone may be insufficient for the initialization
     64    static HeapCrossRef *createHeapCrossRef(const GR &G)
     65    {
     66      return new HeapCrossRef(G);
     67    }
     68   
    5369    ///The heap type used by Dijkstra algorithm.
    5470
     
    6076                    typename GR::template NodeMap<int>,
    6177                    std::less<Value> > Heap;
     78
     79    static Heap *createHeap(HeapCrossRef& R)
     80    {
     81      return new Heap(R);
     82    }
    6283
    6384    ///\brief The type of the map that stores the last
     
    196217    ///The type of the map that stores the dists of the nodes.
    197218    typedef typename TR::DistMap DistMap;
     219    ///The cross reference type used for the current heap.
     220    typedef typename TR::HeapCrossRef HeapCrossRef;
    198221    ///The heap type used by the dijkstra algorithm.
    199222    typedef typename TR::Heap Heap;
     
    215238    ///Indicates if \ref _processed is locally allocated (\c true) or not.
    216239    bool local_processed;
     240    ///Pointer to the heap cross references.
     241    HeapCrossRef *_heap_cross_ref;
     242    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
     243    bool local_heap_cross_ref;
     244    ///Pointer to the heap.
     245    Heap *_heap;
     246    ///Indicates if \ref _heap is locally allocated (\c true) or not.
     247    bool local_heap;
    217248
    218249    ///Creates the maps if necessary.
     
    233264        local_processed = true;
    234265        _processed = Traits::createProcessedMap(*G);
     266      }
     267      if (!_heap_cross_ref) {
     268        local_heap_cross_ref = true;
     269        _heap_cross_ref = Traits::createHeapCrossRef(*G);
     270      }
     271      if (!_heap) {
     272        local_heap = true;
     273        _heap = Traits::createHeap(*_heap_cross_ref);
    235274      }
    236275    }
     
    316355      typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create;
    317356    };
     357
     358    template <class H, class CR>
     359    struct DefHeapTraits : public Traits {
     360      typedef CR HeapCrossRef;
     361      typedef H Heap;
     362      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
     363        return new HeapCrossRef(G);
     364      }
     365      static Heap *createHeap(HeapCrossRef &R)
     366      {
     367        return new Heap(R);
     368      }
     369    };
     370    ///\ref named-templ-param "Named parameter" for setting heap and cross
     371    ///reference type
     372
     373    ///\ref named-templ-param "Named parameter" for setting heap and cross
     374    ///reference type
     375    ///
     376    template <class H, class CR = typename Graph::template NodeMap<int> >
     377    struct DefHeap
     378      : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > {
     379      typedef Dijkstra< Graph,  LengthMap, DefHeapTraits<H, CR> > Create;
     380    };
    318381   
    319382    ///@}
    320383
    321384
    322   private:
    323     typename Graph::template NodeMap<int> _heap_map;
    324     Heap _heap;
    325385  protected:
    326386
     
    338398      _dist(NULL), local_dist(false),
    339399      _processed(NULL), local_processed(false),
    340       _heap_map(*G,-1),_heap(_heap_map)
     400      _heap_cross_ref(NULL), local_heap_cross_ref(false),
     401      _heap(NULL), local_heap(false)
    341402    { }
    342403   
     
    347408      if(local_dist) delete _dist;
    348409      if(local_processed) delete _processed;
     410      if(local_heap_cross_ref) delete _heap_cross_ref;
     411      if(local_heap) delete _heap;
    349412    }
    350413
     
    417480    ///Initializes the internal data structures.
    418481    ///
    419     ///\todo _heap_map's type could also be in the traits class.
    420     ///\todo The heaps should be able to make themselves empty directly.
    421482    void init()
    422483    {
    423484      create_maps();
    424       while(!_heap.empty()) _heap.pop();
     485      _heap->clear();
    425486      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    426487        _pred->set(u,INVALID);
    427488        _processed->set(u,false);
    428         _heap_map.set(u,Heap::PRE_HEAP);
     489        _heap_cross_ref->set(u,Heap::PRE_HEAP);
    429490      }
    430491    }
     
    441502    void addSource(Node s,Value dst=0)
    442503    {
    443       if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
    444       else if(_heap[s]<dst) {
    445         _heap.push(s,dst);
     504      if(_heap->state(s) != Heap::IN_HEAP) {
     505        _heap->push(s,dst);
     506      } else if((*_heap)[s]<dst) {
     507        _heap->push(s,dst);
    446508        _pred->set(s,INVALID);
    447509      }
     
    457519    Node processNextNode()
    458520    {
    459       Node v=_heap.top();
    460       Value oldvalue=_heap[v];
    461       _heap.pop();
     521      Node v=_heap->top();
     522      Value oldvalue=_heap->prio();
     523      _heap->pop();
    462524      finalizeNodeData(v,oldvalue);
    463525     
    464526      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
    465527        Node w=G->target(e);
    466         switch(_heap.state(w)) {
     528        switch(_heap->state(w)) {
    467529        case Heap::PRE_HEAP:
    468           _heap.push(w,oldvalue+(*length)[e]);
     530          _heap->push(w,oldvalue+(*length)[e]);
    469531          _pred->set(w,e);
    470532          break;
    471533        case Heap::IN_HEAP:
    472           if ( oldvalue+(*length)[e] < _heap[w] ) {
    473             _heap.decrease(w, oldvalue+(*length)[e]);
     534          if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
     535            _heap->decrease(w, oldvalue+(*length)[e]);
    474536            _pred->set(w,e);
    475537          }
     
    490552    Node nextNode()
    491553    {
    492       return _heap.empty()?_heap.top():INVALID;
     554      return _heap->empty()?_heap->top():INVALID;
    493555    }
    494556 
     
    498560    ///Returns \c false if there are nodes
    499561    ///to be processed in the priority heap
    500     bool emptyQueue() { return _heap.empty(); }
     562    bool emptyQueue() { return _heap->empty(); }
    501563    ///Returns the number of the nodes to be processed in the priority heap
    502564
    503565    ///Returns the number of the nodes to be processed in the priority heap
    504566    ///
    505     int queueSize() { return _heap.size(); }
     567    int queueSize() { return _heap->size(); }
    506568   
    507569    ///Executes the algorithm.
     
    521583    void start()
    522584    {
    523       while ( !_heap.empty() ) processNextNode();
     585      while ( !_heap->empty() ) processNextNode();
    524586    }
    525587   
     
    540602    void start(Node dest)
    541603    {
    542       while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
    543       if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
     604      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
     605      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    544606    }
    545607   
     
    556618    void start(const NodeBoolMap &nm)
    557619    {
    558       while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
    559       if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
     620      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
     621      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    560622    }
    561623   
     
    684746    ///\pre \ref run() must be called before using this function.
    685747    ///
    686     bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
     748    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
    687749   
    688750    ///@}
     
    712774    ///The heap type used by Dijkstra algorithm.
    713775
     776    /// The cross reference type used by heap.
     777
     778    /// The cross reference type used by heap.
     779    /// Usually it is \c Graph::NodeMap<int>.
     780    typedef typename Graph::template NodeMap<int> HeapCrossRef;
     781    ///Instantiates a HeapCrossRef.
     782
     783    ///This function instantiates a \ref HeapCrossRef.
     784    /// \param G is the graph, to which we would like to define the
     785    /// HeapCrossRef.
     786    /// \todo The graph alone may be insufficient for the initialization
     787    static HeapCrossRef *createHeapCrossRef(const GR &G)
     788    {
     789      return new HeapCrossRef(G);
     790    }
     791   
     792    ///The heap type used by Dijkstra algorithm.
     793
    714794    ///The heap type used by Dijkstra algorithm.
    715795    ///
    716796    ///\sa BinHeap
    717797    ///\sa Dijkstra
    718     typedef BinHeap<typename Graph::Node,
    719                     typename LM::Value,
     798    typedef BinHeap<typename Graph::Node, typename LM::Value,
    720799                    typename GR::template NodeMap<int>,
    721800                    std::less<Value> > Heap;
     801
     802    static Heap *createHeap(HeapCrossRef& R)
     803    {
     804      return new Heap(R);
     805    }
    722806
    723807    ///\brief The type of the map that stores the last
     
    808892    ///Pointer to the map of predecessors edges.
    809893    void *_pred;
    810 //     ///Pointer to the map of predecessors nodes.
    811 //     void *_predNode;
    812894    ///Pointer to the map of distances.
    813895    void *_dist;
     
    821903    /// all of the attributes to default values (0, INVALID).
    822904    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
    823 //                         _predNode(0),
    824905                           _dist(0), _source(INVALID) {}
    825906
     
    834915    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
    835916      _g((void *)&g), _length((void *)&l), _pred(0),
    836 //       _predNode(0),
    837917      _dist(0), _source(s) {}
    838918
     
    856936  ///
    857937  /// It does not have own \ref run method. When its \ref run method is called
    858   /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
    859   /// method of it.
     938  /// it initiates a plain \ref Dijkstra class, and calls the \ref
     939  /// Dijkstra::run method of it.
    860940  template<class TR>
    861941  class DijkstraWizard : public TR
     
    881961    ///edges of the shortest paths.
    882962    typedef typename TR::PredMap PredMap;
    883 //     ///\brief The type of the map that stores the last but one
    884 //     ///nodes of the shortest paths.
    885 //     typedef typename TR::PredNodeMap PredNodeMap;
    886963    ///The type of the map that stores the dists of the nodes.
    887964    typedef typename TR::DistMap DistMap;
    888 
    889965    ///The heap type used by the dijkstra algorithm.
    890966    typedef typename TR::Heap Heap;
     
    915991        dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
    916992      if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
    917 //       if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
    918993      if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
    919994      dij.run(Base::_source);
     
    9501025    }
    9511026   
    952 
    953 //     template<class T>
    954 //     struct DefPredNodeMapBase : public Base {
    955 //       typedef T PredNodeMap;
    956 //       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
    957 //       DefPredNodeMapBase(const TR &b) : TR(b) {}
    958 //     };
    959    
    960 //     ///\brief \ref named-templ-param "Named parameter"
    961 //     ///function for setting PredNodeMap type
    962 //     ///
    963 //     /// \ref named-templ-param "Named parameter"
    964 //     ///function for setting PredNodeMap type
    965 //     ///
    966 //     template<class T>
    967 //     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
    968 //     {
    969 //       Base::_predNode=(void *)&t;
    970 //       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
    971 //     }
    972    
    9731027    template<class T>
    9741028    struct DefDistMapBase : public Base {
Note: See TracChangeset for help on using the changeset viewer.