A strange compilation failure (under cygwin) is fixed.
Version 0.3 should be fixed as well.
2 * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
19 ///\brief Graph reader.
21 #ifndef LEMON_GRAPH_READER_H
22 #define LEMON_GRAPH_READER_H
32 #include <lemon/error.h>
38 /// \brief Standard ReaderTraits for the GraphReader class.
40 /// Standard ReaderTraits for the GraphReader class.
41 /// It defines standard reading method for all type of value.
42 struct DefaultReaderTraits {
44 /// \brief Template class for reading an value.
46 /// Template class for reading an value.
47 template <typename _Value>
51 /// \brief Reads a value from the given stream.
53 /// Reads a value from the given stream.
54 void read(std::istream& is, Value& value) {
56 throw DataFormatError("Default reader format exception");
60 /// The reader class for the not needed maps.
61 typedef Reader<std::string> DefaultReader;
65 /// \brief Reader class for quoted strings.
67 /// Reader class for quoted strings. It can process the escape
68 /// sequences in the string.
69 class QuotedStringReader {
71 typedef std::string Value;
73 /// \brief Constructor for the reader.
75 /// Constructor for the reader. If the given parameter is true
76 /// the reader processes the escape sequences.
77 QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
79 /// \brief Reads a quoted string from the given stream.
81 /// Reads a quoted string from the given stream.
82 void read(std::istream& is, std::string& value) {
86 if (!is.get(c) || c != '\"')
87 throw DataFormatError("Quoted string format error");
88 while (is.get(c) && c != '\"') {
89 if (escaped && c == '\\') {
90 value += readEscape(is);
95 if (!is) throw DataFormatError("Quoted string format error");
100 static char readEscape(std::istream& is) {
102 switch (is.get(c), c) {
128 if (!is.get(c) || !isHex(c))
129 throw DataFormatError("Escape format error");
130 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
131 else code = code * 16 + valueHex(c);
138 throw DataFormatError("Escape format error");
139 else if (code = valueOct(c), !is.get(c) || !isOct(c))
141 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
143 else code = code * 8 + valueOct(c);
149 static bool isOct(char c) {
150 return '0' <= c && c <='7';
153 static int valueOct(char c) {
157 static bool isHex(char c) {
158 return ('0' <= c && c <= '9') ||
159 ('a' <= c && c <= 'z') ||
160 ('A' <= c && c <= 'Z');
163 static int valueHex(char c) {
164 if ('0' <= c && c <= '9') return c - '0';
165 if ('a' <= c && c <= 'z') return c - 'a' + 10;
172 /// \brief The graph reader class.
174 /// The reader class for the graph input.
175 /// \see \ref GraphWriter
176 /// \see \ref graph-io-page
177 template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
181 typedef _Graph Graph;
182 typedef typename Graph::Node Node;
183 typedef typename Graph::Edge Edge;
185 typedef _ReaderTraits ReaderTraits;
186 typedef typename ReaderTraits::DefaultReader DefaultReader;
188 /// \brief Construct a new GraphReader.
190 /// Construct a new GraphReader. It reads into the given graph
191 /// and it use the given reader as the default skipper.
192 GraphReader(std::istream& _is, Graph& _graph,
193 const DefaultReader& _reader = DefaultReader())
194 : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
196 /// \brief Destruct the graph reader.
198 /// Destruct the graph reader.
201 for (typename NodeMapReaders::iterator it = node_map_readers.begin();
202 it != node_map_readers.end(); ++it) {
206 for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
207 it != edge_map_readers.end(); ++it) {
213 /// \brief Add a new node map reader command for the reader.
215 /// Add a new node map reader command for the reader.
216 template <typename Map>
217 GraphReader& addNodeMap(std::string name, Map& map) {
218 return addNodeMap<typename ReaderTraits::template
219 Reader<typename Map::Value>, Map>(name, map);
222 /// \brief Add a new node map reader command for the reader.
224 /// Add a new node map reader command for the reader.
225 template <typename Reader, typename Map>
226 GraphReader& addNodeMap(std::string name, Map& map,
227 const Reader& reader = Reader()) {
228 if (node_map_readers.find(name) != node_map_readers.end()) {
230 msg << "Multiple read rule for node map: " << name;
231 throw IOParameterError(msg.message());
233 node_map_readers.insert(
234 make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
238 /// \brief Add a new node map skipper command for the reader.
240 /// Add a new node map skipper command for the reader.
241 template <typename Reader>
242 GraphReader& skipNodeMap(std::string name,
243 const Reader& reader = Reader()) {
244 if (node_map_readers.find(name) != node_map_readers.end()) {
246 msg << "Multiple read rule for node map: " << name;
247 throw IOParameterError(msg.message());
249 node_map_readers.insert(
250 make_pair(name, new SkipReader<Node, Reader>(reader)));
254 /// \brief Add a new edge map reader command for the reader.
256 /// Add a new edge map reader command for the reader.
257 template <typename Map>
258 GraphReader& addEdgeMap(std::string name, Map& map) {
259 return addEdgeMap<typename ReaderTraits::template
260 Reader<typename Map::Value>, Map>(name, map);
264 /// \brief Add a new edge map reader command for the reader.
266 /// Add a new edge map reader command for the reader.
267 template <typename Reader, typename Map>
268 GraphReader& addEdgeMap(std::string name, Map& map,
269 const Reader& reader = Reader()) {
270 if (edge_map_readers.find(name) != edge_map_readers.end()) {
272 msg << "Multiple read rule for edge map: " << name;
273 throw IOParameterError(msg.message());
275 edge_map_readers.insert(
276 make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
280 /// \brief Add a new edge map skipper command for the reader.
282 /// Add a new edge map skipper command for the reader.
283 template <typename Reader>
284 GraphReader& skipEdgeMap(std::string name,
285 const Reader& reader = Reader()) {
286 if (edge_map_readers.find(name) != edge_map_readers.end()) {
288 msg << "Multiple read rule for edge map: " << name;
289 throw IOParameterError(msg.message());
291 edge_map_readers.insert(
292 make_pair(name, new SkipReader<Edge, Reader>(reader)));
296 /// \brief Add a new labeled node reader for the reader.
298 /// Add a new labeled node reader for the reader.
299 GraphReader& addNode(std::string name, Node& node) {
300 if (node_readers.find(name) != node_readers.end()) {
302 msg << "Multiple read rule for node: " << name;
303 throw IOParameterError(msg.message());
305 node_readers.insert(make_pair(name, &node));
309 /// \brief Add a new labeled edge reader for the reader.
311 /// Add a new labeled edge reader for the reader.
312 GraphReader& addEdge(std::string name, Edge& edge) {
313 if (edge_readers.find(name) != edge_readers.end()) {
315 msg << "Multiple read rule for edge: " << name;
316 throw IOParameterError(msg.message());
318 edge_readers.insert(make_pair(name, &edge));
322 /// \brief Executes the reader commands.
324 /// Executes the reader commands.
327 std::auto_ptr<InverterBase<Node> > nodeInverter;
328 std::auto_ptr<InverterBase<Edge> > edgeInverter;
330 std::string line = readNotEmptyLine(is, line_num);
331 if (line.find("@nodeset") == 0) {
332 line = readNodeSet(line_num, nodeInverter);
334 if (line.find("@edgeset") == 0) {
335 line = readEdgeSet(line_num, edgeInverter, nodeInverter);
337 if (line.find("@nodes") == 0) {
338 line = readNodes(line_num, nodeInverter);
340 if (line.find("@edges") == 0) {
341 line = readEdges(line_num, edgeInverter);
343 if (line.find("@end") != 0) {
344 throw DataFormatError("Invalid control sequence error");
346 } catch (DataFormatError e) {
354 template <typename Item> class InverterBase;
356 std::string readNodeSet(int& line_num,
357 auto_ptr<InverterBase<Node> > & nodeInverter) {
358 std::vector<ReaderBase<Node>* > index;
360 std::string line = readNotEmptyLine(is, line_num);
362 std::istringstream ls(line);
364 if (id[0] == '#') break;
365 typename NodeMapReaders::iterator it = node_map_readers.find(id);
366 if (it != node_map_readers.end()) {
367 index.push_back(it->second);
368 node_map_readers.erase(it);
370 index.push_back(&nodeSkipper);
375 if (index.size() == 0) {
376 throw DataFormatError("Cannot find node id map");
379 nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
381 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
382 Node node = graph.addNode();
383 std::istringstream ls(line);
384 nodeInverter->read(ls, node);
385 for (int i = 1; i < (int)index.size(); ++i) {
386 index[i]->read(ls, node);
392 std::string readEdgeSet(int& line_num,
393 auto_ptr<InverterBase<Edge> > & edgeInverter,
394 auto_ptr<InverterBase<Node> > & nodeInverter) {
395 std::vector<ReaderBase<Edge>*> index;
397 std::string line = readNotEmptyLine(is, line_num);
399 std::istringstream ls(line);
401 if (id[0] == '#') break;
402 typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
403 if (it != edge_map_readers.end()) {
404 index.push_back(it->second);
405 edge_map_readers.erase(it);
407 index.push_back(&edgeSkipper);
412 if (index.size() == 0) {
413 throw DataFormatError("Cannot find edge id map");
416 edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
418 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
419 std::istringstream ls(line);
420 Node source = nodeInverter->read(ls);
421 Node target = nodeInverter->read(ls);
422 Edge edge = graph.addEdge(source, target);
423 edgeInverter->read(ls, edge);
424 for (int i = 1; i < (int)index.size(); ++i) {
425 index[i]->read(ls, edge);
431 std::string readNodes(int& line_num,
432 auto_ptr<InverterBase<Node> >& nodeInverter) {
434 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
435 std::istringstream ls(line);
438 typename NodeReaders::iterator it = node_readers.find(name);
439 if (it != node_readers.end()) {
440 *(it -> second) = nodeInverter->read(ls);
446 std::string readEdges(int& line_num,
447 auto_ptr<InverterBase<Edge> >& edgeInverter) {
449 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
450 std::istringstream ls(line);
453 typename EdgeReaders::iterator it = edge_readers.find(name);
454 if (it != edge_readers.end()) {
455 *(it -> second) = edgeInverter->read(ls);
461 std::string readNotEmptyLine(std::istream& is, int& line_num) {
463 while (++line_num, getline(is, line)) {
464 int vi = line.find_first_not_of(" \t");
465 if (vi != (int)string::npos && line[vi] != '#') {
466 return line.substr(vi);
469 throw DataFormatError("End of stream error");
472 // Inverters store and give back the Item from the id,
473 // and may put the ids into a map.
475 template <typename _Item>
479 virtual void read(std::istream&, const Item&) = 0;
480 virtual Item read(std::istream&) = 0;
483 template <typename _Item, typename _Map, typename _Reader>
484 class MapReaderInverter : public InverterBase<_Item> {
487 typedef _Reader Reader;
488 typedef typename Reader::Value Value;
490 typedef std::map<Value, Item> Inverse;
496 MapReaderInverter(Map& _map, const Reader& _reader)
497 : map(_map), reader(_reader) {}
499 virtual ~MapReaderInverter() {}
501 virtual void read(std::istream& is, const Item& item) {
503 reader.read(is, value);
504 map.set(item, value);
505 typename Inverse::iterator it = inverse.find(value);
506 if (it == inverse.end()) {
507 inverse.insert(make_pair(value, item));
509 throw DataFormatError("Multiple ID occurence");
513 virtual Item read(std::istream& is) {
515 reader.read(is, value);
516 typename Inverse::const_iterator it = inverse.find(value);
517 if (it != inverse.end()) {
520 throw DataFormatError("Invalid ID error");
525 template <typename _Item, typename _Reader>
526 class SkipReaderInverter : public InverterBase<_Item> {
529 typedef _Reader Reader;
530 typedef typename Reader::Value Value;
531 typedef std::map<Value, Item> Inverse;
535 SkipReaderInverter(const Reader& _reader)
538 virtual ~SkipReaderInverter() {}
540 virtual void read(std::istream& is, const Item& item) {
542 reader.read(is, value);
543 typename Inverse::iterator it = inverse.find(value);
544 if (it == inverse.end()) {
545 inverse.insert(make_pair(value, item));
547 throw DataFormatError("Multiple ID occurence error");
551 virtual Item read(std::istream& is) {
553 reader.read(is, value);
554 typename Inverse::const_iterator it = inverse.find(value);
555 if (it != inverse.end()) {
558 throw DataFormatError("Invalid ID error");
567 template <typename _Item>
572 // virtual ~ReaderBase() {}
574 virtual void read(std::istream& is, const Item& item) = 0;
575 virtual InverterBase<_Item>* getInverter() = 0;
578 template <typename _Item, typename _Map, typename _Reader>
579 class MapReader : public ReaderBase<_Item> {
582 typedef _Reader Reader;
583 typedef typename Reader::Value Value;
589 MapReader(Map& _map, const Reader& _reader)
590 : map(_map), reader(_reader) {}
592 virtual ~MapReader() {}
594 virtual void read(std::istream& is, const Item& item) {
596 reader.read(is, value);
597 map.set(item, value);
600 virtual InverterBase<_Item>* getInverter() {
601 return new MapReaderInverter<Item, Map, Reader>(map, reader);
606 template <typename _Item, typename _Reader>
607 class SkipReader : public ReaderBase<_Item> {
609 typedef _Reader Reader;
610 typedef typename Reader::Value Value;
614 SkipReader(const Reader& _reader) : reader(_reader) {}
616 virtual ~SkipReader() {}
618 virtual void read(std::istream& is, const Item& item) {
620 reader.read(is, value);
623 virtual InverterBase<Item>* getInverter() {
624 return new SkipReaderInverter<Item, Reader>(reader);
629 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
630 NodeMapReaders node_map_readers;
632 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
633 EdgeMapReaders edge_map_readers;
635 typedef std::map<std::string, Node*> NodeReaders;
636 NodeReaders node_readers;
638 typedef std::map<std::string, Edge*> EdgeReaders;
639 EdgeReaders edge_readers;
644 SkipReader<Node, DefaultReader> nodeSkipper;
645 SkipReader<Edge, DefaultReader> edgeSkipper;
649 /// Ready to use reader function.
650 template<typename Graph, typename CapacityMap, typename CostMap>
651 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
652 typename Graph::Node &s, typename Graph::Node &t,
654 GraphReader<Graph> reader(is, g);
655 reader.addEdgeMap("capacity", capacity);
656 reader.addEdgeMap("cost", cost);
657 reader.addNode("source", s);
658 reader.addNode("target", t);
662 template<typename Graph, typename CapacityMap>
663 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
664 typename Graph::Node &s, typename Graph::Node &t) {
665 GraphReader<Graph> reader(is, g);
666 reader.addEdgeMap("capacity", capacity);
667 reader.addNode("source", s);
668 reader.addNode("target", t);
672 template<typename Graph, typename CapacityMap>
673 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
674 typename Graph::Node &s) {
675 GraphReader<Graph> reader(is, g);
676 reader.addEdgeMap("capacity", capacity);
677 reader.addNode("source", s);
681 template<typename Graph, typename CapacityMap>
682 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
683 GraphReader<Graph> reader(is, g);
684 reader.addEdgeMap("capacity", capacity);
688 template<typename Graph>
689 void readGraph(std::istream& is, Graph &g) {
690 GraphReader<Graph> reader(is, g);