src/lemon/graph_reader.h
author ladanyi
Thu, 14 Apr 2005 21:23:25 +0000
changeset 1355 57936f15055b
parent 1341 bda966891ea0
child 1359 1581f961cfaa
permissions -rw-r--r--
- Use messages similar to stock autoconf macros'.
deba@1137
     1
/* -*- C++ -*-
deba@1137
     2
 * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
deba@1137
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1137
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
deba@1137
     6
 *
deba@1137
     7
 * Permission to use, modify and distribute this software is granted
deba@1137
     8
 * provided that this copyright notice appears in all copies. For
deba@1137
     9
 * precise terms see the accompanying LICENSE file.
deba@1137
    10
 *
deba@1137
    11
 * This software is provided "AS IS" with no warranty of any kind,
deba@1137
    12
 * express or implied, and with no claim as to its suitability for any
deba@1137
    13
 * purpose.
deba@1137
    14
 *
deba@1137
    15
 */
deba@1137
    16
alpar@1287
    17
///\ingroup io_group
deba@1137
    18
///\file
alpar@1287
    19
///\brief Lemon Graph Format reader.
deba@1137
    20
deba@1214
    21
#ifndef LEMON_GRAPH_READER_H
deba@1214
    22
#define LEMON_GRAPH_READER_H
deba@1214
    23
deba@1137
    24
#include <iostream>
deba@1137
    25
#include <sstream>
deba@1137
    26
deba@1137
    27
#include <map>
deba@1137
    28
#include <vector>
deba@1137
    29
deba@1137
    30
#include <memory>
deba@1137
    31
deba@1137
    32
#include <lemon/error.h>
deba@1137
    33
deba@1137
    34
deba@1137
    35
