Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/dijkstra.h
changeset 280 e7f8647ce760
parent 258 0310c8984732
child 281 e9b4fbe163f5
equal deleted inserted replaced
11:909a8392b2ee 13:f6c62e84bc08 
   141     ///Instantiates a \ref PredMap.
 
   141     ///Instantiates a \ref PredMap.
 
   142 
   142 
   143     ///This function instantiates a \ref PredMap.
 
   143     ///This function instantiates a \ref PredMap.
 
   144     ///\param g is the digraph, to which we would like to define the
 
   144     ///\param g is the digraph, to which we would like to define the
 
   145     ///\ref PredMap.
 
   145     ///\ref PredMap.
 
   146     ///\todo The digraph alone may be insufficient for the initialization
 
       
   147     static PredMap *createPredMap(const Digraph &g)
 
   146     static PredMap *createPredMap(const Digraph &g)
 
   148     {
 
   147     {
 
   149       return new PredMap(g);
 
   148       return new PredMap(g);
 
   150     }
 
   149     }
 
   151 
   150 
   152     ///The type of the map that indicates which nodes are processed.
 
   151     ///The type of the map that indicates which nodes are processed.
 
   153 
   152 
   154     ///The type of the map that indicates which nodes are processed.
 
   153     ///The type of the map that indicates which nodes are processed.
 
   155     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 
   154     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 
   156     ///By default it is a NullMap.
 
   155     ///By default it is a NullMap.
 
   157     ///\todo If it is set to a real map,
 
       
   158     ///Dijkstra::processed() should read this.
 
       
   159     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 
   156     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 
   160     ///Instantiates a \ref ProcessedMap.
 
   157     ///Instantiates a \ref ProcessedMap.
 
   161 
   158 
   162     ///This function instantiates a \ref ProcessedMap.
 
   159     ///This function instantiates a \ref ProcessedMap.
 
   163     ///\param g is the digraph, to which
 
   160     ///\param g is the digraph, to which
 
   294     //Pointer to the heap.
 
   291     //Pointer to the heap.
 
   295     Heap *_heap;
 
   292     Heap *_heap;
 
   296     //Indicates if _heap is locally allocated (true) or not.
 
   293     //Indicates if _heap is locally allocated (true) or not.
 
   297     bool local_heap;
 
   294     bool local_heap;
 
   298 
   295 
   299     ///Creates the maps if necessary.
 
   296     //Creates the maps if necessary.
 
   300     ///\todo Better memory allocation (instead of new).
 
       
   301     void create_maps()
 
   297     void create_maps()
 
   302     {
 
   298     {
 
   303       if(!_pred) {
 
   299       if(!_pred) {
 
   304         local_pred = true;
 
   300         local_pred = true;
 
   305         _pred = Traits::createPredMap(*G);
 
   301         _pred = Traits::createPredMap(*G);
 
   955     ///Instantiates a \ref HeapCrossRef.
 
   951     ///Instantiates a \ref HeapCrossRef.
 
   956 
   952 
   957     ///This function instantiates a \ref HeapCrossRef.
 
   953     ///This function instantiates a \ref HeapCrossRef.
 
   958     /// \param g is the digraph, to which we would like to define the
 
   954     /// \param g is the digraph, to which we would like to define the
 
   959     /// HeapCrossRef.
 
   955     /// HeapCrossRef.
 
   960     /// \todo The digraph alone may be insufficient for the initialization
 
       
   961     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
 
   956     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
 
   962     {
 
   957     {
 
   963       return new HeapCrossRef(g);
 
   958       return new HeapCrossRef(g);
 
   964     }
 
   959     }
 
   965 
   960 
   991     ///Instantiates a \ref PredMap.
 
   986     ///Instantiates a \ref PredMap.
 
   992 
   987 
   993     ///This function instantiates a \ref PredMap.
 
   988     ///This function instantiates a \ref PredMap.
 
   994     ///\param g is the digraph, to which we would like to define the
 
   989     ///\param g is the digraph, to which we would like to define the
 
   995     ///\ref PredMap.
 
   990     ///\ref PredMap.
 
   996     ///\todo The digraph alone may be insufficient to initialize
 
       
   997 #ifdef DOXYGEN
 
   991 #ifdef DOXYGEN
 
   998     static PredMap *createPredMap(const Digraph &g)
 
   992     static PredMap *createPredMap(const Digraph &g)
 
   999 #else
 
   993 #else
 
  1000     static PredMap *createPredMap(const Digraph &)
 
   994     static PredMap *createPredMap(const Digraph &)
 
  1001 #endif
 
   995 #endif
 
  1006     ///The type of the map that indicates which nodes are processed.
 
  1000     ///The type of the map that indicates which nodes are processed.
 
  1007 
  1001 
  1008     ///The type of the map that indicates which nodes are processed.
 
  1002     ///The type of the map that indicates which nodes are processed.
 
  1009     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 
  1003     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 
  1010     ///By default it is a NullMap.
 
  1004     ///By default it is a NullMap.
 
  1011     ///\todo If it is set to a real map,
 
       
  1012     ///Dijkstra::processed() should read this.
 
       
  1013     ///\todo named parameter to set this type, function to read and write.
 
       
  1014     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 
  1005     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 
  1015     ///Instantiates a \ref ProcessedMap.
 
  1006     ///Instantiates a \ref ProcessedMap.
 
  1016 
  1007 
  1017     ///This function instantiates a \ref ProcessedMap.
 
  1008     ///This function instantiates a \ref ProcessedMap.
 
  1018     ///\param g is the digraph, to which
 
  1009     ///\param g is the digraph, to which
 
  1052   /// we have created a wizard class.
 
  1043   /// we have created a wizard class.
 
  1053   /// This \ref DijkstraWizard class needs default traits,
 
  1044   /// This \ref DijkstraWizard class needs default traits,
 
  1054   /// as well as the \ref Dijkstra class.
 
  1045   /// as well as the \ref Dijkstra class.
 
  1055   /// The \ref DijkstraWizardBase is a class to be the default traits of the
 
  1046   /// The \ref DijkstraWizardBase is a class to be the default traits of the
 
  1056   /// \ref DijkstraWizard class.
 
  1047   /// \ref DijkstraWizard class.
 
  1057   /// \todo More named parameters are required...
 
       
  1058   template<class GR,class LM>
 
  1048   template<class GR,class LM>
 
  1059   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
 
  1049   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
 
  1060   {
 
  1050   {
 
  1061     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
 
  1051     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
 
  1062   protected:
 
  1052   protected:
lemon