COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/path.h @ 933:1b7c88fbb950

Last change on this file since 933:1b7c88fbb950 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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::skeleton::Path
30
31*/
32
33///\ingroup paths
34///\file
35///\brief Classes for representing paths in graphs.
36
37#ifndef LEMON_PATH_H
38#define LEMON_PATH_H
39
40#include <deque>
41#include <vector>
42#include <algorithm>
43
44#include <lemon/invalid.h>
45
46namespace lemon {
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.
57  //!
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.
63  template<typename Graph>
64  class DirPath {
65  public:
66    /// Edge type of the underlying graph.
67    typedef typename Graph::Edge GraphEdge;
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.
114    GraphNode tail() const {
115      return empty() ? INVALID : gr->tail(edges[0]);
116    }
117    /// \brief End point of the path.
118    ///
119    /// End point of the path.
120    /// Returns INVALID if the path is empty.
121    GraphNode head() const {
122      return empty() ? INVALID : gr->head(edges[length()-1]);
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
142    /// \brief Returns node iterator pointing to the head node of the
143    /// given edge iterator.
144    NodeIt head(const EdgeIt& e) const {
145      return NodeIt(*this, e.idx+1);
146    }
147
148    /// \brief Returns node iterator pointing to the tail node of the
149    /// given edge iterator.
150    NodeIt tail(const EdgeIt& e) const {
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
159     *
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
164     *
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
206     *
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
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->head();
234        else if(idx >= 0)
235          return p->gr->tail(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     * \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.
281
282      /// Sets the starting node of the path. Edge added to the path
283      /// afterwards have to be incident to this node.
284      /// It should be called if and only if
285      /// the path is empty and before any call to
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() {
307        if( !front.empty() || !back.empty() ) {
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
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.
323
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);}
332
333    private:
334      bool empty() {
335        return front.empty() && back.empty() && P.empty();
336      }
337
338      GraphNode tail() const {
339        if( ! front.empty() )
340          return P.gr->tail(front[front.size()-1]);
341        else if( ! P.empty() )
342          return P.gr->tail(P.edges[0]);
343        else if( ! back.empty() )
344          return P.gr->tail(back[0]);
345        else
346          return INVALID;
347      }
348      GraphNode head() const {
349        if( ! back.empty() )
350          return P.gr->head(back[back.size()-1]);
351        else if( ! P.empty() )
352          return P.gr->head(P.edges[P.length()-1]);
353        else if( ! front.empty() )
354          return P.gr->head(front[0]);
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.
383  //!
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.
389  template<typename Graph>
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.
440    GraphNode tail() const {
441      return empty() ? INVALID : gr->tail(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 head() const {
448      return empty() ? INVALID : gr->head(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 head node of the
481    /// given edge iterator.
482    NodeIt head(const EdgeIt& e) const {
483      return NodeIt(*this, e.idx+1);
484    }
485
486    /// \brief Returns node iterator pointing to the tail node of the
487    /// given edge iterator.
488    NodeIt tail(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     * \ingroup paths
498     * This class is used to iterate on the edges of the paths
499     *
500     * Of course it converts to Graph::Edge
501     *
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
544     *
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
549     *
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())
573          return p->head();
574        else if(idx >= 0)
575          return p->gr->tail(p->edges[idx]);
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
593    friend class Builder;
594
595    /**
596     * \brief Class to build paths
597     *
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.
621
622      /// Sets the starting node of the path. Edge added to the path
623      /// afterwards have to be incident to this node.
624      /// It should be called if and only if
625      /// the path is empty and before any call to
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
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.
664
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);}
673
674    private:
675      bool empty() {
676        return front.empty() && back.empty() && P.empty();
677      }
678
679      GraphNode tail() const {
680        if( ! front.empty() )
681          return P.gr->tail(front[front.size()-1]);
682        else if( ! P.empty() )
683          return P.gr->tail(P.edges[0]);
684        else if( ! back.empty() )
685          return P.gr->tail(back[0]);
686        else
687          return INVALID;
688      }
689      GraphNode head() const {
690        if( ! back.empty() )
691          return P.gr->head(back[back.size()-1]);
692        else if( ! P.empty() )
693          return P.gr->head(P.edges[P.length()-1]);
694        else if( ! front.empty() )
695          return P.gr->head(front[0]);
696        else
697          return INVALID;
698      }
699
700    };
701
702  };
703
704
705  ///@}
706
707} // namespace lemon
708
709#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.