src/work/klao/path.h
author marci
Fri, 21 May 2004 10:57:30 +0000
changeset 655 a9878222d5c8
parent 607 327f7cf13843
child 682 1ea8162ce638
permissions -rw-r--r--
bug correction in BidirGraphWrapper<Graph> default constructor
klao@225
     1
// -*- c++ -*- //
klao@225
     2
klao@493
     3
///\ingroup datas
alpar@434
     4
///\file
klao@493
     5
///\brief Classes for representing paths in graphs.
klao@225
     6
klao@225
     7
#ifndef HUGO_PATH_H
klao@225
     8
#define HUGO_PATH_H
klao@225
     9
klao@225
    10
#include <deque>
klao@369
    11
#include <vector>
klao@226
    12
#include <algorithm>
klao@225
    13
athos@607
    14
#include <hugo/invalid.h>
athos@607
    15
#include <hugo/error.h>
klao@493
    16
#include <debug.h>
klao@225
    17
klao@225
    18
namespace hugo {
klao@225
    19
alpar@434
    20
  /// \addtogroup datas
alpar@434
    21
  /// @{
alpar@434
    22
alpar@434
    23
klao@493
    24
  //! \brief A structure for representing directed path in a graph.
klao@493
    25
  //!
klao@619
    26
  //! A structure for representing directed path in a graph.
klao@493
    27
  //! \param Graph The graph type in which the path is.
klao@493
    28
  //! \param DM DebugMode, defaults to DefaultDebugMode.
klao@493
    29
  //! 
klao@493
    30
  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
klao@493
    31
  //! and \c EdgeIt with the same usage. These types converts to the \c Node
klao@493
    32
  //! and \c Edge of the original graph.
klao@493
    33
  //!
klao@493
    34
  //! \todo Thoroughfully check all the range and consistency tests.
klao@493
    35
  template<typename Graph, typename DM = DefaultDebugMode>
klao@369
    36
  class DirPath {
klao@369
    37
  public:
klao@369
    38
    typedef typename Graph::Edge GraphEdge;
klao@369
    39
    typedef typename Graph::Node GraphNode;
klao@369
    40
    class NodeIt;
klao@369
    41
    class EdgeIt;
klao@369
    42
klao@369
    43
  protected:
klao@369
    44
    const Graph *gr;
klao@369
    45
    typedef std::vector<GraphEdge> Container;
klao@369
    46
    Container edges;
klao@369
    47
klao@369
    48
  public:
klao@369
    49
alpar@434
    50
    /// \param _G The graph in which the path is.
alpar@434
    51
    ///
klao@369
    52
    DirPath(const Graph &_G) : gr(&_G) {}
klao@369
    53
klao@493
    54
    /// \brief Subpath constructor.
klao@493
    55
    ///
klao@369
    56
    /// Subpath defined by two nodes.
alpar@434
    57
    /// \warning It is an error if the two edges are not in order!
klao@619
    58
    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
klao@619
    59
      if( DM::range_check && (!a.valid() || !b.valid) ) {
klao@619
    60
	// FIXME: this check should be more elaborate...
klao@619
    61
	fault("DirPath, subpath ctor: invalid bounding nodes");
klao@619
    62
      }
klao@619
    63
      gr = P.gr;
klao@619
    64
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
klao@619
    65
    }
klao@619
    66
klao@493
    67
    /// \brief Subpath constructor.
klao@493
    68
    ///
klao@369
    69
    /// Subpath defined by two edges. Contains edges in [a,b)
alpar@434
    70
    /// \warning It is an error if the two edges are not in order!
klao@619
    71
    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
klao@619
    72
      if( DM::range_check && (!a.valid() || !b.valid) ) {
klao@619
    73
	// FIXME: this check should be more elaborate...
klao@619
    74
	fault("DirPath, subpath ctor: invalid bounding nodes");
klao@619
    75
      }
klao@619
    76
      gr = P.gr;
klao@619
    77
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
klao@619
    78
    }
klao@369
    79
klao@493
    80
    /// Length of the path.
klao@369
    81
    size_t length() const { return edges.size(); }
klao@493
    82
    /// Returns whether the path is empty.
klao@369
    83
    bool empty() const { return edges.empty(); }
klao@493
    84
klao@493
    85
    /// Resets the path to an empty path.
klao@493
    86
    void clear() { edges.clear(); }
klao@493
    87
klao@493
    88
    /// \brief Starting point of the path.
klao@493
    89
    ///
klao@493
    90
    /// Starting point of the path.
klao@493
    91
    /// Returns INVALID if the path is empty.
klao@369
    92
    GraphNode from() const {
klao@369
    93
      return empty() ? INVALID : gr->tail(edges[0]);
klao@369
    94
    }
klao@493
    95
    /// \brief End point of the path.
klao@493
    96
    ///
klao@493
    97
    /// End point of the path.
klao@493
    98
    /// Returns INVALID if the path is empty.
klao@369
    99
    GraphNode to() const {
klao@369
   100
      return empty() ? INVALID : gr->head(edges[length()-1]);
klao@369
   101
    }
klao@369
   102
klao@493
   103
    /// \brief Initializes node or edge iterator to point to the first
klao@493
   104
    /// node or edge.
klao@493
   105
    ///
klao@493
   106
    /// \sa nth
klao@369
   107
    template<typename It>
klao@369
   108
    It& first(It &i) const { return i=It(*this); }
klao@369
   109
klao@619
   110
    /// \brief Initializes node iterator to point to the node of a given index.
klao@619
   111
    NodeIt& nth(NodeIt &i, int n) const {
klao@493
   112
      if( DM::range_check && (n<0 || n>int(length())) )
klao@493
   113
	fault("DirPath::nth: index out of range");
klao@619
   114
      return i=NodeIt(*this, n);
klao@619
   115
    }
klao@619
   116
klao@619
   117
    /// \brief Initializes edge iterator to point to the edge of a given index.
