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 std::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");
383 std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
385 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
386 Node node = graph.addNode();
387 std::istringstream ls(line);
388 nodeInverter->read(ls, node);
389 for (int i = 1; i < (int)index.size(); ++i) {
390 index[i]->read(ls, node);
396 std::string readEdgeSet(int& line_num,
397 std::auto_ptr<InverterBase<Edge> >& edgeInverter,
398 std::auto_ptr<InverterBase<Node> >& nodeInverter) {
399 std::vector<ReaderBase<Edge>*> index;
401 std::string line = readNotEmptyLine(is, line_num);
403 std::istringstream ls(line);
405 if (id[0] == '#') break;
406 typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
407 if (it != edge_map_readers.end()) {
408 index.push_back(it->second);
409 edge_map_readers.erase(it);
411 index.push_back(&edgeSkipper);
416 if (index.size() == 0) {
417 throw DataFormatError("Cannot find edge id map");
421 std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
423 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
424 std::istringstream ls(line);
425 Node source = nodeInverter->read(ls);
426 Node target = nodeInverter->read(ls);
427 Edge edge = graph.addEdge(source, target);
428 edgeInverter->read(ls, edge);
429 for (int i = 1; i < (int)index.size(); ++i) {
430 index[i]->read(ls, edge);
436 std::string readNodes(int& line_num,
437 std::auto_ptr<InverterBase<Node> >& nodeInverter) {
439 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
440 std::istringstream ls(line);
443 typename NodeReaders::iterator it = node_readers.find(name);
444 if (it != node_readers.end()) {
445 *(it -> second) = nodeInverter->read(ls);
451 std::string readEdges(int& line_num,
452 std::auto_ptr<InverterBase<Edge> >& edgeInverter) {
454 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
455 std::istringstream ls(line);
458 typename EdgeReaders::iterator it = edge_readers.find(name);
459 if (it != edge_readers.end()) {
460 *(it -> second) = edgeInverter->read(ls);
466 std::string readNotEmptyLine(std::istream& is, int& line_num) {
468 while (++line_num, getline(is, line)) {
469 int vi = line.find_first_not_of(" \t");
470 if (vi != (int)std::string::npos && line[vi] != '#') {
471 return line.substr(vi);
474 throw DataFormatError("End of stream error");
477 // Inverters store and give back the Item from the id,
478 // and may put the ids into a map.
480 template <typename _Item>
484 virtual void read(std::istream&, const Item&) = 0;
485 virtual Item read(std::istream&) = 0;
488 template <typename _Item, typename _Map, typename _Reader>
489 class MapReaderInverter : public InverterBase<_Item> {
492 typedef _Reader Reader;
493 typedef typename Reader::Value Value;
495 typedef std::map<Value, Item> Inverse;
501 MapReaderInverter(Map& _map, const Reader& _reader)
502 : map(_map), reader(_reader) {}
504 virtual ~MapReaderInverter() {}
506 virtual void read(std::istream& is, const Item& item) {
508 reader.read(is, value);
509 map.set(item, value);
510 typename Inverse::iterator it = inverse.find(value);
511 if (it == inverse.end()) {
512 inverse.insert(std::make_pair(value, item));
514 throw DataFormatError("Multiple ID occurence");
518 virtual Item read(std::istream& is) {
520 reader.read(is, value);
521 typename Inverse::const_iterator it = inverse.find(value);
522 if (it != inverse.end()) {
525 throw DataFormatError("Invalid ID error");
530 template <typename _Item, typename _Reader>
531 class SkipReaderInverter : public InverterBase<_Item> {
534 typedef _Reader Reader;
535 typedef typename Reader::Value Value;
536 typedef std::map<Value, Item> Inverse;
540 SkipReaderInverter(const Reader& _reader)
543 virtual ~SkipReaderInverter() {}
545 virtual void read(std::istream& is, const Item& item) {
547 reader.read(is, value);
548 typename Inverse::iterator it = inverse.find(value);
549 if (it == inverse.end()) {
550 inverse.insert(std::make_pair(value, item));
552 throw DataFormatError("Multiple ID occurence error");
556 virtual Item read(std::istream& is) {
558 reader.read(is, value);
559 typename Inverse::const_iterator it = inverse.find(value);
560 if (it != inverse.end()) {
563 throw DataFormatError("Invalid ID error");
572 template <typename _Item>
577 // virtual ~ReaderBase() {}
579 virtual void read(std::istream& is, const Item& item) = 0;
580 virtual InverterBase<_Item>* getInverter() = 0;
583 template <typename _Item, typename _Map, typename _Reader>
584 class MapReader : public ReaderBase<_Item> {
587 typedef _Reader Reader;
588 typedef typename Reader::Value Value;
594 MapReader(Map& _map, const Reader& _reader)
595 : map(_map), reader(_reader) {}
597 virtual ~MapReader() {}
599 virtual void read(std::istream& is, const Item& item) {
601 reader.read(is, value);
602 map.set(item, value);
605 virtual InverterBase<_Item>* getInverter() {
606 return new MapReaderInverter<Item, Map, Reader>(map, reader);
611 template <typename _Item, typename _Reader>
612 class SkipReader : public ReaderBase<_Item> {
614 typedef _Reader Reader;
615 typedef typename Reader::Value Value;
619 SkipReader(const Reader& _reader) : reader(_reader) {}
621 virtual ~SkipReader() {}
623 virtual void read(std::istream& is, const Item&) {
625 reader.read(is, value);
628 virtual InverterBase<Item>* getInverter() {
629 return new SkipReaderInverter<Item, Reader>(reader);
634 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
635 NodeMapReaders node_map_readers;
637 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
638 EdgeMapReaders edge_map_readers;
640 typedef std::map<std::string, Node*> NodeReaders;
641 NodeReaders node_readers;
643 typedef std::map<std::string, Edge*> EdgeReaders;
644 EdgeReaders edge_readers;
649 SkipReader<Node, DefaultReader> nodeSkipper;
650 SkipReader<Edge, DefaultReader> edgeSkipper;
654 /// Ready to use reader function.
655 template<typename Graph, typename CapacityMap, typename CostMap>
656 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
657 typename Graph::Node &s, typename Graph::Node &t,
659 GraphReader<Graph> reader(is, g);
660 reader.addEdgeMap("capacity", capacity);
661 reader.addEdgeMap("cost", cost);
662 reader.addNode("source", s);
663 reader.addNode("target", t);
667 template<typename Graph, typename CapacityMap>
668 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
669 typename Graph::Node &s, typename Graph::Node &t) {
670 GraphReader<Graph> reader(is, g);
671 reader.addEdgeMap("capacity", capacity);
672 reader.addNode("source", s);
673 reader.addNode("target", t);
677 template<typename Graph, typename CapacityMap>
678 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
679 typename Graph::Node &s) {
680 GraphReader<Graph> reader(is, g);
681 reader.addEdgeMap("capacity", capacity);
682 reader.addNode("source", s);
686 template<typename Graph, typename CapacityMap>
687 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
688 GraphReader<Graph> reader(is, g);
689 reader.addEdgeMap("capacity", capacity);
693 template<typename Graph>
694 void readGraph(std::istream& is, Graph &g) {
695 GraphReader<Graph> reader(is, g);