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';

      case 'v':

        return '\v';

      case 'x':

        {

          int code;

          if (!is.get(c) || !isHex(c))

            throw FormatError("Escape format error");

          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);

          else code = code * 16 + valueHex(c);

          return code;

        }

      default:

        {

          int code;

          if (!isOct(c))

            throw FormatError("Escape format error");

          else if (code = valueOct(c), !is.get(c) || !isOct(c))

            is.putback(c);

          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))

            is.putback(c);

          else code = code * 8 + valueOct(c);

          return code;

        }

      }

    }

    inline std::istream& readToken(std::istream& is, std::string& str) {

      std::ostringstream os;

      char c;

      is >> std::ws;

      if (!is.get(c))

        return is;

      if (c == '\"') {

        while (is.get(c) && c != '\"') {

          if (c == '\\')

            c = readEscape(is);

          os << c;

        }

        if (!is)

          throw FormatError("Quoted format error");

      } else {

        is.putback(c);

        while (is.get(c) && !isWhiteSpace(c)) {

          if (c == '\\')

            c = readEscape(is);

          os << c;

        }

        if (!is) {

          is.clear();

        } else {

          is.putback(c);

        }

      }

      str = os.str();

      return is;

    }

    class Section {

    public:

      virtual ~Section() {}

      virtual void process(std::istream& is, int& line_num) = 0;

    };

    template <typename Functor>

    class LineSection : public Section {

    private:

      Functor _functor;

    public:

      LineSection(const Functor& functor) : _functor(functor) {}

      virtual ~LineSection() {}

      virtual void process(std::istream& is, int& line_num) {

        char c;

        std::string line;

        while (is.get(c) && c != '@') {

          if (c == '\n') {

            ++line_num;

          } else if (c == '#') {

            getline(is, line);

            ++line_num;

          } else if (!isWhiteSpace(c)) {

            is.putback(c);

            getline(is, line);

            _functor(line);

            ++line_num;

          }

        }

        if (is) is.putback(c);

        else if (is.eof()) is.clear();

      }

    };

    template <typename Functor>

    class StreamSection : public Section {

    private:

      Functor _functor;

    public:

      StreamSection(const Functor& functor) : _functor(functor) {}

      virtual ~StreamSection() {}

      virtual void process(std::istream& is, int& line_num) {

        _functor(is, line_num);

        char c;

        std::string line;

        while (is.get(c) && c != '@') {

          if (c == '\n') {

            ++line_num;

          } else if (!isWhiteSpace(c)) {

            getline(is, line);

            ++line_num;

          }

        }

        if (is) is.putback(c);

        else if (is.eof()) is.clear();

      }

    };

  }

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphReader& operator=(const DigraphReader&);

  public:

    /// \name Reading Rules

    /// @{

    /// \brief Node map reading rule

    ///

    /// Add a node map reading rule to the reader.

    template <typename Map>

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

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

      _reader_bits::MapStorageBase<Node>* storage =

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

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

      return *this;

    }

    /// \brief Node map reading rule

    ///

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

    /// reader.

    template <typename Map, typename Converter>

    DigraphReader& nodeMap(const std::string& caption, Map& map,

                           const Converter& converter = Converter()) {

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

      _reader_bits::MapStorageBase<Node>* storage =

        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);

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

      return *this;

    }

    /// \brief Arc map reading rule

    ///

    /// Add an arc map reading rule to the reader.

    template <typename Map>

    DigraphReader& arcMap(const std::string& caption, Map& map) {

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

      _reader_bits::MapStorageBase<Arc>* storage =

        new _reader_bits::MapStorage<Arc, Map>(map);

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

      return *this;

    }

    /// \brief Arc map reading rule

    ///

    /// Add an arc map reading rule with specialized converter to the

    /// reader.

    template <typename Map, typename Converter>

    DigraphReader& arcMap(const std::string& caption, Map& map,

                          const Converter& converter = Converter()) {

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

      _reader_bits::MapStorageBase<Arc>* storage =

        new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);

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

      return *this;

    }

    /// \brief Attribute reading rule

    ///

    /// Add an attribute reading rule to the reader.

    template <typename Value>

    DigraphReader& attribute(const std::string& caption, Value& value) {

      _reader_bits::ValueStorageBase* storage =

        new _reader_bits::ValueStorage<Value>(value);

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

      return *this;

    }

    /// \brief Attribute reading rule

    ///

    /// Add an attribute reading rule with specialized converter to the

    /// reader.

    template <typename Value, typename Converter>

    DigraphReader& attribute(const std::string& caption, Value& value,

                             const Converter& converter = Converter()) {

      _reader_bits::ValueStorageBase* storage =

        new _reader_bits::ValueStorage<Value, Converter>(value, converter);

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

      return *this;

    }

    /// \brief Node reading rule

    ///

    /// Add a node reading rule to reader.

    DigraphReader& node(const std::string& caption, Node& node) {

      typedef _reader_bits::MapLookUpConverter<Node> Converter;

      Converter converter(_node_index);

      _reader_bits::ValueStorageBase* storage =

        new _reader_bits::ValueStorage<Node, Converter>(node, converter);

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

      return *this;

    }

    /// \brief Arc reading rule

    ///

    /// Add an arc reading rule to reader.

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

      typedef _reader_bits::MapLookUpConverter<Arc> Converter;

      Converter converter(_arc_index);

      _reader_bits::ValueStorageBase* storage =

        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

    ///

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

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

      _nodes_caption = caption;

      return *this;

    }

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

      }