klao@619
   118
    EdgeIt& nth(EdgeIt &i, int n) const {
klao@619
   119
      if( DM::range_check && (n<0 || n>=int(length())) )
klao@619
   120
	fault("DirPath::nth: index out of range");
klao@619
   121
      return i=EdgeIt(*this, n);
klao@493
   122
    }
klao@369
   123
klao@493
   124
    /// Checks validity of a node or edge iterator.
klao@369
   125
    template<typename It>
klao@619
   126
    static
klao@619
   127
    bool valid(const It &i) { return i.valid(); }
klao@369
   128
klao@493
   129
    /// Steps the given node or edge iterator.
klao@369
   130
    template<typename It>
klao@619
   131
    static
klao@619
   132
    It& next(It &e) {
klao@493
   133
      if( DM::range_check && !e.valid() )
klao@493
   134
	fault("DirPath::next() on invalid iterator");
klao@493
   135
      return ++e;
klao@493
   136
    }
klao@369
   137
klao@493
   138
    /// \brief Returns node iterator pointing to the head node of the
klao@493
   139
    /// given edge iterator.
klao@493
   140
    NodeIt head(const EdgeIt& e) const {
klao@619
   141
      if( DM::range_check && !e.valid() )
klao@619
   142
	fault("DirPath::head() on invalid iterator");
klao@493
   143
      return NodeIt(*this, e.idx+1);
klao@493
   144
    }
klao@493
   145
klao@493
   146
    /// \brief Returns node iterator pointing to the tail node of the
klao@493
   147
    /// given edge iterator.
klao@493
   148
    NodeIt tail(const EdgeIt& e) const {
klao@619
   149
      if( DM::range_check && !e.valid() )
klao@619
   150
	fault("DirPath::tail() on invalid iterator");
klao@493
   151
      return NodeIt(*this, e.idx);
klao@493
   152
    }
klao@369
   153
klao@369
   154
klao@369
   155
    /*** Iterator classes ***/
klao@369
   156
    class EdgeIt {
klao@369
   157
      friend class DirPath;
klao@369
   158
klao@369
   159
      int idx;
klao@369
   160
      const DirPath *p;
klao@369
   161
    public:
klao@369
   162
      EdgeIt() {}
klao@369
   163
      EdgeIt(Invalid) : idx(-1), p(0) {}
klao@369
   164
      EdgeIt(const DirPath &_p, int _idx = 0) :
klao@369
   165
	idx(_idx), p(&_p) { validate(); }
klao@369
   166
klao@369
   167
      bool valid() const { return idx!=-1; }
klao@369
   168
klao@369
   169
      operator GraphEdge () const {
klao@369
   170
	return valid() ? p->edges[idx] : INVALID;
klao@369
   171
      }
klao@369
   172
      EdgeIt& operator++() { ++idx; validate(); return *this; }
klao@369
   173
klao@369
   174
      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
klao@369
   175
      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
klao@369
   176
      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
klao@369
   177
klao@369
   178
    private:
klao@369
   179
      // FIXME: comparison between signed and unsigned...
klao@369
   180
      // Jo ez igy? Vagy esetleg legyen a length() int?
klao@369
   181
      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
klao@369
   182
    };
klao@369
   183
klao@369
   184
    class NodeIt {
klao@369
   185
      friend class DirPath;
klao@369
   186
klao@369
   187
      int idx;
klao@369
   188
      const DirPath *p;
klao@369
   189
    public:
klao@369
   190
      NodeIt() {}
klao@369
   191
      NodeIt(Invalid) : idx(-1), p(0) {}
klao@369
   192
      NodeIt(const DirPath &_p, int _idx = 0) :
klao@369
   193
	idx(_idx), p(&_p) { validate(); }
klao@369
   194
klao@369
   195
      bool valid() const { return idx!=-1; }
klao@369
   196
klao@619
   197
      operator const GraphNode& () const {
klao@369
   198
	if(idx >= p->length())
klao@369
   199
	  return p->to();
klao@369
   200
	else if(idx >= 0)
klao@369
   201
	  return p->gr->tail(p->edges[idx]);
klao@369
   202
	else
klao@369
   203
	  return INVALID;
klao@369
   204
      }
klao@369
   205
      NodeIt& operator++() { ++idx; validate(); return *this; }
klao@369
   206
klao@369
   207
      bool operator==(const NodeIt& e) const { return idx==e.idx; }
klao@369
   208
      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
klao@369
   209
      bool operator<(const NodeIt& e) const { return idx<e.idx; }
klao@369
   210
klao@369
   211
    private:
klao@369
   212
      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
klao@369
   213
    };
klao@369
   214
klao@369
   215
    friend class Builder;    
alpar@434
   216
klao@493
   217
    /**
klao@493
   218
     * \brief Class to build paths
klao@493
   219
     * 
klao@493
   220
     * \ingroup datas
klao@493
   221
     * This class is used to fill a path with edges.
klao@493
   222
     *
klao@493
   223
     * You can push new edges to the front and to the back of the path in
klao@619
   224
     * arbitrary order then you should commit these changes to the graph.
klao@493
   225
     *
klao@493
   226
     * Fundamentally, for most "Paths" (classes fulfilling the
klao@493
   227
     * PathConcept) while the builder is active (after the first modifying
klao@493
   228
     * operation and until the commit()) the original Path is in a
klao@493
   229
     * "transitional" state (operations ot it have undefined result). But
klao@493
   230
     * in the case of DirPath the original path is unchanged until the
klao@493
   231
     * commit. However we don't recomend that you use this feature.
klao@493
   232
     */
klao@369
   233
    class Builder {
klao@369
   234
      DirPath &P;
klao@493
   235
      Container front, back;
klao@369
   236
klao@369
   237
    public:
klao@493
   238
      ///\param _P the path you want to fill in.
alpar@434
   239
      ///
klao@369
   240
      Builder(DirPath &_P) : P(_P) {}
klao@369
   241
klao@619
   242
      /// Sets the starting node of the path.
alpar@434
   243
      
klao@619
   244
      /// Sets the starting node of the path. Edge added to the path
klao@619
   245
      /// afterwards have to be incident to this node.
klao@619
   246
      /// It should be called iff the path is empty and before any call to
klao@619
   247
      /// \ref pushFront() or \ref pushBack()
klao@619
   248
      void setStart(const GraphNode &) {}
klao@619
   249
alpar@434
   250
      ///Push a new edge to the front of the path
alpar@434
   251
alpar@434
   252
      ///Push a new edge to the front of the path.
klao@619
   253
      ///\sa setStart
klao@493
   254
      void pushFront(const GraphEdge& e) {
klao@493
   255
	if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
klao@493
   256
	  fault("DirPath::Builder::pushFront: nonincident edge");
klao@369
   257
	}
klao@493
   258
	front.push_back(e);
klao@369
   259
      }
