LEMON/LEMON-official Changeset - r832:9ae88e7c04a7

@@ -5,106 +5,115 @@

5

 * Copyright (C) 2003-2009

6

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

7

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

8

9

 * Permission to use, modify and distribute this software is granted

10

 * provided that this copyright notice appears in all copies. For

11

 * precise terms see the accompanying LICENSE file.

12

13

 * This software is provided "AS IS" with no warranty of any kind,

14

 * express or implied, and with no claim as to its suitability for any

15

 * purpose.

16

17

*/

18

19

///\ingroup concept

20

///\file

21

///\brief Classes for representing paths in digraphs.

21

///\brief The concept of paths

22

///

23

24

#ifndef LEMON_CONCEPTS_PATH_H

25

#define LEMON_CONCEPTS_PATH_H

26

27

#include <lemon/core.h>

28

#include <lemon/concept_check.h>

29

30

namespace lemon {

31

  namespace concepts {

32

33

    /// \addtogroup concept

34

    /// @{

35

36

    /// \brief A skeleton structure for representing directed paths in

37

    /// a digraph.

38

///

39

    /// A skeleton structure for representing directed paths in a

40

    /// digraph.

41

    /// In a sense, a path can be treated as a list of arcs.

42

    /// LEMON path types just store this list. As a consequence, they cannot

43

    /// enumerate the nodes on the path directly and a zero length path

44

    /// cannot store its source node.

45

///

46

    /// The arcs of a path should be stored in the order of their directions,

47

    /// i.e. the target node of each arc should be the same as the source

48

    /// node of the next arc. This consistency could be checked using

49

    /// \ref checkPath().

50

    /// The source and target nodes of a (consistent) path can be obtained

51

    /// using \ref pathSource() and \ref pathTarget().

52

///

53

    /// A path can be constructed from another path of any type using the

54

    /// copy constructor or the assignment operator.

55

///

41

56

    /// \tparam GR The digraph type in which the path is.

42

///

43

    /// In a sense, the path can be treated as a list of arcs. The

44

    /// lemon path type stores just this list. As a consequence it

45

    /// cannot enumerate the nodes in the path and the zero length

46

    /// paths cannot store the source.

47

///

48

57

    template <typename GR>

49

58

    class Path {

50

59

    public:

      /// Type of the underlying digraph.

53

62

      typedef GR Digraph;

54

63

      /// Arc type of the underlying digraph.

55

64

      typedef typename Digraph::Arc Arc;

      class ArcIt;

      /// \brief Default constructor

60

69

      Path() {}

61

70

62

      /// \brief Template constructor

71

      /// \brief Template copy constructor

63

72

      template <typename CPath>

64

73

      Path(const CPath& cpath) {}

65

74

66

      /// \brief Template assigment

75

      /// \brief Template assigment operator

67

76

      template <typename CPath>

68

77