namespace lemon {
deba@1137
    36
deba@1333
    37
  /// \addtogroup io_group
deba@1333
    38
  /// @{
deba@1137
    39
deba@1137
    40
  /// \brief Standard ReaderTraits for the GraphReader class.
deba@1137
    41
  ///
deba@1137
    42
  /// Standard ReaderTraits for the GraphReader class.
deba@1137
    43
  /// It defines standard reading method for all type of value. 
deba@1333
    44
  /// \author Balazs Dezso
deba@1137
    45
  struct DefaultReaderTraits {
deba@1137
    46
deba@1333
    47
    /// \brief Template class for reading an value.
deba@1137
    48
    ///
deba@1137
    49
    /// Template class for reading an value.
deba@1333
    50
    /// \author Balazs Dezso
deba@1137
    51
    template <typename _Value>
deba@1137
    52
    struct Reader {
deba@1137
    53
      /// The value type.
deba@1137
    54
      typedef _Value Value;
deba@1137
    55
      /// \brief Reads a value from the given stream.
deba@1137
    56
      ///
deba@1137
    57
      /// Reads a value from the given stream.
deba@1137
    58
      void read(std::istream& is, Value& value) {
deba@1137
    59
	if (!(is >> value)) 
deba@1208
    60
	  throw DataFormatError("Default reader format exception");
deba@1137
    61
      }
deba@1137
    62
    };
deba@1137
    63
deba@1333
    64
    /// \brief Returns wheter this name is an ID map name.
deba@1333
    65
    ///
deba@1333
    66
    /// Returns wheter this name is an ID map name.
deba@1333
    67
    static bool idMapName(const std::string& name) {
deba@1333
    68
      return name == "id";
deba@1333
    69
    }
deba@1333
    70
deba@1137
    71
    /// The reader class for the not needed maps.
deba@1137
    72
    typedef Reader<std::string> DefaultReader;
deba@1137
    73
deba@1137
    74
  };
deba@1137
    75
deba@1137
    76
  /// \brief Reader class for quoted strings.
deba@1137
    77
  ///
deba@1137
    78
  /// Reader class for quoted strings. It can process the escape
deba@1137
    79
  /// sequences in the string.
deba@1333
    80
  /// \author Balazs Dezso
deba@1137
    81
  class QuotedStringReader {
deba@1137
    82
  public:
deba@1137
    83
    typedef std::string Value;
deba@1137
    84
    
deba@1137
    85
    /// \brief Constructor for the reader.
deba@1137
    86
    ///
deba@1137
    87
    /// Constructor for the reader. If the given parameter is true
deba@1137
    88
    /// the reader processes the escape sequences.
deba@1137
    89
    QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
deba@1137
    90
    
deba@1137
    91
    /// \brief Reads a quoted string from the given stream.
deba@1137
    92
    ///
deba@1137
    93
    /// Reads a quoted string from the given stream.
deba@1137
    94
    void read(std::istream& is, std::string& value) {
deba@1137
    95
      char c;
deba@1137
    96
      value.clear();
deba@1311
    97
      is >> std::ws;
deba@1137
    98
      if (!is.get(c) || c != '\"') 
deba@1208
    99
	throw DataFormatError("Quoted string format error");
deba@1137
   100
      while (is.get(c) && c != '\"') {
deba@1137
   101
	if (escaped && c == '\\') {
deba@1137
   102
	  value += readEscape(is);
deba@1137
   103
	} else {
deba@1137
   104
	  value += c;
deba@1137
   105
	}
deba@1137
   106
      }
deba@1208
   107
      if (!is) throw DataFormatError("Quoted string format error");
deba@1137
   108
    }
deba@1137
   109
deba@1137
   110
  private:
deba@1137
   111
    
deba@1137
   112
    static char readEscape(std::istream& is) {
deba@1137
   113
      char c;
deba@1137
   114
      switch (is.get(c), c) {
deba@1137
   115
      case '\\':
deba@1137
   116
	return '\\';
deba@1137
   117
      case '\"':
deba@1137
   118
	return '\"';
deba@1137
   119
      case '\'':
deba@1137
   120
	return '\'';
deba@1137
   121
      case '\?':
deba@1137
   122
	return '\?';
deba@1137
   123
      case 'a':
deba@1137
   124
	return '\a';
deba@1137
   125
      case 'b':
deba@1137
   126
	return '\b';
deba@1137
   127
      case 'f':
deba@1137
   128
	return '\f';
deba@1137
   129
      case 'n':
deba@1137
   130
	return '\n';
deba@1137
   131
      case 'r':
deba@1137
   132
	return '\r';
deba@1137
   133
      case 't':
deba@1137
   134
	return '\t';
deba@1137
   135
      case 'v':
deba@1137
   136
	return '\v';
deba@1137
   137
      case 'x':
deba@1137
   138
	{
deba@1137
   139
	  int code;
deba@1137
   140
	  if (!is.get(c) || !isHex(c)) 
deba@1208
   141
	    throw DataFormatError("Escape format error");
deba@1137
   142
	  else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
deba@1137
   143
	  else code = code * 16 + valueHex(c);
deba@1137
   144
	  return code;
deba@1137
   145
	}
deba@1137
   146
      default:
deba@1137
   147
	{
deba@1137
   148
	  int code;
deba@1137
   149
	  if (!isOct(c)) 
deba@1208
   150
	    throw DataFormatError("Escape format error");
deba@1137
   151
	  else if (code = valueOct(c), !is.get(c) || !isOct(c)) 
deba@1137
   152
	    is.putback(c);
deba@1137
   153
	  else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 
deba@1137
   154
	    is.putback(c);
deba@1137
   155
	  else code = code * 8 + valueOct(c);
deba@1137
   156
	  return code;
deba@1137
   157
	}	      
deba@1137
   158
      } 
deba@1137
   159
    }
deba@1137
   160
deba@1137
   161
    static bool isOct(char c) {
deba@1137
   162
      return '0' <= c && c <='7'; 
deba@1137
   163
    }
deba@1137
   164
    
deba@1137
   165
    static int valueOct(char c) {
deba@1137
   166
      return c - '0';
deba@1137
   167
    }
deba@1137
   168
deba@1137
   169
   static bool isHex(char c) {
deba@1137
   170
      return ('0' <= c && c <= '9') || 
deba@1137
   171
	('a' <= c && c <= 'z') || 
deba@1137
   172
	('A' <= c && c <= 'Z'); 
deba@1137
   173
    }
deba@1137
   174
    
deba@1137
   175
    static int valueHex(char c) {
deba@1137
   176
      if ('0' <= c && c <= '9') return c - '0';
deba@1137
   177
      if ('a' <= c && c <= 'z') return c - 'a' + 10;
deba@1137
   178
      return c - 'A' + 10;
deba@1137
   179
    }
deba@1137
   180
deba@1137
   181
    bool escaped;
deba@1137
   182
  };
deba@1137
   183
deba@1137
   184
  /// \brief The graph reader class.
deba@1137
   185
  ///
deba@1333
   186
  ///
deba@1333
   187
  /// The given file format may contain several maps and labeled nodes or 
deba@1333
   188
  /// edges.
deba@1333
   189
  ///
deba@1333
   190
  /// If you read a graph you need not read all the maps and items just those
deba@1333
   191
  /// that you need. The interface of the \c GraphReader is very similar to
deba@1333
   192
  /// the GraphWriter but the reading method does not depend on the order the
deba@1333
   193
  /// given commands.
deba@1333
   194
  ///
deba@1333
   195
  /// The reader object suppose that each not readed value does not contain 
deba@1333
   196
  /// whitespaces, therefore it has some extra possibilities to control how
deba@1333
   197
  /// it should skip the values when the string representation contains spaces.
deba@1333
   198
  ///
deba@1333
   199
  /// \code
deba@1333
   200
  /// GraphReader<ListGraph> reader(std::cin, graph);
deba@1333
   201
  /// \endcode
deba@1333
   202
  ///
deba@1333
   203
  /// The \c addNodeMap() function reads a map from the \c \@nodeset section.
deba@1333
   204
  /// If there is a map that you do not want to read from the file and there is
deba@1333
   205
  /// whitespace in the string represenation of the values then you should
deba@1333
   206
  /// call the \c skipNodeMap() template member function with proper 
deba@1333
   207
  /// parameters.
deba@1333
   208
  ///
deba@1333
   209
  /// \code
deba@1333
   210
  /// reader.addNodeMap("x-coord", xCoordMap);
deba@1333
   211
  /// reader.addNodeMap("y-coord", yCoordMap);
deba@1333
   212
  ///
deba@1333
   213
  /// reader.addNodeMap<QuotedStringReader>("label", labelMap);
deba@1333
   214
  /// reader.skipNodeMap<QuotedStringReader>("description");
deba@1333
   215
  ///
deba@1333
   216
  /// reader.addNodeMap("color", colorMap);
deba@1333
   217
  /// \endcode
deba@1333
   218
  ///
deba@1333
   219
  /// With the \c addEdgeMap() member function you can give an edge map
deba@1333
   220
  /// reading command similar to the NodeMaps. 
deba@1333
   221
  ///
deba@1333
   222
  /// \code
deba@1333
   223
  /// reader.addEdgeMap("weight", weightMap);
deba@1333
   224
  /// reader.addEdgeMap("label", labelMap);
deba@1333
   225
  /// \endcode
deba@1333
   226
  ///
deba@1333
   227
  /// With \c addNode() and \c addEdge() functions you can read labeled Nodes 
deba@1333
   228
  /// and Edges.
deba@1333
   229
  ///
deba@1333
   230
  /// \code
deba@1333
   231
  /// reader.addNode("source", sourceNode);
deba@1333
   232
  /// reader.addNode("target", targetNode);
deba@1333
   233
  ///
deba@1333
   234
  /// reader.addEdge("observed", edge);
deba@1333
   235
  /// \endcode
deba@1333
   236
  ///
deba@1333
   237
  /// After you give all read commands you must call the \c run() member
deba@1333
   238
  /// function, which execute all the commands.
deba@1333
   239
  ///
deba@1333
   240
  /// \code
deba@1333
   241
  /// reader.run();
deba@1333
   242
  /// \endcode
deba@1333
   243
  ///
alpar@1287
   244
  /// \see DefaultReaderTraits
alpar@1287
   245
  /// \see QuotedStringReader
alpar@1138
   246
  /// \see \ref GraphWriter
alpar@1138
   247
  /// \see \ref graph-io-page
deba@1333
   248
  /// \author Balazs Dezso
deba@1137
   249
  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits> 
deba@1137
   250
  class GraphReader {
deba@1137
   251
  public:
deba@1137
   252
    
deba@1137
   253
    typedef _Graph Graph;
deba@1137
   254
    typedef typename Graph::Node Node;
deba@1137
   255
    typedef typename Graph::Edge Edge;
deba@1137
   256
deba@1137
   257
    typedef _ReaderTraits ReaderTraits;
deba@1137
   258
    typedef typename ReaderTraits::DefaultReader DefaultReader;
deba@1137
   259
deba@1137
   260
    /// \brief Construct a new GraphReader.
deba@1137
   261
    ///
deba@1208
   262
    /// Construct a new GraphReader. It reads into the given graph
deba@1208
   263
    /// and it use the given reader as the default skipper.
deba@1137
   264
    GraphReader(std::istream& _is, Graph& _graph, 
deba@1137
   265
		const DefaultReader& _reader = DefaultReader()) 
deba@1137
   266
      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
deba@1137
   267
deba@1137
   268
    /// \brief Destruct the graph reader.
deba@1137
   269
    ///
deba@1137
   270
    /// Destruct the graph reader.
deba@1137
   271
    ~GraphReader() {
deba@1137
   272
      for (typename NodeMapReaders::iterator it = node_map_readers.begin(); 
deba@1137
   273
	   it != node_map_readers.end(); ++it) {
deba@1137
   274
	delete it->second;
deba@1137
   275
      }
deba@1137
   276
deba@1137
   277
      for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); 
deba@1137
   278
	   it != edge_map_readers.end(); ++it) {
deba@1137
   279
	delete it->second;
deba@1137
   280
      }
deba@1137
   281
deba@1137
   282
    }