klao@493
   260
alpar@434
   261
      ///Push a new edge to the back of the path
alpar@434
   262
alpar@434
   263
      ///Push a new edge to the back of the path.
klao@619
   264
      ///\sa setStart
klao@493
   265
      void pushBack(const GraphEdge& e) {
klao@493
   266
	if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
klao@493
   267
	  fault("DirPath::Builder::pushBack: nonincident edge");
klao@369
   268
	}
klao@493
   269
	back.push_back(e);
klao@369
   270
      }
klao@369
   271
alpar@434
   272
      ///Commit the changes to the path.
klao@369
   273
      void commit() {
klao@493
   274
	if( !(front.empty() && back.empty()) ) {
klao@493
   275
	  Container tmp;
klao@493
   276
	  tmp.reserve(front.size()+back.size()+P.length());
klao@493
   277
	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
klao@493
   278
	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
klao@493
   279
	  tmp.insert(tmp.end(), back.begin(), back.end());
klao@493
   280
	  P.edges.swap(tmp);
klao@493
   281
	  front.clear();
klao@493
   282
	  back.clear();
klao@369
   283
	}
klao@369
   284
      }
klao@369
   285
klao@619
   286
      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
klao@619
   287
      // Hogy kenyelmes egy ilyet hasznalni?
klao@619
   288
      void reserve(size_t r) {
klao@619
   289
	front.reserve(r);
klao@619
   290
	back.reserve(r);
klao@619
   291
      }
alpar@434
   292
klao@619
   293
    private:
klao@619
   294
      bool empty() {
klao@619
   295
	return front.empty() && back.empty() && P.empty();
klao@619
   296
      }
klao@619
   297
klao@619
   298
      GraphNode from() const {
klao@619
   299
	if( ! front.empty() )
klao@619
   300
	  return P.gr->tail(front[front.size()-1]);
klao@619
   301
	else if( ! P.empty() )
klao@619
   302
	  return P.gr->tail(P.edges[0]);
klao@619
   303
	else if( ! back.empty() )
klao@619
   304
	  return P.gr->tail(back[0]);
klao@619
   305
	else
klao@619
   306
	  return INVALID;
klao@619
   307
      }
klao@619
   308
      GraphNode to() const {
klao@619
   309
	if( ! back.empty() )
klao@619
   310
	  return P.gr->head(back[back.size()-1]);
klao@619
   311
	else if( ! P.empty() )
klao@619
   312
	  return P.gr->head(P.edges[P.length()-1]);
klao@619
   313
	else if( ! front.empty() )
klao@619
   314
	  return P.gr->head(front[0]);
klao@619
   315
	else
klao@619
   316
	  return INVALID;
klao@619
   317
      }
klao@619
   318
klao@619
   319
    };
klao@619
   320
klao@619
   321
  };
klao@619
   322
klao@619
   323
klao@619
   324
klao@619
   325
klao@619
   326
klao@619
   327
klao@619
   328
klao@619
   329
klao@619
   330
klao@619
   331
klao@619
   332
  /**********************************************************************/
klao@619
   333
klao@619
   334
klao@619
   335
  //! \brief A structure for representing undirected path in a graph.
klao@619
   336
  //!
klao@619
   337
  //! A structure for representing undirected path in a graph. Ie. this is
klao@619
   338
  //! a path in a \e directed graph but the edges should not be directed
klao@619
   339
  //! forward.
klao@619
   340
  //!
klao@619
   341
  //! \param Graph The graph type in which the path is.
klao@619
   342
  //! \param DM DebugMode, defaults to DefaultDebugMode.
klao@619
   343
  //! 
klao@619
   344
  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
klao@619
   345
  //! and \c EdgeIt with the same usage. These types converts to the \c Node
klao@619
   346
  //! and \c Edge of the original graph.
klao@619
   347
  //!
klao@619
   348
  //! \todo Thoroughfully check all the range and consistency tests.
klao@619
   349
  template<typename Graph, typename DM = DefaultDebugMode>
klao@619
   350
  class UndirPath {
klao@619
   351
  public:
klao@619
   352
    typedef typename Graph::Edge GraphEdge;
klao@619
   353
    typedef typename Graph::Node GraphNode;
klao@619
   354
    class NodeIt;
klao@619
   355
    class EdgeIt;
klao@619
   356
klao@619
   357
  protected:
klao@619
   358
    const Graph *gr;
klao@619
   359
    typedef std::vector<GraphEdge> Container;
klao@619
   360
    Container edges;
klao@619
   361
klao@619
   362
  public:
klao@619
   363
klao@619
   364
    /// \param _G The graph in which the path is.
klao@619
   365
    ///
klao@619
   366
    UndirPath(const Graph &_G) : gr(&_G) {}
klao@619
   367
klao@619
   368
    /// \brief Subpath constructor.
klao@619
   369
    ///
klao@619
   370
    /// Subpath defined by two nodes.
klao@619
   371
    /// \warning It is an error if the two edges are not in order!
klao@619
   372
    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
klao@619
   373
      if( DM::range_check && (!a.valid() || !b.valid) ) {
klao@619
   374
	// FIXME: this check should be more elaborate...
klao@619
   375
	fault("UndirPath, subpath ctor: invalid bounding nodes");
klao@619
   376
      }
klao@619
   377
      gr = P.gr;
klao@619
   378
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
klao@619
   379
    }
klao@619
   380
klao@619
   381
    /// \brief Subpath constructor.
