lemon/suurballe.h
changeset 561 6e0525ec5355
parent 519 c786cd201266
child 584 33c6b6e755cd
equal deleted inserted replaced
4:c294dcbb3735 5:160397e13edc
    43   /// from a given source node to a given target node in a digraph.
    43   /// from a given source node to a given target node in a digraph.
    44   ///
    44   ///
    45   /// In fact, this implementation is the specialization of the
    45   /// In fact, this implementation is the specialization of the
    46   /// \ref CapacityScaling "successive shortest path" algorithm.
    46   /// \ref CapacityScaling "successive shortest path" algorithm.
    47   ///
    47   ///
    48   /// \tparam Digraph The digraph type the algorithm runs on.
    48   /// \tparam GR The digraph type the algorithm runs on.
    49   /// The default value is \c ListDigraph.
    49   /// The default value is \c ListDigraph.
    50   /// \tparam LengthMap The type of the length (cost) map.
    50   /// \tparam LEN The type of the length (cost) map.
    51   /// The default value is <tt>Digraph::ArcMap<int></tt>.
    51   /// The default value is <tt>Digraph::ArcMap<int></tt>.
    52   ///
    52   ///
    53   /// \warning Length values should be \e non-negative \e integers.
    53   /// \warning Length values should be \e non-negative \e integers.
    54   ///
    54   ///
    55   /// \note For finding node-disjoint paths this algorithm can be used
    55   /// \note For finding node-disjoint paths this algorithm can be used
    56   /// with \ref SplitNodes.
    56   /// with \ref SplitNodes.
    57 #ifdef DOXYGEN
    57 #ifdef DOXYGEN
    58   template <typename Digraph, typename LengthMap>
    58   template <typename GR, typename LEN>
    59 #else
    59 #else
    60   template < typename Digraph = ListDigraph,
    60   template < typename GR = ListDigraph,
    61              typename LengthMap = typename Digraph::template ArcMap<int> >
    61              typename LEN = typename GR::template ArcMap<int> >
    62 #endif
    62 #endif
    63   class Suurballe
    63   class Suurballe
    64   {
    64   {
    65     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    65     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    66 
    66 
       
    67     typedef ConstMap<Arc, int> ConstArcMap;
       
    68     typedef typename GR::template NodeMap<Arc> PredMap;
       
    69 
       
    70   public:
       
    71 
       
    72     /// The type of the digraph the algorithm runs on.
       
    73     typedef GR Digraph;
       
    74     /// The type of the length map.
       
    75     typedef LEN LengthMap;
       
    76     /// The type of the lengths.
    67     typedef typename LengthMap::Value Length;
    77     typedef typename LengthMap::Value Length;
    68     typedef ConstMap<Arc, int> ConstArcMap;
       
    69     typedef typename Digraph::template NodeMap<Arc> PredMap;
       
    70 
       
    71   public:
       
    72 
       
    73     /// The type of the flow map.
    78     /// The type of the flow map.
    74     typedef typename Digraph::template ArcMap<int> FlowMap;
    79     typedef typename Digraph::template ArcMap<int> FlowMap;
    75     /// The type of the potential map.
    80     /// The type of the potential map.
    76     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    81     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    77     /// The type of the path structures.
    82     /// The type of the path structures.
   254     /// This function sets the flow map.
   259     /// This function sets the flow map.
   255     ///
   260     ///
   256     /// The found flow contains only 0 and 1 values. It is the union of
   261     /// The found flow contains only 0 and 1 values. It is the union of
   257     /// the found arc-disjoint paths.
   262     /// the found arc-disjoint paths.
   258     ///
   263     ///
   259     /// \return \c (*this)
   264     /// \return <tt>(*this)</tt>
   260     Suurballe& flowMap(FlowMap &map) {
   265     Suurballe& flowMap(FlowMap &map) {
   261       if (_local_flow) {
   266       if (_local_flow) {
   262         delete _flow;
   267         delete _flow;
   263         _local_flow = false;
   268         _local_flow = false;
   264       }
   269       }
   271     /// This function sets the potential map.
   276     /// This function sets the potential map.
   272     ///
   277     ///
   273     /// The potentials provide the dual solution of the underlying
   278     /// The potentials provide the dual solution of the underlying
   274     /// minimum cost flow problem.
   279     /// minimum cost flow problem.
   275     ///
   280     ///
   276     /// \return \c (*this)
   281     /// \return <tt>(*this)</tt>
   277     Suurballe& potentialMap(PotentialMap &map) {
   282     Suurballe& potentialMap(PotentialMap &map) {
   278       if (_local_potential) {
   283       if (_local_potential) {
   279         delete _potential;
   284         delete _potential;
   280         _local_potential = false;
   285         _local_potential = false;
   281       }
   286       }
   456     }
   461     }
   457 
   462 
   458     /// \brief Return the total length (cost) of the found paths (flow).
   463     /// \brief Return the total length (cost) of the found paths (flow).
   459     ///
   464     ///
   460     /// This function returns the total length (cost) of the found paths
   465     /// This function returns the total length (cost) of the found paths
   461     /// (flow). The complexity of the function is \f$ O(e) \f$.
   466     /// (flow). The complexity of the function is O(e).
   462     ///
   467     ///
   463     /// \pre \ref run() or \ref findFlow() must be called before using
   468     /// \pre \ref run() or \ref findFlow() must be called before using
   464     /// this function.
   469     /// this function.
   465     Length totalLength() const {
   470     Length totalLength() const {
   466       Length c = 0;
   471       Length c = 0;