COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 1865:dcefd1d1377f

Last change on this file since 1865:dcefd1d1377f was 1730:fffa6456548a, checked in by Balazs Dezso, 14 years ago

Minor changes and bugfixes

File size: 19.8 KB
Line 
1/* -*- C++ -*-
2 * lemon/path.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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    int 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      void validate() { if(idx >= p->length() ) idx=-1; }
201    };
202
203    /**
204     * \brief Iterator class to iterate on the nodes of the paths
205     *
206     * This class is used to iterate on the nodes of the paths
207     *
208     * Of course it converts to Graph::Node
209     *
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())
231          return p->target();
232        else if(idx >= 0)
233          return p->gr->source(p->edges[idx]);
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:
248      void validate() { if(idx > p->length() ) idx=-1; }
249    };
250
251    friend class Builder;
252
253    /**
254     * \brief Class to build paths
255     *
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:
273      ///\param _p the path you want to fill in.
274      ///
275      Builder(DirPath &_p) : P(_p) {}
276
277      /// Sets the starting node of the path.
278
279      /// Sets the starting node of the path. Edge added to the path
280      /// afterwards have to be incident to this node.
281      /// It should be called if and only if
282      /// the path is empty and before any call to
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() {
304        if( !front.empty() || !back.empty() ) {
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
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.
320
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);}
329
330    private:
331      bool empty() {
332        return front.empty() && back.empty() && P.empty();
333      }
334
335      GraphNode source() const {
336        if( ! front.empty() )
337          return P.gr->source(front[front.size()-1]);
338        else if( ! P.empty() )
339          return P.gr->source(P.edges[0]);
340        else if( ! back.empty() )
341          return P.gr->source(back[0]);
342        else
343          return INVALID;
344      }
345      GraphNode target() const {
346        if( ! back.empty() )
347          return P.gr->target(back[back.size()-1]);
348        else if( ! P.empty() )
349          return P.gr->target(P.edges[P.length()-1]);
350        else if( ! front.empty() )
351          return P.gr->target(front[0]);
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.
380  //!
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.
386  /// \todo May we need just path for undirected graph instead of this.
387  template<typename Graph>
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.
438    GraphNode source() const {
439      return empty() ? INVALID : gr->source(edges[0]);
440    }
441    /// \brief End point of the path.
442    ///
443    /// End point of the path.
444    /// Returns INVALID if the path is empty.
445    GraphNode target() const {
446      return empty() ? INVALID : gr->target(edges[length()-1]);
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
478    /// \brief Returns node iterator pointing to the target node of the
479    /// given edge iterator.
480    NodeIt target(const EdgeIt& e) const {
481      return NodeIt(*this, e.idx+1);
482    }
483
484    /// \brief Returns node iterator pointing to the source node of the
485    /// given edge iterator.
486    NodeIt source(const EdgeIt& e) const {
487      return NodeIt(*this, e.idx);
488    }
489
490
491
492    /**
493     * \brief Iterator class to iterate on the edges of the paths
494     *
495     * This class is used to iterate on the edges of the paths
496     *
497     * Of course it converts to Graph::Edge
498     *
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
541     *
542     * This class is used to iterate on the nodes of the paths
543     *
544     * Of course it converts to Graph::Node
545     *
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())
569          return p->target();
570        else if(idx >= 0)
571          return p->gr->source(p->edges[idx]);
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
589    friend class Builder;
590
591    /**
592     * \brief Class to build paths
593     *
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:
611      ///\param _p the path you want to fill in.
612      ///
613      Builder(UndirPath &_p) : P(_p) {}
614
615      /// Sets the starting node of the path.
616
617      /// Sets the starting node of the path. Edge added to the path
618      /// afterwards have to be incident to this node.
619      /// It should be called if and only if
620      /// the path is empty and before any call to
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
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.
659
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);}
668
669    private:
670      bool empty() {
671        return front.empty() && back.empty() && P.empty();
672      }
673
674      GraphNode source() const {
675        if( ! front.empty() )
676          return P.gr->source(front[front.size()-1]);
677        else if( ! P.empty() )
678          return P.gr->source(P.edges[0]);
679        else if( ! back.empty() )
680          return P.gr->source(back[0]);
681        else
682          return INVALID;
683      }
684      GraphNode target() const {
685        if( ! back.empty() )
686          return P.gr->target(back[back.size()-1]);
687        else if( ! P.empty() )
688          return P.gr->target(P.edges[P.length()-1]);
689        else if( ! front.empty() )
690          return P.gr->target(front[0]);
691        else
692          return INVALID;
693      }
694
695    };
696
697  };
698
699
700  ///@}
701
702} // namespace lemon
703
704#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.