lemon/suurballe.h
changeset 858 9f6ed854d409
parent 854 9a7e4e606f83
child 863 a93f1a27d831
equal deleted inserted replaced
11:d706ecae73d2 12:fbb4ca8689e5
    31 #include <lemon/list_graph.h>
    31 #include <lemon/list_graph.h>
    32 #include <lemon/dijkstra.h>
    32 #include <lemon/dijkstra.h>
    33 #include <lemon/maps.h>
    33 #include <lemon/maps.h>
    34 
    34 
    35 namespace lemon {
    35 namespace lemon {
       
    36 
       
    37   /// \brief Default traits class of Suurballe algorithm.
       
    38   ///
       
    39   /// Default traits class of Suurballe algorithm.
       
    40   /// \tparam GR The digraph type the algorithm runs on.
       
    41   /// \tparam LEN The type of the length map.
       
    42   /// The default value is <tt>GR::ArcMap<int></tt>.
       
    43 #ifdef DOXYGEN
       
    44   template <typename GR, typename LEN>
       
    45 #else
       
    46   template < typename GR,
       
    47              typename LEN = typename GR::template ArcMap<int> >
       
    48 #endif
       
    49   struct SuurballeDefaultTraits
       
    50   {
       
    51     /// The type of the digraph.
       
    52     typedef GR Digraph;
       
    53     /// The type of the length map.
       
    54     typedef LEN LengthMap;
       
    55     /// The type of the lengths.
       
    56     typedef typename LEN::Value Length;
       
    57     /// The type of the flow map.
       
    58     typedef typename GR::template ArcMap<int> FlowMap;
       
    59     /// The type of the potential map.
       
    60     typedef typename GR::template NodeMap<Length> PotentialMap;
       
    61 
       
    62     /// \brief The path type
       
    63     ///
       
    64     /// The type used for storing the found arc-disjoint paths.
       
    65     /// It must conform to the \ref lemon::concepts::Path "Path" concept
       
    66     /// and it must have an \c addBack() function.
       
    67     typedef lemon::Path<Digraph> Path;
       
    68     
       
    69     /// The cross reference type used for the heap.
       
    70     typedef typename GR::template NodeMap<int> HeapCrossRef;
       
    71 
       
    72     /// \brief The heap type used for internal Dijkstra computations.
       
    73     ///
       
    74     /// The type of the heap used for internal Dijkstra computations.
       
    75     /// It must conform to the \ref lemon::concepts::Heap "Heap" concept
       
    76     /// and its priority type must be \c Length.
       
    77     typedef BinHeap<Length, HeapCrossRef> Heap;
       
    78   };
    36 
    79 
    37   /// \addtogroup shortest_path
    80   /// \addtogroup shortest_path
    38   /// @{
    81   /// @{
    39 
    82 
    40   /// \brief Algorithm for finding arc-disjoint paths between two nodes
    83   /// \brief Algorithm for finding arc-disjoint paths between two nodes
    59   /// \warning Length values should be \e non-negative.
   102   /// \warning Length values should be \e non-negative.
    60   ///
   103   ///
    61   /// \note For finding \e node-disjoint paths, this algorithm can be used
   104   /// \note For finding \e node-disjoint paths, this algorithm can be used
    62   /// along with the \ref SplitNodes adaptor.
   105   /// along with the \ref SplitNodes adaptor.
    63 #ifdef DOXYGEN
   106 #ifdef DOXYGEN
    64   template <typename GR, typename LEN>
   107   template <typename GR, typename LEN, typename TR>
    65 #else
   108 #else
    66   template < typename GR,
   109   template < typename GR,
    67              typename LEN = typename GR::template ArcMap<int> >
   110              typename LEN = typename GR::template ArcMap<int>,
       
   111              typename TR = SuurballeDefaultTraits<GR, LEN> >
    68 #endif
   112 #endif
    69   class Suurballe
   113   class Suurballe
    70   {
   114   {
    71     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   115     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    72 
   116 
    73     typedef ConstMap<Arc, int> ConstArcMap;
   117     typedef ConstMap<Arc, int> ConstArcMap;
    74     typedef typename GR::template NodeMap<Arc> PredMap;
   118     typedef typename GR::template NodeMap<Arc> PredMap;
    75 
   119 
    76   public:
   120   public:
    77 
   121 
    78     /// The type of the digraph the algorithm runs on.
   122     /// The type of the digraph.
    79     typedef GR Digraph;
   123     typedef typename TR::Digraph Digraph;
    80     /// The type of the length map.
   124     /// The type of the length map.
    81     typedef LEN LengthMap;
   125     typedef typename TR::LengthMap LengthMap;
    82     /// The type of the lengths.
   126     /// The type of the lengths.
    83     typedef typename LengthMap::Value Length;
   127     typedef typename TR::Length Length;
    84 #ifdef DOXYGEN
   128 
    85     /// The type of the flow map.
   129     /// The type of the flow map.
    86     typedef GR::ArcMap<int> FlowMap;
   130     typedef typename TR::FlowMap FlowMap;
    87     /// The type of the potential map.
   131     /// The type of the potential map.
    88     typedef GR::NodeMap<Length> PotentialMap;
   132     typedef typename TR::PotentialMap PotentialMap;
    89 #else
       
    90     /// The type of the flow map.
       
    91     typedef typename Digraph::template ArcMap<int> FlowMap;
       
    92     /// The type of the potential map.
       
    93     typedef typename Digraph::template NodeMap<Length> PotentialMap;
       
    94 #endif
       
    95 
       
    96     /// The type of the path structures.
   133     /// The type of the path structures.
    97     typedef SimplePath<GR> Path;
   134     typedef typename TR::Path Path;
       
   135     /// The cross reference type used for the heap.
       
   136     typedef typename TR::HeapCrossRef HeapCrossRef;
       
   137     /// The heap type used for internal Dijkstra computations.
       
   138     typedef typename TR::Heap Heap;
       
   139 
       
   140     /// The \ref SuurballeDefaultTraits "traits class" of the algorithm.
       
   141     typedef TR Traits;
    98 
   142 
    99   private:
   143   private:
   100 
       
   101     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
       
   102     typedef BinHeap<Length, HeapCrossRef> Heap;
       
   103 
   144 
   104     // ResidualDijkstra is a special implementation of the
   145     // ResidualDijkstra is a special implementation of the
   105     // Dijkstra algorithm for finding shortest paths in the
   146     // Dijkstra algorithm for finding shortest paths in the
   106     // residual network with respect to the reduced arc lengths
   147     // residual network with respect to the reduced arc lengths
   107     // and modifying the node potentials according to the
   148     // and modifying the node potentials according to the
   252         return true;
   293         return true;
   253       }
   294       }
   254 
   295 
   255     }; //class ResidualDijkstra
   296     }; //class ResidualDijkstra
   256 
   297 
       
   298   public:
       
   299 
       
   300     /// \name Named Template Parameters
       
   301     /// @{
       
   302 
       
   303     template <typename T>
       
   304     struct SetFlowMapTraits : public Traits {
       
   305       typedef T FlowMap;
       
   306     };
       
   307 
       
   308     /// \brief \ref named-templ-param "Named parameter" for setting
       
   309     /// \c FlowMap type.
       
   310     ///
       
   311     /// \ref named-templ-param "Named parameter" for setting
       
   312     /// \c FlowMap type.
       
   313     template <typename T>
       
   314     struct SetFlowMap
       
   315       : public Suurballe<GR, LEN, SetFlowMapTraits<T> > {
       
   316       typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create;
       
   317     };
       
   318 
       
   319     template <typename T>
       
   320     struct SetPotentialMapTraits : public Traits {
       
   321       typedef T PotentialMap;
       
   322     };
       
   323 
       
   324     /// \brief \ref named-templ-param "Named parameter" for setting
       
   325     /// \c PotentialMap type.
       
   326     ///
       
   327     /// \ref named-templ-param "Named parameter" for setting
       
   328     /// \c PotentialMap type.
       
   329     template <typename T>
       
   330     struct SetPotentialMap
       
   331       : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > {
       
   332       typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create;
       
   333     };
       
   334 
       
   335     template <typename T>
       
   336     struct SetPathTraits : public Traits {
       
   337       typedef T Path;
       
   338     };
       
   339 
       
   340     /// \brief \ref named-templ-param "Named parameter" for setting
       
   341     /// \c %Path type.
       
   342     ///
       
   343     /// \ref named-templ-param "Named parameter" for setting \c %Path type.
       
   344     /// It must conform to the \ref lemon::concepts::Path "Path" concept
       
   345     /// and it must have an \c addBack() function.
       
   346     template <typename T>
       
   347     struct SetPath
       
   348       : public Suurballe<GR, LEN, SetPathTraits<T> > {
       
   349       typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
       
   350     };
       
   351     
       
   352     template <typename H, typename CR>
       
   353     struct SetHeapTraits : public Traits {
       
   354       typedef H Heap;
       
   355       typedef CR HeapCrossRef;
       
   356     };
       
   357 
       
   358     /// \brief \ref named-templ-param "Named parameter" for setting
       
   359     /// \c Heap and \c HeapCrossRef types.
       
   360     ///
       
   361     /// \ref named-templ-param "Named parameter" for setting \c Heap
       
   362     /// and \c HeapCrossRef types with automatic allocation. 
       
   363     /// They will be used for internal Dijkstra computations.
       
   364     /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
       
   365     /// concept and its priority type must be \c Length.
       
   366     template <typename H,
       
   367               typename CR = typename Digraph::template NodeMap<int> >
       
   368     struct SetHeap
       
   369       : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > {
       
   370       typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create;
       
   371     };
       
   372 
       
   373     /// @}
       
   374 
   257   private:
   375   private:
   258 
   376 
   259     // The digraph the algorithm runs on
   377     // The digraph the algorithm runs on
   260     const Digraph &_graph;
   378     const Digraph &_graph;
   261     // The length map
   379     // The length map