Fix wrong reference in the documentation.
2 * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 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.
29 #include <lemon/error.h>
31 /// \todo fix exceptions
40 virtual ~IOException() {}
41 virtual string what() const = 0;
44 class DataFormatException : public IOException {
47 DataFormatException(const std::string& _message)
48 : message(_message) {}
49 std::string what() const {
50 return "DataFormatException: " + message;
54 template <typename _Exception>
55 class StreamException : public _Exception {
57 typedef _Exception Exception;
58 StreamException(int _line, Exception _exception)
59 : Exception(_exception), line_num(_line) {}
60 virtual int line() const {
64 virtual ~StreamException() {}
66 virtual std::string what() const {
68 os << Exception::what() << " in line " << line();
76 /// \brief Standard ReaderTraits for the GraphReader class.
78 /// Standard ReaderTraits for the GraphReader class.
79 /// It defines standard reading method for all type of value.
80 struct DefaultReaderTraits {
82 /// \brief Template class for reading an value.
84 /// Template class for reading an value.
85 template <typename _Value>
89 /// \brief Reads a value from the given stream.
91 /// Reads a value from the given stream.
92 void read(std::istream& is, Value& value) {
94 throw DataFormatException("Default Reader format exception");
98 /// The reader class for the not needed maps.
99 typedef Reader<std::string> DefaultReader;
103 /// \brief Reader class for quoted strings.
105 /// Reader class for quoted strings. It can process the escape
106 /// sequences in the string.
107 class QuotedStringReader {
109 typedef std::string Value;
111 /// \brief Constructor for the reader.
113 /// Constructor for the reader. If the given parameter is true
114 /// the reader processes the escape sequences.
115 QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
117 /// \brief Reads a quoted string from the given stream.
119 /// Reads a quoted string from the given stream.
120 void read(std::istream& is, std::string& value) {
124 if (!is.get(c) || c != '\"')
125 throw DataFormatException("Quoted string format");
126 while (is.get(c) && c != '\"') {
127 if (escaped && c == '\\') {
128 value += readEscape(is);
133 if (!is) throw DataFormatException("Quoted string format");
138 static char readEscape(std::istream& is) {
140 switch (is.get(c), c) {
166 if (!is.get(c) || !isHex(c))
167 throw DataFormatException("Escape format exception");
168 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
169 else code = code * 16 + valueHex(c);
176 throw DataFormatException("Escape format exception");
177 else if (code = valueOct(c), !is.get(c) || !isOct(c))
179 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
181 else code = code * 8 + valueOct(c);
187 static bool isOct(char c) {
188 return '0' <= c && c <='7';
191 static int valueOct(char c) {
195 static bool isHex(char c) {
196 return ('0' <= c && c <= '9') ||
197 ('a' <= c && c <= 'z') ||
198 ('A' <= c && c <= 'Z');
201 static int valueHex(char c) {
202 if ('0' <= c && c <= '9') return c - '0';
203 if ('a' <= c && c <= 'z') return c - 'a' + 10;
210 /// \brief The graph reader class.
212 /// The reader class for the graph input.
213 /// \see \ref GraphWriter
214 /// \see \ref graph-io-page
215 template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
219 typedef _Graph Graph;
220 typedef typename Graph::Node Node;
221 typedef typename Graph::Edge Edge;
223 typedef _ReaderTraits ReaderTraits;
224 typedef typename ReaderTraits::DefaultReader DefaultReader;
226 /// \brief Construct a new GraphReader.
228 /// Construct a new GraphReader. It reads from the given map,
229 /// it constructs the given map and it use the given reader as the
231 GraphReader(std::istream& _is, Graph& _graph,
232 const DefaultReader& _reader = DefaultReader())
233 : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
235 /// \brief Destruct the graph reader.
237 /// Destruct the graph reader.
240 for (typename NodeMapReaders::iterator it = node_map_readers.begin();
241 it != node_map_readers.end(); ++it) {
245 for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
246 it != edge_map_readers.end(); ++it) {
252 /// \brief Add a new node map reader command for the reader.
254 /// Add a new node map reader command for the reader.
255 template <typename Map>
256 GraphReader& addNodeMap(std::string name, Map& map) {
257 return addNodeMap<typename ReaderTraits::template
258 Reader<typename Map::Value>, Map>(name, map);
261 /// \brief Add a new node map reader command for the reader.
263 /// Add a new node map reader command for the reader.
264 template <typename Reader, typename Map>
265 GraphReader& addNodeMap(std::string name, Map& map,
266 const Reader& reader = Reader()) {
267 if (node_map_readers.find(name) != node_map_readers.end()) {
268 throw Exception() << "Multiple read rule for node map: " << name;
270 node_map_readers.insert(
271 make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
275 /// \brief Add a new node map skipper command for the reader.
277 /// Add a new node map skipper command for the reader.
278 template <typename Reader>
279 GraphReader& skipNodeMap(std::string name,
280 const Reader& reader = Reader()) {
281 if (node_map_readers.find(name) != node_map_readers.end()) {
282 throw Exception() << "Multiple read rule for node map: " << name;
284 node_map_readers.insert(
285 make_pair(name, new SkipReader<Node, Reader>(reader)));
289 /// \brief Add a new edge map reader command for the reader.
291 /// Add a new edge map reader command for the reader.
292 template <typename Map>
293 GraphReader& addEdgeMap(std::string name, Map& map) {
294 return addEdgeMap<typename ReaderTraits::template
295 Reader<typename Map::Value>, Map>(name, map);
299 /// \brief Add a new edge map reader command for the reader.
301 /// Add a new edge map reader command for the reader.
302 template <typename Reader, typename Map>
303 GraphReader& addEdgeMap(std::string name, Map& map,
304 const Reader& reader = Reader()) {
305 if (edge_map_readers.find(name) != edge_map_readers.end()) {
306 throw Exception() << "Multiple read rule for edge map: " << name;
308 edge_map_readers.insert(
309 make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
313 /// \brief Add a new edge map skipper command for the reader.
315 /// Add a new edge map skipper command for the reader.
316 template <typename Reader>
317 GraphReader& skipEdgeMap(std::string name,
318 const Reader& reader = Reader()) {
319 if (edge_map_readers.find(name) != edge_map_readers.end()) {
320 throw Exception() << "Multiple read rule for edge map: " << name;
322 edge_map_readers.insert(
323 make_pair(name, new SkipReader<Edge, Reader>(reader)));
327 /// \brief Add a new labeled node reader for the reader.
329 /// Add a new labeled node reader for the reader.
330 GraphReader& addNode(std::string name, Node& node) {
331 if (node_readers.find(name) != node_readers.end()) {
332 throw Exception() << "Multiple read rule for node";
334 node_readers.insert(make_pair(name, &node));
338 /// \brief Add a new labeled edge reader for the reader.
340 /// Add a new labeled edge reader for the reader.
341 GraphReader& addEdge(std::string name, Edge& edge) {
342 if (edge_readers.find(name) != edge_readers.end()) {
343 throw Exception() << "Multiple read rule for edge";
345 edge_readers.insert(make_pair(name, &edge));
349 /// \brief Executes the reader commands.
351 /// Executes the reader commands.
354 std::auto_ptr<InverterBase<Node> > nodeInverter;
355 std::auto_ptr<InverterBase<Edge> > edgeInverter;
357 std::string line = readNotEmptyLine(is, line_num);
358 if (line.find("@nodeset") == 0) {
359 line = readNodeSet(line_num, nodeInverter);
361 if (line.find("@edgeset") == 0) {
362 line = readEdgeSet(line_num, edgeInverter, nodeInverter);
364 if (line.find("@nodes") == 0) {
365 line = readNodes(line_num, nodeInverter);
367 if (line.find("@edges") == 0) {
368 line = readEdges(line_num, edgeInverter);
370 if (line.find("@end") != 0) {
371 throw DataFormatException("Invalid control sequence: " + line);
373 } catch (DataFormatException e) {
374 throw StreamException<DataFormatException>(line_num, e);
380 template <typename Item> class InverterBase;
382 std::string readNodeSet(int& line_num,
383 auto_ptr<InverterBase<Node> > & nodeInverter) {
384 std::vector<ReaderBase<Node>* > index;
386 std::string line = readNotEmptyLine(is, line_num);
388 std::istringstream ls(line);
390 if (id[0] == '#') break;
391 typename NodeMapReaders::iterator it = node_map_readers.find(id);
392 if (it != node_map_readers.end()) {
393 index.push_back(it->second);
394 node_map_readers.erase(it);
396 index.push_back(&nodeSkipper);
401 if (index.size() == 0) {
402 throw DataFormatException("No node map found");
405 nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
407 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
408 Node node = graph.addNode();
409 std::istringstream ls(line);
410 nodeInverter->read(ls, node);
411 for (int i = 1; i < (int)index.size(); ++i) {
412 index[i]->read(ls, node);
418 std::string readEdgeSet(int& line_num,
419 auto_ptr<InverterBase<Edge> > & edgeInverter,
420 auto_ptr<InverterBase<Node> > & nodeInverter) {
421 std::vector<ReaderBase<Edge>*> index;
423 std::string line = readNotEmptyLine(is, line_num);
425 std::istringstream ls(line);
427 if (id[0] == '#') break;
428 typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
429 if (it != edge_map_readers.end()) {
430 index.push_back(it->second);
431 edge_map_readers.erase(it);
433 index.push_back(&edgeSkipper);
438 if (index.size() == 0) {
439 throw DataFormatException("No edge map found");
442 edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
444 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
445 std::istringstream ls(line);
446 Node source = nodeInverter->read(ls);
447 Node target = nodeInverter->read(ls);
448 Edge edge = graph.addEdge(source, target);
449 edgeInverter->read(ls, edge);
450 for (int i = 1; i < (int)index.size(); ++i) {
451 index[i]->read(ls, edge);
457 std::string readNodes(int& line_num,
458 auto_ptr<InverterBase<Node> >& nodeInverter) {
460 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
461 std::istringstream ls(line);
464 typename NodeReaders::iterator it = node_readers.find(name);
465 if (it != node_readers.end()) {
466 *(it -> second) = nodeInverter->read(ls);
472 std::string readEdges(int& line_num,
473 auto_ptr<InverterBase<Edge> >& edgeInverter) {
475 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
476 std::istringstream ls(line);
479 typename EdgeReaders::iterator it = edge_readers.find(name);
480 if (it != edge_readers.end()) {
481 *(it -> second) = edgeInverter->read(ls);
487 std::string readNotEmptyLine(std::istream& is, int& line_num) {
489 while (++line_num, getline(is, line)) {
490 int vi = line.find_first_not_of(" \t");
491 if (vi != (int)string::npos && line[vi] != '#') {
492 return line.substr(vi);
495 throw DataFormatException("End of stream");
498 // Inverters store and give back the Item from the id,
499 // and may put the ids into a map.
501 template <typename _Item>
505 virtual void read(std::istream&, const Item&) = 0;
506 virtual Item read(std::istream&) = 0;
509 template <typename _Item, typename _Map, typename _Reader>
510 class MapReaderInverter : public InverterBase<_Item> {
513 typedef _Reader Reader;
514 typedef typename Reader::Value Value;
516 typedef std::map<Value, Item> Inverse;
522 MapReaderInverter(Map& _map, const Reader& _reader)
523 : map(_map), reader(_reader) {}
525 virtual ~MapReaderInverter() {}
527 virtual void read(std::istream& is, const Item& item) {
529 reader.read(is, value);
530 map.set(item, value);
531 typename Inverse::iterator it = inverse.find(value);
532 if (it == inverse.end()) {
533 inverse.insert(make_pair(value, item));
535 throw DataFormatException("Multiple ID occurence");
539 virtual Item read(std::istream& is) {
541 reader.read(is, value);
542 typename Inverse::const_iterator it = inverse.find(value);
543 if (it != inverse.end()) {
546 throw DataFormatException("Invalid ID");
551 template <typename _Item, typename _Reader>
552 class SkipReaderInverter : public InverterBase<_Item> {
555 typedef _Reader Reader;
556 typedef typename Reader::Value Value;
557 typedef std::map<Value, Item> Inverse;
561 SkipReaderInverter(const Reader& _reader)
564 virtual ~SkipReaderInverter() {}
566 virtual void read(std::istream& is, const Item& item) {
568 reader.read(is, value);
569 typename Inverse::iterator it = inverse.find(value);
570 if (it == inverse.end()) {
571 inverse.insert(make_pair(value, item));
573 throw DataFormatException("Multiple ID occurence");
577 virtual Item read(std::istream& is) {
579 reader.read(is, value);
580 typename Inverse::const_iterator it = inverse.find(value);
581 if (it != inverse.end()) {
584 throw DataFormatException("Invalid ID");
593 template <typename _Item>
598 // virtual ~ReaderBase() {}
600 virtual void read(std::istream& is, const Item& item) = 0;
601 virtual InverterBase<_Item>* getInverter() = 0;
604 template <typename _Item, typename _Map, typename _Reader>
605 class MapReader : public ReaderBase<_Item> {
608 typedef _Reader Reader;
609 typedef typename Reader::Value Value;
615 MapReader(Map& _map, const Reader& _reader)
616 : map(_map), reader(_reader) {}
618 virtual ~MapReader() {}
620 virtual void read(std::istream& is, const Item& item) {
622 reader.read(is, value);
623 map.set(item, value);
626 virtual InverterBase<_Item>* getInverter() {
627 return new MapReaderInverter<Item, Map, Reader>(map, reader);
632 template <typename _Item, typename _Reader>
633 class SkipReader : public ReaderBase<_Item> {
635 typedef _Reader Reader;
636 typedef typename Reader::Value Value;
640 SkipReader(const Reader& _reader) : reader(_reader) {}
642 virtual ~SkipReader() {}
644 virtual void read(std::istream& is, const Item& item) {
646 reader.read(is, value);
649 virtual InverterBase<Item>* getInverter() {
650 return new SkipReaderInverter<Item, Reader>(reader);
655 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
656 NodeMapReaders node_map_readers;
658 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
659 EdgeMapReaders edge_map_readers;
661 typedef std::map<std::string, Node*> NodeReaders;
662 NodeReaders node_readers;
664 typedef std::map<std::string, Edge*> EdgeReaders;
665 EdgeReaders edge_readers;
670 SkipReader<Node, DefaultReader> nodeSkipper;
671 SkipReader<Edge, DefaultReader> edgeSkipper;