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. |
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 } |