COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 2084:59769591eb60, checked in by Balazs Dezso, 13 years ago

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

SwapBpUGraphAdaptor

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

File size: 19.3 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///\ingroup paths
21///\file
22///\brief Classes for representing paths in graphs.
23///
24///\todo Iterators have obsolete style
25
26#ifndef LEMON_PATH_H
27#define LEMON_PATH_H
28
29#include <deque>
30#include <vector>
31#include <algorithm>
32
33#include <lemon/bits/invalid.h>
34
35namespace lemon {
36
37  /// \addtogroup paths
38  /// @{
39
40
41  //! \brief A structure for representing directed paths in a graph.
42  //!
43  //! A structure for representing directed path in a graph.
44  //! \param Graph The graph type in which the path is.
45  //! \param DM DebugMode, defaults to DefaultDebugMode.
46  //!
47  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
48  //! and \c EdgeIt with the same usage. These types converts to the \c Node
49  //! and \c Edge of the original graph.
50  //!
51  //! \todo Thoroughfully check all the range and consistency tests.
52  template<typename Graph>
53  class DirPath {
54  public:
55    /// Edge type of the underlying graph.
56    typedef typename Graph::Edge GraphEdge;
57    /// Node type of the underlying graph.
58    typedef typename Graph::Node GraphNode;
59    class NodeIt;
60    class EdgeIt;
61
62  protected:
63    const Graph *gr;
64    typedef std::vector<GraphEdge> Container;
65    Container edges;
66
67  public:
68
69    /// \param _G The graph in which the path is.
70    ///
71    DirPath(const Graph &_G) : gr(&_G) {}
72
73    /// \brief Subpath constructor.
74    ///
75    /// Subpath defined by two nodes.
76    /// \warning It is an error if the two edges are not in order!
77    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
78      gr = P.gr;
79      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
80    }
81
82    /// \brief Subpath constructor.
83    ///
84    /// Subpath defined by two edges. Contains edges in [a,b)
85    /// \warning It is an error if the two edges are not in order!
86    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
87      gr = P.gr;
88      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
89    }
90
91    /// Length of the path.
92    int length() const { return edges.size(); }
93    /// Returns whether the path is empty.
94    bool empty() const { return edges.empty(); }
95
96    /// Resets the path to an empty path.
97    void clear() { edges.clear(); }
98
99    /// \brief Starting point of the path.
100    ///
101    /// Starting point of the path.
102    /// Returns INVALID if the path is empty.
103    GraphNode source() const {
104      return empty() ? INVALID : gr->source(edges[0]);
105    }
106    /// \brief End point of the path.
107    ///
108    /// End point of the path.
109    /// Returns INVALID if the path is empty.
110    GraphNode target() const {
111      return empty() ? INVALID : gr->target(edges[length()-1]);
112    }
113
114    /// \brief Initializes node or edge iterator to point to the first
115    /// node or edge.
116    ///
117    /// \sa nth
118    template<typename It>
119    It& first(It &i) const { return i=It(*this); }
120
121    /// \brief Initializes node iterator to point to the node of a given index.
122    NodeIt& nth(NodeIt &i, int n) const {
123      return i=NodeIt(*this, n);
124    }
125
126    /// \brief Initializes edge iterator to point to the edge of a given index.
127    EdgeIt& nth(EdgeIt &i, int n) const {
128      return i=EdgeIt(*this, n);
129    }
130
131    /// \brief Returns node iterator pointing to the target node of the
132    /// given edge iterator.
133    NodeIt target(const EdgeIt& e) const {
134      return NodeIt(*this, e.idx+1);
135    }
136
137    /// \brief Returns node iterator pointing to the source node of the
138    /// given edge iterator.
139    NodeIt source(const EdgeIt& e) const {
140      return NodeIt(*this, e.idx);
141    }
142
143
144    /* Iterator classes */
145
146    /**
147     * \brief Iterator class to iterate on the edges of the paths
148     *
149     * This class is used to iterate on the edges of the paths
150     *
151     * Of course it converts to Graph::Edge
152     *
153     */
154    class EdgeIt {
155      friend class DirPath;
156
157      int idx;
158      const DirPath *p;
159    public:
160      /// Default constructor
161      EdgeIt() {}
162      /// Invalid constructor
163      EdgeIt(Invalid) : idx(-1), p(0) {}
164      /// Constructor with starting point
165      EdgeIt(const DirPath &_p, int _idx = 0) :
166        idx(_idx), p(&_p) { validate(); }
167
168      ///Validity check
169      bool valid() const { return idx!=-1; }
170
171      ///Conversion to Graph::Edge
172      operator GraphEdge () const {
173        return valid() ? p->edges[idx] : INVALID;
174      }
175
176      /// Next edge
177      EdgeIt& operator++() { ++idx; validate(); return *this; }
178
179      /// Comparison operator
180      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
181      /// Comparison operator
182      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
183      /// Comparison operator
184      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
185
186    private:
187      void validate() { if(idx >= p->length() ) idx=-1; }
188    };
189
190    /**
191     * \brief Iterator class to iterate on the nodes of the paths
192     *
193     * This class is used to iterate on the nodes of the paths
194     *
195     * Of course it converts to Graph::Node
196     *
197     */
198    class NodeIt {
199      friend class DirPath;
200
201      int idx;
202      const DirPath *p;
203    public:
204      /// Default constructor
205      NodeIt() {}
206      /// Invalid constructor
207      NodeIt(Invalid) : idx(-1), p(0) {}
208      /// Constructor with starting point
209      NodeIt(const DirPath &_p, int _idx = 0) :
210        idx(_idx), p(&_p) { validate(); }
211
212      ///Validity check
213      bool valid() const { return idx!=-1; }
214
215      ///Conversion to Graph::Node
216      operator GraphNode () const {
217        if(idx >= p->length())
218          return p->target();
219        else if(idx >= 0)
220          return p->gr->source(p->edges[idx]);
221        else
222          return INVALID;
223      }
224      /// Next node
225      NodeIt& operator++() { ++idx; validate(); return *this; }
226
227      /// Comparison operator
228      bool operator==(const NodeIt& e) const { return idx==e.idx; }
229      /// Comparison operator
230      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
231      /// Comparison operator
232      bool operator<(const NodeIt& e) const { return idx<e.idx; }
233
234    private:
235      void validate() { if(idx > p->length() ) idx=-1; }
236    };
237
238    friend class Builder;
239
240    /**
241     * \brief Class to build paths
242     *
243     * This class is used to fill a path with edges.
244     *
245     * You can push new edges to the front and to the back of the path in
246     * arbitrary order then you should commit these changes to the graph.
247     *
248     * Fundamentally, for most "Paths" (classes fulfilling the
249     * PathConcept) while the builder is active (after the first modifying
250     * operation and until the commit()) the original Path is in a
251     * "transitional" state (operations on it have undefined result). But
252     * in the case of DirPath the original path remains unchanged until the
253     * commit. However we don't recomend that you use this feature.
254     */
255    class Builder {
256      DirPath &P;
257      Container front, back;
258
259    public:
260      ///\param _p the path you want to fill in.
261      ///
262      Builder(DirPath &_p) : P(_p) {}
263
264      /// Sets the starting node of the path.
265
266      /// Sets the starting node of the path. Edge added to the path
267      /// afterwards have to be incident to this node.
268      /// It should be called if and only if
269      /// the path is empty and before any call to
270      /// \ref pushFront() or \ref pushBack()
271      void setStartNode(const GraphNode &) {}
272
273      ///Push a new edge to the front of the path
274
275      ///Push a new edge to the front of the path.
276      ///\sa setStartNode
277      void pushFront(const GraphEdge& e) {
278        front.push_back(e);
279      }
280
281      ///Push a new edge to the back of the path
282
283      ///Push a new edge to the back of the path.
284      ///\sa setStartNode
285      void pushBack(const GraphEdge& e) {
286        back.push_back(e);
287      }
288
289      ///Commit the changes to the path.
290      void commit() {
291        if( !front.empty() || !back.empty() ) {
292          Container tmp;
293          tmp.reserve(front.size()+back.size()+P.length());
294          tmp.insert(tmp.end(), front.rbegin(), front.rend());
295          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
296          tmp.insert(tmp.end(), back.begin(), back.end());
297          P.edges.swap(tmp);
298          front.clear();
299          back.clear();
300        }
301      }
302
303      ///Reserve storage for the builder in advance.
304
305      ///If you know a reasonable upper bound of the number of the edges
306      ///to add to the front, using this function you can speed up the building.
307
308      void reserveFront(size_t r) {front.reserve(r);}
309
310      ///Reserve storage for the builder in advance.
311
312      ///If you know a reasonable upper bound of the number of the edges
313      ///to add to the back, using this function you can speed up the building.
314
315      void reserveBack(size_t r) {back.reserve(r);}
316
317    private:
318      bool empty() {
319        return front.empty() && back.empty() && P.empty();
320      }
321
322      GraphNode source() const {
323        if( ! front.empty() )
324          return P.gr->source(front[front.size()-1]);
325        else if( ! P.empty() )
326          return P.gr->source(P.edges[0]);
327        else if( ! back.empty() )
328          return P.gr->source(back[0]);
329        else
330          return INVALID;
331      }
332      GraphNode target() const {
333        if( ! back.empty() )
334          return P.gr->target(back[back.size()-1]);
335        else if( ! P.empty() )
336          return P.gr->target(P.edges[P.length()-1]);
337        else if( ! front.empty() )
338          return P.gr->target(front[0]);
339        else
340          return INVALID;
341      }
342
343    };
344
345  };
346
347
348
349
350
351
352
353
354
355
356  /**********************************************************************/
357
358
359  //! \brief A structure for representing undirected path in a graph.
360  //!
361  //! A structure for representing undirected path in a graph. Ie. this is
362  //! a path in a \e directed graph but the edges should not be directed
363  //! forward.
364  //!
365  //! \param Graph The graph type in which the path is.
366  //! \param DM DebugMode, defaults to DefaultDebugMode.
367  //!
368  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
369  //! and \c EdgeIt with the same usage. These types converts to the \c Node
370  //! and \c Edge of the original graph.
371  //!
372  //! \todo Thoroughfully check all the range and consistency tests.
373  /// \todo May we need just path for undirected graph instead of this.
374  template<typename Graph>
375  class UPath {
376  public:
377    /// Edge type of the underlying graph.
378    typedef typename Graph::Edge GraphEdge;
379     /// Node type of the underlying graph.
380   typedef typename Graph::Node GraphNode;
381    class NodeIt;
382    class EdgeIt;
383
384  protected:
385    const Graph *gr;
386    typedef std::vector<GraphEdge> Container;
387    Container edges;
388
389  public:
390
391    /// \param _G The graph in which the path is.
392    ///
393    UPath(const Graph &_G) : gr(&_G) {}
394
395    /// \brief Subpath constructor.
396    ///
397    /// Subpath defined by two nodes.
398    /// \warning It is an error if the two edges are not in order!
399    UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
400      gr = P.gr;
401      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
402    }
403
404    /// \brief Subpath constructor.
405    ///
406    /// Subpath defined by two edges. Contains edges in [a,b)
407    /// \warning It is an error if the two edges are not in order!
408    UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
409      gr = P.gr;
410      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
411    }
412
413    /// Length of the path.
414    size_t length() const { return edges.size(); }
415    /// Returns whether the path is empty.
416    bool empty() const { return edges.empty(); }
417
418    /// Resets the path to an empty path.
419    void clear() { edges.clear(); }
420
421    /// \brief Starting point of the path.
422    ///
423    /// Starting point of the path.
424    /// Returns INVALID if the path is empty.
425    GraphNode source() const {
426      return empty() ? INVALID : gr->source(edges[0]);
427    }
428    /// \brief End point of the path.
429    ///
430    /// End point of the path.
431    /// Returns INVALID if the path is empty.
432    GraphNode target() const {
433      return empty() ? INVALID : gr->target(edges[length()-1]);
434    }
435
436    /// \brief Initializes node or edge iterator to point to the first
437    /// node or edge.
438    ///
439    /// \sa nth
440    template<typename It>
441    It& first(It &i) const { return i=It(*this); }
442
443    /// \brief Initializes node iterator to point to the node of a given index.
444    NodeIt& nth(NodeIt &i, int n) const {
445      return i=NodeIt(*this, n);
446    }
447
448    /// \brief Initializes edge iterator to point to the edge of a given index.
449    EdgeIt& nth(EdgeIt &i, int n) const {
450      return i=EdgeIt(*this, n);
451    }
452
453    /// Checks validity of a node or edge iterator.
454    template<typename It>
455    static
456    bool valid(const It &i) { return i.valid(); }
457
458    /// Steps the given node or edge iterator.
459    template<typename It>
460    static
461    It& next(It &e) {
462      return ++e;
463    }
464
465    /// \brief Returns node iterator pointing to the target node of the
466    /// given edge iterator.
467    NodeIt target(const EdgeIt& e) const {
468      return NodeIt(*this, e.idx+1);
469    }
470
471    /// \brief Returns node iterator pointing to the source node of the
472    /// given edge iterator.
473    NodeIt source(const EdgeIt& e) const {
474      return NodeIt(*this, e.idx);
475    }
476
477
478
479    /**
480     * \brief Iterator class to iterate on the edges of the paths
481     *
482     * This class is used to iterate on the edges of the paths
483     *
484     * Of course it converts to Graph::Edge
485     *
486     * \todo Its interface differs from the standard edge iterator.
487     * Yes, it shouldn't.
488     */
489    class EdgeIt {
490      friend class UPath;
491
492      int idx;
493      const UPath *p;
494    public:
495      /// Default constructor
496      EdgeIt() {}
497      /// Invalid constructor
498      EdgeIt(Invalid) : idx(-1), p(0) {}
499      /// Constructor with starting point
500      EdgeIt(const UPath &_p, int _idx = 0) :
501        idx(_idx), p(&_p) { validate(); }
502
503      ///Validity check
504      bool valid() const { return idx!=-1; }
505
506      ///Conversion to Graph::Edge
507      operator GraphEdge () const {
508        return valid() ? p->edges[idx] : INVALID;
509      }
510      /// Next edge
511     EdgeIt& operator++() { ++idx; validate(); return *this; }
512
513      /// Comparison operator
514      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
515      /// Comparison operator
516      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
517      /// Comparison operator
518      bool operator<(const EdgeIt& e) const { return idx<e.idx; }
519
520    private:
521      // FIXME: comparison between signed and unsigned...
522      // Jo ez igy? Vagy esetleg legyen a length() int?
523      void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
524    };
525
526    /**
527     * \brief Iterator class to iterate on the nodes of the paths
528     *
529     * This class is used to iterate on the nodes of the paths
530     *
531     * Of course it converts to Graph::Node
532     *
533     * \todo Its interface differs from the standard node iterator.
534     * Yes, it shouldn't.
535     */
536    class NodeIt {
537      friend class UPath;
538
539      int idx;
540      const UPath *p;
541    public:
542      /// Default constructor
543      NodeIt() {}
544      /// Invalid constructor
545      NodeIt(Invalid) : idx(-1), p(0) {}
546      /// Constructor with starting point
547      NodeIt(const UPath &_p, int _idx = 0) :
548        idx(_idx), p(&_p) { validate(); }
549
550      ///Validity check
551      bool valid() const { return idx!=-1; }
552
553      ///Conversion to Graph::Node
554      operator const GraphNode& () const {
555        if(idx >= p->length())
556          return p->target();
557        else if(idx >= 0)
558          return p->gr->source(p->edges[idx]);
559        else
560          return INVALID;
561      }
562      /// Next node
563      NodeIt& operator++() { ++idx; validate(); return *this; }
564
565      /// Comparison operator
566      bool operator==(const NodeIt& e) const { return idx==e.idx; }
567      /// Comparison operator
568      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
569       /// Comparison operator
570     bool operator<(const NodeIt& e) const { return idx<e.idx; }
571
572    private:
573      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
574    };
575
576    friend class Builder;
577
578    /**
579     * \brief Class to build paths
580     *
581     * This class is used to fill a path with edges.
582     *
583     * You can push new edges to the front and to the back of the path in
584     * arbitrary order then you should commit these changes to the graph.
585     *
586     * Fundamentally, for most "Paths" (classes fulfilling the
587     * PathConcept) while the builder is active (after the first modifying
588     * operation and until the commit()) the original Path is in a
589     * "transitional" state (operations ot it have undefined result). But
590     * in the case of UPath the original path is unchanged until the
591     * commit. However we don't recomend that you use this feature.
592     */
593    class Builder {
594      UPath &P;
595      Container front, back;
596
597    public:
598      ///\param _p the path you want to fill in.
599      ///
600      Builder(UPath &_p) : P(_p) {}
601
602      /// Sets the starting node of the path.
603
604      /// Sets the starting node of the path. Edge added to the path
605      /// afterwards have to be incident to this node.
606      /// It should be called if and only if
607      /// the path is empty and before any call to
608      /// \ref pushFront() or \ref pushBack()
609      void setStartNode(const GraphNode &) {}
610
611      ///Push a new edge to the front of the path
612
613      ///Push a new edge to the front of the path.
614      ///\sa setStartNode
615      void pushFront(const GraphEdge& e) {
616        front.push_back(e);
617      }
618
619      ///Push a new edge to the back of the path
620
621      ///Push a new edge to the back of the path.
622      ///\sa setStartNode
623      void pushBack(const GraphEdge& e) {
624        back.push_back(e);
625      }
626
627      ///Commit the changes to the path.
628      void commit() {
629        if( !(front.empty() && back.empty()) ) {
630          Container tmp;
631          tmp.reserve(front.size()+back.size()+P.length());
632          tmp.insert(tmp.end(), front.rbegin(), front.rend());
633          tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
634          tmp.insert(tmp.end(), back.begin(), back.end());
635          P.edges.swap(tmp);
636          front.clear();
637          back.clear();
638        }
639      }
640
641
642      ///Reserve storage for the builder in advance.
643
644      ///If you know a reasonable upper bound of the number of the edges
645      ///to add to the front, using this function you can speed up the building.
646
647      void reserveFront(size_t r) {front.reserve(r);}
648
649      ///Reserve storage for the builder in advance.
650
651      ///If you know a reasonable upper bound of the number of the edges
652      ///to add to the back, using this function you can speed up the building.
653
654      void reserveBack(size_t r) {back.reserve(r);}
655
656    private:
657      bool empty() {
658        return front.empty() && back.empty() && P.empty();
659      }
660
661      GraphNode source() const {
662        if( ! front.empty() )
663          return P.gr->source(front[front.size()-1]);
664        else if( ! P.empty() )
665          return P.gr->source(P.edges[0]);
666        else if( ! back.empty() )
667          return P.gr->source(back[0]);
668        else
669          return INVALID;
670      }
671      GraphNode target() const {
672        if( ! back.empty() )
673          return P.gr->target(back[back.size()-1]);
674        else if( ! P.empty() )
675          return P.gr->target(P.edges[P.length()-1]);
676        else if( ! front.empty() )
677          return P.gr->target(front[0]);
678        else
679          return INVALID;
680      }
681
682    };
683
684  };
685
686
687  ///@}
688
689} // namespace lemon
690
691#endif // LEMON_PATH_H
Note: See TracBrowser for help on using the repository browser.