deba@1137
   283
deba@1137
   284
    /// \brief Add a new node map reader command for the reader.
deba@1137
   285
    ///
deba@1137
   286
    /// Add a new node map reader command for the reader.
deba@1137
   287
    template <typename Map>
deba@1137
   288
    GraphReader& addNodeMap(std::string name, Map& map) {
deba@1137
   289
      return addNodeMap<typename ReaderTraits::template 
deba@1137
   290
	Reader<typename Map::Value>, Map>(name, map);
deba@1137
   291
    }
deba@1137
   292
deba@1137
   293
    /// \brief Add a new node map reader command for the reader.
deba@1137
   294
    ///
deba@1137
   295
    /// Add a new node map reader command for the reader.
deba@1137
   296
    template <typename Reader, typename Map>
deba@1137
   297
    GraphReader& addNodeMap(std::string name, Map& map, 
deba@1137
   298
			     const Reader& reader = Reader()) {
deba@1137
   299
      if (node_map_readers.find(name) != node_map_readers.end()) {
deba@1208
   300
	ErrorMessage msg;
deba@1208
   301
	msg << "Multiple read rule for node map: " << name;
deba@1214
   302
	throw IOParameterError(msg.message());
deba@1137
   303
      }
deba@1137
   304
      node_map_readers.insert(
deba@1137
   305
        make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
deba@1137
   306
      return *this;
deba@1137
   307
    }
deba@1137
   308
deba@1137
   309
    /// \brief Add a new node map skipper command for the reader.
deba@1137
   310
    ///
deba@1137
   311
    /// Add a new node map skipper command for the reader.
deba@1137
   312
    template <typename Reader>
deba@1137
   313
    GraphReader& skipNodeMap(std::string name, 
deba@1137
   314
			     const Reader& reader = Reader()) {
deba@1137
   315
      if (node_map_readers.find(name) != node_map_readers.end()) {
deba@1208
   316
	ErrorMessage msg;
deba@1208
   317
	msg << "Multiple read rule for node map: " << name;
deba@1214
   318
	throw IOParameterError(msg.message());
deba@1137
   319
      }
deba@1137
   320
      node_map_readers.insert(
deba@1137
   321
        make_pair(name, new SkipReader<Node, Reader>(reader)));
deba@1137
   322
      return *this;
deba@1137
   323
    }
deba@1137
   324
deba@1137
   325
    /// \brief Add a new edge map reader command for the reader.
deba@1137
   326
    ///
deba@1137
   327
    /// Add a new edge map reader command for the reader.
deba@1137
   328
    template <typename Map>
deba@1137
   329
    GraphReader& addEdgeMap(std::string name, Map& map) { 
deba@1137
   330
      return addEdgeMap<typename ReaderTraits::template
deba@1137
   331
	Reader<typename Map::Value>, Map>(name, map);
deba@1137
   332
    }
deba@1137
   333
deba@1137
   334
deba@1137
   335
    /// \brief Add a new edge map reader command for the reader.
deba@1137
   336
    ///
deba@1137
   337
    /// Add a new edge map reader command for the reader.
deba@1137
   338
    template <typename Reader, typename Map>
deba@1137
   339
    GraphReader& addEdgeMap(std::string name, Map& map,
deba@1137
   340
			     const Reader& reader = Reader()) {
deba@1137
   341
      if (edge_map_readers.find(name) != edge_map_readers.end()) {
deba@1208
   342
	ErrorMessage msg;
deba@1208
   343
	msg << "Multiple read rule for edge map: " << name;
deba@1214
   344
	throw IOParameterError(msg.message());
deba@1137
   345
      }
deba@1137
   346
      edge_map_readers.insert(
deba@1137
   347
        make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
deba@1137
   348
      return *this;
deba@1137
   349
    }
deba@1137
   350
deba@1137
   351
    /// \brief Add a new edge map skipper command for the reader.
deba@1137
   352
    ///
deba@1137
   353
    /// Add a new edge map skipper command for the reader.
deba@1137
   354
    template <typename Reader>
deba@1137
   355
    GraphReader& skipEdgeMap(std::string name,
deba@1137
   356
			     const Reader& reader = Reader()) {
deba@1137
   357
      if (edge_map_readers.find(name) != edge_map_readers.end()) {
deba@1208
   358
	ErrorMessage msg;
deba@1208
   359
	msg << "Multiple read rule for edge map: " << name;
deba@1214
   360
	throw IOParameterError(msg.message());
deba@1137
   361
      }
deba@1137
   362
      edge_map_readers.insert(
deba@1137
   363
        make_pair(name, new SkipReader<Edge, Reader>(reader)));
deba@1137
   364
      return *this;
deba@1137
   365
    }
deba@1137
   366
deba@1137
   367
    /// \brief Add a new labeled node reader for the reader.
deba@1137
   368
    ///
deba@1137
   369
    /// Add a new labeled node reader for the reader.
deba@1137
   370
    GraphReader& addNode(std::string name, Node& node) {
deba@1137
   371
      if (node_readers.find(name) != node_readers.end()) {
deba@1208
   372
	ErrorMessage msg;
deba@1208
   373
	msg << "Multiple read rule for node: " << name;
deba@1214
   374
	throw IOParameterError(msg.message());
deba@1137
   375
      }
deba@1137
   376
      node_readers.insert(make_pair(name, &node));
deba@1137
   377
      return *this;
deba@1137
   378
    }
deba@1137
   379
deba@1137
   380
    /// \brief Add a new labeled edge reader for the reader.
deba@1137
   381
    ///
deba@1137
   382
    /// Add a new labeled edge reader for the reader.
deba@1137
   383
    GraphReader& addEdge(std::string name, Edge& edge) {
deba@1137
   384
      if (edge_readers.find(name) != edge_readers.end()) {
deba@1208
   385
	ErrorMessage msg;
deba@1208
   386
	msg << "Multiple read rule for edge: " << name;
deba@1214
   387
	throw IOParameterError(msg.message());
deba@1137
   388
      }
deba@1137
   389
      edge_readers.insert(make_pair(name, &edge));
deba@1137
   390
      return *this;
deba@1137
   391
    }
deba@1137
   392
deba@1137
   393
    /// \brief Executes the reader commands.
deba@1137
   394
    ///
deba@1137
   395
    /// Executes the reader commands.
deba@1137
   396
    void run() {
deba@1137
   397
      int line_num = 0;
deba@1137
   398
      std::auto_ptr<InverterBase<Node> > nodeInverter;
deba@1137
   399
      std::auto_ptr<InverterBase<Edge> > edgeInverter;
deba@1137
   400
      try {
deba@1137
   401
	std::string line = readNotEmptyLine(is, line_num);
deba@1137
   402
	if (line.find("@nodeset") == 0) {
deba@1137
   403
	  line = readNodeSet(line_num, nodeInverter);
deba@1137
   404
	} 
deba@1137
   405
	if (line.find("@edgeset") == 0) {
deba@1137
   406
	  line = readEdgeSet(line_num, edgeInverter, nodeInverter);
deba@1137
   407
	}
deba@1137
   408
	if (line.find("@nodes") == 0) {
deba@1137
   409
	  line = readNodes(line_num, nodeInverter);
deba@1137
   410
	}
deba@1137
   411
	if (line.find("@edges") == 0) {
deba@1137
   412
	  line = readEdges(line_num, edgeInverter);
deba@1137
   413
	}
deba@1137
   414
	if (line.find("@end") != 0) {
deba@1208
   415
	  throw DataFormatError("Invalid control sequence error");
deba@1137
   416
	}
deba@1208
   417
      } catch (DataFormatError e) {
deba@1208
   418
	e.line(line_num);
deba@1208
   419
	throw e;
deba@1137
   420
      }
deba@1137
   421
    }
deba@1137
   422
deba@1137
   423
  private:
deba@1137
   424
deba@1137
   425
    template <typename Item> class InverterBase;
deba@1137
   426
deba@1137
   427
    std::string readNodeSet(int& line_num, 
deba@1311
   428
			    std::auto_ptr<InverterBase<Node> >& nodeInverter) {
deba@1137
   429
      std::vector<ReaderBase<Node>* > index;
deba@1137
   430
      {
deba@1137
   431
	std::string line = readNotEmptyLine(is, line_num);    
deba@1137
   432
	std::string id;
deba@1137
   433
	std::istringstream ls(line);	
deba@1137
   434
	while (ls >> id) {
deba@1137
   435
	  typename NodeMapReaders::iterator it = node_map_readers.find(id);
deba@1137
   436
	  if (it != node_map_readers.end()) {
deba@1137
   437
	    index.push_back(it->second);
deba@1137
   438
	    node_map_readers.erase(it);
deba@1137
   439
	  } else {
deba@1137
   440
	    index.push_back(&nodeSkipper);
deba@1137
   441
	  }
deba@1333
   442
	  if (ReaderTraits::idMapName(id) && nodeInverter.get() == 0) {
deba@1333
   443
	    nodeInverter.reset(index.back()->getInverter());
deba@1333
   444
	    index.back() = nodeInverter.get();
deba@1333
   445
	  }
deba@1137
   446
	}
deba@1137
   447
      }
deba@1137
   448
deba@1333
   449
//       if (index.size() == 0) {
deba@1333
   450
// 	throw DataFormatError("Cannot find node id map");
deba@1333
   451
//       }
deba@1137
   452
deba@1333
   453
//       nodeInverter = 
deba@1333
   454
// 	std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
deba@1137
   455
      std::string line;
deba@1137
   456
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
deba@1137
   457
	Node node = graph.addNode();
deba@1137
   458
	std::istringstream ls(line);
deba@1333
   459
	for (int i = 0; i < (int)index.size(); ++i) {
deba@1137
   460
	  index[i]->read(ls, node);
deba@1137
   461
	}
deba@1137
   462
      }
deba@1137
   463
      return line;
deba@1137
   464
    }
deba@1137
   465
deba@1137
   466
    std::string readEdgeSet(int& line_num, 
deba@1311
   467
			    std::auto_ptr<InverterBase<Edge> >& edgeInverter, 
deba@1311
   468
			    std::auto_ptr<InverterBase<Node> >& nodeInverter) {
deba@1137
   469
      std::vector<ReaderBase<Edge>*> index;
deba@1137
   470
      {
deba@1137
   471
	std::string line = readNotEmptyLine(is, line_num);    
deba@1137
   472
	std::string id;
deba@1137
   473
	std::istringstream ls(line);	
deba@1137
   474
	while (ls >> id) {
deba@1137
   475
	  typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
deba@1137
   476
	  if (it != edge_map_readers.end()) {
deba@1137
   477
	    index.push_back(it->second);
deba@1137
   478
	    edge_map_readers.erase(it);
deba@1137
   479
	  } else {
deba@1137
   480
	    index.push_back(&edgeSkipper);
deba@1137
   481
	  }
deba@1333
   482
	  if (ReaderTraits::idMapName(id) && edgeInverter.get() == 0) {
deba@1333
   483
	    edgeInverter.reset(index.back()->getInverter());
deba@1333
   484
	    index.back() = edgeInverter.get();
deba@1333
   485
	  }
deba@1137
   486
	}
deba@1137
   487
      }
deba@1333
   488
      
deba@1333
   489
      if (nodeInverter.get() == 0) {
deba@1333
   490
 	throw DataFormatError("Cannot find node id map");
deba@1333
   491
      }
deba@1333
   492
//       if (index.size() == 0) {
deba@1333
   493
// 	throw DataFormatError("Cannot find edge id map");
deba@1333
   494
//       }
deba@1137
   495
deba@1333
   496
//       edgeInverter = 
deba@1333
   497
// 	std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
deba@1137
   498
      std::string line;
deba@1137
   499
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {	
deba@1137
   500
	std::istringstream ls(line);
deba@1137
   501
	Node source = nodeInverter->read(ls);
deba@1137
   502
	Node target = nodeInverter->read(ls);
deba@1137
   503
	Edge edge = graph.addEdge(source, target);
deba@1333
   504
	for (int i = 0; i < (int)index.size(); ++i) {
deba@1137
   505
	  index[i]->read(ls, edge);
deba@1137
   506
	}
deba@1137
   507
      }      
deba@1137
   508
      return line;
deba@1137
   509
    }
deba@1137
   510
deba@1137
   511
    std::string readNodes(int& line_num, 
deba@1311
   512
			  std::auto_ptr<InverterBase<Node> >& nodeInverter) {
deba@1137
   513
      std::string line;
deba@1333
   514
      if (nodeInverter.get() == 0) {
deba@1333
   515
 	throw DataFormatError("Cannot find node id map");
deba@1333
   516
      }
deba@1137
   517
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
deba@1137
   518
	std::istringstream ls(line);
deba@1137
   519
	std::string name;
deba@1137
   520
	ls >> name;
deba@1137
   521
	typename NodeReaders::iterator it = node_readers.find(name);
deba@1137
   522
	if (it != node_readers.end()) {
deba@1137
   523
	  *(it -> second) = nodeInverter->read(ls);
deba@1137
   524
	} 
deba@1137
   525
      }        
deba@1137
   526
      return line;
deba@1137
   527
    }
