COIN-OR::LEMON - Graph Library

Changeset 953:d9c115e2eeaf in lemon-0.x


Ignore:
Timestamp:
11/01/04 18:57:19 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1333
Message:
  • Named parameters and traits for Dijkstra (in src/work/alpar/dijkstra.h to be swithced to src/lemon)
  • doc/named-param.dox: Doxygen page for named parameters.
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • doc/Doxyfile

    r939 r953  
    426426INPUT                  = mainpage.dox \
    427427                         graphs.dox \
     428                         named-param.dox \
    428429                         maps.dox \
    429430                         coding_style.dox \
  • src/work/alpar/dijkstra.h

    r952 r953  
    2222///\brief Dijkstra algorithm.
    2323
     24#include <lemon/list_graph.h>
    2425#include <lemon/bin_heap.h>
    2526#include <lemon/invalid.h>
     
    3031/// @{
    3132
     33  template<class GR, class LM>
     34  struct DijkstraDefaultTraits
     35  {
     36    ///\e
     37    typedef GR Graph;
     38    ///\e
     39    typedef typename Graph::Node Node;
     40    ///\e
     41    typedef typename Graph::Edge Edge;
     42    ///The type of the map that stores the edge lengths.
     43
     44    ///It must meet the \ref ReadMap concept.
     45    ///
     46    typedef LM LengthMap;
     47    ///The type of the length of the edges.
     48    typedef typename LM::ValueType ValueType;
     49    ///The heap type used by the dijkstra algorithm.
     50    typedef BinHeap<typename Graph::Node,
     51                    typename LM::ValueType,
     52                    typename GR::template NodeMap<int>,
     53                    std::less<ValueType> > Heap;
     54
     55    ///\brief The type of the map that stores the last
     56    ///edges of the shortest paths.
     57    ///
     58    ///It must meet the \ref WriteMap concept.
     59    ///
     60    typedef typename Graph::template NodeMap<Edge> PredMap;
     61    ///
     62 
     63    ///\todo Please document...
     64    ///
     65    static PredMap *createPredMap(const Graph &G)
     66    {
     67      return new PredMap(G);
     68    }
     69    ///\brief The type of the map that stores the last but one
     70    ///nodes of the shortest paths.
     71    ///
     72    ///It must meet the \ref WriteMap concept.
     73    ///
     74    typedef typename Graph::template NodeMap<Node> PredNodeMap;
     75    ///
     76 
     77    ///\todo Please document...
     78    ///
     79    static PredNodeMap *createPredNodeMap(const Graph &G)
     80    {
     81      return new PredNodeMap(G);
     82    }
     83    ///The type of the map that stores the dists of the nodes.
     84 
     85    ///It must meet the \ref WriteMap concept.
     86    ///
     87    typedef typename Graph::template NodeMap<ValueType> DistMap;
     88    ///
     89 
     90    ///\todo Please document...
     91    ///
     92    static DistMap *createDistMap(const Graph &G)
     93    {
     94      return new DistMap(G);
     95    }
     96  };
     97 
    3298  ///%Dijkstra algorithm class.
    3399
     
    42108  ///It is also possible to change the underlying priority heap.
    43109  ///
    44   ///\param GR The graph type the algorithm runs on.
     110  ///\param GR The graph type the algorithm runs on. The default value is
     111  ///\ref ListGraph
    45112  ///\param LM This read-only
    46113  ///EdgeMap
     
    62129  template <typename GR,
    63130            typename LM,
    64             typename Heap>
     131            typename TR>
    65132#else
    66   template <typename GR,
     133  template <typename GR=ListGraph,
    67134            typename LM=typename GR::template EdgeMap<int>,
    68             template <class,class,class,class> class Heap = BinHeap >
     135            typename TR=DijkstraDefaultTraits<GR,LM> >
    69136#endif
    70137  class Dijkstra{
    71138  public:
     139    typedef TR Traits;
    72140    ///The type of the underlying graph.
    73141    typedef GR Graph;
     
    87155    ///\brief The type of the map that stores the last
    88156    ///edges of the shortest paths.
    89     typedef typename Graph::template NodeMap<Edge> PredMap;
     157    typedef typename TR::PredMap PredMap;
    90158    ///\brief The type of the map that stores the last but one
    91159    ///nodes of the shortest paths.
    92     typedef typename Graph::template NodeMap<Node> PredNodeMap;
     160    typedef typename TR::PredNodeMap PredNodeMap;
    93161    ///The type of the map that stores the dists of the nodes.
    94     typedef typename Graph::template NodeMap<ValueType> DistMap;
     162    typedef typename TR::DistMap DistMap;
     163
     164    ///The heap type used by the dijkstra algorithm.
     165    typedef typename TR::Heap Heap;
    95166
    96167  private:
     
    123194      if(!predecessor) {
    124195        local_predecessor = true;
    125         predecessor = new PredMap(*G);
     196        predecessor = Traits::createPredMap(*G);
    126197      }
    127198      if(!pred_node) {
    128199        local_pred_node = true;
    129         pred_node = new PredNodeMap(*G);
     200        pred_node = Traits::createPredNodeMap(*G);
    130201      }
    131202      if(!distance) {
    132203        local_distance = true;
    133         distance = new DistMap(*G);
     204        distance = Traits::createDistMap(*G);
    134205      }
    135206    }
    136207   
    137208  public :
     209
     210    template <class T>
     211    struct SetPredMapTraits : public Traits {
     212      typedef T PredMap;
     213      ///\todo An exception should be thrown.
     214      ///
     215      static PredMap *createPredMap(const Graph &G)
     216      {
     217        std::cerr << __FILE__ ":" << __LINE__ <<
     218          ": error: Special maps should be manually created" << std::endl;
     219        exit(1);
     220      }
     221    };
     222    ///\ref named-templ-param "Named parameter" for setting PredMap's type
     223    template <class T>
     224    class SetPredMap : public Dijkstra< Graph,
     225                                        LengthMap,
     226                                        SetPredMapTraits<T> > { };
     227   
     228    template <class T>
     229    struct SetPredNodeMapTraits : public Traits {
     230      typedef T PredNodeMap;
     231      ///\todo An exception should be thrown.
     232      ///
     233      static PredNodeMap *createPredNodeMap(const Graph &G)
     234      {
     235        std::cerr << __FILE__ ":" << __LINE__ <<
     236          ": error: Special maps should be manually created" << std::endl;
     237        exit(1);
     238      }
     239    };
     240    ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
     241    template <class T>
     242    class SetPredNodeMap : public Dijkstra< Graph,
     243                                            LengthMap,
     244                                            SetPredNodeMapTraits<T> > { };
     245   
     246    template <class T>
     247    struct SetDistMapTraits : public Traits {
     248      typedef T DistMap;
     249      ///\todo An exception should be thrown.
     250      ///
     251      static DistMap *createDistMap(const Graph &G)
     252      {
     253        std::cerr << __FILE__ ":" << __LINE__ <<
     254          ": error: Special maps should be manually created" << std::endl;
     255        exit(1);
     256      }
     257    };
     258    ///\ref named-templ-param "Named parameter" for setting DistMap's type
     259    template <class T>
     260    class SetDistMap : public Dijkstra< Graph,
     261                                        LengthMap,
     262                                        SetDistMapTraits<T> > { };
     263   
    138264    ///Constructor.
    139265   
     
    238364      typename GR::template NodeMap<int> heap_map(*G,-1);
    239365     
    240       typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
    241       std::less<ValueType> >
    242       HeapType;
    243      
    244       HeapType heap(heap_map);
     366      Heap heap(heap_map);
    245367     
    246368      heap.push(s,0);
     
    257379          Node w=G->head(e);
    258380          switch(heap.state(w)) {
    259           case HeapType::PRE_HEAP:
     381          case Heap::PRE_HEAP:
    260382            heap.push(w,oldvalue+(*length)[e]);
    261383            predecessor->set(w,e);
    262384            pred_node->set(w,v);
    263385            break;
    264           case HeapType::IN_HEAP:
     386          case Heap::IN_HEAP:
    265387            if ( oldvalue+(*length)[e] < heap[w] ) {
    266388              heap.decrease(w, oldvalue+(*length)[e]);
     
    269391            }
    270392            break;
    271           case HeapType::POST_HEAP:
     393          case Heap::POST_HEAP:
    272394            break;
    273395          }
     
    335457   
    336458  };
     459
     460  ///\e
     461
     462  ///\e
     463  ///
     464  template<class TR>
     465  class _Dijkstra
     466  {
     467    typedef TR Traits;
     468
     469    ///The type of the underlying graph.
     470    typedef typename TR::Graph Graph;
     471    ///\e
     472    typedef typename Graph::Node Node;
     473    ///\e
     474    typedef typename Graph::NodeIt NodeIt;
     475    ///\e
     476    typedef typename Graph::Edge Edge;
     477    ///\e
     478    typedef typename Graph::OutEdgeIt OutEdgeIt;
     479   
     480    ///The type of the map that stores the edge lengths.
     481    typedef typename TR::LengthMap LengthMap;
     482    ///The type of the length of the edges.
     483    typedef typename LengthMap::ValueType ValueType;
     484    ///\brief The type of the map that stores the last
     485    ///edges of the shortest paths.
     486    typedef typename TR::PredMap PredMap;
     487    ///\brief The type of the map that stores the last but one
     488    ///nodes of the shortest paths.
     489    typedef typename TR::PredNodeMap PredNodeMap;
     490    ///The type of the map that stores the dists of the nodes.
     491    typedef typename TR::DistMap DistMap;
     492
     493    ///The heap type used by the dijkstra algorithm.
     494    typedef typename TR::Heap Heap;
     495
     496    /// Pointer to the underlying graph.
     497    const Graph *G;
     498    /// Pointer to the length map
     499    const LengthMap *length;
     500    ///Pointer to the map of predecessors edges.
     501    PredMap *predecessor;
     502    ///Pointer to the map of predecessors nodes.
     503    PredNodeMap *pred_node;
     504    ///Pointer to the map of distances.
     505    DistMap *distance;
     506   
     507    Node source;
     508   
     509public:
     510    _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0),
     511                  distance(0), source(INVALID) {}
     512
     513    _Dijkstra(const Graph &g,const LengthMap &l, Node s) :
     514      G(&g), length(&l), predecessor(0), pred_node(0),
     515                  distance(0), source(s) {}
     516
     517    ~_Dijkstra()
     518    {
     519      Dijkstra<Graph,LengthMap,TR> Dij(*G,*length);
     520      if(predecessor) Dij.setPredMap(*predecessor);
     521      if(pred_node) Dij.setPredNodeMap(*pred_node);
     522      if(distance) Dij.setDistMap(*distance);
     523      Dij.run(source);
     524    }
     525
     526    template<class T>
     527    struct SetPredMapTraits : public Traits {typedef T PredMap;};
     528   
     529    ///\e
     530    template<class T>
     531    _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t)
     532    {
     533      _Dijkstra<SetPredMapTraits<T> > r;
     534      r.G=G;
     535      r.length=length;
     536      r.predecessor=&t;
     537      r.pred_node=pred_node;
     538      r.distance=distance;
     539      r.source=source;
     540      return r;
     541    }
     542   
     543    template<class T>
     544    struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;};
     545    ///\e
     546    template<class T>
     547    _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t)
     548    {
     549      _Dijkstra<SetPredNodeMapTraits<T> > r;
     550      r.G=G;
     551      r.length=length;
     552      r.predecessor=predecessor;
     553      r.pred_node=&t;
     554      r.distance=distance;
     555      r.source=source;
     556      return r;
     557    }
     558   
     559    template<class T>
     560    struct SetDistMapTraits : public Traits {typedef T DistMap;};
     561    ///\e
     562    template<class T>
     563    _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t)
     564    {
     565      _Dijkstra<SetPredMapTraits<T> > r;
     566      r.G=G;
     567      r.length=length;
     568      r.predecessor=predecessor;
     569      r.pred_node=pred_node;
     570      r.distance=&t;
     571      r.source=source;
     572      return r;
     573    }
     574   
     575    ///\e
     576    _Dijkstra<TR> &setSource(Node s)
     577    {
     578      source=s;
     579      return *this;
     580    }
     581   
     582  };
    337583 
     584  ///\e
     585
     586  ///\e
     587  ///
     588  template<class GR, class LM>
     589  _Dijkstra<DijkstraDefaultTraits<GR,LM> >
     590  dijkstra(const GR &g,const LM &l,typename GR::Node s)
     591  {
     592    return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);
     593  }
     594
    338595/// @}
    339596 
Note: See TracChangeset for help on using the changeset viewer.