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>
37 /// \addtogroup io_group
40 /// \brief Standard ReaderTraits for the GraphReader class.
42 /// Standard ReaderTraits for the GraphReader class.
43 /// It defines standard reading method for all type of value.
44 /// \author Balazs Dezso
45 struct DefaultReaderTraits {
47 /// \brief Template class for reading an value.
49 /// Template class for reading an value.
50 /// \author Balazs Dezso
51 template <typename _Value>
55 /// \brief Reads a value from the given stream.
57 /// Reads a value from the given stream.
58 void read(std::istream& is, Value& value) {
60 throw DataFormatError("Default reader format exception");
64 /// \brief Returns wheter this name is an ID map name.
66 /// Returns wheter this name is an ID map name.
67 static bool idMapName(const std::string& name) {
71 /// The reader class for the not needed maps.
72 typedef Reader<std::string> DefaultReader;
76 /// \brief Reader class for quoted strings.
78 /// Reader class for quoted strings. It can process the escape
79 /// sequences in the string.
80 /// \author Balazs Dezso
81 class QuotedStringReader {
83 typedef std::string Value;
85 /// \brief Constructor for the reader.
87 /// Constructor for the reader. If the given parameter is true
88 /// the reader processes the escape sequences.
89 QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
91 /// \brief Reads a quoted string from the given stream.
93 /// Reads a quoted string from the given stream.
94 void read(std::istream& is, std::string& value) {
98 if (!is.get(c) || c != '\"')
99 throw DataFormatError("Quoted string format error");
100 while (is.get(c) && c != '\"') {
101 if (escaped && c == '\\') {
102 value += readEscape(is);
107 if (!is) throw DataFormatError("Quoted string format error");
112 static char readEscape(std::istream& is) {
114 switch (is.get(c), c) {
140 if (!is.get(c) || !isHex(c))
141 throw DataFormatError("Escape format error");
142 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
143 else code = code * 16 + valueHex(c);
150 throw DataFormatError("Escape format error");
151 else if (code = valueOct(c), !is.get(c) || !isOct(c))
153 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
155 else code = code * 8 + valueOct(c);
161 static bool isOct(char c) {
162 return '0' <= c && c <='7';
165 static int valueOct(char c) {
169 static bool isHex(char c) {
170 return ('0' <= c && c <= '9') ||
171 ('a' <= c && c <= 'z') ||
172 ('A' <= c && c <= 'Z');
175 static int valueHex(char c) {
176 if ('0' <= c && c <= '9') return c - '0';
177 if ('a' <= c && c <= 'z') return c - 'a' + 10;
184 /// \brief The graph reader class.
187 /// The given file format may contain several maps and labeled nodes or
190 /// If you read a graph you need not read all the maps and items just those
191 /// that you need. The interface of the \c GraphReader is very similar to
192 /// the GraphWriter but the reading method does not depend on the order the
195 /// The reader object suppose that each not readed value does not contain
196 /// whitespaces, therefore it has some extra possibilities to control how
197 /// it should skip the values when the string representation contains spaces.
200 /// GraphReader<ListGraph> reader(std::cin, graph);
203 /// The \c addNodeMap() function reads a map from the \c \@nodeset section.
204 /// If there is a map that you do not want to read from the file and there is
205 /// whitespace in the string represenation of the values then you should
206 /// call the \c skipNodeMap() template member function with proper
210 /// reader.addNodeMap("x-coord", xCoordMap);
211 /// reader.addNodeMap("y-coord", yCoordMap);
213 /// reader.addNodeMap<QuotedStringReader>("label", labelMap);
214 /// reader.skipNodeMap<QuotedStringReader>("description");
216 /// reader.addNodeMap("color", colorMap);
219 /// With the \c addEdgeMap() member function you can give an edge map
220 /// reading command similar to the NodeMaps.
223 /// reader.addEdgeMap("weight", weightMap);
224 /// reader.addEdgeMap("label", labelMap);
227 /// With \c addNode() and \c addEdge() functions you can read labeled Nodes
231 /// reader.addNode("source", sourceNode);
232 /// reader.addNode("target", targetNode);
234 /// reader.addEdge("observed", edge);
237 /// After you give all read commands you must call the \c run() member
238 /// function, which execute all the commands.
244 /// \see DefaultReaderTraits
245 /// \see QuotedStringReader
246 /// \see \ref GraphWriter
247 /// \see \ref graph-io-page
248 /// \author Balazs Dezso
249 template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
253 typedef _Graph Graph;
254 typedef typename Graph::Node Node;
255 typedef typename Graph::Edge Edge;
257 typedef _ReaderTraits ReaderTraits;
258 typedef typename ReaderTraits::DefaultReader DefaultReader;
260 /// \brief Construct a new GraphReader.
262 /// Construct a new GraphReader. It reads into the given graph
263 /// and it use the given reader as the default skipper.
264 GraphReader(std::istream& _is, Graph& _graph,
265 const DefaultReader& _reader = DefaultReader())
266 : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
268 /// \brief Destruct the graph reader.
270 /// Destruct the graph reader.
272 for (typename NodeMapReaders::iterator it = node_map_readers.begin();
273 it != node_map_readers.end(); ++it) {
277 for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
278 it != edge_map_readers.end(); ++it) {
284 /// \brief Add a new node map reader command for the reader.
286 /// Add a new node map reader command for the reader.
287 template <typename Map>
288 GraphReader& addNodeMap(std::string name, Map& map) {
289 return addNodeMap<typename ReaderTraits::template
290 Reader<typename Map::Value>, Map>(name, map);
293 /// \brief Add a new node map reader command for the reader.
295 /// Add a new node map reader command for the reader.
296 template <typename Reader, typename Map>
297 GraphReader& addNodeMap(std::string name, Map& map,
298 const Reader& reader = Reader()) {
299 if (node_map_readers.find(name) != node_map_readers.end()) {
301 msg << "Multiple read rule for node map: " << name;
302 throw IOParameterError(msg.message());
304 node_map_readers.insert(
305 make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
309 /// \brief Add a new node map skipper command for the reader.
311 /// Add a new node map skipper command for the reader.
312 template <typename Reader>
313 GraphReader& skipNodeMap(std::string name,
314 const Reader& reader = Reader()) {
315 if (node_map_readers.find(name) != node_map_readers.end()) {
317 msg << "Multiple read rule for node map: " << name;
318 throw IOParameterError(msg.message());
320 node_map_readers.insert(
321 make_pair(name, new SkipReader<Node, Reader>(reader)));
325 /// \brief Add a new edge map reader command for the reader.
327 /// Add a new edge map reader command for the reader.
328 template <typename Map>
329 GraphReader& addEdgeMap(std::string name, Map& map) {
330 return addEdgeMap<typename ReaderTraits::template
331 Reader<typename Map::Value>, Map>(name, map);
335 /// \brief Add a new edge map reader command for the reader.
337 /// Add a new edge map reader command for the reader.
338 template <typename Reader, typename Map>
339 GraphReader& addEdgeMap(std::string name, Map& map,
340 const Reader& reader = Reader()) {
341 if (edge_map_readers.find(name) != edge_map_readers.end()) {
343 msg << "Multiple read rule for edge map: " << name;
344 throw IOParameterError(msg.message());
346 edge_map_readers.insert(
347 make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
351 /// \brief Add a new edge map skipper command for the reader.
353 /// Add a new edge map skipper command for the reader.
354 template <typename Reader>
355 GraphReader& skipEdgeMap(std::string name,
356 const Reader& reader = Reader()) {
357 if (edge_map_readers.find(name) != edge_map_readers.end()) {
359 msg << "Multiple read rule for edge map: " << name;
360 throw IOParameterError(msg.message());
362 edge_map_readers.insert(
363 make_pair(name, new SkipReader<Edge, Reader>(reader)));
367 /// \brief Add a new labeled node reader for the reader.
369 /// Add a new labeled node reader for the reader.
370 GraphReader& addNode(std::string name, Node& node) {
371 if (node_readers.find(name) != node_readers.end()) {
373 msg << "Multiple read rule for node: " << name;
374 throw IOParameterError(msg.message());
376 node_readers.insert(make_pair(name, &node));
380 /// \brief Add a new labeled edge reader for the reader.
382 /// Add a new labeled edge reader for the reader.
383 GraphReader& addEdge(std::string name, Edge& edge) {
384 if (edge_readers.find(name) != edge_readers.end()) {
386 msg << "Multiple read rule for edge: " << name;
387 throw IOParameterError(msg.message());
389 edge_readers.insert(make_pair(name, &edge));
393 /// \brief Executes the reader commands.
395 /// Executes the reader commands.
398 std::auto_ptr<InverterBase<Node> > nodeInverter;
399 std::auto_ptr<InverterBase<Edge> > edgeInverter;
401 std::string line = readNotEmptyLine(is, line_num);
402 if (line.find("@nodeset") == 0) {
403 line = readNodeSet(line_num, nodeInverter);
405 if (line.find("@edgeset") == 0) {
406 line = readEdgeSet(line_num, edgeInverter, nodeInverter);
408 if (line.find("@nodes") == 0) {
409 line = readNodes(line_num, nodeInverter);
411 if (line.find("@edges") == 0) {
412 line = readEdges(line_num, edgeInverter);
414 if (line.find("@end") != 0) {
415 throw DataFormatError("Invalid control sequence error");
417 } catch (DataFormatError e) {
425 template <typename Item> class InverterBase;
427 std::string readNodeSet(int& line_num,
428 std::auto_ptr<InverterBase<Node> >& nodeInverter) {
429 std::vector<ReaderBase<Node>* > index;
431 std::string line = readNotEmptyLine(is, line_num);
433 std::istringstream ls(line);
435 typename NodeMapReaders::iterator it = node_map_readers.find(id);
436 if (it != node_map_readers.end()) {
437 index.push_back(it->second);
438 node_map_readers.erase(it);
440 index.push_back(&nodeSkipper);
442 if (ReaderTraits::idMapName(id) && nodeInverter.get() == 0) {
443 nodeInverter.reset(index.back()->getInverter());
444 index.back() = nodeInverter.get();
449 // if (index.size() == 0) {
450 // throw DataFormatError("Cannot find node id map");
454 // std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
456 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
457 Node node = graph.addNode();
458 std::istringstream ls(line);
459 for (int i = 0; i < (int)index.size(); ++i) {
460 index[i]->read(ls, node);
466 std::string readEdgeSet(int& line_num,
467 std::auto_ptr<InverterBase<Edge> >& edgeInverter,
468 std::auto_ptr<InverterBase<Node> >& nodeInverter) {
469 std::vector<ReaderBase<Edge>*> index;
471 std::string line = readNotEmptyLine(is, line_num);
473 std::istringstream ls(line);
475 typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
476 if (it != edge_map_readers.end()) {
477 index.push_back(it->second);
478 edge_map_readers.erase(it);
480 index.push_back(&edgeSkipper);
482 if (ReaderTraits::idMapName(id) && edgeInverter.get() == 0) {
483 edgeInverter.reset(index.back()->getInverter());
484 index.back() = edgeInverter.get();
489 if (nodeInverter.get() == 0) {
490 throw DataFormatError("Cannot find node id map");
492 // if (index.size() == 0) {
493 // throw DataFormatError("Cannot find edge id map");
497 // std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
499 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
500 std::istringstream ls(line);
501 Node source = nodeInverter->read(ls);
502 Node target = nodeInverter->read(ls);
503 Edge edge = graph.addEdge(source, target);
504 for (int i = 0; i < (int)index.size(); ++i) {
505 index[i]->read(ls, edge);
511 std::string readNodes(int& line_num,
512 std::auto_ptr<InverterBase<Node> >& nodeInverter) {
514 if (nodeInverter.get() == 0) {
515 throw DataFormatError("Cannot find node id map");
517 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
518 std::istringstream ls(line);
521 typename NodeReaders::iterator it = node_readers.find(name);
522 if (it != node_readers.end()) {
523 *(it -> second) = nodeInverter->read(ls);
529 std::string readEdges(int& line_num,
530 std::auto_ptr<InverterBase<Edge> >& edgeInverter) {
532 if (edgeInverter.get() == 0) {
533 throw DataFormatError("Cannot find edge id map");
535 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
536 std::istringstream ls(line);
539 typename EdgeReaders::iterator it = edge_readers.find(name);
540 if (it != edge_readers.end()) {
541 *(it -> second) = edgeInverter->read(ls);
547 std::string readNotEmptyLine(std::istream& is, int& line_num) {
549 while (++line_num, getline(is, line)) {
550 int vi = line.find('#');
551 if (vi != (int)::std::string::npos) {
552 line = line.substr(0, vi);
554 vi = line.find_first_not_of(" \t");
555 if (vi != (int)std::string::npos) {
556 // std::cerr << "Line: " << line.substr(vi) << std::endl;
557 return line.substr(vi);
560 throw DataFormatError("End of stream error");
563 template <typename _Item>
566 template <typename _Item>
567 class InverterBase : public ReaderBase<_Item> {
570 virtual void read(std::istream&, const Item&) = 0;
571 virtual Item read(std::istream&) = 0;
573 virtual InverterBase<_Item>* getInverter() {
578 template <typename _Item, typename _Map, typename _Reader>
579 class MapReaderInverter : public InverterBase<_Item> {
582 typedef _Reader Reader;
583 typedef typename Reader::Value Value;
585 typedef std::map<Value, Item> Inverse;
591 MapReaderInverter(Map& _map, const Reader& _reader)
592 : map(_map), reader(_reader) {}
594 virtual ~MapReaderInverter() {}
596 virtual void read(std::istream& is, const Item& item) {
598 reader.read(is, value);
599 map.set(item, value);
600 typename Inverse::iterator it = inverse.find(value);
601 if (it == inverse.end()) {
602 inverse.insert(std::make_pair(value, item));
604 throw DataFormatError("Multiple ID occurence");
608 virtual Item read(std::istream& is) {
610 reader.read(is, value);
611 typename Inverse::const_iterator it = inverse.find(value);
612 if (it != inverse.end()) {
615 throw DataFormatError("Invalid ID error");
620 template <typename _Item, typename _Reader>
621 class SkipReaderInverter : public InverterBase<_Item> {
624 typedef _Reader Reader;
625 typedef typename Reader::Value Value;
626 typedef std::map<Value, Item> Inverse;
630 SkipReaderInverter(const Reader& _reader)
633 virtual ~SkipReaderInverter() {}
635 virtual void read(std::istream& is, const Item& item) {
637 reader.read(is, value);
638 typename Inverse::iterator it = inverse.find(value);
639 if (it == inverse.end()) {
640 inverse.insert(std::make_pair(value, item));
642 throw DataFormatError("Multiple ID occurence error");
646 virtual Item read(std::istream& is) {
648 reader.read(is, value);
649 typename Inverse::const_iterator it = inverse.find(value);
650 if (it != inverse.end()) {
653 throw DataFormatError("Invalid ID error");
662 template <typename _Item>
667 // virtual ~ReaderBase() {}
669 virtual void read(std::istream& is, const Item& item) = 0;
670 virtual InverterBase<_Item>* getInverter() = 0;
673 template <typename _Item, typename _Map, typename _Reader>
674 class MapReader : public ReaderBase<_Item> {
677 typedef _Reader Reader;
678 typedef typename Reader::Value Value;
684 MapReader(Map& _map, const Reader& _reader)
685 : map(_map), reader(_reader) {}
687 virtual ~MapReader() {}
689 virtual void read(std::istream& is, const Item& item) {
691 reader.read(is, value);
692 map.set(item, value);
695 virtual InverterBase<_Item>* getInverter() {
696 return new MapReaderInverter<Item, Map, Reader>(map, reader);
701 template <typename _Item, typename _Reader>
702 class SkipReader : public ReaderBase<_Item> {
704 typedef _Reader Reader;
705 typedef typename Reader::Value Value;
709 SkipReader(const Reader& _reader) : reader(_reader) {}
711 virtual ~SkipReader() {}
713 virtual void read(std::istream& is, const Item&) {
715 reader.read(is, value);
718 virtual InverterBase<Item>* getInverter() {
719 return new SkipReaderInverter<Item, Reader>(reader);
724 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
725 NodeMapReaders node_map_readers;
727 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
728 EdgeMapReaders edge_map_readers;
730 typedef std::map<std::string, Node*> NodeReaders;
731 NodeReaders node_readers;
733 typedef std::map<std::string, Edge*> EdgeReaders;
734 EdgeReaders edge_readers;
739 SkipReader<Node, DefaultReader> nodeSkipper;
740 SkipReader<Edge, DefaultReader> edgeSkipper;
744 /// \brief Read a graph from the input.
746 /// Read a graph from the input.
747 /// \param is The input stream.
748 /// \param g The graph.
749 /// \param capacity The capacity map.
750 /// \param s The source node.
751 /// \param t The target node.
752 /// \param cost The cost map.
753 template<typename Graph, typename CapacityMap, typename CostMap>
754 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
755 typename Graph::Node &s, typename Graph::Node &t,
757 GraphReader<Graph> reader(is, g);
758 reader.addEdgeMap("capacity", capacity);
759 reader.addEdgeMap("cost", cost);
760 reader.addNode("source", s);
761 reader.addNode("target", t);
765 /// \brief Read a graph from the input.
767 /// Read a graph from the input.
768 /// \param is The input stream.
769 /// \param g The graph.
770 /// \param capacity The capacity map.
771 /// \param s The source node.
772 /// \param t The target node.
773 template<typename Graph, typename CapacityMap>
774 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
775 typename Graph::Node &s, typename Graph::Node &t) {
776 GraphReader<Graph> reader(is, g);
777 reader.addEdgeMap("capacity", capacity);
778 reader.addNode("source", s);
779 reader.addNode("target", t);
783 /// \brief Read a graph from the input.
785 /// Read a graph from the input.
786 /// \param is The input stream.
787 /// \param g The graph.
788 /// \param capacity The capacity map.
789 /// \param s The source node.
790 template<typename Graph, typename CapacityMap>
791 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
792 typename Graph::Node &s) {
793 GraphReader<Graph> reader(is, g);
794 reader.addEdgeMap("capacity", capacity);
795 reader.addNode("source", s);
799 /// \brief Read a graph from the input.
801 /// Read a graph from the input.
802 /// \param is The input stream.
803 /// \param g The graph.
804 /// \param capacity The capacity map.
805 template<typename Graph, typename CapacityMap>
806 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
807 GraphReader<Graph> reader(is, g);
808 reader.addEdgeMap("capacity", capacity);
812 /// \brief Read a graph from the input.
814 /// Read a graph from the input.
815 /// \param is The input stream.
816 /// \param g The graph.
817 template<typename Graph>
818 void readGraph(std::istream& is, Graph &g) {
819 GraphReader<Graph> reader(is, g);