klao@619
   382
    ///
klao@619
   383
    /// Subpath defined by two edges. Contains edges in [a,b)
klao@619
   384
    /// \warning It is an error if the two edges are not in order!
klao@619
   385
    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
klao@619
   386
      if( DM::range_check && (!a.valid() || !b.valid) ) {
klao@619
   387
	// FIXME: this check should be more elaborate...
klao@619
   388
	fault("UndirPath, subpath ctor: invalid bounding nodes");
klao@619
   389
      }
klao@619
   390
      gr = P.gr;
klao@619
   391
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
klao@619
   392
    }
klao@619
   393
klao@619
   394
    /// Length of the path.
klao@619
   395
    size_t length() const { return edges.size(); }
klao@619
   396
    /// Returns whether the path is empty.
klao@619
   397
    bool empty() const { return edges.empty(); }
klao@619
   398
klao@619
   399
    /// Resets the path to an empty path.
klao@619
   400
    void clear() { edges.clear(); }
klao@619
   401
klao@619
   402
    /// \brief Starting point of the path.
klao@619
   403
    ///
klao@619
   404
    /// Starting point of the path.
klao@619
   405
    /// Returns INVALID if the path is empty.
klao@619
   406
    GraphNode from() const {
klao@619
   407
      return empty() ? INVALID : gr->tail(edges[0]);
klao@619
   408
    }
klao@619
   409
    /// \brief End point of the path.
klao@619
   410
    ///
klao@619
   411
    /// End point of the path.
klao@619
   412
    /// Returns INVALID if the path is empty.
klao@619
   413
    GraphNode to() const {
klao@619
   414
      return empty() ? INVALID : gr->head(edges[length()-1]);
klao@619
   415
    }
klao@619
   416
klao@619
   417
    /// \brief Initializes node or edge iterator to point to the first
klao@619
   418
    /// node or edge.
klao@619
   419
    ///
klao@619
   420
    /// \sa nth
klao@619
   421
    template<typename It>
klao@619
   422
    It& first(It &i) const { return i=It(*this); }
klao@619
   423
klao@619
   424
    /// \brief Initializes node iterator to point to the node of a given index.
klao@619
   425
    NodeIt& nth(NodeIt &i, int n) const {
klao@619
   426
      if( DM::range_check && (n<0 || n>int(length())) )
klao@619
   427
	fault("UndirPath::nth: index out of range");
klao@619
   428
      return i=NodeIt(*this, n);
klao@619
   429
    }
klao@619
   430
klao@619
   431
    /// \brief Initializes edge iterator to point to the edge of a given index.
klao@619
   432
    EdgeIt& nth(EdgeIt &i, int n) const {
klao@619
   433
      if( DM::range_check && (n<0 || n>=int(length())) )
klao@619
   434
	fault("UndirPath::nth: index out of range");
klao@619
   435
      return i=EdgeIt(*this, n);
klao@619
   436
    }
klao@619
   437
klao@619
   438
    /// Checks validity of a node or edge iterator.
klao@619
   439
    template<typename It>
klao@619
   440
    static
klao@619
   441
    bool valid(const It &i) { return i.valid(); }
klao@619
   442
klao@619
   443
    /// Steps the given node or edge iterator.
klao@619
   444
    template<typename It>
klao@619
   445
    static
klao@619
   446
    It& next(It &e) {
klao@619
   447
      if( DM::range_check && !e.valid() )
klao@619
   448
	fault("UndirPath::next() on invalid iterator");
klao@619
   449
      return ++e;
klao@619
   450
    }
klao@619
   451
klao@619
   452
    /// \brief Returns node iterator pointing to the head node of the
klao@619
   453
    /// given edge iterator.
klao@619
   454
    NodeIt head(const EdgeIt& e) const {
klao@619
   455
      if( DM::range_check && !e.valid() )
klao@619
   456
	fault("UndirPath::head() on invalid iterator");
klao@619
   457
      return NodeIt(*this, e.idx+1);
klao@619
   458
    }
klao@619
   459
klao@619
   460
    /// \brief Returns node iterator pointing to the tail node of the
klao@619
   461
    /// given edge iterator.
klao@619
   462
    NodeIt tail(const EdgeIt& e) const {
klao@619
   463
      if( DM::range_check && !e.valid() )
klao@619
   464
	fault("UndirPath::tail() on invalid iterator");
klao@619
   465
      return NodeIt(*this, e.idx);
klao@619
   466
    }
klao@619
   467
klao@619
   468
klao@619
   469
    /*** Iterator classes ***/
klao@619
   470
    class EdgeIt {
klao@619
   471
      friend class UndirPath;
klao@619
   472
klao@619
   473
      int idx;
klao@619
   474
      const UndirPath *p;
klao@619
   475
    public:
klao@619
   476
      EdgeIt() {}
klao@619
   477
      EdgeIt(Invalid) : idx(-1), p(0) {}
klao@619
   478
      EdgeIt(const UndirPath &_p, int _idx = 0) :
klao@619
   479
	idx(_idx), p(&_p) { validate(); }
klao@619
   480
klao@619
   481
      bool valid() const { return idx!=-1; }
klao@619
   482
klao@619
   483
      operator GraphEdge () const {
klao@619
   484
	return valid() ? p->edges[idx] : INVALID;
klao@619
   485
      }
klao@619
   486
      EdgeIt& operator++() { ++idx; validate(); return *this; }
klao@619
   487
klao@619
   488
      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
klao@619
   489
      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
klao@619
   490
      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
klao@619
   491
klao@619
   492
    private:
klao@619
   493
      // FIXME: comparison between signed and unsigned...
klao@619
   494
      // Jo ez igy? Vagy esetleg legyen a length() int?
klao@619
   495
      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
klao@619
   496
    };
klao@619
   497
