lemon/dijkstra.h
changeset 217 b67149f0e675
parent 209 765619b7cbb2
child 220 a5d8c039f218
child 244 c30731a37f91
equal deleted inserted replaced
4:8f6ed5bfce34 5:fff5815c9c95
   171     ///
   171     ///
   172     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   172     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   173     ///Instantiates a DistMap.
   173     ///Instantiates a DistMap.
   174 
   174 
   175     ///This function instantiates a \ref DistMap.
   175     ///This function instantiates a \ref DistMap.
   176     ///\param G is the digraph, to which we would like to define the \ref DistMap
   176     ///\param G is the digraph, to which we would like to define
       
   177     ///the \ref DistMap
   177     static DistMap *createDistMap(const GR &G)
   178     static DistMap *createDistMap(const GR &G)
   178     {
   179     {
   179       return new DistMap(G);
   180       return new DistMap(G);
   180     }
   181     }
   181   };
   182   };
   334 
   335 
   335     ///\ref named-templ-param "Named parameter" for setting PredMap type
   336     ///\ref named-templ-param "Named parameter" for setting PredMap type
   336     ///
   337     ///
   337     template <class T>
   338     template <class T>
   338     struct DefPredMap
   339     struct DefPredMap
   339       : public Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > {
   340       : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
   340       typedef Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > Create;
   341       typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create;
   341     };
   342     };
   342 
   343 
   343     template <class T>
   344     template <class T>
   344     struct DefDistMapTraits : public Traits {
   345     struct DefDistMapTraits : public Traits {
   345       typedef T DistMap;
   346       typedef T DistMap;
   370 
   371 
   371     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   372     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   372     ///
   373     ///
   373     template <class T>
   374     template <class T>
   374     struct DefProcessedMap
   375     struct DefProcessedMap
   375       : public Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > {
   376       : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
   376       typedef Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > Create;
   377       typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create;
   377     };
   378     };
   378 
   379 
   379     struct DefDigraphProcessedMapTraits : public Traits {
   380     struct DefDigraphProcessedMapTraits : public Traits {
   380       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   381       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   381       static ProcessedMap *createProcessedMap(const Digraph &G)
   382       static ProcessedMap *createProcessedMap(const Digraph &G)
   390     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   391     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   391     ///If you don't set it explicitely, it will be automatically allocated.
   392     ///If you don't set it explicitely, it will be automatically allocated.
   392     template <class T>
   393     template <class T>
   393     struct DefProcessedMapToBeDefaultMap
   394     struct DefProcessedMapToBeDefaultMap
   394       : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
   395       : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
   395       typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
   396       typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits>
       
   397       Create;
   396     };
   398     };
   397 
   399 
   398     template <class H, class CR>
   400     template <class H, class CR>
   399     struct DefHeapTraits : public Traits {
   401     struct DefHeapTraits : public Traits {
   400       typedef CR HeapCrossRef;
   402       typedef CR HeapCrossRef;
   413     ///\ref named-templ-param "Named parameter" for setting heap and cross
   415     ///\ref named-templ-param "Named parameter" for setting heap and cross
   414     ///reference type
   416     ///reference type
   415     ///
   417     ///
   416     template <class H, class CR = typename Digraph::template NodeMap<int> >
   418     template <class H, class CR = typename Digraph::template NodeMap<int> >
   417     struct DefHeap
   419     struct DefHeap
   418       : public Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > {
   420       : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
   419       typedef Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > Create;
   421       typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create;
   420     };
   422     };
   421 
   423 
   422     template <class H, class CR>
   424     template <class H, class CR>
   423     struct DefStandardHeapTraits : public Traits {
   425     struct DefStandardHeapTraits : public Traits {
   424       typedef CR HeapCrossRef;
   426       typedef CR HeapCrossRef;
   438     ///reference type. It can allocate the heap and the cross reference
   440     ///reference type. It can allocate the heap and the cross reference
   439     ///object if the cross reference's constructor waits for the digraph as
   441     ///object if the cross reference's constructor waits for the digraph as
   440     ///parameter and the heap's constructor waits for the cross reference.
   442     ///parameter and the heap's constructor waits for the cross reference.
   441     template <class H, class CR = typename Digraph::template NodeMap<int> >
   443     template <class H, class CR = typename Digraph::template NodeMap<int> >
   442     struct DefStandardHeap
   444     struct DefStandardHeap
   443       : public Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> > {
   445       : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {
   444       typedef Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> >
   446       typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >
   445       Create;
   447       Create;
   446     };
   448     };
   447 
   449 
   448     template <class T>
   450     template <class T>
   449     struct DefOperationTraitsTraits : public Traits {
   451     struct DefOperationTraitsTraits : public Traits {
   974     ///
   976     ///
   975     typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
   977     typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
   976     ///Instantiates a DistMap.
   978     ///Instantiates a DistMap.
   977 
   979 
   978     ///This function instantiates a \ref DistMap.
   980     ///This function instantiates a \ref DistMap.
   979     ///\param g is the digraph, to which we would like to define the \ref DistMap
   981     ///\param g is the digraph, to which we would like to define
       
   982     ///the \ref DistMap
   980 #ifdef DOXYGEN
   983 #ifdef DOXYGEN
   981     static DistMap *createDistMap(const GR &g)
   984     static DistMap *createDistMap(const GR &g)
   982 #else
   985 #else
   983     static DistMap *createDistMap(const GR &)
   986     static DistMap *createDistMap(const GR &)
   984 #endif
   987 #endif