deba@1137
   528
deba@1137
   529
    std::string readEdges(int& line_num, 
deba@1311
   530
			  std::auto_ptr<InverterBase<Edge> >& edgeInverter) {
deba@1137
   531
      std::string line;
deba@1333
   532
      if (edgeInverter.get() == 0) {
deba@1333
   533
 	throw DataFormatError("Cannot find edge id map");
deba@1333
   534
      }
deba@1137
   535
      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
deba@1137
   536
	std::istringstream ls(line);
deba@1137
   537
	std::string name;
deba@1137
   538
	ls >> name;
deba@1137
   539
	typename EdgeReaders::iterator it = edge_readers.find(name);
deba@1137
   540
	if (it != edge_readers.end()) {
deba@1137
   541
	  *(it -> second) = edgeInverter->read(ls);
deba@1137
   542
	} 
deba@1137
   543
      }        
deba@1137
   544
      return line;    
deba@1137
   545
    }
deba@1137
   546
deba@1137
   547
    std::string readNotEmptyLine(std::istream& is, int& line_num) {
deba@1137
   548
      std::string line;
deba@1137
   549
      while (++line_num, getline(is, line)) {	
deba@1333
   550
	int vi = line.find('#');
deba@1333
   551
	if (vi != (int)::std::string::npos) {
deba@1333
   552
	  line = line.substr(0, vi);
deba@1333
   553
	}
deba@1333
   554
	vi = line.find_first_not_of(" \t");
deba@1333
   555
	if (vi != (int)std::string::npos) { 
deba@1137
   556
	  return line.substr(vi);
deba@1137
   557
	}
deba@1137
   558
      }
deba@1208
   559
      throw DataFormatError("End of stream error");
deba@1137
   560
    }
