r947:abb95d48e89e
Fri, 16 Oct 2009 09:35:46
[Not Reviewed]
0 comments (0 inline)
0
2
0
138
20
| ... | ... |
@@ -29,16 +29,59 @@ |
| 29 | 29 |
#include <lemon/bin_heap.h> |
| 30 | 30 |
#include <lemon/path.h> |
| 31 | 31 |
#include <lemon/list_graph.h> |
| 32 | 32 |
#include <lemon/dijkstra.h> |
| 33 | 33 |
#include <lemon/maps.h> |
| 34 | 34 |
|
| 35 | 35 |
namespace lemon {
|
| 36 | 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 |
}; |
|
| 79 |
|
|
| 37 | 80 |
/// \addtogroup shortest_path |
| 38 | 81 |
/// @{
|
| 39 | 82 |
|
| 40 | 83 |
/// \brief Algorithm for finding arc-disjoint paths between two nodes |
| 41 | 84 |
/// having minimum total length. |
| 42 | 85 |
/// |
| 43 | 86 |
/// \ref lemon::Suurballe "Suurballe" implements an algorithm for |
| 44 | 87 |
/// finding arc-disjoint paths having minimum total length (cost) |
| ... | ... |
@@ -56,56 +99,54 @@ |
| 56 | 99 |
/// \tparam LEN The type of the length map. |
| 57 | 100 |
/// The default value is <tt>GR::ArcMap<int></tt>. |
| 58 | 101 |
/// |
| 59 | 102 |
/// \warning Length values should be \e non-negative. |
| 60 | 103 |
/// |
| 61 | 104 |
/// \note For finding \e node-disjoint paths, this algorithm can be used |
| 62 | 105 |
/// along with the \ref SplitNodes adaptor. |
| 63 | 106 |
#ifdef DOXYGEN |
| 64 |
template <typename GR, typename LEN> |
|
| 107 |
template <typename GR, typename LEN, typename TR> |
|
| 65 | 108 |
#else |
| 66 | 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 | 112 |
#endif |
| 69 | 113 |
class Suurballe |
| 70 | 114 |
{
|
| 71 | 115 |
TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
| 72 | 116 |
|
| 73 | 117 |
typedef ConstMap<Arc, int> ConstArcMap; |
| 74 | 118 |
typedef typename GR::template NodeMap<Arc> PredMap; |
| 75 | 119 |
|
| 76 | 120 |
public: |
| 77 | 121 |
|
| 78 |
/// The type of the digraph the algorithm runs on. |
|
| 79 |
typedef GR Digraph; |
|
| 122 |
/// The type of the digraph. |
|
| 123 |
typedef typename TR::Digraph Digraph; |
|
| 80 | 124 |
/// The type of the length map. |
| 81 |
typedef |
|
| 125 |
typedef typename TR::LengthMap LengthMap; |
|
| 82 | 126 |
/// The type of the lengths. |
| 83 |
typedef typename LengthMap::Value Length; |
|
| 84 |
#ifdef DOXYGEN |
|
| 127 |
typedef typename TR::Length Length; |
|
| 128 |
|
|
| 85 | 129 |
/// The type of the flow map. |
| 86 |
typedef |
|
| 130 |
typedef typename TR::FlowMap FlowMap; |
|
| 87 | 131 |
/// The type of the potential map. |
| 88 |
typedef GR::NodeMap<Length> 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 |
|
|
| 132 |
typedef typename TR::PotentialMap PotentialMap; |
|
| 133 |
/// The type of the path structures. |
|
| 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; |
|
| 95 | 139 |
|
| 96 |
/// The type of the path structures. |
|
| 97 |
typedef SimplePath<GR> Path; |
|
| 140 |
/// The \ref SuurballeDefaultTraits "traits class" of the algorithm. |
|
| 141 |
typedef TR Traits; |
|
| 98 | 142 |
|
| 99 | 143 |
private: |
| 100 | 144 |
|
| 101 |
typedef typename Digraph::template NodeMap<int> HeapCrossRef; |
|
| 102 |
typedef BinHeap<Length, HeapCrossRef> Heap; |
|
| 103 |
|
|
| 104 | 145 |
// ResidualDijkstra is a special implementation of the |
| 105 | 146 |
// Dijkstra algorithm for finding shortest paths in the |
| 106 | 147 |
// residual network with respect to the reduced arc lengths |
| 107 | 148 |
// and modifying the node potentials according to the |
| 108 | 149 |
// distance of the nodes. |
| 109 | 150 |
class ResidualDijkstra |
| 110 | 151 |
{
|
| 111 | 152 |
private: |
| ... | ... |
@@ -249,16 +290,93 @@ |
| 249 | 290 |
Length t_dist = heap.prio(); |
| 250 | 291 |
for (int i = 0; i < int(_proc_nodes.size()); ++i) |
| 251 | 292 |
_pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist; |
| 252 | 293 |
return true; |
| 253 | 294 |
} |
| 254 | 295 |
|
| 255 | 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 | 375 |
private: |
| 258 | 376 |
|
| 259 | 377 |
// The digraph the algorithm runs on |
| 260 | 378 |
const Digraph &_graph; |
| 261 | 379 |
// The length map |
| 262 | 380 |
const LengthMap &_length; |
| 263 | 381 |
|
| 264 | 382 |
// Arc map of the current flow |
| ... | ... |
@@ -18,16 +18,17 @@ |
| 18 | 18 |
|
| 19 | 19 |
#include <iostream> |
| 20 | 20 |
|
| 21 | 21 |
#include <lemon/list_graph.h> |
| 22 | 22 |
#include <lemon/lgf_reader.h> |
| 23 | 23 |
#include <lemon/path.h> |
| 24 | 24 |
#include <lemon/suurballe.h> |
| 25 | 25 |
#include <lemon/concepts/digraph.h> |
| 26 |
#include <lemon/concepts/heap.h> |
|
| 26 | 27 |
|
| 27 | 28 |
#include "test_tools.h" |
| 28 | 29 |
|
| 29 | 30 |
using namespace lemon; |
| 30 | 31 |
|
| 31 | 32 |
char test_lgf[] = |
| 32 | 33 |
"@nodes\n" |
| 33 | 34 |
"label\n" |
| ... | ... |
@@ -76,17 +77,23 @@ |
| 76 | 77 |
{
|
| 77 | 78 |
typedef int VType; |
| 78 | 79 |
typedef concepts::Digraph Digraph; |
| 79 | 80 |
|
| 80 | 81 |
typedef Digraph::Node Node; |
| 81 | 82 |
typedef Digraph::Arc Arc; |
| 82 | 83 |
typedef concepts::ReadMap<Arc, VType> LengthMap; |
| 83 | 84 |
|
| 84 |
typedef Suurballe<Digraph, LengthMap> |
|
| 85 |
typedef Suurballe<Digraph, LengthMap> ST; |
|
| 86 |
typedef Suurballe<Digraph, LengthMap> |
|
| 87 |
::SetFlowMap<ST::FlowMap> |
|
| 88 |
::SetPotentialMap<ST::PotentialMap> |
|
| 89 |
::SetPath<SimplePath<Digraph> > |
|
| 90 |
::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > > |
|
| 91 |
::Create SuurballeType; |
|
| 85 | 92 |
|
| 86 | 93 |
Digraph g; |
| 87 | 94 |
Node n; |
| 88 | 95 |
Arc e; |
| 89 | 96 |
LengthMap len; |
| 90 | 97 |
SuurballeType::FlowMap flow(g); |
| 91 | 98 |
SuurballeType::PotentialMap pi(g); |
| 92 | 99 |
|
0 comments (0 inline)