RhodeCode

/// "DigraphReader" class.

///

/// The \c "digraph.lgf" file:

/// \include digraph.lgf

///

/// And the program which reads it:

/// \include lgf_demo.cc

#include <iostream>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/lgf_writer.h>

using namespace lemon;

int main() {

  SmartDigraph g;

  SmartDigraph::ArcMap<int> cap(g);

  SmartDigraph::Node s, t;

    arcMap("capacity", cap).       // read the 'capacity' arc map into cap

    node("source", s).             // read 'source' node to s

    node("target", t).             // read 'target' node to t

    run();

  std::cout << "Number of nodes: " << countNodes(g) << std::endl;

  std::cout << "Number of arcs: " << countArcs(g) << std::endl;

  std::cout << "We can write it to the standard output:" << std::endl;

  digraphWriter(std::cout, g).     // write g to the standard output

    arcMap("capacity", cap).       // write cap into 'capacity'

    node("source", s).             // write s to 'source'

    node("target", t).             // write t to 'target'

    run();

  return 0;

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

This group describes the tools for importing and exporting graphs 

and graph related data. Now it supports the LEMON format, the

\c DIMACS format and the encapsulated postscript (EPS) format.

*/

/**

@defgroup lemon_io Lemon Input-Output

@ingroup io_group

*/

/**

@defgroup eps_io Postscript exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group describes general \c EPS drawing methods and special

graph exporting tools. 

*/

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

<em>token</em>s 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 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,

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

 * 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.

 *

 */

///\ingroup lemon_io

///\file

#ifndef LEMON_LGF_READER_H

#define LEMON_LGF_READER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <set>

#include <map>

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph);

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const std::string& fn, Digraph& digraph);

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const char *fn, Digraph& digraph);

  /// \ingroup lemon_io

  ///  

  ///

  /// 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

  /// is set, it will determine how the tokens in the file should be

  /// 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

  ///\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

  /// 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

  /// a single pass, because the arcs are not constructed when the node

  /// maps are read.

  template <typename _Digraph>

  class DigraphReader {

  public:

    typedef _Digraph Digraph;

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  private:

      _use_nodes = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (NodeIt n(_digraph); n != INVALID; ++n) {

	_node_index.insert(std::make_pair(converter(map[n]), n));

      }

      return *this;

    }

    /// \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

    template <typename Map, typename Converter>

    DigraphReader& useNodes(const Map& map, 

			    const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 

      _use_nodes = true;

      for (NodeIt n(_digraph); n != INVALID; ++n) {

	_node_index.insert(std::make_pair(converter(map[n]), n));

      }

      return *this;

    }

      _use_arcs = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (ArcIt a(_digraph); a != INVALID; ++a) {

	_arc_index.insert(std::make_pair(converter(map[a]), a));

      }

      return *this;

    }

    /// \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

    template <typename Map, typename Converter>

    DigraphReader& useArcs(const Map& map, 

			   const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member"); 

      _use_arcs = true;

      for (ArcIt a(_digraph); a != INVALID; ++a) {

	_arc_index.insert(std::make_pair(converter(map[a]), a));

      }

      return *this;

    }

    /// \brief Skips the reading of node section

    ///

    /// Omit the reading of the node section. This implies that each node

    /// will not be constructed, which usually cause that the arc set

    DigraphReader& skipNodes() {

      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 

      _skip_nodes = true;

      return *this;

    }

    /// \brief Skips the reading of arc section

    ///

    /// Omit the reading of the arc section. This implies that each arc

    /// will not be constructed.

    DigraphReader& skipArcs() {

      LEMON_ASSERT(!_skip_arcs, "Skip arcs already set"); 

      _skip_arcs = true;

      return *this;

    }

    /// @}

  private:

    bool readLine() {

      }

      if (!attributes_done && !_attributes.empty()) {

	throw DataFormatError("Section @attributes not found");

      }

    }

    /// @}

  };

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {

    DigraphReader<Digraph> tmp(is, digraph);

    return tmp;

  }

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const std::string& fn, 

				       Digraph& digraph) {

    DigraphReader<Digraph> tmp(fn, digraph);

    return tmp;

  }

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {

    DigraphReader<Digraph> tmp(fn, digraph);

    return tmp;

  }

  template <typename Graph>

  class GraphReader;

  template <typename Graph>

  GraphReader<Graph> graphReader(std::istream& is, Graph& graph);    

  template <typename Graph>

  GraphReader<Graph> graphReader(const std::string& fn, Graph& graph);   

  template <typename Graph>

  GraphReader<Graph> graphReader(const char *fn, Graph& graph);    

  /// \ingroup lemon_io

  ///  

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  template <typename _Graph>

  class GraphReader {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    std::istream* _is;

    bool local_is;

    bool _use_edges;

    bool _skip_nodes;

    bool _skip_edges;

    int line_num;

    std::istringstream line;

  public:

    /// \brief Constructor

    ///

    /// input stream.

    GraphReader(std::istream& is, Graph& graph) 

      : _is(&is), local_is(false), _graph(graph),

	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// file.

    GraphReader(const std::string& fn, Graph& graph) 

      : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),

    	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// file.

    GraphReader(const char* fn, Graph& graph) 

      : _is(new std::ifstream(fn)), local_is(true), _graph(graph),

    	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Destructor

    ~GraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin(); 

	   it != _node_maps.end(); ++it) {

	delete it->second;

      }

	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// @}

    /// \name Select section by name

    /// @{

    /// \brief Set \c \@nodes section to be read

    ///

    GraphReader& nodes(const std::string& caption) {

      _nodes_caption = caption;

      return *this;

    }

    /// \brief Set \c \@edges section to be read

    ///

    GraphReader& edges(const std::string& caption) {

      _edges_caption = caption;

      return *this;

    }

    /// \brief Set \c \@attributes section to be read

    ///

    GraphReader& attributes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// @}

    /// \name Using previously constructed node or edge set

    /// @{

    /// \brief Use previously constructed node set

    ///

      _use_nodes = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (NodeIt n(_graph); n != INVALID; ++n) {

	_node_index.insert(std::make_pair(converter(map[n]), n));

      }

      return *this;

    }

    /// \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

    template <typename Map, typename Converter>

    GraphReader& useNodes(const Map& map, 

			    const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 

      _use_nodes = true;

      for (NodeIt n(_graph); n != INVALID; ++n) {

	_node_index.insert(std::make_pair(converter(map[n]), n));

      }

      return *this;

    }

      _use_edges = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (EdgeIt a(_graph); a != INVALID; ++a) {

	_edge_index.insert(std::make_pair(converter(map[a]), a));

      }

      return *this;

    }

    /// \brief Use previously constructed edge set

    ///

    /// Use previously constructed edge set, and specify the edge

    /// label map and a functor which converts the label map values to

    template <typename Map, typename Converter>

    GraphReader& useEdges(const Map& map, 

			    const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 

      _use_edges = true;

      for (EdgeIt a(_graph); a != INVALID; ++a) {

	_edge_index.insert(std::make_pair(converter(map[a]), a));

      }

      return *this;

    }

    ///

    /// Omit the reading of the node section. This implies that each node

    /// will not be constructed, which usually cause that the edge set

    /// could not be read due to lack of node name

    GraphReader& skipNodes() {

      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 

      _skip_nodes = true;

      return *this;

    }

    ///

    /// Omit the reading of the edge section. This implies that each edge

    /// will not be constructed.

    GraphReader& skipEdges() {

      LEMON_ASSERT(!_skip_edges, "Skip edges already set"); 

      _skip_edges = true;

      return *this;

    }

    /// @}

  private:

    bool readLine() {

      }

      if (!attributes_done && !_attributes.empty()) {

	throw DataFormatError("Section @attributes not found");

      }

    }

    /// @}

  };

  /// \relates GraphReader

  template <typename Graph>

  GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {

    GraphReader<Graph> tmp(is, graph);

    return tmp;

  }

  /// \relates GraphReader

  template <typename Graph>

  GraphReader<Graph> graphReader(const std::string& fn, 

				       Graph& graph) {

    GraphReader<Graph> tmp(fn, graph);

    return tmp;

  }

  /// \relates GraphReader

  template <typename Graph>

  GraphReader<Graph> graphReader(const char* fn, Graph& graph) {

    GraphReader<Graph> tmp(fn, graph);

    return tmp;

  }

  class SectionReader;

  SectionReader sectionReader(std::istream& is);

  SectionReader sectionReader(const std::string& fn);

  SectionReader sectionReader(const char* fn);

  /// \brief Section reader class

  ///

  /// sectionStream() member the section can be read from an input

  /// stream.

  class SectionReader {

  private:

    std::istream* _is;

    bool local_is;

    typedef std::map<std::string, _reader_bits::Section*> Sections;

    Sections _sections;

    int line_num;

    /// and the comment lines are filtered out, and the leading

    /// whitespaces are trimmed from each processed string.

    ///

    /// For example let's see a section, which contain several

    /// integers, which should be inserted into a vector.

    ///\code

    ///  @numbers

    ///  12 45 23

    ///  4

    ///  23 6

    ///\endcode

    ///

    ///\code

    ///  struct NumberSection {

    ///    std::vector<int>& _data;

    ///    NumberSection(std::vector<int>& data) : _data(data) {}

    ///    void operator()(const std::string& line) {

    ///      std::istringstream ls(line);

    ///      int value;

    ///      while (ls >> value) _data.push_back(value);

    ///    }

    ///  };

    ///

    ///  // ...

    ///

    ///  reader.sectionLines("numbers", NumberSection(vec));  

    ///\endcode

    template <typename Functor>

    SectionReader& sectionLines(const std::string& type, Functor functor) {

      LEMON_ASSERT(_sections.find(type) == _sections.end(), 

		   "Multiple reading of section.");

      _sections.insert(std::make_pair(type, 

        new _reader_bits::LineSection<Functor>(functor)));

      return *this;

    }

    /// \brief Add a section processor with stream oriented reading

    ///

    /// The first parameter is the type of the section, the second is

    /// parameter, the latter regard to the line number of stream. The

    /// functor can read the input while the section go on, and the

    /// line number should be modified accordingly.

    template <typename Functor>

    SectionReader& sectionStream(const std::string& type, Functor functor) {

      LEMON_ASSERT(_sections.find(type) == _sections.end(), 

		   "Multiple reading of section.");

      _sections.insert(std::make_pair(type, 

	 new _reader_bits::StreamSection<Functor>(functor)));

      return *this;

    }    

    /// @}

  private:

    bool readLine() {

      }

      line.putback(c);

    }

  public:

    /// \name Execution of the reader    

    /// @{

    /// \brief Start the batch processing

    ///

    void run() {

      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");

      std::set<std::string> extra_sections;

      line_num = 0;      

      readLine();

      skipSection();

      while (readSuccess()) {

	try {

	if (extra_sections.find(it->first) == extra_sections.end()) {

	  std::ostringstream os;

	  os << "Cannot find section: " << it->first;

	  throw DataFormatError(os.str().c_str());

	}

      }

    }

    /// @}

  };

  /// \relates SectionReader

  inline SectionReader sectionReader(std::istream& is) {

    SectionReader tmp(is);

    return tmp;

  }

  /// \relates SectionReader

  inline SectionReader sectionReader(const std::string& fn) {

    SectionReader tmp(fn);

    return tmp;

  }

  /// \relates SectionReader

  inline SectionReader sectionReader(const char* fn) {

    SectionReader tmp(fn);

    return tmp;

  }

  /// \ingroup lemon_io

  ///

  /// \brief Reader for the contents of the \ref lgf-format "LGF" file 

  ///

  /// This class can be used to read the sections, the map names and

  /// the attributes from a file. Usually, the Lemon programs know

  /// that, which type of graph, which maps and which attributes

  /// should be read from a file, but in general tools (like glemon)

  /// the contents of an LGF file should be guessed somehow. This class

  /// reads the graph and stores the appropriate information for

  /// reading the graph.

  ///

  /// contents.run();

  ///

  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {

  ///   return -1;

  /// }

  ///           << contents.nodeSection(0) << std::endl;

  ///           << contents.arcMaps(0).size() << std::endl;

  ///           << contents.arcMaps(0)[1] << std::endl;

  ///\endcode

  class LgfContents {    

  private:

    std::istream* _is;

    bool local_is;

    std::vector<std::string> _node_sections;

    std::vector<std::string> _edge_sections;

    std::vector<std::string> _attribute_sections;

    std::vector<std::string> _extra_sections;

    /// \name Node sections

    /// @{

    /// \brief Gives back the number of node sections in the file.

    ///

    /// Gives back the number of node sections in the file.

    int nodeSectionNum() const {

      return _node_sections.size();

    }

    ///

    const std::string& nodeSection(int i) const {

      return _node_sections[i];

    }

    /// \brief Gives back the node maps for the given section.

    ///

    /// Gives back the node maps for the given section.

    const std::vector<std::string>& nodeMapNames(int i) const {

      return _node_maps[i];

    }

    /// @}

    /// \name Arc/Edge sections 

    /// @{

    /// \brief Gives back the number of arc/edge sections in the file.

    ///

    /// Gives back the number of arc/edge sections in the file.

    /// \note It is synonym of \c edgeSectionNum().

    int arcSectionNum() const {

      return _edge_sections.size();

    }

    ///

    /// \note It is synonym of \c edgeSection().

    const std::string& arcSection(int i) const {

      return _edge_sections[i];

    }

    /// \brief Gives back the arc/edge maps for the given section.

    ///

    /// Gives back the arc/edge maps for the given section.

    /// \note It is synonym of \c edgeMapNames().

    const std::vector<std::string>& arcMapNames(int i) const {

      return _edge_maps[i];

    }

    /// @}

    /// \name Attribute sections   

    /// @{

    /// \brief Gives back the number of attribute sections in the file.

    ///

    /// Gives back the number of attribute sections in the file.

    int attributeSectionNum() const {

      return _attribute_sections.size();

    }

    ///

    const std::string& attributeSectionNames(int i) const {

      return _attribute_sections[i];

    }

    /// \brief Gives back the attributes for the given section.

    ///

    /// Gives back the attributes for the given section.

    const std::vector<std::string>& attributes(int i) const {

      return _attributes[i];

    }

    /// @}

	_reader_bits::readToken(line, attr);

	attrs.push_back(attr);

	readLine();

      }

      line.putback(c);

    }

  public:

    /// \name Execution of the contents reader    

    /// @{

    ///

    void run() {

      readLine();

      skipSection();

      while (readSuccess()) {

	char c;

	line >> c;

	std::string section, caption;

	_reader_bits::readToken(line, section);

 * 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.

 *

 */

///\ingroup lemon_io

///\file

#ifndef LEMON_LGF_WRITER_H

#define LEMON_LGF_WRITER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <vector>

				       const Digraph& digraph);

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const std::string& fn, 

				       const Digraph& digraph);

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const char *fn, 

				       const Digraph& digraph);

  /// \ingroup lemon_io

  ///  

  ///

  /// 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

  /// 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

  ///\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

      _nodes_caption = other._nodes_caption;

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphWriter& operator=(const DigraphWriter&);

  public:

    /// \name Writing rules

    /// @{

    ///

    template <typename Map>

    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      _writer_bits::MapStorageBase<Node>* storage = 

	new _writer_bits::MapStorage<Node, Map>(map);

      _node_maps.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Node map writing rule

    ///

    /// Add a node map writing rule with specialized converter to the

    /// \brief Arc writing rule

    ///

    /// Add an arc writing rule to writer.

    DigraphWriter& arc(const std::string& caption, const Arc& arc) {

      typedef _writer_bits::MapLookUpConverter<Arc> Converter;

      Converter converter(_arc_index);

      _writer_bits::ValueStorageBase* storage =