deba@1137
   561
    
deba@1333
   562
    template <typename _Item>
deba@1333
   563
    class ReaderBase;
deba@1137
   564
    
deba@1137
   565
    template <typename _Item>
deba@1333
   566
    class InverterBase : public ReaderBase<_Item> {
deba@1137
   567
    public:
deba@1137
   568
      typedef _Item Item;
deba@1137
   569
      virtual void read(std::istream&, const Item&) = 0;
deba@1137
   570
      virtual Item read(std::istream&) = 0;
deba@1333
   571
deba@1333
   572
      virtual InverterBase<_Item>* getInverter() {
deba@1333
   573
	return this;
deba@1333
   574
      }
deba@1137
   575
    };
deba@1137
   576
deba@1137
   577
    template <typename _Item, typename _Map, typename _Reader>
deba@1137
   578
    class MapReaderInverter : public InverterBase<_Item> {
deba@1137
   579
    public:
deba@1137
   580
      typedef _Item Item;
deba@1137
   581
      typedef _Reader Reader;
deba@1137
   582
      typedef typename Reader::Value Value;
deba@1137
   583
      typedef _Map Map;
deba@1137
   584
      typedef std::map<Value, Item> Inverse;
deba@1137
   585
deba@1137
   586
      Map& map;
deba@1137
   587
      Reader reader;
deba@1137
   588
      Inverse inverse;
deba@1137
   589
deba@1137
   590
      MapReaderInverter(Map& _map, const Reader& _reader) 
deba@1137
   591
	: map(_map), reader(_reader) {}
deba@1137
   592
deba@1137
   593
      virtual ~MapReaderInverter() {}
deba@1137
   594
deba@1137
   595
      virtual void read(std::istream& is, const Item& item) {
deba@1137
   596
	Value value;
deba@1137
   597
	reader.read(is, value);
deba@1137
   598
	map.set(item, value);
deba@1137
   599
	typename Inverse::iterator it = inverse.find(value);
deba@1137
   600
	if (it == inverse.end()) {
deba@1311
   601
	  inverse.insert(std::make_pair(value, item));
deba@1137
   602
	} else {
deba@1208
   603
	  throw DataFormatError("Multiple ID occurence");
deba@1137
   604
	}
deba@1137
   605
      }
deba@1137
   606
deba@1137
   607
      virtual Item read(std::istream& is) {
deba@1137
   608
	Value value;
deba@1137
   609
	reader.read(is, value);	
deba@1137
   610
	typename Inverse::const_iterator it = inverse.find(value);
deba@1137
   611
	if (it != inverse.end()) {
deba@1137
   612
	  return it->second;
deba@1137
   613
	} else {
deba@1208
   614
	  throw DataFormatError("Invalid ID error");
deba@1137
   615
	}
deba@1137
   616
      }      
deba@1137
   617
    };