klao@619
   498
    class NodeIt {
klao@619
   499
      friend class UndirPath;
klao@619
   500
klao@619
   501
      int idx;
klao@619
   502
      const UndirPath *p;
klao@619
   503
    public:
klao@619
   504
      NodeIt() {}
klao@619
   505
      NodeIt(Invalid) : idx(-1), p(0) {}
klao@619
   506
      NodeIt(const UndirPath &_p, int _idx = 0) :
klao@619
   507
	idx(_idx), p(&_p) { validate(); }
klao@619
   508
klao@619
   509
      bool valid() const { return idx!=-1; }
klao@619
   510
klao@619
   511
      operator const GraphNode& () const {
klao@619
   512
	if(idx >= p->length())
klao@619
   513
	  return p->to();
klao@619
   514
	else if(idx >= 0)
klao@619
   515
	  return p->gr->tail(p->edges[idx]);
klao@619
   516
	else
klao@619
   517
	  return INVALID;
klao@619
   518
      }
klao@619
   519
      NodeIt& operator++() { ++idx; validate(); return *this; }
klao@619
   520
klao@619
   521
      bool operator==(const NodeIt& e) const { return idx==e.idx; }
klao@619
   522
      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
klao@619
   523
      bool operator<(const NodeIt& e) const { return idx<e.idx; }
klao@619
   524
klao@619
   525
    private:
klao@619
   526
      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
klao@619
   527
    };
klao@619
   528
klao@619
   529
    friend class Builder;    
klao@619
   530
klao@619
   531
    /**
klao@619
   532
     * \brief Class to build paths
klao@619
   533
     * 
klao@619
   534
     * \ingroup datas
klao@619
   535
     * This class is used to fill a path with edges.
klao@619
   536
     *
klao@619
   537
     * You can push new edges to the front and to the back of the path in
klao@619
   538
     * arbitrary order then you should commit these changes to the graph.
klao@619
   539
     *
klao@619
   540
     * Fundamentally, for most "Paths" (classes fulfilling the
klao@619
   541
     * PathConcept) while the builder is active (after the first modifying
klao@619
   542
     * operation and until the commit()) the original Path is in a
klao@619
   543
     * "transitional" state (operations ot it have undefined result). But
klao@619
   544
     * in the case of UndirPath the original path is unchanged until the
klao@619
   545
     * commit. However we don't recomend that you use this feature.
klao@619
   546
     */
klao@619
   547
    class Builder {
klao@619
   548
      UndirPath &P;
klao@619
   549
      Container front, back;
klao@619
   550
klao@619
   551
    public:
klao@619
   552
      ///\param _P the path you want to fill in.
klao@619
   553
      ///
klao@619
   554
      Builder(UndirPath &_P) : P(_P) {}
klao@619
   555
klao@619
   556
      /// Sets the starting node of the path.
klao@619
   557
      
klao@619
   558
      /// Sets the starting node of the path. Edge added to the path
klao@619
   559
      /// afterwards have to be incident to this node.
klao@619
   560
      /// It should be called iff the path is empty and before any call to
klao@619
   561
      /// \ref pushFront() or \ref pushBack()
klao@619
   562
      void setStart(const GraphNode &) {}
klao@619
   563
klao@619
   564
      ///Push a new edge to the front of the path
klao@619
   565
klao@619
   566
      ///Push a new edge to the front of the path.
klao@619
   567
      ///\sa setStart
klao@619
   568
      void pushFront(const GraphEdge& e) {
klao@619
   569
	if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
klao@619
   570
	  fault("UndirPath::Builder::pushFront: nonincident edge");
klao@619
   571
	}
klao@619
   572
	front.push_back(e);
klao@619
   573
      }
klao@619
   574
klao@619
   575
      ///Push a new edge to the back of the path
klao@619
   576
klao@619
   577
      ///Push a new edge to the back of the path.
klao@619
   578
      ///\sa setStart
klao@619
   579
      void pushBack(const GraphEdge& e) {
klao@619
   580
	if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
klao@619
   581
	  fault("UndirPath::Builder::pushBack: nonincident edge");
klao@619
   582
	}
klao@619
   583
	back.push_back(e);
klao@619
   584
      }
klao@619
   585
klao@619
   586
      ///Commit the changes to the path.
klao@619
   587
      void commit() {
klao@619
   588
	if( !(front.empty() && back.empty()) ) {
klao@619
   589
	  Container tmp;
klao@619
   590
	  tmp.reserve(front.size()+back.size()+P.length());
klao@619
   591
	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
klao@619
   592
	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
klao@619
   593
	  tmp.insert(tmp.end(), back.begin(), back.end());
klao@619
   594
	  P.edges.swap(tmp);
klao@619
   595
	  front.clear();
klao@619
   596
	  back.clear();
klao@619
   597
	}
klao@619
   598
      }
klao@369
   599
klao@369
   600
      // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
klao@369
   601
      // Hogy kenyelmes egy ilyet hasznalni?
klao@369
   602
      void reserve(size_t r) {
klao@493
   603
	front.reserve(r);
klao@493
   604
	back.reserve(r);
klao@369
   605
      }
klao@369
   606
klao@369
   607
    private:
klao@493
   608
      bool empty() {
klao@493
   609
	return front.empty() && back.empty() && P.empty();
klao@493
   610
      }
klao@369
   611
klao@369
   612
      GraphNode from() const {
klao@493
   613
	if( ! front.empty() )
klao@493
   614
	  return P.gr->tail(front[front.size()-1]);
klao@369
   615
	else if( ! P.empty() )
klao@369
   616
	  return P.gr->tail(P.edges[0]);
klao@493
   617
	else if( ! back.empty() )
klao@493
   618
	  return P.gr->tail(back[0]);
klao@369
   619
	else
klao@369
   620
	  return INVALID;
klao@369
   621
      }
klao@369
   622
      GraphNode to() const {
klao@493
   623
	if( ! back.empty() )
klao@493
   624
	  return P.gr->head(back[back.size()-1]);
klao@493
   625
	else if( ! P.empty() )
klao@369
   626
	  return P.gr->head(P.edges[P.length()-1]);
klao@493
   627
	else if( ! front.empty() )
klao@493
   628
	  return P.gr->head(front[0]);
klao@369
   629
	else
klao@369
   630
	  return INVALID;
klao@369
   631
      }
klao@369
   632
