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);
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 inline bool isWhiteSpace(char c) {
199 return c == ' ' || c == '\t' || c == '\v' ||
200 c == '\n' || c == '\r' || c == '\f';
203 inline bool isOct(char c) {
204 return '0' <= c && c <='7';
207 inline int valueOct(char c) {
208 LEMON_ASSERT(isOct(c), "The character is not octal.");
212 inline bool isHex(char c) {
213 return ('0' <= c && c <= '9') ||
214 ('a' <= c && c <= 'z') ||
215 ('A' <= c && c <= 'Z');
218 inline 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 inline bool isIdentifierFirstChar(char c) {
226 return ('a' <= c && c <= 'z') ||
227 ('A' <= c && c <= 'Z') || c == '_';
230 inline bool isIdentifierChar(char c) {
231 return isIdentifierFirstChar(c) ||
232 ('0' <= c && c <= '9');
235 inline 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 inline 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 template <typename Digraph>
392 template <typename Digraph>
393 DigraphReader<Digraph> digraphReader(Digraph& digraph,
394 std::istream& is = std::cin);
396 template <typename Digraph>
397 DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
399 template <typename Digraph>
400 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
402 /// \ingroup lemon_io
404 /// \brief \ref lgf-format "LGF" reader for directed graphs
406 /// This utility reads an \ref lgf-format "LGF" file.
408 /// The reading method does a batch processing. The user creates a
409 /// reader object, then various reading rules can be added to the
410 /// reader, and eventually the reading is executed with the \c run()
411 /// member function. A map reading rule can be added to the reader
412 /// with the \c nodeMap() or \c arcMap() members. An optional
413 /// converter parameter can also be added as a standard functor
414 /// converting from \c std::string to the value type of the map. If it
415 /// is set, it will determine how the tokens in the file should be
416 /// converted to the value type of the map. If the functor is not set,
417 /// then a default conversion will be used. One map can be read into
418 /// multiple map objects at the same time. The \c attribute(), \c
419 /// node() and \c arc() functions are used to add attribute reading
423 /// DigraphReader<Digraph>(digraph, std::cin).
424 /// nodeMap("coordinates", coord_map).
425 /// arcMap("capacity", cap_map).
426 /// node("source", src).
427 /// node("target", trg).
428 /// attribute("caption", caption).
432 /// By default the reader uses the first section in the file of the
433 /// proper type. If a section has an optional name, then it can be
434 /// selected for reading by giving an optional name parameter to the
435 /// \c nodes(), \c arcs() or \c attributes() functions.
437 /// The \c useNodes() and \c useArcs() functions are used to tell the reader
438 /// that the nodes or arcs should not be constructed (added to the
439 /// graph) during the reading, but instead the label map of the items
440 /// are given as a parameter of these functions. An
441 /// application of these functions is multipass reading, which is
442 /// important if two \c \@arcs sections must be read from the
443 /// file. In this case the first phase would read the node set and one
444 /// of the arc sets, while the second phase would read the second arc
445 /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
446 /// The previously read label node map should be passed to the \c
447 /// useNodes() functions. Another application of multipass reading when
448 /// paths are given as a node map or an arc map.
449 /// It is impossible to read this in
450 /// a single pass, because the arcs are not constructed when the node
452 template <typename _Digraph>
453 class DigraphReader {
456 typedef _Digraph Digraph;
457 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
467 std::string _nodes_caption;
468 std::string _arcs_caption;
469 std::string _attributes_caption;
471 typedef std::map<std::string, Node> NodeIndex;
472 NodeIndex _node_index;
473 typedef std::map<std::string, Arc> ArcIndex;
476 typedef std::vector<std::pair<std::string,
477 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
480 typedef std::vector<std::pair<std::string,
481 _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
484 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
486 Attributes _attributes;
495 std::istringstream line;
499 /// \brief Constructor
501 /// Construct a directed graph reader, which reads from the given
503 DigraphReader(Digraph& digraph, std::istream& is = std::cin)
504 : _is(&is), local_is(false), _digraph(digraph),
505 _use_nodes(false), _use_arcs(false),
506 _skip_nodes(false), _skip_arcs(false) {}
508 /// \brief Constructor
510 /// Construct a directed graph reader, which reads from the given
512 DigraphReader(Digraph& digraph, const std::string& fn)
513 : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
514 _use_nodes(false), _use_arcs(false),
515 _skip_nodes(false), _skip_arcs(false) {}
517 /// \brief Constructor
519 /// Construct a directed graph reader, which reads from the given
521 DigraphReader(Digraph& digraph, const char* fn)
522 : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
523 _use_nodes(false), _use_arcs(false),
524 _skip_nodes(false), _skip_arcs(false) {}
526 /// \brief Destructor
528 for (typename NodeMaps::iterator it = _node_maps.begin();
529 it != _node_maps.end(); ++it) {
533 for (typename ArcMaps::iterator it = _arc_maps.begin();
534 it != _arc_maps.end(); ++it) {
538 for (typename Attributes::iterator it = _attributes.begin();
539 it != _attributes.end(); ++it) {
551 friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
553 friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
554 const std::string& fn);
555 friend DigraphReader<Digraph> digraphReader<>(Digraph& digraph,
558 DigraphReader(DigraphReader& other)
559 : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
560 _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
561 _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
564 other.local_is = false;
566 _node_index.swap(other._node_index);
567 _arc_index.swap(other._arc_index);
569 _node_maps.swap(other._node_maps);
570 _arc_maps.swap(other._arc_maps);
571 _attributes.swap(other._attributes);
573 _nodes_caption = other._nodes_caption;
574 _arcs_caption = other._arcs_caption;
575 _attributes_caption = other._attributes_caption;
579 DigraphReader& operator=(const DigraphReader&);
583 /// \name Reading rules
586 /// \brief Node map reading rule
588 /// Add a node map reading rule to the reader.
589 template <typename Map>
590 DigraphReader& nodeMap(const std::string& caption, Map& map) {
591 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
592 _reader_bits::MapStorageBase<Node>* storage =
593 new _reader_bits::MapStorage<Node, Map>(map);
594 _node_maps.push_back(std::make_pair(caption, storage));
598 /// \brief Node map reading rule
600 /// Add a node map reading rule with specialized converter to the
602 template <typename Map, typename Converter>
603 DigraphReader& nodeMap(const std::string& caption, Map& map,
604 const Converter& converter = Converter()) {
605 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
606 _reader_bits::MapStorageBase<Node>* storage =
607 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
608 _node_maps.push_back(std::make_pair(caption, storage));
612 /// \brief Arc map reading rule
614 /// Add an arc map reading rule to the reader.
615 template <typename Map>
616 DigraphReader& arcMap(const std::string& caption, Map& map) {
617 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
618 _reader_bits::MapStorageBase<Arc>* storage =
619 new _reader_bits::MapStorage<Arc, Map>(map);
620 _arc_maps.push_back(std::make_pair(caption, storage));
624 /// \brief Arc map reading rule
626 /// Add an arc map reading rule with specialized converter to the
628 template <typename Map, typename Converter>
629 DigraphReader& arcMap(const std::string& caption, Map& map,
630 const Converter& converter = Converter()) {
631 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
632 _reader_bits::MapStorageBase<Arc>* storage =
633 new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
634 _arc_maps.push_back(std::make_pair(caption, storage));
638 /// \brief Attribute reading rule
640 /// Add an attribute reading rule to the reader.
641 template <typename Value>
642 DigraphReader& attribute(const std::string& caption, Value& value) {
643 _reader_bits::ValueStorageBase* storage =
644 new _reader_bits::ValueStorage<Value>(value);
645 _attributes.insert(std::make_pair(caption, storage));
649 /// \brief Attribute reading rule
651 /// Add an attribute reading rule with specialized converter to the
653 template <typename Value, typename Converter>
654 DigraphReader& attribute(const std::string& caption, Value& value,
655 const Converter& converter = Converter()) {
656 _reader_bits::ValueStorageBase* storage =
657 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
658 _attributes.insert(std::make_pair(caption, storage));
662 /// \brief Node reading rule
664 /// Add a node reading rule to reader.
665 DigraphReader& node(const std::string& caption, Node& node) {
666 typedef _reader_bits::MapLookUpConverter<Node> Converter;
667 Converter converter(_node_index);
668 _reader_bits::ValueStorageBase* storage =
669 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
670 _attributes.insert(std::make_pair(caption, storage));
674 /// \brief Arc reading rule
676 /// Add an arc reading rule to reader.
677 DigraphReader& arc(const std::string& caption, Arc& arc) {
678 typedef _reader_bits::MapLookUpConverter<Arc> Converter;
679 Converter converter(_arc_index);
680 _reader_bits::ValueStorageBase* storage =
681 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
682 _attributes.insert(std::make_pair(caption, storage));
688 /// \name Select section by name
691 /// \brief Set \c \@nodes section to be read
693 /// Set \c \@nodes section to be read
694 DigraphReader& nodes(const std::string& caption) {
695 _nodes_caption = caption;
699 /// \brief Set \c \@arcs section to be read
701 /// Set \c \@arcs section to be read
702 DigraphReader& arcs(const std::string& caption) {
703 _arcs_caption = caption;
707 /// \brief Set \c \@attributes section to be read
709 /// Set \c \@attributes section to be read
710 DigraphReader& attributes(const std::string& caption) {
711 _attributes_caption = caption;
717 /// \name Using previously constructed node or arc set
720 /// \brief Use previously constructed node set
722 /// Use previously constructed node set, and specify the node
724 template <typename Map>
725 DigraphReader& useNodes(const Map& map) {
726 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
727 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
729 _writer_bits::DefaultConverter<typename Map::Value> converter;
730 for (NodeIt n(_digraph); n != INVALID; ++n) {
731 _node_index.insert(std::make_pair(converter(map[n]), n));
736 /// \brief Use previously constructed node set
738 /// Use previously constructed node set, and specify the node
739 /// label map and a functor which converts the label map values to
741 template <typename Map, typename Converter>
742 DigraphReader& useNodes(const Map& map,
743 const Converter& converter = Converter()) {
744 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
745 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
747 for (NodeIt n(_digraph); n != INVALID; ++n) {
748 _node_index.insert(std::make_pair(converter(map[n]), n));
753 /// \brief Use previously constructed arc set
755 /// Use previously constructed arc set, and specify the arc
757 template <typename Map>
758 DigraphReader& useArcs(const Map& map) {
759 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
760 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
762 _writer_bits::DefaultConverter<typename Map::Value> converter;
763 for (ArcIt a(_digraph); a != INVALID; ++a) {
764 _arc_index.insert(std::make_pair(converter(map[a]), a));
769 /// \brief Use previously constructed arc set
771 /// Use previously constructed arc set, and specify the arc
772 /// label map and a functor which converts the label map values to
774 template <typename Map, typename Converter>
775 DigraphReader& useArcs(const Map& map,
776 const Converter& converter = Converter()) {
777 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
778 LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
780 for (ArcIt a(_digraph); a != INVALID; ++a) {
781 _arc_index.insert(std::make_pair(converter(map[a]), a));
786 /// \brief Skips the reading of node section
788 /// Omit the reading of the node section. This implies that each node
789 /// map reading rule will be abandoned, and the nodes of the graph
790 /// will not be constructed, which usually cause that the arc set
791 /// could not be read due to lack of node name resolving.
792 /// Therefore \c skipArcs() function should also be used, or
793 /// \c useNodes() should be used to specify the label of the nodes.
794 DigraphReader& skipNodes() {
795 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
800 /// \brief Skips the reading of arc section
802 /// Omit the reading of the arc section. This implies that each arc
803 /// map reading rule will be abandoned, and the arcs of the graph
804 /// will not be constructed.
805 DigraphReader& skipArcs() {
806 LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
817 while(++line_num, std::getline(*_is, str)) {
818 line.clear(); line.str(str);
820 if (line >> std::ws >> c && c != '#') {
829 return static_cast<bool>(*_is);
834 while (readSuccess() && line >> c && c != '@') {
842 std::vector<int> map_index(_node_maps.size());
843 int map_num, label_index;
846 if (!readLine() || !(line >> c) || c == '@') {
847 if (readSuccess() && line) line.putback(c);
848 if (!_node_maps.empty())
849 throw DataFormatError("Cannot find map names");
855 std::map<std::string, int> maps;
859 while (_reader_bits::readToken(line, map)) {
860 if (maps.find(map) != maps.end()) {
861 std::ostringstream msg;
862 msg << "Multiple occurence of node map: " << map;
863 throw DataFormatError(msg.str().c_str());
865 maps.insert(std::make_pair(map, index));
869 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
870 std::map<std::string, int>::iterator jt =
871 maps.find(_node_maps[i].first);
872 if (jt == maps.end()) {
873 std::ostringstream msg;
874 msg << "Map not found in file: " << _node_maps[i].first;
875 throw DataFormatError(msg.str().c_str());
877 map_index[i] = jt->second;
881 std::map<std::string, int>::iterator jt = maps.find("label");
882 if (jt != maps.end()) {
883 label_index = jt->second;
888 map_num = maps.size();
891 while (readLine() && line >> c && c != '@') {
894 std::vector<std::string> tokens(map_num);
895 for (int i = 0; i < map_num; ++i) {
896 if (!_reader_bits::readToken(line, tokens[i])) {
897 std::ostringstream msg;
898 msg << "Column not found (" << i + 1 << ")";
899 throw DataFormatError(msg.str().c_str());
902 if (line >> std::ws >> c)
903 throw DataFormatError("Extra character on the end of line");
907 n = _digraph.addNode();
908 if (label_index != -1)
909 _node_index.insert(std::make_pair(tokens[label_index], n));
911 if (label_index == -1)
912 throw DataFormatError("Label map not found in file");
913 typename std::map<std::string, Node>::iterator it =
914 _node_index.find(tokens[label_index]);
915 if (it == _node_index.end()) {
916 std::ostringstream msg;
917 msg << "Node with label not found: " << tokens[label_index];
918 throw DataFormatError(msg.str().c_str());
923 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
924 _node_maps[i].second->set(n, tokens[map_index[i]]);
935 std::vector<int> map_index(_arc_maps.size());
936 int map_num, label_index;
939 if (!readLine() || !(line >> c) || c == '@') {
940 if (readSuccess() && line) line.putback(c);
941 if (!_arc_maps.empty())
942 throw DataFormatError("Cannot find map names");
948 std::map<std::string, int> maps;
952 while (_reader_bits::readToken(line, map)) {
953 if (maps.find(map) != maps.end()) {
954 std::ostringstream msg;
955 msg << "Multiple occurence of arc map: " << map;
956 throw DataFormatError(msg.str().c_str());
958 maps.insert(std::make_pair(map, index));
962 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
963 std::map<std::string, int>::iterator jt =
964 maps.find(_arc_maps[i].first);
965 if (jt == maps.end()) {
966 std::ostringstream msg;
967 msg << "Map not found in file: " << _arc_maps[i].first;
968 throw DataFormatError(msg.str().c_str());
970 map_index[i] = jt->second;
974 std::map<std::string, int>::iterator jt = maps.find("label");
975 if (jt != maps.end()) {
976 label_index = jt->second;
981 map_num = maps.size();
984 while (readLine() && line >> c && c != '@') {
987 std::string source_token;
988 std::string target_token;
990 if (!_reader_bits::readToken(line, source_token))
991 throw DataFormatError("Source not found");
993 if (!_reader_bits::readToken(line, target_token))
994 throw DataFormatError("Target not found");
996 std::vector<std::string> tokens(map_num);
997 for (int i = 0; i < map_num; ++i) {
998 if (!_reader_bits::readToken(line, tokens[i])) {
999 std::ostringstream msg;
1000 msg << "Column not found (" << i + 1 << ")";
1001 throw DataFormatError(msg.str().c_str());
1004 if (line >> std::ws >> c)
1005 throw DataFormatError("Extra character on the end of line");
1010 typename NodeIndex::iterator it;
1012 it = _node_index.find(source_token);
1013 if (it == _node_index.end()) {
1014 std::ostringstream msg;
1015 msg << "Item not found: " << source_token;
1016 throw DataFormatError(msg.str().c_str());
1018 Node source = it->second;
1020 it = _node_index.find(target_token);
1021 if (it == _node_index.end()) {
1022 std::ostringstream msg;
1023 msg << "Item not found: " << target_token;
1024 throw DataFormatError(msg.str().c_str());
1026 Node target = it->second;
1028 a = _digraph.addArc(source, target);
1029 if (label_index != -1)
1030 _arc_index.insert(std::make_pair(tokens[label_index], a));
1032 if (label_index == -1)
1033 throw DataFormatError("Label map not found in file");
1034 typename std::map<std::string, Arc>::iterator it =
1035 _arc_index.find(tokens[label_index]);
1036 if (it == _arc_index.end()) {
1037 std::ostringstream msg;
1038 msg << "Arc with label not found: " << tokens[label_index];
1039 throw DataFormatError(msg.str().c_str());
1044 for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1045 _arc_maps[i].second->set(a, tokens[map_index[i]]);
1049 if (readSuccess()) {
1054 void readAttributes() {
1056 std::set<std::string> read_attr;
1059 while (readLine() && line >> c && c != '@') {
1062 std::string attr, token;
1063 if (!_reader_bits::readToken(line, attr))
1064 throw DataFormatError("Attribute name not found");
1065 if (!_reader_bits::readToken(line, token))
1066 throw DataFormatError("Attribute value not found");
1068 throw DataFormatError("Extra character on the end of line");
1071 std::set<std::string>::iterator it = read_attr.find(attr);
1072 if (it != read_attr.end()) {
1073 std::ostringstream msg;
1074 msg << "Multiple occurence of attribute " << attr;
1075 throw DataFormatError(msg.str().c_str());
1077 read_attr.insert(attr);
1081 typename Attributes::iterator it = _attributes.lower_bound(attr);
1082 while (it != _attributes.end() && it->first == attr) {
1083 it->second->set(token);
1089 if (readSuccess()) {
1092 for (typename Attributes::iterator it = _attributes.begin();
1093 it != _attributes.end(); ++it) {
1094 if (read_attr.find(it->first) == read_attr.end()) {
1095 std::ostringstream msg;
1096 msg << "Attribute not found in file: " << it->first;
1097 throw DataFormatError(msg.str().c_str());
1104 /// \name Execution of the reader
1107 /// \brief Start the batch processing
1109 /// This function starts the batch processing
1111 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1113 throw DataFormatError("Cannot find file");
1116 bool nodes_done = _skip_nodes;
1117 bool arcs_done = _skip_arcs;
1118 bool attributes_done = false;
1124 while (readSuccess()) {
1127 std::string section, caption;
1129 _reader_bits::readToken(line, section);
1130 _reader_bits::readToken(line, caption);
1133 throw DataFormatError("Extra character on the end of line");
1135 if (section == "nodes" && !nodes_done) {
1136 if (_nodes_caption.empty() || _nodes_caption == caption) {
1140 } else if ((section == "arcs" || section == "edges") &&
1142 if (_arcs_caption.empty() || _arcs_caption == caption) {
1146 } else if (section == "attributes" && !attributes_done) {
1147 if (_attributes_caption.empty() || _attributes_caption == caption) {
1149 attributes_done = true;
1155 } catch (DataFormatError& error) {
1156 error.line(line_num);
1162 throw DataFormatError("Section @nodes not found");
1166 throw DataFormatError("Section @arcs not found");
1169 if (!attributes_done && !_attributes.empty()) {
1170 throw DataFormatError("Section @attributes not found");
1179 /// \brief Return a \ref DigraphReader class
1181 /// This function just returns a \ref DigraphReader class.
1182 /// \relates DigraphReader
1183 template <typename Digraph>
1184 DigraphReader<Digraph> digraphReader(Digraph& digraph,
1185 std::istream& is = std::cin) {
1186 DigraphReader<Digraph> tmp(digraph, is);
1190 /// \brief Return a \ref DigraphReader class
1192 /// This function just returns a \ref DigraphReader class.
1193 /// \relates DigraphReader
1194 template <typename Digraph>
1195 DigraphReader<Digraph> digraphReader(Digraph& digraph,
1196 const std::string& fn) {
1197 DigraphReader<Digraph> tmp(digraph, fn);
1201 /// \brief Return a \ref DigraphReader class
1203 /// This function just returns a \ref DigraphReader class.
1204 /// \relates DigraphReader
1205 template <typename Digraph>
1206 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
1207 DigraphReader<Digraph> tmp(digraph, fn);
1211 template <typename Graph>
1214 template <typename Graph>
1215 GraphReader<Graph> graphReader(Graph& graph,
1216 std::istream& is = std::cin);
1218 template <typename Graph>
1219 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
1221 template <typename Graph>
1222 GraphReader<Graph> graphReader(Graph& graph, const char *fn);
1224 /// \ingroup lemon_io
1226 /// \brief \ref lgf-format "LGF" reader for undirected graphs
1228 /// This utility reads an \ref lgf-format "LGF" file.
1230 /// It can be used almost the same way as \c DigraphReader.
1231 /// The only difference is that this class can handle edges and
1232 /// edge maps as well as arcs and arc maps.
1234 /// The columns in the \c \@edges (or \c \@arcs) section are the
1235 /// edge maps. However, if there are two maps with the same name
1236 /// prefixed with \c '+' and \c '-', then these can be read into an
1237 /// arc map. Similarly, an attribute can be read into an arc, if
1238 /// it's value is an edge label prefixed with \c '+' or \c '-'.
1239 template <typename _Graph>
1243 typedef _Graph Graph;
1244 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1253 std::string _nodes_caption;
1254 std::string _edges_caption;
1255 std::string _attributes_caption;
1257 typedef std::map<std::string, Node> NodeIndex;
1258 NodeIndex _node_index;
1259 typedef std::map<std::string, Edge> EdgeIndex;
1260 EdgeIndex _edge_index;
1262 typedef std::vector<std::pair<std::string,
1263 _reader_bits::MapStorageBase<Node>*> > NodeMaps;
1264 NodeMaps _node_maps;
1266 typedef std::vector<std::pair<std::string,
1267 _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1268 EdgeMaps _edge_maps;
1270 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1272 Attributes _attributes;
1281 std::istringstream line;
1285 /// \brief Constructor
1287 /// Construct an undirected graph reader, which reads from the given
1289 GraphReader(Graph& graph, std::istream& is = std::cin)
1290 : _is(&is), local_is(false), _graph(graph),
1291 _use_nodes(false), _use_edges(false),
1292 _skip_nodes(false), _skip_edges(false) {}
1294 /// \brief Constructor
1296 /// Construct an undirected graph reader, which reads from the given
1298 GraphReader(Graph& graph, const std::string& fn)
1299 : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
1300 _use_nodes(false), _use_edges(false),
1301 _skip_nodes(false), _skip_edges(false) {}
1303 /// \brief Constructor
1305 /// Construct an undirected graph reader, which reads from the given
1307 GraphReader(Graph& graph, const char* fn)
1308 : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
1309 _use_nodes(false), _use_edges(false),
1310 _skip_nodes(false), _skip_edges(false) {}
1312 /// \brief Destructor
1314 for (typename NodeMaps::iterator it = _node_maps.begin();
1315 it != _node_maps.end(); ++it) {
1319 for (typename EdgeMaps::iterator it = _edge_maps.begin();
1320 it != _edge_maps.end(); ++it) {
1324 for (typename Attributes::iterator it = _attributes.begin();
1325 it != _attributes.end(); ++it) {
1336 friend GraphReader<Graph> graphReader<>(Graph& graph, std::istream& is);
1337 friend GraphReader<Graph> graphReader<>(Graph& graph,
1338 const std::string& fn);
1339 friend GraphReader<Graph> graphReader<>(Graph& graph, const char *fn);
1341 GraphReader(GraphReader& other)
1342 : _is(other._is), local_is(other.local_is), _graph(other._graph),
1343 _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1344 _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1347 other.local_is = false;
1349 _node_index.swap(other._node_index);
1350 _edge_index.swap(other._edge_index);
1352 _node_maps.swap(other._node_maps);
1353 _edge_maps.swap(other._edge_maps);
1354 _attributes.swap(other._attributes);
1356 _nodes_caption = other._nodes_caption;
1357 _edges_caption = other._edges_caption;
1358 _attributes_caption = other._attributes_caption;
1362 GraphReader& operator=(const GraphReader&);
1366 /// \name Reading rules
1369 /// \brief Node map reading rule
1371 /// Add a node map reading rule to the reader.
1372 template <typename Map>
1373 GraphReader& nodeMap(const std::string& caption, Map& map) {
1374 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1375 _reader_bits::MapStorageBase<Node>* storage =
1376 new _reader_bits::MapStorage<Node, Map>(map);
1377 _node_maps.push_back(std::make_pair(caption, storage));
1381 /// \brief Node map reading rule
1383 /// Add a node map reading rule with specialized converter to the
1385 template <typename Map, typename Converter>
1386 GraphReader& nodeMap(const std::string& caption, Map& map,
1387 const Converter& converter = Converter()) {
1388 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1389 _reader_bits::MapStorageBase<Node>* storage =
1390 new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1391 _node_maps.push_back(std::make_pair(caption, storage));
1395 /// \brief Edge map reading rule
1397 /// Add an edge map reading rule to the reader.
1398 template <typename Map>
1399 GraphReader& edgeMap(const std::string& caption, Map& map) {
1400 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1401 _reader_bits::MapStorageBase<Edge>* storage =
1402 new _reader_bits::MapStorage<Edge, Map>(map);
1403 _edge_maps.push_back(std::make_pair(caption, storage));
1407 /// \brief Edge map reading rule
1409 /// Add an edge map reading rule with specialized converter to the
1411 template <typename Map, typename Converter>
1412 GraphReader& edgeMap(const std::string& caption, Map& map,
1413 const Converter& converter = Converter()) {
1414 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1415 _reader_bits::MapStorageBase<Edge>* storage =
1416 new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1417 _edge_maps.push_back(std::make_pair(caption, storage));
1421 /// \brief Arc map reading rule
1423 /// Add an arc map reading rule to the reader.
1424 template <typename Map>
1425 GraphReader& arcMap(const std::string& caption, Map& map) {
1426 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1427 _reader_bits::MapStorageBase<Edge>* forward_storage =
1428 new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1429 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1430 _reader_bits::MapStorageBase<Edge>* backward_storage =
1431 new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1432 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1436 /// \brief Arc map reading rule
1438 /// Add an arc map reading rule with specialized converter to the
1440 template <typename Map, typename Converter>
1441 GraphReader& arcMap(const std::string& caption, Map& map,
1442 const Converter& converter = Converter()) {
1443 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1444 _reader_bits::MapStorageBase<Edge>* forward_storage =
1445 new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1446 (_graph, map, converter);
1447 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1448 _reader_bits::MapStorageBase<Edge>* backward_storage =
1449 new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1450 (_graph, map, converter);
1451 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1455 /// \brief Attribute reading rule
1457 /// Add an attribute reading rule to the reader.
1458 template <typename Value>
1459 GraphReader& attribute(const std::string& caption, Value& value) {
1460 _reader_bits::ValueStorageBase* storage =
1461 new _reader_bits::ValueStorage<Value>(value);
1462 _attributes.insert(std::make_pair(caption, storage));
1466 /// \brief Attribute reading rule
1468 /// Add an attribute reading rule with specialized converter to the
1470 template <typename Value, typename Converter>
1471 GraphReader& attribute(const std::string& caption, Value& value,
1472 const Converter& converter = Converter()) {
1473 _reader_bits::ValueStorageBase* storage =
1474 new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1475 _attributes.insert(std::make_pair(caption, storage));
1479 /// \brief Node reading rule
1481 /// Add a node reading rule to reader.
1482 GraphReader& node(const std::string& caption, Node& node) {
1483 typedef _reader_bits::MapLookUpConverter<Node> Converter;
1484 Converter converter(_node_index);
1485 _reader_bits::ValueStorageBase* storage =
1486 new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1487 _attributes.insert(std::make_pair(caption, storage));
1491 /// \brief Edge reading rule
1493 /// Add an edge reading rule to reader.
1494 GraphReader& edge(const std::string& caption, Edge& edge) {
1495 typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1496 Converter converter(_edge_index);
1497 _reader_bits::ValueStorageBase* storage =
1498 new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1499 _attributes.insert(std::make_pair(caption, storage));
1503 /// \brief Arc reading rule
1505 /// Add an arc reading rule to reader.
1506 GraphReader& arc(const std::string& caption, Arc& arc) {
1507 typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
1508 Converter converter(_graph, _edge_index);
1509 _reader_bits::ValueStorageBase* storage =
1510 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1511 _attributes.insert(std::make_pair(caption, storage));
1517 /// \name Select section by name
1520 /// \brief Set \c \@nodes section to be read
1522 /// Set \c \@nodes section to be read.
1523 GraphReader& nodes(const std::string& caption) {
1524 _nodes_caption = caption;
1528 /// \brief Set \c \@edges section to be read
1530 /// Set \c \@edges section to be read.
1531 GraphReader& edges(const std::string& caption) {
1532 _edges_caption = caption;
1536 /// \brief Set \c \@attributes section to be read
1538 /// Set \c \@attributes section to be read.
1539 GraphReader& attributes(const std::string& caption) {
1540 _attributes_caption = caption;
1546 /// \name Using previously constructed node or edge set
1549 /// \brief Use previously constructed node set
1551 /// Use previously constructed node set, and specify the node
1553 template <typename Map>
1554 GraphReader& useNodes(const Map& map) {
1555 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1556 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1558 _writer_bits::DefaultConverter<typename Map::Value> converter;
1559 for (NodeIt n(_graph); n != INVALID; ++n) {
1560 _node_index.insert(std::make_pair(converter(map[n]), n));
1565 /// \brief Use previously constructed node set
1567 /// Use previously constructed node set, and specify the node
1568 /// label map and a functor which converts the label map values to
1570 template <typename Map, typename Converter>
1571 GraphReader& useNodes(const Map& map,
1572 const Converter& converter = Converter()) {
1573 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1574 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1576 for (NodeIt n(_graph); n != INVALID; ++n) {
1577 _node_index.insert(std::make_pair(converter(map[n]), n));
1582 /// \brief Use previously constructed edge set
1584 /// Use previously constructed edge set, and specify the edge
1586 template <typename Map>
1587 GraphReader& useEdges(const Map& map) {
1588 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1589 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1591 _writer_bits::DefaultConverter<typename Map::Value> converter;
1592 for (EdgeIt a(_graph); a != INVALID; ++a) {
1593 _edge_index.insert(std::make_pair(converter(map[a]), a));
1598 /// \brief Use previously constructed edge set
1600 /// Use previously constructed edge set, and specify the edge
1601 /// label map and a functor which converts the label map values to
1603 template <typename Map, typename Converter>
1604 GraphReader& useEdges(const Map& map,
1605 const Converter& converter = Converter()) {
1606 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1607 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1609 for (EdgeIt a(_graph); a != INVALID; ++a) {
1610 _edge_index.insert(std::make_pair(converter(map[a]), a));
1615 /// \brief Skip the reading of node section
1617 /// Omit the reading of the node section. This implies that each node
1618 /// map reading rule will be abandoned, and the nodes of the graph
1619 /// will not be constructed, which usually cause that the edge set
1620 /// could not be read due to lack of node name
1621 /// could not be read due to lack of node name resolving.
1622 /// Therefore \c skipEdges() function should also be used, or
1623 /// \c useNodes() should be used to specify the label of the nodes.
1624 GraphReader& skipNodes() {
1625 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1630 /// \brief Skip the reading of edge section
1632 /// Omit the reading of the edge section. This implies that each edge
1633 /// map reading rule will be abandoned, and the edges of the graph
1634 /// will not be constructed.
1635 GraphReader& skipEdges() {
1636 LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1647 while(++line_num, std::getline(*_is, str)) {
1648 line.clear(); line.str(str);
1650 if (line >> std::ws >> c && c != '#') {
1658 bool readSuccess() {
1659 return static_cast<bool>(*_is);
1662 void skipSection() {
1664 while (readSuccess() && line >> c && c != '@') {
1672 std::vector<int> map_index(_node_maps.size());
1673 int map_num, label_index;
1676 if (!readLine() || !(line >> c) || c == '@') {
1677 if (readSuccess() && line) line.putback(c);
1678 if (!_node_maps.empty())
1679 throw DataFormatError("Cannot find map names");
1685 std::map<std::string, int> maps;
1689 while (_reader_bits::readToken(line, map)) {
1690 if (maps.find(map) != maps.end()) {
1691 std::ostringstream msg;
1692 msg << "Multiple occurence of node map: " << map;
1693 throw DataFormatError(msg.str().c_str());
1695 maps.insert(std::make_pair(map, index));
1699 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1700 std::map<std::string, int>::iterator jt =
1701 maps.find(_node_maps[i].first);
1702 if (jt == maps.end()) {
1703 std::ostringstream msg;
1704 msg << "Map not found in file: " << _node_maps[i].first;
1705 throw DataFormatError(msg.str().c_str());
1707 map_index[i] = jt->second;
1711 std::map<std::string, int>::iterator jt = maps.find("label");
1712 if (jt != maps.end()) {
1713 label_index = jt->second;
1718 map_num = maps.size();
1721 while (readLine() && line >> c && c != '@') {
1724 std::vector<std::string> tokens(map_num);
1725 for (int i = 0; i < map_num; ++i) {
1726 if (!_reader_bits::readToken(line, tokens[i])) {
1727 std::ostringstream msg;
1728 msg << "Column not found (" << i + 1 << ")";
1729 throw DataFormatError(msg.str().c_str());
1732 if (line >> std::ws >> c)
1733 throw DataFormatError("Extra character on the end of line");
1737 n = _graph.addNode();
1738 if (label_index != -1)
1739 _node_index.insert(std::make_pair(tokens[label_index], n));
1741 if (label_index == -1)
1742 throw DataFormatError("Label map not found in file");
1743 typename std::map<std::string, Node>::iterator it =
1744 _node_index.find(tokens[label_index]);
1745 if (it == _node_index.end()) {
1746 std::ostringstream msg;
1747 msg << "Node with label not found: " << tokens[label_index];
1748 throw DataFormatError(msg.str().c_str());
1753 for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1754 _node_maps[i].second->set(n, tokens[map_index[i]]);
1758 if (readSuccess()) {
1765 std::vector<int> map_index(_edge_maps.size());
1766 int map_num, label_index;
1769 if (!readLine() || !(line >> c) || c == '@') {
1770 if (readSuccess() && line) line.putback(c);
1771 if (!_edge_maps.empty())
1772 throw DataFormatError("Cannot find map names");
1778 std::map<std::string, int> maps;
1782 while (_reader_bits::readToken(line, map)) {
1783 if (maps.find(map) != maps.end()) {
1784 std::ostringstream msg;
1785 msg << "Multiple occurence of edge map: " << map;
1786 throw DataFormatError(msg.str().c_str());
1788 maps.insert(std::make_pair(map, index));
1792 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1793 std::map<std::string, int>::iterator jt =
1794 maps.find(_edge_maps[i].first);
1795 if (jt == maps.end()) {
1796 std::ostringstream msg;
1797 msg << "Map not found in file: " << _edge_maps[i].first;
1798 throw DataFormatError(msg.str().c_str());
1800 map_index[i] = jt->second;
1804 std::map<std::string, int>::iterator jt = maps.find("label");
1805 if (jt != maps.end()) {
1806 label_index = jt->second;
1811 map_num = maps.size();
1814 while (readLine() && line >> c && c != '@') {
1817 std::string source_token;
1818 std::string target_token;
1820 if (!_reader_bits::readToken(line, source_token))
1821 throw DataFormatError("Node u not found");
1823 if (!_reader_bits::readToken(line, target_token))
1824 throw DataFormatError("Node v not found");
1826 std::vector<std::string> tokens(map_num);
1827 for (int i = 0; i < map_num; ++i) {
1828 if (!_reader_bits::readToken(line, tokens[i])) {
1829 std::ostringstream msg;
1830 msg << "Column not found (" << i + 1 << ")";
1831 throw DataFormatError(msg.str().c_str());
1834 if (line >> std::ws >> c)
1835 throw DataFormatError("Extra character on the end of line");
1840 typename NodeIndex::iterator it;
1842 it = _node_index.find(source_token);
1843 if (it == _node_index.end()) {
1844 std::ostringstream msg;
1845 msg << "Item not found: " << source_token;
1846 throw DataFormatError(msg.str().c_str());
1848 Node source = it->second;
1850 it = _node_index.find(target_token);
1851 if (it == _node_index.end()) {
1852 std::ostringstream msg;
1853 msg << "Item not found: " << target_token;
1854 throw DataFormatError(msg.str().c_str());
1856 Node target = it->second;
1858 e = _graph.addEdge(source, target);
1859 if (label_index != -1)
1860 _edge_index.insert(std::make_pair(tokens[label_index], e));
1862 if (label_index == -1)
1863 throw DataFormatError("Label map not found in file");
1864 typename std::map<std::string, Edge>::iterator it =
1865 _edge_index.find(tokens[label_index]);
1866 if (it == _edge_index.end()) {
1867 std::ostringstream msg;
1868 msg << "Edge with label not found: " << tokens[label_index];
1869 throw DataFormatError(msg.str().c_str());
1874 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1875 _edge_maps[i].second->set(e, tokens[map_index[i]]);
1879 if (readSuccess()) {
1884 void readAttributes() {
1886 std::set<std::string> read_attr;
1889 while (readLine() && line >> c && c != '@') {
1892 std::string attr, token;
1893 if (!_reader_bits::readToken(line, attr))
1894 throw DataFormatError("Attribute name not found");
1895 if (!_reader_bits::readToken(line, token))
1896 throw DataFormatError("Attribute value not found");
1898 throw DataFormatError("Extra character on the end of line");
1901 std::set<std::string>::iterator it = read_attr.find(attr);
1902 if (it != read_attr.end()) {
1903 std::ostringstream msg;
1904 msg << "Multiple occurence of attribute " << attr;
1905 throw DataFormatError(msg.str().c_str());
1907 read_attr.insert(attr);
1911 typename Attributes::iterator it = _attributes.lower_bound(attr);
1912 while (it != _attributes.end() && it->first == attr) {
1913 it->second->set(token);
1919 if (readSuccess()) {
1922 for (typename Attributes::iterator it = _attributes.begin();
1923 it != _attributes.end(); ++it) {
1924 if (read_attr.find(it->first) == read_attr.end()) {
1925 std::ostringstream msg;
1926 msg << "Attribute not found in file: " << it->first;
1927 throw DataFormatError(msg.str().c_str());
1934 /// \name Execution of the reader
1937 /// \brief Start the batch processing
1939 /// This function starts the batch processing
1942 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1944 bool nodes_done = _skip_nodes;
1945 bool edges_done = _skip_edges;
1946 bool attributes_done = false;
1952 while (readSuccess()) {
1955 std::string section, caption;
1957 _reader_bits::readToken(line, section);
1958 _reader_bits::readToken(line, caption);
1961 throw DataFormatError("Extra character on the end of line");
1963 if (section == "nodes" && !nodes_done) {
1964 if (_nodes_caption.empty() || _nodes_caption == caption) {
1968 } else if ((section == "edges" || section == "arcs") &&
1970 if (_edges_caption.empty() || _edges_caption == caption) {
1974 } else if (section == "attributes" && !attributes_done) {
1975 if (_attributes_caption.empty() || _attributes_caption == caption) {
1977 attributes_done = true;
1983 } catch (DataFormatError& error) {
1984 error.line(line_num);
1990 throw DataFormatError("Section @nodes not found");
1994 throw DataFormatError("Section @edges not found");
1997 if (!attributes_done && !_attributes.empty()) {
1998 throw DataFormatError("Section @attributes not found");
2007 /// \brief Return a \ref GraphReader class
2009 /// This function just returns a \ref GraphReader class.
2010 /// \relates GraphReader
2011 template <typename Graph>
2012 GraphReader<Graph> graphReader(Graph& graph, std::istream& is = std::cin) {
2013 GraphReader<Graph> tmp(graph, is);
2017 /// \brief Return a \ref GraphReader class
2019 /// This function just returns a \ref GraphReader class.
2020 /// \relates GraphReader
2021 template <typename Graph>
2022 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
2023 GraphReader<Graph> tmp(graph, fn);
2027 /// \brief Return a \ref GraphReader class
2029 /// This function just returns a \ref GraphReader class.
2030 /// \relates GraphReader
2031 template <typename Graph>
2032 GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
2033 GraphReader<Graph> tmp(graph, fn);
2037 class SectionReader;
2039 SectionReader sectionReader(std::istream& is);
2040 SectionReader sectionReader(const std::string& fn);
2041 SectionReader sectionReader(const char* fn);
2043 /// \ingroup lemon_io
2045 /// \brief Section reader class
2047 /// In the \ref lgf-format "LGF" file extra sections can be placed,
2048 /// which contain any data in arbitrary format. Such sections can be
2049 /// read with this class. A reading rule can be added to the class
2050 /// with two different functions. With the \c sectionLines() function a
2051 /// functor can process the section line-by-line, while with the \c
2052 /// sectionStream() member the section can be read from an input
2054 class SectionReader {
2060 typedef std::map<std::string, _reader_bits::Section*> Sections;
2064 std::istringstream line;
2068 /// \brief Constructor
2070 /// Construct a section reader, which reads from the given input
2072 SectionReader(std::istream& is)
2073 : _is(&is), local_is(false) {}
2075 /// \brief Constructor
2077 /// Construct a section reader, which reads from the given file.
2078 SectionReader(const std::string& fn)
2079 : _is(new std::ifstream(fn.c_str())), local_is(true) {}
2081 /// \brief Constructor
2083 /// Construct a section reader, which reads from the given file.
2084 SectionReader(const char* fn)
2085 : _is(new std::ifstream(fn)), local_is(true) {}
2087 /// \brief Destructor
2089 for (Sections::iterator it = _sections.begin();
2090 it != _sections.end(); ++it) {
2102 friend SectionReader sectionReader(std::istream& is);
2103 friend SectionReader sectionReader(const std::string& fn);
2104 friend SectionReader sectionReader(const char* fn);
2106 SectionReader(SectionReader& other)
2107 : _is(other._is), local_is(other.local_is) {
2110 other.local_is = false;
2112 _sections.swap(other._sections);
2115 SectionReader& operator=(const SectionReader&);
2119 /// \name Section readers
2122 /// \brief Add a section processor with line oriented reading
2124 /// The first parameter is the type descriptor of the section, the
2125 /// second is a functor, which takes just one \c std::string
2126 /// parameter. At the reading process, each line of the section
2127 /// will be given to the functor object. However, the empty lines
2128 /// and the comment lines are filtered out, and the leading
2129 /// whitespaces are trimmed from each processed string.
2131 /// For example let's see a section, which contain several
2132 /// integers, which should be inserted into a vector.
2140 /// The functor is implemented as a struct:
2142 /// struct NumberSection {
2143 /// std::vector<int>& _data;
2144 /// NumberSection(std::vector<int>& data) : _data(data) {}
2145 /// void operator()(const std::string& line) {
2146 /// std::istringstream ls(line);
2148 /// while (ls >> value) _data.push_back(value);
2154 /// reader.sectionLines("numbers", NumberSection(vec));
2156 template <typename Functor>
2157 SectionReader& sectionLines(const std::string& type, Functor functor) {
2158 LEMON_ASSERT(!type.empty(), "Type is empty.");
2159 LEMON_ASSERT(_sections.find(type) == _sections.end(),
2160 "Multiple reading of section.");
2161 _sections.insert(std::make_pair(type,
2162 new _reader_bits::LineSection<Functor>(functor)));
2167 /// \brief Add a section processor with stream oriented reading
2169 /// The first parameter is the type of the section, the second is
2170 /// a functor, which takes an \c std::istream& and an \c int&
2171 /// parameter, the latter regard to the line number of stream. The
2172 /// functor can read the input while the section go on, and the
2173 /// line number should be modified accordingly.
2174 template <typename Functor>
2175 SectionReader& sectionStream(const std::string& type, Functor functor) {
2176 LEMON_ASSERT(!type.empty(), "Type is empty.");
2177 LEMON_ASSERT(_sections.find(type) == _sections.end(),
2178 "Multiple reading of section.");
2179 _sections.insert(std::make_pair(type,
2180 new _reader_bits::StreamSection<Functor>(functor)));
2190 while(++line_num, std::getline(*_is, str)) {
2191 line.clear(); line.str(str);
2193 if (line >> std::ws >> c && c != '#') {
2201 bool readSuccess() {
2202 return static_cast<bool>(*_is);
2205 void skipSection() {
2207 while (readSuccess() && line >> c && c != '@') {
2216 /// \name Execution of the reader
2219 /// \brief Start the batch processing
2221 /// This function starts the batch processing.
2224 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2226 std::set<std::string> extra_sections;
2232 while (readSuccess()) {
2235 std::string section, caption;
2237 _reader_bits::readToken(line, section);
2238 _reader_bits::readToken(line, caption);
2241 throw DataFormatError("Extra character on the end of line");
2243 if (extra_sections.find(section) != extra_sections.end()) {
2244 std::ostringstream msg;
2245 msg << "Multiple occurence of section " << section;
2246 throw DataFormatError(msg.str().c_str());
2248 Sections::iterator it = _sections.find(section);
2249 if (it != _sections.end()) {
2250 extra_sections.insert(section);
2251 it->second->process(*_is, line_num);
2255 } catch (DataFormatError& error) {
2256 error.line(line_num);
2260 for (Sections::iterator it = _sections.begin();
2261 it != _sections.end(); ++it) {
2262 if (extra_sections.find(it->first) == extra_sections.end()) {
2263 std::ostringstream os;
2264 os << "Cannot find section: " << it->first;
2265 throw DataFormatError(os.str().c_str());
2274 /// \brief Return a \ref SectionReader class
2276 /// This function just returns a \ref SectionReader class.
2277 /// \relates SectionReader
2278 inline SectionReader sectionReader(std::istream& is) {
2279 SectionReader tmp(is);
2283 /// \brief Return a \ref SectionReader class
2285 /// This function just returns a \ref SectionReader class.
2286 /// \relates SectionReader
2287 inline SectionReader sectionReader(const std::string& fn) {
2288 SectionReader tmp(fn);
2292 /// \brief Return a \ref SectionReader class
2294 /// This function just returns a \ref SectionReader class.
2295 /// \relates SectionReader
2296 inline SectionReader sectionReader(const char* fn) {
2297 SectionReader tmp(fn);
2301 /// \ingroup lemon_io
2303 /// \brief Reader for the contents of the \ref lgf-format "LGF" file
2305 /// This class can be used to read the sections, the map names and
2306 /// the attributes from a file. Usually, the LEMON programs know
2307 /// that, which type of graph, which maps and which attributes
2308 /// should be read from a file, but in general tools (like glemon)
2309 /// the contents of an LGF file should be guessed somehow. This class
2310 /// reads the graph and stores the appropriate information for
2311 /// reading the graph.
2314 /// LgfContents contents("graph.lgf");
2317 /// // Does it contain any node section and arc section?
2318 /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
2319 /// std::cerr << "Failure, cannot find graph." << std::endl;
2322 /// std::cout << "The name of the default node section: "
2323 /// << contents.nodeSection(0) << std::endl;
2324 /// std::cout << "The number of the arc maps: "
2325 /// << contents.arcMaps(0).size() << std::endl;
2326 /// std::cout << "The name of second arc map: "
2327 /// << contents.arcMaps(0)[1] << std::endl;
2335 std::vector<std::string> _node_sections;
2336 std::vector<std::string> _edge_sections;
2337 std::vector<std::string> _attribute_sections;
2338 std::vector<std::string> _extra_sections;
2340 std::vector<bool> _arc_sections;
2342 std::vector<std::vector<std::string> > _node_maps;
2343 std::vector<std::vector<std::string> > _edge_maps;
2345 std::vector<std::vector<std::string> > _attributes;
2349 std::istringstream line;
2353 /// \brief Constructor
2355 /// Construct an \e LGF contents reader, which reads from the given
2357 LgfContents(std::istream& is)
2358 : _is(&is), local_is(false) {}
2360 /// \brief Constructor
2362 /// Construct an \e LGF contents reader, which reads from the given
2364 LgfContents(const std::string& fn)
2365 : _is(new std::ifstream(fn.c_str())), local_is(true) {}
2367 /// \brief Constructor
2369 /// Construct an \e LGF contents reader, which reads from the given
2371 LgfContents(const char* fn)
2372 : _is(new std::ifstream(fn)), local_is(true) {}
2374 /// \brief Destructor
2376 if (local_is) delete _is;
2381 LgfContents(const LgfContents&);
2382 LgfContents& operator=(const LgfContents&);
2387 /// \name Node sections
2390 /// \brief Gives back the number of node sections in the file.
2392 /// Gives back the number of node sections in the file.
2393 int nodeSectionNum() const {
2394 return _node_sections.size();
2397 /// \brief Returns the node section name at the given position.
2399 /// Returns the node section name at the given position.
2400 const std::string& nodeSection(int i) const {
2401 return _node_sections[i];
2404 /// \brief Gives back the node maps for the given section.
2406 /// Gives back the node maps for the given section.
2407 const std::vector<std::string>& nodeMapNames(int i) const {
2408 return _node_maps[i];
2413 /// \name Arc/Edge sections
2416 /// \brief Gives back the number of arc/edge sections in the file.
2418 /// Gives back the number of arc/edge sections in the file.
2419 /// \note It is synonym of \c edgeSectionNum().
2420 int arcSectionNum() const {
2421 return _edge_sections.size();
2424 /// \brief Returns the arc/edge section name at the given position.
2426 /// Returns the arc/edge section name at the given position.
2427 /// \note It is synonym of \c edgeSection().
2428 const std::string& arcSection(int i) const {
2429 return _edge_sections[i];
2432 /// \brief Gives back the arc/edge maps for the given section.
2434 /// Gives back the arc/edge maps for the given section.
2435 /// \note It is synonym of \c edgeMapNames().
2436 const std::vector<std::string>& arcMapNames(int i) const {
2437 return _edge_maps[i];
2445 /// \brief Gives back the number of arc/edge sections in the file.
2447 /// Gives back the number of arc/edge sections in the file.
2448 /// \note It is synonym of \c arcSectionNum().
2449 int edgeSectionNum() const {
2450 return _edge_sections.size();
2453 /// \brief Returns the section name at the given position.
2455 /// Returns the section name at the given position.
2456 /// \note It is synonym of \c arcSection().
2457 const std::string& edgeSection(int i) const {
2458 return _edge_sections[i];
2461 /// \brief Gives back the edge maps for the given section.
2463 /// Gives back the edge maps for the given section.
2464 /// \note It is synonym of \c arcMapNames().
2465 const std::vector<std::string>& edgeMapNames(int i) const {
2466 return _edge_maps[i];
2471 /// \name Attribute sections
2474 /// \brief Gives back the number of attribute sections in the file.
2476 /// Gives back the number of attribute sections in the file.
2477 int attributeSectionNum() const {
2478 return _attribute_sections.size();
2481 /// \brief Returns the attribute section name at the given position.
2483 /// Returns the attribute section name at the given position.
2484 const std::string& attributeSectionNames(int i) const {
2485 return _attribute_sections[i];
2488 /// \brief Gives back the attributes for the given section.
2490 /// Gives back the attributes for the given section.
2491 const std::vector<std::string>& attributes(int i) const {
2492 return _attributes[i];
2497 /// \name Extra sections
2500 /// \brief Gives back the number of extra sections in the file.
2502 /// Gives back the number of extra sections in the file.
2503 int extraSectionNum() const {
2504 return _extra_sections.size();
2507 /// \brief Returns the extra section type at the given position.
2509 /// Returns the section type at the given position.
2510 const std::string& extraSection(int i) const {
2511 return _extra_sections[i];
2520 while(++line_num, std::getline(*_is, str)) {
2521 line.clear(); line.str(str);
2523 if (line >> std::ws >> c && c != '#') {
2531 bool readSuccess() {
2532 return static_cast<bool>(*_is);
2535 void skipSection() {
2537 while (readSuccess() && line >> c && c != '@') {
2543 void readMaps(std::vector<std::string>& maps) {
2545 if (!readLine() || !(line >> c) || c == '@') {
2546 if (readSuccess() && line) line.putback(c);
2551 while (_reader_bits::readToken(line, map)) {
2552 maps.push_back(map);
2556 void readAttributes(std::vector<std::string>& attrs) {
2559 while (readSuccess() && line >> c && c != '@') {
2562 _reader_bits::readToken(line, attr);
2563 attrs.push_back(attr);
2571 /// \name Execution of the contents reader
2574 /// \brief Starts the reading
2576 /// This function starts the reading.
2582 while (readSuccess()) {
2587 std::string section, caption;
2588 _reader_bits::readToken(line, section);
2589 _reader_bits::readToken(line, caption);
2591 if (section == "nodes") {
2592 _node_sections.push_back(caption);
2593 _node_maps.push_back(std::vector<std::string>());
2594 readMaps(_node_maps.back());
2595 readLine(); skipSection();
2596 } else if (section == "arcs" || section == "edges") {
2597 _edge_sections.push_back(caption);
2598 _arc_sections.push_back(section == "arcs");
2599 _edge_maps.push_back(std::vector<std::string>());
2600 readMaps(_edge_maps.back());
2601 readLine(); skipSection();
2602 } else if (section == "attributes") {
2603 _attribute_sections.push_back(caption);
2604 _attributes.push_back(std::vector<std::string>());
2605 readAttributes(_attributes.back());
2607 _extra_sections.push_back(section);
2608 readLine(); skipSection();