RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * 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 <em>column oriented</em>

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

<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. The first is a header line, its 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

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 \@arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

//  LocalWords:  whitespace whitespaces

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

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

 *

 */

///\ingroup lemon_io

///\file

///\brief \ref lgf-format "LEMON Graph Format" reader.

#ifndef LEMON_LGF_READER_H

#define LEMON_LGF_READER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <set>

#include <map>

#include <lemon/core.h>

#include <lemon/lgf_writer.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

namespace lemon {

  namespace _reader_bits {

    template <typename Value>

    struct DefaultConverter {

      Value operator()(const std::string& str) {

        std::istringstream is(str);

        Value value;

        if (!(is >> value)) {

          throw FormatError("Cannot read token");

        }

        char c;

        if (is >> std::ws >> c) {

          throw FormatError("Remaining characters in token");

        }

        return value;

      }

    };

    template <>

    struct DefaultConverter<std::string> {

      std::string operator()(const std::string& str) {

        return str;

      }

    };

    template <typename _Item>

    class MapStorageBase {

    public:

      typedef _Item Item;

    public:

      MapStorageBase() {}

      virtual ~MapStorageBase() {}

      virtual void set(const Item& item, const std::string& value) = 0;

    };

    template <typename _Item, typename _Map,

              typename _Converter = DefaultConverter<typename _Map::Value> >

    class MapStorage : public MapStorageBase<_Item> {

    public:

      typedef _Map Map;

      typedef _Converter Converter;

      typedef _Item Item;

    private:

      Map& _map;

      Converter _converter;

    public:

      MapStorage(Map& map, const Converter& converter = Converter())

        : _map(map), _converter(converter) {}

      virtual ~MapStorage() {}

      virtual void set(const Item& item ,const std::string& value) {

        _map.set(item, _converter(value));

      }

    };

    template <typename _GR, bool _dir, typename _Map,

              typename _Converter = DefaultConverter<typename _Map::Value> >

    class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> {

    public:

      typedef _Map Map;

      typedef _Converter Converter;

      typedef _GR GR;

      typedef typename GR::Edge Item;

      static const bool dir = _dir;

    private:

      const GR& _graph;

      Map& _map;

      Converter _converter;

    public:

      GraphArcMapStorage(const GR& graph, Map& map,

                         const Converter& converter = Converter())

        : _graph(graph), _map(map), _converter(converter) {}

      virtual ~GraphArcMapStorage() {}

      virtual void set(const Item& item ,const std::string& value) {

        _map.set(_graph.direct(item, dir), _converter(value));

      }

    };

    class ValueStorageBase {

    public:

      ValueStorageBase() {}

      virtual ~ValueStorageBase() {}

      virtual void set(const std::string&) = 0;

    };

    template <typename _Value, typename _Converter = DefaultConverter<_Value> >

    class ValueStorage : public ValueStorageBase {

    public:

      typedef _Value Value;

      typedef _Converter Converter;

    private:

      Value& _value;

      Converter _converter;

    public:

      ValueStorage(Value& value, const Converter& converter = Converter())

        : _value(value), _converter(converter) {}

      virtual void set(const std::string& value) {

        _value = _converter(value);

      }

    };

    template <typename Value>

    struct MapLookUpConverter {

      const std::map<std::string, Value>& _map;

      MapLookUpConverter(const std::map<std::string, Value>& map)

        : _map(map) {}

      Value operator()(const std::string& str) {

        typename std::map<std::string, Value>::const_iterator it =

          _map.find(str);

        if (it == _map.end()) {

          std::ostringstream msg;

          msg << "Item not found: " << str;

          throw FormatError(msg.str());

        }

        return it->second;

      }

    };

    template <typename GR>

    struct GraphArcLookUpConverter {

      const GR& _graph;

      const std::map<std::string, typename GR::Edge>& _map;

      GraphArcLookUpConverter(const GR& graph,

                              const std::map<std::string,

                                             typename GR::Edge>& map)

        : _graph(graph), _map(map) {}