klao@369
   633
    };
klao@369
   634
klao@369
   635
  };
klao@369
   636
klao@369
   637
klao@369
   638
klao@369
   639
klao@369
   640
klao@369
   641
klao@369
   642
klao@369
   643
klao@369
   644
klao@369
   645
klao@369
   646
  /**********************************************************************/
klao@369
   647
klao@369
   648
klao@225
   649
  /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
klao@225
   650
     elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
klao@225
   651
klao@225
   652
  template<typename Graph>
klao@369
   653
  class DynamicPath {
klao@225
   654
klao@225
   655
  public:
klao@225
   656
    typedef typename Graph::Edge GraphEdge;
klao@225
   657
    typedef typename Graph::Node GraphNode;
klao@225
   658
    class NodeIt;
klao@225
   659
    class EdgeIt;
klao@225
   660
klao@225
   661
  protected:
klao@225
   662
    Graph& G;
klao@225
   663
    // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
klao@225
   664
    // iranyitasat:
klao@225
   665
    GraphNode _first, _last;
klao@225
   666
    typedef std::deque<GraphEdge> Container;
klao@225
   667
    Container edges;
klao@225
   668
klao@225
   669
  public:
klao@225
   670
klao@369
   671
    DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
klao@225
   672
klao@226
   673
    /// Subpath defined by two nodes.
klao@226
   674
    /// Nodes may be in reversed order, then
klao@226
   675
    /// we contstruct the reversed path.
klao@369
   676
    DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
klao@226
   677
    /// Subpath defined by two edges. Contains edges in [a,b)
klao@226
   678
    /// It is an error if the two edges are not in order!
klao@369
   679
    DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
klao@225
   680
    
klao@225
   681
    size_t length() const { return edges.size(); }
klao@225
   682
    GraphNode from() const { return _first; }
klao@225
   683
    GraphNode to() const { return _last; }
klao@225
   684
klao@225
   685
    NodeIt& first(NodeIt &n) const { return nth(n, 0); }
klao@225
   686
    EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
klao@225
   687
    template<typename It>
klao@225
   688
    It first() const { 
klao@225
   689
      It e;
klao@225
   690
      first(e);
klao@225
   691
      return e; 
klao@225
   692
    }
klao@225
   693
klao@225
   694
    NodeIt& nth(NodeIt &, size_t) const;
klao@225
   695
    EdgeIt& nth(EdgeIt &, size_t) const;
klao@225
   696
    template<typename It>
klao@225
   697
    It nth(size_t n) const { 
klao@225
   698
      It e;
klao@225
   699
      nth(e, n);
klao@225
   700
      return e; 
klao@225
   701
    }
klao@225
   702
klao@225
   703
    bool valid(const NodeIt &n) const { return n.idx <= length(); }
klao@225
   704
    bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
klao@225
   705
klao@225
   706
    bool isForward(const EdgeIt &e) const { return e.forw; }
klao@225
   707
klao@226
   708
    /// index of a node on the path. Returns length+2 for the invalid NodeIt
klao@226
   709
    int index(const NodeIt &n) const { return n.idx; }
klao@226
   710
    /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
klao@226
   711
    int index(const EdgeIt &e) const { return e.it - edges.begin(); }
klao@226
   712
klao@225
   713
    EdgeIt& next(EdgeIt &e) const;
klao@225
   714
    NodeIt& next(NodeIt &n) const;
klao@225
   715
    template <typename It>
klao@225
   716
    It getNext(It it) const {
klao@225
   717
      It tmp(it); return next(tmp);
klao@225
   718
    }
klao@225
   719
klao@225
   720
    // A path is constructed using the following four functions.
klao@225
   721
    // They return false if the requested operation is inconsistent
klao@225
   722
    // with the path constructed so far.
klao@225
   723
    // If your path has only one edge you MUST set either "from" or "to"!
klao@225
   724
    // So you probably SHOULD call it in any case to be safe (and check the
klao@225
   725
    // returned value to check if your path is consistent with your idea).
klao@225
   726
    bool pushFront(const GraphEdge &e);
klao@225
   727
    bool pushBack(const GraphEdge &e);
klao@225
   728
    bool setFrom(const GraphNode &n);
klao@225
   729
    bool setTo(const GraphNode &n);
klao@225
   730
klao@225
   731
    // WARNING: these two functions return the head/tail of an edge with
klao@225
   732
    // respect to the direction of the path!
klao@225
   733
    // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if 
klao@225
   734
    // P.forward(e) is true (or the edge is a loop)!
klao@225
   735
    NodeIt head(const EdgeIt& e) const;
klao@225
   736
    NodeIt tail(const EdgeIt& e) const;
klao@225
   737
klao@225
   738
    // FIXME: ezeknek valami jobb nev kellene!!!
klao@225
   739
    GraphEdge graphEdge(const EdgeIt& e) const;
klao@225
   740
    GraphNode graphNode(const NodeIt& n) const;
klao@225
   741
klao@225
   742
klao@225
   743
    /*** Iterator classes ***/
klao@225
   744
    class EdgeIt {
klao@369
   745
      friend class DynamicPath;
klao@225
   746
klao@225
   747
      typename Container::const_iterator it;
klao@225
   748
      bool forw;
klao@225
   749
    public:
klao@225
   750
      // FIXME: jarna neki ilyen is...
klao@225
   751
      // EdgeIt(Invalid);
klao@225
   752
klao@225
   753
      bool forward() const { return forw; }
klao@225
   754
klao@225
   755
      bool operator==(const EdgeIt& e) const { return it==e.it; }
klao@225
   756
      bool operator!=(const EdgeIt& e) const { return it!=e.it; }
klao@225
   757
      bool operator<(const EdgeIt& e) const { return it<e.it; }
klao@225
   758
    };
klao@225
   759
klao@225
   760
    class NodeIt {
klao@369
   761
      friend class DynamicPath;
klao@225
   762
klao@226
   763
      size_t idx;
klao@225
   764
      bool tail;  // Is this node the tail of the edge with same idx?
klao@225
   765
klao@225
   766
    public:
klao@225
   767
      // FIXME: jarna neki ilyen is...
klao@225
   768
      // NodeIt(Invalid);
klao@225
   769
klao@225
   770
      bool operator==(const NodeIt& n) const { return idx==n.idx; }
klao@225
   771
      bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
klao@225
   772
      bool operator<(const NodeIt& n) const { return idx<n.idx; }
klao@225
   773
    };
klao@225
   774
klao@225
   775
  private:
klao@225
   776
    bool edgeIncident(const GraphEdge &e, const GraphNode &a,
klao@225
   777
		      GraphNode &b);
klao@225
   778
    bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
klao@225
   779
  };
