COIN-OR::LEMON - Graph Library

Changeset 1218:5331168bbb18 in lemon-0.x for src/lemon/dijkstra.h


Ignore:
Timestamp:
03/16/05 08:56:25 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1638
Message:
  • Several updates and clarifications on dijkstra.h
  • bfs.h and dfs.h is synchronized with dijkstra.h
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/dijkstra.h

    r1201 r1218  
    7777      return new PredMap(G);
    7878    }
    79     ///\brief The type of the map that stores the last but one
    80     ///nodes of the shortest paths.
    81     ///
    82     ///The type of the map that stores the last but one
    83     ///nodes of the shortest paths.
    84     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    85     ///
    86     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
    87     ///Instantiates a PredNodeMap.
    88    
    89     ///This function instantiates a \ref PredNodeMap.
    90     ///\param G is the graph, to which
    91     ///we would like to define the \ref PredNodeMap
    92     static PredNodeMap *createPredNodeMap(const GR &G)
    93     {
    94       return new PredNodeMap();
    95     }
    96 
    97     ///The type of the map that stores whether a nodes is reached.
    98  
    99     ///The type of the map that stores whether a nodes is reached.
     79//     ///\brief The type of the map that stores the last but one
     80//     ///nodes of the shortest paths.
     81//     ///
     82//     ///The type of the map that stores the last but one
     83//     ///nodes of the shortest paths.
     84//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     85//     ///
     86//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     87//     ///Instantiates a PredNodeMap.
     88   
     89//     ///This function instantiates a \ref PredNodeMap.
     90//     ///\param G is the graph, to which
     91//     ///we would like to define the \ref PredNodeMap
     92//     static PredNodeMap *createPredNodeMap(const GR &G)
     93//     {
     94//       return new PredNodeMap();
     95//     }
     96
     97    ///The type of the map that stores whether a nodes is processed.
     98 
     99    ///The type of the map that stores whether a nodes is processed.
    100100    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    101101    ///By default it is a NullMap.
    102     ///\todo If it is set to a real map, Dijkstra::reached() should read this.
     102    ///\todo If it is set to a real map,
     103    ///Dijkstra::processed() should read this.
    103104    ///\todo named parameter to set this type, function to read and write.
    104     typedef NullMap<typename Graph::Node,bool> ReachedMap;
    105     ///Instantiates a ReachedMap.
    106  
    107     ///This function instantiates a \ref ReachedMap.
     105    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     106    ///Instantiates a ProcessedMap.
     107 
     108    ///This function instantiates a \ref ProcessedMap.
    108109    ///\param G is the graph, to which
    109     ///we would like to define the \ref ReachedMap
    110     static ReachedMap *createReachedMap(const GR &G)
    111     {
    112       return new ReachedMap();
     110    ///we would like to define the \ref ProcessedMap
     111    static ProcessedMap *createProcessedMap(const GR &G)
     112    {
     113      return new ProcessedMap();
    113114    }
    114115    ///The type of the map that stores the dists of the nodes.
     
    141142  ///It is also possible to change the underlying priority heap.
    142143  ///
    143   ///\param GR The graph type the algorithm runs on. The default value is
    144   ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
    145   ///is only passed to \ref DijkstraDefaultTraits.
    146   ///\param LM This read-only
    147   ///EdgeMap
    148   ///determines the
    149   ///lengths of the edges. It is read once for each edge, so the map
    150   ///may involve in relatively time consuming process to compute the edge
    151   ///length if it is necessary. The default map type is
    152   ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
    153   ///The value of LM is not used directly by Dijkstra, it
    154   ///is only passed to \ref DijkstraDefaultTraits.
    155   ///\param TR Traits class to set various data types used by the algorithm.
    156   ///The default traits class is
    157   ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
    158   ///See \ref DijkstraDefaultTraits for the documentation of
    159   ///a Dijkstra traits class.
     144  ///\param GR The graph type the algorithm runs on. The default value
     145  ///is \ref ListGraph. The value of GR is not used directly by
     146  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
     147  ///\param LM This read-only EdgeMap determines the lengths of the
     148  ///edges. It is read once for each edge, so the map may involve in
     149  ///relatively time consuming process to compute the edge length if
     150  ///it is necessary. The default map type is \ref
     151  ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     152  ///of LM is not used directly by Dijkstra, it is only passed to \ref
     153  ///DijkstraDefaultTraits.  \param TR Traits class to set
     154  ///various data types used by the algorithm.  The default traits
     155  ///class is \ref DijkstraDefaultTraits
     156  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
     157  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
     158  ///class.
    160159  ///
    161160  ///\author Jacint Szabo and Alpar Juttner
     
    182181    public:
    183182      virtual const char* exceptionName() const {
    184         return "lemon::Dijsktra::UninitializedParameter";
     183        return "lemon::Dijkstra::UninitializedParameter";
    185184      }
    186185    };
     
    205204    ///edges of the shortest paths.
    206205    typedef typename TR::PredMap PredMap;
    207     ///\brief The type of the map that stores the last but one
    208     ///nodes of the shortest paths.
    209     typedef typename TR::PredNodeMap PredNodeMap;
    210     ///The type of the map indicating if a node is reached.
    211     typedef typename TR::ReachedMap ReachedMap;
     206//     ///\brief The type of the map that stores the last but one
     207//     ///nodes of the shortest paths.
     208//     typedef typename TR::PredNodeMap PredNodeMap;
     209    ///The type of the map indicating if a node is processed.
     210    typedef typename TR::ProcessedMap ProcessedMap;
    212211    ///The type of the map that stores the dists of the nodes.
    213212    typedef typename TR::DistMap DistMap;
     
    223222    ///Indicates if \ref _pred is locally allocated (\c true) or not.
    224223    bool local_pred;
    225     ///Pointer to the map of predecessors nodes.
    226     PredNodeMap *_predNode;
    227     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
    228     bool local_predNode;
     224//     ///Pointer to the map of predecessors nodes.
     225//     PredNodeMap *_predNode;
     226//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
     227//     bool local_predNode;
    229228    ///Pointer to the map of distances.
    230229    DistMap *_dist;
    231230    ///Indicates if \ref _dist is locally allocated (\c true) or not.
    232231    bool local_dist;
    233     ///Pointer to the map of reached status of the nodes.
    234     ReachedMap *_reached;
    235     ///Indicates if \ref _reached is locally allocated (\c true) or not.
    236     bool local_reached;
    237 
    238     ///The source node of the last execution.
    239     Node source;
     232    ///Pointer to the map of processed status of the nodes.
     233    ProcessedMap *_processed;
     234    ///Indicates if \ref _processed is locally allocated (\c true) or not.
     235    bool local_processed;
     236
     237//     ///The source node of the last execution.
     238//     Node source;
    240239
    241240    ///Creates the maps if necessary.
     
    249248        _pred = Traits::createPredMap(*G);
    250249      }
    251       if(!_predNode) {
    252         local_predNode = true;
    253         _predNode = Traits::createPredNodeMap(*G);
    254       }
     250//       if(!_predNode) {
     251//      local_predNode = true;
     252//      _predNode = Traits::createPredNodeMap(*G);
     253//       }
    255254      if(!_dist) {
    256255        local_dist = true;
    257256        _dist = Traits::createDistMap(*G);
    258257      }
    259       if(!_reached) {
    260         local_reached = true;
    261         _reached = Traits::createReachedMap(*G);
     258      if(!_processed) {
     259        local_processed = true;
     260        _processed = Traits::createProcessedMap(*G);
    262261      }
    263262    }
     
    286285                                        DefPredMapTraits<T> > { };
    287286   
    288     template <class T>
    289     struct DefPredNodeMapTraits : public Traits {
    290       typedef T PredNodeMap;
    291       static PredNodeMap *createPredNodeMap(const Graph &G)
    292       {
    293         throw UninitializedParameter();
    294       }
    295     };
    296     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
    297 
    298     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
    299     ///
    300     template <class T>
    301     class DefPredNodeMap : public Dijkstra< Graph,
    302                                             LengthMap,
    303                                             DefPredNodeMapTraits<T> > { };
     287//     template <class T>
     288//     struct DefPredNodeMapTraits : public Traits {
     289//       typedef T PredNodeMap;
     290//       static PredNodeMap *createPredNodeMap(const Graph &G)
     291//       {
     292//      throw UninitializedParameter();
     293//       }
     294//     };
     295//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     296
     297//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     298//     ///
     299//     template <class T>
     300//     class DefPredNodeMap : public Dijkstra< Graph,
     301//                                          LengthMap,
     302//                                          DefPredNodeMapTraits<T> > { };
    304303   
    305304    template <class T>
     
    321320   
    322321    template <class T>
    323     struct DefReachedMapTraits : public Traits {
    324       typedef T ReachedMap;
    325       static ReachedMap *createReachedMap(const Graph &G)
     322    struct DefProcessedMapTraits : public Traits {
     323      typedef T ProcessedMap;
     324      static ProcessedMap *createProcessedMap(const Graph &G)
    326325      {
    327326        throw UninitializedParameter();
    328327      }
    329328    };
    330     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    331 
    332     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     329    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     330
     331    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    333332    ///
    334333    template <class T>
    335     class DefReachedMap : public Dijkstra< Graph,
     334    class DefProcessedMap : public Dijkstra< Graph,
    336335                                        LengthMap,
    337                                         DefReachedMapTraits<T> > { };
    338    
    339     struct DefGraphReachedMapTraits : public Traits {
    340       typedef typename Graph::template NodeMap<bool> ReachedMap;
    341       static ReachedMap *createReachedMap(const Graph &G)
     336                                        DefProcessedMapTraits<T> > { };
     337   
     338    struct DefGraphProcessedMapTraits : public Traits {
     339      typedef typename Graph::template NodeMap<bool> ProcessedMap;
     340      static ProcessedMap *createProcessedMap(const Graph &G)
    342341      {
    343         return new ReachedMap(G);
     342        return new ProcessedMap(G);
    344343      }
    345344    };
    346345    ///\brief \ref named-templ-param "Named parameter"
    347     ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
     346    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
    348347    ///
    349348    ///\ref named-templ-param "Named parameter"
    350     ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
     349    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
    351350    ///If you don't set it explicitely, it will be automatically allocated.
    352351    template <class T>
    353     class DefReachedMapToBeDefaultMap :
     352    class DefProcessedMapToBeDefaultMap :
    354353      public Dijkstra< Graph,
    355354                       LengthMap,
    356                        DefGraphReachedMapTraits> { };
     355                       DefGraphProcessedMapTraits> { };
    357356   
    358357    ///@}
     
    371370      G(&_G), length(&_length),
    372371      _pred(NULL), local_pred(false),
    373       _predNode(NULL), local_predNode(false),
     372//       _predNode(NULL), local_predNode(false),
    374373      _dist(NULL), local_dist(false),
    375       _reached(NULL), local_reached(false),
     374      _processed(NULL), local_processed(false),
    376375      _heap_map(*G,-1),_heap(_heap_map)
    377376    { }
     
    381380    {
    382381      if(local_pred) delete _pred;
    383       if(local_predNode) delete _predNode;
     382//       if(local_predNode) delete _predNode;
    384383      if(local_dist) delete _dist;
    385       if(local_reached) delete _reached;
     384      if(local_processed) delete _processed;
    386385    }
    387386
     
    413412    }
    414413
    415     ///Sets the map storing the predecessor nodes.
    416 
    417     ///Sets the map storing the predecessor nodes.
    418     ///If you don't use this function before calling \ref run(),
    419     ///it will allocate one. The destuctor deallocates this
    420     ///automatically allocated map, of course.
    421     ///\return <tt> (*this) </tt>
    422     Dijkstra &predNodeMap(PredNodeMap &m)
    423     {
    424       if(local_predNode) {
    425         delete _predNode;
    426         local_predNode=false;
    427       }
    428       _predNode = &m;
    429       return *this;
    430     }
     414//     ///Sets the map storing the predecessor nodes.
     415
     416//     ///Sets the map storing the predecessor nodes.
     417//     ///If you don't use this function before calling \ref run(),
     418//     ///it will allocate one. The destuctor deallocates this
     419//     ///automatically allocated map, of course.
     420//     ///\return <tt> (*this) </tt>
     421//     Dijkstra &predNodeMap(PredNodeMap &m)
     422//     {
     423//       if(local_predNode) {
     424//      delete _predNode;
     425//      local_predNode=false;
     426//       }
     427//       _predNode = &m;
     428//       return *this;
     429//     }
    431430
    432431    ///Sets the map storing the distances calculated by the algorithm.
     
    450449    void finalizeNodeData(Node v,Value dst)
    451450    {
    452       _reached->set(v,true);
     451      _processed->set(v,true);
    453452      _dist->set(v, dst);
    454       if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
     453//       if((*_pred)[v]!=INVALID)
     454//       _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
    455455    }
    456456
    457457  public:
    458     ///\name Excetution control
     458    ///\name Execution control
    459459    ///The simplest way to execute the algorithm is to use
    460460    ///one of the member functions called \c run(...).
    461461    ///\n
    462     ///It you need more control on the execution,
     462    ///If you need more control on the execution,
    463463    ///first you must call \ref init(), then you can add several source nodes
    464     ///with \ref addSource(). Finally \ref start() will perform the actual path
     464    ///with \ref addSource().
     465    ///Finally \ref start() will perform the actual path
    465466    ///computation.
    466467
     
    478479      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    479480        _pred->set(u,INVALID);
    480         _predNode->set(u,INVALID);
    481         ///\todo *_reached is not set to false.
     481//      _predNode->set(u,INVALID);
     482        _processed->set(u,false);
    482483        _heap_map.set(u,Heap::PRE_HEAP);
    483484      }
     
    495496    void addSource(Node s,Value dst=0)
    496497    {
    497       source = s;
     498//       source = s;
    498499      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
    499500      else if(_heap[s]<dst) {
     
    536537    }
    537538
    538     ///Returns \c false if there are nodes to be processed in the priority heap
    539 
    540     ///Returns \c false if there are nodes to be processed in the priority heap
    541     ///
    542     bool emptyHeap() { return _heap.empty(); }
     539    ///\brief Returns \c false if there are nodes
     540    ///to be processed in the priority heap
     541    ///
     542    ///Returns \c false if there are nodes
     543    ///to be processed in the priority heap
     544    bool emptyQueue() { return _heap.empty(); }
    543545    ///Returns the number of the nodes to be processed in the priority heap
    544546
    545547    ///Returns the number of the nodes to be processed in the priority heap
    546548    ///
    547     int heapSize() { return _heap.size(); }
     549    int queueSize() { return _heap.size(); }
    548550   
    549551    ///Executes the algorithm.
     
    697699    const PredMap &predMap() const { return *_pred;}
    698700 
    699     ///Returns a reference to the map of nodes of shortest paths.
    700 
    701     ///Returns a reference to the NodeMap of the last but one nodes of the
    702     ///shortest path tree.
     701//     ///Returns a reference to the map of nodes of shortest paths.
     702
     703//     ///Returns a reference to the NodeMap of the last but one nodes of the
     704//     ///shortest path tree.
     705//     ///\pre \ref run() must be called before using this function.
     706//     const PredNodeMap &predNodeMap() const { return *_predNode;}
     707
     708    ///Checks if a node is reachable from the root.
     709
     710    ///Returns \c true if \c v is reachable from the root.
     711    ///\warning The source nodes are inditated as unreached.
    703712    ///\pre \ref run() must be called before using this function.
    704     const PredNodeMap &predNodeMap() const { return *_predNode;}
    705 
    706     ///Checks if a node is reachable from the root.
    707 
    708     ///Returns \c true if \c v is reachable from the root.
    709     ///\warning If the algorithm is started from multiple nodes,
    710     ///this function may give false result for the source nodes.
    711     ///\pre \ref run() must be called before using this function.
    712     ///
    713     bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
     713    ///
     714    bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
    714715   
    715716    ///@}
    716717  };
    717718
     719
     720
     721
     722 
     723  ///Default traits class of Dijkstra function.
     724
     725  ///Default traits class of Dijkstra function.
     726  ///\param GR Graph type.
     727  ///\param LM Type of length map.
     728  template<class GR, class LM>
     729  struct DijkstraWizardDefaultTraits
     730  {
     731    ///The graph type the algorithm runs on.
     732    typedef GR Graph;
     733    ///The type of the map that stores the edge lengths.
     734
     735    ///The type of the map that stores the edge lengths.
     736    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
     737    typedef LM LengthMap;
     738    //The type of the length of the edges.
     739    typedef typename LM::Value Value;
     740    ///The heap type used by Dijkstra algorithm.
     741
     742    ///The heap type used by Dijkstra algorithm.
     743    ///
     744    ///\sa BinHeap
     745    ///\sa Dijkstra
     746    typedef BinHeap<typename Graph::Node,
     747                    typename LM::Value,
     748                    typename GR::template NodeMap<int>,
     749                    std::less<Value> > Heap;
     750
     751    ///\brief The type of the map that stores the last
     752    ///edges of the shortest paths.
     753    ///
     754    ///The type of the map that stores the last
     755    ///edges of the shortest paths.
     756    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     757    ///
     758    typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
     759    ///Instantiates a PredMap.
     760 
     761    ///This function instantiates a \ref PredMap.
     762    ///\param G is the graph, to which we would like to define the PredMap.
     763    ///\todo The graph alone may be insufficient for the initialization
     764    static PredMap *createPredMap(const GR &G)
     765    {
     766      return new PredMap();
     767    }
     768    ///The type of the map that stores whether a nodes is processed.
     769 
     770    ///The type of the map that stores whether a nodes is processed.
     771    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     772    ///By default it is a NullMap.
     773    ///\todo If it is set to a real map,
     774    ///Dijkstra::processed() should read this.
     775    ///\todo named parameter to set this type, function to read and write.
     776    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     777    ///Instantiates a ProcessedMap.
     778 
     779    ///This function instantiates a \ref ProcessedMap.
     780    ///\param G is the graph, to which
     781    ///we would like to define the \ref ProcessedMap
     782    static ProcessedMap *createProcessedMap(const GR &G)
     783    {
     784      return new ProcessedMap();
     785    }
     786    ///The type of the map that stores the dists of the nodes.
     787 
     788    ///The type of the map that stores the dists of the nodes.
     789    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     790    ///
     791    typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
     792    ///Instantiates a DistMap.
     793 
     794    ///This function instantiates a \ref DistMap.
     795    ///\param G is the graph, to which we would like to define the \ref DistMap
     796    static DistMap *createDistMap(const GR &G)
     797    {
     798      return new DistMap();
     799    }
     800  };
     801 
    718802  /// Default traits used by \ref DijkstraWizard
    719803
     
    725809  /// \ref DijkstraWizard class.
    726810  template<class GR,class LM>
    727   class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
     811  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
    728812  {
    729813
    730     typedef DijkstraDefaultTraits<GR,LM> Base;
     814    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
    731815  protected:
    732816    /// Type of the nodes in the graph.
     
    739823    ///Pointer to the map of predecessors edges.
    740824    void *_pred;
    741     ///Pointer to the map of predecessors nodes.
    742     void *_predNode;
     825//     ///Pointer to the map of predecessors nodes.
     826//     void *_predNode;
    743827    ///Pointer to the map of distances.
    744828    void *_dist;
     
    751835    /// This constructor does not require parameters, therefore it initiates
    752836    /// all of the attributes to default values (0, INVALID).
    753     DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
    754                        _dist(0), _source(INVALID) {}
     837    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
     838//                         _predNode(0),
     839                           _dist(0), _source(INVALID) {}
    755840
    756841    /// Constructor.
     
    763848    /// \param s is the initial value of  \ref _source
    764849    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
    765       _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
    766                   _dist(0), _source(s) {}
     850      _g((void *)&g), _length((void *)&l), _pred(0),
     851//       _predNode(0),
     852      _dist(0), _source(s) {}
    767853
    768854  };
     
    770856  /// A class to make easier the usage of Dijkstra algorithm
    771857
    772   /// \ingroup flowalgs
    773858  /// This class is created to make it easier to use Dijkstra algorithm.
    774859  /// It uses the functions and features of the plain \ref Dijkstra,
     
    811896    ///edges of the shortest paths.
    812897    typedef typename TR::PredMap PredMap;
    813     ///\brief The type of the map that stores the last but one
    814     ///nodes of the shortest paths.
    815     typedef typename TR::PredNodeMap PredNodeMap;
     898//     ///\brief The type of the map that stores the last but one
     899//     ///nodes of the shortest paths.
     900//     typedef typename TR::PredNodeMap PredNodeMap;
    816901    ///The type of the map that stores the dists of the nodes.
    817902    typedef typename TR::DistMap DistMap;
     
    845930        Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
    846931      if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
    847       if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
     932//       if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
    848933      if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
    849934      Dij.run(Base::_source);
     
    881966   
    882967
    883     template<class T>
    884     struct DefPredNodeMapBase : public Base {
    885       typedef T PredNodeMap;
    886       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
    887       DefPredNodeMapBase(const Base &b) : Base(b) {}
    888     };
    889    
    890     ///\brief \ref named-templ-param "Named parameter"
    891     ///function for setting PredNodeMap type
    892     ///
    893     /// \ref named-templ-param "Named parameter"
    894     ///function for setting PredNodeMap type
    895     ///
    896     template<class T>
    897     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
    898     {
    899       Base::_predNode=(void *)&t;
    900       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
    901     }
     968//     template<class T>
     969//     struct DefPredNodeMapBase : public Base {
     970//       typedef T PredNodeMap;
     971//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
     972//       DefPredNodeMapBase(const Base &b) : Base(b) {}
     973//     };
     974   
     975//     ///\brief \ref named-templ-param "Named parameter"
     976//     ///function for setting PredNodeMap type
     977//     ///
     978//     /// \ref named-templ-param "Named parameter"
     979//     ///function for setting PredNodeMap type
     980//     ///
     981//     template<class T>
     982//     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
     983//     {
     984//       Base::_predNode=(void *)&t;
     985//       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
     986//     }
    902987   
    903988    template<class T>
     
    9331018  };
    9341019 
    935   ///\e
     1020  ///Function type interface for Dijkstra algorithm.
    9361021
    9371022  /// \ingroup flowalgs
    938   ///\todo Please document...
     1023  ///Function type interface for Dijkstra algorithm.
    9391024  ///
     1025  ///This function also has several
     1026  ///\ref named-templ-func-param "named parameters",
     1027  ///they are declared as the members of class \ref DijkstraWizard.
     1028  ///The following
     1029  ///example shows how to use these parameters.
     1030  ///\code
     1031  ///  dijkstra(g,length,source).predMap(preds).run();
     1032  ///\endcode
     1033  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1034  ///to the end of the parameter list.
     1035  ///\sa DijkstraWizard
     1036  ///\sa Dijkstra
    9401037  template<class GR, class LM>
    9411038  DijkstraWizard<DijkstraWizardBase<GR,LM> >
     
    9451042  }
    9461043
    947 /// @}
    948  
    9491044} //END OF NAMESPACE LEMON
    9501045
Note: See TracChangeset for help on using the changeset viewer.