      Path& operator=(const CPath& cpath) {

69

78

        ignore_unused_variable_warning(cpath);

70

79

        return *this;

      /// Length of the path ie. the number of arcs in the path.

82

      /// Length of the path, i.e. the number of arcs on the path.

74

83

      int length() const { return 0;}

      /// Returns whether the path is empty.

77

86

      bool empty() const { return true;}

      /// Resets the path to an empty path.

80

89

      void clear() {}

81

90

82

      /// \brief LEMON style iterator for path arcs

91

      /// \brief LEMON style iterator for enumerating the arcs of a path.

83

92

///

84

      /// This class is used to iterate on the arcs of the paths.

93

      /// LEMON style iterator class for enumerating the arcs of a path.

85

94

      class ArcIt {

86

95

      public:

87

96

        /// Default constructor

88

97

        ArcIt() {}

89

98

        /// Invalid constructor

90

99

        ArcIt(Invalid) {}

91

        /// Constructor for first arc

100

        /// Sets the iterator to the first arc of the given path

92

101

        ArcIt(const Path &) {}

93

102

94

        /// Conversion to Arc

103

        /// Conversion to \c Arc

95

104

        operator Arc() const { return INVALID; }

        /// Next arc

98

107

        ArcIt& operator++() {return *this;}

        /// Comparison operator

101

110

        bool operator==(const ArcIt&) const {return true;}

102

111

        /// Comparison operator

103

112

        bool operator!=(const ArcIt&) const {return true;}

104

113

        /// Comparison operator

105

114

        bool operator<(const ArcIt&) const {return false;}

};

      template <typename _Path>

110

119

      struct Constraints {

...

@@ -179,114 +188,108 @@

179

188

          e = (i != INVALID);

          ignore_unused_variable_warning(l);

182

191

          ignore_unused_variable_warning(e);

183

192

          ignore_unused_variable_warning(id);

184

193

          ignore_unused_variable_warning(ed);

        _Path& p;

187

196

};

    /// \brief A skeleton structure for path dumpers.

193

202

///

194

203

    /// A skeleton structure for path dumpers. The path dumpers are

195

    /// the generalization of the paths. The path dumpers can

196

    /// enumerate the arcs of the path wheter in forward or in

197

    /// backward order.  In most time these classes are not used

198

    /// directly rather it used to assign a dumped class to a real

199

    /// path type.

204

    /// the generalization of the paths, they can enumerate the arcs

205

    /// of the path either in forward or in backward order.

206

    /// These classes are typically not used directly, they are rather

207

    /// used to be assigned to a real path type.

200

208

///

201

209

    /// The main purpose of this concept is that the shortest path

202

    /// algorithms can enumerate easily the arcs in reverse order.

203

    /// If we would like to give back a real path from these

204

    /// algorithms then we should create a temporarly path object. In

205

    /// LEMON such algorithms gives back a path dumper what can

206

    /// assigned to a real path and the dumpers can be implemented as

210

    /// algorithms can enumerate the arcs easily in reverse order.

211

    /// In LEMON, such algorithms give back a (reverse) path dumper that

212

    /// can be assigned to a real path. The dumpers can be implemented as

207

213

    /// an adaptor class to the predecessor map.

208

214

///

209

215

    /// \tparam GR The digraph type in which the path is.

210

///

211

    /// The paths can be constructed from any path type by a

212

    /// template constructor or a template assignment operator.

213

216

    template <typename GR>

214

217

    class PathDumper {

215

218

    public:

      /// Type of the underlying digraph.

218

221

      typedef GR Digraph;

219

222

      /// Arc type of the underlying digraph.

220

223

      typedef typename Digraph::Arc Arc;

221

224

222

      /// Length of the path ie. the number of arcs in the path.

225

      /// Length of the path, i.e. the number of arcs on the path.

223

226

      int length() const { return 0;}

      /// Returns whether the path is empty.

226

229

      bool empty() const { return true;}

      /// \brief Forward or reverse dumping

229

232

///

230

      /// If the RevPathTag is defined and true then reverse dumping

231

      /// is provided in the path dumper. In this case instead of the

232

      /// ArcIt the RevArcIt iterator should be implemented in the

233

      /// dumper.

233

      /// If this tag is defined to be \c True, then reverse dumping

234

      /// is provided in the path dumper. In this case, \c RevArcIt

235

      /// iterator should be implemented instead of \c ArcIt iterator.

234

236

      typedef False RevPathTag;

235

237

236

      /// \brief LEMON style iterator for path arcs

238

      /// \brief LEMON style iterator for enumerating the arcs of a path.

237

239

///

238

      /// This class is used to iterate on the arcs of the paths.

240

      /// LEMON style iterator class for enumerating the arcs of a path.

239

241

      class ArcIt {

240

242

      public:

241

243

        /// Default constructor

242

244

        ArcIt() {}

243

245

        /// Invalid constructor

244

246

        ArcIt(Invalid) {}

245

        /// Constructor for first arc

247

        /// Sets the iterator to the first arc of the given path

246

248

        ArcIt(const PathDumper&) {}

247

249

248

        /// Conversion to Arc

250

        /// Conversion to \c Arc

249

251

        operator Arc() const { return INVALID; }

        /// Next arc

252

254

        ArcIt& operator++() {return *this;}

        /// Comparison operator

255

257

        bool operator==(const ArcIt&) const {return true;}

256

258

        /// Comparison operator

257

259

        bool operator!=(const ArcIt&) const {return true;}

258

260

        /// Comparison operator

259

261

        bool operator<(const ArcIt&) const {return false;}

};

262

264

263

      /// \brief LEMON style iterator for path arcs

265

      /// \brief LEMON style iterator for enumerating the arcs of a path

266

      /// in reverse direction.

264

267

///

265

      /// This class is used to iterate on the arcs of the paths in

266

      /// reverse direction.

268

      /// LEMON style iterator class for enumerating the arcs of a path

269

      /// in reverse direction.

267

270

      class RevArcIt {

268

271

      public:

269

272

        /// Default constructor

270

273

        RevArcIt() {}

271

274

        /// Invalid constructor

272

275

        RevArcIt(Invalid) {}

273

        /// Constructor for first arc

276

        /// Sets the iterator to the last arc of the given path

274

277

        RevArcIt(const PathDumper &) {}

275

278

276

        /// Conversion to Arc

279

        /// Conversion to \c Arc

277

280

        operator Arc() const { return INVALID; }

        /// Next arc

280

283

        RevArcIt& operator++() {return *this;}

        /// Comparison operator

283

286

        bool operator==(const RevArcIt&) const {return true;}

284

287

        /// Comparison operator

285

288

        bool operator!=(const RevArcIt&) const {return true;}

286

289

        /// Comparison operator

287

290

        bool operator<(const RevArcIt&) const {return false;}

};

      template <typename _Path>

292

295

      struct Constraints {

RhodeCode

Login to your account