COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 1842:8abf74160dc4

Last change on this file since 1842:8abf74160dc4 was 1730:fffa6456548a, checked in by Balazs Dezso, 14 years ago

Minor changes and bugfixes

File size: 19.8 KB
RevLine 
[906]1/* -*- C++ -*-
[1435]2 * 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.
[1730]386  /// \todo May we need just path for undirected graph instead of this.
[831]387  template<typename Graph>
[819]388  class UndirPath {
389  public:
390    /// Edge type of the underlying graph.
391    typedef typename Graph::Edge GraphEdge;
392     /// Node type of the underlying graph.
393   typedef typename Graph::Node GraphNode;
394    class NodeIt;
395    class EdgeIt;
396
397  protected:
398    const Graph *gr;
399    typedef std::vector<GraphEdge> Container;
400    Container edges;
401
402  public:
403
404    /// \param _G The graph in which the path is.
405    ///
406    UndirPath(const Graph &_G) : gr(&_G) {}
407
408    /// \brief Subpath constructor.
409    ///
410    /// Subpath defined by two nodes.
411    /// \warning It is an error if the two edges are not in order!
412    UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
413      gr = P.gr;
414      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
415    }
416
417    /// \brief Subpath constructor.
418    ///
419    /// Subpath defined by two edges. Contains edges in [a,b)
420    /// \warning It is an error if the two edges are not in order!
421    UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
422      gr = P.gr;
423      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
424    }
425
426    /// Length of the path.
427    size_t length() const { return edges.size(); }
428    /// Returns whether the path is empty.
429    bool empty() const { return edges.empty(); }
430
431    /// Resets the path to an empty path.
432    void clear() { edges.clear(); }
433
434    /// \brief Starting point of the path.
435    ///
436    /// Starting point of the path.
437    /// Returns INVALID if the path is empty.
[986]438    GraphNode source() const {
439      return empty() ? INVALID : gr->source(edges[0]);
[819]440    }
441    /// \brief End point of the path.
442    ///
443    /// End point of the path.
444    /// Returns INVALID if the path is empty.
[986]445    GraphNode target() const {
446      return empty() ? INVALID : gr->target(edges[length()-1]);
[819]447    }
448
449    /// \brief Initializes node or edge iterator to point to the first
450    /// node or edge.
451    ///
452    /// \sa nth
453    template<typename It>
454    It& first(It &i) const { return i=It(*this); }
455
456    /// \brief Initializes node iterator to point to the node of a given index.
457    NodeIt& nth(NodeIt &i, int n) const {
458      return i=NodeIt(*this, n);
459    }
460
461    /// \brief Initializes edge iterator to point to the edge of a given index.
462    EdgeIt& nth(EdgeIt &i, int n) const {
463      return i=EdgeIt(*this, n);
464    }
465
466    /// Checks validity of a node or edge iterator.
467    template<typename It>
468    static
469    bool valid(const It &i) { return i.valid(); }
470
471    /// Steps the given node or edge iterator.
472    template<typename It>
473    static
474    It& next(It &e) {
475      return ++e;
476    }
477
[986]478    /// \brief Returns node iterator pointing to the target node of the
[819]479    /// given edge iterator.
[986]480    NodeIt target(const EdgeIt& e) const {
[819]481      return NodeIt(*this, e.idx+1);
482    }
483
[986]484    /// \brief Returns node iterator pointing to the source node of the
[819]485    /// given edge iterator.
[986]486    NodeIt source(const EdgeIt& e) const {
[819]487      return NodeIt(*this, e.idx);
488    }
489
490
491
492    /**
493     * \brief Iterator class to iterate on the edges of the paths
[837]494     *
[819]495     * This class is used to iterate on the edges of the paths
496     *
497     * Of course it converts to Graph::Edge
[837]498     *
[819]499     * \todo Its interface differs from the standard edge iterator.
500     * Yes, it shouldn't.
501     */
502    class EdgeIt {
503      friend class UndirPath;
504
505      int idx;
506      const UndirPath *p;
507    public:
508      /// Default constructor
509      EdgeIt() {}
510      /// Invalid constructor
511      EdgeIt(Invalid) : idx(-1), p(0) {}
512      /// Constructor with starting point
513      EdgeIt(const UndirPath &_p, int _idx = 0) :
514        idx(_idx), p(&_p) { validate(); }
515
516      ///Validity check
517      bool valid() const { return idx!=-1; }
518
519      ///Conversion to Graph::Edge
520      operator GraphEdge () const {
521        return valid() ? p->edges[idx] : INVALID;
522      }
523      /// Next edge
524     EdgeIt& operator++() { ++idx; validate(); return *this; }
525
526      /// Comparison operator
527      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
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
533    private:
534      // FIXME: comparison between signed and unsigned...
535      // Jo ez igy? Vagy esetleg legyen a length() int?
536      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
537    };
538
539    /**
540     * \brief Iterator class to iterate on the nodes of the paths
[837]541     *
[819]542     * This class is used to iterate on the nodes of the paths
543     *
544     * Of course it converts to Graph::Node
[837]545     *
[819]546     * \todo Its interface differs from the standard node iterator.
547     * Yes, it shouldn't.
548     */
549    class NodeIt {
550      friend class UndirPath;
551
552      int idx;
553      const UndirPath *p;
554    public:
555      /// Default constructor
556      NodeIt() {}
557      /// Invalid constructor
558      NodeIt(Invalid) : idx(-1), p(0) {}
559      /// Constructor with starting point
560      NodeIt(const UndirPath &_p, int _idx = 0) :
561        idx(_idx), p(&_p) { validate(); }
562
563      ///Validity check
564      bool valid() const { return idx!=-1; }
565
566      ///Conversion to Graph::Node
567      operator const GraphNode& () const {
568        if(idx >= p->length())
[986]569          return p->target();
[819]570        else if(idx >= 0)
[986]571          return p->gr->source(p->edges[idx]);
[819]572        else
573          return INVALID;
574      }
575      /// Next node
576      NodeIt& operator++() { ++idx; validate(); return *this; }
577
578      /// Comparison operator
579      bool operator==(const NodeIt& e) const { return idx==e.idx; }
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
585    private:
586      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
587    };
588
[837]589    friend class Builder;
[819]590
591    /**
592     * \brief Class to build paths
[837]593     *
[819]594     * This class is used to fill a path with edges.
595     *
596     * You can push new edges to the front and to the back of the path in
597     * arbitrary order then you should commit these changes to the graph.
598     *
599     * Fundamentally, for most "Paths" (classes fulfilling the
600     * PathConcept) while the builder is active (after the first modifying
601     * operation and until the commit()) the original Path is in a
602     * "transitional" state (operations ot it have undefined result). But
603     * in the case of UndirPath the original path is unchanged until the
604     * commit. However we don't recomend that you use this feature.
605     */
606    class Builder {
607      UndirPath &P;
608      Container front, back;
609
610    public:
[1228]611      ///\param _p the path you want to fill in.
[819]612      ///
[1228]613      Builder(UndirPath &_p) : P(_p) {}
[819]614
615      /// Sets the starting node of the path.
[837]616
[819]617      /// Sets the starting node of the path. Edge added to the path
618      /// afterwards have to be incident to this node.
[900]619      /// It should be called if and only if
620      /// the path is empty and before any call to
[819]621      /// \ref pushFront() or \ref pushBack()
622      void setStartNode(const GraphNode &) {}
623
624      ///Push a new edge to the front of the path
625
626      ///Push a new edge to the front of the path.
627      ///\sa setStartNode
628      void pushFront(const GraphEdge& e) {
629        front.push_back(e);
630      }
631
632      ///Push a new edge to the back of the path
633
634      ///Push a new edge to the back of the path.
635      ///\sa setStartNode
636      void pushBack(const GraphEdge& e) {
637        back.push_back(e);
638      }
639
640      ///Commit the changes to the path.
641      void commit() {
642        if( !(front.empty() && back.empty()) ) {
643          Container tmp;
644          tmp.reserve(front.size()+back.size()+P.length());
645          tmp.insert(tmp.end(), front.rbegin(), front.rend());
646          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
647          tmp.insert(tmp.end(), back.begin(), back.end());
648          P.edges.swap(tmp);
649          front.clear();
650          back.clear();
651        }
652      }
653
654
655      ///Reserve storage for the builder in advance.
656
[837]657      ///If you know a reasonable upper bound of the number of the edges
658      ///to add to the front, using this function you can speed up the building.
[819]659
[837]660      void reserveFront(size_t r) {front.reserve(r);}
661
662      ///Reserve storage for the builder in advance.
663
664      ///If you know a reasonable upper bound of the number of the edges
665      ///to add to the back, using this function you can speed up the building.
666
667      void reserveBack(size_t r) {back.reserve(r);}
[831]668
[819]669    private:
670      bool empty() {
671        return front.empty() && back.empty() && P.empty();
672      }
673
[986]674      GraphNode source() const {
[819]675        if( ! front.empty() )
[986]676          return P.gr->source(front[front.size()-1]);
[819]677        else if( ! P.empty() )
[986]678          return P.gr->source(P.edges[0]);
[819]679        else if( ! back.empty() )
[986]680          return P.gr->source(back[0]);
[819]681        else
682          return INVALID;
683      }
[986]684      GraphNode target() const {
[819]685        if( ! back.empty() )
[986]686          return P.gr->target(back[back.size()-1]);
[819]687        else if( ! P.empty() )
[986]688          return P.gr->target(P.edges[P.length()-1]);
[819]689        else if( ! front.empty() )
[986]690          return P.gr->target(front[0]);
[819]691        else
692          return INVALID;
693      }
694
695    };
696
697  };
698
699
700  ///@}
701
[921]702} // namespace lemon
[819]703
[921]704#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.