COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/path.h @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 19.9 KB
RevLine 
[906]1/* -*- C++ -*-
[921]2 * src/lemon/path.h - Part of LEMON, a generic C++ optimization library
[906]3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
36
[921]37#ifndef LEMON_PATH_H
38#define LEMON_PATH_H
[819]39
40#include <deque>
41#include <vector>
42#include <algorithm>
43
[921]44#include <lemon/invalid.h>
[819]45
[921]46namespace lemon {
[819]47
48  /// \addtogroup paths
49  /// @{
50
51
52  //! \brief A structure for representing directed paths in a graph.
53  //!
54  //! A structure for representing directed path in a graph.
55  //! \param Graph The graph type in which the path is.
56  //! \param DM DebugMode, defaults to DefaultDebugMode.
[837]57  //!
[819]58  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
59  //! and \c EdgeIt with the same usage. These types converts to the \c Node
60  //! and \c Edge of the original graph.
61  //!
62  //! \todo Thoroughfully check all the range and consistency tests.
[831]63  template<typename Graph>
[819]64  class DirPath {
65  public:
66    /// Edge type of the underlying graph.
[837]67    typedef typename Graph::Edge GraphEdge;
[819]68    /// Node type of the underlying graph.
69    typedef typename Graph::Node GraphNode;
70    class NodeIt;
71    class EdgeIt;
72
73  protected:
74    const Graph *gr;
75    typedef std::vector<GraphEdge> Container;
76    Container edges;
77
78  public:
79
80    /// \param _G The graph in which the path is.
81    ///
82    DirPath(const Graph &_G) : gr(&_G) {}
83
84    /// \brief Subpath constructor.
85    ///
86    /// Subpath defined by two nodes.
87    /// \warning It is an error if the two edges are not in order!
88    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
89      gr = P.gr;
90      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
91    }
92
93    /// \brief Subpath constructor.
94    ///
95    /// Subpath defined by two edges. Contains edges in [a,b)
96    /// \warning It is an error if the two edges are not in order!
97    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
98      gr = P.gr;
99      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
100    }
101
102    /// Length of the path.
103    size_t length() const { return edges.size(); }
104    /// Returns whether the path is empty.
105    bool empty() const { return edges.empty(); }
106
107    /// Resets the path to an empty path.
108    void clear() { edges.clear(); }
109
110    /// \brief Starting point of the path.
111    ///
112    /// Starting point of the path.
113    /// Returns INVALID if the path is empty.
[986]114    GraphNode source() const {
115      return empty() ? INVALID : gr->source(edges[0]);
[819]116    }
117    /// \brief End point of the path.
118    ///
119    /// End point of the path.
120    /// Returns INVALID if the path is empty.
[986]121    GraphNode target() const {
122      return empty() ? INVALID : gr->target(edges[length()-1]);
[819]123    }
124
125    /// \brief Initializes node or edge iterator to point to the first
126    /// node or edge.
127    ///
128    /// \sa nth
129    template<typename It>
130    It& first(It &i) const { return i=It(*this); }
131
132    /// \brief Initializes node iterator to point to the node of a given index.
133    NodeIt& nth(NodeIt &i, int n) const {
134      return i=NodeIt(*this, n);
135    }
136
137    /// \brief Initializes edge iterator to point to the edge of a given index.
138    EdgeIt& nth(EdgeIt &i, int n) const {
139      return i=EdgeIt(*this, n);
140    }
141
[986]142    /// \brief Returns node iterator pointing to the target node of the
[819]143    /// given edge iterator.
[986]144    NodeIt target(const EdgeIt& e) const {
[819]145      return NodeIt(*this, e.idx+1);
146    }
147
[986]148    /// \brief Returns node iterator pointing to the source node of the
[819]149    /// given edge iterator.
[986]150    NodeIt source(const EdgeIt& e) const {
[819]151      return NodeIt(*this, e.idx);
152    }
153
154
155    /* Iterator classes */
156
157    /**
158     * \brief Iterator class to iterate on the edges of the paths
[837]159     *
[819]160     * \ingroup paths
161     * This class is used to iterate on the edges of the paths
162     *
163     * Of course it converts to Graph::Edge
[837]164     *
[819]165     */
166    class EdgeIt {
167      friend class DirPath;
168
169      int idx;
170      const DirPath *p;
171    public:
172      /// Default constructor
173      EdgeIt() {}
174      /// Invalid constructor
175      EdgeIt(Invalid) : idx(-1), p(0) {}
176      /// Constructor with starting point
177      EdgeIt(const DirPath &_p, int _idx = 0) :
178        idx(_idx), p(&_p) { validate(); }
179
180      ///Validity check
181      bool valid() const { return idx!=-1; }
182
183      ///Conversion to Graph::Edge
184      operator GraphEdge () const {
185        return valid() ? p->edges[idx] : INVALID;
186      }
187
188      /// Next edge
189      EdgeIt& operator++() { ++idx; validate(); return *this; }
190
191      /// Comparison operator
192      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
193      /// Comparison operator
194      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
195      /// Comparison operator
196      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
197
198    private:
199      // FIXME: comparison between signed and unsigned...
200      // Jo ez igy? Vagy esetleg legyen a length() int?
201      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
202    };
203
204    /**
205     * \brief Iterator class to iterate on the nodes of the paths
[837]206     *
[819]207     * \ingroup paths
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:
250      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
251    };
252
[837]253    friend class Builder;
[819]254
255    /**
256     * \brief Class to build paths
[837]257     *
[819]258     * \ingroup paths
259     * This class is used to fill a path with edges.
260     *
261     * You can push new edges to the front and to the back of the path in
262     * arbitrary order then you should commit these changes to the graph.
263     *
264     * Fundamentally, for most "Paths" (classes fulfilling the
265     * PathConcept) while the builder is active (after the first modifying
266     * operation and until the commit()) the original Path is in a
267     * "transitional" state (operations on it have undefined result). But
268     * in the case of DirPath the original path remains unchanged until the
269     * commit. However we don't recomend that you use this feature.
270     */
271    class Builder {
272      DirPath &P;
273      Container front, back;
274
275    public:
276      ///\param _P the path you want to fill in.
277      ///
278      Builder(DirPath &_P) : P(_P) {}
279
280      /// Sets the starting node of the path.
[837]281
[819]282      /// Sets the starting node of the path. Edge added to the path
283      /// afterwards have to be incident to this node.
[900]284      /// It should be called if and only if
285      /// the path is empty and before any call to
[819]286      /// \ref pushFront() or \ref pushBack()
287      void setStartNode(const GraphNode &) {}
288
289      ///Push a new edge to the front of the path
290
291      ///Push a new edge to the front of the path.
292      ///\sa setStartNode
293      void pushFront(const GraphEdge& e) {
294        front.push_back(e);
295      }
296
297      ///Push a new edge to the back of the path
298
299      ///Push a new edge to the back of the path.
300      ///\sa setStartNode
301      void pushBack(const GraphEdge& e) {
302        back.push_back(e);
303      }
304
305      ///Commit the changes to the path.
306      void commit() {
[837]307        if( !front.empty() || !back.empty() ) {
[819]308          Container tmp;
309          tmp.reserve(front.size()+back.size()+P.length());
310          tmp.insert(tmp.end(), front.rbegin(), front.rend());
311          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
312          tmp.insert(tmp.end(), back.begin(), back.end());
313          P.edges.swap(tmp);
314          front.clear();
315          back.clear();
316        }
317      }
318
319      ///Reserve storage for the builder in advance.
320
[837]321      ///If you know a reasonable upper bound of the number of the edges
322      ///to add to the front, using this function you can speed up the building.
[819]323
[837]324      void reserveFront(size_t r) {front.reserve(r);}
325
326      ///Reserve storage for the builder in advance.
327
328      ///If you know a reasonable upper bound of the number of the edges
329      ///to add to the back, using this function you can speed up the building.
330
331      void reserveBack(size_t r) {back.reserve(r);}
[831]332
[819]333    private:
334      bool empty() {
335        return front.empty() && back.empty() && P.empty();
336      }
337
[986]338      GraphNode source() const {
[819]339        if( ! front.empty() )
[986]340          return P.gr->source(front[front.size()-1]);
[819]341        else if( ! P.empty() )
[986]342          return P.gr->source(P.edges[0]);
[819]343        else if( ! back.empty() )
[986]344          return P.gr->source(back[0]);
[819]345        else
346          return INVALID;
347      }
[986]348      GraphNode target() const {
[819]349        if( ! back.empty() )
[986]350          return P.gr->target(back[back.size()-1]);
[819]351        else if( ! P.empty() )
[986]352          return P.gr->target(P.edges[P.length()-1]);
[819]353        else if( ! front.empty() )
[986]354          return P.gr->target(front[0]);
[819]355        else
356          return INVALID;
357      }
358
359    };
360
361  };
362
363
364
365
366
367
368
369
370
371
372  /**********************************************************************/
373
374
375  //! \brief A structure for representing undirected path in a graph.
376  //!
377  //! A structure for representing undirected path in a graph. Ie. this is
378  //! a path in a \e directed graph but the edges should not be directed
379  //! forward.
380  //!
381  //! \param Graph The graph type in which the path is.
382  //! \param DM DebugMode, defaults to DefaultDebugMode.
[837]383  //!
[819]384  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
385  //! and \c EdgeIt with the same usage. These types converts to the \c Node
386  //! and \c Edge of the original graph.
387  //!
388  //! \todo Thoroughfully check all the range and consistency tests.
[831]389  template<typename Graph>
[819]390  class UndirPath {
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    ///
408    UndirPath(const Graph &_G) : gr(&_G) {}
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!
414    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
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!
423    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
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     * \ingroup paths
498     * This class is used to iterate on the edges of the paths
499     *
500     * Of course it converts to Graph::Edge
[837]501     *
[819]502     * \todo Its interface differs from the standard edge iterator.
503     * Yes, it shouldn't.
504     */
505    class EdgeIt {
506      friend class UndirPath;
507
508      int idx;
509      const UndirPath *p;
510    public:
511      /// Default constructor
512      EdgeIt() {}
513      /// Invalid constructor
514      EdgeIt(Invalid) : idx(-1), p(0) {}
515      /// Constructor with starting point
516      EdgeIt(const UndirPath &_p, int _idx = 0) :
517        idx(_idx), p(&_p) { validate(); }
518
519      ///Validity check
520      bool valid() const { return idx!=-1; }
521
522      ///Conversion to Graph::Edge
523      operator GraphEdge () const {
524        return valid() ? p->edges[idx] : INVALID;
525      }
526      /// Next edge
527     EdgeIt& operator++() { ++idx; validate(); return *this; }
528
529      /// Comparison operator
530      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
531      /// Comparison operator
532      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
533      /// Comparison operator
534      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
535
536    private:
537      // FIXME: comparison between signed and unsigned...
538      // Jo ez igy? Vagy esetleg legyen a length() int?
539      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
540    };
541
542    /**
543     * \brief Iterator class to iterate on the nodes of the paths
[837]544     *
[819]545     * \ingroup paths
546     * This class is used to iterate on the nodes of the paths
547     *
548     * Of course it converts to Graph::Node
[837]549     *
[819]550     * \todo Its interface differs from the standard node iterator.
551     * Yes, it shouldn't.
552     */
553    class NodeIt {
554      friend class UndirPath;
555
556      int idx;
557      const UndirPath *p;
558    public:
559      /// Default constructor
560      NodeIt() {}
561      /// Invalid constructor
562      NodeIt(Invalid) : idx(-1), p(0) {}
563      /// Constructor with starting point
564      NodeIt(const UndirPath &_p, int _idx = 0) :
565        idx(_idx), p(&_p) { validate(); }
566
567      ///Validity check
568      bool valid() const { return idx!=-1; }
569
570      ///Conversion to Graph::Node
571      operator const GraphNode& () const {
572        if(idx >= p->length())
[986]573          return p->target();
[819]574        else if(idx >= 0)
[986]575          return p->gr->source(p->edges[idx]);
[819]576        else
577          return INVALID;
578      }
579      /// Next node
580      NodeIt& operator++() { ++idx; validate(); return *this; }
581
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       /// Comparison operator
587     bool operator<(const NodeIt& e) const { return idx<e.idx; }
588
589    private:
590      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
591    };
592
[837]593    friend class Builder;
[819]594
595    /**
596     * \brief Class to build paths
[837]597     *
[819]598     * \ingroup paths
599     * This class is used to fill a path with edges.
600     *
601     * You can push new edges to the front and to the back of the path in
602     * arbitrary order then you should commit these changes to the graph.
603     *
604     * Fundamentally, for most "Paths" (classes fulfilling the
605     * PathConcept) while the builder is active (after the first modifying
606     * operation and until the commit()) the original Path is in a
607     * "transitional" state (operations ot it have undefined result). But
608     * in the case of UndirPath the original path is unchanged until the
609     * commit. However we don't recomend that you use this feature.
610     */
611    class Builder {
612      UndirPath &P;
613      Container front, back;
614
615    public:
616      ///\param _P the path you want to fill in.
617      ///
618      Builder(UndirPath &_P) : P(_P) {}
619
620      /// Sets the starting node of the path.
[837]621
[819]622      /// Sets the starting node of the path. Edge added to the path
623      /// afterwards have to be incident to this node.
[900]624      /// It should be called if and only if
625      /// the path is empty and before any call to
[819]626      /// \ref pushFront() or \ref pushBack()
627      void setStartNode(const GraphNode &) {}
628
629      ///Push a new edge to the front of the path
630
631      ///Push a new edge to the front of the path.
632      ///\sa setStartNode
633      void pushFront(const GraphEdge& e) {
634        front.push_back(e);
635      }
636
637      ///Push a new edge to the back of the path
638
639      ///Push a new edge to the back of the path.
640      ///\sa setStartNode
641      void pushBack(const GraphEdge& e) {
642        back.push_back(e);
643      }
644
645      ///Commit the changes to the path.
646      void commit() {
647        if( !(front.empty() && back.empty()) ) {
648          Container tmp;
649          tmp.reserve(front.size()+back.size()+P.length());
650          tmp.insert(tmp.end(), front.rbegin(), front.rend());
651          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
652          tmp.insert(tmp.end(), back.begin(), back.end());
653          P.edges.swap(tmp);
654          front.clear();
655          back.clear();
656        }
657      }
658
659
660      ///Reserve storage for the builder in advance.
661
[837]662      ///If you know a reasonable upper bound of the number of the edges
663      ///to add to the front, using this function you can speed up the building.
[819]664
[837]665      void reserveFront(size_t r) {front.reserve(r);}
666
667      ///Reserve storage for the builder in advance.
668
669      ///If you know a reasonable upper bound of the number of the edges
670      ///to add to the back, using this function you can speed up the building.
671
672      void reserveBack(size_t r) {back.reserve(r);}
[831]673
[819]674    private:
675      bool empty() {
676        return front.empty() && back.empty() && P.empty();
677      }
678
[986]679      GraphNode source() const {
[819]680        if( ! front.empty() )
[986]681          return P.gr->source(front[front.size()-1]);
[819]682        else if( ! P.empty() )
[986]683          return P.gr->source(P.edges[0]);
[819]684        else if( ! back.empty() )
[986]685          return P.gr->source(back[0]);
[819]686        else
687          return INVALID;
688      }
[986]689      GraphNode target() const {
[819]690        if( ! back.empty() )
[986]691          return P.gr->target(back[back.size()-1]);
[819]692        else if( ! P.empty() )
[986]693          return P.gr->target(P.edges[P.length()-1]);
[819]694        else if( ! front.empty() )
[986]695          return P.gr->target(front[0]);
[819]696        else
697          return INVALID;
698      }
699
700    };
701
702  };
703
704
705  ///@}
706
[921]707} // namespace lemon
[819]708
[921]709#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.