Bug fix.
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 Lemon Graph Format 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 /// \ingroup io_group
175 /// The reader class for the graph input.
176 /// \see DefaultReaderTraits
177 /// \see QuotedStringReader
178 /// \see \ref GraphWriter
179 /// \see \ref graph-io-page
180 template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
184 typedef _Graph Graph;
185 typedef typename Graph::Node Node;
186 typedef typename Graph::Edge Edge;
188 typedef _ReaderTraits ReaderTraits;
189 typedef typename ReaderTraits::DefaultReader DefaultReader;
191 /// \brief Construct a new GraphReader.
193 /// Construct a new GraphReader. It reads into the given graph
194 /// and it use the given reader as the default skipper.
195 GraphReader(std::istream& _is, Graph& _graph,
196 const DefaultReader& _reader = DefaultReader())
197 : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
199 /// \brief Destruct the graph reader.
201 /// Destruct the graph reader.
204 for (typename NodeMapReaders::iterator it = node_map_readers.begin();
205 it != node_map_readers.end(); ++it) {
209 for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
210 it != edge_map_readers.end(); ++it) {
216 /// \brief Add a new node map reader command for the reader.
218 /// Add a new node map reader command for the reader.
219 template <typename Map>
220 GraphReader& addNodeMap(std::string name, Map& map) {
221 return addNodeMap<typename ReaderTraits::template
222 Reader<typename Map::Value>, Map>(name, map);
225 /// \brief Add a new node map reader command for the reader.
227 /// Add a new node map reader command for the reader.
228 template <typename Reader, typename Map>
229 GraphReader& addNodeMap(std::string name, Map& map,
230 const Reader& reader = Reader()) {
231 if (node_map_readers.find(name) != node_map_readers.end()) {
233 msg << "Multiple read rule for node map: " << name;
234 throw IOParameterError(msg.message());
236 node_map_readers.insert(
237 make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
241 /// \brief Add a new node map skipper command for the reader.
243 /// Add a new node map skipper command for the reader.
244 template <typename Reader>
245 GraphReader& skipNodeMap(std::string name,
246 const Reader& reader = Reader()) {
247 if (node_map_readers.find(name) != node_map_readers.end()) {
249 msg << "Multiple read rule for node map: " << name;
250 throw IOParameterError(msg.message());
252 node_map_readers.insert(
253 make_pair(name, new SkipReader<Node, Reader>(reader)));
257 /// \brief Add a new edge map reader command for the reader.
259 /// Add a new edge map reader command for the reader.
260 template <typename Map>
261 GraphReader& addEdgeMap(std::string name, Map& map) {
262 return addEdgeMap<typename ReaderTraits::template
263 Reader<typename Map::Value>, Map>(name, map);
267 /// \brief Add a new edge map reader command for the reader.
269 /// Add a new edge map reader command for the reader.
270 template <typename Reader, typename Map>
271 GraphReader& addEdgeMap(std::string name, Map& map,
272 const Reader& reader = Reader()) {
273 if (edge_map_readers.find(name) != edge_map_readers.end()) {
275 msg << "Multiple read rule for edge map: " << name;
276 throw IOParameterError(msg.message());
278 edge_map_readers.insert(
279 make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
283 /// \brief Add a new edge map skipper command for the reader.
285 /// Add a new edge map skipper command for the reader.
286 template <typename Reader>
287 GraphReader& skipEdgeMap(std::string name,
288 const Reader& reader = Reader()) {
289 if (edge_map_readers.find(name) != edge_map_readers.end()) {
291 msg << "Multiple read rule for edge map: " << name;
292 throw IOParameterError(msg.message());
294 edge_map_readers.insert(
295 make_pair(name, new SkipReader<Edge, Reader>(reader)));
299 /// \brief Add a new labeled node reader for the reader.
301 /// Add a new labeled node reader for the reader.
302 GraphReader& addNode(std::string name, Node& node) {
303 if (node_readers.find(name) != node_readers.end()) {
305 msg << "Multiple read rule for node: " << name;
306 throw IOParameterError(msg.message());
308 node_readers.insert(make_pair(name, &node));
312 /// \brief Add a new labeled edge reader for the reader.
314 /// Add a new labeled edge reader for the reader.
315 GraphReader& addEdge(std::string name, Edge& edge) {
316 if (edge_readers.find(name) != edge_readers.end()) {
318 msg << "Multiple read rule for edge: " << name;
319 throw IOParameterError(msg.message());
321 edge_readers.insert(make_pair(name, &edge));
325 /// \brief Executes the reader commands.
327 /// Executes the reader commands.
330 std::auto_ptr<InverterBase<Node> > nodeInverter;
331 std::auto_ptr<InverterBase<Edge> > edgeInverter;
333 std::string line = readNotEmptyLine(is, line_num);
334 if (line.find("@nodeset") == 0) {
335 line = readNodeSet(line_num, nodeInverter);
337 if (line.find("@edgeset") == 0) {
338 line = readEdgeSet(line_num, edgeInverter, nodeInverter);
340 if (line.find("@nodes") == 0) {
341 line = readNodes(line_num, nodeInverter);
343 if (line.find("@edges") == 0) {
344 line = readEdges(line_num, edgeInverter);
346 if (line.find("@end") != 0) {
347 throw DataFormatError("Invalid control sequence error");
349 } catch (DataFormatError e) {
357 template <typename Item> class InverterBase;
359 std::string readNodeSet(int& line_num,
360 auto_ptr<InverterBase<Node> > & nodeInverter) {
361 std::vector<ReaderBase<Node>* > index;
363 std::string line = readNotEmptyLine(is, line_num);
365 std::istringstream ls(line);
367 if (id[0] == '#') break;
368 typename NodeMapReaders::iterator it = node_map_readers.find(id);
369 if (it != node_map_readers.end()) {
370 index.push_back(it->second);
371 node_map_readers.erase(it);
373 index.push_back(&nodeSkipper);
378 if (index.size() == 0) {
379 throw DataFormatError("Cannot find node id map");
382 nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
384 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
385 Node node = graph.addNode();
386 std::istringstream ls(line);
387 nodeInverter->read(ls, node);
388 for (int i = 1; i < (int)index.size(); ++i) {
389 index[i]->read(ls, node);
395 std::string readEdgeSet(int& line_num,
396 auto_ptr<InverterBase<Edge> > & edgeInverter,
397 auto_ptr<InverterBase<Node> > & nodeInverter) {
398 std::vector<ReaderBase<Edge>*> index;
400 std::string line = readNotEmptyLine(is, line_num);
402 std::istringstream ls(line);
404 if (id[0] == '#') break;
405 typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
406 if (it != edge_map_readers.end()) {
407 index.push_back(it->second);
408 edge_map_readers.erase(it);
410 index.push_back(&edgeSkipper);
415 if (index.size() == 0) {
416 throw DataFormatError("Cannot find edge id map");
419 edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
421 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
422 std::istringstream ls(line);
423 Node source = nodeInverter->read(ls);
424 Node target = nodeInverter->read(ls);
425 Edge edge = graph.addEdge(source, target);
426 edgeInverter->read(ls, edge);
427 for (int i = 1; i < (int)index.size(); ++i) {
428 index[i]->read(ls, edge);
434 std::string readNodes(int& line_num,
435 auto_ptr<InverterBase<Node> >& nodeInverter) {
437 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
438 std::istringstream ls(line);
441 typename NodeReaders::iterator it = node_readers.find(name);
442 if (it != node_readers.end()) {
443 *(it -> second) = nodeInverter->read(ls);
449 std::string readEdges(int& line_num,
450 auto_ptr<InverterBase<Edge> >& edgeInverter) {
452 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
453 std::istringstream ls(line);
456 typename EdgeReaders::iterator it = edge_readers.find(name);
457 if (it != edge_readers.end()) {
458 *(it -> second) = edgeInverter->read(ls);
464 std::string readNotEmptyLine(std::istream& is, int& line_num) {
466 while (++line_num, getline(is, line)) {
467 int vi = line.find_first_not_of(" \t");
468 if (vi != (int)string::npos && line[vi] != '#') {
469 return line.substr(vi);
472 throw DataFormatError("End of stream error");
475 // Inverters store and give back the Item from the id,
476 // and may put the ids into a map.
478 template <typename _Item>
482 virtual void read(std::istream&, const Item&) = 0;
483 virtual Item read(std::istream&) = 0;
486 template <typename _Item, typename _Map, typename _Reader>
487 class MapReaderInverter : public InverterBase<_Item> {
490 typedef _Reader Reader;
491 typedef typename Reader::Value Value;
493 typedef std::map<Value, Item> Inverse;
499 MapReaderInverter(Map& _map, const Reader& _reader)
500 : map(_map), reader(_reader) {}
502 virtual ~MapReaderInverter() {}
504 virtual void read(std::istream& is, const Item& item) {
506 reader.read(is, value);
507 map.set(item, value);
508 typename Inverse::iterator it = inverse.find(value);
509 if (it == inverse.end()) {
510 inverse.insert(make_pair(value, item));
512 throw DataFormatError("Multiple ID occurence");
516 virtual Item read(std::istream& is) {
518 reader.read(is, value);
519 typename Inverse::const_iterator it = inverse.find(value);
520 if (it != inverse.end()) {
523 throw DataFormatError("Invalid ID error");
528 template <typename _Item, typename _Reader>
529 class SkipReaderInverter : public InverterBase<_Item> {
532 typedef _Reader Reader;
533 typedef typename Reader::Value Value;
534 typedef std::map<Value, Item> Inverse;
538 SkipReaderInverter(const Reader& _reader)
541 virtual ~SkipReaderInverter() {}
543 virtual void read(std::istream& is, const Item& item) {
545 reader.read(is, value);
546 typename Inverse::iterator it = inverse.find(value);
547 if (it == inverse.end()) {
548 inverse.insert(make_pair(value, item));
550 throw DataFormatError("Multiple ID occurence error");
554 virtual Item read(std::istream& is) {
556 reader.read(is, value);
557 typename Inverse::const_iterator it = inverse.find(value);
558 if (it != inverse.end()) {
561 throw DataFormatError("Invalid ID error");
570 template <typename _Item>
575 // virtual ~ReaderBase() {}
577 virtual void read(std::istream& is, const Item& item) = 0;
578 virtual InverterBase<_Item>* getInverter() = 0;
581 template <typename _Item, typename _Map, typename _Reader>
582 class MapReader : public ReaderBase<_Item> {
585 typedef _Reader Reader;
586 typedef typename Reader::Value Value;
592 MapReader(Map& _map, const Reader& _reader)
593 : map(_map), reader(_reader) {}
595 virtual ~MapReader() {}
597 virtual void read(std::istream& is, const Item& item) {
599 reader.read(is, value);
600 map.set(item, value);
603 virtual InverterBase<_Item>* getInverter() {
604 return new MapReaderInverter<Item, Map, Reader>(map, reader);
609 template <typename _Item, typename _Reader>
610 class SkipReader : public ReaderBase<_Item> {
612 typedef _Reader Reader;
613 typedef typename Reader::Value Value;
617 SkipReader(const Reader& _reader) : reader(_reader) {}
619 virtual ~SkipReader() {}
621 virtual void read(std::istream& is, const Item&) {
623 reader.read(is, value);
626 virtual InverterBase<Item>* getInverter() {
627 return new SkipReaderInverter<Item, Reader>(reader);
632 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
633 NodeMapReaders node_map_readers;
635 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
636 EdgeMapReaders edge_map_readers;
638 typedef std::map<std::string, Node*> NodeReaders;
639 NodeReaders node_readers;
641 typedef std::map<std::string, Edge*> EdgeReaders;
642 EdgeReaders edge_readers;
647 SkipReader<Node, DefaultReader> nodeSkipper;
648 SkipReader<Edge, DefaultReader> edgeSkipper;
652 /// Ready to use reader function.
653 template<typename Graph, typename CapacityMap, typename CostMap>
654 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
655 typename Graph::Node &s, typename Graph::Node &t,
657 GraphReader<Graph> reader(is, g);
658 reader.addEdgeMap("capacity", capacity);
659 reader.addEdgeMap("cost", cost);
660 reader.addNode("source", s);
661 reader.addNode("target", t);
665 template<typename Graph, typename CapacityMap>
666 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
667 typename Graph::Node &s, typename Graph::Node &t) {
668 GraphReader<Graph> reader(is, g);
669 reader.addEdgeMap("capacity", capacity);
670 reader.addNode("source", s);
671 reader.addNode("target", t);
675 template<typename Graph, typename CapacityMap>
676 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
677 typename Graph::Node &s) {
678 GraphReader<Graph> reader(is, g);
679 reader.addEdgeMap("capacity", capacity);
680 reader.addNode("source", s);
684 template<typename Graph, typename CapacityMap>
685 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
686 GraphReader<Graph> reader(is, g);
687 reader.addEdgeMap("capacity", capacity);
691 template<typename Graph>
692 void readGraph(std::istream& is, Graph &g) {
693 GraphReader<Graph> reader(is, g);