      typename GR::Arc operator()(const std::string& str) {

        if (str.empty() || (str[0] != '+' && str[0] != '-')) {

          throw FormatError("Item must start with '+' or '-'");

        }

        typename std::map<std::string, typename GR::Edge>

          ::const_iterator it = _map.find(str.substr(1));

        if (it == _map.end()) {

          throw FormatError("Item not found");

        }

        return _graph.direct(it->second, str[0] == '+');

      }

    };

    inline bool isWhiteSpace(char c) {

      return c == ' ' || c == '\t' || c == '\v' ||

        c == '\n' || c == '\r' || c == '\f';

    }

    inline bool isOct(char c) {

      return '0' <= c && c <='7';

    }

    inline int valueOct(char c) {

      LEMON_ASSERT(isOct(c), "The character is not octal.");

      return c - '0';

    }

    inline bool isHex(char c) {

      return ('0' <= c && c <= '9') ||

        ('a' <= c && c <= 'z') ||

        ('A' <= c && c <= 'Z');

    }

    inline int valueHex(char c) {

      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");

      if ('0' <= c && c <= '9') return c - '0';

      if ('a' <= c && c <= 'z') return c - 'a' + 10;

      return c - 'A' + 10;

    }

    inline bool isIdentifierFirstChar(char c) {

      return ('a' <= c && c <= 'z') ||

        ('A' <= c && c <= 'Z') || c == '_';

    }

    inline bool isIdentifierChar(char c) {

      return isIdentifierFirstChar(c) ||

        ('0' <= c && c <= '9');

    }

    inline char readEscape(std::istream& is) {

      char c;

      if (!is.get(c))

        throw FormatError("Escape format error");

      switch (c) {

      case '\\':

        return '\\';

      case '\"':

        return '\"';

      case '\'':

        return '\'';

      case '\?':

        return '\?';

      case 'a':

        return '\a';

      case 'b':

        return '\b';

      case 'f':

        return '\f';

      case 'n':

        return '\n';

      case 'r':

        return '\r';

      case 't':

        return '\t';

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

    }

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

    }

    /// @}

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

    DigraphReader& useNodes(const Map& map) {

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

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

      _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

    /// \c std::string.

    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;

    }

    /// \brief Use previously constructed arc set

    ///

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

    /// label map.

    template <typename Map>

