Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 154)
+++ doc/Makefile.am (revision 156)
@@ -4,4 +4,5 @@
doc/dirs.dox \
doc/groups.dox \
+ doc/lgf.dox \
doc/license.dox \
doc/mainpage.dox \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 83)
+++ doc/groups.dox (revision 156)
@@ -484,23 +484,4 @@
/**
-@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
Index: doc/lgf.dox
===================================================================
--- doc/lgf.dox (revision 156)
+++ doc/lgf.dox (revision 156)
@@ -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
Index: lemon/lgf_reader.h
===================================================================
--- lemon/lgf_reader.h (revision 148)
+++ lemon/lgf_reader.h (revision 156)
@@ -269,33 +269,56 @@
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 {
@@ -342,21 +365,32 @@
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),
@@ -378,5 +412,5 @@
}
- /// \e
+ /// \brief Destructor
~DigraphReader() {
for (typename NodeMaps::iterator it = _node_maps.begin();
@@ -407,5 +441,10 @@
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) {
@@ -417,5 +456,8 @@
}
- /// \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,
@@ -428,5 +470,7 @@
}
- /// \e
+ /// \brief Arc map reading rule
+ ///
+ /// Add an arc map reading rule to the reader.
template
DigraphReader& arcMap(const std::string& caption, Map& map) {
@@ -438,5 +482,8 @@
}
- /// \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,
@@ -449,5 +496,7 @@
}
- /// \e
+ /// \brief Attribute reading rule
+ ///
+ /// Add an attribute reading rule to the reader.
template
DigraphReader& attribute(const std::string& caption, Value& value) {
@@ -458,5 +507,8 @@
}
- /// \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,
@@ -468,5 +520,7 @@
}
- /// \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;
@@ -478,5 +532,7 @@
}
- /// \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;
@@ -488,5 +544,12 @@
}
- /// \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;
@@ -494,5 +557,7 @@
}
- /// \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;
@@ -500,5 +565,7 @@
}
- /// \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;
@@ -506,5 +573,13 @@
}
- /// \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) {
@@ -519,5 +594,9 @@
}
- /// \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,
@@ -532,5 +611,8 @@
}
- /// \e
+ /// \brief Use previously constructed arc set
+ ///
+ /// Use previously constructed arc set, and specify the arc
+ /// label map.
template
DigraphReader& useArcs(const Map& map) {
@@ -545,5 +627,9 @@
}
- /// \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,
@@ -558,4 +644,6 @@
}
+ /// @}
+
private:
@@ -598,5 +686,5 @@
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;
@@ -681,5 +769,5 @@
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;
@@ -788,5 +876,5 @@
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))
@@ -828,6 +916,11 @@
public:
-
- /// \e
+
+ /// \name Execution of the reader
+ /// @{
+
+ /// \brief Start the batch processing
+ ///
+ /// This function starts the batch processing
void run() {
@@ -847,6 +940,6 @@
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)
@@ -892,7 +985,10 @@
}
+
+ /// @}
};
+ /// \relates DigraphReader
template
DigraphReader digraphReader(std::istream& is, Digraph& digraph) {
@@ -900,4 +996,5 @@
}
+ /// \relates DigraphReader
template
DigraphReader digraphReader(const std::string& fn,
@@ -906,4 +1003,5 @@
}
+ /// \relates DigraphReader
template
DigraphReader digraphReader(const char* fn, Digraph& digraph) {
Index: lemon/lgf_writer.h
===================================================================
--- lemon/lgf_writer.h (revision 148)
+++ lemon/lgf_writer.h (revision 156)
@@ -205,4 +205,5 @@
bool requireEscape(const std::string& str) {
+ if (str.empty() || str[0] == '@') return true;
std::istringstream is(str);
char c;
@@ -232,5 +233,48 @@
}
- /// \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 {
@@ -274,19 +318,32 @@
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),
@@ -308,5 +365,5 @@
}
- /// \e
+ /// \brief Destructor
~DigraphWriter() {
for (typename NodeMaps::iterator it = _node_maps.begin();
@@ -336,5 +393,10 @@
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) {
@@ -346,5 +408,8 @@
}
- /// \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,
@@ -357,5 +422,7 @@
}
- /// \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) {
@@ -367,5 +434,8 @@
}
- /// \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,
@@ -378,5 +448,7 @@
}
- /// \e
+ /// \brief Attribute writing rule
+ ///
+ /// Add an attribute writing rule to the writer.
template
DigraphWriter& attribute(const std::string& caption, const Value& value) {
@@ -387,5 +459,8 @@
}
- /// \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,
@@ -397,5 +472,7 @@
}
- /// \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;
@@ -407,5 +484,7 @@
}
- /// \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;
@@ -417,5 +496,10 @@
}
- /// \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;
@@ -423,5 +507,7 @@
}
- /// \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;
@@ -429,5 +515,7 @@
}
- /// \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;
@@ -435,4 +523,10 @@
}
+ /// \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");
@@ -440,8 +534,13 @@
}
+ /// \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:
@@ -459,5 +558,5 @@
*_os << "@nodes";
if (!_nodes_caption.empty()) {
- *_os << ' ' << _nodes_caption;
+ _writer_bits::writeToken(*_os << ' ', _nodes_caption);
}
*_os << std::endl;
@@ -468,5 +567,5 @@
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;
@@ -519,5 +618,5 @@
*_os << "@arcs";
if (!_arcs_caption.empty()) {
- *_os << ' ' << _arcs_caption;
+ _writer_bits::writeToken(*_os << ' ', _arcs_caption);
}
*_os << std::endl;
@@ -529,5 +628,5 @@
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;
@@ -578,10 +677,10 @@
*_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;
@@ -591,5 +690,10 @@
public:
- /// \e
+ /// \name Execution of the writer
+ /// @{
+
+ /// \brief Start the batch processing
+ ///
+ /// This function starts the batch processing
void run() {
if (!_skip_nodes) {
@@ -602,10 +706,15 @@
}
- /// \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) {
@@ -613,4 +722,5 @@
}
+ /// \relates DigraphWriter
template
DigraphWriter digraphWriter(const std::string& fn,
@@ -619,4 +729,5 @@
}
+ /// \relates DigraphWriter
template
DigraphWriter digraphWriter(const char* fn, Digraph& digraph) {