COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/path_utils.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 10.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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///\ingroup paths
20///\file
21///\brief Classes for representing paths in graphs.
22///
23
24#ifndef LEMON_PATH_UTILS_H
25#define LEMON_PATH_UTILS_H
26
27#include <lemon/concepts/path.h>
28#include <lemon/lemon_reader.h>
29#include <lemon/lemon_writer.h>
30
31namespace lemon {
32
33  namespace _path_bits {
34
35    template <typename Path, typename Enable = void>
36    struct RevTagIndicator {
37      static const bool value = false;
38    };
39
40    template <typename Graph>
41    struct RevTagIndicator<
42      Graph,
43      typename enable_if<typename Graph::RevTag, void>::type
44    > {
45      static const bool value = true;
46    };
47
48    template <typename Target, typename Source,
49              typename BuildEnable = void, typename RevEnable = void>
50    struct PathCopySelector {
51      static void copy(Target& target, const Source& source) {
52        target.clear();
53        for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
54          target.addBack(it);
55        }
56      }
57    };
58
59    template <typename Target, typename Source, typename BuildEnable>
60    struct PathCopySelector<
61      Target, Source, BuildEnable,
62      typename enable_if<typename Source::RevPathTag, void>::type> {
63      static void copy(Target& target, const Source& source) {
64        target.clear();
65        for (typename Source::RevEdgeIt it(source); it != INVALID; ++it) {
66          target.addFront(it);
67        }
68      }
69    };
70
71    template <typename Target, typename Source, typename RevEnable>
72    struct PathCopySelector<
73      Target, Source,
74      typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
75      static void copy(Target& target, const Source& source) {
76        target.clear();
77        target.build(source);
78      }
79    };
80
81    template <typename Target, typename Source>
82    struct PathCopySelector<
83      Target, Source,
84      typename enable_if<typename Target::BuildTag, void>::type,
85      typename enable_if<typename Source::RevPathTag, void>::type> {
86      static void copy(Target& target, const Source& source) {
87        target.clear();
88        target.buildRev(source);
89      }
90    };
91
92  }
93
94
95  /// \brief Make of copy of a path.
96  ///
97  ///  Make of copy of a path.
98  template <typename Target, typename Source>
99  void copyPath(Target& target, const Source& source) {
100    checkConcept<concepts::PathDumper<typename Source::Graph>, Source>();
101    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
102  }
103
104  /// \brief Checks the path's consistency.
105  ///
106  /// Checks that each edge's target is the next's source.
107  ///
108  template <typename Graph, typename Path>
109  bool checkPath(const Graph& graph, const Path& path) {
110    typename Path::EdgeIt it(path);
111    if (it == INVALID) return true;
112    typename Graph::Node node = graph.target(it);
113    ++it;
114    while (it != INVALID) {
115      if (graph.source(it) != node) return false;
116      node = graph.target(it);
117      ++it;
118    }
119    return true;
120  }
121
122  /// \brief Gives back the source of the path
123  ///
124  /// Gives back the source of the path.
125  template <typename Graph, typename Path>
126  typename Graph::Node pathSource(const Graph& graph, const Path& path) {
127    return graph.source(path.front());
128  }
129
130  /// \brief Gives back the target of the path
131  ///
132  /// Gives back the target of the path.
133  template <typename Graph, typename Path>
134  typename Graph::Node pathTarget(const Graph& graph, const Path& path) {
135    return graph.target(path.back());
136  }
137
138  /// \brief Class which helps to iterate the nodes of a path
139  ///
140  /// In a sense, the path can be treated as a list of edges. The
141  /// lemon path type stores just this list. As a consequence it
142  /// cannot enumerate the nodes in the path and the zero length paths
143  /// cannot store the node.
144  ///
145  /// This class implements the node iterator of a path structure. To
146  /// provide this feature, the underlying graph should be given to
147  /// the constructor of the iterator.
148  template <typename Path>
149  class PathNodeIt {
150  private:
151    const typename Path::Graph *_graph;
152    typename Path::EdgeIt _it;
153    typename Path::Graph::Node _nd;
154
155  public:
156
157    typedef typename Path::Graph Graph;
158    typedef typename Graph::Node Node;
159   
160    /// Default constructor
161    PathNodeIt() {}
162    /// Invalid constructor
163    PathNodeIt(Invalid)
164      : _graph(0), _it(INVALID), _nd(INVALID) {}
165    /// Constructor
166    PathNodeIt(const Graph& graph, const Path& path)
167      : _graph(&graph), _it(path) {
168      _nd = (_it != INVALID ? _graph->source(_it) : INVALID);
169    }
170    /// Constructor
171    PathNodeIt(const Graph& graph, const Path& path, const Node& src)
172      : _graph(&graph), _it(path), _nd(src) {}
173
174    ///Conversion to Graph::Node
175    operator Node() const {
176      return _nd;
177    }
178
179    /// Next node
180    PathNodeIt& operator++() {
181      if (_it == INVALID) _nd = INVALID;
182      else {
183        _nd = _graph->target(_it);
184        ++_it;
185      }
186      return *this;
187    }
188
189    /// Comparison operator
190    bool operator==(const PathNodeIt& n) const {
191      return _it == n._it && _nd == n._nd;
192    }
193    /// Comparison operator
194    bool operator!=(const PathNodeIt& n) const {
195      return _it != n._it || _nd != n._nd;
196    }
197    /// Comparison operator
198    bool operator<(const PathNodeIt& n) const {
199      return (_it < n._it && _nd != INVALID);
200    }
201   
202  };
203
204  /// \brief Item writer for paths
205  ///
206  /// This class can write paths into files. You can store paths in
207  /// distinict mapset or in attributes section.
208  ///
209  ///\code
210  /// GraphWriter<SmartGraph> gw(std::cout, g);
211  /// NodeMapWriter<SmartGraph> nmw(gw, g, gw);
212  ///
213  /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
214  /// for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
215  ///   pnm[n] = bfs.path(n);
216  /// }
217  /// nmw.writeNodeMap("pnm", pnm, PathWriter<Path<SmartGraph> >(gw));
218  ///
219  /// gw.run();
220  ///\endcode
221  ///
222  /// \warning Do not use this class to write node or edge map values
223  /// into usual nodesets or edgesets. You will not be able to read
224  /// back your paths. Rather use NodeMapWriter, EdgeSetWriter or
225  /// UEdgeSetWriter to dump paths from maps to lemon file.
226  template <typename Path>
227  class PathWriter {
228  private:
229
230    typedef typename Path::Edge Edge;
231    std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > edgeLabelWriter;
232
233  public:
234
235    typedef Path Value;
236
237    PathWriter(const PathWriter& pw) {
238      edgeLabelWriter.reset(pw.edgeLabelWriter->clone());
239    }
240
241    /// \brief Constructor
242    ///
243    /// The paramter shold be an edge label writer which could
244    /// be a GraphWriter or an EdgeSetWriter.
245    template <typename EdgeLabelWriter>
246    explicit PathWriter(const EdgeLabelWriter& _edgeLabelWriter) {
247      edgeLabelWriter.reset(new _writer_bits::
248        LabelWriter<Edge, EdgeLabelWriter>(_edgeLabelWriter));
249    }
250
251    /// \brief Writer function
252    ///
253    /// Writes the path to the current stream. The representation
254    /// is the edge labels beetween parentheses.
255    void write(std::ostream& os, const Value& value) const {
256      if (!edgeLabelWriter->isLabelWriter()) {
257        throw DataFormatError("Cannot find edgeset or label map");
258      }
259      os << '(' << ' ';
260      for (typename Path::EdgeIt e(value); e != INVALID; ++e) {
261        edgeLabelWriter->write(os, e);
262        os << ' ';
263      }
264      os << ')';
265    }
266   
267  };
268
269  namespace _path_bits {
270
271    template <typename _Graph>
272    class PathProxy {
273    public:
274      typedef False RevPathTag;
275
276      typedef _Graph Graph;
277      typedef typename Graph::Edge Edge;
278
279      PathProxy(const std::vector<Edge>& edges)
280        : _edges(edges) {}
281
282      int length() const {
283        return _edges.size();
284      }
285
286      bool empty() const {
287        return _edges.size() == 0;
288      }
289
290      class EdgeIt {
291      public:
292        EdgeIt() {}
293        EdgeIt(const PathProxy& path)
294          : _path(&path), _index(0) {}
295       
296        operator const Edge() const {
297          return _path->_edges[_index];
298        }
299
300        EdgeIt& operator++() {
301          ++_index;
302          return *this;
303        }
304
305        bool operator==(Invalid) const {
306          return int(_path->_edges.size()) == _index;
307        }
308        bool operator!=(Invalid) const {
309          return int(_path->_edges.size()) != _index;
310        }
311
312      private:
313        const PathProxy* _path;
314        int _index;
315      };
316     
317    private:
318      const std::vector<Edge>& _edges;
319     
320    };
321
322  }
323
324  /// \brief Item reader for paths
325  ///
326  /// This class can read paths from files. You can store paths in
327  /// distinict mapset or in attributes section.
328  ///
329  ///\code
330  /// GraphReader<SmartGraph> gr(std::cout, g);
331  /// NodeMapReader<SmartGraph> nmr(gr, g, gr);
332  ///
333  /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
334  /// nmr.readNodeMap("pnm", pnm, PathReader<Path<SmartGraph> >(gr));
335  ///
336  /// gr.run();
337  ///\endcode
338  ///
339  /// \warning Do not use this class to read node or edge map values
340  /// from nodesets or edgesets. The edges are not surely constructed
341  /// when the edge list should be read. Rather use NodeMapReader,
342  /// EdgeSetReader or UEdgeSetReader to read distinict map sets from file.
343  template <typename Path>
344  class PathReader {
345  private:
346
347    typedef typename Path::Edge Edge;
348    std::auto_ptr<_reader_bits::LabelReaderBase<Edge> > edgeLabelReader;
349
350  public:
351
352    typedef Path Value;
353
354    PathReader(const PathReader& pw) {
355      edgeLabelReader.reset(pw.edgeLabelReader->clone());
356    }
357
358    /// \brief Constructor
359    ///
360    /// The paramter shold be an edge label reader which could
361    /// be a GraphReader or an EdgeSetReader.
362    template <typename EdgeLabelReader>
363    explicit PathReader(const EdgeLabelReader& _edgeLabelReader) {
364      edgeLabelReader.reset(new _reader_bits::
365        LabelReader<Edge, EdgeLabelReader>(_edgeLabelReader));
366    }
367
368
369    /// \brief Reader function
370    ///
371    /// Reads the path from the current stream. The representation
372    /// is the edge labels beetween parentheses.
373    void read(std::istream& is, Value& value) const {
374      if (!edgeLabelReader->isLabelReader()) {
375        throw DataFormatError("Cannot find edgeset or label map");
376      }
377      char c;
378      if (!(is >> c) || c != '(')
379        throw DataFormatError("PathReader format error");
380      std::vector<typename Path::Edge> v;
381      while (is >> c && c != ')') {
382        is.putback(c);
383        Edge edge = edgeLabelReader->read(is);
384        v.push_back(edge);
385      }
386      if (!is) throw DataFormatError("PathReader format error");
387      copyPath(value, _path_bits::PathProxy<typename Path::Edge>(v));
388    }
389   
390  };
391 
392}
393
394#endif
Note: See TracBrowser for help on using the repository browser.