1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
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 \ref lgf-format "LEMON Graph Format" reader.
24 #ifndef LEMON_LGF_READER_H
25 #define LEMON_LGF_READER_H
34 #include <lemon/assert.h>
35 #include <lemon/core.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);
52 throw FormatError("Cannot read token");
56 if (is >> std::ws >> c) {
57 throw FormatError("Remaining characters in token");
64 struct DefaultConverter<std::string> {
65 std::string operator()(const std::string& str) {
70 template <typename _Item>
71 class MapStorageBase {
77 virtual ~MapStorageBase() {}
79 virtual void set(const Item& item, const std::string& value) = 0;
83 template <typename _Item, typename _Map,
84 typename _Converter = DefaultConverter<typename _Map::Value> >
85 class MapStorage : public MapStorageBase<_Item> {
88 typedef _Converter Converter;
96 MapStorage(Map& map, const Converter& converter = Converter())
97 : _map(map), _converter(converter) {}
98 virtual ~MapStorage() {}
100 virtual void set(const Item& item ,const std::string& value) {
101 _map.set(item, _converter(value));
105 template <typename _Graph, bool _dir, typename _Map,
106 typename _Converter = DefaultConverter<typename _Map::Value> >
107 class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
110 typedef _Converter Converter;
111 typedef _Graph Graph;
112 typedef typename Graph::Edge Item;
113 static const bool dir = _dir;
118 Converter _converter;
121 GraphArcMapStorage(const Graph& graph, Map& map,
122 const Converter& converter = Converter())
123 : _graph(graph), _map(map), _converter(converter) {}
124 virtual ~GraphArcMapStorage() {}
126 virtual void set(const Item& item ,const std::string& value) {
127 _map.set(_graph.direct(item, dir), _converter(value));
131 class ValueStorageBase {
133 ValueStorageBase() {}
134 virtual ~ValueStorageBase() {}
136 virtual void set(const std::string&) = 0;
139 template <typename _Value, typename _Converter = DefaultConverter<_Value> >
140 class ValueStorage : public ValueStorageBase {
142 typedef _Value Value;
143 typedef _Converter Converter;
147 Converter _converter;
150 ValueStorage(Value& value, const Converter& converter = Converter())
151 : _value(value), _converter(converter) {}
153 virtual void set(const std::string& value) {
154 _value = _converter(value);
158 template <typename Value>
159 struct MapLookUpConverter {
160 const std::map<std::string, Value>& _map;
162 MapLookUpConverter(const std::map<std::string, Value>& map)
165 Value operator()(const std::string& str) {
166 typename std::map<std::string, Value>::const_iterator it =
168 if (it == _map.end()) {
169 std::ostringstream msg;
170 msg << "Item not found: " << str;
171 throw FormatError(msg.str());
177 template <typename Graph>
178 struct GraphArcLookUpConverter {
180 const std::map<std::string, typename Graph::Edge>& _map;
182 GraphArcLookUpConverter(const Graph& graph,
183 const std::map<std::string,
184 typename Graph::Edge>& map)
185 : _graph(graph), _map(map) {}
187 typename Graph::Arc operator()(const std::string& str) {
188 if (str.empty() || (str[0] != '+' && str[0] != '-')) {
189 throw FormatError("Item must start with '+' or '-'");
191 typename std::map<std::string, typename Graph::Edge>
192 ::const_iterator it = _map.find(str.substr(1));
193 if (it == _map.end()) {
194 throw FormatError("Item not found");
196 return _graph.direct(it->second, str[0] == '+');
200 inline bool isWhiteSpace(char c) {
201 return c == ' ' || c == '\t' || c == '\v' ||
202 c == '\n' || c == '\r' || c == '\f';
205 inline bool isOct(char c) {
206 return '0' <= c && c <='7';
209 inline int valueOct(char c) {
210 LEMON_ASSERT(isOct(c), "The character is not octal.");
214 inline bool isHex(char c) {
215 return ('0' <= c && c <= '9') ||
216 ('a' <= c && c <= 'z') ||
217 ('A' <= c && c <= 'Z');
220 inline int valueHex(char c) {
221 LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
222 if ('0' <= c && c <= '9') return c - '0';
223 if ('a' <= c && c <= 'z') return c - 'a' + 10;
227 inline bool isIdentifierFirstChar(char c) {
228 return ('a' <= c && c <= 'z') ||
229 ('A' <= c && c <= 'Z') || c == '_';
232 inline bool isIdentifierChar(char c) {
233 return isIdentifierFirstChar(c) ||
234 ('0' <= c && c <= '9');
237 inline char readEscape(std::istream& is) {
240 throw FormatError("Escape format error");
268 if (!is.get(c) || !isHex(c))
269 throw FormatError("Escape format error");
270 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
271 else code = code * 16 + valueHex(c);
278 throw FormatError("Escape format error");
279 else if (code = valueOct(c), !is.get(c) || !isOct(c))
281 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
283 else code = code * 8 + valueOct(c);
289 inline std::istream& readToken(std::istream& is, std::string& str) {
290 std::ostringstream os;
299 while (is.get(c) && c != '\"') {
305 throw FormatError("Quoted format error");
308 while (is.get(c) && !isWhiteSpace(c)) {
325 virtual ~Section() {}
326 virtual void process(std::istream& is, int& line_num) = 0;
329 template <typename Functor>
330 class LineSection : public Section {
337 LineSection(const Functor& functor) : _functor(functor) {}
338 virtual ~LineSection() {}
340 virtual void process(std::istream& is, int& line_num) {
343 while (is.get(c) && c != '@') {
346 } else if (c == '#') {
349 } else if (!isWhiteSpace(c)) {
356 if (is) is.putback(c);
357 else if (is.eof()) is.clear();
361 template <typename Functor>
362 class StreamSection : public Section {
369 StreamSection(const Functor& functor) : _functor(functor) {}
370 virtual ~StreamSection() {}
372 virtual void process(std::istream& is, int& line_num) {
373 _functor(is, line_num);
376 while (is.get(c) && c != '@') {
379 } else if (!isWhiteSpace(c)) {
384 if (is) is.putback(c);
385 else if (is.eof()) is.clear();
391 template <typename Digraph>
394 template <typename Digraph>
395 DigraphReader<Digraph> digraphReader(Digraph& digraph,
396 std::istream& is = std::cin);
398 template <typename Digraph>
399 DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
401 template <typename Digraph>
402 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
404 /// \ingroup lemon_io
406 /// \brief \ref lgf-format "LGF" reader for directed graphs
408 /// This utility reads an \ref lgf-format "LGF" file.
410 /// The reading method does a batch processing. The user creates a
411 /// reader object, then various reading rules can be added to the
412 /// reader, and eventually the reading is executed with the \c run()
413 /// member function. A map reading rule can be added to the reader
414 /// with the \c nodeMap() or \c arcMap() members. An optional
415 /// converter parameter can also be added as a standard functor
416 /// converting from \c std::string to the value type of the map. If it
417 /// is set, it will determine how the tokens in the file should be
418 /// converted to the value type of the map. If the functor is not set,
419 /// then a default conversion will be used. One map can be read into
420 /// multiple map objects at the same time. The \c attribute(), \c
421 /// node() and \c arc() functions are used to add attribute reading
425 /// DigraphReader<Digraph>(digraph, std::cin).
426 /// nodeMap("coordinates", coord_map).
427 /// arcMap("capacity", cap_map).
428 /// node("source", src).
429 /// node("target", trg).
430 /// attribute("caption", caption).
434 /// By default the reader uses the first section in the file of the
435 /// proper type. If a section has an optional name, then it can be
436 /// selected for reading by giving an optional name parameter to the
437 /// \c nodes(), \c arcs() or \c attributes() functions.
439 /// The \c useNodes() and \c useArcs() functions are used to tell the reader
440 /// that the nodes or arcs should not be constructed (added to the
441 /// graph) during the reading, but instead the label map of the items
442 /// are given as a parameter of these functions. An
443 /// application of these functions is multipass reading, which is
444 /// important if two \c \@arcs sections must be read from the
445 /// file. In this case the first phase would read the node set and one
446 /// of the arc sets, while the second phase would read the second arc
447 /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
448 /// The previously read label node map should be passed to the \c
449 /// useNodes() functions. Another application of multipass reading when
450 /// paths are given as a node map or an arc map.
451 /// It is impossible to read this in
452 /// a single pass, because the arcs are not constructed when the node
454 template <typename _Digraph>
455 class DigraphReader {
458 typedef _Digraph Digraph;
459 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
466 std::string _filename;
470 std::string _nodes_caption;
471 std::string _arcs_caption;
472 std::string _attributes_caption;
474 typedef std::map<std::string, Node> NodeIndex;
475 NodeIndex _node_index;
476 typedef std::map<std::string, Arc> ArcIndex;
479 typedef std::vector<std::pair<std::string,
480 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
483 typedef std::vector<std::pair<std::string,
484 _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
487 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
489 Attributes _attributes;
498 std::istringstream line;
502 /// \brief Constructor
504 /// Construct a directed graph reader, which reads from the given
506 DigraphReader(Digraph& digraph, std::istream& is = std::cin)
507 : _is(&is), local_is(false), _digraph(digraph),
508 _use_nodes(false), _use_arcs(false),
509 _skip_nodes(false), _skip_arcs(false) {}
511 /// \brief Constructor
513 /// Construct a directed graph reader, which reads from the given
515 DigraphReader(Digraph& digraph, const std::string& fn)
516 : _is(new std::ifstream(fn.c_str())), local_is(true),
517 _filename(fn), _digraph(digraph),
518 _use_nodes(false), _use_arcs(false),
519 _skip_nodes(false), _skip_arcs(false) {
520 if (!(*_is)) 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) {
532 if (!(*_is)) throw IoError("Cannot open file", fn);
535 /// \brief Destructor
537 for (typename NodeMaps::iterator it = _node_maps.begin();
538 it != _node_maps.end(); ++it) {
542 for (typename ArcMaps::iterator it = _arc_maps.begin();
543 it != _arc_maps.end(); ++it) {
547 for (typename Attributes::iterator it = _attributes.begin();
548 it != _attributes.end(); ++it) {
560 friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
562 friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
563 const std::string& fn);
564 friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
567 DigraphReader(DigraphReader& other)
568 : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
569 _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
570 _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
573 other.local_is = false;
575 _node_index.swap(other._node_index);
576 _arc_index.swap(other._arc_index);
578 _node_maps.swap(other._node_maps);
579 _arc_maps.swap(other._arc_maps);
580 _attributes.swap(other._attributes);
582 _nodes_caption = other._nodes_caption;
583 _arcs_caption = other._arcs_caption;
584 _attributes_caption = other._attributes_caption;
588 DigraphReader& operator=(const DigraphReader&);
592 /// \name Reading rules
595 /// \brief Node map reading rule
597 /// Add a node map reading rule to the reader.
598 template <typename Map>
599 DigraphReader& nodeMap(const std::string& caption, Map& map) {
600 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
601 _reader_bits::MapStorageBase<Node>* storage =
602 new _reader_bits::MapStorage<Node, Map>(map);
603 _node_maps.push_back(std::make_pair(caption, storage));
607 /// \brief Node map reading rule
609 /// Add a node map reading rule with specialized converter to the
611 template <typename Map, typename Converter>
612 DigraphReader& nodeMap(const std::string& caption, Map& map,
613 const Converter& converter = Converter()) {
614 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
615 _reader_bits::MapStorageBase<Node>* storage =
616 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
617 _node_maps.push_back(std::make_pair(caption, storage));
621 /// \brief Arc map reading rule
623 /// Add an arc map reading rule to the reader.
624 template <typename Map>
625 DigraphReader& arcMap(const std::string& caption, Map& map) {
626 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
627 _reader_bits::MapStorageBase<Arc>* storage =
628 new _reader_bits::MapStorage<Arc, Map>(map);
629 _arc_maps.push_back(std::make_pair(caption, storage));
633 /// \brief Arc map reading rule
635 /// Add an arc map reading rule with specialized converter to the
637 template <typename Map, typename Converter>
638 DigraphReader& arcMap(const std::string& caption, Map& map,
639 const Converter& converter = Converter()) {
640 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
641 _reader_bits::MapStorageBase<Arc>* storage =
642 new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
643 _arc_maps.push_back(std::make_pair(caption, storage));
647 /// \brief Attribute reading rule
649 /// Add an attribute reading rule to the reader.
650 template <typename Value>
651 DigraphReader& attribute(const std::string& caption, Value& value) {
652 _reader_bits::ValueStorageBase* storage =
653 new _reader_bits::ValueStorage<Value>(value);
654 _attributes.insert(std::make_pair(caption, storage));
658 /// \brief Attribute reading rule
660 /// Add an attribute reading rule with specialized converter to the
662 template <typename Value, typename Converter>
663 DigraphReader& attribute(const std::string& caption, Value& value,
664 const Converter& converter = Converter()) {
665 _reader_bits::ValueStorageBase* storage =
666 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
667 _attributes.insert(std::make_pair(caption, storage));
671 /// \brief Node reading rule
673 /// Add a node reading rule to reader.
674 DigraphReader& node(const std::string& caption, Node& node) {
675 typedef _reader_bits::MapLookUpConverter<Node> Converter;
676 Converter converter(_node_index);
677 _reader_bits::ValueStorageBase* storage =
678 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
679 _attributes.insert(std::make_pair(caption, storage));
683 /// \brief Arc reading rule
685 /// Add an arc reading rule to reader.
686 DigraphReader& arc(const std::string& caption, Arc& arc) {
687 typedef _reader_bits::MapLookUpConverter<Arc> Converter;
688 Converter converter(_arc_index);
689 _reader_bits::ValueStorageBase* storage =
690 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
691 _attributes.insert(std::make_pair(caption, storage));
697 /// \name Select section by name
700 /// \brief Set \c \@nodes section to be read
702 /// Set \c \@nodes section to be read
703 DigraphReader& nodes(const std::string& caption) {
704 _nodes_caption = caption;
708 /// \brief Set \c \@arcs section to be read
710 /// Set \c \@arcs section to be read
711 DigraphReader& arcs(const std::string& caption) {
712 _arcs_caption = caption;
716 /// \brief Set \c \@attributes section to be read
718 /// Set \c \@attributes section to be read
719 DigraphReader& attributes(const std::string& caption) {
720 _attributes_caption = caption;
726 /// \name Using previously constructed node or arc set
729 /// \brief Use previously constructed node set
731 /// Use previously constructed node set, and specify the node
733 template <typename Map>
734 DigraphReader& useNodes(const Map& map) {
735 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
736 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
738 _writer_bits::DefaultConverter<typename Map::Value> converter;
739 for (NodeIt n(_digraph); n != INVALID; ++n) {
740 _node_index.insert(std::make_pair(converter(map[n]), n));
745 /// \brief Use previously constructed node set
747 /// Use previously constructed node set, and specify the node
748 /// label map and a functor which converts the label map values to
750 template <typename Map, typename Converter>
751 DigraphReader& useNodes(const Map& map,
752 const Converter& converter = Converter()) {
753 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
754 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
756 for (NodeIt n(_digraph); n != INVALID; ++n) {
757 _node_index.insert(std::make_pair(converter(map[n]), n));
762 /// \brief Use previously constructed arc set
764 /// Use previously constructed arc set, and specify the arc
766 template <typename Map>
767 DigraphReader& useArcs(const Map& map) {
768 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
769 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
771 _writer_bits::DefaultConverter<typename Map::Value> converter;
772 for (ArcIt a(_digraph); a != INVALID; ++a) {
773 _arc_index.insert(std::make_pair(converter(map[a]), a));
778 /// \brief Use previously constructed arc set
780 /// Use previously constructed arc set, and specify the arc
781 /// label map and a functor which converts the label map values to
783 template <typename Map, typename Converter>
784 DigraphReader& useArcs(const Map& map,
785 const Converter& converter = Converter()) {
786 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
787 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
789 for (ArcIt a(_digraph); a != INVALID; ++a) {
790 _arc_index.insert(std::make_pair(converter(map[a]), a));
795 /// \brief Skips the reading of node section
797 /// Omit the reading of the node section. This implies that each node
798 /// map reading rule will be abandoned, and the nodes of the graph
799 /// will not be constructed, which usually cause that the arc set
800 /// could not be read due to lack of node name resolving.
801 /// Therefore \c skipArcs() function should also be used, or
802 /// \c useNodes() should be used to specify the label of the nodes.
803 DigraphReader& skipNodes() {
804 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
809 /// \brief Skips the reading of arc section
811 /// Omit the reading of the arc section. This implies that each arc
812 /// map reading rule will be abandoned, and the arcs of the graph
813 /// will not be constructed.
814 DigraphReader& skipArcs() {
815 LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
826 while(++line_num, std::getline(*_is, str)) {
827 line.clear(); line.str(str);
829 if (line >> std::ws >> c && c != '#') {
838 return static_cast<bool>(*_is);
843 while (readSuccess() && line >> c && c != '@') {
851 std::vector<int> map_index(_node_maps.size());
852 int map_num, label_index;
855 if (!readLine() || !(line >> c) || c == '@') {
856 if (readSuccess() && line) line.putback(c);
857 if (!_node_maps.empty())
858 throw FormatError("Cannot find map names");
864 std::map<std::string, int> maps;
868 while (_reader_bits::readToken(line, map)) {
869 if (maps.find(map) != maps.end()) {
870 std::ostringstream msg;
871 msg << "Multiple occurence of node map: " << map;
872 throw FormatError(msg.str());
874 maps.insert(std::make_pair(map, index));
878 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
879 std::map<std::string, int>::iterator jt =
880 maps.find(_node_maps[i].first);
881 if (jt == maps.end()) {
882 std::ostringstream msg;
883 msg << "Map not found: " << _node_maps[i].first;
884 throw FormatError(msg.str());
886 map_index[i] = jt->second;
890 std::map<std::string, int>::iterator jt = maps.find("label");
891 if (jt != maps.end()) {
892 label_index = jt->second;
897 map_num = maps.size();
900 while (readLine() && line >> c && c != '@') {
903 std::vector<std::string> tokens(map_num);
904 for (int i = 0; i < map_num; ++i) {
905 if (!_reader_bits::readToken(line, tokens[i])) {
906 std::ostringstream msg;
907 msg << "Column not found (" << i + 1 << ")";
908 throw FormatError(msg.str());
911 if (line >> std::ws >> c)
912 throw FormatError("Extra character at the end of line");
916 n = _digraph.addNode();
917 if (label_index != -1)
918 _node_index.insert(std::make_pair(tokens[label_index], n));
920 if (label_index == -1)
921 throw FormatError("Label map not found");
922 typename std::map<std::string, Node>::iterator it =
923 _node_index.find(tokens[label_index]);
924 if (it == _node_index.end()) {
925 std::ostringstream msg;
926 msg << "Node with label not found: " << tokens[label_index];
927 throw FormatError(msg.str());
932 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
933 _node_maps[i].second->set(n, tokens[map_index[i]]);
944 std::vector<int> map_index(_arc_maps.size());
945 int map_num, label_index;
948 if (!readLine() || !(line >> c) || c == '@') {
949 if (readSuccess() && line) line.putback(c);
950 if (!_arc_maps.empty())
951 throw FormatError("Cannot find map names");
957 std::map<std::string, int> maps;
961 while (_reader_bits::readToken(line, map)) {
962 if (maps.find(map) != maps.end()) {
963 std::ostringstream msg;
964 msg << "Multiple occurence of arc map: " << map;
965 throw FormatError(msg.str());
967 maps.insert(std::make_pair(map, index));
971 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
972 std::map<std::string, int>::iterator jt =
973 maps.find(_arc_maps[i].first);
974 if (jt == maps.end()) {
975 std::ostringstream msg;
976 msg << "Map not found: " << _arc_maps[i].first;
977 throw FormatError(msg.str());
979 map_index[i] = jt->second;
983 std::map<std::string, int>::iterator jt = maps.find("label");
984 if (jt != maps.end()) {
985 label_index = jt->second;
990 map_num = maps.size();
993 while (readLine() && line >> c && c != '@') {
996 std::string source_token;
997 std::string target_token;
999 if (!_reader_bits::readToken(line, source_token))
1000 throw FormatError("Source not found");
1002 if (!_reader_bits::readToken(line, target_token))
1003 throw FormatError("Target not found");
1005 std::vector<std::string> tokens(map_num);
1006 for (int i = 0; i < map_num; ++i) {
1007 if (!_reader_bits::readToken(line, tokens[i])) {
1008 std::ostringstream msg;
1009 msg << "Column not found (" << i + 1 << ")";
1010 throw FormatError(msg.str());
1013 if (line >> std::ws >> c)
1014 throw FormatError("Extra character at the end of line");
1019 typename NodeIndex::iterator it;
1021 it = _node_index.find(source_token);
1022 if (it == _node_index.end()) {
1023 std::ostringstream msg;
1024 msg << "Item not found: " << source_token;
1025 throw FormatError(msg.str());
1027 Node source = it->second;
1029 it = _node_index.find(target_token);
1030 if (it == _node_index.end()) {
1031 std::ostringstream msg;
1032 msg << "Item not found: " << target_token;
1033 throw FormatError(msg.str());
1035 Node target = it->second;
1037 a = _digraph.addArc(source, target);
1038 if (label_index != -1)
1039 _arc_index.insert(std::make_pair(tokens[label_index], a));
1041 if (label_index == -1)
1042 throw FormatError("Label map not found");
1043 typename std::map<std::string, Arc>::iterator it =
1044 _arc_index.find(tokens[label_index]);
1045 if (it == _arc_index.end()) {
1046 std::ostringstream msg;
1047 msg << "Arc with label not found: " << tokens[label_index];
1048 throw FormatError(msg.str());
1053 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1054 _arc_maps[i].second->set(a, tokens[map_index[i]]);
1058 if (readSuccess()) {
1063 void readAttributes() {
1065 std::set<std::string> read_attr;
1068 while (readLine() && line >> c && c != '@') {
1071 std::string attr, token;
1072 if (!_reader_bits::readToken(line, attr))
1073 throw FormatError("Attribute name not found");
1074 if (!_reader_bits::readToken(line, token))
1075 throw FormatError("Attribute value not found");
1077 throw FormatError("Extra character at the end of line");
1080 std::set<std::string>::iterator it = read_attr.find(attr);
1081 if (it != read_attr.end()) {
1082 std::ostringstream msg;
1083 msg << "Multiple occurence of attribute: " << attr;
1084 throw FormatError(msg.str());
1086 read_attr.insert(attr);
1090 typename Attributes::iterator it = _attributes.lower_bound(attr);
1091 while (it != _attributes.end() && it->first == attr) {
1092 it->second->set(token);
1098 if (readSuccess()) {
1101 for (typename Attributes::iterator it = _attributes.begin();
1102 it != _attributes.end(); ++it) {
1103 if (read_attr.find(it->first) == read_attr.end()) {
1104 std::ostringstream msg;
1105 msg << "Attribute not found: " << it->first;
1106 throw FormatError(msg.str());
1113 /// \name Execution of the reader
1116 /// \brief Start the batch processing
1118 /// This function starts the batch processing
1120 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1122 bool nodes_done = _skip_nodes;
1123 bool arcs_done = _skip_arcs;
1124 bool attributes_done = false;
1130 while (readSuccess()) {
1133 std::string section, caption;
1135 _reader_bits::readToken(line, section);
1136 _reader_bits::readToken(line, caption);
1139 throw FormatError("Extra character at the end of line");
1141 if (section == "nodes" && !nodes_done) {
1142 if (_nodes_caption.empty() || _nodes_caption == caption) {
1146 } else if ((section == "arcs" || section == "edges") &&
1148 if (_arcs_caption.empty() || _arcs_caption == caption) {
1152 } else if (section == "attributes" && !attributes_done) {
1153 if (_attributes_caption.empty() || _attributes_caption == caption) {
1155 attributes_done = true;
1161 } catch (FormatError& error) {
1162 error.line(line_num);
1163 error.file(_filename);
1169 throw FormatError("Section @nodes not found");
1173 throw FormatError("Section @arcs not found");
1176 if (!attributes_done && !_attributes.empty()) {
1177 throw FormatError("Section @attributes not found");
1186 /// \brief Return a \ref DigraphReader class
1188 /// This function just returns a \ref DigraphReader class.
1189 /// \relates DigraphReader
1190 template <typename Digraph>
1191 DigraphReader<Digraph> digraphReader(Digraph& digraph,
1192 std::istream& is = std::cin) {
1193 DigraphReader<Digraph> tmp(digraph, is);
1197 /// \brief Return a \ref DigraphReader class
1199 /// This function just returns a \ref DigraphReader class.
1200 /// \relates DigraphReader
1201 template <typename Digraph>
1202 DigraphReader<Digraph> digraphReader(Digraph& digraph,
1203 const std::string& fn) {
1204 DigraphReader<Digraph> tmp(digraph, fn);
1208 /// \brief Return a \ref DigraphReader class
1210 /// This function just returns a \ref DigraphReader class.
1211 /// \relates DigraphReader
1212 template <typename Digraph>
1213 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
1214 DigraphReader<Digraph> tmp(digraph, fn);
1218 template <typename Graph>
1221 template <typename Graph>
1222 GraphReader<Graph> graphReader(Graph& graph,
1223 std::istream& is = std::cin);
1225 template <typename Graph>
1226 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
1228 template <typename Graph>
1229 GraphReader<Graph> graphReader(Graph& graph, const char *fn);
1231 /// \ingroup lemon_io
1233 /// \brief \ref lgf-format "LGF" reader for undirected graphs
1235 /// This utility reads an \ref lgf-format "LGF" file.
1237 /// It can be used almost the same way as \c DigraphReader.
1238 /// The only difference is that this class can handle edges and
1239 /// edge maps as well as arcs and arc maps.
1241 /// The columns in the \c \@edges (or \c \@arcs) section are the
1242 /// edge maps. However, if there are two maps with the same name
1243 /// prefixed with \c '+' and \c '-', then these can be read into an
1244 /// arc map. Similarly, an attribute can be read into an arc, if
1245 /// it's value is an edge label prefixed with \c '+' or \c '-'.
1246 template <typename _Graph>
1250 typedef _Graph Graph;
1251 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1257 std::string _filename;
1261 std::string _nodes_caption;
1262 std::string _edges_caption;
1263 std::string _attributes_caption;
1265 typedef std::map<std::string, Node> NodeIndex;
1266 NodeIndex _node_index;
1267 typedef std::map<std::string, Edge> EdgeIndex;
1268 EdgeIndex _edge_index;
1270 typedef std::vector<std::pair<std::string,
1271 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
1272 NodeMaps _node_maps;
1274 typedef std::vector<std::pair<std::string,
1275 _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1276 EdgeMaps _edge_maps;
1278 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1280 Attributes _attributes;
1289 std::istringstream line;
1293 /// \brief Constructor
1295 /// Construct an undirected graph reader, which reads from the given
1297 GraphReader(Graph& graph, std::istream& is = std::cin)
1298 : _is(&is), local_is(false), _graph(graph),
1299 _use_nodes(false), _use_edges(false),
1300 _skip_nodes(false), _skip_edges(false) {}
1302 /// \brief Constructor
1304 /// Construct an undirected graph reader, which reads from the given
1306 GraphReader(Graph& graph, const std::string& fn)
1307 : _is(new std::ifstream(fn.c_str())), local_is(true),
1308 _filename(fn), _graph(graph),
1309 _use_nodes(false), _use_edges(false),
1310 _skip_nodes(false), _skip_edges(false) {
1311 if (!(*_is)) throw IoError("Cannot open file", fn);
1314 /// \brief Constructor
1316 /// Construct an undirected graph reader, which reads from the given
1318 GraphReader(Graph& graph, const char* fn)
1319 : _is(new std::ifstream(fn)), local_is(true),
1320 _filename(fn), _graph(graph),
1321 _use_nodes(false), _use_edges(false),
1322 _skip_nodes(false), _skip_edges(false) {
1323 if (!(*_is)) throw IoError("Cannot open file", fn);
1326 /// \brief Destructor
1328 for (typename NodeMaps::iterator it = _node_maps.begin();
1329 it != _node_maps.end(); ++it) {
1333 for (typename EdgeMaps::iterator it = _edge_maps.begin();
1334 it != _edge_maps.end(); ++it) {
1338 for (typename Attributes::iterator it = _attributes.begin();
1339 it != _attributes.end(); ++it) {
1350 friend GraphReader<Graph> graphReader<>(Graph& graph, std::istream& is);
1351 friend GraphReader<Graph> graphReader<>(Graph& graph,
1352 const std::string& fn);
1353 friend GraphReader<Graph> graphReader<>(Graph& graph, const char *fn);
1355 GraphReader(GraphReader& other)
1356 : _is(other._is), local_is(other.local_is), _graph(other._graph),
1357 _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1358 _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1361 other.local_is = false;
1363 _node_index.swap(other._node_index);
1364 _edge_index.swap(other._edge_index);
1366 _node_maps.swap(other._node_maps);
1367 _edge_maps.swap(other._edge_maps);
1368 _attributes.swap(other._attributes);
1370 _nodes_caption = other._nodes_caption;
1371 _edges_caption = other._edges_caption;
1372 _attributes_caption = other._attributes_caption;
1376 GraphReader& operator=(const GraphReader&);
1380 /// \name Reading rules
1383 /// \brief Node map reading rule
1385 /// Add a node map reading rule to the reader.
1386 template <typename Map>
1387 GraphReader& nodeMap(const std::string& caption, Map& map) {
1388 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1389 _reader_bits::MapStorageBase<Node>* storage =
1390 new _reader_bits::MapStorage<Node, Map>(map);
1391 _node_maps.push_back(std::make_pair(caption, storage));
1395 /// \brief Node map reading rule
1397 /// Add a node map reading rule with specialized converter to the
1399 template <typename Map, typename Converter>
1400 GraphReader& nodeMap(const std::string& caption, Map& map,
1401 const Converter& converter = Converter()) {
1402 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1403 _reader_bits::MapStorageBase<Node>* storage =
1404 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1405 _node_maps.push_back(std::make_pair(caption, storage));
1409 /// \brief Edge map reading rule
1411 /// Add an edge map reading rule to the reader.
1412 template <typename Map>
1413 GraphReader& edgeMap(const std::string& caption, Map& map) {
1414 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1415 _reader_bits::MapStorageBase<Edge>* storage =
1416 new _reader_bits::MapStorage<Edge, Map>(map);
1417 _edge_maps.push_back(std::make_pair(caption, storage));
1421 /// \brief Edge map reading rule
1423 /// Add an edge map reading rule with specialized converter to the
1425 template <typename Map, typename Converter>
1426 GraphReader& edgeMap(const std::string& caption, Map& map,
1427 const Converter& converter = Converter()) {
1428 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1429 _reader_bits::MapStorageBase<Edge>* storage =
1430 new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1431 _edge_maps.push_back(std::make_pair(caption, storage));
1435 /// \brief Arc map reading rule
1437 /// Add an arc map reading rule to the reader.
1438 template <typename Map>
1439 GraphReader& arcMap(const std::string& caption, Map& map) {
1440 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1441 _reader_bits::MapStorageBase<Edge>* forward_storage =
1442 new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1443 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1444 _reader_bits::MapStorageBase<Edge>* backward_storage =
1445 new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1446 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1450 /// \brief Arc map reading rule
1452 /// Add an arc map reading rule with specialized converter to the
1454 template <typename Map, typename Converter>
1455 GraphReader& arcMap(const std::string& caption, Map& map,
1456 const Converter& converter = Converter()) {
1457 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1458 _reader_bits::MapStorageBase<Edge>* forward_storage =
1459 new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1460 (_graph, map, converter);
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, Converter>
1464 (_graph, map, converter);
1465 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1469 /// \brief Attribute reading rule
1471 /// Add an attribute reading rule to the reader.
1472 template <typename Value>
1473 GraphReader& attribute(const std::string& caption, Value& value) {
1474 _reader_bits::ValueStorageBase* storage =
1475 new _reader_bits::ValueStorage<Value>(value);
1476 _attributes.insert(std::make_pair(caption, storage));
1480 /// \brief Attribute reading rule
1482 /// Add an attribute reading rule with specialized converter to the
1484 template <typename Value, typename Converter>
1485 GraphReader& attribute(const std::string& caption, Value& value,
1486 const Converter& converter = Converter()) {
1487 _reader_bits::ValueStorageBase* storage =
1488 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1489 _attributes.insert(std::make_pair(caption, storage));
1493 /// \brief Node reading rule
1495 /// Add a node reading rule to reader.
1496 GraphReader& node(const std::string& caption, Node& node) {
1497 typedef _reader_bits::MapLookUpConverter<Node> Converter;
1498 Converter converter(_node_index);
1499 _reader_bits::ValueStorageBase* storage =
1500 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1501 _attributes.insert(std::make_pair(caption, storage));
1505 /// \brief Edge reading rule
1507 /// Add an edge reading rule to reader.
1508 GraphReader& edge(const std::string& caption, Edge& edge) {
1509 typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1510 Converter converter(_edge_index);
1511 _reader_bits::ValueStorageBase* storage =
1512 new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1513 _attributes.insert(std::make_pair(caption, storage));
1517 /// \brief Arc reading rule
1519 /// Add an arc reading rule to reader.
1520 GraphReader& arc(const std::string& caption, Arc& arc) {
1521 typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
1522 Converter converter(_graph, _edge_index);
1523 _reader_bits::ValueStorageBase* storage =
1524 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1525 _attributes.insert(std::make_pair(caption, storage));
1531 /// \name Select section by name
1534 /// \brief Set \c \@nodes section to be read
1536 /// Set \c \@nodes section to be read.
1537 GraphReader& nodes(const std::string& caption) {
1538 _nodes_caption = caption;
1542 /// \brief Set \c \@edges section to be read
1544 /// Set \c \@edges section to be read.
1545 GraphReader& edges(const std::string& caption) {
1546 _edges_caption = caption;
1550 /// \brief Set \c \@attributes section to be read
1552 /// Set \c \@attributes section to be read.
1553 GraphReader& attributes(const std::string& caption) {
1554 _attributes_caption = caption;
1560 /// \name Using previously constructed node or edge set
1563 /// \brief Use previously constructed node set
1565 /// Use previously constructed node set, and specify the node
1567 template <typename Map>
1568 GraphReader& useNodes(const Map& map) {
1569 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1570 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1572 _writer_bits::DefaultConverter<typename Map::Value> converter;
1573 for (NodeIt n(_graph); n != INVALID; ++n) {
1574 _node_index.insert(std::make_pair(converter(map[n]), n));
1579 /// \brief Use previously constructed node set
1581 /// Use previously constructed node set, and specify the node
1582 /// label map and a functor which converts the label map values to
1584 template <typename Map, typename Converter>
1585 GraphReader& useNodes(const Map& map,
1586 const Converter& converter = Converter()) {
1587 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1588 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1590 for (NodeIt n(_graph); n != INVALID; ++n) {
1591 _node_index.insert(std::make_pair(converter(map[n]), n));
1596 /// \brief Use previously constructed edge set
1598 /// Use previously constructed edge set, and specify the edge
1600 template <typename Map>
1601 GraphReader& useEdges(const Map& map) {
1602 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1603 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1605 _writer_bits::DefaultConverter<typename Map::Value> converter;
1606 for (EdgeIt a(_graph); a != INVALID; ++a) {
1607 _edge_index.insert(std::make_pair(converter(map[a]), a));
1612 /// \brief Use previously constructed edge set
1614 /// Use previously constructed edge set, and specify the edge
1615 /// label map and a functor which converts the label map values to
1617 template <typename Map, typename Converter>
1618 GraphReader& useEdges(const Map& map,
1619 const Converter& converter = Converter()) {
1620 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1621 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1623 for (EdgeIt a(_graph); a != INVALID; ++a) {
1624 _edge_index.insert(std::make_pair(converter(map[a]), a));
1629 /// \brief Skip the reading of node section
1631 /// Omit the reading of the node section. This implies that each node
1632 /// map reading rule will be abandoned, and the nodes of the graph
1633 /// will not be constructed, which usually cause that the edge set
1634 /// could not be read due to lack of node name
1635 /// could not be read due to lack of node name resolving.
1636 /// Therefore \c skipEdges() function should also be used, or
1637 /// \c useNodes() should be used to specify the label of the nodes.
1638 GraphReader& skipNodes() {
1639 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1644 /// \brief Skip the reading of edge section
1646 /// Omit the reading of the edge section. This implies that each edge
1647 /// map reading rule will be abandoned, and the edges of the graph
1648 /// will not be constructed.
1649 GraphReader& skipEdges() {
1650 LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1661 while(++line_num, std::getline(*_is, str)) {
1662 line.clear(); line.str(str);
1664 if (line >> std::ws >> c && c != '#') {
1672 bool readSuccess() {
1673 return static_cast<bool>(*_is);
1676 void skipSection() {
1678 while (readSuccess() && line >> c && c != '@') {
1686 std::vector<int> map_index(_node_maps.size());
1687 int map_num, label_index;
1690 if (!readLine() || !(line >> c) || c == '@') {
1691 if (readSuccess() && line) line.putback(c);
1692 if (!_node_maps.empty())
1693 throw FormatError("Cannot find map names");
1699 std::map<std::string, int> maps;
1703 while (_reader_bits::readToken(line, map)) {
1704 if (maps.find(map) != maps.end()) {
1705 std::ostringstream msg;
1706 msg << "Multiple occurence of node map: " << map;
1707 throw FormatError(msg.str());
1709 maps.insert(std::make_pair(map, index));
1713 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1714 std::map<std::string, int>::iterator jt =
1715 maps.find(_node_maps[i].first);
1716 if (jt == maps.end()) {
1717 std::ostringstream msg;
1718 msg << "Map not found: " << _node_maps[i].first;
1719 throw FormatError(msg.str());
1721 map_index[i] = jt->second;
1725 std::map<std::string, int>::iterator jt = maps.find("label");
1726 if (jt != maps.end()) {
1727 label_index = jt->second;
1732 map_num = maps.size();
1735 while (readLine() && line >> c && c != '@') {
1738 std::vector<std::string> tokens(map_num);
1739 for (int i = 0; i < map_num; ++i) {
1740 if (!_reader_bits::readToken(line, tokens[i])) {
1741 std::ostringstream msg;
1742 msg << "Column not found (" << i + 1 << ")";
1743 throw FormatError(msg.str());
1746 if (line >> std::ws >> c)
1747 throw FormatError("Extra character at the end of line");
1751 n = _graph.addNode();
1752 if (label_index != -1)
1753 _node_index.insert(std::make_pair(tokens[label_index], n));
1755 if (label_index == -1)
1756 throw FormatError("Label map not found");
1757 typename std::map<std::string, Node>::iterator it =
1758 _node_index.find(tokens[label_index]);
1759 if (it == _node_index.end()) {
1760 std::ostringstream msg;
1761 msg << "Node with label not found: " << tokens[label_index];
1762 throw FormatError(msg.str());
1767 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1768 _node_maps[i].second->set(n, tokens[map_index[i]]);
1772 if (readSuccess()) {
1779 std::vector<int> map_index(_edge_maps.size());
1780 int map_num, label_index;
1783 if (!readLine() || !(line >> c) || c == '@') {
1784 if (readSuccess() && line) line.putback(c);
1785 if (!_edge_maps.empty())
1786 throw FormatError("Cannot find map names");
1792 std::map<std::string, int> maps;
1796 while (_reader_bits::readToken(line, map)) {
1797 if (maps.find(map) != maps.end()) {
1798 std::ostringstream msg;
1799 msg << "Multiple occurence of edge map: " << map;
1800 throw FormatError(msg.str());
1802 maps.insert(std::make_pair(map, index));
1806 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1807 std::map<std::string, int>::iterator jt =
1808 maps.find(_edge_maps[i].first);
1809 if (jt == maps.end()) {
1810 std::ostringstream msg;
1811 msg << "Map not found: " << _edge_maps[i].first;
1812 throw FormatError(msg.str());
1814 map_index[i] = jt->second;
1818 std::map<std::string, int>::iterator jt = maps.find("label");
1819 if (jt != maps.end()) {
1820 label_index = jt->second;
1825 map_num = maps.size();
1828 while (readLine() && line >> c && c != '@') {
1831 std::string source_token;
1832 std::string target_token;
1834 if (!_reader_bits::readToken(line, source_token))
1835 throw FormatError("Node u not found");
1837 if (!_reader_bits::readToken(line, target_token))
1838 throw FormatError("Node v not found");
1840 std::vector<std::string> tokens(map_num);
1841 for (int i = 0; i < map_num; ++i) {
1842 if (!_reader_bits::readToken(line, tokens[i])) {
1843 std::ostringstream msg;
1844 msg << "Column not found (" << i + 1 << ")";
1845 throw FormatError(msg.str());
1848 if (line >> std::ws >> c)
1849 throw FormatError("Extra character at the end of line");
1854 typename NodeIndex::iterator it;
1856 it = _node_index.find(source_token);
1857 if (it == _node_index.end()) {
1858 std::ostringstream msg;
1859 msg << "Item not found: " << source_token;
1860 throw FormatError(msg.str());
1862 Node source = it->second;
1864 it = _node_index.find(target_token);
1865 if (it == _node_index.end()) {
1866 std::ostringstream msg;
1867 msg << "Item not found: " << target_token;
1868 throw FormatError(msg.str());
1870 Node target = it->second;
1872 e = _graph.addEdge(source, target);
1873 if (label_index != -1)
1874 _edge_index.insert(std::make_pair(tokens[label_index], e));
1876 if (label_index == -1)
1877 throw FormatError("Label map not found");
1878 typename std::map<std::string, Edge>::iterator it =
1879 _edge_index.find(tokens[label_index]);
1880 if (it == _edge_index.end()) {
1881 std::ostringstream msg;
1882 msg << "Edge with label not found: " << tokens[label_index];
1883 throw FormatError(msg.str());
1888 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1889 _edge_maps[i].second->set(e, tokens[map_index[i]]);
1893 if (readSuccess()) {
1898 void readAttributes() {
1900 std::set<std::string> read_attr;
1903 while (readLine() && line >> c && c != '@') {
1906 std::string attr, token;
1907 if (!_reader_bits::readToken(line, attr))
1908 throw FormatError("Attribute name not found");
1909 if (!_reader_bits::readToken(line, token))
1910 throw FormatError("Attribute value not found");
1912 throw FormatError("Extra character at the end of line");
1915 std::set<std::string>::iterator it = read_attr.find(attr);
1916 if (it != read_attr.end()) {
1917 std::ostringstream msg;
1918 msg << "Multiple occurence of attribute: " << attr;
1919 throw FormatError(msg.str());
1921 read_attr.insert(attr);
1925 typename Attributes::iterator it = _attributes.lower_bound(attr);
1926 while (it != _attributes.end() && it->first == attr) {
1927 it->second->set(token);
1933 if (readSuccess()) {
1936 for (typename Attributes::iterator it = _attributes.begin();
1937 it != _attributes.end(); ++it) {
1938 if (read_attr.find(it->first) == read_attr.end()) {
1939 std::ostringstream msg;
1940 msg << "Attribute not found: " << it->first;
1941 throw FormatError(msg.str());
1948 /// \name Execution of the reader
1951 /// \brief Start the batch processing
1953 /// This function starts the batch processing
1956 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1958 bool nodes_done = _skip_nodes;
1959 bool edges_done = _skip_edges;
1960 bool attributes_done = false;
1966 while (readSuccess()) {
1969 std::string section, caption;
1971 _reader_bits::readToken(line, section);
1972 _reader_bits::readToken(line, caption);
1975 throw FormatError("Extra character at the end of line");
1977 if (section == "nodes" && !nodes_done) {
1978 if (_nodes_caption.empty() || _nodes_caption == caption) {
1982 } else if ((section == "edges" || section == "arcs") &&
1984 if (_edges_caption.empty() || _edges_caption == caption) {
1988 } else if (section == "attributes" && !attributes_done) {
1989 if (_attributes_caption.empty() || _attributes_caption == caption) {
1991 attributes_done = true;
1997 } catch (FormatError& error) {
1998 error.line(line_num);
1999 error.file(_filename);
2005 throw FormatError("Section @nodes not found");
2009 throw FormatError("Section @edges not found");
2012 if (!attributes_done && !_attributes.empty()) {
2013 throw FormatError("Section @attributes not found");
2022 /// \brief Return a \ref GraphReader class
2024 /// This function just returns a \ref GraphReader class.
2025 /// \relates GraphReader
2026 template <typename Graph>
2027 GraphReader<Graph> graphReader(Graph& graph, std::istream& is = std::cin) {
2028 GraphReader<Graph> tmp(graph, is);
2032 /// \brief Return a \ref GraphReader class
2034 /// This function just returns a \ref GraphReader class.
2035 /// \relates GraphReader
2036 template <typename Graph>
2037 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
2038 GraphReader<Graph> tmp(graph, fn);
2042 /// \brief Return a \ref GraphReader class
2044 /// This function just returns a \ref GraphReader class.
2045 /// \relates GraphReader
2046 template <typename Graph>
2047 GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
2048 GraphReader<Graph> tmp(graph, fn);
2052 class SectionReader;
2054 SectionReader sectionReader(std::istream& is);
2055 SectionReader sectionReader(const std::string& fn);
2056 SectionReader sectionReader(const char* fn);
2058 /// \ingroup lemon_io
2060 /// \brief Section reader class
2062 /// In the \ref lgf-format "LGF" file extra sections can be placed,
2063 /// which contain any data in arbitrary format. Such sections can be
2064 /// read with this class. A reading rule can be added to the class
2065 /// with two different functions. With the \c sectionLines() function a
2066 /// functor can process the section line-by-line, while with the \c
2067 /// sectionStream() member the section can be read from an input
2069 class SectionReader {
2074 std::string _filename;
2076 typedef std::map<std::string, _reader_bits::Section*> Sections;
2080 std::istringstream line;
2084 /// \brief Constructor
2086 /// Construct a section reader, which reads from the given input
2088 SectionReader(std::istream& is)
2089 : _is(&is), local_is(false) {}
2091 /// \brief Constructor
2093 /// Construct a section reader, which reads from the given file.
2094 SectionReader(const std::string& fn)
2095 : _is(new std::ifstream(fn.c_str())), local_is(true),
2097 if (!(*_is)) throw IoError("Cannot open file", fn);
2100 /// \brief Constructor
2102 /// Construct a section reader, which reads from the given file.
2103 SectionReader(const char* fn)
2104 : _is(new std::ifstream(fn)), local_is(true),
2106 if (!(*_is)) throw IoError("Cannot open file", fn);
2109 /// \brief Destructor
2111 for (Sections::iterator it = _sections.begin();
2112 it != _sections.end(); ++it) {
2124 friend SectionReader sectionReader(std::istream& is);
2125 friend SectionReader sectionReader(const std::string& fn);
2126 friend SectionReader sectionReader(const char* fn);
2128 SectionReader(SectionReader& other)
2129 : _is(other._is), local_is(other.local_is) {
2132 other.local_is = false;
2134 _sections.swap(other._sections);
2137 SectionReader& operator=(const SectionReader&);
2141 /// \name Section readers
2144 /// \brief Add a section processor with line oriented reading
2146 /// The first parameter is the type descriptor of the section, the
2147 /// second is a functor, which takes just one \c std::string
2148 /// parameter. At the reading process, each line of the section
2149 /// will be given to the functor object. However, the empty lines
2150 /// and the comment lines are filtered out, and the leading
2151 /// whitespaces are trimmed from each processed string.
2153 /// For example let's see a section, which contain several
2154 /// integers, which should be inserted into a vector.
2162 /// The functor is implemented as a struct:
2164 /// struct NumberSection {
2165 /// std::vector<int>& _data;
2166 /// NumberSection(std::vector<int>& data) : _data(data) {}
2167 /// void operator()(const std::string& line) {
2168 /// std::istringstream ls(line);
2170 /// while (ls >> value) _data.push_back(value);
2176 /// reader.sectionLines("numbers", NumberSection(vec));
2178 template <typename Functor>
2179 SectionReader& sectionLines(const std::string& type, Functor functor) {
2180 LEMON_ASSERT(!type.empty(), "Type is empty.");
2181 LEMON_ASSERT(_sections.find(type) == _sections.end(),
2182 "Multiple reading of section.");
2183 _sections.insert(std::make_pair(type,
2184 new _reader_bits::LineSection<Functor>(functor)));
2189 /// \brief Add a section processor with stream oriented reading
2191 /// The first parameter is the type of the section, the second is
2192 /// a functor, which takes an \c std::istream& and an \c int&
2193 /// parameter, the latter regard to the line number of stream. The
2194 /// functor can read the input while the section go on, and the
2195 /// line number should be modified accordingly.
2196 template <typename Functor>
2197 SectionReader& sectionStream(const std::string& type, Functor functor) {
2198 LEMON_ASSERT(!type.empty(), "Type is empty.");
2199 LEMON_ASSERT(_sections.find(type) == _sections.end(),
2200 "Multiple reading of section.");
2201 _sections.insert(std::make_pair(type,
2202 new _reader_bits::StreamSection<Functor>(functor)));
2212 while(++line_num, std::getline(*_is, str)) {
2213 line.clear(); line.str(str);
2215 if (line >> std::ws >> c && c != '#') {
2223 bool readSuccess() {
2224 return static_cast<bool>(*_is);
2227 void skipSection() {
2229 while (readSuccess() && line >> c && c != '@') {
2238 /// \name Execution of the reader
2241 /// \brief Start the batch processing
2243 /// This function starts the batch processing.
2246 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2248 std::set<std::string> extra_sections;
2254 while (readSuccess()) {
2257 std::string section, caption;
2259 _reader_bits::readToken(line, section);
2260 _reader_bits::readToken(line, caption);
2263 throw FormatError("Extra character at the end of line");
2265 if (extra_sections.find(section) != extra_sections.end()) {
2266 std::ostringstream msg;
2267 msg << "Multiple occurence of section: " << section;
2268 throw FormatError(msg.str());
2270 Sections::iterator it = _sections.find(section);
2271 if (it != _sections.end()) {
2272 extra_sections.insert(section);
2273 it->second->process(*_is, line_num);
2277 } catch (FormatError& error) {
2278 error.line(line_num);
2279 error.file(_filename);
2283 for (Sections::iterator it = _sections.begin();
2284 it != _sections.end(); ++it) {
2285 if (extra_sections.find(it->first) == extra_sections.end()) {
2286 std::ostringstream os;
2287 os << "Cannot find section: " << it->first;
2288 throw FormatError(os.str());
2297 /// \brief Return a \ref SectionReader class
2299 /// This function just returns a \ref SectionReader class.
2300 /// \relates SectionReader
2301 inline SectionReader sectionReader(std::istream& is) {
2302 SectionReader tmp(is);
2306 /// \brief Return a \ref SectionReader class
2308 /// This function just returns a \ref SectionReader class.
2309 /// \relates SectionReader
2310 inline SectionReader sectionReader(const std::string& fn) {
2311 SectionReader tmp(fn);
2315 /// \brief Return a \ref SectionReader class
2317 /// This function just returns a \ref SectionReader class.
2318 /// \relates SectionReader
2319 inline SectionReader sectionReader(const char* fn) {
2320 SectionReader tmp(fn);
2324 /// \ingroup lemon_io
2326 /// \brief Reader for the contents of the \ref lgf-format "LGF" file
2328 /// This class can be used to read the sections, the map names and
2329 /// the attributes from a file. Usually, the LEMON programs know
2330 /// that, which type of graph, which maps and which attributes
2331 /// should be read from a file, but in general tools (like glemon)
2332 /// the contents of an LGF file should be guessed somehow. This class
2333 /// reads the graph and stores the appropriate information for
2334 /// reading the graph.
2337 /// LgfContents contents("graph.lgf");
2340 /// // Does it contain any node section and arc section?
2341 /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
2342 /// std::cerr << "Failure, cannot find graph." << std::endl;
2345 /// std::cout << "The name of the default node section: "
2346 /// << contents.nodeSection(0) << std::endl;
2347 /// std::cout << "The number of the arc maps: "
2348 /// << contents.arcMaps(0).size() << std::endl;
2349 /// std::cout << "The name of second arc map: "
2350 /// << contents.arcMaps(0)[1] << std::endl;
2358 std::vector<std::string> _node_sections;
2359 std::vector<std::string> _edge_sections;
2360 std::vector<std::string> _attribute_sections;
2361 std::vector<std::string> _extra_sections;
2363 std::vector<bool> _arc_sections;
2365 std::vector<std::vector<std::string> > _node_maps;
2366 std::vector<std::vector<std::string> > _edge_maps;
2368 std::vector<std::vector<std::string> > _attributes;
2372 std::istringstream line;
2376 /// \brief Constructor
2378 /// Construct an \e LGF contents reader, which reads from the given
2380 LgfContents(std::istream& is)
2381 : _is(&is), local_is(false) {}
2383 /// \brief Constructor
2385 /// Construct an \e LGF contents reader, which reads from the given
2387 LgfContents(const std::string& fn)
2388 : _is(new std::ifstream(fn.c_str())), local_is(true) {
2389 if (!(*_is)) throw IoError("Cannot open file", fn);
2392 /// \brief Constructor
2394 /// Construct an \e LGF contents reader, which reads from the given
2396 LgfContents(const char* fn)
2397 : _is(new std::ifstream(fn)), local_is(true) {
2398 if (!(*_is)) throw IoError("Cannot open file", fn);
2401 /// \brief Destructor
2403 if (local_is) delete _is;
2408 LgfContents(const LgfContents&);
2409 LgfContents& operator=(const LgfContents&);
2414 /// \name Node sections
2417 /// \brief Gives back the number of node sections in the file.
2419 /// Gives back the number of node sections in the file.
2420 int nodeSectionNum() const {
2421 return _node_sections.size();
2424 /// \brief Returns the node section name at the given position.
2426 /// Returns the node section name at the given position.
2427 const std::string& nodeSection(int i) const {
2428 return _node_sections[i];
2431 /// \brief Gives back the node maps for the given section.
2433 /// Gives back the node maps for the given section.
2434 const std::vector<std::string>& nodeMapNames(int i) const {
2435 return _node_maps[i];
2440 /// \name Arc/Edge sections
2443 /// \brief Gives back the number of arc/edge sections in the file.
2445 /// Gives back the number of arc/edge sections in the file.
2446 /// \note It is synonym of \c edgeSectionNum().
2447 int arcSectionNum() const {
2448 return _edge_sections.size();
2451 /// \brief Returns the arc/edge section name at the given position.
2453 /// Returns the arc/edge section name at the given position.
2454 /// \note It is synonym of \c edgeSection().
2455 const std::string& arcSection(int i) const {
2456 return _edge_sections[i];
2459 /// \brief Gives back the arc/edge maps for the given section.
2461 /// Gives back the arc/edge maps for the given section.
2462 /// \note It is synonym of \c edgeMapNames().
2463 const std::vector<std::string>& arcMapNames(int i) const {
2464 return _edge_maps[i];
2472 /// \brief Gives back the number of arc/edge sections in the file.
2474 /// Gives back the number of arc/edge sections in the file.
2475 /// \note It is synonym of \c arcSectionNum().
2476 int edgeSectionNum() const {
2477 return _edge_sections.size();
2480 /// \brief Returns the section name at the given position.
2482 /// Returns the section name at the given position.
2483 /// \note It is synonym of \c arcSection().
2484 const std::string& edgeSection(int i) const {
2485 return _edge_sections[i];
2488 /// \brief Gives back the edge maps for the given section.
2490 /// Gives back the edge maps for the given section.
2491 /// \note It is synonym of \c arcMapNames().
2492 const std::vector<std::string>& edgeMapNames(int i) const {
2493 return _edge_maps[i];
2498 /// \name Attribute sections
2501 /// \brief Gives back the number of attribute sections in the file.
2503 /// Gives back the number of attribute sections in the file.
2504 int attributeSectionNum() const {
2505 return _attribute_sections.size();
2508 /// \brief Returns the attribute section name at the given position.
2510 /// Returns the attribute section name at the given position.
2511 const std::string& attributeSectionNames(int i) const {
2512 return _attribute_sections[i];
2515 /// \brief Gives back the attributes for the given section.
2517 /// Gives back the attributes for the given section.
2518 const std::vector<std::string>& attributes(int i) const {
2519 return _attributes[i];
2524 /// \name Extra sections
2527 /// \brief Gives back the number of extra sections in the file.
2529 /// Gives back the number of extra sections in the file.
2530 int extraSectionNum() const {
2531 return _extra_sections.size();
2534 /// \brief Returns the extra section type at the given position.
2536 /// Returns the section type at the given position.
2537 const std::string& extraSection(int i) const {
2538 return _extra_sections[i];
2547 while(++line_num, std::getline(*_is, str)) {
2548 line.clear(); line.str(str);
2550 if (line >> std::ws >> c && c != '#') {
2558 bool readSuccess() {
2559 return static_cast<bool>(*_is);
2562 void skipSection() {
2564 while (readSuccess() && line >> c && c != '@') {
2570 void readMaps(std::vector<std::string>& maps) {
2572 if (!readLine() || !(line >> c) || c == '@') {
2573 if (readSuccess() && line) line.putback(c);
2578 while (_reader_bits::readToken(line, map)) {
2579 maps.push_back(map);
2583 void readAttributes(std::vector<std::string>& attrs) {
2586 while (readSuccess() && line >> c && c != '@') {
2589 _reader_bits::readToken(line, attr);
2590 attrs.push_back(attr);
2598 /// \name Execution of the contents reader
2601 /// \brief Starts the reading
2603 /// This function starts the reading.
2609 while (readSuccess()) {
2614 std::string section, caption;
2615 _reader_bits::readToken(line, section);
2616 _reader_bits::readToken(line, caption);
2618 if (section == "nodes") {
2619 _node_sections.push_back(caption);
2620 _node_maps.push_back(std::vector<std::string>());
2621 readMaps(_node_maps.back());
2622 readLine(); skipSection();
2623 } else if (section == "arcs" || section == "edges") {
2624 _edge_sections.push_back(caption);
2625 _arc_sections.push_back(section == "arcs");
2626 _edge_maps.push_back(std::vector<std::string>());
2627 readMaps(_edge_maps.back());
2628 readLine(); skipSection();
2629 } else if (section == "attributes") {
2630 _attribute_sections.push_back(caption);
2631 _attributes.push_back(std::vector<std::string>());
2632 readAttributes(_attributes.back());
2634 _extra_sections.push_back(section);
2635 readLine(); skipSection();