This way it works also when both GLPK and CPLEX are enabled.
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 Research Group on Combinatorial Optimization, 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 return line.substr(vi);
559 throw DataFormatError("End of stream error");
562 template <typename _Item>
565 template <typename _Item>
566 class InverterBase : public ReaderBase<_Item> {
569 virtual void read(std::istream&, const Item&) = 0;
570 virtual Item read(std::istream&) = 0;
572 virtual InverterBase<_Item>* getInverter() {
577 template <typename _Item, typename _Map, typename _Reader>
578 class MapReaderInverter : public InverterBase<_Item> {
581 typedef _Reader Reader;
582 typedef typename Reader::Value Value;
584 typedef std::map<Value, Item> Inverse;
590 MapReaderInverter(Map& _map, const Reader& _reader)
591 : map(_map), reader(_reader) {}
593 virtual ~MapReaderInverter() {}
595 virtual void read(std::istream& is, const Item& item) {
597 reader.read(is, value);
598 map.set(item, value);
599 typename Inverse::iterator it = inverse.find(value);
600 if (it == inverse.end()) {
601 inverse.insert(std::make_pair(value, item));
603 throw DataFormatError("Multiple ID occurence");
607 virtual Item read(std::istream& is) {
609 reader.read(is, value);
610 typename Inverse::const_iterator it = inverse.find(value);
611 if (it != inverse.end()) {
614 throw DataFormatError("Invalid ID error");
619 template <typename _Item, typename _Reader>
620 class SkipReaderInverter : public InverterBase<_Item> {
623 typedef _Reader Reader;
624 typedef typename Reader::Value Value;
625 typedef std::map<Value, Item> Inverse;
629 SkipReaderInverter(const Reader& _reader)
632 virtual ~SkipReaderInverter() {}
634 virtual void read(std::istream& is, const Item& item) {
636 reader.read(is, value);
637 typename Inverse::iterator it = inverse.find(value);
638 if (it == inverse.end()) {
639 inverse.insert(std::make_pair(value, item));
641 throw DataFormatError("Multiple ID occurence error");
645 virtual Item read(std::istream& is) {
647 reader.read(is, value);
648 typename Inverse::const_iterator it = inverse.find(value);
649 if (it != inverse.end()) {
652 throw DataFormatError("Invalid ID error");
661 template <typename _Item>
666 // virtual ~ReaderBase() {}
668 virtual void read(std::istream& is, const Item& item) = 0;
669 virtual InverterBase<_Item>* getInverter() = 0;
672 template <typename _Item, typename _Map, typename _Reader>
673 class MapReader : public ReaderBase<_Item> {
676 typedef _Reader Reader;
677 typedef typename Reader::Value Value;
683 MapReader(Map& _map, const Reader& _reader)
684 : map(_map), reader(_reader) {}
686 virtual ~MapReader() {}
688 virtual void read(std::istream& is, const Item& item) {
690 reader.read(is, value);
691 map.set(item, value);
694 virtual InverterBase<_Item>* getInverter() {
695 return new MapReaderInverter<Item, Map, Reader>(map, reader);
700 template <typename _Item, typename _Reader>
701 class SkipReader : public ReaderBase<_Item> {
703 typedef _Reader Reader;
704 typedef typename Reader::Value Value;
708 SkipReader(const Reader& _reader) : reader(_reader) {}
710 virtual ~SkipReader() {}
712 virtual void read(std::istream& is, const Item&) {
714 reader.read(is, value);
717 virtual InverterBase<Item>* getInverter() {
718 return new SkipReaderInverter<Item, Reader>(reader);
723 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
724 NodeMapReaders node_map_readers;
726 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
727 EdgeMapReaders edge_map_readers;
729 typedef std::map<std::string, Node*> NodeReaders;
730 NodeReaders node_readers;
732 typedef std::map<std::string, Edge*> EdgeReaders;
733 EdgeReaders edge_readers;
738 SkipReader<Node, DefaultReader> nodeSkipper;
739 SkipReader<Edge, DefaultReader> edgeSkipper;
743 /// \brief Read a graph from the input.
745 /// Read a graph from the input.
746 /// \param is The input stream.
747 /// \param g The graph.
748 /// \param capacity The capacity map.
749 /// \param s The source node.
750 /// \param t The target node.
751 /// \param cost The cost map.
752 template<typename Graph, typename CapacityMap, typename CostMap>
753 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
754 typename Graph::Node &s, typename Graph::Node &t,
756 GraphReader<Graph> reader(is, g);
757 reader.addEdgeMap("capacity", capacity);
758 reader.addEdgeMap("cost", cost);
759 reader.addNode("source", s);
760 reader.addNode("target", t);
764 /// \brief Read a graph from the input.
766 /// Read a graph from the input.
767 /// \param is The input stream.
768 /// \param g The graph.
769 /// \param capacity The capacity map.
770 /// \param s The source node.
771 /// \param t The target node.
772 template<typename Graph, typename CapacityMap>
773 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
774 typename Graph::Node &s, typename Graph::Node &t) {
775 GraphReader<Graph> reader(is, g);
776 reader.addEdgeMap("capacity", capacity);
777 reader.addNode("source", s);
778 reader.addNode("target", t);
782 /// \brief Read a graph from the input.
784 /// Read a graph from the input.
785 /// \param is The input stream.
786 /// \param g The graph.
787 /// \param capacity The capacity map.
788 /// \param s The source node.
789 template<typename Graph, typename CapacityMap>
790 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
791 typename Graph::Node &s) {
792 GraphReader<Graph> reader(is, g);
793 reader.addEdgeMap("capacity", capacity);
794 reader.addNode("source", s);
798 /// \brief Read a graph from the input.
800 /// Read a graph from the input.
801 /// \param is The input stream.
802 /// \param g The graph.
803 /// \param capacity The capacity map.
804 template<typename Graph, typename CapacityMap>
805 void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
806 GraphReader<Graph> reader(is, g);
807 reader.addEdgeMap("capacity", capacity);
811 /// \brief Read a graph from the input.
813 /// Read a graph from the input.
814 /// \param is The input stream.
815 /// \param g The graph.
816 template<typename Graph>
817 void readGraph(std::istream& is, Graph &g) {
818 GraphReader<Graph> reader(is, g);