deba@1137
   618
deba@1137
   619
    template <typename _Item, typename _Reader>
deba@1137
   620
    class SkipReaderInverter : public InverterBase<_Item> {
deba@1137
   621
    public:
deba@1137
   622
      typedef _Item Item;
deba@1137
   623
      typedef _Reader Reader;
deba@1137
   624
      typedef typename Reader::Value Value;
deba@1137
   625
      typedef std::map<Value, Item> Inverse;
deba@1137
   626
deba@1137
   627
      Reader reader;
deba@1137
   628
deba@1137
   629
      SkipReaderInverter(const Reader& _reader) 
deba@1137
   630
	: reader(_reader) {}
deba@1137
   631
deba@1137
   632
      virtual ~SkipReaderInverter() {}
deba@1137
   633
deba@1137
   634
      virtual void read(std::istream& is, const Item& item) {
deba@1137
   635
	Value value;
deba@1137
   636
	reader.read(is, value);
deba@1137
   637
	typename Inverse::iterator it = inverse.find(value);
deba@1137
   638
	if (it == inverse.end()) {
deba@1311
   639
	  inverse.insert(std::make_pair(value, item));
deba@1137
   640
	} else {
deba@1208
   641
	  throw DataFormatError("Multiple ID occurence error");
deba@1137
   642
	}
deba@1137
   643
      }
deba@1137
   644
deba@1137
   645
      virtual Item read(std::istream& is) {
deba@1137
   646
	Value value;
deba@1137
   647
	reader.read(is, value);	
deba@1137
   648
	typename Inverse::const_iterator it = inverse.find(value);
deba@1137
   649
	if (it != inverse.end()) {
deba@1137
   650
	  return it->second;
deba@1137
   651
	} else {
deba@1208
   652
	  throw DataFormatError("Invalid ID error");
deba@1137
   653
	}
deba@1137
   654
      }      
deba@1137
   655
    private:
deba@1137
   656
      Inverse inverse;
deba@1137
   657
    };
