gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 5 0
merge default
0 files changed with 132 insertions and 133 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
... ...
@@ -185,184 +185,183 @@
185 185
    //Pointer to the map of reached status of the nodes.
186 186
    ReachedMap *_reached;
187 187
    //Indicates if _reached is locally allocated (true) or not.
188 188
    bool local_reached;
189 189
    //Pointer to the map of processed status of the nodes.
190 190
    ProcessedMap *_processed;
191 191
    //Indicates if _processed is locally allocated (true) or not.
192 192
    bool local_processed;
193 193

	
194 194
    std::vector<typename Digraph::Node> _queue;
195 195
    int _queue_head,_queue_tail,_queue_next_dist;
196 196
    int _curr_dist;
197 197

	
198 198
    ///Creates the maps if necessary.
199 199
    ///\todo Better memory allocation (instead of new).
200 200
    void create_maps()
201 201
    {
202 202
      if(!_pred) {
203 203
        local_pred = true;
204 204
        _pred = Traits::createPredMap(*G);
205 205
      }
206 206
      if(!_dist) {
207 207
        local_dist = true;
208 208
        _dist = Traits::createDistMap(*G);
209 209
      }
210 210
      if(!_reached) {
211 211
        local_reached = true;
212 212
        _reached = Traits::createReachedMap(*G);
213 213
      }
214 214
      if(!_processed) {
215 215
        local_processed = true;
216 216
        _processed = Traits::createProcessedMap(*G);
217 217
      }
218 218
    }
219 219

	
220 220
  protected:
221 221

	
222 222
    Bfs() {}
223 223

	
224 224
  public:
225 225

	
226 226
    typedef Bfs Create;
227 227

	
228 228
    ///\name Named template parameters
229 229

	
230 230
    ///@{
231 231

	
232 232
    template <class T>
233
    struct DefPredMapTraits : public Traits {
233
    struct SetPredMapTraits : public Traits {
234 234
      typedef T PredMap;
235 235
      static PredMap *createPredMap(const Digraph &)
236 236
      {
237 237
        throw UninitializedParameter();
238 238
      }
239 239
    };
240 240
    ///\brief \ref named-templ-param "Named parameter" for setting
241 241
    ///\ref PredMap type.
242 242
    ///
243 243
    ///\ref named-templ-param "Named parameter" for setting
244 244
    ///\ref PredMap type.
245 245
    template <class T>
246
    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
247
      typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
246
    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
247
      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
248 248
    };
249 249

	
250 250
    template <class T>
251
    struct DefDistMapTraits : public Traits {
251
    struct SetDistMapTraits : public Traits {
252 252
      typedef T DistMap;
253 253
      static DistMap *createDistMap(const Digraph &)
254 254
      {
255 255
        throw UninitializedParameter();
256 256
      }
257 257
    };
258 258
    ///\brief \ref named-templ-param "Named parameter" for setting
259 259
    ///\ref DistMap type.
260 260
    ///
261 261
    ///\ref named-templ-param "Named parameter" for setting
262 262
    ///\ref DistMap type.
263 263
    template <class T>
264
    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
265
      typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
264
    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
265
      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
266 266
    };
267 267

	
268 268
    template <class T>
269
    struct DefReachedMapTraits : public Traits {
269
    struct SetReachedMapTraits : public Traits {
270 270
      typedef T ReachedMap;
271 271
      static ReachedMap *createReachedMap(const Digraph &)
272 272
      {
273 273
        throw UninitializedParameter();
274 274
      }
275 275
    };
276 276
    ///\brief \ref named-templ-param "Named parameter" for setting
277 277
    ///\ref ReachedMap type.
278 278
    ///
279 279
    ///\ref named-templ-param "Named parameter" for setting
280 280
    ///\ref ReachedMap type.
281 281
    template <class T>
282
    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
283
      typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
282
    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
283
      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
284 284
    };
285 285

	
286 286
    template <class T>
287
    struct DefProcessedMapTraits : public Traits {
287
    struct SetProcessedMapTraits : public Traits {
288 288
      typedef T ProcessedMap;
289 289
      static ProcessedMap *createProcessedMap(const Digraph &)
290 290
      {
291 291
        throw UninitializedParameter();
292 292
      }
293 293
    };
294 294
    ///\brief \ref named-templ-param "Named parameter" for setting
295 295
    ///\ref ProcessedMap type.
296 296
    ///
297 297
    ///\ref named-templ-param "Named parameter" for setting
298 298
    ///\ref ProcessedMap type.
299 299
    template <class T>
300
    struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
301
      typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
300
    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
301
      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
302 302
    };
