RhodeCode

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

 *

 * 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 <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 _Graph, bool _dir, typename _Map,

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

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

    public:

      typedef _Map Map;

      typedef _Converter Converter;

      typedef _Graph Graph;

      typedef typename Graph::Edge Item;

      static const bool dir = _dir;

    private:

      const Graph& _graph;

      Map& _map;

      Converter _converter;

    public:

      GraphArcMapStorage(const Graph& 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 Graph>

    struct GraphArcLookUpConverter {

      const Graph& _graph;

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

      GraphArcLookUpConverter(const Graph& graph,

                              const std::map<std::string,

                                             typename Graph::Edge>& map)

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

      typename Graph::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 Graph::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] == '+');

      }

    };

      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) {

        _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

    /// \c std::string.

    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;

    }

    /// \brief Skip 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 edge set

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

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

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

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

    GraphReader& skipNodes() {

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

      _skip_nodes = true;

      return *this;

    }

    /// \brief Skip the reading of edge section

    ///

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

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

    /// will not be constructed.

    GraphReader& skipEdges() {

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

      _skip_edges = 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 = _graph.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 readEdges() {

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

      int map_num, label_index;

      char c;

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

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

        if (!_edge_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 edge map: " << map;

            throw FormatError(msg.str());

          }

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

          ++index;

        }

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

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

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

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

            std::ostringstream msg;

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

            throw FormatError(msg.str());

          }

          map_index[i] = jt->second;

        }

        {

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