# HG changeset patch
# User deba
# Date 1107775765 0
# Node ID 83a48cfd8553d8e557ba44b209212aa9fd5d6aba
# Parent  8d066154b66ad92a5fa3f001fc388e7987ae2ae4
IO moved to lemon.

diff -r 8d066154b66a -r 83a48cfd8553 src/lemon/Makefile.am
--- a/src/lemon/Makefile.am	Mon Feb 07 11:28:37 2005 +0000
+++ b/src/lemon/Makefile.am	Mon Feb 07 11:29:25 2005 +0000
@@ -35,7 +35,10 @@
 	extendable_graph_extender.h					\
 	clearable_graph_extender.h					\
 	erasable_graph_extender.h					\
-	undir_graph_extender.h
+	undir_graph_extender.h                                          \
+	graph_reader.h							\
+	graph_writer.h							\
+	map_utils.h
 
 noinst_HEADERS =							\
 	concept/graph.h							\
diff -r 8d066154b66a -r 83a48cfd8553 src/lemon/graph_reader.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/graph_reader.h	Mon Feb 07 11:29:25 2005 +0000
@@ -0,0 +1,674 @@
+/* -*- 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 <iostream>
+#include <sstream>
+
+#include <map>
+#include <vector>
+
+#include <memory>
+
+#include <lemon/error.h>
+
+/// \todo fix exceptions
+
+
+namespace lemon {
+
+  // Exceptions
+
+  class IOException {
+  public:
+    virtual ~IOException() {}
+    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 <typename _Exception>
+  class StreamException : public _Exception {
+  public:
+    typedef _Exception Exception;
+    StreamException(int _line, Exception _exception) 
+      : Exception(_exception), line_num(_line) {}
+    virtual int line() const {
+      return line_num;
+    }
+
+    virtual ~StreamException() {}
+
+    virtual std::string what() const {
+      ostringstream os;
+      os << Exception::what() << " in line " << line();
+      return os.str();
+    }
+  private:
+    int line_num;
+  };  
+
+
+  /// \brief Standard ReaderTraits for the GraphReader class.
+  ///
+  /// Standard ReaderTraits for the GraphReader class.
+  /// It defines standard reading method for all type of value. 
+  struct DefaultReaderTraits {
+
+    /// \brief Template class for reading an value.
+    ///
+    /// Template class for reading an value.
+    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 DataFormatException("Default Reader format exception");
+      }
+    };
+
+    /// 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.
+  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 >> 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;
+  };
+
+  /// \brief The graph reader class.
+  ///
+  /// The reader class for the graph input.
+  /// \see graph-io-page
+  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 from the given map,
+    /// it constructs the given map 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()) {
+	throw Exception() << "Multiple read rule for node map: " << name;
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for node map: " << name;
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for edge map: " << name;
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for edge map: " << name;
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for node";
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for edge";
+      }
+      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 DataFormatException("Invalid control sequence: " + line);
+	}
+      } catch (DataFormatException e) {
+	throw StreamException<DataFormatException>(line_num, e);
+      }
+    }
+
+  private:
+
+    template <typename Item> class InverterBase;
+
+    std::string readNodeSet(int& line_num, 
+			    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) {
+	  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<InverterBase<Node> >(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 < (int)index.size(); ++i) {
+	  index[i]->read(ls, node);
+	}
+      }
+      return line;
+    }
+
+    std::string readEdgeSet(int& line_num, 
+			    auto_ptr<InverterBase<Edge> > & edgeInverter, 
+			    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) {
+	  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<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);
+	edgeInverter->read(ls, edge);
+	for (int i = 1; i < (int)index.size(); ++i) {
+	  index[i]->read(ls, edge);
+	}
+      }      
+      return line;
+    }
+
+    std::string readNodes(int& line_num, 
+			  auto_ptr<InverterBase<Node> >& 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<InverterBase<Edge> >& 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 != (int)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 <typename _Item>
+    class InverterBase {
+    public:
+      typedef _Item Item;
+      virtual void read(std::istream&, const Item&) = 0;
+      virtual Item read(std::istream&) = 0;
+    };
+
+    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(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 <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(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 <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& 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;
+
+  };
+
+}
diff -r 8d066154b66a -r 83a48cfd8553 src/lemon/graph_writer.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/graph_writer.h	Mon Feb 07 11:29:25 2005 +0000
@@ -0,0 +1,372 @@
+/* -*- C++ -*-
+ * src/lemon/graph_writer.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 writer.
+
+
+#include <iostream>
+#include <sstream>
+
+#include <map>
+#include <vector>
+
+#include <memory>
+
+#include <lemon/invalid.h>
+#include <lemon/error.h>
+
+
+namespace lemon {
+
+  /// \brief Standard WriterTraits for the GraphWriter class.
+  ///
+  /// Standard WriterTraits for the GraphWriter class.
+  /// It defines standard writing method for all type of value. 
+  struct DefaultWriterTraits {
+
+    /// \brief Template class for writing an value.
+    ///
+    /// Template class for writing an value.
+    template <typename _Value>
+    struct Writer {
+      /// The value type.
+      typedef _Value Value;
+
+      /// \brief Writes a value from the given stream.
+      ///
+      /// Writes a value from the given stream.
+      void write(std::ostream& os, const Value& value) {
+	os << value << '\t';
+      }
+    };
+
+  };
+
+
+  /// \brief Writer class for quoted strings.
+  ///
+  /// Writer class for quoted strings. It can process the escape
+  /// sequences in the string.
+  class QuotedStringWriter {
+  public:
+    typedef std::string Value;
+
+    /// \brief Constructor for the writer.
+    ///
+    /// Constructor for the writer. If the given parameter is true
+    /// the writer creates escape sequences from special characters.
+    QuotedStringWriter(bool _escaped = true) : escaped(_escaped) {}
+
+    /// \brief Writes a quoted string from the given stream.
+    ///
+    /// Writes a quoted string from the given stream.
+    void write(std::ostream& os, const std::string& value) {
+      os << "\"";
+      if (escaped) {
+	ostringstream ls;
+	for (int i = 0; i < (int)value.size(); ++i) {
+	  writeEscape(ls, value[i]);
+	}
+	os << ls.str();
+      } else {
+	os << value;
+      }
+      os << "\"";
+    }
+
+  private:
+    
+    static void writeEscape(std::ostream& os, char c) {
+      switch (c) {
+      case '\\':
+	os << "\\\\";
+	return;
+      case '\"':
+	os << "\\\"";
+	return;
+      case '\'':
+	os << "\\\'";
+	return;
+      case '\?':
+	os << "\\\?";
+	return;
+      case '\a':
+	os << "\\a";
+	return;
+      case '\b':
+	os << "\\b";
+	return;
+      case '\f':
+	os << "\\f";
+	return;
+      case '\r':
+	os << "\\r";
+	return;
+      case '\n':
+	os << "\\n";
+	return;
+      case '\t':
+	os << "\\t";
+	return;
+      case '\v':
+	os << "\\v";
+	return;
+      default:
+	if (c < 0x20) {
+	  os << '\\' << oct << (int)c;
+	} else {
+	  os << c;
+	}
+	return;
+      }     
+    }
+  private:
+    bool escaped;
+  };
+
+  
+  /// \brief The graph writer class.
+  ///
+  /// The writer class for the graph output.
+  /// \see graph-io-page
+  template <typename _Graph, typename _WriterTraits = DefaultWriterTraits> 
+  class GraphWriter {
+  public:
+    
+    typedef _Graph Graph;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+
+    typedef _WriterTraits WriterTraits;
+ 
+    /// \brief Construct a new GraphWriter.
+    ///
+    /// Construct a new GraphWriter. It writes from the given map,
+    /// it constructs the given map and it use the given writer as the
+    /// default skipper.
+    GraphWriter(std::ostream& _os, Graph& _graph) : os(_os), graph(_graph) {}
+
+
+    /// \brief Destruct the graph writer.
+    ///
+    /// Destruct the graph writer.
+    ~GraphWriter() {
+      for (typename NodeMapWriters::iterator it = node_map_writers.begin(); 
+	   it != node_map_writers.end(); ++it) {
+	delete it->second;
+      }
+
+      for (typename EdgeMapWriters::iterator it = edge_map_writers.begin();
+	   it != edge_map_writers.end(); ++it) {
+	delete it->second;
+      }
+
+    }
+
+    // Node map rules
+
+    /// \brief Add a new node map writer command for the writer.
+    ///
+    /// Add a new node map writer command for the writer.
+    template <typename Map>
+    GraphWriter& addNodeMap(std::string name, const Map& map) {
+      return addNodeMap<typename WriterTraits::template Writer<
+	typename Map::Value>, Map>(name, map);
+    }
+
+    /// \brief Add a new node map writer command for the writer.
+    ///
+    /// Add a new node map writer command for the writer.
+    template <typename Writer, typename Map>
+    GraphWriter& addNodeMap(std::string name, const Map& map, 
+			      const Writer& writer = Writer()) {
+      node_map_writers.push_back(
+        make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));
+      return *this;
+    }
+
+    // Edge map rules
+
+    /// \brief Add a new edge map writer command for the writer.
+    ///
+    /// Add a new edge map writer command for the writer.
+    template <typename Map>
+    GraphWriter& addEdgeMap(std::string name, const Map& map) { 
+      return addEdgeMap<typename WriterTraits::template Writer<
+        typename Map::Value>, Map>(name, map);
+    }
+
+
+    /// \brief Add a new edge map writer command for the writer.
+    ///
+    /// Add a new edge map writer command for the writer.
+    template <typename Writer, typename Map>
+    GraphWriter& addEdgeMap(std::string name, 
+			    const Map& map, const Writer& writer = Writer()) {
+      edge_map_writers.push_back(make_pair(name, 
+	new MapWriter<Edge, Map, Writer>(map, writer)));
+      return *this;
+    }
+
+    /// \brief Add a new labeled node writer for the writer.
+    ///
+    /// Add a new labeled node writer for the writer.
+    GraphWriter& addNode(std::string name, const Node& node) {
+      node_writers.push_back(make_pair(name, node));
+      return *this;
+    }
+
+    /// \brief Add a new labeled edge writer for the writer.
+    ///
+    /// Add a new labeled edge writer for the writer.
+    GraphWriter& addEdge(std::string name, const Edge& edge) {
+      edge_writers.push_back(make_pair(name, edge));
+      return *this;
+    }
+
+    /// \brief Executes the writer commands.
+    ///
+    /// Executes the writer commands.
+    void run() {   
+      writeNodeSet();
+      writeEdgeSet();
+      writeNodes();
+      writeEdges();
+      os << "@end" << std::endl;
+    }
+
+  private:
+
+    void writeNodeSet() {
+      if (node_map_writers.size() == 0) return;
+      os << "@nodeset" << std::endl;
+      for (int i = 0; i < (int)node_map_writers.size(); ++i) {
+	os << node_map_writers[i].first << '\t';
+      } 
+      os << std::endl;
+      for (NodeIt it(graph); it != INVALID; ++it) {
+	for (int i = 0; i < (int)node_map_writers.size(); ++i) {
+	  node_map_writers[i].second->write(os, it);
+	}
+	os << std::endl;
+      }
+
+    }
+
+    void writeEdgeSet() {
+      if (edge_map_writers.size() == 0) return;
+      if (node_map_writers.size() == 0) {
+	throw Exception() << "Missing node id map";
+      }
+      os << "@edgeset" << std::endl;
+      os << "\t\t";
+      for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
+	os << edge_map_writers[i].first << '\t';
+      } 
+      os << std::endl;
+      for (EdgeIt it(graph); it != INVALID; ++it) {
+	node_map_writers[0].second->write(os, graph.source(it));
+	node_map_writers[0].second->write(os, graph.target(it));
+	for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
+	  edge_map_writers[i].second->write(os, it);
+	}
+	os << std::endl;
+      }
+    }
+
+    void writeNodes() {
+      if (node_writers.size() == 0) return;
+      if (node_map_writers.size() == 0) {
+	throw Exception() << "Missing node id map";
+      }
+      os << "@nodes" << std::endl;
+      for (int i = 0; i < (int)node_writers.size(); ++i) {
+	os << node_writers[i].first << '\t';
+	node_map_writers[0].second->write(os, node_writers[i].second);
+	os << std::endl;
+      } 
+    }
+
+    void writeEdges() {
+      if (edge_writers.size() == 0) return;
+      if (edge_map_writers.size() == 0) {
+	throw Exception() << "Missing edge id map";
+      }
+      os << "@edges" << std::endl;
+      for (int i = 0; i < (int)edge_writers.size(); ++i) {
+	os << edge_writers[i].first << '\t';
+	edge_map_writers[0].second->write(os, edge_writers[i].second);
+	os << std::endl;
+      } 
+    }
+    
+    // Writers
+
+    template <class _Item>
+    class WriterBase {
+    public:
+      typedef _Item Item;
+      virtual void write(std::ostream&, const Item&) = 0;
+    };
+
+    template <class _Item, typename _Map, typename _Writer>
+    class MapWriter : public WriterBase<_Item> {
+    public:
+      typedef _Map Map;
+      typedef _Writer Writer;
+      typedef typename Writer::Value Value;
+      typedef _Item Item;
+      
+      const Map& map;
+      Writer writer;
+
+      MapWriter(const Map& _map, const Writer& _writer) 
+	: map(_map), writer(_writer) {}
+
+
+      virtual void write(std::ostream& os, const Item& item) {
+	writer.write(os, map[item]);
+      }
+
+    };
+
+
+
+    typedef std::vector< std::pair<std::string, WriterBase<Node>*> > 
+      NodeMapWriters;
+    NodeMapWriters node_map_writers;
+
+    typedef std::vector< std::pair<std::string, WriterBase<Edge>*> > 
+      EdgeMapWriters;
+    EdgeMapWriters edge_map_writers;
+
+    typedef std::vector<std::pair<std::string, Node> > NodeWriters;
+    NodeWriters node_writers;
+
+    typedef std::vector<std::pair<std::string, Edge> > EdgeWriters;
+    EdgeWriters edge_writers;
+
+    std::ostream& os;
+    Graph& graph;
+
+  };
+
+
+}
diff -r 8d066154b66a -r 83a48cfd8553 src/lemon/map_utils.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/map_utils.h	Mon Feb 07 11:29:25 2005 +0000
@@ -0,0 +1,276 @@
+/* -*- C++ -*-
+ * src/lemon/map_utils.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 mutils
+///\file
+///\brief Map utilities.
+
+#include <map>
+
+
+namespace lemon {
+
+  /// \addtogroup mutils
+  /// @{
+
+  /// \brief General inversable map type.
+
+  /// This type provides simple inversable map functions. 
+  /// The InversableMap wraps an arbitrary ReadWriteMap 
+  /// and if a key is setted to a new value then store it
+  /// in the inverse map.
+  /// \param _Graph The graph type.
+  /// \param _Map The map to extend with inversable functionality. 
+  template <
+    typename _Graph, 
+    typename _Map
+  >
+  class InversableMap : protected _Map {
+
+  public:
+    typedef _Graph Graph;
+
+    typedef _Map Map;
+    /// The key type of InversableMap (Node, Edge, UndirEdge).
+    typedef typename _Map::Key Key;
+    /// The value type of the InversableMap.
+    typedef typename _Map::Value Value;
+    typedef std::map<Value, Key> InverseMap;
+    
+    typedef typename _Map::ConstReference ConstReference;
+
+    /// \brief Constructor.
+    ///
+    /// Construct a new InversableMap for the graph.
+    ///
+    InversableMap(const Graph& graph) : Map(graph) {} 
+    
+    /// \brief The setter function of the map.
+    ///
+    /// It sets the map and the inverse map to given key-value pair.
+    void set(const Key& key, const Value& val) {
+      Value oldval = Map::operator[](key);
+      typename InverseMap::iterator it = invMap.find(oldval);
+      if (it != invMap.end() && it->second == key) {
+	invMap.erase(it);
+      }      
+      invMap.insert(make_pair(val, key));
+      Map::set(key, val);
+    }
+
+    /// \brief The getter function of the map.
+    ///
+    /// It gives back the value associated with the key.
+    ConstReference operator[](const Key& key) const {
+      return Map::operator[](key);
+    }
+
+    /// \brief Add a new key to the map.
+    ///
+    /// Add a new key to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void add(const Key& key) {
+      Map::add(key);
+    }
+
+    /// \brief Erase the key from the map.
+    ///
+    /// Erase the key to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void erase(const Key& key) {
+      Value val = Map::operator[](key);
+      typename InverseMap::iterator it = invMap.find(val);
+      if (it != invMap.end() && it->second == key) {
+	invMap.erase(it);
+      }
+      Map::erase(key);
+    }
+
+    /// \brief Clear the keys from the map and inverse map.
+    ///
+    /// Clear the keys from the map and inverse map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void clear() {
+      invMap.clear();
+      Map::clear();
+    }
+
+    /// \brief It gives back the just readeable inverse map.
+    ///
+    /// It gives back the just readeable inverse map.
+    const InverseMap& inverse() const {
+      return invMap;
+    } 
+
+
+  private:
+    InverseMap invMap;    
+  };
+
+
+  
+  /// \brief Provides a mutable, continous and unique descriptor for each 
+  /// item in the graph.
+  ///
+  /// The DescriptorMap class provides a mutable, continous and immutable
+  /// mapping for each item in the graph.
+  ///
+  /// \param _Graph The graph class the \c DescriptorMap belongs to.
+  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
+  /// UndirEdge.
+  /// \param _Map A ReadWriteMap mapping from the item type to integer.
+
+  template <
+    typename _Graph,   
+    typename _Item,
+    typename _Map
+  >
+  class DescriptorMap : protected _Map {
+
+    typedef _Item Item;
+    typedef _Map Map;
+
+  public:
+    /// The graph class of DescriptorMap.
+    typedef _Graph Graph;
+
+    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
+    typedef typename _Map::Key Key;
+    /// The value type of DescriptorMap.
+    typedef typename _Map::Value Value;
+
+    typedef std::vector<Item> InverseMap;
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating descriptor map.
+    DescriptorMap(const Graph& _graph) : Map(_graph) {
+      build();
+    }
+
+    /// \brief Add a new key to the map.
+    ///
+    /// Add a new key to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void add(const Item& item) {
+      Map::add(item);
+      Map::set(item, invMap.size());
+      invMap.push_back(item);
+    }
+
+    /// \brief Erase the key from the map.
+    ///
+    /// Erase the key to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void erase(const Item& item) {
+      Map::set(invMap.back(), Map::operator[](item));
+      invMap[Map::operator[](item)] = invMap.back();
+      Map::erase(item);
+    }
+
+    /// \brief Build the unique map.
+    ///
+    /// Build the unique map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void build() {
+      Map::build();
+      Item it;
+      for (getGraph()->first(it); it != INVALID; getGraph()->next(it)) {
+	Map::set(it, invMap.size());
+	invMap.push_back(it);	
+      }      
+    }
+    
+    /// \brief Clear the keys from the map.
+    ///
+    /// Clear the keys from the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void clear() {
+      invMap.clear();
+      Map::clear();
+    }
+
+    /// \brief Gives back the \e descriptor of the item.
+    ///
+    /// Gives back the mutable and unique \e descriptor of the map.
+    int operator[](const Item& item) const {
+      return Map::operator[](item);
+    }
+    
+    /// \brief Gives back the inverse of the map.
+    ///
+    /// Gives back the inverse of the map.
+    const InverseMap inverse() const {
+      return invMap;
+    }
+
+  private:
+    vector<Item> invMap;
+  };
+  
+  /// Provides an immutable and unique id for each item in the graph.
+
+  /// The IdMap class provides an unique and immutable mapping for each item
+  /// in the graph.
+  ///
+  template <typename _Graph, typename _Item>
+  class IdMap {
+  public:
+    typedef _Graph Graph;
+    typedef int Value;
+    typedef _Item Item;
+
+    /// \brief The class represents the inverse of the map.
+    ///
+    /// The class represents the inverse of the map.
+    /// \see inverse()
+    class InverseMap {
+    protected:
+      InverseMap(const Graph& _graph) : graph(_graph) {}
+    public:
+      /// \brief Gives back the given item by its id.
+      ///
+      /// Gives back the given item by its id.
+      /// 
+      Item operator[](int id) const { return graph->fromId(id, Item());}
+    private:
+      Graph* graph;
+    };
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating id map.
+    IdMap(const Graph& _graph) : graph(&_graph) {}
+
+    /// \brief Gives back the \e id of the item.
+    ///
+    /// Gives back the immutable and unique \e id of the map.
+    int operator[](const Item& item) const { return graph->id(item);}
+
+    /// \brief Gives back the inverse of the map.
+    ///
+    /// Gives back the inverse of the map.
+    InverseMap inverse() const { return InverseMap(*graph);} 
+
+  private:
+    const Graph* graph;
+
+  };
+
+
+
+}
+