Revert to long long int since currently I don't know a better solution.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 ///\brief Classes for representing paths in graphs.
24 #ifndef LEMON_PATH_UTILS_H
25 #define LEMON_PATH_UTILS_H
27 #include <lemon/concepts/path.h>
28 #include <lemon/lemon_reader.h>
29 #include <lemon/lemon_writer.h>
33 namespace _path_bits {
35 template <typename Path, typename Enable = void>
36 struct RevTagIndicator {
37 static const bool value = false;
40 template <typename Graph>
41 struct RevTagIndicator<
43 typename enable_if<typename Graph::RevTag, void>::type
45 static const bool value = true;
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) {
53 for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
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) {
65 for (typename Source::RevEdgeIt it(source); it != INVALID; ++it) {
71 template <typename Target, typename Source, typename RevEnable>
72 struct PathCopySelector<
74 typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
75 static void copy(Target& target, const Source& source) {
81 template <typename Target, typename Source>
82 struct PathCopySelector<
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) {
88 target.buildRev(source);
95 /// \brief Make of copy of a path.
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);
104 /// \brief Checks the path's consistency.
106 /// Checks that each edge's target is the next's source.
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);
114 while (it != INVALID) {
115 if (graph.source(it) != node) return false;
116 node = graph.target(it);
122 /// \brief Gives back the source of the path
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());
130 /// \brief Gives back the target of the path
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());
138 /// \brief Class which helps to iterate the nodes of a path
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.
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>
151 const typename Path::Graph *_graph;
152 typename Path::EdgeIt _it;
153 typename Path::Graph::Node _nd;
157 typedef typename Path::Graph Graph;
158 typedef typename Graph::Node Node;
160 /// Default constructor
162 /// Invalid constructor
164 : _graph(0), _it(INVALID), _nd(INVALID) {}
166 PathNodeIt(const Graph& graph, const Path& path)
167 : _graph(&graph), _it(path) {
168 _nd = (_it != INVALID ? _graph->source(_it) : INVALID);
171 PathNodeIt(const Graph& graph, const Path& path, const Node& src)
172 : _graph(&graph), _it(path), _nd(src) {}
174 ///Conversion to Graph::Node
175 operator Node() const {
180 PathNodeIt& operator++() {
181 if (_it == INVALID) _nd = INVALID;
183 _nd = _graph->target(_it);
189 /// Comparison operator
190 bool operator==(const PathNodeIt& n) const {
191 return _it == n._it && _nd == n._nd;
193 /// Comparison operator
194 bool operator!=(const PathNodeIt& n) const {
195 return _it != n._it || _nd != n._nd;
197 /// Comparison operator
198 bool operator<(const PathNodeIt& n) const {
199 return (_it < n._it && _nd != INVALID);
204 /// \brief Item writer for paths
206 /// This class can write paths into files. You can store paths in
207 /// distinict mapset or in attributes section.
210 /// GraphWriter<SmartGraph> gw(std::cout, g);
211 /// NodeMapWriter<SmartGraph> nmw(gw, g, gw);
213 /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
214 /// for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
215 /// pnm[n] = bfs.path(n);
217 /// nmw.writeNodeMap("pnm", pnm, PathWriter<Path<SmartGraph> >(gw));
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>
230 typedef typename Path::Edge Edge;
231 std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > edgeLabelWriter;
237 PathWriter(const PathWriter& pw) {
238 edgeLabelWriter.reset(pw.edgeLabelWriter->clone());
241 /// \brief Constructor
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));
251 /// \brief Writer function
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");
260 for (typename Path::EdgeIt e(value); e != INVALID; ++e) {
261 edgeLabelWriter->write(os, e);
269 namespace _path_bits {
271 template <typename _Graph>
274 typedef False RevPathTag;
276 typedef _Graph Graph;
277 typedef typename Graph::Edge Edge;
279 PathProxy(const std::vector<Edge>& edges)
283 return _edges.size();
287 return _edges.size() == 0;
293 EdgeIt(const PathProxy& path)
294 : _path(&path), _index(0) {}
296 operator const Edge() const {
297 return _path->_edges[_index];
300 EdgeIt& operator++() {
305 bool operator==(Invalid) const {
306 return int(_path->_edges.size()) == _index;
308 bool operator!=(Invalid) const {
309 return int(_path->_edges.size()) != _index;
313 const PathProxy* _path;
318 const std::vector<Edge>& _edges;
324 /// \brief Item reader for paths
326 /// This class can read paths from files. You can store paths in
327 /// distinict mapset or in attributes section.
330 /// GraphReader<SmartGraph> gr(std::cout, g);
331 /// NodeMapReader<SmartGraph> nmr(gr, g, gr);
333 /// SmartGraph::NodeMap<Path<SmartGraph> > pnm(g);
334 /// nmr.readNodeMap("pnm", pnm, PathReader<Path<SmartGraph> >(gr));
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>
347 typedef typename Path::Edge Edge;
348 std::auto_ptr<_reader_bits::LabelReaderBase<Edge> > edgeLabelReader;
354 PathReader(const PathReader& pw) {
355 edgeLabelReader.reset(pw.edgeLabelReader->clone());
358 /// \brief Constructor
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));
369 /// \brief Reader function
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");
378 if (!(is >> c) || c != '(')
379 throw DataFormatError("PathReader format error");
380 std::vector<typename Path::Edge> v;
381 while (is >> c && c != ')') {
383 Edge edge = edgeLabelReader->read(is);
386 if (!is) throw DataFormatError("PathReader format error");
387 copyPath(value, _path_bits::PathProxy<typename Path::Edge>(v));