COIN-OR::LEMON - Graph Library

Changeset 1116:f97e1cbbd453 in lemon-0.x


Ignore:
Timestamp:
02/02/05 12:54:55 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1515
Message:
  • More or less follows the new naming convetions
  • New implementation for dijkstra();
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/dijkstra.h

    r1043 r1116  
    144144            typename TR=DijkstraDefaultTraits<GR,LM> >
    145145#endif
    146   class Dijkstra{
     146  class Dijkstra {
    147147  public:
    148148    typedef TR Traits;
     
    214214   
    215215  public :
    216 
     216 
    217217    template <class T>
    218     struct SetPredMapTraits : public Traits {
     218    struct DefPredMapTraits : public Traits {
    219219      typedef T PredMap;
    220220      ///\todo An exception should be thrown.
     
    232232    ///
    233233    template <class T>
    234     class SetPredMap : public Dijkstra< Graph,
     234    class DefPredMap : public Dijkstra< Graph,
    235235                                        LengthMap,
    236                                         SetPredMapTraits<T> > { };
     236                                        DefPredMapTraits<T> > { };
    237237   
    238238    template <class T>
    239     struct SetPredNodeMapTraits : public Traits {
     239    struct DefPredNodeMapTraits : public Traits {
    240240      typedef T PredNodeMap;
    241241      ///\todo An exception should be thrown.
     
    253253    ///
    254254    template <class T>
    255     class SetPredNodeMap : public Dijkstra< Graph,
     255    class DefPredNodeMap : public Dijkstra< Graph,
    256256                                            LengthMap,
    257                                             SetPredNodeMapTraits<T> > { };
     257                                            DefPredNodeMapTraits<T> > { };
    258258   
    259259    template <class T>
    260     struct SetDistMapTraits : public Traits {
     260    struct DefDistMapTraits : public Traits {
    261261      typedef T DistMap;
    262262      ///\todo An exception should be thrown.
     
    274274    ///
    275275    template <class T>
    276     class SetDistMap : public Dijkstra< Graph,
     276    class DefDistMap : public Dijkstra< Graph,
    277277                                        LengthMap,
    278                                         SetDistMapTraits<T> > { };
     278                                        DefDistMapTraits<T> > { };
    279279   
    280280    ///Constructor.
     
    301301    ///Sets the length map.
    302302    ///\return <tt> (*this) </tt>
    303     Dijkstra &setLengthMap(const LengthMap &m)
     303    Dijkstra &lengthMap(const LengthMap &m)
    304304    {
    305305      length = &m;
     
    314314    ///automatically allocated map, of course.
    315315    ///\return <tt> (*this) </tt>
    316     Dijkstra &setPredMap(PredMap &m)
     316    Dijkstra &predMap(PredMap &m)
    317317    {
    318318      if(local_predecessor) {
     
    331331    ///automatically allocated map, of course.
    332332    ///\return <tt> (*this) </tt>
    333     Dijkstra &setPredNodeMap(PredNodeMap &m)
     333    Dijkstra &predNodeMap(PredNodeMap &m)
    334334    {
    335335      if(local_pred_node) {
     
    348348    ///automatically allocated map, of course.
    349349    ///\return <tt> (*this) </tt>
    350     Dijkstra &setDistMap(DistMap &m)
     350    Dijkstra &distMap(DistMap &m)
    351351    {
    352352      if(local_distance) {
     
    474474  };
    475475
     476  template<class GR,class LM>
     477  class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
     478  {
     479
     480    typedef DijkstraDefaultTraits<GR,LM> Base;
     481  protected:
     482    /// Pointer to the underlying graph.
     483    void *_g;
     484    /// Pointer to the length map
     485    void *_length;
     486    ///Pointer to the map of predecessors edges.
     487    void *_pred;
     488    ///Pointer to the map of predecessors nodes.
     489    void *_predNode;
     490    ///Pointer to the map of distances.
     491    void *_dist;
     492    ///Pointer to the source node.
     493    void *_source;
     494
     495    typedef typename Base::Graph::Node Node;
     496
     497    public:
     498    DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
     499                       _dist(0), _source(INVALID) {}
     500
     501    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
     502      _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
     503                  _dist(0), _source((void *)&s) {}
     504
     505  };
     506 
    476507  ///\e
    477508
     
    479510  ///
    480511  template<class TR>
    481   class _Dijkstra
     512  class DijkstraWizard : public TR
    482513  {
    483     typedef TR Traits;
     514    typedef TR Base;
    484515
    485516    ///The type of the underlying graph.
     
    509540    ///The heap type used by the dijkstra algorithm.
    510541    typedef typename TR::Heap Heap;
    511 
    512     /// Pointer to the underlying graph.
    513     const Graph *G;
    514     /// Pointer to the length map
    515     const LengthMap *length;
    516     ///Pointer to the map of predecessors edges.
    517     PredMap *predecessor;
    518     ///Pointer to the map of predecessors nodes.
    519     PredNodeMap *pred_node;
    520     ///Pointer to the map of distances.
    521     DistMap *distance;
    522    
    523     Node source;
    524    
    525542public:
    526     _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0),
    527                   distance(0), source(INVALID) {}
    528 
    529     _Dijkstra(const Graph &g,const LengthMap &l, Node s) :
    530       G(&g), length(&l), predecessor(0), pred_node(0),
    531                   distance(0), source(s) {}
    532 
    533     ~_Dijkstra()
    534     {
    535       Dijkstra<Graph,LengthMap,TR> Dij(*G,*length);
    536       if(predecessor) Dij.setPredMap(*predecessor);
    537       if(pred_node) Dij.setPredNodeMap(*pred_node);
    538       if(distance) Dij.setDistMap(*distance);
    539       Dij.run(source);
     543    DijkstraWizard() : TR() {}
     544
     545    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
     546      TR(g,l,s) {}
     547
     548    DijkstraWizard(const TR &b) : TR(b) {}
     549
     550    ~DijkstraWizard() {}
     551
     552    ///\e
     553    void run()
     554    {
     555      Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
     556      if(_pred) Dij.predMap(*(PredMap*)_pred);
     557      if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
     558      if(_dist) Dij.distMap(*(DistMap*)_dist);
     559      Dij.run(*(Node*)_source);
     560    }
     561
     562    ///\e
     563    void run(Node s)
     564    {
     565      _source=(void *)&s;
     566      run();
    540567    }
    541568
    542569    template<class T>
    543     struct SetPredMapTraits : public Traits {typedef T PredMap;};
     570    struct DefPredMapBase : public Base {
     571      typedef T PredMap;
     572      static PredMap *createPredMap(const Graph &G) {};
     573    };
    544574   
    545575    ///\e
    546576    template<class T>
    547     _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t)
    548     {
    549       _Dijkstra<SetPredMapTraits<T> > r;
    550       r.G=G;
    551       r.length=length;
    552       r.predecessor=&t;
    553       r.pred_node=pred_node;
    554       r.distance=distance;
    555       r.source=source;
    556       return r;
    557     }
    558    
     577    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
     578    {
     579      _pred=(void *)&t;
     580      return DijkstraWizard<DefPredMapBase<T> >(*this);
     581    }
     582   
     583
    559584    template<class T>
    560     struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;};
     585    struct DefPredNodeMapBase : public Base {
     586      typedef T PredNodeMap;
     587      static PredNodeMap *createPredNodeMap(const Graph &G) {};
     588    };
     589   
    561590    ///\e
    562591    template<class T>
    563     _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t)
    564     {
    565       _Dijkstra<SetPredNodeMapTraits<T> > r;
    566       r.G=G;
    567       r.length=length;
    568       r.predecessor=predecessor;
    569       r.pred_node=&t;
    570       r.distance=distance;
    571       r.source=source;
    572       return r;
    573     }
    574    
     592    DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
     593    {
     594      _predNode=(void *)&t;
     595      return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
     596    }
     597   
    575598    template<class T>
    576     struct SetDistMapTraits : public Traits {typedef T DistMap;};
     599    struct DefDistMapBase : public Base {
     600      typedef T DistMap;
     601      static DistMap *createDistMap(const Graph &G) {};
     602    };
     603   
    577604    ///\e
    578605    template<class T>
    579     _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t)
    580     {
    581       _Dijkstra<SetPredMapTraits<T> > r;
    582       r.G=G;
    583       r.length=length;
    584       r.predecessor=predecessor;
    585       r.pred_node=pred_node;
    586       r.distance=&t;
    587       r.source=source;
    588       return r;
    589     }
    590    
    591     ///\e
    592     _Dijkstra<TR> &setSource(Node s)
    593     {
    594       source=s;
     606    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
     607    {
     608      _dist=(void *)&t;
     609      return DijkstraWizard<DefDistMapBase<T> >(*this);
     610    }
     611
     612    ///\e
     613    DijkstraWizard<TR> &setSource(Node s)
     614    {
     615      source=(void *)&s;
    595616      return *this;
    596617    }
     
    603624  ///
    604625  template<class GR, class LM>
    605   _Dijkstra<DijkstraDefaultTraits<GR,LM> >
    606   dijkstra(const GR &g,const LM &l,typename GR::Node s)
     626  DijkstraWizard<DijkstraWizardBase<GR,LM> >
     627  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
    607628  {
    608     return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);
     629    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
    609630  }
    610631
Note: See TracChangeset for help on using the changeset viewer.