1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2011
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 ///\brief \ref lgf-format "LEMON Graph Format" reader.
24 #ifndef LEMON_LGF_READER_H
25 #define LEMON_LGF_READER_H
34 #include <lemon/core.h>
36 #include <lemon/lgf_writer.h>
38 #include <lemon/concept_check.h>
39 #include <lemon/concepts/maps.h>
43 namespace _reader_bits {
45 template <typename Value>
46 struct DefaultConverter {
47 Value operator()(const std::string& str) {
48 std::istringstream is(str);
51 throw FormatError("Cannot read token");
55 if (is >> std::ws >> c) {
56 throw FormatError("Remaining characters in token");
63 struct DefaultConverter<std::string> {
64 std::string operator()(const std::string& str) {
69 template <typename _Item>
70 class MapStorageBase {
76 virtual ~MapStorageBase() {}
78 virtual void set(const Item& item, const std::string& value) = 0;
82 template <typename _Item, typename _Map,
83 typename _Converter = DefaultConverter<typename _Map::Value> >
84 class MapStorage : public MapStorageBase<_Item> {
87 typedef _Converter Converter;
95 MapStorage(Map& map, const Converter& converter = Converter())
96 : _map(map), _converter(converter) {}
97 virtual ~MapStorage() {}
99 virtual void set(const Item& item ,const std::string& value) {
100 _map.set(item, _converter(value));
104 template <typename _Graph, bool _dir, typename _Map,
105 typename _Converter = DefaultConverter<typename _Map::Value> >
106 class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
109 typedef _Converter Converter;
110 typedef _Graph Graph;
111 typedef typename Graph::Edge Item;
112 static const bool dir = _dir;
117 Converter _converter;
120 GraphArcMapStorage(const Graph& graph, Map& map,
121 const Converter& converter = Converter())
122 : _graph(graph), _map(map), _converter(converter) {}
123 virtual ~GraphArcMapStorage() {}
125 virtual void set(const Item& item ,const std::string& value) {
126 _map.set(_graph.direct(item, dir), _converter(value));
130 class ValueStorageBase {
132 ValueStorageBase() {}
133 virtual ~ValueStorageBase() {}
135 virtual void set(const std::string&) = 0;
138 template <typename _Value, typename _Converter = DefaultConverter<_Value> >
139 class ValueStorage : public ValueStorageBase {
141 typedef _Value Value;
142 typedef _Converter Converter;
146 Converter _converter;
149 ValueStorage(Value& value, const Converter& converter = Converter())
150 : _value(value), _converter(converter) {}
152 virtual void set(const std::string& value) {
153 _value = _converter(value);
157 template <typename Value>
158 struct MapLookUpConverter {
159 const std::map<std::string, Value>& _map;
161 MapLookUpConverter(const std::map<std::string, Value>& map)
164 Value operator()(const std::string& str) {
165 typename std::map<std::string, Value>::const_iterator it =
167 if (it == _map.end()) {
168 std::ostringstream msg;
169 msg << "Item not found: " << str;
170 throw FormatError(msg.str());
176 template <typename Graph>
177 struct GraphArcLookUpConverter {
179 const std::map<std::string, typename Graph::Edge>& _map;
181 GraphArcLookUpConverter(const Graph& graph,
182 const std::map<std::string,
183 typename Graph::Edge>& map)
184 : _graph(graph), _map(map) {}
186 typename Graph::Arc operator()(const std::string& str) {
187 if (str.empty() || (str[0] != '+' && str[0] != '-')) {
188 throw FormatError("Item must start with '+' or '-'");
190 typename std::map<std::string, typename Graph::Edge>
191 ::const_iterator it = _map.find(str.substr(1));
192 if (it == _map.end()) {
193 throw FormatError("Item not found");
195 return _graph.direct(it->second, str[0] == '+');
199 inline bool isWhiteSpace(char c) {
200 return c == ' ' || c == '\t' || c == '\v' ||
201 c == '\n' || c == '\r' || c == '\f';
204 inline bool isOct(char c) {
205 return '0' <= c && c <='7';
208 inline int valueOct(char c) {
209 LEMON_ASSERT(isOct(c), "The character is not octal.");
213 inline bool isHex(char c) {
214 return ('0' <= c && c <= '9') ||
215 ('a' <= c && c <= 'z') ||
216 ('A' <= c && c <= 'Z');
219 inline int valueHex(char c) {
220 LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
221 if ('0' <= c && c <= '9') return c - '0';
222 if ('a' <= c && c <= 'z') return c - 'a' + 10;
226 inline bool isIdentifierFirstChar(char c) {
227 return ('a' <= c && c <= 'z') ||
228 ('A' <= c && c <= 'Z') || c == '_';
231 inline bool isIdentifierChar(char c) {
232 return isIdentifierFirstChar(c) ||
233 ('0' <= c && c <= '9');
236 inline char readEscape(std::istream& is) {
239 throw FormatError("Escape format error");
267 if (!is.get(c) || !isHex(c))
268 throw FormatError("Escape format error");
269 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
270 else code = code * 16 + valueHex(c);
277 throw FormatError("Escape format error");
278 else if (code = valueOct(c), !is.get(c) || !isOct(c))
280 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
282 else code = code * 8 + valueOct(c);
288 inline std::istream& readToken(std::istream& is, std::string& str) {
289 std::ostringstream os;
298 while (is.get(c) && c != '\"') {
304 throw FormatError("Quoted format error");
307 while (is.get(c) && !isWhiteSpace(c)) {
324 virtual ~Section() {}
325 virtual void process(std::istream& is, int& line_num) = 0;
328 template <typename Functor>
329 class LineSection : public Section {
336 LineSection(const Functor& functor) : _functor(functor) {}
337 virtual ~LineSection() {}
339 virtual void process(std::istream& is, int& line_num) {
342 while (is.get(c) && c != '@') {
345 } else if (c == '#') {
348 } else if (!isWhiteSpace(c)) {
355 if (is) is.putback(c);
356 else if (is.eof()) is.clear();
360 template <typename Functor>
361 class StreamSection : public Section {
368 StreamSection(const Functor& functor) : _functor(functor) {}
369 virtual ~StreamSection() {}
371 virtual void process(std::istream& is, int& line_num) {
372 _functor(is, line_num);
375 while (is.get(c) && c != '@') {
378 } else if (!isWhiteSpace(c)) {
383 if (is) is.putback(c);
384 else if (is.eof()) is.clear();
390 template <typename Digraph>
393 template <typename Digraph>
394 DigraphReader<Digraph> digraphReader(Digraph& digraph,
395 std::istream& is = std::cin);
396 template <typename Digraph>
397 DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
398 template <typename Digraph>
399 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
401 /// \ingroup lemon_io
403 /// \brief \ref lgf-format "LGF" reader for directed graphs
405 /// This utility reads an \ref lgf-format "LGF" file.
407 /// The reading method does a batch processing. The user creates a
408 /// reader object, then various reading rules can be added to the
409 /// reader, and eventually the reading is executed with the \c run()
410 /// member function. A map reading rule can be added to the reader
411 /// with the \c nodeMap() or \c arcMap() members. An optional
412 /// converter parameter can also be added as a standard functor
413 /// converting from \c std::string to the value type of the map. If it
414 /// is set, it will determine how the tokens in the file should be
415 /// converted to the value type of the map. If the functor is not set,
416 /// then a default conversion will be used. One map can be read into
417 /// multiple map objects at the same time. The \c attribute(), \c
418 /// node() and \c arc() functions are used to add attribute reading
422 /// DigraphReader<Digraph>(digraph, std::cin).
423 /// nodeMap("coordinates", coord_map).
424 /// arcMap("capacity", cap_map).
425 /// node("source", src).
426 /// node("target", trg).
427 /// attribute("caption", caption).
431 /// By default the reader uses the first section in the file of the
432 /// proper type. If a section has an optional name, then it can be
433 /// selected for reading by giving an optional name parameter to the
434 /// \c nodes(), \c arcs() or \c attributes() functions.
436 /// The \c useNodes() and \c useArcs() functions are used to tell the reader
437 /// that the nodes or arcs should not be constructed (added to the
438 /// graph) during the reading, but instead the label map of the items
439 /// are given as a parameter of these functions. An
440 /// application of these functions is multipass reading, which is
441 /// important if two \c \@arcs sections must be read from the
442 /// file. In this case the first phase would read the node set and one
443 /// of the arc sets, while the second phase would read the second arc
444 /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
445 /// The previously read label node map should be passed to the \c
446 /// useNodes() functions. Another application of multipass reading when
447 /// paths are given as a node map or an arc map.
448 /// It is impossible to read this in
449 /// a single pass, because the arcs are not constructed when the node
451 template <typename _Digraph>
452 class DigraphReader {
455 typedef _Digraph Digraph;
456 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
463 std::string _filename;
467 std::string _nodes_caption;
468 std::string _arcs_caption;
469 std::string _attributes_caption;
471 typedef std::map<std::string, Node> NodeIndex;
472 NodeIndex _node_index;
473 typedef std::map<std::string, Arc> ArcIndex;
476 typedef std::vector<std::pair<std::string,
477 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
480 typedef std::vector<std::pair<std::string,
481 _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
484 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
486 Attributes _attributes;
495 std::istringstream line;
499 /// \brief Constructor
501 /// Construct a directed graph reader, which reads from the given
503 DigraphReader(Digraph& digraph, std::istream& is = std::cin)
504 : _is(&is), local_is(false), _digraph(digraph),
505 _use_nodes(false), _use_arcs(false),
506 _skip_nodes(false), _skip_arcs(false) {}
508 /// \brief Constructor
510 /// Construct a directed graph reader, which reads from the given
512 DigraphReader(Digraph& digraph, const std::string& fn)
513 : _is(new std::ifstream(fn.c_str())), local_is(true),
514 _filename(fn), _digraph(digraph),
515 _use_nodes(false), _use_arcs(false),
516 _skip_nodes(false), _skip_arcs(false) {
519 throw IoError("Cannot open file", fn);
523 /// \brief Constructor
525 /// Construct a directed graph reader, which reads from the given
527 DigraphReader(Digraph& digraph, const char* fn)
528 : _is(new std::ifstream(fn)), local_is(true),
529 _filename(fn), _digraph(digraph),
530 _use_nodes(false), _use_arcs(false),
531 _skip_nodes(false), _skip_arcs(false) {
534 throw IoError("Cannot open file", fn);
538 /// \brief Destructor
540 for (typename NodeMaps::iterator it = _node_maps.begin();
541 it != _node_maps.end(); ++it) {
545 for (typename ArcMaps::iterator it = _arc_maps.begin();
546 it != _arc_maps.end(); ++it) {
550 for (typename Attributes::iterator it = _attributes.begin();
551 it != _attributes.end(); ++it) {
563 template <typename DGR>
564 friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
565 template <typename DGR>
566 friend DigraphReader<DGR> digraphReader(DGR& digraph,
567 const std::string& fn);
568 template <typename DGR>
569 friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
571 DigraphReader(DigraphReader& other)
572 : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
573 _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
574 _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
577 other.local_is = false;
579 _node_index.swap(other._node_index);
580 _arc_index.swap(other._arc_index);
582 _node_maps.swap(other._node_maps);
583 _arc_maps.swap(other._arc_maps);
584 _attributes.swap(other._attributes);
586 _nodes_caption = other._nodes_caption;
587 _arcs_caption = other._arcs_caption;
588 _attributes_caption = other._attributes_caption;
592 DigraphReader& operator=(const DigraphReader&);
596 /// \name Reading rules
599 /// \brief Node map reading rule
601 /// Add a node map reading rule to the reader.
602 template <typename Map>
603 DigraphReader& nodeMap(const std::string& caption, Map& map) {
604 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
605 _reader_bits::MapStorageBase<Node>* storage =
606 new _reader_bits::MapStorage<Node, Map>(map);
607 _node_maps.push_back(std::make_pair(caption, storage));
611 /// \brief Node map reading rule
613 /// Add a node map reading rule with specialized converter to the
615 template <typename Map, typename Converter>
616 DigraphReader& nodeMap(const std::string& caption, Map& map,
617 const Converter& converter = Converter()) {
618 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
619 _reader_bits::MapStorageBase<Node>* storage =
620 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
621 _node_maps.push_back(std::make_pair(caption, storage));
625 /// \brief Arc map reading rule
627 /// Add an arc map reading rule to the reader.
628 template <typename Map>
629 DigraphReader& arcMap(const std::string& caption, Map& map) {
630 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
631 _reader_bits::MapStorageBase<Arc>* storage =
632 new _reader_bits::MapStorage<Arc, Map>(map);
633 _arc_maps.push_back(std::make_pair(caption, storage));
637 /// \brief Arc map reading rule
639 /// Add an arc map reading rule with specialized converter to the
641 template <typename Map, typename Converter>
642 DigraphReader& arcMap(const std::string& caption, Map& map,
643 const Converter& converter = Converter()) {
644 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
645 _reader_bits::MapStorageBase<Arc>* storage =
646 new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
647 _arc_maps.push_back(std::make_pair(caption, storage));
651 /// \brief Attribute reading rule
653 /// Add an attribute reading rule to the reader.
654 template <typename Value>
655 DigraphReader& attribute(const std::string& caption, Value& value) {
656 _reader_bits::ValueStorageBase* storage =
657 new _reader_bits::ValueStorage<Value>(value);
658 _attributes.insert(std::make_pair(caption, storage));
662 /// \brief Attribute reading rule
664 /// Add an attribute reading rule with specialized converter to the
666 template <typename Value, typename Converter>
667 DigraphReader& attribute(const std::string& caption, Value& value,
668 const Converter& converter = Converter()) {
669 _reader_bits::ValueStorageBase* storage =
670 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
671 _attributes.insert(std::make_pair(caption, storage));
675 /// \brief Node reading rule
677 /// Add a node reading rule to reader.
678 DigraphReader& node(const std::string& caption, Node& node) {
679 typedef _reader_bits::MapLookUpConverter<Node> Converter;
680 Converter converter(_node_index);
681 _reader_bits::ValueStorageBase* storage =
682 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
683 _attributes.insert(std::make_pair(caption, storage));
687 /// \brief Arc reading rule
689 /// Add an arc reading rule to reader.
690 DigraphReader& arc(const std::string& caption, Arc& arc) {
691 typedef _reader_bits::MapLookUpConverter<Arc> Converter;
692 Converter converter(_arc_index);
693 _reader_bits::ValueStorageBase* storage =
694 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
695 _attributes.insert(std::make_pair(caption, storage));
701 /// \name Select section by name
704 /// \brief Set \c \@nodes section to be read
706 /// Set \c \@nodes section to be read
707 DigraphReader& nodes(const std::string& caption) {
708 _nodes_caption = caption;
712 /// \brief Set \c \@arcs section to be read
714 /// Set \c \@arcs section to be read
715 DigraphReader& arcs(const std::string& caption) {
716 _arcs_caption = caption;
720 /// \brief Set \c \@attributes section to be read
722 /// Set \c \@attributes section to be read
723 DigraphReader& attributes(const std::string& caption) {
724 _attributes_caption = caption;
730 /// \name Using previously constructed node or arc set
733 /// \brief Use previously constructed node set
735 /// Use previously constructed node set, and specify the node
737 template <typename Map>
738 DigraphReader& useNodes(const Map& map) {
739 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
740 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
742 _writer_bits::DefaultConverter<typename Map::Value> converter;
743 for (NodeIt n(_digraph); n != INVALID; ++n) {
744 _node_index.insert(std::make_pair(converter(map[n]), n));
749 /// \brief Use previously constructed node set
751 /// Use previously constructed node set, and specify the node
752 /// label map and a functor which converts the label map values to
754 template <typename Map, typename Converter>
755 DigraphReader& useNodes(const Map& map,
756 const Converter& converter = Converter()) {
757 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
758 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
760 for (NodeIt n(_digraph); n != INVALID; ++n) {
761 _node_index.insert(std::make_pair(converter(map[n]), n));
766 /// \brief Use previously constructed arc set
768 /// Use previously constructed arc set, and specify the arc
770 template <typename Map>
771 DigraphReader& useArcs(const Map& map) {
772 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
773 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
775 _writer_bits::DefaultConverter<typename Map::Value> converter;
776 for (ArcIt a(_digraph); a != INVALID; ++a) {
777 _arc_index.insert(std::make_pair(converter(map[a]), a));
782 /// \brief Use previously constructed arc set
784 /// Use previously constructed arc set, and specify the arc
785 /// label map and a functor which converts the label map values to
787 template <typename Map, typename Converter>
788 DigraphReader& useArcs(const Map& map,
789 const Converter& converter = Converter()) {
790 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
791 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
793 for (ArcIt a(_digraph); a != INVALID; ++a) {
794 _arc_index.insert(std::make_pair(converter(map[a]), a));
799 /// \brief Skips the reading of node section
801 /// Omit the reading of the node section. This implies that each node
802 /// map reading rule will be abandoned, and the nodes of the graph
803 /// will not be constructed, which usually cause that the arc set
804 /// could not be read due to lack of node name resolving.
805 /// Therefore \c skipArcs() function should also be used, or
806 /// \c useNodes() should be used to specify the label of the nodes.
807 DigraphReader& skipNodes() {
808 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
813 /// \brief Skips the reading of arc section
815 /// Omit the reading of the arc section. This implies that each arc
816 /// map reading rule will be abandoned, and the arcs of the graph
817 /// will not be constructed.
818 DigraphReader& skipArcs() {
819 LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
830 while(++line_num, std::getline(*_is, str)) {
831 line.clear(); line.str(str);
833 if (line >> std::ws >> c && c != '#') {
842 return static_cast<bool>(*_is);
847 while (readSuccess() && line >> c && c != '@') {
857 std::vector<int> map_index(_node_maps.size());
858 int map_num, label_index;
861 if (!readLine() || !(line >> c) || c == '@') {
862 if (readSuccess() && line) line.putback(c);
863 if (!_node_maps.empty())
864 throw FormatError("Cannot find map names");
870 std::map<std::string, int> maps;
874 while (_reader_bits::readToken(line, map)) {
875 if (maps.find(map) != maps.end()) {
876 std::ostringstream msg;
877 msg << "Multiple occurence of node map: " << map;
878 throw FormatError(msg.str());
880 maps.insert(std::make_pair(map, index));
884 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
885 std::map<std::string, int>::iterator jt =
886 maps.find(_node_maps[i].first);
887 if (jt == maps.end()) {
888 std::ostringstream msg;
889 msg << "Map not found: " << _node_maps[i].first;
890 throw FormatError(msg.str());
892 map_index[i] = jt->second;
896 std::map<std::string, int>::iterator jt = maps.find("label");
897 if (jt != maps.end()) {
898 label_index = jt->second;
903 map_num = maps.size();
906 while (readLine() && line >> c && c != '@') {
909 std::vector<std::string> tokens(map_num);
910 for (int i = 0; i < map_num; ++i) {
911 if (!_reader_bits::readToken(line, tokens[i])) {
912 std::ostringstream msg;
913 msg << "Column not found (" << i + 1 << ")";
914 throw FormatError(msg.str());
917 if (line >> std::ws >> c)
918 throw FormatError("Extra character at the end of line");
922 n = _digraph.addNode();
923 if (label_index != -1)
924 _node_index.insert(std::make_pair(tokens[label_index], n));
926 if (label_index == -1)
927 throw FormatError("Label map not found");
928 typename std::map<std::string, Node>::iterator it =
929 _node_index.find(tokens[label_index]);
930 if (it == _node_index.end()) {
931 std::ostringstream msg;
932 msg << "Node with label not found: " << tokens[label_index];
933 throw FormatError(msg.str());
938 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
939 _node_maps[i].second->set(n, tokens[map_index[i]]);
950 std::vector<int> map_index(_arc_maps.size());
951 int map_num, label_index;
954 if (!readLine() || !(line >> c) || c == '@') {
955 if (readSuccess() && line) line.putback(c);
956 if (!_arc_maps.empty())
957 throw FormatError("Cannot find map names");
963 std::map<std::string, int> maps;
967 while (_reader_bits::readToken(line, map)) {
970 throw FormatError("'-' is not allowed as a map name");
971 else if (line >> std::ws >> c)
972 throw FormatError("Extra character at the end of line");
975 if (maps.find(map) != maps.end()) {
976 std::ostringstream msg;
977 msg << "Multiple occurence of arc map: " << map;
978 throw FormatError(msg.str());
980 maps.insert(std::make_pair(map, index));
984 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
985 std::map<std::string, int>::iterator jt =
986 maps.find(_arc_maps[i].first);
987 if (jt == maps.end()) {
988 std::ostringstream msg;
989 msg << "Map not found: " << _arc_maps[i].first;
990 throw FormatError(msg.str());
992 map_index[i] = jt->second;
996 std::map<std::string, int>::iterator jt = maps.find("label");
997 if (jt != maps.end()) {
998 label_index = jt->second;
1003 map_num = maps.size();
1006 while (readLine() && line >> c && c != '@') {
1009 std::string source_token;
1010 std::string target_token;
1012 if (!_reader_bits::readToken(line, source_token))
1013 throw FormatError("Source not found");
1015 if (!_reader_bits::readToken(line, target_token))
1016 throw FormatError("Target not found");
1018 std::vector<std::string> tokens(map_num);
1019 for (int i = 0; i < map_num; ++i) {
1020 if (!_reader_bits::readToken(line, tokens[i])) {
1021 std::ostringstream msg;
1022 msg << "Column not found (" << i + 1 << ")";
1023 throw FormatError(msg.str());
1026 if (line >> std::ws >> c)
1027 throw FormatError("Extra character at the end of line");
1032 typename NodeIndex::iterator it;
1034 it = _node_index.find(source_token);
1035 if (it == _node_index.end()) {
1036 std::ostringstream msg;
1037 msg << "Item not found: " << source_token;
1038 throw FormatError(msg.str());
1040 Node source = it->second;
1042 it = _node_index.find(target_token);
1043 if (it == _node_index.end()) {
1044 std::ostringstream msg;
1045 msg << "Item not found: " << target_token;
1046 throw FormatError(msg.str());
1048 Node target = it->second;
1050 a = _digraph.addArc(source, target);
1051 if (label_index != -1)
1052 _arc_index.insert(std::make_pair(tokens[label_index], a));
1054 if (label_index == -1)
1055 throw FormatError("Label map not found");
1056 typename std::map<std::string, Arc>::iterator it =
1057 _arc_index.find(tokens[label_index]);
1058 if (it == _arc_index.end()) {
1059 std::ostringstream msg;
1060 msg << "Arc with label not found: " << tokens[label_index];
1061 throw FormatError(msg.str());
1066 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1067 _arc_maps[i].second->set(a, tokens[map_index[i]]);
1071 if (readSuccess()) {
1076 void readAttributes() {
1078 std::set<std::string> read_attr;
1081 while (readLine() && line >> c && c != '@') {
1084 std::string attr, token;
1085 if (!_reader_bits::readToken(line, attr))
1086 throw FormatError("Attribute name not found");
1087 if (!_reader_bits::readToken(line, token))
1088 throw FormatError("Attribute value not found");
1090 throw FormatError("Extra character at the end of line");
1093 std::set<std::string>::iterator it = read_attr.find(attr);
1094 if (it != read_attr.end()) {
1095 std::ostringstream msg;
1096 msg << "Multiple occurence of attribute: " << attr;
1097 throw FormatError(msg.str());
1099 read_attr.insert(attr);
1103 typename Attributes::iterator it = _attributes.lower_bound(attr);
1104 while (it != _attributes.end() && it->first == attr) {
1105 it->second->set(token);
1111 if (readSuccess()) {
1114 for (typename Attributes::iterator it = _attributes.begin();
1115 it != _attributes.end(); ++it) {
1116 if (read_attr.find(it->first) == read_attr.end()) {
1117 std::ostringstream msg;
1118 msg << "Attribute not found: " << it->first;
1119 throw FormatError(msg.str());
1126 /// \name Execution of the reader
1129 /// \brief Start the batch processing
1131 /// This function starts the batch processing
1133 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1135 bool nodes_done = _skip_nodes;
1136 bool arcs_done = _skip_arcs;
1137 bool attributes_done = false;
1143 while (readSuccess()) {
1146 std::string section, caption;
1148 _reader_bits::readToken(line, section);
1149 _reader_bits::readToken(line, caption);
1152 throw FormatError("Extra character at the end of line");
1154 if (section == "nodes" && !nodes_done) {
1155 if (_nodes_caption.empty() || _nodes_caption == caption) {
1159 } else if ((section == "arcs" || section == "edges") &&
1161 if (_arcs_caption.empty() || _arcs_caption == caption) {
1165 } else if (section == "attributes" && !attributes_done) {
1166 if (_attributes_caption.empty() || _attributes_caption == caption) {
1168 attributes_done = true;
1174 } catch (FormatError& error) {
1175 error.line(line_num);
1176 error.file(_filename);
1182 throw FormatError("Section @nodes not found");
1186 throw FormatError("Section @arcs not found");
1189 if (!attributes_done && !_attributes.empty()) {
1190 throw FormatError("Section @attributes not found");
1199 /// \brief Return a \ref DigraphReader class
1201 /// This function just returns a \ref DigraphReader class.
1202 /// \relates DigraphReader
1203 template <typename Digraph>
1204 DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
1205 DigraphReader<Digraph> tmp(digraph, is);
1209 /// \brief Return a \ref DigraphReader class
1211 /// This function just returns a \ref DigraphReader class.
1212 /// \relates DigraphReader
1213 template <typename Digraph>
1214 DigraphReader<Digraph> digraphReader(Digraph& digraph,
1215 const std::string& fn) {
1216 DigraphReader<Digraph> tmp(digraph, fn);
1220 /// \brief Return a \ref DigraphReader class
1222 /// This function just returns a \ref DigraphReader class.
1223 /// \relates DigraphReader
1224 template <typename Digraph>
1225 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
1226 DigraphReader<Digraph> tmp(digraph, fn);
1230 template <typename Graph>
1233 template <typename Graph>
1234 GraphReader<Graph> graphReader(Graph& graph,
1235 std::istream& is = std::cin);
1236 template <typename Graph>
1237 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
1238 template <typename Graph>
1239 GraphReader<Graph> graphReader(Graph& graph, const char *fn);
1241 /// \ingroup lemon_io
1243 /// \brief \ref lgf-format "LGF" reader for undirected graphs
1245 /// This utility reads an \ref lgf-format "LGF" file.
1247 /// It can be used almost the same way as \c DigraphReader.
1248 /// The only difference is that this class can handle edges and
1249 /// edge maps as well as arcs and arc maps.
1251 /// The columns in the \c \@edges (or \c \@arcs) section are the
1252 /// edge maps. However, if there are two maps with the same name
1253 /// prefixed with \c '+' and \c '-', then these can be read into an
1254 /// arc map. Similarly, an attribute can be read into an arc, if
1255 /// it's value is an edge label prefixed with \c '+' or \c '-'.
1256 template <typename _Graph>
1260 typedef _Graph Graph;
1261 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1267 std::string _filename;
1271 std::string _nodes_caption;
1272 std::string _edges_caption;
1273 std::string _attributes_caption;
1275 typedef std::map<std::string, Node> NodeIndex;
1276 NodeIndex _node_index;
1277 typedef std::map<std::string, Edge> EdgeIndex;
1278 EdgeIndex _edge_index;
1280 typedef std::vector<std::pair<std::string,
1281 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
1282 NodeMaps _node_maps;
1284 typedef std::vector<std::pair<std::string,
1285 _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1286 EdgeMaps _edge_maps;
1288 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1290 Attributes _attributes;
1299 std::istringstream line;
1303 /// \brief Constructor
1305 /// Construct an undirected graph reader, which reads from the given
1307 GraphReader(Graph& graph, std::istream& is = std::cin)
1308 : _is(&is), local_is(false), _graph(graph),
1309 _use_nodes(false), _use_edges(false),
1310 _skip_nodes(false), _skip_edges(false) {}
1312 /// \brief Constructor
1314 /// Construct an undirected graph reader, which reads from the given
1316 GraphReader(Graph& graph, const std::string& fn)
1317 : _is(new std::ifstream(fn.c_str())), local_is(true),
1318 _filename(fn), _graph(graph),
1319 _use_nodes(false), _use_edges(false),
1320 _skip_nodes(false), _skip_edges(false) {
1323 throw IoError("Cannot open file", fn);
1327 /// \brief Constructor
1329 /// Construct an undirected graph reader, which reads from the given
1331 GraphReader(Graph& graph, const char* fn)
1332 : _is(new std::ifstream(fn)), local_is(true),
1333 _filename(fn), _graph(graph),
1334 _use_nodes(false), _use_edges(false),
1335 _skip_nodes(false), _skip_edges(false) {
1338 throw IoError("Cannot open file", fn);
1342 /// \brief Destructor
1344 for (typename NodeMaps::iterator it = _node_maps.begin();
1345 it != _node_maps.end(); ++it) {
1349 for (typename EdgeMaps::iterator it = _edge_maps.begin();
1350 it != _edge_maps.end(); ++it) {
1354 for (typename Attributes::iterator it = _attributes.begin();
1355 it != _attributes.end(); ++it) {
1366 template <typename GR>
1367 friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
1368 template <typename GR>
1369 friend GraphReader<GR> graphReader(GR& graph, const std::string& fn);
1370 template <typename GR>
1371 friend GraphReader<GR> graphReader(GR& graph, const char *fn);
1373 GraphReader(GraphReader& other)
1374 : _is(other._is), local_is(other.local_is), _graph(other._graph),
1375 _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1376 _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1379 other.local_is = false;
1381 _node_index.swap(other._node_index);
1382 _edge_index.swap(other._edge_index);
1384 _node_maps.swap(other._node_maps);
1385 _edge_maps.swap(other._edge_maps);
1386 _attributes.swap(other._attributes);
1388 _nodes_caption = other._nodes_caption;
1389 _edges_caption = other._edges_caption;
1390 _attributes_caption = other._attributes_caption;
1394 GraphReader& operator=(const GraphReader&);
1398 /// \name Reading rules
1401 /// \brief Node map reading rule
1403 /// Add a node map reading rule to the reader.
1404 template <typename Map>
1405 GraphReader& nodeMap(const std::string& caption, Map& map) {
1406 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1407 _reader_bits::MapStorageBase<Node>* storage =
1408 new _reader_bits::MapStorage<Node, Map>(map);
1409 _node_maps.push_back(std::make_pair(caption, storage));
1413 /// \brief Node map reading rule
1415 /// Add a node map reading rule with specialized converter to the
1417 template <typename Map, typename Converter>
1418 GraphReader& nodeMap(const std::string& caption, Map& map,
1419 const Converter& converter = Converter()) {
1420 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1421 _reader_bits::MapStorageBase<Node>* storage =
1422 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1423 _node_maps.push_back(std::make_pair(caption, storage));
1427 /// \brief Edge map reading rule
1429 /// Add an edge map reading rule to the reader.
1430 template <typename Map>
1431 GraphReader& edgeMap(const std::string& caption, Map& map) {
1432 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1433 _reader_bits::MapStorageBase<Edge>* storage =
1434 new _reader_bits::MapStorage<Edge, Map>(map);
1435 _edge_maps.push_back(std::make_pair(caption, storage));
1439 /// \brief Edge map reading rule
1441 /// Add an edge map reading rule with specialized converter to the
1443 template <typename Map, typename Converter>
1444 GraphReader& edgeMap(const std::string& caption, Map& map,
1445 const Converter& converter = Converter()) {
1446 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1447 _reader_bits::MapStorageBase<Edge>* storage =
1448 new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1449 _edge_maps.push_back(std::make_pair(caption, storage));
1453 /// \brief Arc map reading rule
1455 /// Add an arc map reading rule to the reader.
1456 template <typename Map>
1457 GraphReader& arcMap(const std::string& caption, Map& map) {
1458 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1459 _reader_bits::MapStorageBase<Edge>* forward_storage =
1460 new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1461 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1462 _reader_bits::MapStorageBase<Edge>* backward_storage =
1463 new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1464 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1468 /// \brief Arc map reading rule
1470 /// Add an arc map reading rule with specialized converter to the
1472 template <typename Map, typename Converter>
1473 GraphReader& arcMap(const std::string& caption, Map& map,
1474 const Converter& converter = Converter()) {
1475 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1476 _reader_bits::MapStorageBase<Edge>* forward_storage =
1477 new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1478 (_graph, map, converter);
1479 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1480 _reader_bits::MapStorageBase<Edge>* backward_storage =
1481 new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1482 (_graph, map, converter);
1483 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1487 /// \brief Attribute reading rule
1489 /// Add an attribute reading rule to the reader.
1490 template <typename Value>
1491 GraphReader& attribute(const std::string& caption, Value& value) {
1492 _reader_bits::ValueStorageBase* storage =
1493 new _reader_bits::ValueStorage<Value>(value);
1494 _attributes.insert(std::make_pair(caption, storage));
1498 /// \brief Attribute reading rule
1500 /// Add an attribute reading rule with specialized converter to the
1502 template <typename Value, typename Converter>
1503 GraphReader& attribute(const std::string& caption, Value& value,
1504 const Converter& converter = Converter()) {
1505 _reader_bits::ValueStorageBase* storage =
1506 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1507 _attributes.insert(std::make_pair(caption, storage));
1511 /// \brief Node reading rule
1513 /// Add a node reading rule to reader.
1514 GraphReader& node(const std::string& caption, Node& node) {
1515 typedef _reader_bits::MapLookUpConverter<Node> Converter;
1516 Converter converter(_node_index);
1517 _reader_bits::ValueStorageBase* storage =
1518 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1519 _attributes.insert(std::make_pair(caption, storage));
1523 /// \brief Edge reading rule
1525 /// Add an edge reading rule to reader.
1526 GraphReader& edge(const std::string& caption, Edge& edge) {
1527 typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1528 Converter converter(_edge_index);
1529 _reader_bits::ValueStorageBase* storage =
1530 new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1531 _attributes.insert(std::make_pair(caption, storage));
1535 /// \brief Arc reading rule
1537 /// Add an arc reading rule to reader.
1538 GraphReader& arc(const std::string& caption, Arc& arc) {
1539 typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
1540 Converter converter(_graph, _edge_index);
1541 _reader_bits::ValueStorageBase* storage =
1542 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1543 _attributes.insert(std::make_pair(caption, storage));
1549 /// \name Select section by name
1552 /// \brief Set \c \@nodes section to be read
1554 /// Set \c \@nodes section to be read.
1555 GraphReader& nodes(const std::string& caption) {
1556 _nodes_caption = caption;
1560 /// \brief Set \c \@edges section to be read
1562 /// Set \c \@edges section to be read.
1563 GraphReader& edges(const std::string& caption) {
1564 _edges_caption = caption;
1568 /// \brief Set \c \@attributes section to be read
1570 /// Set \c \@attributes section to be read.
1571 GraphReader& attributes(const std::string& caption) {
1572 _attributes_caption = caption;
1578 /// \name Using previously constructed node or edge set
1581 /// \brief Use previously constructed node set
1583 /// Use previously constructed node set, and specify the node
1585 template <typename Map>
1586 GraphReader& useNodes(const Map& map) {
1587 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1588 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1590 _writer_bits::DefaultConverter<typename Map::Value> converter;
1591 for (NodeIt n(_graph); n != INVALID; ++n) {
1592 _node_index.insert(std::make_pair(converter(map[n]), n));
1597 /// \brief Use previously constructed node set
1599 /// Use previously constructed node set, and specify the node
1600 /// label map and a functor which converts the label map values to
1602 template <typename Map, typename Converter>
1603 GraphReader& useNodes(const Map& map,
1604 const Converter& converter = Converter()) {
1605 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1606 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1608 for (NodeIt n(_graph); n != INVALID; ++n) {
1609 _node_index.insert(std::make_pair(converter(map[n]), n));
1614 /// \brief Use previously constructed edge set
1616 /// Use previously constructed edge set, and specify the edge
1618 template <typename Map>
1619 GraphReader& useEdges(const Map& map) {
1620 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1621 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1623 _writer_bits::DefaultConverter<typename Map::Value> converter;
1624 for (EdgeIt a(_graph); a != INVALID; ++a) {
1625 _edge_index.insert(std::make_pair(converter(map[a]), a));
1630 /// \brief Use previously constructed edge set
1632 /// Use previously constructed edge set, and specify the edge
1633 /// label map and a functor which converts the label map values to
1635 template <typename Map, typename Converter>
1636 GraphReader& useEdges(const Map& map,
1637 const Converter& converter = Converter()) {
1638 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1639 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1641 for (EdgeIt a(_graph); a != INVALID; ++a) {
1642 _edge_index.insert(std::make_pair(converter(map[a]), a));
1647 /// \brief Skip the reading of node section
1649 /// Omit the reading of the node section. This implies that each node
1650 /// map reading rule will be abandoned, and the nodes of the graph
1651 /// will not be constructed, which usually cause that the edge set
1652 /// could not be read due to lack of node name
1653 /// could not be read due to lack of node name resolving.
1654 /// Therefore \c skipEdges() function should also be used, or
1655 /// \c useNodes() should be used to specify the label of the nodes.
1656 GraphReader& skipNodes() {
1657 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1662 /// \brief Skip the reading of edge section
1664 /// Omit the reading of the edge section. This implies that each edge
1665 /// map reading rule will be abandoned, and the edges of the graph
1666 /// will not be constructed.
1667 GraphReader& skipEdges() {
1668 LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1679 while(++line_num, std::getline(*_is, str)) {
1680 line.clear(); line.str(str);
1682 if (line >> std::ws >> c && c != '#') {
1690 bool readSuccess() {
1691 return static_cast<bool>(*_is);
1694 void skipSection() {
1696 while (readSuccess() && line >> c && c != '@') {
1699 if (readSuccess()) {
1706 std::vector<int> map_index(_node_maps.size());
1707 int map_num, label_index;
1710 if (!readLine() || !(line >> c) || c == '@') {
1711 if (readSuccess() && line) line.putback(c);
1712 if (!_node_maps.empty())
1713 throw FormatError("Cannot find map names");
1719 std::map<std::string, int> maps;
1723 while (_reader_bits::readToken(line, map)) {
1724 if (maps.find(map) != maps.end()) {
1725 std::ostringstream msg;
1726 msg << "Multiple occurence of node map: " << map;
1727 throw FormatError(msg.str());
1729 maps.insert(std::make_pair(map, index));
1733 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1734 std::map<std::string, int>::iterator jt =
1735 maps.find(_node_maps[i].first);
1736 if (jt == maps.end()) {
1737 std::ostringstream msg;
1738 msg << "Map not found: " << _node_maps[i].first;
1739 throw FormatError(msg.str());
1741 map_index[i] = jt->second;
1745 std::map<std::string, int>::iterator jt = maps.find("label");
1746 if (jt != maps.end()) {
1747 label_index = jt->second;
1752 map_num = maps.size();
1755 while (readLine() && line >> c && c != '@') {
1758 std::vector<std::string> tokens(map_num);
1759 for (int i = 0; i < map_num; ++i) {
1760 if (!_reader_bits::readToken(line, tokens[i])) {
1761 std::ostringstream msg;
1762 msg << "Column not found (" << i + 1 << ")";
1763 throw FormatError(msg.str());
1766 if (line >> std::ws >> c)
1767 throw FormatError("Extra character at the end of line");
1771 n = _graph.addNode();
1772 if (label_index != -1)
1773 _node_index.insert(std::make_pair(tokens[label_index], n));
1775 if (label_index == -1)
1776 throw FormatError("Label map not found");
1777 typename std::map<std::string, Node>::iterator it =
1778 _node_index.find(tokens[label_index]);
1779 if (it == _node_index.end()) {
1780 std::ostringstream msg;
1781 msg << "Node with label not found: " << tokens[label_index];
1782 throw FormatError(msg.str());
1787 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1788 _node_maps[i].second->set(n, tokens[map_index[i]]);
1792 if (readSuccess()) {
1799 std::vector<int> map_index(_edge_maps.size());
1800 int map_num, label_index;
1803 if (!readLine() || !(line >> c) || c == '@') {
1804 if (readSuccess() && line) line.putback(c);
1805 if (!_edge_maps.empty())
1806 throw FormatError("Cannot find map names");
1812 std::map<std::string, int> maps;
1816 while (_reader_bits::readToken(line, map)) {
1819 throw FormatError("'-' is not allowed as a map name");
1820 else if (line >> std::ws >> c)
1821 throw FormatError("Extra character at the end of line");
1824 if (maps.find(map) != maps.end()) {
1825 std::ostringstream msg;
1826 msg << "Multiple occurence of edge map: " << map;
1827 throw FormatError(msg.str());
1829 maps.insert(std::make_pair(map, index));
1833 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1834 std::map<std::string, int>::iterator jt =
1835 maps.find(_edge_maps[i].first);
1836 if (jt == maps.end()) {
1837 std::ostringstream msg;
1838 msg << "Map not found: " << _edge_maps[i].first;
1839 throw FormatError(msg.str());
1841 map_index[i] = jt->second;
1845 std::map<std::string, int>::iterator jt = maps.find("label");
1846 if (jt != maps.end()) {
1847 label_index = jt->second;
1852 map_num = maps.size();
1855 while (readLine() && line >> c && c != '@') {
1858 std::string source_token;
1859 std::string target_token;
1861 if (!_reader_bits::readToken(line, source_token))
1862 throw FormatError("Node u not found");
1864 if (!_reader_bits::readToken(line, target_token))
1865 throw FormatError("Node v not found");
1867 std::vector<std::string> tokens(map_num);
1868 for (int i = 0; i < map_num; ++i) {
1869 if (!_reader_bits::readToken(line, tokens[i])) {
1870 std::ostringstream msg;
1871 msg << "Column not found (" << i + 1 << ")";
1872 throw FormatError(msg.str());
1875 if (line >> std::ws >> c)
1876 throw FormatError("Extra character at the end of line");
1881 typename NodeIndex::iterator it;
1883 it = _node_index.find(source_token);
1884 if (it == _node_index.end()) {
1885 std::ostringstream msg;
1886 msg << "Item not found: " << source_token;
1887 throw FormatError(msg.str());
1889 Node source = it->second;
1891 it = _node_index.find(target_token);
1892 if (it == _node_index.end()) {
1893 std::ostringstream msg;
1894 msg << "Item not found: " << target_token;
1895 throw FormatError(msg.str());
1897 Node target = it->second;
1899 e = _graph.addEdge(source, target);
1900 if (label_index != -1)
1901 _edge_index.insert(std::make_pair(tokens[label_index], e));
1903 if (label_index == -1)
1904 throw FormatError("Label map not found");
1905 typename std::map<std::string, Edge>::iterator it =
1906 _edge_index.find(tokens[label_index]);
1907 if (it == _edge_index.end()) {
1908 std::ostringstream msg;
1909 msg << "Edge with label not found: " << tokens[label_index];
1910 throw FormatError(msg.str());
1915 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1916 _edge_maps[i].second->set(e, tokens[map_index[i]]);
1920 if (readSuccess()) {
1925 void readAttributes() {
1927 std::set<std::string> read_attr;
1930 while (readLine() && line >> c && c != '@') {
1933 std::string attr, token;
1934 if (!_reader_bits::readToken(line, attr))
1935 throw FormatError("Attribute name not found");
1936 if (!_reader_bits::readToken(line, token))
1937 throw FormatError("Attribute value not found");
1939 throw FormatError("Extra character at the end of line");
1942 std::set<std::string>::iterator it = read_attr.find(attr);
1943 if (it != read_attr.end()) {
1944 std::ostringstream msg;
1945 msg << "Multiple occurence of attribute: " << attr;
1946 throw FormatError(msg.str());
1948 read_attr.insert(attr);
1952 typename Attributes::iterator it = _attributes.lower_bound(attr);
1953 while (it != _attributes.end() && it->first == attr) {
1954 it->second->set(token);
1960 if (readSuccess()) {
1963 for (typename Attributes::iterator it = _attributes.begin();
1964 it != _attributes.end(); ++it) {
1965 if (read_attr.find(it->first) == read_attr.end()) {
1966 std::ostringstream msg;
1967 msg << "Attribute not found: " << it->first;
1968 throw FormatError(msg.str());
1975 /// \name Execution of the reader
1978 /// \brief Start the batch processing
1980 /// This function starts the batch processing
1983 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1985 bool nodes_done = _skip_nodes;
1986 bool edges_done = _skip_edges;
1987 bool attributes_done = false;
1993 while (readSuccess()) {
1996 std::string section, caption;
1998 _reader_bits::readToken(line, section);
1999 _reader_bits::readToken(line, caption);
2002 throw FormatError("Extra character at the end of line");
2004 if (section == "nodes" && !nodes_done) {
2005 if (_nodes_caption.empty() || _nodes_caption == caption) {
2009 } else if ((section == "edges" || section == "arcs") &&
2011 if (_edges_caption.empty() || _edges_caption == caption) {
2015 } else if (section == "attributes" && !attributes_done) {
2016 if (_attributes_caption.empty() || _attributes_caption == caption) {
2018 attributes_done = true;
2024 } catch (FormatError& error) {
2025 error.line(line_num);
2026 error.file(_filename);
2032 throw FormatError("Section @nodes not found");
2036 throw FormatError("Section @edges not found");
2039 if (!attributes_done && !_attributes.empty()) {
2040 throw FormatError("Section @attributes not found");
2049 /// \brief Return a \ref GraphReader class
2051 /// This function just returns a \ref GraphReader class.
2052 /// \relates GraphReader
2053 template <typename Graph>
2054 GraphReader<Graph> graphReader(Graph& graph, std::istream& is) {
2055 GraphReader<Graph> tmp(graph, is);
2059 /// \brief Return a \ref GraphReader class
2061 /// This function just returns a \ref GraphReader class.
2062 /// \relates GraphReader
2063 template <typename Graph>
2064 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
2065 GraphReader<Graph> tmp(graph, fn);
2069 /// \brief Return a \ref GraphReader class
2071 /// This function just returns a \ref GraphReader class.
2072 /// \relates GraphReader
2073 template <typename Graph>
2074 GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
2075 GraphReader<Graph> tmp(graph, fn);
2079 class SectionReader;
2081 SectionReader sectionReader(std::istream& is);
2082 SectionReader sectionReader(const std::string& fn);
2083 SectionReader sectionReader(const char* fn);
2085 /// \ingroup lemon_io
2087 /// \brief Section reader class
2089 /// In the \ref lgf-format "LGF" file extra sections can be placed,
2090 /// which contain any data in arbitrary format. Such sections can be
2091 /// read with this class. A reading rule can be added to the class
2092 /// with two different functions. With the \c sectionLines() function a
2093 /// functor can process the section line-by-line, while with the \c
2094 /// sectionStream() member the section can be read from an input
2096 class SectionReader {
2101 std::string _filename;
2103 typedef std::map<std::string, _reader_bits::Section*> Sections;
2107 std::istringstream line;
2111 /// \brief Constructor
2113 /// Construct a section reader, which reads from the given input
2115 SectionReader(std::istream& is)
2116 : _is(&is), local_is(false) {}
2118 /// \brief Constructor
2120 /// Construct a section reader, which reads from the given file.
2121 SectionReader(const std::string& fn)
2122 : _is(new std::ifstream(fn.c_str())), local_is(true),
2126 throw IoError("Cannot open file", fn);
2130 /// \brief Constructor
2132 /// Construct a section reader, which reads from the given file.
2133 SectionReader(const char* fn)
2134 : _is(new std::ifstream(fn)), local_is(true),
2138 throw IoError("Cannot open file", fn);
2142 /// \brief Destructor
2144 for (Sections::iterator it = _sections.begin();
2145 it != _sections.end(); ++it) {
2157 friend SectionReader sectionReader(std::istream& is);
2158 friend SectionReader sectionReader(const std::string& fn);
2159 friend SectionReader sectionReader(const char* fn);
2161 SectionReader(SectionReader& other)
2162 : _is(other._is), local_is(other.local_is) {
2165 other.local_is = false;
2167 _sections.swap(other._sections);
2170 SectionReader& operator=(const SectionReader&);
2174 /// \name Section readers
2177 /// \brief Add a section processor with line oriented reading
2179 /// The first parameter is the type descriptor of the section, the
2180 /// second is a functor, which takes just one \c std::string
2181 /// parameter. At the reading process, each line of the section
2182 /// will be given to the functor object. However, the empty lines
2183 /// and the comment lines are filtered out, and the leading
2184 /// whitespaces are trimmed from each processed string.
2186 /// For example let's see a section, which contain several
2187 /// integers, which should be inserted into a vector.
2195 /// The functor is implemented as a struct:
2197 /// struct NumberSection {
2198 /// std::vector<int>& _data;
2199 /// NumberSection(std::vector<int>& data) : _data(data) {}
2200 /// void operator()(const std::string& line) {
2201 /// std::istringstream ls(line);
2203 /// while (ls >> value) _data.push_back(value);
2209 /// reader.sectionLines("numbers", NumberSection(vec));
2211 template <typename Functor>
2212 SectionReader& sectionLines(const std::string& type, Functor functor) {
2213 LEMON_ASSERT(!type.empty(), "Type is empty.");
2214 LEMON_ASSERT(_sections.find(type) == _sections.end(),
2215 "Multiple reading of section.");
2216 _sections.insert(std::make_pair(type,
2217 new _reader_bits::LineSection<Functor>(functor)));
2222 /// \brief Add a section processor with stream oriented reading
2224 /// The first parameter is the type of the section, the second is
2225 /// a functor, which takes an \c std::istream& and an \c int&
2226 /// parameter, the latter regard to the line number of stream. The
2227 /// functor can read the input while the section go on, and the
2228 /// line number should be modified accordingly.
2229 template <typename Functor>
2230 SectionReader& sectionStream(const std::string& type, Functor functor) {
2231 LEMON_ASSERT(!type.empty(), "Type is empty.");
2232 LEMON_ASSERT(_sections.find(type) == _sections.end(),
2233 "Multiple reading of section.");
2234 _sections.insert(std::make_pair(type,
2235 new _reader_bits::StreamSection<Functor>(functor)));
2245 while(++line_num, std::getline(*_is, str)) {
2246 line.clear(); line.str(str);
2248 if (line >> std::ws >> c && c != '#') {
2256 bool readSuccess() {
2257 return static_cast<bool>(*_is);
2260 void skipSection() {
2262 while (readSuccess() && line >> c && c != '@') {
2265 if (readSuccess()) {
2273 /// \name Execution of the reader
2276 /// \brief Start the batch processing
2278 /// This function starts the batch processing.
2281 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2283 std::set<std::string> extra_sections;
2289 while (readSuccess()) {
2292 std::string section, caption;
2294 _reader_bits::readToken(line, section);
2295 _reader_bits::readToken(line, caption);
2298 throw FormatError("Extra character at the end of line");
2300 if (extra_sections.find(section) != extra_sections.end()) {
2301 std::ostringstream msg;
2302 msg << "Multiple occurence of section: " << section;
2303 throw FormatError(msg.str());
2305 Sections::iterator it = _sections.find(section);
2306 if (it != _sections.end()) {
2307 extra_sections.insert(section);
2308 it->second->process(*_is, line_num);
2312 } catch (FormatError& error) {
2313 error.line(line_num);
2314 error.file(_filename);
2318 for (Sections::iterator it = _sections.begin();
2319 it != _sections.end(); ++it) {
2320 if (extra_sections.find(it->first) == extra_sections.end()) {
2321 std::ostringstream os;
2322 os << "Cannot find section: " << it->first;
2323 throw FormatError(os.str());
2332 /// \brief Return a \ref SectionReader class
2334 /// This function just returns a \ref SectionReader class.
2335 /// \relates SectionReader
2336 inline SectionReader sectionReader(std::istream& is) {
2337 SectionReader tmp(is);
2341 /// \brief Return a \ref SectionReader class
2343 /// This function just returns a \ref SectionReader class.
2344 /// \relates SectionReader
2345 inline SectionReader sectionReader(const std::string& fn) {
2346 SectionReader tmp(fn);
2350 /// \brief Return a \ref SectionReader class
2352 /// This function just returns a \ref SectionReader class.
2353 /// \relates SectionReader
2354 inline SectionReader sectionReader(const char* fn) {
2355 SectionReader tmp(fn);
2359 /// \ingroup lemon_io
2361 /// \brief Reader for the contents of the \ref lgf-format "LGF" file
2363 /// This class can be used to read the sections, the map names and
2364 /// the attributes from a file. Usually, the LEMON programs know
2365 /// that, which type of graph, which maps and which attributes
2366 /// should be read from a file, but in general tools (like glemon)
2367 /// the contents of an LGF file should be guessed somehow. This class
2368 /// reads the graph and stores the appropriate information for
2369 /// reading the graph.
2372 /// LgfContents contents("graph.lgf");
2375 /// // Does it contain any node section and arc section?
2376 /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
2377 /// std::cerr << "Failure, cannot find graph." << std::endl;
2380 /// std::cout << "The name of the default node section: "
2381 /// << contents.nodeSection(0) << std::endl;
2382 /// std::cout << "The number of the arc maps: "
2383 /// << contents.arcMaps(0).size() << std::endl;
2384 /// std::cout << "The name of second arc map: "
2385 /// << contents.arcMaps(0)[1] << std::endl;
2393 std::vector<std::string> _node_sections;
2394 std::vector<std::string> _edge_sections;
2395 std::vector<std::string> _attribute_sections;
2396 std::vector<std::string> _extra_sections;
2398 std::vector<bool> _arc_sections;
2400 std::vector<std::vector<std::string> > _node_maps;
2401 std::vector<std::vector<std::string> > _edge_maps;
2403 std::vector<std::vector<std::string> > _attributes;
2407 std::istringstream line;
2411 /// \brief Constructor
2413 /// Construct an \e LGF contents reader, which reads from the given
2415 LgfContents(std::istream& is)
2416 : _is(&is), local_is(false) {}
2418 /// \brief Constructor
2420 /// Construct an \e LGF contents reader, which reads from the given
2422 LgfContents(const std::string& fn)
2423 : _is(new std::ifstream(fn.c_str())), local_is(true) {
2426 throw IoError("Cannot open file", fn);
2430 /// \brief Constructor
2432 /// Construct an \e LGF contents reader, which reads from the given
2434 LgfContents(const char* fn)
2435 : _is(new std::ifstream(fn)), local_is(true) {
2438 throw IoError("Cannot open file", fn);
2442 /// \brief Destructor
2444 if (local_is) delete _is;
2449 LgfContents(const LgfContents&);
2450 LgfContents& operator=(const LgfContents&);
2455 /// \name Node sections
2458 /// \brief Gives back the number of node sections in the file.
2460 /// Gives back the number of node sections in the file.
2461 int nodeSectionNum() const {
2462 return _node_sections.size();
2465 /// \brief Returns the node section name at the given position.
2467 /// Returns the node section name at the given position.
2468 const std::string& nodeSection(int i) const {
2469 return _node_sections[i];
2472 /// \brief Gives back the node maps for the given section.
2474 /// Gives back the node maps for the given section.
2475 const std::vector<std::string>& nodeMapNames(int i) const {
2476 return _node_maps[i];
2481 /// \name Arc/Edge sections
2484 /// \brief Gives back the number of arc/edge sections in the file.
2486 /// Gives back the number of arc/edge sections in the file.
2487 /// \note It is synonym of \c edgeSectionNum().
2488 int arcSectionNum() const {
2489 return _edge_sections.size();
2492 /// \brief Returns the arc/edge section name at the given position.
2494 /// Returns the arc/edge section name at the given position.
2495 /// \note It is synonym of \c edgeSection().
2496 const std::string& arcSection(int i) const {
2497 return _edge_sections[i];
2500 /// \brief Gives back the arc/edge maps for the given section.
2502 /// Gives back the arc/edge maps for the given section.
2503 /// \note It is synonym of \c edgeMapNames().
2504 const std::vector<std::string>& arcMapNames(int i) const {
2505 return _edge_maps[i];
2513 /// \brief Gives back the number of arc/edge sections in the file.
2515 /// Gives back the number of arc/edge sections in the file.
2516 /// \note It is synonym of \c arcSectionNum().
2517 int edgeSectionNum() const {
2518 return _edge_sections.size();
2521 /// \brief Returns the section name at the given position.
2523 /// Returns the section name at the given position.
2524 /// \note It is synonym of \c arcSection().
2525 const std::string& edgeSection(int i) const {
2526 return _edge_sections[i];
2529 /// \brief Gives back the edge maps for the given section.
2531 /// Gives back the edge maps for the given section.
2532 /// \note It is synonym of \c arcMapNames().
2533 const std::vector<std::string>& edgeMapNames(int i) const {
2534 return _edge_maps[i];
2539 /// \name Attribute sections
2542 /// \brief Gives back the number of attribute sections in the file.
2544 /// Gives back the number of attribute sections in the file.
2545 int attributeSectionNum() const {
2546 return _attribute_sections.size();
2549 /// \brief Returns the attribute section name at the given position.
2551 /// Returns the attribute section name at the given position.
2552 const std::string& attributeSectionNames(int i) const {
2553 return _attribute_sections[i];
2556 /// \brief Gives back the attributes for the given section.
2558 /// Gives back the attributes for the given section.
2559 const std::vector<std::string>& attributes(int i) const {
2560 return _attributes[i];
2565 /// \name Extra sections
2568 /// \brief Gives back the number of extra sections in the file.
2570 /// Gives back the number of extra sections in the file.
2571 int extraSectionNum() const {
2572 return _extra_sections.size();
2575 /// \brief Returns the extra section type at the given position.
2577 /// Returns the section type at the given position.
2578 const std::string& extraSection(int i) const {
2579 return _extra_sections[i];
2588 while(++line_num, std::getline(*_is, str)) {
2589 line.clear(); line.str(str);
2591 if (line >> std::ws >> c && c != '#') {
2599 bool readSuccess() {
2600 return static_cast<bool>(*_is);
2603 void skipSection() {
2605 while (readSuccess() && line >> c && c != '@') {
2608 if (readSuccess()) {
2613 void readMaps(std::vector<std::string>& maps) {
2615 if (!readLine() || !(line >> c) || c == '@') {
2616 if (readSuccess() && line) line.putback(c);
2621 while (_reader_bits::readToken(line, map)) {
2622 maps.push_back(map);
2626 void readAttributes(std::vector<std::string>& attrs) {
2629 while (readSuccess() && line >> c && c != '@') {
2632 _reader_bits::readToken(line, attr);
2633 attrs.push_back(attr);
2641 /// \name Execution of the contents reader
2644 /// \brief Starts the reading
2646 /// This function starts the reading.
2652 while (readSuccess()) {
2657 std::string section, caption;
2658 _reader_bits::readToken(line, section);
2659 _reader_bits::readToken(line, caption);
2661 if (section == "nodes") {
2662 _node_sections.push_back(caption);
2663 _node_maps.push_back(std::vector<std::string>());
2664 readMaps(_node_maps.back());
2665 readLine(); skipSection();
2666 } else if (section == "arcs" || section == "edges") {
2667 _edge_sections.push_back(caption);
2668 _arc_sections.push_back(section == "arcs");
2669 _edge_maps.push_back(std::vector<std::string>());
2670 readMaps(_edge_maps.back());
2671 readLine(); skipSection();
2672 } else if (section == "attributes") {
2673 _attribute_sections.push_back(caption);
2674 _attributes.push_back(std::vector<std::string>());
2675 readAttributes(_attributes.back());
2677 _extra_sections.push_back(section);
2678 readLine(); skipSection();