1.1 --- a/lemon/suurballe.h Fri Oct 16 01:06:16 2009 +0200
1.2 +++ b/lemon/suurballe.h Fri Oct 16 02:32:30 2009 +0200
1.3 @@ -29,6 +29,7 @@
1.4 #include <lemon/bin_heap.h>
1.5 #include <lemon/path.h>
1.6 #include <lemon/list_graph.h>
1.7 +#include <lemon/dijkstra.h>
1.8 #include <lemon/maps.h>
1.9
1.10 namespace lemon {
1.11 @@ -97,6 +98,9 @@
1.12
1.13 private:
1.14
1.15 + typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.16 + typedef BinHeap<Length, HeapCrossRef> Heap;
1.17 +
1.18 // ResidualDijkstra is a special implementation of the
1.19 // Dijkstra algorithm for finding shortest paths in the
1.20 // residual network with respect to the reduced arc lengths
1.21 @@ -104,9 +108,6 @@
1.22 // distance of the nodes.
1.23 class ResidualDijkstra
1.24 {
1.25 - typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.26 - typedef BinHeap<Length, HeapCrossRef> Heap;
1.27 -
1.28 private:
1.29
1.30 const Digraph &_graph;
1.31 @@ -278,6 +279,11 @@
1.32
1.33 // The pred arc map
1.34 PredMap _pred;
1.35 +
1.36 + // Data for full init
1.37 + PotentialMap *_init_dist;
1.38 + PredMap *_init_pred;
1.39 + bool _full_init;
1.40
1.41 public:
1.42
1.43 @@ -290,13 +296,16 @@
1.44 Suurballe( const Digraph &graph,
1.45 const LengthMap &length ) :
1.46 _graph(graph), _length(length), _flow(0), _local_flow(false),
1.47 - _potential(0), _local_potential(false), _pred(graph)
1.48 + _potential(0), _local_potential(false), _pred(graph),
1.49 + _init_dist(0), _init_pred(0)
1.50 {}
1.51
1.52 /// Destructor.
1.53 ~Suurballe() {
1.54 if (_local_flow) delete _flow;
1.55 if (_local_potential) delete _potential;
1.56 + delete _init_dist;
1.57 + delete _init_pred;
1.58 }
1.59
1.60 /// \brief Set the flow map.
1.61 @@ -341,10 +350,13 @@
1.62
1.63 /// \name Execution Control
1.64 /// The simplest way to execute the algorithm is to call the run()
1.65 - /// function.
1.66 - /// \n
1.67 + /// function.\n
1.68 + /// If you need to execute the algorithm many times using the same
1.69 + /// source node, then you may call fullInit() once and start()
1.70 + /// for each target node.\n
1.71 /// If you only need the flow that is the union of the found
1.72 - /// arc-disjoint paths, you may call init() and findFlow().
1.73 + /// arc-disjoint paths, then you may call findFlow() instead of
1.74 + /// start().
1.75
1.76 /// @{
1.77
1.78 @@ -364,19 +376,17 @@
1.79 /// just a shortcut of the following code.
1.80 /// \code
1.81 /// s.init(s);
1.82 - /// s.findFlow(t, k);
1.83 - /// s.findPaths();
1.84 + /// s.start(t, k);
1.85 /// \endcode
1.86 int run(const Node& s, const Node& t, int k = 2) {
1.87 init(s);
1.88 - findFlow(t, k);
1.89 - findPaths();
1.90 + start(t, k);
1.91 return _path_num;
1.92 }
1.93
1.94 /// \brief Initialize the algorithm.
1.95 ///
1.96 - /// This function initializes the algorithm.
1.97 + /// This function initializes the algorithm with the given source node.
1.98 ///
1.99 /// \param s The source node.
1.100 void init(const Node& s) {
1.101 @@ -391,8 +401,63 @@
1.102 _potential = new PotentialMap(_graph);
1.103 _local_potential = true;
1.104 }
1.105 - for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
1.106 - for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
1.107 + _full_init = false;
1.108 + }
1.109 +
1.110 + /// \brief Initialize the algorithm and perform Dijkstra.
1.111 + ///
1.112 + /// This function initializes the algorithm and performs a full
1.113 + /// Dijkstra search from the given source node. It makes consecutive
1.114 + /// executions of \ref start() "start(t, k)" faster, since they
1.115 + /// have to perform %Dijkstra only k-1 times.
1.116 + ///
1.117 + /// This initialization is usually worth using instead of \ref init()
1.118 + /// if the algorithm is executed many times using the same source node.
1.119 + ///
1.120 + /// \param s The source node.
1.121 + void fullInit(const Node& s) {
1.122 + // Initialize maps
1.123 + init(s);
1.124 + if (!_init_dist) {
1.125 + _init_dist = new PotentialMap(_graph);
1.126 + }
1.127 + if (!_init_pred) {
1.128 + _init_pred = new PredMap(_graph);
1.129 + }
1.130 +
1.131 + // Run a full Dijkstra
1.132 + typename Dijkstra<Digraph, LengthMap>
1.133 + ::template SetStandardHeap<Heap>
1.134 + ::template SetDistMap<PotentialMap>
1.135 + ::template SetPredMap<PredMap>
1.136 + ::Create dijk(_graph, _length);
1.137 + dijk.distMap(*_init_dist).predMap(*_init_pred);
1.138 + dijk.run(s);
1.139 +
1.140 + _full_init = true;
1.141 + }
1.142 +
1.143 + /// \brief Execute the algorithm.
1.144 + ///
1.145 + /// This function executes the algorithm.
1.146 + ///
1.147 + /// \param t The target node.
1.148 + /// \param k The number of paths to be found.
1.149 + ///
1.150 + /// \return \c k if there are at least \c k arc-disjoint paths from
1.151 + /// \c s to \c t in the digraph. Otherwise it returns the number of
1.152 + /// arc-disjoint paths found.
1.153 + ///
1.154 + /// \note Apart from the return value, <tt>s.start(t, k)</tt> is
1.155 + /// just a shortcut of the following code.
1.156 + /// \code
1.157 + /// s.findFlow(t, k);
1.158 + /// s.findPaths();
1.159 + /// \endcode
1.160 + int start(const Node& t, int k = 2) {
1.161 + findFlow(t, k);
1.162 + findPaths();
1.163 + return _path_num;
1.164 }
1.165
1.166 /// \brief Execute the algorithm to find an optimal flow.
1.167 @@ -412,9 +477,30 @@
1.168 int findFlow(const Node& t, int k = 2) {
1.169 _t = t;
1.170 ResidualDijkstra dijkstra(*this);
1.171 +
1.172 + // Initialization
1.173 + for (ArcIt e(_graph); e != INVALID; ++e) {
1.174 + (*_flow)[e] = 0;
1.175 + }
1.176 + if (_full_init) {
1.177 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.178 + (*_potential)[n] = (*_init_dist)[n];
1.179 + }
1.180 + Node u = _t;
1.181 + Arc e;
1.182 + while ((e = (*_init_pred)[u]) != INVALID) {
1.183 + (*_flow)[e] = 1;
1.184 + u = _graph.source(e);
1.185 + }
1.186 + _path_num = 1;
1.187 + } else {
1.188 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.189 + (*_potential)[n] = 0;
1.190 + }
1.191 + _path_num = 0;
1.192 + }
1.193
1.194 // Find shortest paths
1.195 - _path_num = 0;
1.196 while (_path_num < k) {
1.197 // Run Dijkstra
1.198 if (!dijkstra.run(_path_num)) break;
2.1 --- a/test/suurballe_test.cc Fri Oct 16 01:06:16 2009 +0200
2.2 +++ b/test/suurballe_test.cc Fri Oct 16 02:32:30 2009 +0200
2.3 @@ -101,6 +101,9 @@
2.4 k = suurb_test.run(n, n);
2.5 k = suurb_test.run(n, n, k);
2.6 suurb_test.init(n);
2.7 + suurb_test.fullInit(n);
2.8 + suurb_test.start(n);
2.9 + suurb_test.start(n, k);
2.10 k = suurb_test.findFlow(n);
2.11 k = suurb_test.findFlow(n, k);
2.12 suurb_test.findPaths();