deba@1137
   658
deba@1137
   659
    // Readers
deba@1137
   660
deba@1137
   661
    template <typename _Item>    
deba@1137
   662
    class ReaderBase {
deba@1137
   663
    public:
deba@1137
   664
      typedef _Item Item;
deba@1137
   665
deba@1137
   666
      //      virtual ~ReaderBase() {}
deba@1137
   667
deba@1137
   668
      virtual void read(std::istream& is, const Item& item) = 0;
deba@1137
   669
      virtual InverterBase<_Item>* getInverter() = 0;
deba@1137
   670
    };
deba@1137
   671
deba@1137
   672
    template <typename _Item, typename _Map, typename _Reader>
deba@1137
   673
    class MapReader : public ReaderBase<_Item> {
deba@1137
   674
    public:
deba@1137
   675
      typedef _Map Map;
deba@1137
   676
      typedef _Reader Reader;
deba@1137
   677
      typedef typename Reader::Value Value;
deba@1137
   678
      typedef _Item Item;
deba@1137
   679
      
deba@1137
   680
      Map& map;
deba@1137
   681
      Reader reader;
deba@1137
   682
deba@1137
   683
      MapReader(Map& _map, const Reader& _reader) 
deba@1137
   684
	: map(_map), reader(_reader) {}
deba@1137
   685
deba@1137
   686
      virtual ~MapReader() {}
deba@1137
   687
deba@1137
   688
      virtual void read(std::istream& is, const Item& item) {
deba@1137
   689
	Value value;
deba@1137
   690
	reader.read(is, value);
deba@1137
   691
	map.set(item, value);
deba@1137
   692
      }
deba@1137
   693
deba@1137
   694
      virtual InverterBase<_Item>* getInverter() {
deba@1137
   695
	return new MapReaderInverter<Item, Map, Reader>(map, reader);
deba@1137
   696
      }
deba@1137
   697
    };
deba@1137
   698
deba@1137
   699
deba@1137
   700
    template <typename _Item, typename _Reader>
deba@1137
   701
    class SkipReader : public ReaderBase<_Item> {
deba@1137
   702
    public:
deba@1137
   703
      typedef _Reader Reader;
deba@1137
   704
      typedef typename Reader::Value Value;
deba@1137
   705
      typedef _Item Item;
deba@1137
   706
deba@1137
   707
      Reader reader;
deba@1137
   708
      SkipReader(const Reader& _reader) : reader(_reader) {}
deba@1137
   709
deba@1137
   710
      virtual ~SkipReader() {}
deba@1137
   711
alpar@1250
   712
      virtual void read(std::istream& is, const Item&) {
deba@1137
   713
	Value value;
deba@1137
   714
	reader.read(is, value);
deba@1137
   715
      }      
deba@1137
   716
deba@1137
   717
      virtual InverterBase<Item>* getInverter() {
deba@1137
   718
	return new SkipReaderInverter<Item, Reader>(reader);
deba@1137
   719
      }
deba@1137
   720
    };
