source: lemon-0.x/src/lemon/graph_reader.h @ 1343:a81f9cfc9775

/* -*- C++ -*-
 * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Combinatorial Optimization Research Group, 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 io_group
///\file
///\brief Lemon Graph Format reader.

#ifndef LEMON_GRAPH_READER_H
#define LEMON_GRAPH_READER_H

#include <iostream>
#include <sstream>

#include <map>
#include <vector>

#include <memory>

#include <lemon/error.h>


namespace lemon {

  /// \addtogroup io_group
  /// @{

  /// \brief Standard ReaderTraits for the GraphReader class.
  ///
  /// Standard ReaderTraits for the GraphReader class.
  /// It defines standard reading method for all type of value. 
  /// \author Balazs Dezso
  struct DefaultReaderTraits {

    /// \brief Template class for reading an value.
    ///
    /// Template class for reading an value.
    /// \author Balazs Dezso
    template <typename _Value>
    struct Reader {
      /// The value type.
      typedef _Value Value;
      /// \brief Reads a value from the given stream.
      ///
      /// Reads a value from the given stream.
      void read(std::istream& is, Value& value) {
        if (!(is >> value)) 
          throw DataFormatError("Default reader format exception");
      }
    };

    /// \brief Returns wheter this name is an ID map name.
    ///
    /// Returns wheter this name is an ID map name.
    static bool idMapName(const std::string& name) {
      return name == "id";
    }

    /// The reader class for the not needed maps.
    typedef Reader<std::string> DefaultReader;

  };

  /// \brief Reader class for quoted strings.
  ///
  /// Reader class for quoted strings. It can process the escape
  /// sequences in the string.
  /// \author Balazs Dezso
  class QuotedStringReader {
  public:
    typedef std::string Value;
    
    /// \brief Constructor for the reader.
    ///
    /// Constructor for the reader. If the given parameter is true
    /// the reader processes the escape sequences.
    QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
    
    /// \brief Reads a quoted string from the given stream.
    ///
    /// Reads a quoted string from the given stream.
    void read(std::istream& is, std::string& value) {
      char c;
      value.clear();
      is >> std::ws;
      if (!is.get(c) || c != '\"') 
        throw DataFormatError("Quoted string format error");
      while (is.get(c) && c != '\"') {
        if (escaped && c == '\\') {
          value += readEscape(is);
        } else {
          value += c;
        }
      }
      if (!is) throw DataFormatError("Quoted string format error");
    }

  private:
    
    static char readEscape(std::istream& is) {
      char c;
      switch (is.get(c), 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 DataFormatError("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 DataFormatError("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;
        }             
      } 
    }

    static bool isOct(char c) {
      return '0' <= c && c <='7'; 
    }
    
    static int valueOct(char c) {
      return c - '0';
    }

   static bool isHex(char c) {
      return ('0' <= c && c <= '9') || 
        ('a' <= c && c <= 'z') || 
        ('A' <= c && c <= 'Z'); 
    }
    
    static int valueHex(char c) {
      if ('0' <= c && c <= '9') return c - '0';
      if ('a' <= c && c <= 'z') return c - 'a' + 10;
      return c - 'A' + 10;
    }

    bool escaped;
  };

  /// \brief The graph reader class.
  ///
  ///
  /// The given file format may contain several maps and labeled nodes or 
  /// edges.
  ///
  /// If you read a graph you need not read all the maps and items just those
  /// that you need. The interface of the \c GraphReader is very similar to
  /// the GraphWriter but the reading method does not depend on the order the
  /// given commands.
  ///
  /// The reader object suppose that each not readed value does not contain 
  /// whitespaces, therefore it has some extra possibilities to control how
  /// it should skip the values when the string representation contains spaces.
  ///
  /// \code
  /// GraphReader<ListGraph> reader(std::cin, graph);
  /// \endcode
  ///
  /// The \c addNodeMap() function reads a map from the \c \@nodeset section.
  /// If there is a map that you do not want to read from the file and there is
  /// whitespace in the string represenation of the values then you should
  /// call the \c skipNodeMap() template member function with proper 
  /// parameters.
  ///
  /// \code
  /// reader.addNodeMap("x-coord", xCoordMap);
  /// reader.addNodeMap("y-coord", yCoordMap);
  ///
  /// reader.addNodeMap<QuotedStringReader>("label", labelMap);
  /// reader.skipNodeMap<QuotedStringReader>("description");
  ///
  /// reader.addNodeMap("color", colorMap);
  /// \endcode
  ///
  /// With the \c addEdgeMap() member function you can give an edge map
  /// reading command similar to the NodeMaps. 
  ///
  /// \code
  /// reader.addEdgeMap("weight", weightMap);
  /// reader.addEdgeMap("label", labelMap);
  /// \endcode
  ///
  /// With \c addNode() and \c addEdge() functions you can read labeled Nodes 
  /// and Edges.
  ///
  /// \code
  /// reader.addNode("source", sourceNode);
  /// reader.addNode("target", targetNode);
  ///
  /// reader.addEdge("observed", edge);
  /// \endcode
  ///
  /// After you give all read commands you must call the \c run() member
  /// function, which execute all the commands.
  ///
  /// \code
  /// reader.run();
  /// \endcode
  ///
  /// \see DefaultReaderTraits
  /// \see QuotedStringReader
  /// \see \ref GraphWriter
  /// \see \ref graph-io-page
  /// \author Balazs Dezso
  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits> 
  class GraphReader {
  public:
    
    typedef _Graph Graph;
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;

    typedef _ReaderTraits ReaderTraits;
    typedef typename ReaderTraits::DefaultReader DefaultReader;

    /// \brief Construct a new GraphReader.
    ///
    /// Construct a new GraphReader. It reads into the given graph
    /// and it use the given reader as the default skipper.
    GraphReader(std::istream& _is, Graph& _graph, 
                const DefaultReader& _reader = DefaultReader()) 
      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}

    /// \brief Destruct the graph reader.
    ///
    /// Destruct the graph reader.
    ~GraphReader() {
      for (typename NodeMapReaders::iterator it = node_map_readers.begin(); 
           it != node_map_readers.end(); ++it) {
        delete it->second;
      }

      for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); 
           it != edge_map_readers.end(); ++it) {
        delete it->second;
      }

    }

    /// \brief Add a new node map reader command for the reader.
    ///
    /// Add a new node map reader command for the reader.
    template <typename Map>
    GraphReader& addNodeMap(std::string name, Map& map) {
      return addNodeMap<typename ReaderTraits::template 
        Reader<typename Map::Value>, Map>(name, map);
    }

    /// \brief Add a new node map reader command for the reader.
    ///
    /// Add a new node map reader command for the reader.
    template <typename Reader, typename Map>
    GraphReader& addNodeMap(std::string name, Map& map, 
                             const Reader& reader = Reader()) {
      if (node_map_readers.find(name) != node_map_readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node map: " << name;
        throw IOParameterError(msg.message());
      }
      node_map_readers.insert(
        make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
      return *this;
    }

    /// \brief Add a new node map skipper command for the reader.
    ///
    /// Add a new node map skipper command for the reader.
    template <typename Reader>
    GraphReader& skipNodeMap(std::string name, 
                             const Reader& reader = Reader()) {
      if (node_map_readers.find(name) != node_map_readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node map: " << name;
        throw IOParameterError(msg.message());
      }
      node_map_readers.insert(
        make_pair(name, new SkipReader<Node, Reader>(reader)));
      return *this;
    }

    /// \brief Add a new edge map reader command for the reader.
    ///
    /// Add a new edge map reader command for the reader.
    template <typename Map>
    GraphReader& addEdgeMap(std::string name, Map& map) { 
      return addEdgeMap<typename ReaderTraits::template
        Reader<typename Map::Value>, Map>(name, map);
    }


    /// \brief Add a new edge map reader command for the reader.
    ///
    /// Add a new edge map reader command for the reader.
    template <typename Reader, typename Map>
    GraphReader& addEdgeMap(std::string name, Map& map,
                             const Reader& reader = Reader()) {
      if (edge_map_readers.find(name) != edge_map_readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for edge map: " << name;
        throw IOParameterError(msg.message());
      }
      edge_map_readers.insert(
        make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
      return *this;
    }

    /// \brief Add a new edge map skipper command for the reader.
    ///
    /// Add a new edge map skipper command for the reader.
    template <typename Reader>
    GraphReader& skipEdgeMap(std::string name,
                             const Reader& reader = Reader()) {
      if (edge_map_readers.find(name) != edge_map_readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for edge map: " << name;
        throw IOParameterError(msg.message());
      }
      edge_map_readers.insert(
        make_pair(name, new SkipReader<Edge, Reader>(reader)));
      return *this;
    }

    /// \brief Add a new labeled node reader for the reader.
    ///
    /// Add a new labeled node reader for the reader.
    GraphReader& addNode(std::string name, Node& node) {
      if (node_readers.find(name) != node_readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node: " << name;
        throw IOParameterError(msg.message());
      }
      node_readers.insert(make_pair(name, &node));
      return *this;
    }

    /// \brief Add a new labeled edge reader for the reader.
    ///
    /// Add a new labeled edge reader for the reader.
    GraphReader& addEdge(std::string name, Edge& edge) {
      if (edge_readers.find(name) != edge_readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for edge: " << name;
        throw IOParameterError(msg.message());
      }
      edge_readers.insert(make_pair(name, &edge));
      return *this;
    }

    /// \brief Executes the reader commands.
    ///
    /// Executes the reader commands.
    void run() {
      int line_num = 0;
      std::auto_ptr<InverterBase<Node> > nodeInverter;
      std::auto_ptr<InverterBase<Edge> > edgeInverter;
      try {
        std::string line = readNotEmptyLine(is, line_num);
        if (line.find("@nodeset") == 0) {
          line = readNodeSet(line_num, nodeInverter);
        } 
        if (line.find("@edgeset") == 0) {
          line = readEdgeSet(line_num, edgeInverter, nodeInverter);
        }
        if (line.find("@nodes") == 0) {
          line = readNodes(line_num, nodeInverter);
        }
        if (line.find("@edges") == 0) {
          line = readEdges(line_num, edgeInverter);
        }
        if (line.find("@end") != 0) {
          throw DataFormatError("Invalid control sequence error");
        }
      } catch (DataFormatError e) {
        e.line(line_num);
        throw e;
      }
    }

  private:

    template <typename Item> class InverterBase;

    std::string readNodeSet(int& line_num, 
                            std::auto_ptr<InverterBase<Node> >& nodeInverter) {
      std::vector<ReaderBase<Node>* > index;
      {
        std::string line = readNotEmptyLine(is, line_num);    
        std::string id;
        std::istringstream ls(line);    
        while (ls >> id) {
          typename NodeMapReaders::iterator it = node_map_readers.find(id);
          if (it != node_map_readers.end()) {
            index.push_back(it->second);
            node_map_readers.erase(it);
          } else {
            index.push_back(&nodeSkipper);
          }
          if (ReaderTraits::idMapName(id) && nodeInverter.get() == 0) {
            nodeInverter.reset(index.back()->getInverter());
            index.back() = nodeInverter.get();
          }
        }
      }

//       if (index.size() == 0) {
//      throw DataFormatError("Cannot find node id map");
//       }

//       nodeInverter = 
//      std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
      std::string line;
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
        Node node = graph.addNode();
        std::istringstream ls(line);
        for (int i = 0; i < (int)index.size(); ++i) {
          index[i]->read(ls, node);
        }
      }
      return line;
    }

    std::string readEdgeSet(int& line_num, 
                            std::auto_ptr<InverterBase<Edge> >& edgeInverter, 
                            std::auto_ptr<InverterBase<Node> >& nodeInverter) {
      std::vector<ReaderBase<Edge>*> index;
      {
        std::string line = readNotEmptyLine(is, line_num);    
        std::string id;
        std::istringstream ls(line);    
        while (ls >> id) {
          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
          if (it != edge_map_readers.end()) {
            index.push_back(it->second);
            edge_map_readers.erase(it);
          } else {
            index.push_back(&edgeSkipper);
          }
          if (ReaderTraits::idMapName(id) && edgeInverter.get() == 0) {
            edgeInverter.reset(index.back()->getInverter());
            index.back() = edgeInverter.get();
          }
        }
      }
      
      if (nodeInverter.get() == 0) {
        throw DataFormatError("Cannot find node id map");
      }
//       if (index.size() == 0) {
//      throw DataFormatError("Cannot find edge id map");
//       }

//       edgeInverter = 
//      std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
      std::string line;
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
        std::istringstream ls(line);
        Node source = nodeInverter->read(ls);
        Node target = nodeInverter->read(ls);
        Edge edge = graph.addEdge(source, target);
        for (int i = 0; i < (int)index.size(); ++i) {
          index[i]->read(ls, edge);
        }
      }      
      return line;
    }

    std::string readNodes(int& line_num, 
                          std::auto_ptr<InverterBase<Node> >& nodeInverter) {
      std::string line;
      if (nodeInverter.get() == 0) {
        throw DataFormatError("Cannot find node id map");
      }
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
        std::istringstream ls(line);
        std::string name;
        ls >> name;
        typename NodeReaders::iterator it = node_readers.find(name);
        if (it != node_readers.end()) {
          *(it -> second) = nodeInverter->read(ls);
        } 
      }        
      return line;
    }

    std::string readEdges(int& line_num, 
                          std::auto_ptr<InverterBase<Edge> >& edgeInverter) {
      std::string line;
      if (edgeInverter.get() == 0) {
        throw DataFormatError("Cannot find edge id map");
      }
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
        std::istringstream ls(line);
        std::string name;
        ls >> name;
        typename EdgeReaders::iterator it = edge_readers.find(name);
        if (it != edge_readers.end()) {
          *(it -> second) = edgeInverter->read(ls);
        } 
      }        
      return line;    
    }

    std::string readNotEmptyLine(std::istream& is, int& line_num) {
      std::string line;
      while (++line_num, getline(is, line)) {   
        int vi = line.find('#');
        if (vi != (int)::std::string::npos) {
          line = line.substr(0, vi);
        }
        vi = line.find_first_not_of(" \t");
        if (vi != (int)std::string::npos) { 
          return line.substr(vi);
        }
      }
      throw DataFormatError("End of stream error");
    }
    
    template <typename _Item>
    class ReaderBase;
    
    template <typename _Item>
    class InverterBase : public ReaderBase<_Item> {
    public:
      typedef _Item Item;
      virtual void read(std::istream&, const Item&) = 0;
      virtual Item read(std::istream&) = 0;

      virtual InverterBase<_Item>* getInverter() {
        return this;
      }
    };

    template <typename _Item, typename _Map, typename _Reader>
    class MapReaderInverter : public InverterBase<_Item> {
    public:
      typedef _Item Item;
      typedef _Reader Reader;
      typedef typename Reader::Value Value;
      typedef _Map Map;
      typedef std::map<Value, Item> Inverse;

      Map& map;
      Reader reader;
      Inverse inverse;

      MapReaderInverter(Map& _map, const Reader& _reader) 
        : map(_map), reader(_reader) {}

      virtual ~MapReaderInverter() {}

      virtual void read(std::istream& is, const Item& item) {
        Value value;
        reader.read(is, value);
        map.set(item, value);
        typename Inverse::iterator it = inverse.find(value);
        if (it == inverse.end()) {
          inverse.insert(std::make_pair(value, item));
        } else {
          throw DataFormatError("Multiple ID occurence");
        }
      }

      virtual Item read(std::istream& is) {
        Value value;
        reader.read(is, value); 
        typename Inverse::const_iterator it = inverse.find(value);
        if (it != inverse.end()) {
          return it->second;
        } else {
          throw DataFormatError("Invalid ID error");
        }
      }      
    };

    template <typename _Item, typename _Reader>
    class SkipReaderInverter : public InverterBase<_Item> {
    public:
      typedef _Item Item;
      typedef _Reader Reader;
      typedef typename Reader::Value Value;
      typedef std::map<Value, Item> Inverse;

      Reader reader;

      SkipReaderInverter(const Reader& _reader) 
        : reader(_reader) {}

      virtual ~SkipReaderInverter() {}

      virtual void read(std::istream& is, const Item& item) {
        Value value;
        reader.read(is, value);
        typename Inverse::iterator it = inverse.find(value);
        if (it == inverse.end()) {
          inverse.insert(std::make_pair(value, item));
        } else {
          throw DataFormatError("Multiple ID occurence error");
        }
      }

      virtual Item read(std::istream& is) {
        Value value;
        reader.read(is, value); 
        typename Inverse::const_iterator it = inverse.find(value);
        if (it != inverse.end()) {
          return it->second;
        } else {
          throw DataFormatError("Invalid ID error");
        }
      }      
    private:
      Inverse inverse;
    };

    // Readers

    template <typename _Item>    
    class ReaderBase {
    public:
      typedef _Item Item;

      //      virtual ~ReaderBase() {}

      virtual void read(std::istream& is, const Item& item) = 0;
      virtual InverterBase<_Item>* getInverter() = 0;
    };

    template <typename _Item, typename _Map, typename _Reader>
    class MapReader : public ReaderBase<_Item> {
    public:
      typedef _Map Map;
      typedef _Reader Reader;
      typedef typename Reader::Value Value;
      typedef _Item Item;
      
      Map& map;
      Reader reader;

      MapReader(Map& _map, const Reader& _reader) 
        : map(_map), reader(_reader) {}

      virtual ~MapReader() {}

      virtual void read(std::istream& is, const Item& item) {
        Value value;
        reader.read(is, value);
        map.set(item, value);
      }

      virtual InverterBase<_Item>* getInverter() {
        return new MapReaderInverter<Item, Map, Reader>(map, reader);
      }
    };


    template <typename _Item, typename _Reader>
    class SkipReader : public ReaderBase<_Item> {
    public:
      typedef _Reader Reader;
      typedef typename Reader::Value Value;
      typedef _Item Item;

      Reader reader;
      SkipReader(const Reader& _reader) : reader(_reader) {}

      virtual ~SkipReader() {}

      virtual void read(std::istream& is, const Item&) {
        Value value;
        reader.read(is, value);
      }      

      virtual InverterBase<Item>* getInverter() {
        return new SkipReaderInverter<Item, Reader>(reader);
      }
    };


    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
    NodeMapReaders node_map_readers;

    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
    EdgeMapReaders edge_map_readers;

    typedef std::map<std::string, Node*> NodeReaders;
    NodeReaders node_readers;

    typedef std::map<std::string, Edge*> EdgeReaders;
    EdgeReaders edge_readers;

    std::istream& is;
    Graph& graph;

    SkipReader<Node, DefaultReader> nodeSkipper;
    SkipReader<Edge, DefaultReader> edgeSkipper;

  };

  /// \brief Read a graph from the input.
  ///
  /// Read a graph from the input.
  /// \param is The input stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  /// \param s The source node.
  /// \param t The target node.
  /// \param cost The cost map.
  template<typename Graph, typename CapacityMap, typename CostMap>
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 
                  typename Graph::Node &s, typename Graph::Node &t, 
                  CostMap& cost) {
    GraphReader<Graph> reader(is, g);
    reader.addEdgeMap("capacity", capacity);
    reader.addEdgeMap("cost", cost);
    reader.addNode("source", s);
    reader.addNode("target", t);
    reader.run();
  }

  /// \brief Read a graph from the input.
  ///
  /// Read a graph from the input.
  /// \param is The input stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  /// \param s The source node.
  /// \param t The target node.
  template<typename Graph, typename CapacityMap>
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 
                  typename Graph::Node &s, typename Graph::Node &t) {
    GraphReader<Graph> reader(is, g);
    reader.addEdgeMap("capacity", capacity);
    reader.addNode("source", s);
    reader.addNode("target", t);
    reader.run();
  }

  /// \brief Read a graph from the input.
  ///
  /// Read a graph from the input.
  /// \param is The input stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  /// \param s The source node.
  template<typename Graph, typename CapacityMap>
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 
                  typename Graph::Node &s) {
    GraphReader<Graph> reader(is, g);
    reader.addEdgeMap("capacity", capacity);
    reader.addNode("source", s);
    reader.run();
  }

  /// \brief Read a graph from the input.
  ///
  /// Read a graph from the input.
  /// \param is The input stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  template<typename Graph, typename CapacityMap>
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
    GraphReader<Graph> reader(is, g);
    reader.addEdgeMap("capacity", capacity);
    reader.run();
  }

  /// \brief Read a graph from the input.
  ///
  /// Read a graph from the input.
  /// \param is The input stream.
  /// \param g The graph.
  template<typename Graph>
  void readGraph(std::istream& is, Graph &g) {
    GraphReader<Graph> reader(is, g);
    reader.run();
  }

  /// @}
}

#endif