klao@225
   780
klao@225
   781
  template<typename Gr>
klao@369
   782
  typename DynamicPath<Gr>::EdgeIt&
klao@369
   783
  DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
klao@225
   784
    if( e.it == edges.end() ) 
klao@225
   785
      return e;
klao@225
   786
klao@225
   787
    GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
klao@225
   788
    ++e.it;
klao@225
   789
klao@225
   790
    // Invalid edgeit is always forward :)
klao@225
   791
    if( e.it == edges.end() ) {
klao@225
   792
      e.forw = true;
klao@225
   793
      return e;
klao@225
   794
    }
klao@225
   795
klao@225
   796
    e.forw = ( G.tail(*e.it) == common_node );
klao@225
   797
    return e;
klao@225
   798
  }
klao@225
   799
klao@225
   800
  template<typename Gr>
klao@369
   801
  typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
klao@225
   802
    if( n.idx >= length() ) {
klao@225
   803
      // FIXME: invalid
klao@225
   804
      n.idx = length()+1;
klao@225
   805
      return n;
klao@225
   806
    }
klao@225
   807
klao@225
   808
    
klao@225
   809
    GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
klao@225
   810
			      G.tail(edges[n.idx]) );
klao@225
   811
    ++n.idx;
klao@225
   812
    if( n.idx < length() ) {
klao@225
   813
      n.tail = ( next_node == G.tail(edges[n.idx]) );
klao@225
   814
    }
klao@225
   815
    else {
klao@225
   816
      n.tail = true;
klao@225
   817
    }
klao@225
   818
klao@225
   819
    return n;
klao@225
   820
  }
klao@225
   821
klao@225
   822
  template<typename Gr>
klao@369
   823
  bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
klao@225
   824
			  GraphNode &b) {
klao@225
   825
    if( G.tail(e) == a ) {
klao@225
   826
      b=G.head(e);
klao@225
   827
      return true;
klao@225
   828
    }
klao@225
   829
    if( G.head(e) == a ) {
klao@225
   830
      b=G.tail(e);
klao@225
   831
      return true;
klao@225
   832
    }
klao@225
   833
    return false;
klao@225
   834
  }
klao@225
   835
klao@225
   836
  template<typename Gr>
klao@369
   837
  bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
klao@225
   838
			     const GraphEdge &f) {
klao@225
   839
    if( edgeIncident(f, G.tail(e), _last) ) {
klao@225
   840
      _first = G.head(e);
klao@225
   841
      return true;
klao@225
   842
    }
klao@225
   843
    if( edgeIncident(f, G.head(e), _last) ) {
klao@225
   844
      _first = G.tail(e);
klao@225
   845
      return true;
klao@225
   846
    }
klao@225
   847
    return false;
klao@225
   848
  }
klao@225
   849
klao@225
   850
  template<typename Gr>
klao@369
   851
  bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
klao@225
   852
    if( G.valid(_first) ) {
klao@225
   853
	if( edgeIncident(e, _first, _first) ) {
klao@225
   854
	  edges.push_front(e);
klao@225
   855
	  return true;
klao@225
   856
	}
klao@225
   857
	else
klao@225
   858
	  return false;
klao@225
   859
    }
klao@225
   860
    else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
klao@225
   861
      edges.push_front(e);
klao@225
   862
      return true;
klao@225
   863
    }
klao@225
   864
    else
klao@225
   865
      return false;
klao@225
   866
  }
klao@225
   867
klao@225
   868
  template<typename Gr>
klao@369
   869
  bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
klao@225
   870
    if( G.valid(_last) ) {
klao@225
   871
	if( edgeIncident(e, _last, _last) ) {
klao@225
   872
	  edges.push_back(e);
klao@225
   873
	  return true;
klao@225
   874
	}
klao@225
   875
	else
klao@225
   876
	  return false;
klao@225
   877
    }
klao@225
   878
    else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
klao@225
   879
      edges.push_back(e);
klao@225
   880
      return true;
klao@225
   881
    }
klao@225
   882
    else
klao@225
   883
      return false;
klao@225
   884
  }
klao@225
   885
klao@225
   886
klao@225
   887
  template<typename Gr>
klao@369
   888
  bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
klao@225
   889
    if( G.valid(_first) ) {
klao@225
   890
      return _first == n;
klao@225
   891
    }
klao@225
   892
    else {
klao@225
   893
      if( length() > 0) {
klao@225
   894
	if( edgeIncident(edges[0], n, _last) ) {
klao@225
   895
	  _first = n;
klao@225
   896
	  return true;
klao@225
   897
	}
klao@225
   898
	else return false;
klao@225
   899
      }
klao@225
   900
      else {
klao@225
   901
	_first = _last = n;
klao@225
   902
	return true;
klao@225
   903
      }
klao@225
   904
    }
klao@225
   905
  }
klao@225
   906
klao@225
   907
  template<typename Gr>
klao@369
   908
  bool DynamicPath<Gr>::setTo(const GraphNode &n) {
klao@225
   909
    if( G.valid(_last) ) {
klao@225
   910
      return _last == n;
klao@225
   911
    }
klao@225
   912
    else {
klao@225
   913
      if( length() > 0) {
klao@225
   914
	if( edgeIncident(edges[0], n, _first) ) {
klao@225
   915
	  _last = n;
klao@225
   916
	  return true;
klao@225
   917
	}
klao@225
   918
	else return false;
klao@225
   919
      }
klao@225
   920
      else {
klao@225
   921
	_first = _last = n;
klao@225
   922
	return true;
klao@225
   923
      }
klao@225
   924
    }
klao@225
   925
  }
