3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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 Lemon Graph Format reader.
24 #ifndef LEMON_LGF_READER_H
25 #define LEMON_LGF_READER_H
34 #include <lemon/assert.h>
35 #include <lemon/graph_utils.h>
37 #include <lemon/lgf_writer.h>
39 #include <lemon/concept_check.h>
40 #include <lemon/concepts/maps.h>
44 namespace _reader_bits {
46 template <typename Value>
47 struct DefaultConverter {
48 Value operator()(const std::string& str) {
49 std::istringstream is(str);
54 if (is >> std::ws >> c) {
55 throw DataFormatError("Remaining characters in token");
62 struct DefaultConverter<std::string> {
63 std::string operator()(const std::string& str) {
68 template <typename _Item>
69 class MapStorageBase {
75 virtual ~MapStorageBase() {}
77 virtual void set(const Item& item, const std::string& value) = 0;
81 template <typename _Item, typename _Map,
82 typename _Converter = DefaultConverter<typename _Map::Value> >
83 class MapStorage : public MapStorageBase<_Item> {
86 typedef _Converter Converter;
94 MapStorage(Map& map, const Converter& converter = Converter())
95 : _map(map), _converter(converter) {}
96 virtual ~MapStorage() {}
98 virtual void set(const Item& item ,const std::string& value) {
99 _map.set(item, _converter(value));
103 template <typename _Graph, bool _dir, typename _Map,
104 typename _Converter = DefaultConverter<typename _Map::Value> >
105 class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
108 typedef _Converter Converter;
109 typedef _Graph Graph;
110 typedef typename Graph::Edge Item;
111 static const bool dir = _dir;
116 Converter _converter;
119 GraphArcMapStorage(const Graph& graph, Map& map,
120 const Converter& converter = Converter())
121 : _graph(graph), _map(map), _converter(converter) {}
122 virtual ~GraphArcMapStorage() {}
124 virtual void set(const Item& item ,const std::string& value) {
125 _map.set(_graph.direct(item, dir), _converter(value));
129 class ValueStorageBase {
131 ValueStorageBase() {}
132 virtual ~ValueStorageBase() {}
134 virtual void set(const std::string&) = 0;
137 template <typename _Value, typename _Converter = DefaultConverter<_Value> >
138 class ValueStorage : public ValueStorageBase {
140 typedef _Value Value;
141 typedef _Converter Converter;
145 Converter _converter;
148 ValueStorage(Value& value, const Converter& converter = Converter())
149 : _value(value), _converter(converter) {}
151 virtual void set(const std::string& value) {
152 _value = _converter(value);
156 template <typename Value>
157 struct MapLookUpConverter {
158 const std::map<std::string, Value>& _map;
160 MapLookUpConverter(const std::map<std::string, Value>& map)
163 Value operator()(const std::string& str) {
164 typename std::map<std::string, Value>::const_iterator it =
166 if (it == _map.end()) {
167 std::ostringstream msg;
168 msg << "Item not found: " << str;
169 throw DataFormatError(msg.str().c_str());
175 template <typename Graph>
176 struct GraphArcLookUpConverter {
178 const std::map<std::string, typename Graph::Edge>& _map;
180 GraphArcLookUpConverter(const Graph& graph,
181 const std::map<std::string,
182 typename Graph::Edge>& map)
183 : _graph(graph), _map(map) {}
185 typename Graph::Arc operator()(const std::string& str) {
186 if (str.empty() || (str[0] != '+' && str[0] != '-')) {
187 throw DataFormatError("Item must start with '+' or '-'");
189 typename std::map<std::string, typename Graph::Edge>
190 ::const_iterator it = _map.find(str.substr(1));
191 if (it == _map.end()) {
192 throw DataFormatError("Item not found");
194 return _graph.direct(it->second, str[0] == '+');
198 bool isWhiteSpace(char c) {
199 return c == ' ' || c == '\t' || c == '\v' ||
200 c == '\n' || c == '\r' || c == '\f';
204 return '0' <= c && c <='7';
207 int valueOct(char c) {
208 LEMON_ASSERT(isOct(c), "The character is not octal.");
213 return ('0' <= c && c <= '9') ||
214 ('a' <= c && c <= 'z') ||
215 ('A' <= c && c <= 'Z');
218 int valueHex(char c) {
219 LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
220 if ('0' <= c && c <= '9') return c - '0';
221 if ('a' <= c && c <= 'z') return c - 'a' + 10;
225 bool isIdentifierFirstChar(char c) {
226 return ('a' <= c && c <= 'z') ||
227 ('A' <= c && c <= 'Z') || c == '_';
230 bool isIdentifierChar(char c) {
231 return isIdentifierFirstChar(c) ||
232 ('0' <= c && c <= '9');
235 char readEscape(std::istream& is) {
238 throw DataFormatError("Escape format error");
266 if (!is.get(c) || !isHex(c))
267 throw DataFormatError("Escape format error");
268 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
269 else code = code * 16 + valueHex(c);
276 throw DataFormatError("Escape format error");
277 else if (code = valueOct(c), !is.get(c) || !isOct(c))
279 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
281 else code = code * 8 + valueOct(c);
287 std::istream& readToken(std::istream& is, std::string& str) {
288 std::ostringstream os;
297 while (is.get(c) && c != '\"') {
303 throw DataFormatError("Quoted format error");
306 while (is.get(c) && !isWhiteSpace(c)) {
323 virtual ~Section() {}
324 virtual void process(std::istream& is, int& line_num) = 0;
327 template <typename Functor>
328 class LineSection : public Section {
335 LineSection(const Functor& functor) : _functor(functor) {}
336 virtual ~LineSection() {}
338 virtual void process(std::istream& is, int& line_num) {
341 while (is.get(c) && c != '@') {
344 } else if (c == '#') {
347 } else if (!isWhiteSpace(c)) {
354 if (is) is.putback(c);
355 else if (is.eof()) is.clear();
359 template <typename Functor>
360 class StreamSection : public Section {
367 StreamSection(const Functor& functor) : _functor(functor) {}
368 virtual ~StreamSection() {}
370 virtual void process(std::istream& is, int& line_num) {
371 _functor(is, line_num);
374 while (is.get(c) && c != '@') {
377 } else if (!isWhiteSpace(c)) {
382 if (is) is.putback(c);
383 else if (is.eof()) is.clear();
389 /// \ingroup lemon_io
391 /// \brief LGF reader for directed graphs
393 /// This utility reads an \ref lgf-format "LGF" file.
395 /// The reading method does a batch processing. The user creates a
396 /// reader object, then various reading rules can be added to the
397 /// reader, and eventually the reading is executed with the \c run()
398 /// member function. A map reading rule can be added to the reader
399 /// with the \c nodeMap() or \c arcMap() members. An optional
400 /// converter parameter can also be added as a standard functor
401 /// converting from std::string to the value type of the map. If it
402 /// is set, it will determine how the tokens in the file should be
403 /// is converted to the map's value type. If the functor is not set,
404 /// then a default conversion will be used. One map can be read into
405 /// multiple map objects at the same time. The \c attribute(), \c
406 /// node() and \c arc() functions are used to add attribute reading
410 /// DigraphReader<Digraph>(std::cin, digraph).
411 /// nodeMap("coordinates", coord_map).
412 /// arcMap("capacity", cap_map).
413 /// node("source", src).
414 /// node("target", trg).
415 /// attribute("caption", caption).
419 /// By default the reader uses the first section in the file of the
420 /// proper type. If a section has an optional name, then it can be
421 /// selected for reading by giving an optional name parameter to the
422 /// \c nodes(), \c arcs() or \c attributes() functions. The readers
423 /// also can load extra sections with the \c sectionLines() and
424 /// sectionStream() functions.
426 /// The \c useNodes() and \c useArcs() functions are used to tell the reader
427 /// that the nodes or arcs should not be constructed (added to the
428 /// graph) during the reading, but instead the label map of the items
429 /// are given as a parameter of these functions. An
430 /// application of these function is multipass reading, which is
431 /// important if two \e \@arcs sections must be read from the
432 /// file. In this example the first phase would read the node set and one
433 /// of the arc sets, while the second phase would read the second arc
434 /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
435 /// The previously read label node map should be passed to the \c
436 /// useNodes() functions. Another application of multipass reading when
437 /// paths are given as a node map or an arc map. It is impossible read this in
438 /// a single pass, because the arcs are not constructed when the node
440 template <typename _Digraph>
441 class DigraphReader {
444 typedef _Digraph Digraph;
445 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
455 std::string _nodes_caption;
456 std::string _arcs_caption;
457 std::string _attributes_caption;
459 typedef std::map<std::string, Node> NodeIndex;
460 NodeIndex _node_index;
461 typedef std::map<std::string, Arc> ArcIndex;
464 typedef std::vector<std::pair<std::string,
465 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
468 typedef std::vector<std::pair<std::string,
469 _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
472 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
474 Attributes _attributes;
476 typedef std::map<std::string, _reader_bits::Section*> Sections;
486 std::istringstream line;
490 /// \brief Constructor
492 /// Construct a directed graph reader, which reads from the given
494 DigraphReader(std::istream& is, Digraph& digraph)
495 : _is(&is), local_is(false), _digraph(digraph),
496 _use_nodes(false), _use_arcs(false),
497 _skip_nodes(false), _skip_arcs(false) {}
499 /// \brief Constructor
501 /// Construct a directed graph reader, which reads from the given
503 DigraphReader(const std::string& fn, Digraph& digraph)
504 : _is(new std::ifstream(fn.c_str())), local_is(true), _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(const char* fn, Digraph& digraph)
513 : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
514 _use_nodes(false), _use_arcs(false),
515 _skip_nodes(false), _skip_arcs(false) {}
517 /// \brief Copy constructor
519 /// The copy constructor transfers all data from the other reader,
520 /// therefore the copied reader will not be usable more.
521 DigraphReader(DigraphReader& other)
522 : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
523 _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
524 _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
527 other.local_is = false;
529 _node_index.swap(other._node_index);
530 _arc_index.swap(other._arc_index);
532 _node_maps.swap(other._node_maps);
533 _arc_maps.swap(other._arc_maps);
534 _attributes.swap(other._attributes);
536 _nodes_caption = other._nodes_caption;
537 _arcs_caption = other._arcs_caption;
538 _attributes_caption = other._attributes_caption;
540 _sections.swap(other._sections);
543 /// \brief Destructor
545 for (typename NodeMaps::iterator it = _node_maps.begin();
546 it != _node_maps.end(); ++it) {
550 for (typename ArcMaps::iterator it = _arc_maps.begin();
551 it != _arc_maps.end(); ++it) {
555 for (typename Attributes::iterator it = _attributes.begin();
556 it != _attributes.end(); ++it) {
560 for (typename Sections::iterator it = _sections.begin();
561 it != _sections.end(); ++it) {
573 DigraphReader& operator=(const DigraphReader&);
577 /// \name Reading rules
580 /// \brief Node map reading rule
582 /// Add a node map reading rule to the reader.
583 template <typename Map>
584 DigraphReader& nodeMap(const std::string& caption, Map& map) {
585 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
586 _reader_bits::MapStorageBase<Node>* storage =
587 new _reader_bits::MapStorage<Node, Map>(map);
588 _node_maps.push_back(std::make_pair(caption, storage));
592 /// \brief Node map reading rule
594 /// Add a node map reading rule with specialized converter to the
596 template <typename Map, typename Converter>
597 DigraphReader& nodeMap(const std::string& caption, Map& map,
598 const Converter& converter = Converter()) {
599 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
600 _reader_bits::MapStorageBase<Node>* storage =
601 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
602 _node_maps.push_back(std::make_pair(caption, storage));
606 /// \brief Arc map reading rule
608 /// Add an arc map reading rule to the reader.
609 template <typename Map>
610 DigraphReader& arcMap(const std::string& caption, Map& map) {
611 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
612 _reader_bits::MapStorageBase<Arc>* storage =
613 new _reader_bits::MapStorage<Arc, Map>(map);
614 _arc_maps.push_back(std::make_pair(caption, storage));
618 /// \brief Arc map reading rule
620 /// Add an arc map reading rule with specialized converter to the
622 template <typename Map, typename Converter>
623 DigraphReader& arcMap(const std::string& caption, Map& map,
624 const Converter& converter = Converter()) {
625 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
626 _reader_bits::MapStorageBase<Arc>* storage =
627 new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
628 _arc_maps.push_back(std::make_pair(caption, storage));
632 /// \brief Attribute reading rule
634 /// Add an attribute reading rule to the reader.
635 template <typename Value>
636 DigraphReader& attribute(const std::string& caption, Value& value) {
637 _reader_bits::ValueStorageBase* storage =
638 new _reader_bits::ValueStorage<Value>(value);
639 _attributes.insert(std::make_pair(caption, storage));
643 /// \brief Attribute reading rule
645 /// Add an attribute reading rule with specialized converter to the
647 template <typename Value, typename Converter>
648 DigraphReader& attribute(const std::string& caption, Value& value,
649 const Converter& converter = Converter()) {
650 _reader_bits::ValueStorageBase* storage =
651 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
652 _attributes.insert(std::make_pair(caption, storage));
656 /// \brief Node reading rule
658 /// Add a node reading rule to reader.
659 DigraphReader& node(const std::string& caption, Node& node) {
660 typedef _reader_bits::MapLookUpConverter<Node> Converter;
661 Converter converter(_node_index);
662 _reader_bits::ValueStorageBase* storage =
663 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
664 _attributes.insert(std::make_pair(caption, storage));
668 /// \brief Arc reading rule
670 /// Add an arc reading rule to reader.
671 DigraphReader& arc(const std::string& caption, Arc& arc) {
672 typedef _reader_bits::MapLookUpConverter<Arc> Converter;
673 Converter converter(_arc_index);
674 _reader_bits::ValueStorageBase* storage =
675 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
676 _attributes.insert(std::make_pair(caption, storage));
682 /// \name Select section by name
685 /// \brief Set \c \@nodes section to be read
687 /// Set \c \@nodes section to be read
688 DigraphReader& nodes(const std::string& caption) {
689 _nodes_caption = caption;
693 /// \brief Set \c \@arcs section to be read
695 /// Set \c \@arcs section to be read
696 DigraphReader& arcs(const std::string& caption) {
697 _arcs_caption = caption;
701 /// \brief Set \c \@attributes section to be read
703 /// Set \c \@attributes section to be read
704 DigraphReader& attributes(const std::string& caption) {
705 _attributes_caption = caption;
711 /// \name Section readers
714 /// \brief Add a section processor with line oriented reading
716 /// In the \e LGF file extra sections can be placed, which contain
717 /// any data in arbitrary format. These sections can be read with
718 /// this function line by line. The first parameter is the type
719 /// descriptor of the section, the second is a functor, which
720 /// takes just one \c std::string parameter. At the reading
721 /// process, each line of the section will be given to the functor
722 /// object. However, the empty lines and the comment lines are
723 /// filtered out, and the leading whitespaces are stipped from
724 /// each processed string.
726 /// For example let's see a section, which contain several
727 /// integers, which should be inserted into a vector.
735 /// The functor is implemented as an struct:
737 /// struct NumberSection {
738 /// std::vector<int>& _data;
739 /// NumberSection(std::vector<int>& data) : _data(data) {}
740 /// void operator()(const std::string& line) {
741 /// std::istringstream ls(line);
743 /// while (ls >> value) _data.push_back(value);
749 /// reader.sectionLines("numbers", NumberSection(vec));
751 template <typename Functor>
752 DigraphReader& sectionLines(const std::string& type, Functor functor) {
753 LEMON_ASSERT(!type.empty(), "Type is not empty.");
754 LEMON_ASSERT(_sections.find(type) == _sections.end(),
755 "Multiple reading of section.");
756 LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
757 type != "attributes", "Multiple reading of section.");
758 _sections.insert(std::make_pair(type,
759 new _reader_bits::LineSection<Functor>(functor)));
764 /// \brief Add a section processor with stream oriented reading
766 /// In the \e LGF file extra sections can be placed, which contain
767 /// any data in arbitrary format. These sections can be read
768 /// directly with this function. The first parameter is the type
769 /// of the section, the second is a functor, which takes an \c
770 /// std::istream& and an int& parameter, the latter regard to the
771 /// line number of stream. The functor can read the input while
772 /// the section go on, and the line number should be modified
774 template <typename Functor>
775 DigraphReader& sectionStream(const std::string& type, Functor functor) {
776 LEMON_ASSERT(!type.empty(), "Type is not empty.");
777 LEMON_ASSERT(_sections.find(type) == _sections.end(),
778 "Multiple reading of section.");
779 LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
780 type != "attributes", "Multiple reading of section.");
781 _sections.insert(std::make_pair(type,
782 new _reader_bits::StreamSection<Functor>(functor)));
788 /// \name Using previously constructed node or arc set
791 /// \brief Use previously constructed node set
793 /// Use previously constructed node set, and specify the node
795 template <typename Map>
796 DigraphReader& useNodes(const Map& map) {
797 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
798 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
800 _writer_bits::DefaultConverter<typename Map::Value> converter;
801 for (NodeIt n(_digraph); n != INVALID; ++n) {
802 _node_index.insert(std::make_pair(converter(map[n]), n));
807 /// \brief Use previously constructed node set
809 /// Use previously constructed node set, and specify the node
810 /// label map and a functor which converts the label map values to
812 template <typename Map, typename Converter>
813 DigraphReader& useNodes(const Map& map,
814 const Converter& converter = Converter()) {
815 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
816 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
818 for (NodeIt n(_digraph); n != INVALID; ++n) {
819 _node_index.insert(std::make_pair(converter(map[n]), n));
824 /// \brief Use previously constructed arc set
826 /// Use previously constructed arc set, and specify the arc
828 template <typename Map>
829 DigraphReader& useArcs(const Map& map) {
830 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
831 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
833 _writer_bits::DefaultConverter<typename Map::Value> converter;
834 for (ArcIt a(_digraph); a != INVALID; ++a) {
835 _arc_index.insert(std::make_pair(converter(map[a]), a));
840 /// \brief Use previously constructed arc set
842 /// Use previously constructed arc set, and specify the arc
843 /// label map and a functor which converts the label map values to
845 template <typename Map, typename Converter>
846 DigraphReader& useArcs(const Map& map,
847 const Converter& converter = Converter()) {
848 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
849 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
851 for (ArcIt a(_digraph); a != INVALID; ++a) {
852 _arc_index.insert(std::make_pair(converter(map[a]), a));
857 /// \brief Skips the reading of node section
859 /// Omit the reading of the node section. This implies that each node
860 /// map reading rule will be abanoned, and the nodes of the graph
861 /// will not be constructed, which usually cause that the arc set
862 /// could not be read due to lack of node name
863 /// resolving. Therefore, the \c skipArcs() should be used too, or
864 /// the useNodes() member function should be used to specify the
865 /// label of the nodes.
866 DigraphReader& skipNodes() {
867 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
872 /// \brief Skips the reading of arc section
874 /// Omit the reading of the arc section. This implies that each arc
875 /// map reading rule will be abanoned, and the arcs of the graph
876 /// will not be constructed.
877 DigraphReader& skipArcs() {
878 LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
889 while(++line_num, std::getline(*_is, str)) {
890 line.clear(); line.str(str);
892 if (line >> std::ws >> c && c != '#') {
901 return static_cast<bool>(*_is);
906 while (readSuccess() && line >> c && c != '@') {
914 std::vector<int> map_index(_node_maps.size());
915 int map_num, label_index;
918 if (!readLine() || !(line >> c) || c == '@') {
919 if (readSuccess() && line) line.putback(c);
920 if (!_node_maps.empty())
921 throw DataFormatError("Cannot find map names");
927 std::map<std::string, int> maps;
931 while (_reader_bits::readToken(line, map)) {
932 if (maps.find(map) != maps.end()) {
933 std::ostringstream msg;
934 msg << "Multiple occurence of node map: " << map;
935 throw DataFormatError(msg.str().c_str());
937 maps.insert(std::make_pair(map, index));
941 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
942 std::map<std::string, int>::iterator jt =
943 maps.find(_node_maps[i].first);
944 if (jt == maps.end()) {
945 std::ostringstream msg;
946 msg << "Map not found in file: " << _node_maps[i].first;
947 throw DataFormatError(msg.str().c_str());
949 map_index[i] = jt->second;
953 std::map<std::string, int>::iterator jt = maps.find("label");
954 if (jt != maps.end()) {
955 label_index = jt->second;
960 map_num = maps.size();
963 while (readLine() && line >> c && c != '@') {
966 std::vector<std::string> tokens(map_num);
967 for (int i = 0; i < map_num; ++i) {
968 if (!_reader_bits::readToken(line, tokens[i])) {
969 std::ostringstream msg;
970 msg << "Column not found (" << i + 1 << ")";
971 throw DataFormatError(msg.str().c_str());
974 if (line >> std::ws >> c)
975 throw DataFormatError("Extra character on the end of line");
979 n = _digraph.addNode();
980 if (label_index != -1)
981 _node_index.insert(std::make_pair(tokens[label_index], n));
983 if (label_index == -1)
984 throw DataFormatError("Label map not found in file");
985 typename std::map<std::string, Node>::iterator it =
986 _node_index.find(tokens[label_index]);
987 if (it == _node_index.end()) {
988 std::ostringstream msg;
989 msg << "Node with label not found: " << tokens[label_index];
990 throw DataFormatError(msg.str().c_str());
995 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
996 _node_maps[i].second->set(n, tokens[map_index[i]]);
1000 if (readSuccess()) {
1007 std::vector<int> map_index(_arc_maps.size());
1008 int map_num, label_index;
1011 if (!readLine() || !(line >> c) || c == '@') {
1012 if (readSuccess() && line) line.putback(c);
1013 if (!_arc_maps.empty())
1014 throw DataFormatError("Cannot find map names");
1020 std::map<std::string, int> maps;
1024 while (_reader_bits::readToken(line, map)) {
1025 if (maps.find(map) != maps.end()) {
1026 std::ostringstream msg;
1027 msg << "Multiple occurence of arc map: " << map;
1028 throw DataFormatError(msg.str().c_str());
1030 maps.insert(std::make_pair(map, index));
1034 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1035 std::map<std::string, int>::iterator jt =
1036 maps.find(_arc_maps[i].first);
1037 if (jt == maps.end()) {
1038 std::ostringstream msg;
1039 msg << "Map not found in file: " << _arc_maps[i].first;
1040 throw DataFormatError(msg.str().c_str());
1042 map_index[i] = jt->second;
1046 std::map<std::string, int>::iterator jt = maps.find("label");
1047 if (jt != maps.end()) {
1048 label_index = jt->second;
1053 map_num = maps.size();
1056 while (readLine() && line >> c && c != '@') {
1059 std::string source_token;
1060 std::string target_token;
1062 if (!_reader_bits::readToken(line, source_token))
1063 throw DataFormatError("Source not found");
1065 if (!_reader_bits::readToken(line, target_token))
1066 throw DataFormatError("Target not found");
1068 std::vector<std::string> tokens(map_num);
1069 for (int i = 0; i < map_num; ++i) {
1070 if (!_reader_bits::readToken(line, tokens[i])) {
1071 std::ostringstream msg;
1072 msg << "Column not found (" << i + 1 << ")";
1073 throw DataFormatError(msg.str().c_str());
1076 if (line >> std::ws >> c)
1077 throw DataFormatError("Extra character on the end of line");
1082 typename NodeIndex::iterator it;
1084 it = _node_index.find(source_token);
1085 if (it == _node_index.end()) {
1086 std::ostringstream msg;
1087 msg << "Item not found: " << source_token;
1088 throw DataFormatError(msg.str().c_str());
1090 Node source = it->second;
1092 it = _node_index.find(target_token);
1093 if (it == _node_index.end()) {
1094 std::ostringstream msg;
1095 msg << "Item not found: " << target_token;
1096 throw DataFormatError(msg.str().c_str());
1098 Node target = it->second;
1100 a = _digraph.addArc(source, target);
1101 if (label_index != -1)
1102 _arc_index.insert(std::make_pair(tokens[label_index], a));
1104 if (label_index == -1)
1105 throw DataFormatError("Label map not found in file");
1106 typename std::map<std::string, Arc>::iterator it =
1107 _arc_index.find(tokens[label_index]);
1108 if (it == _arc_index.end()) {
1109 std::ostringstream msg;
1110 msg << "Arc with label not found: " << tokens[label_index];
1111 throw DataFormatError(msg.str().c_str());
1116 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1117 _arc_maps[i].second->set(a, tokens[map_index[i]]);
1121 if (readSuccess()) {
1126 void readAttributes() {
1128 std::set<std::string> read_attr;
1131 while (readLine() && line >> c && c != '@') {
1134 std::string attr, token;
1135 if (!_reader_bits::readToken(line, attr))
1136 throw DataFormatError("Attribute name not found");
1137 if (!_reader_bits::readToken(line, token))
1138 throw DataFormatError("Attribute value not found");
1140 throw DataFormatError("Extra character on the end of line");
1143 std::set<std::string>::iterator it = read_attr.find(attr);
1144 if (it != read_attr.end()) {
1145 std::ostringstream msg;
1146 msg << "Multiple occurence of attribute " << attr;
1147 throw DataFormatError(msg.str().c_str());
1149 read_attr.insert(attr);
1153 typename Attributes::iterator it = _attributes.lower_bound(attr);
1154 while (it != _attributes.end() && it->first == attr) {
1155 it->second->set(token);
1161 if (readSuccess()) {
1164 for (typename Attributes::iterator it = _attributes.begin();
1165 it != _attributes.end(); ++it) {
1166 if (read_attr.find(it->first) == read_attr.end()) {
1167 std::ostringstream msg;
1168 msg << "Attribute not found in file: " << it->first;
1169 throw DataFormatError(msg.str().c_str());
1176 /// \name Execution of the reader
1179 /// \brief Start the batch processing
1181 /// This function starts the batch processing
1183 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1185 throw DataFormatError("Cannot find file");
1188 bool nodes_done = _skip_nodes;
1189 bool arcs_done = _skip_arcs;
1190 bool attributes_done = false;
1191 std::set<std::string> extra_sections;
1197 while (readSuccess()) {
1200 std::string section, caption;
1202 _reader_bits::readToken(line, section);
1203 _reader_bits::readToken(line, caption);
1206 throw DataFormatError("Extra character on the end of line");
1208 if (section == "nodes" && !nodes_done) {
1209 if (_nodes_caption.empty() || _nodes_caption == caption) {
1213 } else if ((section == "arcs" || section == "edges") &&
1215 if (_arcs_caption.empty() || _arcs_caption == caption) {
1219 } else if (section == "attributes" && !attributes_done) {
1220 if (_attributes_caption.empty() || _attributes_caption == caption) {
1222 attributes_done = true;
1225 if (extra_sections.find(section) != extra_sections.end()) {
1226 std::ostringstream msg;
1227 msg << "Multiple occurence of section " << section;
1228 throw DataFormatError(msg.str().c_str());
1230 Sections::iterator it = _sections.find(section);
1231 if (it != _sections.end()) {
1232 extra_sections.insert(section);
1233 it->second->process(*_is, line_num);
1238 } catch (DataFormatError& error) {
1239 error.line(line_num);
1245 throw DataFormatError("Section @nodes not found");
1249 throw DataFormatError("Section @arcs not found");
1252 if (!attributes_done && !_attributes.empty()) {
1253 throw DataFormatError("Section @attributes not found");
1262 /// \relates DigraphReader
1263 template <typename Digraph>
1264 DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
1265 DigraphReader<Digraph> tmp(is, digraph);
1269 /// \relates DigraphReader
1270 template <typename Digraph>
1271 DigraphReader<Digraph> digraphReader(const std::string& fn,
1273 DigraphReader<Digraph> tmp(fn, digraph);
1277 /// \relates DigraphReader
1278 template <typename Digraph>
1279 DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
1280 DigraphReader<Digraph> tmp(fn, digraph);
1284 /// \ingroup lemon_io
1286 /// \brief LGF reader for undirected graphs
1288 /// This utility reads an \ref lgf-format "LGF" file.
1289 template <typename _Graph>
1293 typedef _Graph Graph;
1294 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1304 std::string _nodes_caption;
1305 std::string _edges_caption;
1306 std::string _attributes_caption;
1308 typedef std::map<std::string, Node> NodeIndex;
1309 NodeIndex _node_index;
1310 typedef std::map<std::string, Edge> EdgeIndex;
1311 EdgeIndex _edge_index;
1313 typedef std::vector<std::pair<std::string,
1314 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
1315 NodeMaps _node_maps;
1317 typedef std::vector<std::pair<std::string,
1318 _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1319 EdgeMaps _edge_maps;
1321 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1323 Attributes _attributes;
1325 typedef std::map<std::string, _reader_bits::Section*> Sections;
1335 std::istringstream line;
1339 /// \brief Constructor
1341 /// Construct a undirected graph reader, which reads from the given
1343 GraphReader(std::istream& is, Graph& graph)
1344 : _is(&is), local_is(false), _graph(graph),
1345 _use_nodes(false), _use_edges(false),
1346 _skip_nodes(false), _skip_edges(false) {}
1348 /// \brief Constructor
1350 /// Construct a undirected graph reader, which reads from the given
1352 GraphReader(const std::string& fn, Graph& graph)
1353 : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
1354 _use_nodes(false), _use_edges(false),
1355 _skip_nodes(false), _skip_edges(false) {}
1357 /// \brief Constructor
1359 /// Construct a undirected graph reader, which reads from the given
1361 GraphReader(const char* fn, Graph& graph)
1362 : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
1363 _use_nodes(false), _use_edges(false),
1364 _skip_nodes(false), _skip_edges(false) {}
1366 /// \brief Copy constructor
1368 /// The copy constructor transfers all data from the other reader,
1369 /// therefore the copied reader will not be usable more.
1370 GraphReader(GraphReader& other)
1371 : _is(other._is), local_is(other.local_is), _graph(other._graph),
1372 _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1373 _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1376 other.local_is = false;
1378 _node_index.swap(other._node_index);
1379 _edge_index.swap(other._edge_index);
1381 _node_maps.swap(other._node_maps);
1382 _edge_maps.swap(other._edge_maps);
1383 _attributes.swap(other._attributes);
1385 _nodes_caption = other._nodes_caption;
1386 _edges_caption = other._edges_caption;
1387 _attributes_caption = other._attributes_caption;
1389 _sections.swap(other._sections);
1392 /// \brief Destructor
1394 for (typename NodeMaps::iterator it = _node_maps.begin();
1395 it != _node_maps.end(); ++it) {
1399 for (typename EdgeMaps::iterator it = _edge_maps.begin();
1400 it != _edge_maps.end(); ++it) {
1404 for (typename Attributes::iterator it = _attributes.begin();
1405 it != _attributes.end(); ++it) {
1409 for (typename Sections::iterator it = _sections.begin();
1410 it != _sections.end(); ++it) {
1422 GraphReader& operator=(const GraphReader&);
1426 /// \name Reading rules
1429 /// \brief Node map reading rule
1431 /// Add a node map reading rule to the reader.
1432 template <typename Map>
1433 GraphReader& nodeMap(const std::string& caption, Map& map) {
1434 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1435 _reader_bits::MapStorageBase<Node>* storage =
1436 new _reader_bits::MapStorage<Node, Map>(map);
1437 _node_maps.push_back(std::make_pair(caption, storage));
1441 /// \brief Node map reading rule
1443 /// Add a node map reading rule with specialized converter to the
1445 template <typename Map, typename Converter>
1446 GraphReader& nodeMap(const std::string& caption, Map& map,
1447 const Converter& converter = Converter()) {
1448 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1449 _reader_bits::MapStorageBase<Node>* storage =
1450 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1451 _node_maps.push_back(std::make_pair(caption, storage));
1455 /// \brief Edge map reading rule
1457 /// Add an edge map reading rule to the reader.
1458 template <typename Map>
1459 GraphReader& edgeMap(const std::string& caption, Map& map) {
1460 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1461 _reader_bits::MapStorageBase<Edge>* storage =
1462 new _reader_bits::MapStorage<Edge, Map>(map);
1463 _edge_maps.push_back(std::make_pair(caption, storage));
1467 /// \brief Edge map reading rule
1469 /// Add an edge map reading rule with specialized converter to the
1471 template <typename Map, typename Converter>
1472 GraphReader& edgeMap(const std::string& caption, Map& map,
1473 const Converter& converter = Converter()) {
1474 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1475 _reader_bits::MapStorageBase<Edge>* storage =
1476 new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1477 _edge_maps.push_back(std::make_pair(caption, storage));
1481 /// \brief Arc map reading rule
1483 /// Add an arc map reading rule to the reader.
1484 template <typename Map>
1485 GraphReader& arcMap(const std::string& caption, Map& map) {
1486 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1487 _reader_bits::MapStorageBase<Edge>* forward_storage =
1488 new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1489 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1490 _reader_bits::MapStorageBase<Edge>* backward_storage =
1491 new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1492 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1496 /// \brief Arc map reading rule
1498 /// Add an arc map reading rule with specialized converter to the
1500 template <typename Map, typename Converter>
1501 GraphReader& arcMap(const std::string& caption, Map& map,
1502 const Converter& converter = Converter()) {
1503 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1504 _reader_bits::MapStorageBase<Edge>* forward_storage =
1505 new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1506 (_graph, map, converter);
1507 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1508 _reader_bits::MapStorageBase<Edge>* backward_storage =
1509 new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1510 (_graph, map, converter);
1511 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1515 /// \brief Attribute reading rule
1517 /// Add an attribute reading rule to the reader.
1518 template <typename Value>
1519 GraphReader& attribute(const std::string& caption, Value& value) {
1520 _reader_bits::ValueStorageBase* storage =
1521 new _reader_bits::ValueStorage<Value>(value);
1522 _attributes.insert(std::make_pair(caption, storage));
1526 /// \brief Attribute reading rule
1528 /// Add an attribute reading rule with specialized converter to the
1530 template <typename Value, typename Converter>
1531 GraphReader& attribute(const std::string& caption, Value& value,
1532 const Converter& converter = Converter()) {
1533 _reader_bits::ValueStorageBase* storage =
1534 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1535 _attributes.insert(std::make_pair(caption, storage));
1539 /// \brief Node reading rule
1541 /// Add a node reading rule to reader.
1542 GraphReader& node(const std::string& caption, Node& node) {
1543 typedef _reader_bits::MapLookUpConverter<Node> Converter;
1544 Converter converter(_node_index);
1545 _reader_bits::ValueStorageBase* storage =
1546 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1547 _attributes.insert(std::make_pair(caption, storage));
1551 /// \brief Edge reading rule
1553 /// Add an edge reading rule to reader.
1554 GraphReader& edge(const std::string& caption, Edge& edge) {
1555 typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1556 Converter converter(_edge_index);
1557 _reader_bits::ValueStorageBase* storage =
1558 new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1559 _attributes.insert(std::make_pair(caption, storage));
1563 /// \brief Arc reading rule
1565 /// Add an arc reading rule to reader.
1566 GraphReader& arc(const std::string& caption, Arc& arc) {
1567 typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
1568 Converter converter(_graph, _edge_index);
1569 _reader_bits::ValueStorageBase* storage =
1570 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1571 _attributes.insert(std::make_pair(caption, storage));
1577 /// \name Select section by name
1580 /// \brief Set \c \@nodes section to be read
1582 /// Set \c \@nodes section to be read
1583 GraphReader& nodes(const std::string& caption) {
1584 _nodes_caption = caption;
1588 /// \brief Set \c \@edges section to be read
1590 /// Set \c \@edges section to be read
1591 GraphReader& edges(const std::string& caption) {
1592 _edges_caption = caption;
1596 /// \brief Set \c \@attributes section to be read
1598 /// Set \c \@attributes section to be read
1599 GraphReader& attributes(const std::string& caption) {
1600 _attributes_caption = caption;
1606 /// \name Section readers
1609 /// \brief Add a section processor with line oriented reading
1611 /// In the \e LGF file extra sections can be placed, which contain
1612 /// any data in arbitrary format. These sections can be read with
1613 /// this function line by line. The first parameter is the type
1614 /// descriptor of the section, the second is a functor, which
1615 /// takes just one \c std::string parameter. At the reading
1616 /// process, each line of the section will be given to the functor
1617 /// object. However, the empty lines and the comment lines are
1618 /// filtered out, and the leading whitespaces are stipped from
1619 /// each processed string.
1621 /// For example let's see a section, which contain several
1622 /// integers, which should be inserted into a vector.
1630 /// The functor is implemented as an struct:
1632 /// struct NumberSection {
1633 /// std::vector<int>& _data;
1634 /// NumberSection(std::vector<int>& data) : _data(data) {}
1635 /// void operator()(const std::string& line) {
1636 /// std::istringstream ls(line);
1638 /// while (ls >> value) _data.push_back(value);
1644 /// reader.sectionLines("numbers", NumberSection(vec));
1646 template <typename Functor>
1647 GraphReader& sectionLines(const std::string& type, Functor functor) {
1648 LEMON_ASSERT(!type.empty(), "Type is not empty.");
1649 LEMON_ASSERT(_sections.find(type) == _sections.end(),
1650 "Multiple reading of section.");
1651 LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
1652 type != "attributes", "Multiple reading of section.");
1653 _sections.insert(std::make_pair(type,
1654 new _reader_bits::LineSection<Functor>(functor)));
1659 /// \brief Add a section processor with stream oriented reading
1661 /// In the \e LGF file extra sections can be placed, which contain
1662 /// any data in arbitrary format. These sections can be read
1663 /// directly with this function. The first parameter is the type
1664 /// of the section, the second is a functor, which takes an \c
1665 /// std::istream& and an int& parameter, the latter regard to the
1666 /// line number of stream. The functor can read the input while
1667 /// the section go on, and the line number should be modified
1669 template <typename Functor>
1670 GraphReader& sectionStream(const std::string& type, Functor functor) {
1671 LEMON_ASSERT(!type.empty(), "Type is not empty.");
1672 LEMON_ASSERT(_sections.find(type) == _sections.end(),
1673 "Multiple reading of section.");
1674 LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
1675 type != "attributes", "Multiple reading of section.");
1676 _sections.insert(std::make_pair(type,
1677 new _reader_bits::StreamSection<Functor>(functor)));
1683 /// \name Using previously constructed node or edge set
1686 /// \brief Use previously constructed node set
1688 /// Use previously constructed node set, and specify the node
1690 template <typename Map>
1691 GraphReader& useNodes(const Map& map) {
1692 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1693 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1695 _writer_bits::DefaultConverter<typename Map::Value> converter;
1696 for (NodeIt n(_graph); n != INVALID; ++n) {
1697 _node_index.insert(std::make_pair(converter(map[n]), n));
1702 /// \brief Use previously constructed node set
1704 /// Use previously constructed node set, and specify the node
1705 /// label map and a functor which converts the label map values to
1707 template <typename Map, typename Converter>
1708 GraphReader& useNodes(const Map& map,
1709 const Converter& converter = Converter()) {
1710 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1711 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1713 for (NodeIt n(_graph); n != INVALID; ++n) {
1714 _node_index.insert(std::make_pair(converter(map[n]), n));
1719 /// \brief Use previously constructed edge set
1721 /// Use previously constructed edge set, and specify the edge
1723 template <typename Map>
1724 GraphReader& useEdges(const Map& map) {
1725 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1726 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1728 _writer_bits::DefaultConverter<typename Map::Value> converter;
1729 for (EdgeIt a(_graph); a != INVALID; ++a) {
1730 _edge_index.insert(std::make_pair(converter(map[a]), a));
1735 /// \brief Use previously constructed edge set
1737 /// Use previously constructed edge set, and specify the edge
1738 /// label map and a functor which converts the label map values to
1740 template <typename Map, typename Converter>
1741 GraphReader& useEdges(const Map& map,
1742 const Converter& converter = Converter()) {
1743 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1744 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1746 for (EdgeIt a(_graph); a != INVALID; ++a) {
1747 _edge_index.insert(std::make_pair(converter(map[a]), a));
1752 /// \brief Skips the reading of node section
1754 /// Omit the reading of the node section. This implies that each node
1755 /// map reading rule will be abanoned, and the nodes of the graph
1756 /// will not be constructed, which usually cause that the edge set
1757 /// could not be read due to lack of node name
1758 /// resolving. Therefore, the \c skipEdges() should be used too, or
1759 /// the useNodes() member function should be used to specify the
1760 /// label of the nodes.
1761 GraphReader& skipNodes() {
1762 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1767 /// \brief Skips the reading of edge section
1769 /// Omit the reading of the edge section. This implies that each edge
1770 /// map reading rule will be abanoned, and the edges of the graph
1771 /// will not be constructed.
1772 GraphReader& skipEdges() {
1773 LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1784 while(++line_num, std::getline(*_is, str)) {
1785 line.clear(); line.str(str);
1787 if (line >> std::ws >> c && c != '#') {
1795 bool readSuccess() {
1796 return static_cast<bool>(*_is);
1799 void skipSection() {
1801 while (readSuccess() && line >> c && c != '@') {
1809 std::vector<int> map_index(_node_maps.size());
1810 int map_num, label_index;
1813 if (!readLine() || !(line >> c) || c == '@') {
1814 if (readSuccess() && line) line.putback(c);
1815 if (!_node_maps.empty())
1816 throw DataFormatError("Cannot find map names");
1822 std::map<std::string, int> maps;
1826 while (_reader_bits::readToken(line, map)) {
1827 if (maps.find(map) != maps.end()) {
1828 std::ostringstream msg;
1829 msg << "Multiple occurence of node map: " << map;
1830 throw DataFormatError(msg.str().c_str());
1832 maps.insert(std::make_pair(map, index));
1836 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1837 std::map<std::string, int>::iterator jt =
1838 maps.find(_node_maps[i].first);
1839 if (jt == maps.end()) {
1840 std::ostringstream msg;
1841 msg << "Map not found in file: " << _node_maps[i].first;
1842 throw DataFormatError(msg.str().c_str());
1844 map_index[i] = jt->second;
1848 std::map<std::string, int>::iterator jt = maps.find("label");
1849 if (jt != maps.end()) {
1850 label_index = jt->second;
1855 map_num = maps.size();
1858 while (readLine() && line >> c && c != '@') {
1861 std::vector<std::string> tokens(map_num);
1862 for (int i = 0; i < map_num; ++i) {
1863 if (!_reader_bits::readToken(line, tokens[i])) {
1864 std::ostringstream msg;
1865 msg << "Column not found (" << i + 1 << ")";
1866 throw DataFormatError(msg.str().c_str());
1869 if (line >> std::ws >> c)
1870 throw DataFormatError("Extra character on the end of line");
1874 n = _graph.addNode();
1875 if (label_index != -1)
1876 _node_index.insert(std::make_pair(tokens[label_index], n));
1878 if (label_index == -1)
1879 throw DataFormatError("Label map not found in file");
1880 typename std::map<std::string, Node>::iterator it =
1881 _node_index.find(tokens[label_index]);
1882 if (it == _node_index.end()) {
1883 std::ostringstream msg;
1884 msg << "Node with label not found: " << tokens[label_index];
1885 throw DataFormatError(msg.str().c_str());
1890 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1891 _node_maps[i].second->set(n, tokens[map_index[i]]);
1895 if (readSuccess()) {
1902 std::vector<int> map_index(_edge_maps.size());
1903 int map_num, label_index;
1906 if (!readLine() || !(line >> c) || c == '@') {
1907 if (readSuccess() && line) line.putback(c);
1908 if (!_edge_maps.empty())
1909 throw DataFormatError("Cannot find map names");
1915 std::map<std::string, int> maps;
1919 while (_reader_bits::readToken(line, map)) {
1920 if (maps.find(map) != maps.end()) {
1921 std::ostringstream msg;
1922 msg << "Multiple occurence of edge map: " << map;
1923 throw DataFormatError(msg.str().c_str());
1925 maps.insert(std::make_pair(map, index));
1929 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1930 std::map<std::string, int>::iterator jt =
1931 maps.find(_edge_maps[i].first);
1932 if (jt == maps.end()) {
1933 std::ostringstream msg;
1934 msg << "Map not found in file: " << _edge_maps[i].first;
1935 throw DataFormatError(msg.str().c_str());
1937 map_index[i] = jt->second;
1941 std::map<std::string, int>::iterator jt = maps.find("label");
1942 if (jt != maps.end()) {
1943 label_index = jt->second;
1948 map_num = maps.size();
1951 while (readLine() && line >> c && c != '@') {
1954 std::string source_token;
1955 std::string target_token;
1957 if (!_reader_bits::readToken(line, source_token))
1958 throw DataFormatError("Node u not found");
1960 if (!_reader_bits::readToken(line, target_token))
1961 throw DataFormatError("Node v not found");
1963 std::vector<std::string> tokens(map_num);
1964 for (int i = 0; i < map_num; ++i) {
1965 if (!_reader_bits::readToken(line, tokens[i])) {
1966 std::ostringstream msg;
1967 msg << "Column not found (" << i + 1 << ")";
1968 throw DataFormatError(msg.str().c_str());
1971 if (line >> std::ws >> c)
1972 throw DataFormatError("Extra character on the end of line");
1977 typename NodeIndex::iterator it;
1979 it = _node_index.find(source_token);
1980 if (it == _node_index.end()) {
1981 std::ostringstream msg;
1982 msg << "Item not found: " << source_token;
1983 throw DataFormatError(msg.str().c_str());
1985 Node source = it->second;
1987 it = _node_index.find(target_token);
1988 if (it == _node_index.end()) {
1989 std::ostringstream msg;
1990 msg << "Item not found: " << target_token;
1991 throw DataFormatError(msg.str().c_str());
1993 Node target = it->second;
1995 e = _graph.addEdge(source, target);
1996 if (label_index != -1)
1997 _edge_index.insert(std::make_pair(tokens[label_index], e));
1999 if (label_index == -1)
2000 throw DataFormatError("Label map not found in file");
2001 typename std::map<std::string, Edge>::iterator it =
2002 _edge_index.find(tokens[label_index]);
2003 if (it == _edge_index.end()) {
2004 std::ostringstream msg;
2005 msg << "Edge with label not found: " << tokens[label_index];
2006 throw DataFormatError(msg.str().c_str());
2011 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
2012 _edge_maps[i].second->set(e, tokens[map_index[i]]);
2016 if (readSuccess()) {
2021 void readAttributes() {
2023 std::set<std::string> read_attr;
2026 while (readLine() && line >> c && c != '@') {
2029 std::string attr, token;
2030 if (!_reader_bits::readToken(line, attr))
2031 throw DataFormatError("Attribute name not found");
2032 if (!_reader_bits::readToken(line, token))
2033 throw DataFormatError("Attribute value not found");
2035 throw DataFormatError("Extra character on the end of line");
2038 std::set<std::string>::iterator it = read_attr.find(attr);
2039 if (it != read_attr.end()) {
2040 std::ostringstream msg;
2041 msg << "Multiple occurence of attribute " << attr;
2042 throw DataFormatError(msg.str().c_str());
2044 read_attr.insert(attr);
2048 typename Attributes::iterator it = _attributes.lower_bound(attr);
2049 while (it != _attributes.end() && it->first == attr) {
2050 it->second->set(token);
2056 if (readSuccess()) {
2059 for (typename Attributes::iterator it = _attributes.begin();
2060 it != _attributes.end(); ++it) {
2061 if (read_attr.find(it->first) == read_attr.end()) {
2062 std::ostringstream msg;
2063 msg << "Attribute not found in file: " << it->first;
2064 throw DataFormatError(msg.str().c_str());
2071 /// \name Execution of the reader
2074 /// \brief Start the batch processing
2076 /// This function starts the batch processing
2079 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2081 bool nodes_done = _skip_nodes;
2082 bool edges_done = _skip_edges;
2083 bool attributes_done = false;
2084 std::set<std::string> extra_sections;
2090 while (readSuccess()) {
2093 std::string section, caption;
2095 _reader_bits::readToken(line, section);
2096 _reader_bits::readToken(line, caption);
2099 throw DataFormatError("Extra character on the end of line");
2101 if (section == "nodes" && !nodes_done) {
2102 if (_nodes_caption.empty() || _nodes_caption == caption) {
2106 } else if ((section == "edges" || section == "arcs") &&
2108 if (_edges_caption.empty() || _edges_caption == caption) {
2112 } else if (section == "attributes" && !attributes_done) {
2113 if (_attributes_caption.empty() || _attributes_caption == caption) {
2115 attributes_done = true;
2118 if (extra_sections.find(section) != extra_sections.end()) {
2119 std::ostringstream msg;
2120 msg << "Multiple occurence of section " << section;
2121 throw DataFormatError(msg.str().c_str());
2123 Sections::iterator it = _sections.find(section);
2124 if (it != _sections.end()) {
2125 extra_sections.insert(section);
2126 it->second->process(*_is, line_num);
2131 } catch (DataFormatError& error) {
2132 error.line(line_num);
2138 throw DataFormatError("Section @nodes not found");
2142 throw DataFormatError("Section @edges not found");
2145 if (!attributes_done && !_attributes.empty()) {
2146 throw DataFormatError("Section @attributes not found");
2155 /// \relates GraphReader
2156 template <typename Graph>
2157 GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
2158 GraphReader<Graph> tmp(is, graph);
2162 /// \relates GraphReader
2163 template <typename Graph>
2164 GraphReader<Graph> graphReader(const std::string& fn,
2166 GraphReader<Graph> tmp(fn, graph);
2170 /// \relates GraphReader
2171 template <typename Graph>
2172 GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
2173 GraphReader<Graph> tmp(fn, graph);
2177 /// \ingroup lemon_io
2179 /// \brief Reader for the contents of the \ref lgf-format "LGF" file
2181 /// This class can be used to read the sections, the map names and
2182 /// the attributes from a file. Usually, the Lemon programs know
2183 /// that, which type of graph, which maps and which attributes
2184 /// should be read from a file, but in general tools (like glemon)
2185 /// the contents of an LGF file should be guessed somehow. This class
2186 /// reads the graph and stores the appropriate information for
2187 /// reading the graph.
2189 ///\code LgfContents contents("graph.lgf");
2192 /// // does it contain any node section and arc section
2193 /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
2194 /// std::cerr << "Failure, cannot find graph" << std::endl;
2197 /// std::cout << "The name of the default node section : "
2198 /// << contents.nodeSection(0) << std::endl;
2199 /// std::cout << "The number of the arc maps : "
2200 /// << contents.arcMaps(0).size() << std::endl;
2201 /// std::cout << "The name of second arc map : "
2202 /// << contents.arcMaps(0)[1] << std::endl;
2210 std::vector<std::string> _node_sections;
2211 std::vector<std::string> _edge_sections;
2212 std::vector<std::string> _attribute_sections;
2213 std::vector<std::string> _extra_sections;
2215 std::vector<bool> _arc_sections;
2217 std::vector<std::vector<std::string> > _node_maps;
2218 std::vector<std::vector<std::string> > _edge_maps;
2220 std::vector<std::vector<std::string> > _attributes;
2224 std::istringstream line;
2228 /// \brief Constructor
2230 /// Construct an \e LGF contents reader, which reads from the given
2232 LgfContents(std::istream& is)
2233 : _is(&is), local_is(false) {}
2235 /// \brief Constructor
2237 /// Construct an \e LGF contents reader, which reads from the given
2239 LgfContents(const std::string& fn)
2240 : _is(new std::ifstream(fn.c_str())), local_is(true) {}
2242 /// \brief Constructor
2244 /// Construct an \e LGF contents reader, which reads from the given
2246 LgfContents(const char* fn)
2247 : _is(new std::ifstream(fn)), local_is(true) {}
2249 /// \brief Copy constructor
2251 /// The copy constructor transfers all data from the other reader,
2252 /// therefore the copied reader will not be usable more.
2253 LgfContents(LgfContents& other)
2254 : _is(other._is), local_is(other.local_is) {
2257 other.local_is = false;
2259 _node_sections.swap(other._node_sections);
2260 _edge_sections.swap(other._edge_sections);
2261 _attribute_sections.swap(other._attribute_sections);
2262 _extra_sections.swap(other._extra_sections);
2264 _arc_sections.swap(other._arc_sections);
2266 _node_maps.swap(other._node_maps);
2267 _edge_maps.swap(other._edge_maps);
2268 _attributes.swap(other._attributes);
2271 /// \brief Destructor
2273 if (local_is) delete _is;
2277 /// \name Node sections
2280 /// \brief Gives back the number of node sections in the file.
2282 /// Gives back the number of node sections in the file.
2283 int nodeSectionNum() const {
2284 return _node_sections.size();
2287 /// \brief Returns the section name at the given position.
2289 /// Returns the section name at the given position.
2290 const std::string& nodeSection(int i) const {
2291 return _node_sections[i];
2294 /// \brief Gives back the node maps for the given section.
2296 /// Gives back the node maps for the given section.
2297 const std::vector<std::string>& nodeMapNames(int i) const {
2298 return _node_maps[i];
2303 /// \name Arc/Edge sections
2306 /// \brief Gives back the number of arc/edge sections in the file.
2308 /// Gives back the number of arc/edge sections in the file.
2309 /// \note It is synonym of \c edgeSectionNum().
2310 int arcSectionNum() const {
2311 return _edge_sections.size();
2314 /// \brief Returns the section name at the given position.
2316 /// Returns the section name at the given position.
2317 /// \note It is synonym of \c edgeSection().
2318 const std::string& arcSection(int i) const {
2319 return _edge_sections[i];
2322 /// \brief Gives back the arc/edge maps for the given section.
2324 /// Gives back the arc/edge maps for the given section.
2325 /// \note It is synonym of \c edgeMapNames().
2326 const std::vector<std::string>& arcMapNames(int i) const {
2327 return _edge_maps[i];
2335 /// \brief Gives back the number of arc/edge sections in the file.
2337 /// Gives back the number of arc/edge sections in the file.
2338 /// \note It is synonym of \c arcSectionNum().
2339 int edgeSectionNum() const {
2340 return _edge_sections.size();
2343 /// \brief Returns the section name at the given position.
2345 /// Returns the section name at the given position.
2346 /// \note It is synonym of \c arcSection().
2347 const std::string& edgeSection(int i) const {
2348 return _edge_sections[i];
2351 /// \brief Gives back the edge maps for the given section.
2353 /// Gives back the edge maps for the given section.
2354 /// \note It is synonym of \c arcMapNames().
2355 const std::vector<std::string>& edgeMapNames(int i) const {
2356 return _edge_maps[i];
2361 /// \name Attribute sections
2364 /// \brief Gives back the number of attribute sections in the file.
2366 /// Gives back the number of attribute sections in the file.
2367 int attributeSectionNum() const {
2368 return _attribute_sections.size();
2371 /// \brief Returns the section name at the given position.
2373 /// Returns the section name at the given position.
2374 const std::string& attributeSectionNames(int i) const {
2375 return _attribute_sections[i];
2378 /// \brief Gives back the attributes for the given section.
2380 /// Gives back the attributes for the given section.
2381 const std::vector<std::string>& attributes(int i) const {
2382 return _attributes[i];
2387 /// \name Extra sections
2390 /// \brief Gives back the number of extra sections in the file.
2392 /// Gives back the number of extra sections in the file.
2393 int extraSectionNum() const {
2394 return _extra_sections.size();
2397 /// \brief Returns the extra section type at the given position.
2399 /// Returns the section type at the given position.
2400 const std::string& extraSection(int i) const {
2401 return _extra_sections[i];
2410 while(++line_num, std::getline(*_is, str)) {
2411 line.clear(); line.str(str);
2413 if (line >> std::ws >> c && c != '#') {
2421 bool readSuccess() {
2422 return static_cast<bool>(*_is);
2425 void skipSection() {
2427 while (readSuccess() && line >> c && c != '@') {
2433 void readMaps(std::vector<std::string>& maps) {
2435 if (!readLine() || !(line >> c) || c == '@') {
2436 if (readSuccess() && line) line.putback(c);
2441 while (_reader_bits::readToken(line, map)) {
2442 maps.push_back(map);
2446 void readAttributes(std::vector<std::string>& attrs) {
2449 while (readSuccess() && line >> c && c != '@') {
2452 _reader_bits::readToken(line, attr);
2453 attrs.push_back(attr);
2461 /// \name Execution of the contents reader
2464 /// \brief Start the reading
2466 /// This function starts the reading
2472 while (readSuccess()) {
2477 std::string section, caption;
2478 _reader_bits::readToken(line, section);
2479 _reader_bits::readToken(line, caption);
2481 if (section == "nodes") {
2482 _node_sections.push_back(caption);
2483 _node_maps.push_back(std::vector<std::string>());
2484 readMaps(_node_maps.back());
2485 readLine(); skipSection();
2486 } else if (section == "arcs" || section == "edges") {
2487 _edge_sections.push_back(caption);
2488 _arc_sections.push_back(section == "arcs");
2489 _edge_maps.push_back(std::vector<std::string>());
2490 readMaps(_edge_maps.back());
2491 readLine(); skipSection();
2492 } else if (section == "attributes") {
2493 _attribute_sections.push_back(caption);
2494 _attributes.push_back(std::vector<std::string>());
2495 readAttributes(_attributes.back());
2497 _extra_sections.push_back(section);
2498 readLine(); skipSection();