/* -*- C++ -*- * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2004 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 gio ///\file ///\brief Graph reader. #include #include #include #include #include #include /// \todo fix exceptions namespace lemon { // Exceptions class IOException { public: virtual string what() const = 0; }; class DataFormatException : public IOException { std::string message; public: DataFormatException(const std::string& _message) : message(_message) {} std::string what() const { return "DataFormatException: " + message; } }; template class StreamException : public _Exception { public: typedef _Exception Exception; StreamException(int _line, Exception _exception) : line_num(_line), Exception(_exception) {} virtual int line() const { return line_num; } virtual std::string what() const { ostringstream os; os << Exception::what() << " in line " << line(); return os.str(); } private: int line_num; }; // Readers and ReaderTraits struct DefaultReaderTraits { template struct Reader { typedef _Value Value; void read(std::istream& is, Value& value) { if (!(is >> value)) throw DataFormatException("Default Reader format exception"); } }; typedef Reader DefaultReader; }; class QuotedStringReader { public: typedef std::string Value; QuotedStringReader(bool _escaped = true) : escaped(_escaped) {} void read(std::istream& is, std::string& value) { char c; value.clear(); is >> ws; if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format"); while (is.get(c) && c != '\"') { if (escaped && c == '\\') { value += readEscape(is); } else { value += c; } } if (!is) throw DataFormatException("Quoted string format"); } 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 DataFormatException("Escape format exception"); 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 DataFormatException("Escape format exception"); 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; }; // Graph reader template class GraphReader { public: typedef _Graph Graph; typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef _ReaderTraits ReaderTraits; typedef typename ReaderTraits::DefaultReader DefaultReader; GraphReader(std::istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader()) : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_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; } } // Node map rules template GraphReader& readNodeMap(std::string name, Map& map) { return readNodeMap, Map>(name, map); } template GraphReader& readNodeMap(std::string name, Map& map, const Reader& reader = Reader()) { if (node_map_readers.find(name) != node_map_readers.end()) { throw Exception() << "Multiple read rule for node map: " << name; } node_map_readers.insert(make_pair(name, new MapReader(map, reader))); return *this; } template GraphReader& skipNodeMap(std::string name, const Reader& reader = Reader()) { if (node_map_readers.find(name) != node_map_readers.end()) { throw Exception() << "Multiple read rule for node map: " << name; } node_map_readers.insert(make_pair(name, new SkipReader(reader))); return *this; } // Edge map rules template GraphReader& readEdgeMap(std::string name, Map& map) { return readEdgeMap, Map>(name, map); } template GraphReader& readEdgeMap(std::string name, Map& map, const Reader& reader = Reader()) { if (edge_map_readers.find(name) != edge_map_readers.end()) { throw Exception() << "Multiple read rule for edge map: " << name; } edge_map_readers.insert(make_pair(name, new MapReader(map, reader))); return *this; } template GraphReader& skipEdgeMap(std::string name, const Reader& reader = Reader()) { if (edge_map_readers.find(name) != edge_map_readers.end()) { throw Exception() << "Multiple read rule for edge map: " << name; } edge_map_readers.insert(make_pair(name, new SkipReader(reader))); return *this; } // Node rules GraphReader& readNode(std::string name, Node& node) { if (node_readers.find(name) != node_readers.end()) { throw Exception() << "Multiple read rule for node"; } node_readers.insert(make_pair(name, &node)); } // Edge rules GraphReader& readEdge(std::string name, Edge& edge) { if (edge_readers.find(name) != edge_readers.end()) { throw Exception() << "Multiple read rule for edge"; } edge_readers.insert(make_pair(name, &edge)); } void read() { int line_num = 0; std::auto_ptr > nodeInverter; std::auto_ptr > 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 DataFormatException("Invalid control sequence: " + line); } } catch (DataFormatException e) { throw StreamException(line_num, e); } } private: template class InverterBase; std::string readNodeSet(int& line_num, auto_ptr > & nodeInverter) { std::vector* > index; { std::string line = readNotEmptyLine(is, line_num); std::string id; std::istringstream ls(line); while (ls >> id) { if (id[0] == '#') break; 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 (index.size() == 0) { throw DataFormatException("No node map found"); } nodeInverter = auto_ptr >(index[0]->getInverter()); std::string line; while (line = readNotEmptyLine(is, line_num), line[0] != '@') { Node node = graph.addNode(); std::istringstream ls(line); nodeInverter->read(ls, node); for (int i = 1; i < index.size(); ++i) { index[i]->read(ls, node); } } return line; } std::string readEdgeSet(int& line_num, auto_ptr > & edgeInverter, auto_ptr > & nodeInverter) { std::vector*> index; { std::string line = readNotEmptyLine(is, line_num); std::string id; std::istringstream ls(line); while (ls >> id) { if (id[0] == '#') break; 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 (index.size() == 0) { throw DataFormatException("No edge map found"); } edgeInverter = auto_ptr >(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); edgeInverter->read(ls, edge); for (int i = 1; i < index.size(); ++i) { index[i]->read(ls, edge); } } return line; } std::string readNodes(int& line_num, auto_ptr >& nodeInverter) { std::string line; 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, auto_ptr >& edgeInverter) { std::string line; 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_first_not_of(" \t"); if (vi != string::npos && line[vi] != '#') { return line.substr(vi); } } throw DataFormatException("End of stream"); } // Inverters store and give back the Item from the id, // and may put the ids into a map. template class InverterBase { public: typedef _Item Item; virtual void read(std::istream&, const Item&) = 0; virtual Item read(std::istream&) = 0; }; template class MapReaderInverter : public InverterBase<_Item> { public: typedef _Item Item; typedef _Reader Reader; typedef typename Reader::Value Value; typedef _Map Map; typedef std::map Inverse; Map& map; Reader reader; Inverse inverse; MapReaderInverter(Map& _map, const Reader& _reader) : map(_map), reader(_reader) {} 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(make_pair(value, item)); } else { throw DataFormatException("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 DataFormatException("Invalid ID"); } } }; template class SkipReaderInverter : public InverterBase<_Item> { public: typedef _Item Item; typedef _Reader Reader; typedef typename Reader::Value Value; typedef std::map Inverse; Reader reader; SkipReaderInverter(const Reader& _reader) : reader(_reader) {} 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(make_pair(value, item)); } else { throw DataFormatException("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 DataFormatException("Invalid ID"); } } private: Inverse inverse; }; // Readers template class ReaderBase { public: typedef _Item Item; virtual void read(std::istream& is, const Item& item) = 0; virtual InverterBase<_Item>* getInverter() = 0; }; template 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 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(map, reader); } }; template 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 void read(std::istream& is, const Item& item) { Value value; reader.read(is, value); } virtual InverterBase* getInverter() { return new SkipReaderInverter(reader); } }; typedef std::map*> NodeMapReaders; NodeMapReaders node_map_readers; typedef std::map*> EdgeMapReaders; EdgeMapReaders edge_map_readers; typedef std::map NodeReaders; NodeReaders node_readers; typedef std::map EdgeReaders; EdgeReaders edge_readers; std::istream& is; Graph& graph; SkipReader nodeSkipper; SkipReader edgeSkipper; }; }