klao@225
   926
klao@225
   927
klao@225
   928
  template<typename Gr>
klao@369
   929
  typename DynamicPath<Gr>::NodeIt
klao@369
   930
  DynamicPath<Gr>::tail(const EdgeIt& e) const {
klao@225
   931
    NodeIt n;
klao@225
   932
klao@225
   933
    if( e.it == edges.end() ) {
klao@225
   934
      // FIXME: invalid-> invalid
klao@225
   935
      n.idx = length() + 1;
klao@225
   936
      n.tail = true;
klao@225
   937
      return n;
klao@225
   938
    }
klao@225
   939
klao@225
   940
    n.idx = e.it-edges.begin();
klao@225
   941
    n.tail = e.forw;
klao@226
   942
    return n;
klao@225
   943
  }
klao@225
   944
klao@225
   945
  template<typename Gr>
klao@369
   946
  typename DynamicPath<Gr>::NodeIt
klao@369
   947
  DynamicPath<Gr>::head(const EdgeIt& e) const {
klao@225
   948
    if( e.it == edges.end()-1 ) {
klao@225
   949
      return _last;
klao@225
   950
    }
klao@225
   951
klao@225
   952
    EdgeIt next_edge = e;
klao@225
   953
    next(next_edge);
klao@225
   954
    return tail(next_edge);
klao@225
   955
  }
klao@225
   956
      
klao@225
   957
  template<typename Gr>
klao@369
   958
  typename DynamicPath<Gr>::GraphEdge
klao@369
   959
  DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
klao@225
   960
    if( e.it != edges.end() ) {
klao@225
   961
      return *e.it;
klao@225
   962
    }
klao@225
   963
    else {
klao@225
   964
      return INVALID;
klao@225
   965
    }
klao@225
   966
  }
klao@225
   967
  
klao@225
   968
  template<typename Gr>
klao@369
   969
  typename DynamicPath<Gr>::GraphNode
klao@369
   970
  DynamicPath<Gr>::graphNode(const NodeIt& n) const {
klao@225
   971
    if( n.idx < length() ) {
klao@225
   972
      return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
klao@225
   973
    }
klao@225
   974
    else if( n.idx == length() ) {
klao@225
   975
      return _last;
klao@225
   976
    }
klao@225
   977
    else {
klao@225
   978
      return INVALID;
klao@225
   979
    }
klao@225
   980
  }
klao@225
   981
klao@225
   982
  template<typename Gr>
klao@369
   983
  typename DynamicPath<Gr>::EdgeIt&
klao@369
   984
  DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
klao@450
   985
    if( k>=length() ) {
klao@225
   986
      // FIXME: invalid EdgeIt
klao@225
   987
      e.it = edges.end();
klao@225
   988
      e.forw = true;
klao@225
   989
      return e;
klao@225
   990
    }
klao@225
   991
klao@225
   992
    e.it = edges.begin()+k;
klao@225
   993
    if(k==0) {
klao@225
   994
      e.forw = ( G.tail(*e.it) == _first );
klao@225
   995
    }
klao@225
   996
    else {
klao@225
   997
      e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
klao@225
   998
		 G.tail(*e.it) == G.head(edges[k-1]) );
klao@225
   999
    }
klao@225
  1000
    return e;
klao@225
  1001
  }
klao@225
  1002
    
klao@225
  1003
  template<typename Gr>
klao@369
  1004
  typename DynamicPath<Gr>::NodeIt&
klao@369
  1005
  DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
klao@450
  1006
    if( k>length() ) {
klao@225
  1007
      // FIXME: invalid NodeIt
klao@225
  1008
      n.idx = length()+1;
klao@225
  1009
      n.tail = true;
klao@225
  1010
      return n;
klao@225
  1011
    }
klao@225
  1012
    if( k==length() ) {
klao@225
  1013
      n.idx = length();
klao@225
  1014
      n.tail = true;
klao@225
  1015
      return n;
klao@225
  1016
    }
klao@225
  1017
    n = tail(nth<EdgeIt>(k));
klao@225
  1018
    return n;
klao@225
  1019
  }
klao@225
  1020
klao@226
  1021
  // Reszut konstruktorok:
klao@226
  1022
klao@226
  1023
klao@226
  1024
  template<typename Gr>
klao@369
  1025
  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
klao@369
  1026
			       const EdgeIt &b) :
klao@226
  1027
    G(P.G), edges(a.it, b.it)    // WARNING: if b.it < a.it this will blow up! 
klao@226
  1028
  {
klao@226
  1029
    if( G.valid(P._first) && a.it < P.edges.end() ) {
klao@226
  1030
      _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
klao@226
  1031
      if( b.it < P.edges.end() ) {
klao@226
  1032
	_last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
klao@226
  1033
      }
klao@226
  1034
      else {
klao@226
  1035
	_last = P._last;
klao@226
  1036
      }
klao@226
  1037
    }
klao@226
  1038
  }
klao@226
  1039
klao@226
  1040
  template<typename Gr>
klao@369
  1041
  DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
klao@369
  1042
			       const NodeIt &b) : G(P.G)
klao@226
  1043
  {
klao@226
  1044
    if( !P.valid(a) || !P.valid(b) )
klao@226
  1045
      return;
klao@226
  1046
klao@226
  1047
    int ai = a.idx, bi = b.idx;
klao@226
  1048
    if( bi<ai )
klao@450
  1049
      std::swap(ai,bi);
klao@226
  1050
    
klao@226
  1051
    edges.resize(bi-ai);
klao@226
  1052
    copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
klao@226
  1053
klao@226
  1054
    _first = P.graphNode(a);
klao@226
  1055
    _last = P.graphNode(b);
klao@226
  1056
  }
klao@226
  1057
alpar@434
  1058
  ///@}
klao@225
  1059
klao@225
  1060
} // namespace hugo
klao@225
  1061
klao@225
  1062
#endif // HUGO_PATH_H