deba@1137: /* -*- C++ -*- deba@1137: * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library deba@1137: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1137: * (Egervary Combinatorial Optimization Research Group, EGRES). deba@1137: * deba@1137: * Permission to use, modify and distribute this software is granted deba@1137: * provided that this copyright notice appears in all copies. For deba@1137: * precise terms see the accompanying LICENSE file. deba@1137: * deba@1137: * This software is provided "AS IS" with no warranty of any kind, deba@1137: * express or implied, and with no claim as to its suitability for any deba@1137: * purpose. deba@1137: * deba@1137: */ deba@1137: deba@1137: ///\ingroup gio deba@1137: ///\file deba@1137: ///\brief Graph reader. deba@1137: deba@1137: #include deba@1137: #include deba@1137: deba@1137: #include deba@1137: #include deba@1137: deba@1137: #include deba@1137: deba@1137: #include deba@1137: deba@1137: /// \todo fix exceptions deba@1137: deba@1137: deba@1137: namespace lemon { deba@1137: deba@1137: // Exceptions deba@1137: deba@1137: class IOException { deba@1137: public: deba@1137: virtual ~IOException() {} deba@1137: virtual string what() const = 0; deba@1137: }; deba@1137: deba@1137: class DataFormatException : public IOException { deba@1137: std::string message; deba@1137: public: deba@1137: DataFormatException(const std::string& _message) deba@1137: : message(_message) {} deba@1137: std::string what() const { deba@1137: return "DataFormatException: " + message; deba@1137: } deba@1137: }; deba@1137: deba@1137: template deba@1137: class StreamException : public _Exception { deba@1137: public: deba@1137: typedef _Exception Exception; deba@1137: StreamException(int _line, Exception _exception) deba@1137: : Exception(_exception), line_num(_line) {} deba@1137: virtual int line() const { deba@1137: return line_num; deba@1137: } deba@1137: deba@1137: virtual ~StreamException() {} deba@1137: deba@1137: virtual std::string what() const { deba@1137: ostringstream os; deba@1137: os << Exception::what() << " in line " << line(); deba@1137: return os.str(); deba@1137: } deba@1137: private: deba@1137: int line_num; deba@1137: }; deba@1137: deba@1137: deba@1137: /// \brief Standard ReaderTraits for the GraphReader class. deba@1137: /// deba@1137: /// Standard ReaderTraits for the GraphReader class. deba@1137: /// It defines standard reading method for all type of value. deba@1137: struct DefaultReaderTraits { deba@1137: deba@1137: /// \brief Template class for reading an value. deba@1137: /// deba@1137: /// Template class for reading an value. deba@1137: template deba@1137: struct Reader { deba@1137: /// The value type. deba@1137: typedef _Value Value; deba@1137: /// \brief Reads a value from the given stream. deba@1137: /// deba@1137: /// Reads a value from the given stream. deba@1137: void read(std::istream& is, Value& value) { deba@1137: if (!(is >> value)) deba@1137: throw DataFormatException("Default Reader format exception"); deba@1137: } deba@1137: }; deba@1137: deba@1137: /// The reader class for the not needed maps. deba@1137: typedef Reader DefaultReader; deba@1137: deba@1137: }; deba@1137: deba@1137: /// \brief Reader class for quoted strings. deba@1137: /// deba@1137: /// Reader class for quoted strings. It can process the escape deba@1137: /// sequences in the string. deba@1137: class QuotedStringReader { deba@1137: public: deba@1137: typedef std::string Value; deba@1137: deba@1137: /// \brief Constructor for the reader. deba@1137: /// deba@1137: /// Constructor for the reader. If the given parameter is true deba@1137: /// the reader processes the escape sequences. deba@1137: QuotedStringReader(bool _escaped = true) : escaped(_escaped) {} deba@1137: deba@1137: /// \brief Reads a quoted string from the given stream. deba@1137: /// deba@1137: /// Reads a quoted string from the given stream. deba@1137: void read(std::istream& is, std::string& value) { deba@1137: char c; deba@1137: value.clear(); deba@1137: is >> ws; deba@1137: if (!is.get(c) || c != '\"') deba@1137: throw DataFormatException("Quoted string format"); deba@1137: while (is.get(c) && c != '\"') { deba@1137: if (escaped && c == '\\') { deba@1137: value += readEscape(is); deba@1137: } else { deba@1137: value += c; deba@1137: } deba@1137: } deba@1137: if (!is) throw DataFormatException("Quoted string format"); deba@1137: } deba@1137: deba@1137: private: deba@1137: deba@1137: static char readEscape(std::istream& is) { deba@1137: char c; deba@1137: switch (is.get(c), c) { deba@1137: case '\\': deba@1137: return '\\'; deba@1137: case '\"': deba@1137: return '\"'; deba@1137: case '\'': deba@1137: return '\''; deba@1137: case '\?': deba@1137: return '\?'; deba@1137: case 'a': deba@1137: return '\a'; deba@1137: case 'b': deba@1137: return '\b'; deba@1137: case 'f': deba@1137: return '\f'; deba@1137: case 'n': deba@1137: return '\n'; deba@1137: case 'r': deba@1137: return '\r'; deba@1137: case 't': deba@1137: return '\t'; deba@1137: case 'v': deba@1137: return '\v'; deba@1137: case 'x': deba@1137: { deba@1137: int code; deba@1137: if (!is.get(c) || !isHex(c)) deba@1137: throw DataFormatException("Escape format exception"); deba@1137: else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c); deba@1137: else code = code * 16 + valueHex(c); deba@1137: return code; deba@1137: } deba@1137: default: deba@1137: { deba@1137: int code; deba@1137: if (!isOct(c)) deba@1137: throw DataFormatException("Escape format exception"); deba@1137: else if (code = valueOct(c), !is.get(c) || !isOct(c)) deba@1137: is.putback(c); deba@1137: else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) deba@1137: is.putback(c); deba@1137: else code = code * 8 + valueOct(c); deba@1137: return code; deba@1137: } deba@1137: } deba@1137: } deba@1137: deba@1137: static bool isOct(char c) { deba@1137: return '0' <= c && c <='7'; deba@1137: } deba@1137: deba@1137: static int valueOct(char c) { deba@1137: return c - '0'; deba@1137: } deba@1137: deba@1137: static bool isHex(char c) { deba@1137: return ('0' <= c && c <= '9') || deba@1137: ('a' <= c && c <= 'z') || deba@1137: ('A' <= c && c <= 'Z'); deba@1137: } deba@1137: deba@1137: static int valueHex(char c) { deba@1137: if ('0' <= c && c <= '9') return c - '0'; deba@1137: if ('a' <= c && c <= 'z') return c - 'a' + 10; deba@1137: return c - 'A' + 10; deba@1137: } deba@1137: deba@1137: bool escaped; deba@1137: }; deba@1137: deba@1137: /// \brief The graph reader class. deba@1137: /// deba@1137: /// The reader class for the graph input. alpar@1138: /// \see \ref GraphWriter alpar@1138: /// \see \ref graph-io-page deba@1137: template deba@1137: class GraphReader { deba@1137: public: deba@1137: deba@1137: typedef _Graph Graph; deba@1137: typedef typename Graph::Node Node; deba@1137: typedef typename Graph::Edge Edge; deba@1137: deba@1137: typedef _ReaderTraits ReaderTraits; deba@1137: typedef typename ReaderTraits::DefaultReader DefaultReader; deba@1137: deba@1137: /// \brief Construct a new GraphReader. deba@1137: /// deba@1137: /// Construct a new GraphReader. It reads from the given map, deba@1137: /// it constructs the given map and it use the given reader as the deba@1137: /// default skipper. deba@1137: GraphReader(std::istream& _is, Graph& _graph, deba@1137: const DefaultReader& _reader = DefaultReader()) deba@1137: : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {} deba@1137: deba@1137: /// \brief Destruct the graph reader. deba@1137: /// deba@1137: /// Destruct the graph reader. deba@1137: ~GraphReader() { deba@1137: deba@1137: for (typename NodeMapReaders::iterator it = node_map_readers.begin(); deba@1137: it != node_map_readers.end(); ++it) { deba@1137: delete it->second; deba@1137: } deba@1137: deba@1137: for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); deba@1137: it != edge_map_readers.end(); ++it) { deba@1137: delete it->second; deba@1137: } deba@1137: deba@1137: } deba@1137: deba@1137: /// \brief Add a new node map reader command for the reader. deba@1137: /// deba@1137: /// Add a new node map reader command for the reader. deba@1137: template deba@1137: GraphReader& addNodeMap(std::string name, Map& map) { deba@1137: return addNodeMap, Map>(name, map); deba@1137: } deba@1137: deba@1137: /// \brief Add a new node map reader command for the reader. deba@1137: /// deba@1137: /// Add a new node map reader command for the reader. deba@1137: template deba@1137: GraphReader& addNodeMap(std::string name, Map& map, deba@1137: const Reader& reader = Reader()) { deba@1137: if (node_map_readers.find(name) != node_map_readers.end()) { deba@1137: throw Exception() << "Multiple read rule for node map: " << name; deba@1137: } deba@1137: node_map_readers.insert( deba@1137: make_pair(name, new MapReader(map, reader))); deba@1137: return *this; deba@1137: } deba@1137: deba@1137: /// \brief Add a new node map skipper command for the reader. deba@1137: /// deba@1137: /// Add a new node map skipper command for the reader. deba@1137: template deba@1137: GraphReader& skipNodeMap(std::string name, deba@1137: const Reader& reader = Reader()) { deba@1137: if (node_map_readers.find(name) != node_map_readers.end()) { deba@1137: throw Exception() << "Multiple read rule for node map: " << name; deba@1137: } deba@1137: node_map_readers.insert( deba@1137: make_pair(name, new SkipReader(reader))); deba@1137: return *this; deba@1137: } deba@1137: deba@1137: /// \brief Add a new edge map reader command for the reader. deba@1137: /// deba@1137: /// Add a new edge map reader command for the reader. deba@1137: template deba@1137: GraphReader& addEdgeMap(std::string name, Map& map) { deba@1137: return addEdgeMap, Map>(name, map); deba@1137: } deba@1137: deba@1137: deba@1137: /// \brief Add a new edge map reader command for the reader. deba@1137: /// deba@1137: /// Add a new edge map reader command for the reader. deba@1137: template deba@1137: GraphReader& addEdgeMap(std::string name, Map& map, deba@1137: const Reader& reader = Reader()) { deba@1137: if (edge_map_readers.find(name) != edge_map_readers.end()) { deba@1137: throw Exception() << "Multiple read rule for edge map: " << name; deba@1137: } deba@1137: edge_map_readers.insert( deba@1137: make_pair(name, new MapReader(map, reader))); deba@1137: return *this; deba@1137: } deba@1137: deba@1137: /// \brief Add a new edge map skipper command for the reader. deba@1137: /// deba@1137: /// Add a new edge map skipper command for the reader. deba@1137: template deba@1137: GraphReader& skipEdgeMap(std::string name, deba@1137: const Reader& reader = Reader()) { deba@1137: if (edge_map_readers.find(name) != edge_map_readers.end()) { deba@1137: throw Exception() << "Multiple read rule for edge map: " << name; deba@1137: } deba@1137: edge_map_readers.insert( deba@1137: make_pair(name, new SkipReader(reader))); deba@1137: return *this; deba@1137: } deba@1137: deba@1137: /// \brief Add a new labeled node reader for the reader. deba@1137: /// deba@1137: /// Add a new labeled node reader for the reader. deba@1137: GraphReader& addNode(std::string name, Node& node) { deba@1137: if (node_readers.find(name) != node_readers.end()) { deba@1137: throw Exception() << "Multiple read rule for node"; deba@1137: } deba@1137: node_readers.insert(make_pair(name, &node)); deba@1137: return *this; deba@1137: } deba@1137: deba@1137: /// \brief Add a new labeled edge reader for the reader. deba@1137: /// deba@1137: /// Add a new labeled edge reader for the reader. deba@1137: GraphReader& addEdge(std::string name, Edge& edge) { deba@1137: if (edge_readers.find(name) != edge_readers.end()) { deba@1137: throw Exception() << "Multiple read rule for edge"; deba@1137: } deba@1137: edge_readers.insert(make_pair(name, &edge)); deba@1137: return *this; deba@1137: } deba@1137: deba@1137: /// \brief Executes the reader commands. deba@1137: /// deba@1137: /// Executes the reader commands. deba@1137: void run() { deba@1137: int line_num = 0; deba@1137: std::auto_ptr > nodeInverter; deba@1137: std::auto_ptr > edgeInverter; deba@1137: try { deba@1137: std::string line = readNotEmptyLine(is, line_num); deba@1137: if (line.find("@nodeset") == 0) { deba@1137: line = readNodeSet(line_num, nodeInverter); deba@1137: } deba@1137: if (line.find("@edgeset") == 0) { deba@1137: line = readEdgeSet(line_num, edgeInverter, nodeInverter); deba@1137: } deba@1137: if (line.find("@nodes") == 0) { deba@1137: line = readNodes(line_num, nodeInverter); deba@1137: } deba@1137: if (line.find("@edges") == 0) { deba@1137: line = readEdges(line_num, edgeInverter); deba@1137: } deba@1137: if (line.find("@end") != 0) { deba@1137: throw DataFormatException("Invalid control sequence: " + line); deba@1137: } deba@1137: } catch (DataFormatException e) { deba@1137: throw StreamException(line_num, e); deba@1137: } deba@1137: } deba@1137: deba@1137: private: deba@1137: deba@1137: template class InverterBase; deba@1137: deba@1137: std::string readNodeSet(int& line_num, deba@1137: auto_ptr > & nodeInverter) { deba@1137: std::vector* > index; deba@1137: { deba@1137: std::string line = readNotEmptyLine(is, line_num); deba@1137: std::string id; deba@1137: std::istringstream ls(line); deba@1137: while (ls >> id) { deba@1137: if (id[0] == '#') break; deba@1137: typename NodeMapReaders::iterator it = node_map_readers.find(id); deba@1137: if (it != node_map_readers.end()) { deba@1137: index.push_back(it->second); deba@1137: node_map_readers.erase(it); deba@1137: } else { deba@1137: index.push_back(&nodeSkipper); deba@1137: } deba@1137: } deba@1137: } deba@1137: deba@1137: if (index.size() == 0) { deba@1137: throw DataFormatException("No node map found"); deba@1137: } deba@1137: deba@1137: nodeInverter = auto_ptr >(index[0]->getInverter()); deba@1137: std::string line; deba@1137: while (line = readNotEmptyLine(is, line_num), line[0] != '@') { deba@1137: Node node = graph.addNode(); deba@1137: std::istringstream ls(line); deba@1137: nodeInverter->read(ls, node); deba@1137: for (int i = 1; i < (int)index.size(); ++i) { deba@1137: index[i]->read(ls, node); deba@1137: } deba@1137: } deba@1137: return line; deba@1137: } deba@1137: deba@1137: std::string readEdgeSet(int& line_num, deba@1137: auto_ptr > & edgeInverter, deba@1137: auto_ptr > & nodeInverter) { deba@1137: std::vector*> index; deba@1137: { deba@1137: std::string line = readNotEmptyLine(is, line_num); deba@1137: std::string id; deba@1137: std::istringstream ls(line); deba@1137: while (ls >> id) { deba@1137: if (id[0] == '#') break; deba@1137: typename EdgeMapReaders::iterator it = edge_map_readers.find(id); deba@1137: if (it != edge_map_readers.end()) { deba@1137: index.push_back(it->second); deba@1137: edge_map_readers.erase(it); deba@1137: } else { deba@1137: index.push_back(&edgeSkipper); deba@1137: } deba@1137: } deba@1137: } deba@1137: deba@1137: if (index.size() == 0) { deba@1137: throw DataFormatException("No edge map found"); deba@1137: } deba@1137: deba@1137: edgeInverter = auto_ptr >(index[0]->getInverter()); deba@1137: std::string line; deba@1137: while (line = readNotEmptyLine(is, line_num), line[0] != '@') { deba@1137: std::istringstream ls(line); deba@1137: Node source = nodeInverter->read(ls); deba@1137: Node target = nodeInverter->read(ls); deba@1137: Edge edge = graph.addEdge(source, target); deba@1137: edgeInverter->read(ls, edge); deba@1137: for (int i = 1; i < (int)index.size(); ++i) { deba@1137: index[i]->read(ls, edge); deba@1137: } deba@1137: } deba@1137: return line; deba@1137: } deba@1137: deba@1137: std::string readNodes(int& line_num, deba@1137: auto_ptr >& nodeInverter) { deba@1137: std::string line; deba@1137: while (line = readNotEmptyLine(is, line_num), line[0] != '@') { deba@1137: std::istringstream ls(line); deba@1137: std::string name; deba@1137: ls >> name; deba@1137: typename NodeReaders::iterator it = node_readers.find(name); deba@1137: if (it != node_readers.end()) { deba@1137: *(it -> second) = nodeInverter->read(ls); deba@1137: } deba@1137: } deba@1137: return line; deba@1137: } deba@1137: deba@1137: std::string readEdges(int& line_num, deba@1137: auto_ptr >& edgeInverter) { deba@1137: std::string line; deba@1137: while (line = readNotEmptyLine(is, line_num), line[0] != '@') { deba@1137: std::istringstream ls(line); deba@1137: std::string name; deba@1137: ls >> name; deba@1137: typename EdgeReaders::iterator it = edge_readers.find(name); deba@1137: if (it != edge_readers.end()) { deba@1137: *(it -> second) = edgeInverter->read(ls); deba@1137: } deba@1137: } deba@1137: return line; deba@1137: } deba@1137: deba@1137: std::string readNotEmptyLine(std::istream& is, int& line_num) { deba@1137: std::string line; deba@1137: while (++line_num, getline(is, line)) { deba@1137: int vi = line.find_first_not_of(" \t"); deba@1137: if (vi != (int)string::npos && line[vi] != '#') { deba@1137: return line.substr(vi); deba@1137: } deba@1137: } deba@1137: throw DataFormatException("End of stream"); deba@1137: } deba@1137: deba@1137: // Inverters store and give back the Item from the id, deba@1137: // and may put the ids into a map. deba@1137: deba@1137: template deba@1137: class InverterBase { deba@1137: public: deba@1137: typedef _Item Item; deba@1137: virtual void read(std::istream&, const Item&) = 0; deba@1137: virtual Item read(std::istream&) = 0; deba@1137: }; deba@1137: deba@1137: template deba@1137: class MapReaderInverter : public InverterBase<_Item> { deba@1137: public: deba@1137: typedef _Item Item; deba@1137: typedef _Reader Reader; deba@1137: typedef typename Reader::Value Value; deba@1137: typedef _Map Map; deba@1137: typedef std::map Inverse; deba@1137: deba@1137: Map& map; deba@1137: Reader reader; deba@1137: Inverse inverse; deba@1137: deba@1137: MapReaderInverter(Map& _map, const Reader& _reader) deba@1137: : map(_map), reader(_reader) {} deba@1137: deba@1137: virtual ~MapReaderInverter() {} deba@1137: deba@1137: virtual void read(std::istream& is, const Item& item) { deba@1137: Value value; deba@1137: reader.read(is, value); deba@1137: map.set(item, value); deba@1137: typename Inverse::iterator it = inverse.find(value); deba@1137: if (it == inverse.end()) { deba@1137: inverse.insert(make_pair(value, item)); deba@1137: } else { deba@1137: throw DataFormatException("Multiple ID occurence"); deba@1137: } deba@1137: } deba@1137: deba@1137: virtual Item read(std::istream& is) { deba@1137: Value value; deba@1137: reader.read(is, value); deba@1137: typename Inverse::const_iterator it = inverse.find(value); deba@1137: if (it != inverse.end()) { deba@1137: return it->second; deba@1137: } else { deba@1137: throw DataFormatException("Invalid ID"); deba@1137: } deba@1137: } deba@1137: }; deba@1137: deba@1137: template deba@1137: class SkipReaderInverter : public InverterBase<_Item> { deba@1137: public: deba@1137: typedef _Item Item; deba@1137: typedef _Reader Reader; deba@1137: typedef typename Reader::Value Value; deba@1137: typedef std::map Inverse; deba@1137: deba@1137: Reader reader; deba@1137: deba@1137: SkipReaderInverter(const Reader& _reader) deba@1137: : reader(_reader) {} deba@1137: deba@1137: virtual ~SkipReaderInverter() {} deba@1137: deba@1137: virtual void read(std::istream& is, const Item& item) { deba@1137: Value value; deba@1137: reader.read(is, value); deba@1137: typename Inverse::iterator it = inverse.find(value); deba@1137: if (it == inverse.end()) { deba@1137: inverse.insert(make_pair(value, item)); deba@1137: } else { deba@1137: throw DataFormatException("Multiple ID occurence"); deba@1137: } deba@1137: } deba@1137: deba@1137: virtual Item read(std::istream& is) { deba@1137: Value value; deba@1137: reader.read(is, value); deba@1137: typename Inverse::const_iterator it = inverse.find(value); deba@1137: if (it != inverse.end()) { deba@1137: return it->second; deba@1137: } else { deba@1137: throw DataFormatException("Invalid ID"); deba@1137: } deba@1137: } deba@1137: private: deba@1137: Inverse inverse; deba@1137: }; deba@1137: deba@1137: // Readers deba@1137: deba@1137: template deba@1137: class ReaderBase { deba@1137: public: deba@1137: typedef _Item Item; deba@1137: deba@1137: // virtual ~ReaderBase() {} deba@1137: deba@1137: virtual void read(std::istream& is, const Item& item) = 0; deba@1137: virtual InverterBase<_Item>* getInverter() = 0; deba@1137: }; deba@1137: deba@1137: template deba@1137: class MapReader : public ReaderBase<_Item> { deba@1137: public: deba@1137: typedef _Map Map; deba@1137: typedef _Reader Reader; deba@1137: typedef typename Reader::Value Value; deba@1137: typedef _Item Item; deba@1137: deba@1137: Map& map; deba@1137: Reader reader; deba@1137: deba@1137: MapReader(Map& _map, const Reader& _reader) deba@1137: : map(_map), reader(_reader) {} deba@1137: deba@1137: virtual ~MapReader() {} deba@1137: deba@1137: virtual void read(std::istream& is, const Item& item) { deba@1137: Value value; deba@1137: reader.read(is, value); deba@1137: map.set(item, value); deba@1137: } deba@1137: deba@1137: virtual InverterBase<_Item>* getInverter() { deba@1137: return new MapReaderInverter(map, reader); deba@1137: } deba@1137: }; deba@1137: deba@1137: deba@1137: template deba@1137: class SkipReader : public ReaderBase<_Item> { deba@1137: public: deba@1137: typedef _Reader Reader; deba@1137: typedef typename Reader::Value Value; deba@1137: typedef _Item Item; deba@1137: deba@1137: Reader reader; deba@1137: SkipReader(const Reader& _reader) : reader(_reader) {} deba@1137: deba@1137: virtual ~SkipReader() {} deba@1137: deba@1137: virtual void read(std::istream& is, const Item& item) { deba@1137: Value value; deba@1137: reader.read(is, value); deba@1137: } deba@1137: deba@1137: virtual InverterBase* getInverter() { deba@1137: return new SkipReaderInverter(reader); deba@1137: } deba@1137: }; deba@1137: deba@1137: deba@1137: typedef std::map*> NodeMapReaders; deba@1137: NodeMapReaders node_map_readers; deba@1137: deba@1137: typedef std::map*> EdgeMapReaders; deba@1137: EdgeMapReaders edge_map_readers; deba@1137: deba@1137: typedef std::map NodeReaders; deba@1137: NodeReaders node_readers; deba@1137: deba@1137: typedef std::map EdgeReaders; deba@1137: EdgeReaders edge_readers; deba@1137: deba@1137: std::istream& is; deba@1137: Graph& graph; deba@1137: deba@1137: SkipReader nodeSkipper; deba@1137: SkipReader edgeSkipper; deba@1137: deba@1137: }; deba@1137: deba@1137: }