    DigraphReader& useArcs(const Map& map) {

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

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

      _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

    /// \c std::string.

    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

    /// map reading rule will be abandoned, and the nodes of the graph

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

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

    /// Therefore \c skipArcs() function should also be used, or

    /// \c useNodes() should be used to specify the label of the nodes.

    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

    /// map reading rule will be abandoned, and the arcs of the graph

    /// will not be constructed.

    DigraphReader& skipArcs() {

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

      _skip_arcs = true;

      return *this;

    }

    /// @}

  private:

    bool readLine() {

      std::string str;

      while(++line_num, std::getline(*_is, str)) {

        line.clear(); line.str(str);

        char c;

        if (line >> std::ws >> c && c != '#') {

          line.putback(c);

          return true;

        }

      }

      return false;

    }

    bool readSuccess() {

      return static_cast<bool>(*_is);

    }

    void skipSection() {

      char c;

      while (readSuccess() && line >> c && c != '@') {

        readLine();

      }

      if (readSuccess()) {

        line.putback(c);

      }

    }

    void readNodes() {

      std::vector<int> map_index(_node_maps.size());

      int map_num, label_index;

      char c;

      if (!readLine() || !(line >> c) || c == '@') {

        if (readSuccess() && line) line.putback(c);

        if (!_node_maps.empty())

          throw FormatError("Cannot find map names");

        return;

      }

      line.putback(c);

      {

        std::map<std::string, int> maps;

        std::string map;

        int index = 0;

        while (_reader_bits::readToken(line, map)) {

          if (maps.find(map) != maps.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of node map: " << map;

            throw FormatError(msg.str());

          }

          maps.insert(std::make_pair(map, index));

          ++index;

        }

        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {

          std::map<std::string, int>::iterator jt =

            maps.find(_node_maps[i].first);

          if (jt == maps.end()) {

            std::ostringstream msg;

            msg << "Map not found: " << _node_maps[i].first;

            throw FormatError(msg.str());

          }

          map_index[i] = jt->second;

        }

        {

          std::map<std::string, int>::iterator jt = maps.find("label");

          if (jt != maps.end()) {

            label_index = jt->second;

          } else {

            label_index = -1;

          }

        }

        map_num = maps.size();

      }

      while (readLine() && line >> c && c != '@') {

        line.putback(c);

        std::vector<std::string> tokens(map_num);

        for (int i = 0; i < map_num; ++i) {

          if (!_reader_bits::readToken(line, tokens[i])) {

            std::ostringstream msg;

            msg << "Column not found (" << i + 1 << ")";

            throw FormatError(msg.str());

          }

        }

        if (line >> std::ws >> c)

          throw FormatError("Extra character at the end of line");

        Node n;

        if (!_use_nodes) {

          n = _digraph.addNode();

          if (label_index != -1)

            _node_index.insert(std::make_pair(tokens[label_index], n));

        } else {

          if (label_index == -1)

            throw FormatError("Label map not found");

          typename std::map<std::string, Node>::iterator it =

            _node_index.find(tokens[label_index]);

          if (it == _node_index.end()) {

            std::ostringstream msg;

            msg << "Node with label not found: " << tokens[label_index];

            throw FormatError(msg.str());

          }

          n = it->second;

        }

        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {

          _node_maps[i].second->set(n, tokens[map_index[i]]);

        }

      }

      if (readSuccess()) {

        line.putback(c);

      }

    }

    void readArcs() {

      std::vector<int> map_index(_arc_maps.size());

      int map_num, label_index;

      char c;

      if (!readLine() || !(line >> c) || c == '@') {

        if (readSuccess() && line) line.putback(c);

        if (!_arc_maps.empty())

          throw FormatError("Cannot find map names");

        return;

      }

      line.putback(c);

      {

        std::map<std::string, int> maps;

        std::string map;

        int index = 0;

        while (_reader_bits::readToken(line, map)) {

          if (maps.find(map) != maps.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of arc map: " << map;

            throw FormatError(msg.str());

          }

          maps.insert(std::make_pair(map, index));

          ++index;

        }

        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {

          std::map<std::string, int>::iterator jt =

            maps.find(_arc_maps[i].first);

          if (jt == maps.end()) {

            std::ostringstream msg;

            msg << "Map not found: " << _arc_maps[i].first;

            throw FormatError(msg.str());

          }

          map_index[i] = jt->second;

        }

        {

          std::map<std::string, int>::iterator jt = maps.find("label");

          if (jt != maps.end()) {

            label_index = jt->second;

          } else {

            label_index = -1;

          }

        }

        map_num = maps.size();

      }

      while (readLine() && line >> c && c != '@') {

        line.putback(c);

        std::string source_token;

        std::string target_token;

        if (!_reader_bits::readToken(line, source_token))

          throw FormatError("Source not found");

        if (!_reader_bits::readToken(line, target_token))

          throw FormatError("Target not found");

        std::vector<std::string> tokens(map_num);

        for (int i = 0; i < map_num; ++i) {

          if (!_reader_bits::readToken(line, tokens[i])) {

            std::ostringstream msg;

            msg << "Column not found (" << i + 1 << ")";

            throw FormatError(msg.str());

          }

        }

        if (line >> std::ws >> c)

          throw FormatError("Extra character at the end of line");

        Arc a;

        if (!_use_arcs) {

          typename NodeIndex::iterator it;

          it = _node_index.find(source_token);

          if (it == _node_index.end()) {

            std::ostringstream msg;

            msg << "Item not found: " << source_token;

            throw FormatError(msg.str());

          }

          Node source = it->second;

          it = _node_index.find(target_token);

          if (it == _node_index.end()) {

            std::ostringstream msg;

            msg << "Item not found: " << target_token;

            throw FormatError(msg.str());

          }

          Node target = it->second;

          a = _digraph.addArc(source, target);

          if (label_index != -1)

            _arc_index.insert(std::make_pair(tokens[label_index], a));

        } else {

          if (label_index == -1)

            throw FormatError("Label map not found");

          typename std::map<std::string, Arc>::iterator it =

            _arc_index.find(tokens[label_index]);

          if (it == _arc_index.end()) {

            std::ostringstream msg;

            msg << "Arc with label not found: " << tokens[label_index];

            throw FormatError(msg.str());

          }

          a = it->second;

        }

        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {

          _arc_maps[i].second->set(a, tokens[map_index[i]]);

        }

      }

      if (readSuccess()) {

        line.putback(c);

      }

    }

    void readAttributes() {

      std::set<std::string> read_attr;

      char c;

      while (readLine() && line >> c && c != '@') {

        line.putback(c);

        std::string attr, token;

        if (!_reader_bits::readToken(line, attr))

          throw FormatError("Attribute name not found");

        if (!_reader_bits::readToken(line, token))

          throw FormatError("Attribute value not found");

        if (line >> c)

          throw FormatError("Extra character at the end of line");

        {

          std::set<std::string>::iterator it = read_attr.find(attr);

          if (it != read_attr.end()) {

            std::ostringstream msg;

            msg << "Multiple occurence of attribute: " << attr;

            throw FormatError(msg.str());

          }

          read_attr.insert(attr);

        }

        {

          typename Attributes::iterator it = _attributes.lower_bound(attr);

          while (it != _attributes.end() && it->first == attr) {

            it->second->set(token);

            ++it;

          }

        }

      }

      if (readSuccess()) {

        line.putback(c);

      }

      for (typename Attributes::iterator it = _attributes.begin();

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

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

          std::ostringstream msg;

          msg << "Attribute not found: " << it->first;

          throw FormatError(msg.str());

        }

      }

    }

