COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/path.h @ 1389:58b298e50c20

Last change on this file since 1389:58b298e50c20 was 1359:1581f961cfaa, checked in by Alpar Juttner, 19 years ago

Correct the english name of EGRES.

File size: 19.7 KB
RevLine 
[906]1/* -*- C++ -*-
[921]2 * src/lemon/path.h - Part of LEMON, a generic C++ optimization library
[906]3 *
[1164]4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
[819]16
17/**
18@defgroup paths Path Structures
19@ingroup datas
[921]20\brief Path structures implemented in LEMON.
[819]21
[921]22LEMON provides flexible data structures
[819]23to work with paths.
24
25All of them have the same interface, especially they can be built or extended
26using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
27algorithm to store its result in any kind of path structure.
28
[959]29\sa lemon::concept::Path
[819]30
31*/
32
33///\ingroup paths
34///\file
35///\brief Classes for representing paths in graphs.
[1151]36///
37///\todo Iterators have obsolete style
[819]38
[921]39#ifndef LEMON_PATH_H
40#define LEMON_PATH_H
[819]41
42#include <deque>
43#include <vector>
44#include <algorithm>
45
[921]46#include <lemon/invalid.h>
[819]47
[921]48namespace lemon {
[819]49
50  /// \addtogroup paths
51  /// @{
52
53
54  //! \brief A structure for representing directed paths in a graph.
55  //!
56  //! A structure for representing directed path in a graph.
57  //! \param Graph The graph type in which the path is.
58  //! \param DM DebugMode, defaults to DefaultDebugMode.
[837]59  //!
[819]60  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
61  //! and \c EdgeIt with the same usage. These types converts to the \c Node
62  //! and \c Edge of the original graph.
63  //!
64  //! \todo Thoroughfully check all the range and consistency tests.
[831]65  template<typename Graph>
[819]66  class DirPath {
67  public:
68    /// Edge type of the underlying graph.
[837]69    typedef typename Graph::Edge GraphEdge;
[819]70    /// Node type of the underlying graph.
71    typedef typename Graph::Node GraphNode;
72    class NodeIt;
73    class EdgeIt;
74
75  protected:
76    const Graph *gr;
77    typedef std::vector<GraphEdge> Container;
78    Container edges;
79
80  public:
81
82    /// \param _G The graph in which the path is.
83    ///
84    DirPath(const Graph &_G) : gr(&_G) {}
85
86    /// \brief Subpath constructor.
87    ///
88    /// Subpath defined by two nodes.
89    /// \warning It is an error if the two edges are not in order!
90    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
91      gr = P.gr;
92      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
93    }
94
95    /// \brief Subpath constructor.
96    ///
97    /// Subpath defined by two edges. Contains edges in [a,b)
98    /// \warning It is an error if the two edges are not in order!
99    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
100      gr = P.gr;
101      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
102    }
103
104    /// Length of the path.
[1282]105    int length() const { return edges.size(); }
[819]106    /// Returns whether the path is empty.
107    bool empty() const { return edges.empty(); }
108
109    /// Resets the path to an empty path.
110    void clear() { edges.clear(); }
111
112    /// \brief Starting point of the path.
113    ///
114    /// Starting point of the path.
115    /// Returns INVALID if the path is empty.
[986]116    GraphNode source() const {
117      return empty() ? INVALID : gr->source(edges[0]);
[819]118    }
119    /// \brief End point of the path.
120    ///
121    /// End point of the path.
122    /// Returns INVALID if the path is empty.
[986]123    GraphNode target() const {
124      return empty() ? INVALID : gr->target(edges[length()-1]);
[819]125    }
126
127    /// \brief Initializes node or edge iterator to point to the first
128    /// node or edge.
129    ///
130    /// \sa nth
131    template<typename It>
132    It& first(It &i) const { return i=It(*this); }
133
134    /// \brief Initializes node iterator to point to the node of a given index.
135    NodeIt& nth(NodeIt &i, int n) const {
136      return i=NodeIt(*this, n);
137    }
138
139    /// \brief Initializes edge iterator to point to the edge of a given index.
140    EdgeIt& nth(EdgeIt &i, int n) const {
141      return i=EdgeIt(*this, n);
142    }
143
[986]144    /// \brief Returns node iterator pointing to the target node of the
[819]145    /// given edge iterator.
[986]146    NodeIt target(const EdgeIt& e) const {
[819]147      return NodeIt(*this, e.idx+1);
148    }
149
[986]150    /// \brief Returns node iterator pointing to the source node of the
[819]151    /// given edge iterator.
[986]152    NodeIt source(const EdgeIt& e) const {
[819]153      return NodeIt(*this, e.idx);
154    }
155
156
157    /* Iterator classes */
158
159    /**
160     * \brief Iterator class to iterate on the edges of the paths
[837]161     *
[819]162     * This class is used to iterate on the edges of the paths
163     *
164     * Of course it converts to Graph::Edge
[837]165     *
[819]166     */
167    class EdgeIt {
168      friend class DirPath;
169
170      int idx;
171      const DirPath *p;
172    public:
173      /// Default constructor
174      EdgeIt() {}
175      /// Invalid constructor
176      EdgeIt(Invalid) : idx(-1), p(0) {}
177      /// Constructor with starting point
178      EdgeIt(const DirPath &_p, int _idx = 0) :
179        idx(_idx), p(&_p) { validate(); }
180
181      ///Validity check
182      bool valid() const { return idx!=-1; }
183
184      ///Conversion to Graph::Edge
185      operator GraphEdge () const {
186        return valid() ? p->edges[idx] : INVALID;
187      }
188
189      /// Next edge
190      EdgeIt& operator++() { ++idx; validate(); return *this; }
191
192      /// Comparison operator
193      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
194      /// Comparison operator
195      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
196      /// Comparison operator
197      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
198
199    private:
[1282]200      void validate() { if(idx >= p->length() ) idx=-1; }
[819]201    };
202
203    /**
204     * \brief Iterator class to iterate on the nodes of the paths
[837]205     *
[819]206     * This class is used to iterate on the nodes of the paths
207     *
208     * Of course it converts to Graph::Node
[837]209     *
[819]210     */
211    class NodeIt {
212      friend class DirPath;
213
214      int idx;
215      const DirPath *p;
216    public:
217      /// Default constructor
218      NodeIt() {}
219      /// Invalid constructor
220      NodeIt(Invalid) : idx(-1), p(0) {}
221      /// Constructor with starting point
222      NodeIt(const DirPath &_p, int _idx = 0) :
223        idx(_idx), p(&_p) { validate(); }
224
225      ///Validity check
226      bool valid() const { return idx!=-1; }
227
228      ///Conversion to Graph::Node
229      operator const GraphNode& () const {
230        if(idx >= p->length())
[986]231          return p->target();
[819]232        else if(idx >= 0)
[986]233          return p->gr->source(p->edges[idx]);
[819]234        else
235          return INVALID;
236      }
237      /// Next node
238      NodeIt& operator++() { ++idx; validate(); return *this; }
239
240      /// Comparison operator
241      bool operator==(const NodeIt& e) const { return idx==e.idx; }
242      /// Comparison operator
243      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
244      /// Comparison operator
245      bool operator<(const NodeIt& e) const { return idx<e.idx; }
246
247    private:
[1282]248      void validate() { if(idx > p->length() ) idx=-1; }
[819]249    };
250
[837]251    friend class Builder;
[819]252
253    /**
254     * \brief Class to build paths
[837]255     *
[819]256     * This class is used to fill a path with edges.
257     *
258     * You can push new edges to the front and to the back of the path in
259     * arbitrary order then you should commit these changes to the graph.
260     *
261     * Fundamentally, for most "Paths" (classes fulfilling the
262     * PathConcept) while the builder is active (after the first modifying
263     * operation and until the commit()) the original Path is in a
264     * "transitional" state (operations on it have undefined result). But
265     * in the case of DirPath the original path remains unchanged until the
266     * commit. However we don't recomend that you use this feature.
267     */
268    class Builder {
269      DirPath &P;
270      Container front, back;
271
272    public:
[1228]273      ///\param _p the path you want to fill in.
[819]274      ///
[1228]275      Builder(DirPath &_p) : P(_p) {}
[819]276
277      /// Sets the starting node of the path.
[837]278
[819]279      /// Sets the starting node of the path. Edge added to the path
280      /// afterwards have to be incident to this node.
[900]281      /// It should be called if and only if
282      /// the path is empty and before any call to
[819]283      /// \ref pushFront() or \ref pushBack()
284      void setStartNode(const GraphNode &) {}
285
286      ///Push a new edge to the front of the path
287
288      ///Push a new edge to the front of the path.
289      ///\sa setStartNode
290      void pushFront(const GraphEdge& e) {
291        front.push_back(e);
292      }
293
294      ///Push a new edge to the back of the path
295
296      ///Push a new edge to the back of the path.
297      ///\sa setStartNode
298      void pushBack(const GraphEdge& e) {
299        back.push_back(e);
300      }
301
302      ///Commit the changes to the path.
303      void commit() {
[837]304        if( !front.empty() || !back.empty() ) {
[819]305          Container tmp;
306          tmp.reserve(front.size()+back.size()+P.length());
307          tmp.insert(tmp.end(), front.rbegin(), front.rend());
308          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
309          tmp.insert(tmp.end(), back.begin(), back.end());
310          P.edges.swap(tmp);
311          front.clear();
312          back.clear();
313        }
314      }
315
316      ///Reserve storage for the builder in advance.
317
[837]318      ///If you know a reasonable upper bound of the number of the edges
319      ///to add to the front, using this function you can speed up the building.
[819]320
[837]321      void reserveFront(size_t r) {front.reserve(r);}
322
323      ///Reserve storage for the builder in advance.
324
325      ///If you know a reasonable upper bound of the number of the edges
326      ///to add to the back, using this function you can speed up the building.
327
328      void reserveBack(size_t r) {back.reserve(r);}
[831]329
[819]330    private:
331      bool empty() {
332        return front.empty() && back.empty() && P.empty();
333      }
334
[986]335      GraphNode source() const {
[819]336        if( ! front.empty() )
[986]337          return P.gr->source(front[front.size()-1]);
[819]338        else if( ! P.empty() )
[986]339          return P.gr->source(P.edges[0]);
[819]340        else if( ! back.empty() )
[986]341          return P.gr->source(back[0]);
[819]342        else
343          return INVALID;
344      }
[986]345      GraphNode target() const {
[819]346        if( ! back.empty() )
[986]347          return P.gr->target(back[back.size()-1]);
[819]348        else if( ! P.empty() )
[986]349          return P.gr->target(P.edges[P.length()-1]);
[819]350        else if( ! front.empty() )
[986]351          return P.gr->target(front[0]);
[819]352        else
353          return INVALID;
354      }
355
356    };
357
358  };
359
360
361
362
363
364
365
366
367
368
369  /**********************************************************************/
370
371
372  //! \brief A structure for representing undirected path in a graph.
373  //!
374  //! A structure for representing undirected path in a graph. Ie. this is
375  //! a path in a \e directed graph but the edges should not be directed
376  //! forward.
377  //!
378  //! \param Graph The graph type in which the path is.
379  //! \param DM DebugMode, defaults to DefaultDebugMode.
[837]380  //!
[819]381  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
382  //! and \c EdgeIt with the same usage. These types converts to the \c Node
383  //! and \c Edge of the original graph.
384  //!
385  //! \todo Thoroughfully check all the range and consistency tests.
[831]386  template<typename Graph>
[819]387  class UndirPath {
388  public:
389    /// Edge type of the underlying graph.
390    typedef typename Graph::Edge GraphEdge;
391     /// Node type of the underlying graph.
392   typedef typename Graph::Node GraphNode;
393    class NodeIt;
394    class EdgeIt;
395
396  protected:
397    const Graph *gr;
398    typedef std::vector<GraphEdge> Container;
399    Container edges;
400
401  public:
402
403    /// \param _G The graph in which the path is.
404    ///
405    UndirPath(const Graph &_G) : gr(&_G) {}
406
407    /// \brief Subpath constructor.
408    ///
409    /// Subpath defined by two nodes.
410    /// \warning It is an error if the two edges are not in order!
411    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
412      gr = P.gr;
413      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
414    }
415
416    /// \brief Subpath constructor.
417    ///
418    /// Subpath defined by two edges. Contains edges in [a,b)
419    /// \warning It is an error if the two edges are not in order!
420    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
421      gr = P.gr;
422      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
423    }
424
425    /// Length of the path.
426    size_t length() const { return edges.size(); }
427    /// Returns whether the path is empty.
428    bool empty() const { return edges.empty(); }
429
430    /// Resets the path to an empty path.
431    void clear() { edges.clear(); }
432
433    /// \brief Starting point of the path.
434    ///
435    /// Starting point of the path.
436    /// Returns INVALID if the path is empty.
[986]437    GraphNode source() const {
438      return empty() ? INVALID : gr->source(edges[0]);
[819]439    }
440    /// \brief End point of the path.
441    ///
442    /// End point of the path.
443    /// Returns INVALID if the path is empty.
[986]444    GraphNode target() const {
445      return empty() ? INVALID : gr->target(edges[length()-1]);
[819]446    }
447
448    /// \brief Initializes node or edge iterator to point to the first
449    /// node or edge.
450    ///
451    /// \sa nth
452    template<typename It>
453    It& first(It &i) const { return i=It(*this); }
454
455    /// \brief Initializes node iterator to point to the node of a given index.
456    NodeIt& nth(NodeIt &i, int n) const {
457      return i=NodeIt(*this, n);
458    }
459
460    /// \brief Initializes edge iterator to point to the edge of a given index.
461    EdgeIt& nth(EdgeIt &i, int n) const {
462      return i=EdgeIt(*this, n);
463    }
464
465    /// Checks validity of a node or edge iterator.
466    template<typename It>
467    static
468    bool valid(const It &i) { return i.valid(); }
469
470    /// Steps the given node or edge iterator.
471    template<typename It>
472    static
473    It& next(It &e) {
474      return ++e;
475    }
476
[986]477    /// \brief Returns node iterator pointing to the target node of the
[819]478    /// given edge iterator.
[986]479    NodeIt target(const EdgeIt& e) const {
[819]480      return NodeIt(*this, e.idx+1);
481    }
482
[986]483    /// \brief Returns node iterator pointing to the source node of the
[819]484    /// given edge iterator.
[986]485    NodeIt source(const EdgeIt& e) const {
[819]486      return NodeIt(*this, e.idx);
487    }
488
489
490
491    /**
492     * \brief Iterator class to iterate on the edges of the paths
[837]493     *
[819]494     * This class is used to iterate on the edges of the paths
495     *
496     * Of course it converts to Graph::Edge
[837]497     *
[819]498     * \todo Its interface differs from the standard edge iterator.
499     * Yes, it shouldn't.
500     */
501    class EdgeIt {
502      friend class UndirPath;
503
504      int idx;
505      const UndirPath *p;
506    public:
507      /// Default constructor
508      EdgeIt() {}
509      /// Invalid constructor
510      EdgeIt(Invalid) : idx(-1), p(0) {}
511      /// Constructor with starting point
512      EdgeIt(const UndirPath &_p, int _idx = 0) :
513        idx(_idx), p(&_p) { validate(); }
514
515      ///Validity check
516      bool valid() const { return idx!=-1; }
517
518      ///Conversion to Graph::Edge
519      operator GraphEdge () const {
520        return valid() ? p->edges[idx] : INVALID;
521      }
522      /// Next edge
523     EdgeIt& operator++() { ++idx; validate(); return *this; }
524
525      /// Comparison operator
526      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
527      /// Comparison operator
528      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
529      /// Comparison operator
530      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
531
532    private:
533      // FIXME: comparison between signed and unsigned...
534      // Jo ez igy? Vagy esetleg legyen a length() int?
535      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
536    };
537
538    /**
539     * \brief Iterator class to iterate on the nodes of the paths
[837]540     *
[819]541     * This class is used to iterate on the nodes of the paths
542     *
543     * Of course it converts to Graph::Node
[837]544     *
[819]545     * \todo Its interface differs from the standard node iterator.
546     * Yes, it shouldn't.
547     */
548    class NodeIt {
549      friend class UndirPath;
550
551      int idx;
552      const UndirPath *p;
553    public:
554      /// Default constructor
555      NodeIt() {}
556      /// Invalid constructor
557      NodeIt(Invalid) : idx(-1), p(0) {}
558      /// Constructor with starting point
559      NodeIt(const UndirPath &_p, int _idx = 0) :
560        idx(_idx), p(&_p) { validate(); }
561
562      ///Validity check
563      bool valid() const { return idx!=-1; }
564
565      ///Conversion to Graph::Node
566      operator const GraphNode& () const {
567        if(idx >= p->length())
[986]568          return p->target();
[819]569        else if(idx >= 0)
[986]570          return p->gr->source(p->edges[idx]);
[819]571        else
572          return INVALID;
573      }
574      /// Next node
575      NodeIt& operator++() { ++idx; validate(); return *this; }
576
577      /// Comparison operator
578      bool operator==(const NodeIt& e) const { return idx==e.idx; }
579      /// Comparison operator
580      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
581       /// Comparison operator
582     bool operator<(const NodeIt& e) const { return idx<e.idx; }
583
584    private:
585      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
586    };
587
[837]588    friend class Builder;
[819]589
590    /**
591     * \brief Class to build paths
[837]592     *
[819]593     * This class is used to fill a path with edges.
594     *
595     * You can push new edges to the front and to the back of the path in
596     * arbitrary order then you should commit these changes to the graph.
597     *
598     * Fundamentally, for most "Paths" (classes fulfilling the
599     * PathConcept) while the builder is active (after the first modifying
600     * operation and until the commit()) the original Path is in a
601     * "transitional" state (operations ot it have undefined result). But
602     * in the case of UndirPath the original path is unchanged until the
603     * commit. However we don't recomend that you use this feature.
604     */
605    class Builder {
606      UndirPath &P;
607      Container front, back;
608
609    public:
[1228]610      ///\param _p the path you want to fill in.
[819]611      ///
[1228]612      Builder(UndirPath &_p) : P(_p) {}
[819]613
614      /// Sets the starting node of the path.
[837]615
[819]616      /// Sets the starting node of the path. Edge added to the path
617      /// afterwards have to be incident to this node.
[900]618      /// It should be called if and only if
619      /// the path is empty and before any call to
[819]620      /// \ref pushFront() or \ref pushBack()
621      void setStartNode(const GraphNode &) {}
622
623      ///Push a new edge to the front of the path
624
625      ///Push a new edge to the front of the path.
626      ///\sa setStartNode
627      void pushFront(const GraphEdge& e) {
628        front.push_back(e);
629      }
630
631      ///Push a new edge to the back of the path
632
633      ///Push a new edge to the back of the path.
634      ///\sa setStartNode
635      void pushBack(const GraphEdge& e) {
636        back.push_back(e);
637      }
638
639      ///Commit the changes to the path.
640      void commit() {
641        if( !(front.empty() && back.empty()) ) {
642          Container tmp;
643          tmp.reserve(front.size()+back.size()+P.length());
644          tmp.insert(tmp.end(), front.rbegin(), front.rend());
645          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
646          tmp.insert(tmp.end(), back.begin(), back.end());
647          P.edges.swap(tmp);
648          front.clear();
649          back.clear();
650        }
651      }
652
653
654      ///Reserve storage for the builder in advance.
655
[837]656      ///If you know a reasonable upper bound of the number of the edges
657      ///to add to the front, using this function you can speed up the building.
[819]658
[837]659      void reserveFront(size_t r) {front.reserve(r);}
660
661      ///Reserve storage for the builder in advance.
662
663      ///If you know a reasonable upper bound of the number of the edges
664      ///to add to the back, using this function you can speed up the building.
665
666      void reserveBack(size_t r) {back.reserve(r);}
[831]667
[819]668    private:
669      bool empty() {
670        return front.empty() && back.empty() && P.empty();
671      }
672
[986]673      GraphNode source() const {
[819]674        if( ! front.empty() )
[986]675          return P.gr->source(front[front.size()-1]);
[819]676        else if( ! P.empty() )
[986]677          return P.gr->source(P.edges[0]);
[819]678        else if( ! back.empty() )
[986]679          return P.gr->source(back[0]);
[819]680        else
681          return INVALID;
682      }
[986]683      GraphNode target() const {
[819]684        if( ! back.empty() )
[986]685          return P.gr->target(back[back.size()-1]);
[819]686        else if( ! P.empty() )
[986]687          return P.gr->target(P.edges[P.length()-1]);
[819]688        else if( ! front.empty() )
[986]689          return P.gr->target(front[0]);
[819]690        else
691          return INVALID;
692      }
693
694    };
695
696  };
697
698
699  ///@}
700
[921]701} // namespace lemon
[819]702
[921]703#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.