COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

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