COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 2011:1a1bffa615b8

Last change on this file since 2011:1a1bffa615b8 was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

File size: 19.7 KB
Line 
1/* -*- C++ -*-
2 *
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
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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 */
18
19/**
20@defgroup paths Path Structures
21@ingroup datas
22\brief Path structures implemented in LEMON.
23
24LEMON provides flexible data structures
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
31\sa lemon::concept::Path
32
33*/
34
35///\ingroup paths
36///\file
37///\brief Classes for representing paths in graphs.
38///
39///\todo Iterators have obsolete style
40
41#ifndef LEMON_PATH_H
42#define LEMON_PATH_H
43
44#include <deque>
45#include <vector>
46#include <algorithm>
47
48#include <lemon/bits/invalid.h>
49
50namespace lemon {
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.
61  //!
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.
67  template<typename Graph>
68  class DirPath {
69  public:
70    /// Edge type of the underlying graph.
71    typedef typename Graph::Edge GraphEdge;
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.
107    int length() const { return edges.size(); }
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.
118    GraphNode source() const {
119      return empty() ? INVALID : gr->source(edges[0]);
120    }
121    /// \brief End point of the path.
122    ///
123    /// End point of the path.
124    /// Returns INVALID if the path is empty.
125    GraphNode target() const {
126      return empty() ? INVALID : gr->target(edges[length()-1]);
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
146    /// \brief Returns node iterator pointing to the target node of the
147    /// given edge iterator.
148    NodeIt target(const EdgeIt& e) const {
149      return NodeIt(*this, e.idx+1);
150    }
151
152    /// \brief Returns node iterator pointing to the source node of the
153    /// given edge iterator.
154    NodeIt source(const EdgeIt& e) const {
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
163     *
164     * This class is used to iterate on the edges of the paths
165     *
166     * Of course it converts to Graph::Edge
167     *
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:
202      void validate() { if(idx >= p->length() ) idx=-1; }
203    };
204
205    /**
206     * \brief Iterator class to iterate on the nodes of the paths
207     *
208     * This class is used to iterate on the nodes of the paths
209     *
210     * Of course it converts to Graph::Node
211     *
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())
233          return p->target();
234        else if(idx >= 0)
235          return p->gr->source(p->edges[idx]);
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(idx > p->length() ) idx=-1; }
251    };
252
253    friend class Builder;
254
255    /**
256     * \brief Class to build paths
257     *
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:
275      ///\param _p the path you want to fill in.
276      ///
277      Builder(DirPath &_p) : P(_p) {}
278
279      /// Sets the starting node of the path.
280
281      /// Sets the starting node of the path. Edge added to the path
282      /// afterwards have to be incident to this node.
283      /// It should be called if and only if
284      /// the path is empty and before any call to
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() {
306        if( !front.empty() || !back.empty() ) {
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
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.
322
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);}
331
332    private:
333      bool empty() {
334        return front.empty() && back.empty() && P.empty();
335      }
336
337      GraphNode source() const {
338        if( ! front.empty() )
339          return P.gr->source(front[front.size()-1]);
340        else if( ! P.empty() )
341          return P.gr->source(P.edges[0]);
342        else if( ! back.empty() )
343          return P.gr->source(back[0]);
344        else
345          return INVALID;
346      }
347      GraphNode target() const {
348        if( ! back.empty() )
349          return P.gr->target(back[back.size()-1]);
350        else if( ! P.empty() )
351          return P.gr->target(P.edges[P.length()-1]);
352        else if( ! front.empty() )
353          return P.gr->target(front[0]);
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.
382  //!
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.
388  /// \todo May we need just path for undirected graph instead of this.
389  template<typename Graph>
390  class UPath {
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    UPath(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    UPath(const UPath &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    UPath(const UPath &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.
440    GraphNode source() const {
441      return empty() ? INVALID : gr->source(edges[0]);
442    }
443    /// \brief End point of the path.
444    ///
445    /// End point of the path.
446    /// Returns INVALID if the path is empty.
447    GraphNode target() const {
448      return empty() ? INVALID : gr->target(edges[length()-1]);
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
480    /// \brief Returns node iterator pointing to the target node of the
481    /// given edge iterator.
482    NodeIt target(const EdgeIt& e) const {
483      return NodeIt(*this, e.idx+1);
484    }
485
486    /// \brief Returns node iterator pointing to the source node of the
487    /// given edge iterator.
488    NodeIt source(const EdgeIt& e) const {
489      return NodeIt(*this, e.idx);
490    }
491
492
493
494    /**
495     * \brief Iterator class to iterate on the edges of the paths
496     *
497     * This class is used to iterate on the edges of the paths
498     *
499     * Of course it converts to Graph::Edge
500     *
501     * \todo Its interface differs from the standard edge iterator.
502     * Yes, it shouldn't.
503     */
504    class EdgeIt {
505      friend class UPath;
506
507      int idx;
508      const UPath *p;
509    public:
510      /// Default constructor
511      EdgeIt() {}
512      /// Invalid constructor
513      EdgeIt(Invalid) : idx(-1), p(0) {}
514      /// Constructor with starting point
515      EdgeIt(const UPath &_p, int _idx = 0) :
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
543     *
544     * This class is used to iterate on the nodes of the paths
545     *
546     * Of course it converts to Graph::Node
547     *
548     * \todo Its interface differs from the standard node iterator.
549     * Yes, it shouldn't.
550     */
551    class NodeIt {
552      friend class UPath;
553
554      int idx;
555      const UPath *p;
556    public:
557      /// Default constructor
558      NodeIt() {}
559      /// Invalid constructor
560      NodeIt(Invalid) : idx(-1), p(0) {}
561      /// Constructor with starting point
562      NodeIt(const UPath &_p, int _idx = 0) :
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())
571          return p->target();
572        else if(idx >= 0)
573          return p->gr->source(p->edges[idx]);
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
591    friend class Builder;
592
593    /**
594     * \brief Class to build paths
595     *
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
605     * in the case of UPath the original path is unchanged until the
606     * commit. However we don't recomend that you use this feature.
607     */
608    class Builder {
609      UPath &P;
610      Container front, back;
611
612    public:
613      ///\param _p the path you want to fill in.
614      ///
615      Builder(UPath &_p) : P(_p) {}
616
617      /// Sets the starting node of the path.
618
619      /// Sets the starting node of the path. Edge added to the path
620      /// afterwards have to be incident to this node.
621      /// It should be called if and only if
622      /// the path is empty and before any call to
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
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.
661
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);}
670
671    private:
672      bool empty() {
673        return front.empty() && back.empty() && P.empty();
674      }
675
676      GraphNode source() const {
677        if( ! front.empty() )
678          return P.gr->source(front[front.size()-1]);
679        else if( ! P.empty() )
680          return P.gr->source(P.edges[0]);
681        else if( ! back.empty() )
682          return P.gr->source(back[0]);
683        else
684          return INVALID;
685      }
686      GraphNode target() const {
687        if( ! back.empty() )
688          return P.gr->target(back[back.size()-1]);
689        else if( ! P.empty() )
690          return P.gr->target(P.edges[P.length()-1]);
691        else if( ! front.empty() )
692          return P.gr->target(front[0]);
693        else
694          return INVALID;
695      }
696
697    };
698
699  };
700
701
702  ///@}
703
704} // namespace lemon
705
706#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.