  public:

    /// \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");

      bool nodes_done = _skip_nodes;

      bool arcs_done = _skip_arcs;

      bool attributes_done = false;

      line_num = 0;

      readLine();

      skipSection();

      while (readSuccess()) {

        try {

          char c;

          std::string section, caption;

          line >> c;

          _reader_bits::readToken(line, section);

          _reader_bits::readToken(line, caption);

          if (line >> c)

            throw FormatError("Extra character at the end of line");

          if (section == "nodes" && !nodes_done) {

            if (_nodes_caption.empty() || _nodes_caption == caption) {

              readNodes();

              nodes_done = true;

            }

          } else if ((section == "arcs" || section == "edges") &&

                     !arcs_done) {

            if (_arcs_caption.empty() || _arcs_caption == caption) {

              readArcs();

              arcs_done = true;

            }

          } else if (section == "attributes" && !attributes_done) {

            if (_attributes_caption.empty() || _attributes_caption == caption) {

              readAttributes();

              attributes_done = true;

            }

          } else {

            readLine();

            skipSection();

          }

        } catch (FormatError& error) {

          error.line(line_num);

          error.file(_filename);

          throw;

        }

      }

      if (!nodes_done) {

        throw FormatError("Section @nodes not found");

      }

      if (!arcs_done) {

        throw FormatError("Section @arcs not found");

      }

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

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

      }

    }

    /// @}

  };

  /// \ingroup lemon_io

  ///

  /// \brief Return a \ref DigraphReader class

  ///

  /// This function just returns a \ref DigraphReader class.

  ///

  /// With this function a digraph can be read from an

  /// \ref lgf-format "LGF" file or input stream with several maps and

  /// attributes. For example, there is network flow problem on a

  /// digraph, i.e. a digraph with a \e capacity map on the arcs and

  /// \e source and \e target nodes. This digraph can be read with the

  /// following code:

  ///

  ///\code

  ///ListDigraph digraph;

  ///ListDigraph::ArcMap<int> cm(digraph);

  ///ListDigraph::Node src, trg;

  ///digraphReader(digraph, std::cin).

  ///  arcMap("capacity", cap).

  ///  node("source", src).

  ///  node("target", trg).

  ///  run();

  ///\endcode

  ///

  /// For a complete documentation, please see the \ref DigraphReader

  /// class documentation.

  /// \warning Don't forget to put the \ref DigraphReader::run() "run()"

  /// to the end of the parameter list.

  /// \relates DigraphReader

  /// \sa digraphReader(TDGR& digraph, const std::string& fn)

  /// \sa digraphReader(TDGR& digraph, const char* fn)

  template <typename TDGR>

    ///

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

    ///

    /// 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 previously constructed node set, and specify the node

    /// label map.

    template <typename Map>

    GraphReader& useNodes(const Map& map) {

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

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

      _use_nodes = true;