src/work/klao/path.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 803 c3d832275e69
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

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