303 303

	
304
    struct DefDigraphProcessedMapTraits : public Traits {
304
    struct SetStandardProcessedMapTraits : public Traits {
305 305
      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
306 306
      static ProcessedMap *createProcessedMap(const Digraph &g)
307 307
      {
308 308
        return new ProcessedMap(g);
309 309
      }
310 310
    };
311 311
    ///\brief \ref named-templ-param "Named parameter" for setting
312 312
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
313 313
    ///
314 314
    ///\ref named-templ-param "Named parameter" for setting
315 315
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
316 316
    ///If you don't set it explicitly, it will be automatically allocated.
317
    template <class T>
318
    struct DefProcessedMapToBeDefaultMap :
319
      public Bfs< Digraph, DefDigraphProcessedMapTraits> {
320
      typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
317
    struct SetStandardProcessedMap :
318
      public Bfs< Digraph, SetStandardProcessedMapTraits > {
319
      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
321 320
    };
322 321

	
323 322
    ///@}
324 323

	
325 324
  public:
326 325

	
327 326
    ///Constructor.
328 327

	
329 328
    ///Constructor.
330 329
    ///\param g The digraph the algorithm runs on.
331 330
    Bfs(const Digraph &g) :
332 331
      G(&g),
333 332
      _pred(NULL), local_pred(false),
334 333
      _dist(NULL), local_dist(false),
335 334
      _reached(NULL), local_reached(false),
336 335
      _processed(NULL), local_processed(false)
337 336
    { }
338 337

	
339 338
    ///Destructor.
340 339
    ~Bfs()
341 340
    {
342 341
      if(local_pred) delete _pred;
343 342
      if(local_dist) delete _dist;
344 343
      if(local_reached) delete _reached;
345 344
      if(local_processed) delete _processed;
346 345
    }
347 346

	
348 347
    ///Sets the map that stores the predecessor arcs.
349 348

	
350 349
    ///Sets the map that stores the predecessor arcs.
351 350
    ///If you don't use this function before calling \ref run(),
352 351
    ///it will allocate one. The destructor deallocates this
353 352
    ///automatically allocated map, of course.
354 353
    ///\return <tt> (*this) </tt>
355 354
    Bfs &predMap(PredMap &m)
356 355
    {
357 356
      if(local_pred) {
358 357
        delete _pred;
359 358
        local_pred=false;
360 359
      }
361 360
      _pred = &m;
362 361
      return *this;
363 362
    }
364 363

	
365 364
    ///Sets the map that indicates which nodes are reached.
366 365

	
367 366
    ///Sets the map that indicates which nodes are reached.
368 367
    ///If you don't use this function before calling \ref run(),
... ...
@@ -1020,165 +1019,165 @@
1020 1019
    BfsWizard(const Digraph &g, Node s=INVALID) :
1021 1020
      TR(g,s) {}
1022 1021

	
1023 1022
    ///Copy constructor
1024 1023
    BfsWizard(const TR &b) : TR(b) {}
1025 1024

	
1026 1025
    ~BfsWizard() {}
1027 1026

	
1028 1027
    ///Runs BFS algorithm from a source node.
1029 1028

	
1030 1029
    ///Runs BFS algorithm from a source node.
1031 1030
    ///The node can be given with the \ref source() function.
1032 1031
    void run()
1033 1032
    {
1034 1033
      if(Base::_source==INVALID) throw UninitializedParameter();
1035 1034
      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1036 1035
      if(Base::_reached)
1037 1036
        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1038 1037
      if(Base::_processed)
1039 1038
        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1040 1039
      if(Base::_pred)
1041 1040
        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1042 1041
      if(Base::_dist)
1043 1042
        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1044 1043
      alg.run(Base::_source);
1045 1044
    }
1046 1045

	
1047 1046
    ///Runs BFS algorithm from the given node.
1048 1047

	
1049 1048
    ///Runs BFS algorithm from the given node.
1050 1049
    ///\param s is the given source.
1051 1050
    void run(Node s)
1052 1051
    {
1053 1052
      Base::_source=s;
1054 1053
      run();
1055 1054
    }
1056 1055

	
1057 1056
    /// Sets the source node, from which the Bfs algorithm runs.
1058 1057

	
1059 1058
    /// Sets the source node, from which the Bfs algorithm runs.
1060 1059
    /// \param s is the source node.
1061 1060
    BfsWizard<TR> &source(Node s)
1062 1061
    {
1063 1062
      Base::_source=s;
1064 1063
      return *this;
1065 1064
    }
1066 1065

	
1067 1066
    template<class T>
1068
    struct DefPredMapBase : public Base {
1067
    struct SetPredMapBase : public Base {
1069 1068
      typedef T PredMap;
1070 1069
      static PredMap *createPredMap(const Digraph &) { return 0; };
1071
      DefPredMapBase(const TR &b) : TR(b) {}
1070
      SetPredMapBase(const TR &b) : TR(b) {}
1072 1071
    };
1073 1072
    ///\brief \ref named-templ-param "Named parameter"
1074 1073
    ///for setting \ref PredMap object.
1075 1074
    ///
1076 1075
    /// \ref named-templ-param "Named parameter"
1077 1076
    ///for setting \ref PredMap object.
1078 1077
    template<class T>
1079
    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1078
    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1080 1079
    {
1081 1080
      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1082
      return BfsWizard<DefPredMapBase<T> >(*this);
1081
      return BfsWizard<SetPredMapBase<T> >(*this);
1083 1082
    }
1084 1083

	
1085 1084
    template<class T>
1086
    struct DefReachedMapBase : public Base {
1085
    struct SetReachedMapBase : public Base {
1087 1086
      typedef T ReachedMap;
1088 1087
      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1089
      DefReachedMapBase(const TR &b) : TR(b) {}
1088
      SetReachedMapBase(const TR &b) : TR(b) {}
1090 1089
    };
1091 1090
    ///\brief \ref named-templ-param "Named parameter"
1092 1091
    ///for setting \ref ReachedMap object.
1093 1092
    ///
1094 1093
    /// \ref named-templ-param "Named parameter"
1095 1094
    ///for setting \ref ReachedMap object.
1096 1095
    template<class T>
1097
    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1096
    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1098 1097
    {
1099 1098
      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1100
      return BfsWizard<DefReachedMapBase<T> >(*this);
1099
      return BfsWizard<SetReachedMapBase<T> >(*this);
1101 1100
    }
1102 1101

	
1103 1102
    template<class T>
1104
    struct DefProcessedMapBase : public Base {
1103
    struct SetProcessedMapBase : public Base {
1105 1104
      typedef T ProcessedMap;
1106 1105
      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1107
      DefProcessedMapBase(const TR &b) : TR(b) {}
1106
      SetProcessedMapBase(const TR &b) : TR(b) {}
1108 1107
    };
1109 1108
    ///\brief \ref named-templ-param "Named parameter"
1110 1109
    ///for setting \ref ProcessedMap object.
1111 1110
    ///
1112 1111
    /// \ref named-templ-param "Named parameter"
1113 1112
    ///for setting \ref ProcessedMap object.
1114 1113
    template<class T>
1115
    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1114
    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1116 1115
    {
1117 1116
      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1118
      return BfsWizard<DefProcessedMapBase<T> >(*this);
1117
      return BfsWizard<SetProcessedMapBase<T> >(*this);
1119 1118
    }
1120 1119

	
1121 1120
    template<class T>
1122
    struct DefDistMapBase : public Base {
1121
    struct SetDistMapBase : public Base {
1123 1122
      typedef T DistMap;
1124 1123
      static DistMap *createDistMap(const Digraph &) { return 0; };
1125
      DefDistMapBase(const TR &b) : TR(b) {}
1124
      SetDistMapBase(const TR &b) : TR(b) {}
1126 1125
    };
1127 1126
    ///\brief \ref named-templ-param "Named parameter"
1128 1127
    ///for setting \ref DistMap object.
1129 1128
    ///
1130 1129
    /// \ref named-templ-param "Named parameter"
1131 1130
    ///for setting \ref DistMap object.
1132 1131
    template<class T>
1133
    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1132
    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1134 1133
    {
1135 1134
      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1136
      return BfsWizard<DefDistMapBase<T> >(*this);
1135
      return BfsWizard<SetDistMapBase<T> >(*this);
1137 1136
    }
1138 1137

	
1139 1138
  };
1140 1139

	
1141 1140
  ///Function type interface for Bfs algorithm.
1142 1141

	
1143 1142
  /// \ingroup search
1144 1143
  ///Function type interface for Bfs algorithm.
1145 1144
  ///
1146 1145
  ///This function also has several
1147 1146
  ///\ref named-templ-func-param "named parameters",
1148 1147
  ///they are declared as the members of class \ref BfsWizard.
1149 1148
  ///The following
1150 1149
  ///example shows how to use these parameters.
1151 1150
  ///\code
1152 1151
  ///  bfs(g,source).predMap(preds).run();
1153 1152
  ///\endcode
1154 1153
  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1155 1154
  ///to the end of the parameter list.
1156 1155
  ///\sa BfsWizard
1157 1156
  ///\sa Bfs
1158 1157
  template<class GR>
1159 1158
  BfsWizard<BfsWizardBase<GR> >
1160 1159
  bfs(const GR &g,typename GR::Node s=INVALID)
1161 1160
  {
1162 1161
    return BfsWizard<BfsWizardBase<GR> >(g,s);
1163 1162
  }
1164 1163

	
1165 1164
#ifdef DOXYGEN
1166 1165
  /// \brief Visitor class for BFS.
1167 1166
  ///
1168 1167
  /// This class defines the interface of the BfsVisit events, and
1169 1168
  /// it could be the base of a real visitor class.
1170 1169
  template <typename _Digraph>
1171 1170
  struct BfsVisitor {
1172 1171
    typedef _Digraph Digraph;
1173 1172
    typedef typename Digraph::Arc Arc;
1174 1173
    typedef typename Digraph::Node Node;
1175 1174
    /// \brief Called for the source node(s) of the BFS.
1176 1175
    ///
1177 1176
    /// This function is called for the source node(s) of the BFS.
1178 1177
    void start(const Node& node) {}
1179 1178
    /// \brief Called when a node is reached first time.
1180 1179
    ///
1181 1180
    /// This function is called when a node is reached first time.
1182 1181
    void reach(const Node& node) {}
1183 1182
    /// \brief Called when a node is processed.
1184 1183
    ///
... ...
@@ -1309,110 +1308,110 @@
1309 1308
    typedef typename Traits::Digraph Digraph;
1310 1309

	
1311 1310
    ///The visitor type used by the algorithm.
1312 1311
    typedef _Visitor Visitor;
1313 1312

	
1314 1313
    ///The type of the map that indicates which nodes are reached.
1315 1314
    typedef typename Traits::ReachedMap ReachedMap;
1316 1315

	
1317 1316
  private:
1318 1317

	
1319 1318
    typedef typename Digraph::Node Node;
1320 1319
    typedef typename Digraph::NodeIt NodeIt;
1321 1320
    typedef typename Digraph::Arc Arc;
1322 1321
    typedef typename Digraph::OutArcIt OutArcIt;
1323 1322

	
1324 1323
    //Pointer to the underlying digraph.
1325 1324
    const Digraph *_digraph;
1326 1325
    //Pointer to the visitor object.
1327 1326
    Visitor *_visitor;
1328 1327
    //Pointer to the map of reached status of the nodes.
1329 1328
    ReachedMap *_reached;
1330 1329
    //Indicates if _reached is locally allocated (true) or not.
1331 1330
    bool local_reached;
1332 1331

	
1333 1332
    std::vector<typename Digraph::Node> _list;
1334 1333
    int _list_front, _list_back;
1335 1334

	
1336 1335
    ///Creates the maps if necessary.
1337 1336
    ///\todo Better memory allocation (instead of new).
1338 1337
    void create_maps() {
1339 1338
      if(!_reached) {
1340 1339
        local_reached = true;
1341 1340
        _reached = Traits::createReachedMap(*_digraph);
1342 1341
      }
1343 1342
    }
1344 1343

	
1345 1344
  protected:
1346 1345

	
1347 1346
    BfsVisit() {}
1348 1347

	
1349 1348
  public:
1350 1349

	
1351 1350
    typedef BfsVisit Create;
1352 1351

	
1353 1352
    /// \name Named template parameters
1354 1353

	
1355 1354
    ///@{
1356 1355
    template <class T>
1357
    struct DefReachedMapTraits : public Traits {
1356
    struct SetReachedMapTraits : public Traits {
1358 1357
      typedef T ReachedMap;
1359 1358
      static ReachedMap *createReachedMap(const Digraph &digraph) {
1360 1359
        throw UninitializedParameter();
1361 1360
      }
1362 1361
    };
1363 1362
    /// \brief \ref named-templ-param "Named parameter" for setting
1364 1363
    /// ReachedMap type.
1365 1364
    ///
1366 1365
    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1367 1366
    template <class T>
1368
    struct DefReachedMap : public BfsVisit< Digraph, Visitor,
1369
                                            DefReachedMapTraits<T> > {
1370
      typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1367
    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
1368
                                            SetReachedMapTraits<T> > {
1369
      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1371 1370
    };
1372 1371
    ///@}
1373 1372

	
1374 1373
  public:
1375 1374

	
1376 1375
    /// \brief Constructor.
1377 1376
    ///
1378 1377
    /// Constructor.
1379 1378
    ///
1380 1379
    /// \param digraph The digraph the algorithm runs on.
1381 1380
    /// \param visitor The visitor object of the algorithm.
1382 1381
    BfsVisit(const Digraph& digraph, Visitor& visitor)
1383 1382
      : _digraph(&digraph), _visitor(&visitor),
1384 1383
        _reached(0), local_reached(false) {}
1385 1384

	
1386 1385
    /// \brief Destructor.
1387 1386
    ~BfsVisit() {
1388 1387
      if(local_reached) delete _reached;
1389 1388
    }
1390 1389

	
1391 1390
    /// \brief Sets the map that indicates which nodes are reached.
1392 1391
    ///
1393 1392
    /// Sets the map that indicates which nodes are reached.
1394 1393
    /// If you don't use this function before calling \ref run(),
1395 1394
    /// it will allocate one. The destructor deallocates this
1396 1395
    /// automatically allocated map, of course.
1397 1396
    /// \return <tt> (*this) </tt>
1398 1397
    BfsVisit &reachedMap(ReachedMap &m) {
1399 1398
      if(local_reached) {
1400 1399
        delete _reached;
1401 1400
        local_reached = false;
1402 1401
      }
1403 1402
      _reached = &m;
1404 1403
      return *this;
1405 1404
    }
1406 1405

	
1407 1406
  public:
1408 1407

	
1409 1408
    /// \name Execution control
1410 1409
    /// The simplest way to execute the algorithm is to use
1411 1410
    /// one of the member functions called \ref lemon::BfsVisit::run()
1412 1411
    /// "run()".
1413 1412
    /// \n
1414 1413
    /// If you need more control on the execution, first you must call
1415 1414
    /// \ref lemon::BfsVisit::init() "init()", then you can add several
1416 1415
    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1417 1416
    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1418 1417
    /// actual path computation.
Ignore white space 6 line context
... ...
@@ -14,143 +14,146 @@
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_BITS_BASE_EXTENDER_H
20 20
#define LEMON_BITS_BASE_EXTENDER_H
21 21

	
22 22
#include <lemon/core.h>
23 23
#include <lemon/error.h>
24 24

	
25 25
#include <lemon/bits/map_extender.h>
26 26
#include <lemon/bits/default_map.h>
27 27

	
28 28
#include <lemon/concept_check.h>
29 29
#include <lemon/concepts/maps.h>
30 30

	
31 31
///\ingroup digraphbits
32 32
///\file
33 33
///\brief Extenders for the digraph types
34 34
namespace lemon {
35 35

	
36 36
  /// \ingroup digraphbits
37 37
  ///
38 38
  /// \brief BaseDigraph to BaseGraph extender
39 39
  template <typename Base>
40 40
  class UndirDigraphExtender : public Base {
41 41

	
42 42
  public:
43 43

	
44 44
    typedef Base Parent;
45 45
    typedef typename Parent::Arc Edge;
46 46
    typedef typename Parent::Node Node;
47 47

	
48 48
    typedef True UndirectedTag;
49 49

	
50 50
    class Arc : public Edge {
51 51
      friend class UndirDigraphExtender;
52 52

	
53 53
    protected:
54 54
      bool forward;
55 55

	
56 56
      Arc(const Edge &ue, bool _forward) :
57 57
        Edge(ue), forward(_forward) {}
58 58

	
59 59
    public:
60 60
      Arc() {}
61 61

	
62
      /// Invalid arc constructor
62
      // Invalid arc constructor
63 63
      Arc(Invalid i) : Edge(i), forward(true) {}
64 64

	
65 65
      bool operator==(const Arc &that) const {
66 66
        return forward==that.forward && Edge(*this)==Edge(that);
67 67
      }
68 68
      bool operator!=(const Arc &that) const {
69 69
        return forward!=that.forward || Edge(*this)!=Edge(that);
70 70
      }
71 71
      bool operator<(const Arc &that) const {
72 72
        return forward<that.forward ||
73 73
          (!(that.forward<forward) && Edge(*this)<Edge(that));
74 74
      }
75 75
    };
76 76

	
77
    /// First node of the edge
78
    Node u(const Edge &e) const {
79
      return Parent::source(e);
80
    }
77 81

	
78

	
79
    using Parent::source;
80

	
81
    /// Source of the given Arc.
82
    /// Source of the given arc
82 83
    Node source(const Arc &e) const {
83 84
      return e.forward ? Parent::source(e) : Parent::target(e);
84 85
    }
85 86

	
86
    using Parent::target;
87
    /// Second node of the edge
88
    Node v(const Edge &e) const {
89
      return Parent::target(e);
90
    }
87 91

	
88
    /// Target of the given Arc.
92
    /// Target of the given arc
89 93
    Node target(const Arc &e) const {
90 94
      return e.forward ? Parent::target(e) : Parent::source(e);
91 95
    }
92 96

	
93 97
    /// \brief Directed arc from an edge.
94 98
    ///
95
    /// Returns a directed arc corresponding to the specified Edge.
96
    /// If the given bool is true the given edge and the
97
    /// returned arc have the same source node.
98
    static Arc direct(const Edge &ue, bool d) {
99
      return Arc(ue, d);
99
    /// Returns a directed arc corresponding to the specified edge.
100
    /// If the given bool is true, the first node of the given edge and
101
    /// the source node of the returned arc are the same.
102
    static Arc direct(const Edge &e, bool d) {
103
      return Arc(e, d);
100 104
    }
101 105

	
102
    /// Returns whether the given directed arc is same orientation as the
103
    /// corresponding edge.
106
    /// Returns whether the given directed arc has the same orientation
107
    /// as the corresponding edge.
104 108
    ///
105 109
    /// \todo reference to the corresponding point of the undirected digraph
106 110
    /// concept. "What does the direction of an edge mean?"
107
    static bool direction(const Arc &e) { return e.forward; }
108

	
111
    static bool direction(const Arc &a) { return a.forward; }
109 112

	
110 113
    using Parent::first;
111 114
    using Parent::next;
112 115

	
113 116
    void first(Arc &e) const {
114 117
      Parent::first(e);
115 118
      e.forward=true;
116 119
    }
117 120

	
118 121
    void next(Arc &e) const {
119 122
      if( e.forward ) {
120 123
        e.forward = false;
121 124
      }
122 125
      else {
123 126
        Parent::next(e);
124 127
        e.forward = true;
125 128
      }
126 129
    }
127 130

	
128 131
    void firstOut(Arc &e, const Node &n) const {
129 132
      Parent::firstIn(e,n);
130 133
      if( Edge(e) != INVALID ) {
131 134
        e.forward = false;
132 135
      }
133 136
      else {
134 137
        Parent::firstOut(e,n);
135 138
        e.forward = true;
136 139
      }
137 140
    }
138 141
    void nextOut(Arc &e) const {
139 142
      if( ! e.forward ) {
140 143
        Node n = Parent::target(e);
141 144
        Parent::nextIn(e);
142 145
        if( Edge(e) == INVALID ) {
143 146
          Parent::firstOut(e, n);
144 147
          e.forward = true;
145 148
        }
146 149
      }
147 150
      else {
148 151
        Parent::nextOut(e);
149 152
      }
150 153
    }
151 154

	
152 155
    void firstIn(Arc &e, const Node &n) const {
153 156
      Parent::firstOut(e,n);
154 157
      if( Edge(e) != INVALID ) {
155 158
        e.forward = false;
156 159
      }
... ...
@@ -184,97 +187,96 @@
184 187
    void nextInc(Edge &e, bool &d) const {
185 188
      if (d) {
186 189
        Node s = Parent::source(e);
187 190
        Parent::nextOut(e);
188 191
        if (e != INVALID) return;
189 192
        d = false;
190 193
        Parent::firstIn(e, s);
191 194
      } else {
192 195
        Parent::nextIn(e);
193 196
      }
194 197
    }
195 198

	
196 199
    Node nodeFromId(int ix) const {
197 200
      return Parent::nodeFromId(ix);
198 201
    }
199 202

	
200 203
    Arc arcFromId(int ix) const {
201 204
      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
202 205
    }
203 206

	
204 207
    Edge edgeFromId(int ix) const {
205 208
      return Parent::arcFromId(ix);
206 209
    }
207 210

	
208 211
    int id(const Node &n) const {
209 212
      return Parent::id(n);
210 213
    }
211 214

	
212 215
    int id(const Edge &e) const {
213 216
      return Parent::id(e);
214 217
    }
215 218

	
216 219
    int id(const Arc &e) const {
217 220
      return 2 * Parent::id(e) + int(e.forward);
218 221
    }
219 222

	
220 223
    int maxNodeId() const {
221 224
      return Parent::maxNodeId();
222 225
    }
223 226

	
224 227
    int maxArcId() const {
225 228
      return 2 * Parent::maxArcId() + 1;
226 229
    }
227 230

	
228 231
    int maxEdgeId() const {
229 232
      return Parent::maxArcId();
230 233
    }
231 234

	
232

	
233 235
    int arcNum() const {
234 236
      return 2 * Parent::arcNum();
235 237
    }
236 238

	
237 239
    int edgeNum() const {
238 240
      return Parent::arcNum();
239 241
    }
240 242

	
241 243
    Arc findArc(Node s, Node t, Arc p = INVALID) const {
242 244
      if (p == INVALID) {
243 245
        Edge arc = Parent::findArc(s, t);
244 246
        if (arc != INVALID) return direct(arc, true);
245 247
        arc = Parent::findArc(t, s);
246 248
        if (arc != INVALID) return direct(arc, false);
247 249
      } else if (direction(p)) {
248 250
        Edge arc = Parent::findArc(s, t, p);
249 251
        if (arc != INVALID) return direct(arc, true);
250 252
        arc = Parent::findArc(t, s);
251 253
        if (arc != INVALID) return direct(arc, false);
252 254
      } else {
253 255
        Edge arc = Parent::findArc(t, s, p);
254 256
        if (arc != INVALID) return direct(arc, false);
255 257
      }
256 258
      return INVALID;
257 259
    }
258 260

	
259 261
    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
260 262
      if (s != t) {
261 263
        if (p == INVALID) {
262 264
          Edge arc = Parent::findArc(s, t);
263 265
          if (arc != INVALID) return arc;
264 266
          arc = Parent::findArc(t, s);
265 267
          if (arc != INVALID) return arc;
266 268
        } else if (Parent::s(p) == s) {
267 269
          Edge arc = Parent::findArc(s, t, p);
268 270
          if (arc != INVALID) return arc;
269 271
          arc = Parent::findArc(t, s);
270 272
          if (arc != INVALID) return arc;
271 273
        } else {
272 274
          Edge arc = Parent::findArc(t, s, p);
273 275
          if (arc != INVALID) return arc;
274 276
        }
275 277
      } else {
276 278
        return Parent::findArc(s, t, p);
277 279
      }
278 280
      return INVALID;
279 281
    }
280 282
  };
Ignore white space 96 line context
... ...
@@ -185,184 +185,183 @@
185 185
    bool local_dist;
186 186
    //Pointer to the map of reached status of the nodes.
187 187
    ReachedMap *_reached;
188 188
    //Indicates if _reached is locally allocated (true) or not.
189 189
    bool local_reached;
190 190
    //Pointer to the map of processed status of the nodes.
191 191
    ProcessedMap *_processed;
192 192
    //Indicates if _processed is locally allocated (true) or not.
193 193
    bool local_processed;
194 194

	
195 195
    std::vector<typename Digraph::OutArcIt> _stack;
196 196
    int _stack_head;
197 197

	
198 198
    ///Creates the maps if necessary.
199 199
    ///\todo Better memory allocation (instead of new).
200 200
    void create_maps()
201 201
    {
202 202
      if(!_pred) {
203 203
        local_pred = true;
204 204
        _pred = Traits::createPredMap(*G);
205 205
      }
206 206
      if(!_dist) {
207 207
        local_dist = true;
208 208
        _dist = Traits::createDistMap(*G);
209 209
      }
210 210
      if(!_reached) {
211 211
        local_reached = true;
212 212
        _reached = Traits::createReachedMap(*G);
213 213
      }
214 214
      if(!_processed) {
215 215
        local_processed = true;
216 216
        _processed = Traits::createProcessedMap(*G);
217 217
      }
218 218
    }
219 219

	
220 220
  protected:
221 221

	
222 222
    Dfs() {}
223 223

	
224 224
  public:
225 225

	
226 226
    typedef Dfs Create;
227 227

	
228 228
    ///\name Named template parameters
229 229

	
230 230
    ///@{
231 231

	
232 232
    template <class T>
233
    struct DefPredMapTraits : public Traits {
233
    struct SetPredMapTraits : public Traits {
234 234
      typedef T PredMap;
235 235
      static PredMap *createPredMap(const Digraph &)
236 236
      {
237 237
        throw UninitializedParameter();
238 238
      }
239 239
    };
240 240
    ///\brief \ref named-templ-param "Named parameter" for setting
241 241
    ///\ref PredMap type.
242 242
    ///
243 243
    ///\ref named-templ-param "Named parameter" for setting
244 244
    ///\ref PredMap type.
245 245
    template <class T>
246
    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
247
      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
246
    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
247
      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
248 248
    };
249 249

	
250 250
    template <class T>
251
    struct DefDistMapTraits : public Traits {
251
    struct SetDistMapTraits : public Traits {
252 252
      typedef T DistMap;
253 253
      static DistMap *createDistMap(const Digraph &)
254 254
      {
255 255
        throw UninitializedParameter();
256 256
      }
257 257
    };
258 258
    ///\brief \ref named-templ-param "Named parameter" for setting
259 259
    ///\ref DistMap type.
260 260
    ///
261 261
    ///\ref named-templ-param "Named parameter" for setting
262 262
    ///\ref DistMap type.
263 263
    template <class T>
264
    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
265
      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
264
    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
265
      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
266 266
    };
267 267

	
268 268
    template <class T>
269
    struct DefReachedMapTraits : public Traits {
269
    struct SetReachedMapTraits : public Traits {
270 270
      typedef T ReachedMap;
271 271
      static ReachedMap *createReachedMap(const Digraph &)
272 272
      {
273 273
        throw UninitializedParameter();
274 274
      }
275 275
    };
276 276
    ///\brief \ref named-templ-param "Named parameter" for setting
277 277
    ///\ref ReachedMap type.
278 278
    ///
279 279
    ///\ref named-templ-param "Named parameter" for setting
280 280
    ///\ref ReachedMap type.
281 281
    template <class T>
282
    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
283
      typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
282
    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
283
      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
284 284
    };
285 285

	
286 286
    template <class T>
287
    struct DefProcessedMapTraits : public Traits {
287
    struct SetProcessedMapTraits : public Traits {
288 288
      typedef T ProcessedMap;
289 289
      static ProcessedMap *createProcessedMap(const Digraph &)
290 290
      {
291 291
        throw UninitializedParameter();
292 292
      }
293 293
    };
294 294
    ///\brief \ref named-templ-param "Named parameter" for setting
295 295
    ///\ref ProcessedMap type.
296 296
    ///
297 297
    ///\ref named-templ-param "Named parameter" for setting
298 298
    ///\ref ProcessedMap type.
299 299
    template <class T>
300
    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
301
      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
300
    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
301
      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
302 302
    };
303 303

	
304
    struct DefDigraphProcessedMapTraits : public Traits {
304
    struct SetStandardProcessedMapTraits : public Traits {
305 305
      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
306 306
      static ProcessedMap *createProcessedMap(const Digraph &g)
307 307
      {
308 308
        return new ProcessedMap(g);
309 309
      }
310 310
    };
311 311
    ///\brief \ref named-templ-param "Named parameter" for setting
312 312
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
313 313
    ///
314 314
    ///\ref named-templ-param "Named parameter" for setting
315 315
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
316 316
    ///If you don't set it explicitly, it will be automatically allocated.
317
    template <class T>
318
    struct DefProcessedMapToBeDefaultMap :
319
      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
320
      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
317
    struct SetStandardProcessedMap :
318
      public Dfs< Digraph, SetStandardProcessedMapTraits > {
319
      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
321 320
    };
322 321

	
323 322
    ///@}
324 323

	
325 324
  public:
326 325

	
327 326
    ///Constructor.
328 327

	
329 328
    ///Constructor.
330 329
    ///\param g The digraph the algorithm runs on.
331 330
    Dfs(const Digraph &g) :
332 331
      G(&g),
333 332
      _pred(NULL), local_pred(false),
334 333
      _dist(NULL), local_dist(false),
335 334
      _reached(NULL), local_reached(false),
336 335
      _processed(NULL), local_processed(false)
337 336
    { }
338 337

	
339 338
    ///Destructor.
340 339
    ~Dfs()
341 340
    {
342 341
      if(local_pred) delete _pred;
343 342
      if(local_dist) delete _dist;
344 343
      if(local_reached) delete _reached;
345 344
      if(local_processed) delete _processed;
346 345
    }
347 346

	
348 347
    ///Sets the map that stores the predecessor arcs.
349 348

	
350 349
    ///Sets the map that stores the predecessor arcs.
351 350
    ///If you don't use this function before calling \ref run(),
352 351
    ///it will allocate one. The destructor deallocates this
353 352
    ///automatically allocated map, of course.
354 353
    ///\return <tt> (*this) </tt>
355 354
    Dfs &predMap(PredMap &m)
356 355
    {
357 356
      if(local_pred) {
358 357
        delete _pred;
359 358
        local_pred=false;
360 359
      }
361 360
      _pred = &m;
362 361
      return *this;
363 362
    }
364 363

	
365 364
    ///Sets the map that indicates which nodes are reached.
366 365

	
367 366
    ///Sets the map that indicates which nodes are reached.
368 367
    ///If you don't use this function before calling \ref run(),
... ...
@@ -955,165 +954,165 @@
955 954
    DfsWizard(const Digraph &g, Node s=INVALID) :
956 955
      TR(g,s) {}
957 956

	
958 957
    ///Copy constructor
959 958
    DfsWizard(const TR &b) : TR(b) {}
960 959

	
961 960
    ~DfsWizard() {}
962 961

	
963 962
    ///Runs DFS algorithm from a source node.
964 963

	
965 964
    ///Runs DFS algorithm from a source node.
966 965
    ///The node can be given with the \ref source() function.
967 966
    void run()
968 967
    {
969 968
      if(Base::_source==INVALID) throw UninitializedParameter();
970 969
      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
971 970
      if(Base::_reached)
972 971
        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
973 972
      if(Base::_processed)
974 973
        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
975 974
      if(Base::_pred)
976 975
        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
977 976
      if(Base::_dist)
978 977
        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
979 978
      alg.run(Base::_source);
980 979
    }
981 980

	
982 981
    ///Runs DFS algorithm from the given node.
983 982

	
984 983
    ///Runs DFS algorithm from the given node.
985 984
    ///\param s is the given source.
986 985
    void run(Node s)
987 986
    {
988 987
      Base::_source=s;
989 988
      run();
990 989
    }
991 990

	
992 991
    /// Sets the source node, from which the Dfs algorithm runs.
993 992

	
994 993
    /// Sets the source node, from which the Dfs algorithm runs.
995 994
    /// \param s is the source node.
996 995
    DfsWizard<TR> &source(Node s)
997 996
    {
998 997
      Base::_source=s;
999 998
      return *this;
1000 999
    }
1001 1000

	
1002 1001
    template<class T>
1003
    struct DefPredMapBase : public Base {
1002
    struct SetPredMapBase : public Base {
1004 1003
      typedef T PredMap;
1005 1004
      static PredMap *createPredMap(const Digraph &) { return 0; };
1006
      DefPredMapBase(const TR &b) : TR(b) {}
1005
      SetPredMapBase(const TR &b) : TR(b) {}
1007 1006
    };
1008 1007
    ///\brief \ref named-templ-param "Named parameter"
1009 1008
    ///for setting \ref PredMap object.
1010 1009
    ///
1011 1010
    ///\ref named-templ-param "Named parameter"
1012 1011
    ///for setting \ref PredMap object.
1013 1012
    template<class T>
1014
    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1013
    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1015 1014
    {
1016 1015
      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1017
      return DfsWizard<DefPredMapBase<T> >(*this);
1016
      return DfsWizard<SetPredMapBase<T> >(*this);
1018 1017
    }
1019 1018

	
1020 1019
    template<class T>
1021
    struct DefReachedMapBase : public Base {
1020
    struct SetReachedMapBase : public Base {
1022 1021
      typedef T ReachedMap;
1023 1022
      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1024
      DefReachedMapBase(const TR &b) : TR(b) {}
1023
      SetReachedMapBase(const TR &b) : TR(b) {}
1025 1024
    };
1026 1025
    ///\brief \ref named-templ-param "Named parameter"
1027 1026
    ///for setting \ref ReachedMap object.
1028 1027
    ///
1029 1028
    /// \ref named-templ-param "Named parameter"
1030 1029
    ///for setting \ref ReachedMap object.
1031 1030
    template<class T>
1032
    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1031
    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1033 1032
    {
1034 1033
      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1035
      return DfsWizard<DefReachedMapBase<T> >(*this);
1034
      return DfsWizard<SetReachedMapBase<T> >(*this);
1036 1035
    }
1037 1036

	
1038 1037
    template<class T>
1039
    struct DefProcessedMapBase : public Base {
1038
    struct SetProcessedMapBase : public Base {
1040 1039
      typedef T ProcessedMap;
1041 1040
      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1042
      DefProcessedMapBase(const TR &b) : TR(b) {}
1041
      SetProcessedMapBase(const TR &b) : TR(b) {}
1043 1042
    };
1044 1043
    ///\brief \ref named-templ-param "Named parameter"
1045 1044
    ///for setting \ref ProcessedMap object.
1046 1045
    ///
1047 1046
    /// \ref named-templ-param "Named parameter"
1048 1047
    ///for setting \ref ProcessedMap object.
1049 1048
    template<class T>
1050
    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1049
    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1051 1050
    {
1052 1051
      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1053
      return DfsWizard<DefProcessedMapBase<T> >(*this);
1052
      return DfsWizard<SetProcessedMapBase<T> >(*this);
1054 1053
    }
1055 1054

	
1056 1055
    template<class T>
1057
    struct DefDistMapBase : public Base {
1056
    struct SetDistMapBase : public Base {
1058 1057
      typedef T DistMap;
1059 1058
      static DistMap *createDistMap(const Digraph &) { return 0; };
1060
      DefDistMapBase(const TR &b) : TR(b) {}
1059
      SetDistMapBase(const TR &b) : TR(b) {}
1061 1060
    };
1062 1061
    ///\brief \ref named-templ-param "Named parameter"
1063 1062
    ///for setting \ref DistMap object.
1064 1063
    ///
1065 1064
    ///\ref named-templ-param "Named parameter"
1066 1065
    ///for setting \ref DistMap object.
1067 1066
    template<class T>
1068
    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1067
    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1069 1068
    {
1070 1069
      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1071
      return DfsWizard<DefDistMapBase<T> >(*this);
1070
      return DfsWizard<SetDistMapBase<T> >(*this);
1072 1071
    }
1073 1072

	
1074 1073
  };
1075 1074

	
1076 1075
  ///Function type interface for Dfs algorithm.
1077 1076

	
1078 1077
  ///\ingroup search
1079 1078
  ///Function type interface for Dfs algorithm.
1080 1079
  ///
1081 1080
  ///This function also has several
1082 1081
  ///\ref named-templ-func-param "named parameters",
1083 1082
  ///they are declared as the members of class \ref DfsWizard.
1084 1083
  ///The following
1085 1084
  ///example shows how to use these parameters.
1086 1085
  ///\code
1087 1086
  ///  dfs(g,source).predMap(preds).run();
1088 1087
  ///\endcode
1089 1088
  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1090 1089
  ///to the end of the parameter list.
1091 1090
  ///\sa DfsWizard
1092 1091
  ///\sa Dfs
1093 1092
  template<class GR>
1094 1093
  DfsWizard<DfsWizardBase<GR> >
1095 1094
  dfs(const GR &g,typename GR::Node s=INVALID)
1096 1095
  {
1097 1096
    return DfsWizard<DfsWizardBase<GR> >(g,s);
1098 1097
  }
1099 1098

	
1100 1099
#ifdef DOXYGEN
1101 1100
  /// \brief Visitor class for DFS.
1102 1101
  ///
1103 1102
  /// This class defines the interface of the DfsVisit events, and
1104 1103
  /// it could be the base of a real visitor class.
1105 1104
  template <typename _Digraph>
1106 1105
  struct DfsVisitor {
1107 1106
    typedef _Digraph Digraph;
1108 1107
    typedef typename Digraph::Arc Arc;
1109 1108
    typedef typename Digraph::Node Node;
1110 1109
    /// \brief Called for the source node of the DFS.
1111 1110
    ///
1112 1111
    /// This function is called for the source node of the DFS.
1113 1112
    void start(const Node& node) {}
1114 1113
    /// \brief Called when the source node is leaved.
1115 1114
    ///
1116 1115
    /// This function is called when the source node is leaved.
1117 1116
    void stop(const Node& node) {}
1118 1117
    /// \brief Called when a node is reached first time.
1119 1118
    ///
... ...
@@ -1256,110 +1255,110 @@
1256 1255
    typedef typename Traits::Digraph Digraph;
1257 1256

	
1258 1257
    ///The visitor type used by the algorithm.
1259 1258
    typedef _Visitor Visitor;
1260 1259

	
1261 1260
    ///The type of the map that indicates which nodes are reached.
1262 1261
    typedef typename Traits::ReachedMap ReachedMap;
1263 1262

	
1264 1263
  private:
1265 1264

	
1266 1265
    typedef typename Digraph::Node Node;
1267 1266
    typedef typename Digraph::NodeIt NodeIt;
1268 1267
    typedef typename Digraph::Arc Arc;
1269 1268
    typedef typename Digraph::OutArcIt OutArcIt;
1270 1269

	
1271 1270
    //Pointer to the underlying digraph.
1272 1271
    const Digraph *_digraph;
1273 1272
    //Pointer to the visitor object.
1274 1273
    Visitor *_visitor;
1275 1274
    //Pointer to the map of reached status of the nodes.
1276 1275
    ReachedMap *_reached;
1277 1276
    //Indicates if _reached is locally allocated (true) or not.
1278 1277
    bool local_reached;
1279 1278

	
1280 1279
    std::vector<typename Digraph::Arc> _stack;
1281 1280
    int _stack_head;
1282 1281

	
1283 1282
    ///Creates the maps if necessary.
1284 1283
    ///\todo Better memory allocation (instead of new).
1285 1284
    void create_maps() {
1286 1285
      if(!_reached) {
1287 1286
        local_reached = true;
1288 1287
        _reached = Traits::createReachedMap(*_digraph);
1289 1288
      }
1290 1289
    }
1291 1290

	
1292 1291
  protected:
1293 1292

	
1294 1293
    DfsVisit() {}
1295 1294

	
1296 1295
  public:
1297 1296

	
1298 1297
    typedef DfsVisit Create;
1299 1298

	
1300 1299
    /// \name Named template parameters
1301 1300

	
1302 1301
    ///@{
1303 1302
    template <class T>
1304
    struct DefReachedMapTraits : public Traits {
1303
    struct SetReachedMapTraits : public Traits {
1305 1304
      typedef T ReachedMap;
1306 1305
      static ReachedMap *createReachedMap(const Digraph &digraph) {
1307 1306
        throw UninitializedParameter();
1308 1307
      }
1309 1308
    };
1310 1309
    /// \brief \ref named-templ-param "Named parameter" for setting
1311 1310
    /// ReachedMap type.
1312 1311
    ///
1313 1312
    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1314 1313
    template <class T>
1315
    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
1316
                                            DefReachedMapTraits<T> > {
1317
      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1314
    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
1315
                                            SetReachedMapTraits<T> > {
1316
      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1318 1317
    };
1319 1318
    ///@}
1320 1319

	
1321 1320
  public:
1322 1321

	
1323 1322
    /// \brief Constructor.
1324 1323
    ///
1325 1324
    /// Constructor.
1326 1325
    ///
1327 1326
    /// \param digraph The digraph the algorithm runs on.
1328 1327
    /// \param visitor The visitor object of the algorithm.
1329 1328
    DfsVisit(const Digraph& digraph, Visitor& visitor)
1330 1329
      : _digraph(&digraph), _visitor(&visitor),
1331 1330
        _reached(0), local_reached(false) {}
1332 1331

	
1333 1332
    /// \brief Destructor.
1334 1333
    ~DfsVisit() {
1335 1334
      if(local_reached) delete _reached;
1336 1335
    }
1337 1336

	
1338 1337
    /// \brief Sets the map that indicates which nodes are reached.
1339 1338
    ///
1340 1339
    /// Sets the map that indicates which nodes are reached.
1341 1340
    /// If you don't use this function before calling \ref run(),
1342 1341
    /// it will allocate one. The destructor deallocates this
1343 1342
    /// automatically allocated map, of course.
1344 1343
    /// \return <tt> (*this) </tt>
1345 1344
    DfsVisit &reachedMap(ReachedMap &m) {
1346 1345
      if(local_reached) {
1347 1346
        delete _reached;
1348 1347
        local_reached=false;
1349 1348
      }
1350 1349
      _reached = &m;
1351 1350
      return *this;
1352 1351
    }
1353 1352

	
1354 1353
  public:
1355 1354

	
1356 1355
    /// \name Execution control
1357 1356
    /// The simplest way to execute the algorithm is to use
1358 1357
    /// one of the member functions called \ref lemon::DfsVisit::run()
1359 1358
    /// "run()".
1360 1359
    /// \n
1361 1360
    /// If you need more control on the execution, first you must call
1362 1361
    /// \ref lemon::DfsVisit::init() "init()", then you can add several
1363 1362
    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1364 1363
    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1365 1364
    /// actual path computation.
Ignore white space 6 line context
... ...
@@ -286,235 +286,234 @@
286 286
    //Pointer to the map of processed status of the nodes.
287 287
    ProcessedMap *_processed;
288 288
    //Indicates if _processed is locally allocated (true) or not.
289 289
    bool local_processed;
290 290
    //Pointer to the heap cross references.
291 291
    HeapCrossRef *_heap_cross_ref;
292 292
    //Indicates if _heap_cross_ref is locally allocated (true) or not.
293 293
    bool local_heap_cross_ref;
294 294
    //Pointer to the heap.
295 295
    Heap *_heap;
296 296
    //Indicates if _heap is locally allocated (true) or not.
297 297
    bool local_heap;
298 298

	
299 299
    ///Creates the maps if necessary.
300 300
    ///\todo Better memory allocation (instead of new).
301 301
    void create_maps()
302 302
    {
303 303
      if(!_pred) {
304 304
        local_pred = true;
305 305
        _pred = Traits::createPredMap(*G);
306 306
      }
307 307
      if(!_dist) {
308 308
        local_dist = true;
309 309
        _dist = Traits::createDistMap(*G);
310 310
      }
311 311
      if(!_processed) {
312 312
        local_processed = true;
313 313
        _processed = Traits::createProcessedMap(*G);
314 314
      }
315 315
      if (!_heap_cross_ref) {
316 316
        local_heap_cross_ref = true;
317 317
        _heap_cross_ref = Traits::createHeapCrossRef(*G);
318 318
      }
319 319
      if (!_heap) {
320 320
        local_heap = true;
321 321
        _heap = Traits::createHeap(*_heap_cross_ref);
322 322
      }
323 323
    }
324 324

	
325 325
  public:
326 326

	
327 327
    typedef Dijkstra Create;
328 328

	
329 329
    ///\name Named template parameters
330 330

	
331 331
    ///@{
332 332

	
333 333
    template <class T>
334
    struct DefPredMapTraits : public Traits {
334
    struct SetPredMapTraits : public Traits {
335 335
      typedef T PredMap;
336 336
      static PredMap *createPredMap(const Digraph &)
337 337
      {
338 338
        throw UninitializedParameter();
339 339
      }
340 340
    };
341 341
    ///\brief \ref named-templ-param "Named parameter" for setting
342 342
    ///\ref PredMap type.
343 343
    ///
344 344
    ///\ref named-templ-param "Named parameter" for setting
345 345
    ///\ref PredMap type.
346 346
    template <class T>
347
    struct DefPredMap
348
      : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
349
      typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create;
347
    struct SetPredMap
348
      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
349
      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
350 350
    };
351 351

	
352 352
    template <class T>
353
    struct DefDistMapTraits : public Traits {
353
    struct SetDistMapTraits : public Traits {
354 354
      typedef T DistMap;
355 355
      static DistMap *createDistMap(const Digraph &)
356 356
      {
357 357
        throw UninitializedParameter();
358 358
      }
359 359
    };
360 360
    ///\brief \ref named-templ-param "Named parameter" for setting
361 361
    ///\ref DistMap type.
362 362
    ///
363 363
    ///\ref named-templ-param "Named parameter" for setting
364 364
    ///\ref DistMap type.
365 365
    template <class T>
366
    struct DefDistMap
367
      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
368
      typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
366
    struct SetDistMap
367
      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
368
      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
369 369
    };
370 370

	
371 371
    template <class T>
372
    struct DefProcessedMapTraits : public Traits {
372
    struct SetProcessedMapTraits : public Traits {
373 373
      typedef T ProcessedMap;
374 374
      static ProcessedMap *createProcessedMap(const Digraph &)
375 375
      {
376 376
        throw UninitializedParameter();
377 377
      }
378 378
    };
379 379
    ///\brief \ref named-templ-param "Named parameter" for setting
380 380
    ///\ref ProcessedMap type.
381 381
    ///
382 382
    ///\ref named-templ-param "Named parameter" for setting
383 383
    ///\ref ProcessedMap type.
384 384
    template <class T>
385
    struct DefProcessedMap
386
      : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
387
      typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create;
385
    struct SetProcessedMap
386
      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
387
      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
388 388
    };
389 389

	
390
    struct DefDigraphProcessedMapTraits : public Traits {
390
    struct SetStandardProcessedMapTraits : public Traits {
391 391
      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
392 392
      static ProcessedMap *createProcessedMap(const Digraph &g)
393 393
      {
394 394
        return new ProcessedMap(g);
395 395
      }
396 396
    };
397 397
    ///\brief \ref named-templ-param "Named parameter" for setting
398 398
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
399 399
    ///
400 400
    ///\ref named-templ-param "Named parameter" for setting
401 401
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
402 402
    ///If you don't set it explicitly, it will be automatically allocated.
403
    template <class T>
404
    struct DefProcessedMapToBeDefaultMap
405
      : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
406
      typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits>
403
    struct SetStandardProcessedMap
404
      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
405
      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
407 406
      Create;
408 407
    };
409 408

	
410 409
    template <class H, class CR>
411
    struct DefHeapTraits : public Traits {
410
    struct SetHeapTraits : public Traits {
412 411
      typedef CR HeapCrossRef;
413 412
      typedef H Heap;
414 413
      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
415 414
        throw UninitializedParameter();
416 415
      }
417 416
      static Heap *createHeap(HeapCrossRef &)
418 417
      {
419 418
        throw UninitializedParameter();
420 419
      }
421 420
    };
422 421
    ///\brief \ref named-templ-param "Named parameter" for setting
423 422
    ///heap and cross reference type
424 423
    ///
425 424
    ///\ref named-templ-param "Named parameter" for setting heap and cross
426 425
    ///reference type.
427 426
    template <class H, class CR = typename Digraph::template NodeMap<int> >
428
    struct DefHeap
429
      : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
430
      typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create;
427
    struct SetHeap
428
      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
429
      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
431 430
    };
432 431

	
433 432
    template <class H, class CR>
434
    struct DefStandardHeapTraits : public Traits {
433
    struct SetStandardHeapTraits : public Traits {
435 434
      typedef CR HeapCrossRef;
436 435
      typedef H Heap;
437 436
      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
438 437
        return new HeapCrossRef(G);
439 438
      }
440 439
      static Heap *createHeap(HeapCrossRef &R)
441 440
      {
442 441
        return new Heap(R);
443 442
      }
444 443
    };
445 444
    ///\brief \ref named-templ-param "Named parameter" for setting
446 445
    ///heap and cross reference type with automatic allocation
447 446
    ///
448 447
    ///\ref named-templ-param "Named parameter" for setting heap and cross
449 448
    ///reference type. It can allocate the heap and the cross reference
450 449
    ///object if the cross reference's constructor waits for the digraph as
451 450
    ///parameter and the heap's constructor waits for the cross reference.
452 451
    template <class H, class CR = typename Digraph::template NodeMap<int> >
453
    struct DefStandardHeap
454
      : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {
455
      typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >
452
    struct SetStandardHeap
453
      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
454
      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
456 455
      Create;
457 456
    };
458 457

	
459 458
    template <class T>
460
    struct DefOperationTraitsTraits : public Traits {
459
    struct SetOperationTraitsTraits : public Traits {
461 460
      typedef T OperationTraits;
462 461
    };
463 462

	
464 463
    /// \brief \ref named-templ-param "Named parameter" for setting
465 464
    ///\ref OperationTraits type
466 465
    ///
467 466
    ///\ref named-templ-param "Named parameter" for setting
468 467
    ///\ref OperationTraits type.
469 468
    template <class T>
470
    struct DefOperationTraits
471
      : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
472
      typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> >
469
    struct SetOperationTraits
470
      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
471
      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
473 472
      Create;
474 473
    };
475 474

	
476 475
    ///@}
477 476

	
478 477
  protected:
479 478

	
480 479
    Dijkstra() {}
481 480

	
482 481
  public:
483 482

	
484 483
    ///Constructor.
485 484

	
486 485
    ///Constructor.
487 486
    ///\param _g The digraph the algorithm runs on.
488 487
    ///\param _length The length map used by the algorithm.
489 488
    Dijkstra(const Digraph& _g, const LengthMap& _length) :
490 489
      G(&_g), length(&_length),
491 490
      _pred(NULL), local_pred(false),
492 491
      _dist(NULL), local_dist(false),
493 492
      _processed(NULL), local_processed(false),
494 493
      _heap_cross_ref(NULL), local_heap_cross_ref(false),
495 494
      _heap(NULL), local_heap(false)
496 495
    { }
497 496

	
498 497
    ///Destructor.
499 498
    ~Dijkstra()
500 499
    {
501 500
      if(local_pred) delete _pred;
502 501
      if(local_dist) delete _dist;
503 502
      if(local_processed) delete _processed;
504 503
      if(local_heap_cross_ref) delete _heap_cross_ref;
505 504
      if(local_heap) delete _heap;
506 505
    }
507 506

	
508 507
    ///Sets the length map.
509 508

	
510 509
    ///Sets the length map.
511 510
    ///\return <tt> (*this) </tt>
512 511
    Dijkstra &lengthMap(const LengthMap &m)
513 512
    {
514 513
      length = &m;
515 514
      return *this;
516 515
    }
517 516

	
518 517
    ///Sets the map that stores the predecessor arcs.
519 518

	
520 519
    ///Sets the map that stores the predecessor arcs.
... ...
@@ -1160,130 +1159,130 @@
1160 1159
    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
1161 1160
      TR(g,l,s) {}
1162 1161

	
1163 1162
    ///Copy constructor
1164 1163
    DijkstraWizard(const TR &b) : TR(b) {}
1165 1164

	
1166 1165
    ~DijkstraWizard() {}
1167 1166

	
1168 1167
    ///Runs Dijkstra algorithm from a source node.
1169 1168

	
1170 1169
    ///Runs Dijkstra algorithm from a source node.
1171 1170
    ///The node can be given with the \ref source() function.
1172 1171
    void run()
1173 1172
    {
1174 1173
      if(Base::_source==INVALID) throw UninitializedParameter();
1175 1174
      Dijkstra<Digraph,LengthMap,TR>
1176 1175
        dij(*reinterpret_cast<const Digraph*>(Base::_g),
1177 1176
            *reinterpret_cast<const LengthMap*>(Base::_length));
1178 1177
      if(Base::_processed)
1179 1178
        dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1180 1179
      if(Base::_pred)
1181 1180
        dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1182 1181
      if(Base::_dist)
1183 1182
        dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1184 1183
      dij.run(Base::_source);
1185 1184
    }
1186 1185

	
1187 1186
    ///Runs Dijkstra algorithm from the given node.
1188 1187

	
1189 1188
    ///Runs Dijkstra algorithm from the given node.
1190 1189
    ///\param s is the given source.
1191 1190
    void run(Node s)
1192 1191
    {
1193 1192
      Base::_source=s;
1194 1193
      run();
1195 1194
    }
1196 1195

	
1197 1196
    /// Sets the source node, from which the Dijkstra algorithm runs.
1198 1197

	
1199 1198
    /// Sets the source node, from which the Dijkstra algorithm runs.
1200 1199
    /// \param s is the source node.
1201 1200
    DijkstraWizard<TR> &source(Node s)
1202 1201
    {
1203 1202
      Base::_source=s;
1204 1203
      return *this;
1205 1204
    }
1206 1205

	
1207 1206
    template<class T>
1208
    struct DefPredMapBase : public Base {
1207
    struct SetPredMapBase : public Base {
1209 1208
      typedef T PredMap;
1210 1209
      static PredMap *createPredMap(const Digraph &) { return 0; };
1211
      DefPredMapBase(const TR &b) : TR(b) {}
1210
      SetPredMapBase(const TR &b) : TR(b) {}
1212 1211
    };
1213 1212
    ///\brief \ref named-templ-param "Named parameter"
1214 1213
    ///for setting \ref PredMap object.
1215 1214
    ///
1216 1215
    ///\ref named-templ-param "Named parameter"
1217 1216
    ///for setting \ref PredMap object.
1218 1217
    template<class T>
1219
    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1218
    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1220 1219
    {
1221 1220
      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1222
      return DijkstraWizard<DefPredMapBase<T> >(*this);
1221
      return DijkstraWizard<SetPredMapBase<T> >(*this);
1223 1222
    }
1224 1223

	
1225 1224
    template<class T>
1226
    struct DefProcessedMapBase : public Base {
1225
    struct SetProcessedMapBase : public Base {
1227 1226
      typedef T ProcessedMap;
1228 1227
      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1229
      DefProcessedMapBase(const TR &b) : TR(b) {}
1228
      SetProcessedMapBase(const TR &b) : TR(b) {}
1230 1229
    };
1231 1230
    ///\brief \ref named-templ-param "Named parameter"
1232 1231
    ///for setting \ref ProcessedMap object.
1233 1232
    ///
1234 1233
    /// \ref named-templ-param "Named parameter"
1235 1234
    ///for setting \ref ProcessedMap object.
1236 1235
    template<class T>
1237
    DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1236
    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1238 1237
    {
1239 1238
      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1240
      return DijkstraWizard<DefProcessedMapBase<T> >(*this);
1239
      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
1241 1240
    }
1242 1241

	
1243 1242
    template<class T>
1244
    struct DefDistMapBase : public Base {
1243
    struct SetDistMapBase : public Base {
1245 1244
      typedef T DistMap;
1246 1245
      static DistMap *createDistMap(const Digraph &) { return 0; };
1247
      DefDistMapBase(const TR &b) : TR(b) {}
1246
      SetDistMapBase(const TR &b) : TR(b) {}
1248 1247
    };
1249 1248
    ///\brief \ref named-templ-param "Named parameter"
1250 1249
    ///for setting \ref DistMap object.
1251 1250
    ///
1252 1251
    ///\ref named-templ-param "Named parameter"
1253 1252
    ///for setting \ref DistMap object.
1254 1253
    template<class T>
1255
    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1254
    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1256 1255
    {
1257 1256
      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1258
      return DijkstraWizard<DefDistMapBase<T> >(*this);
1257
      return DijkstraWizard<SetDistMapBase<T> >(*this);
1259 1258
    }
1260 1259

	
1261 1260
  };
1262 1261

	
1263 1262
  ///Function type interface for Dijkstra algorithm.
1264 1263

	
1265 1264
  /// \ingroup shortest_path
1266 1265
  ///Function type interface for Dijkstra algorithm.
1267 1266
  ///
1268 1267
  ///This function also has several
1269 1268
  ///\ref named-templ-func-param "named parameters",
1270 1269
  ///they are declared as the members of class \ref DijkstraWizard.
1271 1270
  ///The following
1272 1271
  ///example shows how to use these parameters.
1273 1272
  ///\code
1274 1273
  ///  dijkstra(g,length,source).predMap(preds).run();
1275 1274
  ///\endcode
1276 1275
  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1277 1276
  ///to the end of the parameter list.
1278 1277
  ///\sa DijkstraWizard
1279 1278
  ///\sa Dijkstra
1280 1279
  template<class GR, class LM>
1281 1280
  DijkstraWizard<DijkstraWizardBase<GR,LM> >
1282 1281
  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1283 1282
  {
1284 1283
    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1285 1284
  }
1286 1285

	
1287 1286
} //END OF NAMESPACE LEMON
1288 1287

	
1289 1288
#endif
Ignore white space 6 line context
... ...
@@ -86,97 +86,97 @@
86 86
template <typename Heap>
87 87
void heapSortTest() {
88 88
  RangeMap<int> map(test_len, -1);
89 89

	
90 90
  Heap heap(map);
91 91

	
92 92
  std::vector<int> v(test_len);
93 93

	
94 94
  for (int i = 0; i < test_len; ++i) {
95 95
    v[i] = test_seq[i];
96 96
    heap.push(i, v[i]);
97 97
  }
98 98
  std::sort(v.begin(), v.end());
99 99
  for (int i = 0; i < test_len; ++i) {
100 100
    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
101 101
    heap.pop();
102 102
  }
103 103
}
104 104

	
105 105
template <typename Heap>
106 106
void heapIncreaseTest() {
107 107
  RangeMap<int> map(test_len, -1);
108 108

	
109 109
  Heap heap(map);
110 110

	
111 111
  std::vector<int> v(test_len);
112 112

	
113 113
  for (int i = 0; i < test_len; ++i) {
114 114
    v[i] = test_seq[i];
115 115
    heap.push(i, v[i]);
116 116
  }
117 117
  for (int i = 0; i < test_len; ++i) {
118 118
    v[i] += test_inc[i];
119 119
    heap.increase(i, v[i]);
120 120
  }
121 121
  std::sort(v.begin(), v.end());
122 122
  for (int i = 0; i < test_len; ++i) {
123 123
    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
124 124
    heap.pop();
125 125
  }
126 126
}
127 127

	
128 128

	
129 129

	
130 130
template <typename Heap>
131 131
void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
132 132
                      Node source) {
133 133

	
134
  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
134
  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
135 135
    Create dijkstra(digraph, length);
136 136

	
137 137
  dijkstra.run(source);
138 138

	
139 139
  for(ArcIt a(digraph); a != INVALID; ++a) {
140 140
    Node s = digraph.source(a);
141 141
    Node t = digraph.target(a);
142 142
    if (dijkstra.reached(s)) {
143 143
      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
144 144
             "Error in a shortest path tree!");
145 145
    }
146 146
  }
147 147

	
148 148
  for(NodeIt n(digraph); n != INVALID; ++n) {
149 149
    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
150 150
      Arc a = dijkstra.predArc(n);
151 151
      Node s = digraph.source(a);
152 152
      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
153 153
             "Error in a shortest path tree!");
154 154
    }
155 155
  }
156 156

	
157 157
}
158 158

	
159 159
int main() {
160 160

	
161 161
  typedef int Item;
162 162
  typedef int Prio;
163 163
  typedef RangeMap<int> ItemIntMap;
164 164

	
165 165
  Digraph digraph;
166 166
  IntArcMap length(digraph);
167 167
  Node source;
168 168

	
169 169
  std::istringstream input(test_lgf);
170 170
  digraphReader(input, digraph).
171 171
    arcMap("capacity", length).
172 172
    node("source", source).
173 173
    run();
174 174

	
175 175
  {
176 176
    typedef BinHeap<Prio, ItemIntMap> IntHeap;
177 177
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
178 178
    heapSortTest<IntHeap>();
179 179
    heapIncreaseTest<IntHeap>();
180 180

	
181 181
    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
182 182
    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
0 comments (0 inline)