diff --git a/doc/Makefile.am b/doc/Makefile.am --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -3,6 +3,7 @@ doc/coding_style.dox \ doc/dirs.dox \ doc/groups.dox \ + doc/lgf.dox \ doc/license.dox \ doc/mainpage.dox \ doc/namespaces.dox \ diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -483,25 +483,6 @@ */ /** -@defgroup section_io Section readers and writers -@ingroup lemon_io -\brief Section readers and writers for LEMON Input-Output. - -This group describes section reader and writer classes that can be -attached to \ref LemonReader and \ref LemonWriter. -*/ - -/** -@defgroup item_io Item readers and writers -@ingroup lemon_io -\brief Item readers and writers for LEMON Input-Output. - -This group describes reader and writer classes for various data types -(e.g. map or attribute values). These classes can be attached to -\ref LemonReader and \ref LemonWriter. -*/ - -/** @defgroup eps_io Postscript exporting @ingroup io_group \brief General \c EPS drawer and graph exporter diff --git a/doc/lgf.dox b/doc/lgf.dox new file mode 100644 --- /dev/null +++ b/doc/lgf.dox @@ -0,0 +1,96 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +namespace lemon { +/*! + + + +\page lgf-format Lemon Graph Format (LGF) + +The \e LGF is a column oriented +file format for storing graphs and associated data like +node and edge maps. + +Each line with \c '#' first non-whitespace +character is considered as a comment line. + +Otherwise the file consists of sections starting with +a header line. The header lines starts with an \c '@' character followed by the +type of section. The standard section types are \c \@nodes, \c +\@arcs and \c \@edges +and \@attributes. Each header line may also have an optional +\e name, which can be use to distinguish the sections of the same +type. + +The standard sections are column oriented, each line consists of +tokens separated by whitespaces. A token can be \e plain or +\e quoted. A plain token is just a sequence of non-whitespace characters, +while a quoted token is a +character sequence surrounded by double quotes, and it can also +contain whitespaces and escape sequences. + +The \c \@nodes section describes a set of nodes and associated +maps. The first is a header line, it columns are the names of the +maps appearing in the following lines. +One of the maps must be called \c +"label", which plays special role in the file. +The following +non-empty lines until the next section describes nodes of the +graph. Each line contains the values of the node maps +associated to the current node. + +\code + @nodes + label coordinates size title + 1 (10,20) 10 "First node" + 2 (80,80) 8 "Second node" + 3 (40,10) 10 "Third node" +\endcode + +The \c \@arcs section is very similar to the \c \@nodes section, +it again starts with a header line describing the names of the arc, +but the \c "label" map is not obligatory here. The following lines +describe the arcs. The first two tokens of each line are +the source and the target node of the arc, respectively, then come the map +values. The source and target tokens must be node labels. + +\code + @arcs + capacity + 1 2 16 + 1 3 12 + 2 3 18 +\endcode + +The \c \@edges is just a synonym of \c \@arcs. + +The \c \@attributes section contains key-value pairs, each line +consists of two tokens, an attribute name, and then an attribute value. + +\code + @attributes + source 1 + target 3 + caption "LEMON test digraph" +\endcode + +*/ +} + +// LocalWords: whitespace whitespaces diff --git a/lemon/lgf_reader.h b/lemon/lgf_reader.h --- a/lemon/lgf_reader.h +++ b/lemon/lgf_reader.h @@ -268,35 +268,58 @@ str = os.str(); return is; } - - std::istream& readIdentifier(std::istream& is, std::string& str) { - std::ostringstream os; - - char c; - is >> std::ws; - - if (!is.get(c)) - return is; - - if (!isIdentifierFirstChar(c)) - throw DataFormatError("Wrong char in identifier"); - - os << c; - - while (is.get(c) && !isWhiteSpace(c)) { - if (!isIdentifierChar(c)) - throw DataFormatError("Wrong char in identifier"); - os << c; - } - if (!is) is.clear(); - - str = os.str(); - return is; - } } - - /// \e + + /// \ingroup lemon_io + /// + /// \brief LGF reader for directed graphs + /// + /// This utility reads an \ref lgf-format "LGF" file. + /// + /// The reading method does a batch processing. The user creates a + /// reader object, then various reading rules can be added to the + /// reader, and eventually the reading is executed with the \c run() + /// member function. A map reading rule can be added to the reader + /// with the \c nodeMap() or \c arcMap() members. An optional + /// converter parameter can also be added as a standard functor converting from + /// std::string to the value type of the map. If it is set, it will + /// determine how the tokens in the file should be is converted to the map's + /// value type. If the functor is not set, then a default conversion + /// will be used. One map can be read into multiple map objects at the + /// same time. The \c attribute(), \c node() and \c arc() functions + /// are used to add attribute reading rules. + /// + ///\code + /// DigraphReader(std::cin, digraph). + /// nodeMap("coordinates", coord_map). + /// arcMap("capacity", cap_map). + /// node("source", src). + /// node("target", trg). + /// attribute("caption", caption). + /// run(); + ///\endcode + /// + /// By default the reader uses the first section in the file of the + /// proper type. If a section has an optional name, then it can be + /// selected for reading by giving an optional name parameter to + /// the \c nodes(), \c arcs() or \c attributes() + /// functions. + /// + /// The \c useNodes() and \c useArcs() functions are used to tell the reader + /// that the nodes or arcs should not be constructed (added to the + /// graph) during the reading, but instead the label map of the items + /// are given as a parameter of these functions. An + /// application of these function is multipass reading, which is + /// important if two \e \@arcs sections must be read from the + /// file. In this example the first phase would read the node set and one + /// of the arc sets, while the second phase would read the second arc + /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet). + /// The previously read label node map should be passed to the \c + /// useNodes() functions. Another application of multipass reading when + /// paths are given as a node map or an arc map. It is impossible read this in + /// a single pass, because the arcs are not constructed when the node + /// maps are read. template class DigraphReader { public: @@ -341,23 +364,34 @@ public: - /// \e + /// \brief Constructor + /// + /// Construct a directed graph reader, which reads from the given + /// input stream. DigraphReader(std::istream& is, Digraph& digraph) : _is(&is), local_is(false), _digraph(digraph), _use_nodes(false), _use_arcs(false) {} - /// \e + /// \brief Constructor + /// + /// Construct a directed graph reader, which reads from the given + /// file. DigraphReader(const std::string& fn, Digraph& digraph) : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph), _use_nodes(false), _use_arcs(false) {} - - - /// \e + + /// \brief Constructor + /// + /// Construct a directed graph reader, which reads from the given + /// file. DigraphReader(const char* fn, Digraph& digraph) : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph), _use_nodes(false), _use_arcs(false) {} - /// \e + /// \brief Copy constructor + /// + /// The copy constructor transfers all data from the other reader, + /// therefore the copied reader will not be usable more. DigraphReader(DigraphReader& other) : _is(other._is), local_is(other.local_is), _digraph(other._digraph), _use_nodes(other._use_nodes), _use_arcs(other._use_arcs) { @@ -377,7 +411,7 @@ _attributes_caption = other._attributes_caption; } - /// \e + /// \brief Destructor ~DigraphReader() { for (typename NodeMaps::iterator it = _node_maps.begin(); it != _node_maps.end(); ++it) { @@ -406,7 +440,12 @@ public: - /// \e + /// \name Reading rules + /// @{ + + /// \brief Node map reading rule + /// + /// Add a node map reading rule to the reader. template DigraphReader& nodeMap(const std::string& caption, Map& map) { checkConcept, Map>(); @@ -416,7 +455,10 @@ return *this; } - /// \e + /// \brief Node map reading rule + /// + /// Add a node map reading rule with specialized converter to the + /// reader. template DigraphReader& nodeMap(const std::string& caption, Map& map, const Converter& converter = Converter()) { @@ -427,7 +469,9 @@ return *this; } - /// \e + /// \brief Arc map reading rule + /// + /// Add an arc map reading rule to the reader. template DigraphReader& arcMap(const std::string& caption, Map& map) { checkConcept, Map>(); @@ -437,7 +481,10 @@ return *this; } - /// \e + /// \brief Arc map reading rule + /// + /// Add an arc map reading rule with specialized converter to the + /// reader. template DigraphReader& arcMap(const std::string& caption, Map& map, const Converter& converter = Converter()) { @@ -448,7 +495,9 @@ return *this; } - /// \e + /// \brief Attribute reading rule + /// + /// Add an attribute reading rule to the reader. template DigraphReader& attribute(const std::string& caption, Value& value) { _reader_bits::ValueStorageBase* storage = @@ -457,7 +506,10 @@ return *this; } - /// \e + /// \brief Attribute reading rule + /// + /// Add an attribute reading rule with specialized converter to the + /// reader. template DigraphReader& attribute(const std::string& caption, Value& value, const Converter& converter = Converter()) { @@ -467,7 +519,9 @@ return *this; } - /// \e + /// \brief Node reading rule + /// + /// Add a node reading rule to reader. DigraphReader& node(const std::string& caption, Node& node) { typedef _reader_bits::MapLookUpConverter Converter; Converter converter(_node_index); @@ -477,7 +531,9 @@ return *this; } - /// \e + /// \brief Arc reading rule + /// + /// Add an arc reading rule to reader. DigraphReader& arc(const std::string& caption, Arc& arc) { typedef _reader_bits::MapLookUpConverter Converter; Converter converter(_arc_index); @@ -487,25 +543,44 @@ return *this; } - /// \e + /// @} + + /// \name Select section by name + /// @{ + + /// \brief Set \c \@nodes section to be read + /// + /// Set \c \@nodes section to be read DigraphReader& nodes(const std::string& caption) { _nodes_caption = caption; return *this; } - /// \e + /// \brief Set \c \@arcs section to be read + /// + /// Set \c \@arcs section to be read DigraphReader& arcs(const std::string& caption) { _arcs_caption = caption; return *this; } - /// \e + /// \brief Set \c \@attributes section to be read + /// + /// Set \c \@attributes section to be read DigraphReader& attributes(const std::string& caption) { _attributes_caption = caption; return *this; } - /// \e + /// @} + + /// \name Using previously constructed node or arc set + /// @{ + + /// \brief Use previously constructed node set + /// + /// Use previously constructed node set, and specify the node + /// label map. template DigraphReader& useNodes(const Map& map) { checkConcept, Map>(); @@ -518,7 +593,11 @@ return *this; } - /// \e + /// \brief Use previously constructed node set + /// + /// Use previously constructed node set, and specify the node + /// label map and a functor which converts the label map values to + /// std::string. template DigraphReader& useNodes(const Map& map, const Converter& converter = Converter()) { @@ -531,7 +610,10 @@ return *this; } - /// \e + /// \brief Use previously constructed arc set + /// + /// Use previously constructed arc set, and specify the arc + /// label map. template DigraphReader& useArcs(const Map& map) { checkConcept, Map>(); @@ -544,7 +626,11 @@ return *this; } - /// \e + /// \brief Use previously constructed arc set + /// + /// Use previously constructed arc set, and specify the arc + /// label map and a functor which converts the label map values to + /// std::string. template DigraphReader& useArcs(const Map& map, const Converter& converter = Converter()) { @@ -557,6 +643,8 @@ return *this; } + /// @} + private: bool readLine() { @@ -597,7 +685,7 @@ std::string map; int index = 0; - while (_reader_bits::readIdentifier(line, map)) { + while (_reader_bits::readToken(line, map)) { if (maps.find(map) != maps.end()) { std::ostringstream msg; msg << "Multiple occurence of node map: " << map; @@ -680,7 +768,7 @@ std::string map; int index = 0; - while (_reader_bits::readIdentifier(line, map)) { + while (_reader_bits::readToken(line, map)) { if (maps.find(map) != maps.end()) { std::ostringstream msg; msg << "Multiple occurence of arc map: " << map; @@ -787,7 +875,7 @@ line.putback(c); std::string attr, token; - if (!_reader_bits::readIdentifier(line, attr)) + if (!_reader_bits::readToken(line, attr)) throw DataFormatError("Attribute name not found"); if (!_reader_bits::readToken(line, token)) throw DataFormatError("Attribute value not found"); @@ -827,8 +915,13 @@ } public: - - /// \e + + /// \name Execution of the reader + /// @{ + + /// \brief Start the batch processing + /// + /// This function starts the batch processing void run() { LEMON_ASSERT(_is != 0, "This reader assigned to an other reader"); @@ -846,8 +939,8 @@ char c; std::string section, caption; line >> c; - _reader_bits::readIdentifier(line, section); - _reader_bits::readIdentifier(line, caption); + _reader_bits::readToken(line, section); + _reader_bits::readToken(line, caption); if (line >> c) throw DataFormatError("Extra character on the end of line"); @@ -891,20 +984,25 @@ } } + + /// @} }; + /// \relates DigraphReader template DigraphReader digraphReader(std::istream& is, Digraph& digraph) { return DigraphReader(is, digraph); } + /// \relates DigraphReader template DigraphReader digraphReader(const std::string& fn, Digraph& digraph) { return DigraphReader(fn, digraph); } + /// \relates DigraphReader template DigraphReader digraphReader(const char* fn, Digraph& digraph) { return DigraphReader(fn, digraph); diff --git a/lemon/lgf_writer.h b/lemon/lgf_writer.h --- a/lemon/lgf_writer.h +++ b/lemon/lgf_writer.h @@ -204,6 +204,7 @@ } bool requireEscape(const std::string& str) { + if (str.empty() || str[0] == '@') return true; std::istringstream is(str); char c; while (is.get(c)) { @@ -231,7 +232,50 @@ } - /// \e + /// \ingroup lemon_io + /// + /// \brief LGF writer for directed graphs + /// + /// This utility writes an \ref lgf-format "LGF" file. + /// + /// The writing method does a batch processing. The user creates a + /// writer object, then various writing rules can be added to the + /// writer, and eventually the writing is executed with the \c run() + /// member function. A map writing rule can be added to the writer + /// with the \c nodeMap() or \c arcMap() members. An optional + /// converter parameter can also be added as a standard functor converting from + /// the value type of the map to std::string. If it is set, it will + /// determine how the map's value type is written to the output + /// stream. If the functor is not set, then a default conversion + /// will be used. The \c attribute(), \c node() and \c arc() functions + /// are used to add attribute writing rules. + /// + ///\code + /// DigraphWriter(std::cout, digraph). + /// nodeMap("coordinates", coord_map). + /// nodeMap("size", size). + /// nodeMap("title", title). + /// arcMap("capacity", cap_map). + /// node("source", src). + /// node("target", trg). + /// attribute("caption", caption). + /// run(); + ///\endcode + /// + /// + /// By default, the writer does not write additional captions to the + /// sections, but they can be give as an optional parameter of + /// the \c nodes(), \c arcs() or \c + /// attributes() functions. + /// + /// The \c skipNodes() and \c skipArcs() functions forbid the + /// writing of the sections. If two arc sections should be written to the + /// output, it can be done in two passes, the first pass writes the + /// node section and the first arc section, then the second pass + /// skips the node section and writes just the arc section to the + /// stream. The output stream can be retrieved with the \c ostream() + /// function, hence the second pass can append its output to the output of the + /// first pass. template class DigraphWriter { public: @@ -273,21 +317,34 @@ public: - /// \e + /// \brief Constructor + /// + /// Construct a directed graph writer, which writes to the given + /// output stream. DigraphWriter(std::ostream& is, Digraph& digraph) : _os(&is), local_os(false), _digraph(digraph), _skip_nodes(false), _skip_arcs(false) {} - /// \e + /// \brief Constructor + /// + /// Construct a directed graph writer, which writes to the given + /// output file. DigraphWriter(const std::string& fn, Digraph& digraph) : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph), _skip_nodes(false), _skip_arcs(false) {} - /// \e + /// \brief Constructor + /// + /// Construct a directed graph writer, which writes to the given + /// output file. DigraphWriter(const char* fn, Digraph& digraph) : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph), _skip_nodes(false), _skip_arcs(false) {} + /// \brief Copy constructor + /// + /// The copy constructor transfers all data from the other writer, + /// therefore the copied writer will not be usable more. DigraphWriter(DigraphWriter& other) : _os(other._os), local_os(other.local_os), _digraph(other._digraph), _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) { @@ -307,7 +364,7 @@ _attributes_caption = other._attributes_caption; } - /// \e + /// \brief Destructor ~DigraphWriter() { for (typename NodeMaps::iterator it = _node_maps.begin(); it != _node_maps.end(); ++it) { @@ -335,7 +392,12 @@ public: - /// \e + /// \name Writing rules + /// @{ + + /// \brief Node map reading rule + /// + /// Add a node map reading rule to the writer. template DigraphWriter& nodeMap(const std::string& caption, const Map& map) { checkConcept, Map>(); @@ -345,7 +407,10 @@ return *this; } - /// \e + /// \brief Node map writing rule + /// + /// Add a node map writing rule with specialized converter to the + /// writer. template DigraphWriter& nodeMap(const std::string& caption, const Map& map, const Converter& converter = Converter()) { @@ -356,7 +421,9 @@ return *this; } - /// \e + /// \brief Arc map writing rule + /// + /// Add an arc map writing rule to the writer. template DigraphWriter& arcMap(const std::string& caption, const Map& map) { checkConcept, Map>(); @@ -366,7 +433,10 @@ return *this; } - /// \e + /// \brief Arc map writing rule + /// + /// Add an arc map writing rule with specialized converter to the + /// writer. template DigraphWriter& arcMap(const std::string& caption, const Map& map, const Converter& converter = Converter()) { @@ -377,7 +447,9 @@ return *this; } - /// \e + /// \brief Attribute writing rule + /// + /// Add an attribute writing rule to the writer. template DigraphWriter& attribute(const std::string& caption, const Value& value) { _writer_bits::ValueStorageBase* storage = @@ -386,7 +458,10 @@ return *this; } - /// \e + /// \brief Attribute writing rule + /// + /// Add an attribute writing rule with specialized converter to the + /// writer. template DigraphWriter& attribute(const std::string& caption, const Value& value, const Converter& converter = Converter()) { @@ -396,7 +471,9 @@ return *this; } - /// \e + /// \brief Node writing rule + /// + /// Add a node writing rule to the writer. DigraphWriter& node(const std::string& caption, const Node& node) { typedef _writer_bits::MapLookUpConverter Converter; Converter converter(_node_index); @@ -406,7 +483,9 @@ return *this; } - /// \e + /// \brief Arc writing rule + /// + /// Add an arc writing rule to writer. DigraphWriter& arc(const std::string& caption, const Arc& arc) { typedef _writer_bits::MapLookUpConverter Converter; Converter converter(_arc_index); @@ -416,34 +495,54 @@ return *this; } - /// \e + /// \name Select section by name + /// @{ + + /// \brief Set \c \@nodes section to be read + /// + /// Set \c \@nodes section to be read DigraphWriter& nodes(const std::string& caption) { _nodes_caption = caption; return *this; } - /// \e + /// \brief Set \c \@arcs section to be read + /// + /// Set \c \@arcs section to be read DigraphWriter& arcs(const std::string& caption) { _arcs_caption = caption; return *this; } - /// \e + /// \brief Set \c \@attributes section to be read + /// + /// Set \c \@attributes section to be read DigraphWriter& attributes(const std::string& caption) { _attributes_caption = caption; return *this; } + /// \name Skipping section + /// @{ + + /// \brief Skip writing the node set + /// + /// The \c \@nodes section will be not written to the stream. DigraphWriter& skipNodes() { LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member"); return *this; } + /// \brief Skip writing arc set + /// + /// The \c \@arcs section will be not written to the stream. DigraphWriter& skipArcs() { LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member"); return *this; } + /// @} + private: void writeNodes() { @@ -458,7 +557,7 @@ *_os << "@nodes"; if (!_nodes_caption.empty()) { - *_os << ' ' << _nodes_caption; + _writer_bits::writeToken(*_os << ' ', _nodes_caption); } *_os << std::endl; @@ -467,7 +566,7 @@ } for (typename NodeMaps::iterator it = _node_maps.begin(); it != _node_maps.end(); ++it) { - *_os << it->first << '\t'; + _writer_bits::writeToken(*_os, it->first) << '\t'; } *_os << std::endl; @@ -518,7 +617,7 @@ *_os << "@arcs"; if (!_arcs_caption.empty()) { - *_os << ' ' << _arcs_caption; + _writer_bits::writeToken(*_os << ' ', _arcs_caption); } *_os << std::endl; @@ -528,7 +627,7 @@ } for (typename ArcMaps::iterator it = _arc_maps.begin(); it != _arc_maps.end(); ++it) { - *_os << it->first << '\t'; + _writer_bits::writeToken(*_os, it->first) << '\t'; } *_os << std::endl; @@ -577,12 +676,12 @@ if (_attributes.empty()) return; *_os << "@attributes"; if (!_attributes_caption.empty()) { - *_os << ' ' << _attributes_caption; + _writer_bits::writeToken(*_os << ' ', _attributes_caption); } *_os << std::endl; for (typename Attributes::iterator it = _attributes.begin(); it != _attributes.end(); ++it) { - *_os << it->first << ' '; + _writer_bits::writeToken(*_os, it->first) << ' '; _writer_bits::writeToken(*_os, it->second->get()); *_os << std::endl; } @@ -590,7 +689,12 @@ public: - /// \e + /// \name Execution of the writer + /// @{ + + /// \brief Start the batch processing + /// + /// This function starts the batch processing void run() { if (!_skip_nodes) { writeNodes(); @@ -601,23 +705,30 @@ writeAttributes(); } - /// \e - std::ostream& stream() { + /// \brief Gives back the stream of the writer + /// + /// Gives back the stream of the writer + std::ostream& ostream() { return *_os; } + + /// @} }; + /// \relates DigraphWriter template DigraphWriter digraphWriter(std::istream& is, Digraph& digraph) { return DigraphWriter(is, digraph); } + /// \relates DigraphWriter template DigraphWriter digraphWriter(const std::string& fn, Digraph& digraph) { return DigraphWriter(fn, digraph); } + /// \relates DigraphWriter template DigraphWriter digraphWriter(const char* fn, Digraph& digraph) { return DigraphWriter(fn, digraph);