COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/path.h @ 1151:b217fc69f913

Last change on this file since 1151:b217fc69f913 was 1151:b217fc69f913, checked in by Alpar Juttner, 15 years ago

Several changes in the docs.

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