deba@1137
   721
deba@1137
   722
deba@1137
   723
    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
deba@1137
   724
    NodeMapReaders node_map_readers;
deba@1137
   725
deba@1137
   726
    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
deba@1137
   727
    EdgeMapReaders edge_map_readers;
deba@1137
   728
deba@1137
   729
    typedef std::map<std::string, Node*> NodeReaders;
deba@1137
   730
    NodeReaders node_readers;
deba@1137
   731
deba@1137
   732
    typedef std::map<std::string, Edge*> EdgeReaders;
deba@1137
   733
    EdgeReaders edge_readers;
deba@1137
   734
deba@1137
   735
    std::istream& is;
deba@1137
   736
    Graph& graph;
deba@1137
   737
deba@1137
   738
    SkipReader<Node, DefaultReader> nodeSkipper;
deba@1137
   739
    SkipReader<Edge, DefaultReader> edgeSkipper;
deba@1137
   740
deba@1137
   741
  };
deba@1137
   742
deba@1333
   743
  /// \brief Read a graph from the input.
deba@1333
   744
  ///
deba@1333
   745
  /// Read a graph from the input.
deba@1333
   746
  /// \param is The input stream.
deba@1333
   747
  /// \param g The graph.
deba@1333
   748
  /// \param capacity The capacity map.
deba@1333
   749
  /// \param s The source node.
deba@1333
   750
  /// \param t The target node.
deba@1333
   751
  /// \param cost The cost map.
deba@1208
   752
  template<typename Graph, typename CapacityMap, typename CostMap>
deba@1208
   753
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 
deba@1208
   754
		  typename Graph::Node &s, typename Graph::Node &t, 
deba@1208
   755
		  CostMap& cost) {
deba@1208
   756
    GraphReader<Graph> reader(is, g);
deba@1208
   757
    reader.addEdgeMap("capacity", capacity);
deba@1208
   758
    reader.addEdgeMap("cost", cost);
deba@1208
   759
    reader.addNode("source", s);
deba@1208
   760
    reader.addNode("target", t);
deba@1208
   761
    reader.run();
deba@1208
   762
  }
deba@1208
   763
deba@1333
   764
  /// \brief Read a graph from the input.
deba@1333
   765
  ///
deba@1333
   766
  /// Read a graph from the input.
deba@1333
   767
  /// \param is The input stream.
deba@1333
   768
  /// \param g The graph.
deba@1333
   769
  /// \param capacity The capacity map.
deba@1333
   770
  /// \param s The source node.
deba@1333
   771
  /// \param t The target node.
deba@1208
   772
  template<typename Graph, typename CapacityMap>
deba@1208
   773
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 
deba@1208
   774
		  typename Graph::Node &s, typename Graph::Node &t) {
deba@1208
   775
    GraphReader<Graph> reader(is, g);
deba@1208
   776
    reader.addEdgeMap("capacity", capacity);
deba@1208
   777
    reader.addNode("source", s);
deba@1208
   778
    reader.addNode("target", t);
deba@1208
   779
    reader.run();
deba@1208
   780
  }
deba@1208
   781
deba@1333
   782
  /// \brief Read a graph from the input.
deba@1333
   783
  ///
deba@1333
   784
  /// Read a graph from the input.
deba@1333
   785
  /// \param is The input stream.
deba@1333
   786
  /// \param g The graph.
deba@1333
   787
  /// \param capacity The capacity map.
deba@1333
   788
  /// \param s The source node.
deba@1208
   789
  template<typename Graph, typename CapacityMap>
deba@1208
   790
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 
deba@1208
   791
		  typename Graph::Node &s) {
deba@1208
   792
    GraphReader<Graph> reader(is, g);
deba@1208
   793
    reader.addEdgeMap("capacity", capacity);
deba@1208
   794
    reader.addNode("source", s);
deba@1208
   795
    reader.run();
deba@1208
   796
  }
deba@1208
   797
deba@1333
   798
  /// \brief Read a graph from the input.
deba@1333
   799
  ///
deba@1333
   800
  /// Read a graph from the input.
deba@1333
   801
  /// \param is The input stream.
deba@1333
   802
  /// \param g The graph.
deba@1333
   803
  /// \param capacity The capacity map.
deba@1208
   804
  template<typename Graph, typename CapacityMap>
deba@1208
   805
  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
deba@1208
   806
    GraphReader<Graph> reader(is, g);
deba@1208
   807
    reader.addEdgeMap("capacity", capacity);
deba@1208
   808
    reader.run();
deba@1208
   809
  }
deba@1208
   810
deba@1333
   811
  /// \brief Read a graph from the input.
deba@1333
   812
  ///
deba@1333
   813
  /// Read a graph from the input.
deba@1333
   814
  /// \param is The input stream.
deba@1333
   815
  /// \param g The graph.
deba@1208
   816
  template<typename Graph>
deba@1208
   817
  void readGraph(std::istream& is, Graph &g) {
deba@1208
   818
    GraphReader<Graph> reader(is, g);
deba@1208
   819
    reader.run();
deba@1208
   820
  }
deba@1208
   821
deba@1333
   822
  /// @}
deba@1137
   823
}
deba@1214
   824
deba@1214
   825
#endif