lemon/lgf_writer.h
changeset 144 4e626dbbe408
child 139 701c529ba737
equal deleted inserted replaced
-1:000000000000 0:aace8f24d8cb
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 ///\ingroup lemon_io
       
    20 ///\file
       
    21 ///\brief Lemon Graph Format writer.
       
    22 
       
    23 
       
    24 #ifndef LEMON_LGF_WRITER_H
       
    25 #define LEMON_LGF_WRITER_H
       
    26 
       
    27 #include <iostream>
       
    28 #include <fstream>
       
    29 #include <sstream>
       
    30 
       
    31 #include <algorithm>
       
    32 
       
    33 #include <vector>
       
    34 #include <functional>
       
    35 
       
    36 #include <lemon/assert.h>
       
    37 #include <lemon/graph_utils.h>
       
    38 
       
    39 namespace lemon {
       
    40 
       
    41   namespace _writer_bits {
       
    42 
       
    43     template <typename Value>
       
    44     struct DefaultConverter {
       
    45       std::string operator()(const Value& value) {
       
    46 	std::ostringstream os;
       
    47 	os << value;
       
    48 	return os.str();
       
    49       }
       
    50     };
       
    51 
       
    52     template <typename T>
       
    53     bool operator<(const T&, const T&) {
       
    54       throw DataFormatError("Label map is not comparable");
       
    55     }
       
    56 
       
    57     template <typename _Map>
       
    58     class MapLess {
       
    59     public:
       
    60       typedef _Map Map;
       
    61       typedef typename Map::Key Item;
       
    62 
       
    63     private:
       
    64       const Map& _map;
       
    65       
       
    66     public:
       
    67       MapLess(const Map& map) : _map(map) {}
       
    68 
       
    69       bool operator()(const Item& left, const Item& right) {
       
    70 	return _map[left] < _map[right];
       
    71       }
       
    72     };
       
    73 
       
    74     template <typename _Item>    
       
    75     class MapStorageBase {
       
    76     public:
       
    77       typedef _Item Item;
       
    78 
       
    79     public:
       
    80       MapStorageBase() {}
       
    81       virtual ~MapStorageBase() {}
       
    82 
       
    83       virtual std::string get(const Item& item) = 0;
       
    84       virtual void sort(std::vector<Item>&) = 0;
       
    85     };
       
    86 
       
    87     template <typename _Item, typename _Map, 
       
    88 	      typename _Converter = DefaultConverter<typename _Map::Value> >
       
    89     class MapStorage : public MapStorageBase<_Item> {
       
    90     public:
       
    91       typedef _Map Map;
       
    92       typedef _Converter Converter;
       
    93       typedef _Item Item;
       
    94       
       
    95     private:
       
    96       const Map& _map;
       
    97       Converter _converter;
       
    98 
       
    99     public:
       
   100       MapStorage(const Map& map, const Converter& converter = Converter()) 
       
   101 	: _map(map), _converter(converter) {}
       
   102       virtual ~MapStorage() {}
       
   103 
       
   104       virtual std::string get(const Item& item) {
       
   105 	return _converter(_map[item]);
       
   106       }
       
   107       virtual void sort(std::vector<Item>& items) {
       
   108 	MapLess<Map> less(_map);
       
   109 	std::sort(items.begin(), items.end(), less);
       
   110       }
       
   111     };
       
   112 
       
   113     class ValueStorageBase {
       
   114     public:
       
   115       ValueStorageBase() {}
       
   116       virtual ~ValueStorageBase() {}
       
   117 
       
   118       virtual std::string get() = 0;      
       
   119     };
       
   120 
       
   121     template <typename _Value, typename _Converter = DefaultConverter<_Value> >
       
   122     class ValueStorage : public ValueStorageBase {
       
   123     public:
       
   124       typedef _Value Value;
       
   125       typedef _Converter Converter;
       
   126 
       
   127     private:
       
   128       const Value& _value;
       
   129       Converter _converter;
       
   130 
       
   131     public:
       
   132       ValueStorage(const Value& value, const Converter& converter = Converter())
       
   133  	: _value(value), _converter(converter) {}
       
   134 
       
   135       virtual std::string get() {
       
   136 	return _converter(_value);
       
   137       }
       
   138     };
       
   139 
       
   140     template <typename Value>
       
   141     struct MapLookUpConverter {
       
   142       const std::map<Value, std::string>& _map;
       
   143       
       
   144       MapLookUpConverter(const std::map<Value, std::string>& map) 
       
   145 	: _map(map) {}
       
   146       
       
   147       std::string operator()(const Value& str) {
       
   148 	typename std::map<Value, std::string>::const_iterator it = 
       
   149 	  _map.find(str);
       
   150 	if (it == _map.end()) {
       
   151 	  throw DataFormatError("Item not found");
       
   152 	}
       
   153 	return it->second;
       
   154       }
       
   155     };
       
   156 
       
   157     bool isWhiteSpace(char c) {
       
   158       return c == ' ' || c == '\t' || c == '\v' || 
       
   159         c == '\n' || c == '\r' || c == '\f'; 
       
   160     }
       
   161 
       
   162     bool isEscaped(char c) {
       
   163       return c == '\\' || c == '\"' || c == '\'' || 
       
   164 	c == '\a' || c == '\b';
       
   165     }
       
   166 
       
   167     static void writeEscape(std::ostream& os, char c) {
       
   168       switch (c) {
       
   169       case '\\':
       
   170 	os << "\\\\";
       
   171 	return;
       
   172       case '\"':
       
   173 	os << "\\\"";
       
   174 	return;
       
   175       case '\a':
       
   176 	os << "\\a";
       
   177 	return;
       
   178       case '\b':
       
   179 	os << "\\b";
       
   180 	return;
       
   181       case '\f':
       
   182 	os << "\\f";
       
   183 	return;
       
   184       case '\r':
       
   185 	os << "\\r";
       
   186 	return;
       
   187       case '\n':
       
   188 	os << "\\n";
       
   189 	return;
       
   190       case '\t':
       
   191 	os << "\\t";
       
   192 	return;
       
   193       case '\v':
       
   194 	os << "\\v";
       
   195 	return;
       
   196       default:
       
   197 	if (c < 0x20) {
       
   198 	  os << '\\' << std::oct << static_cast<int>(c);
       
   199 	} else {
       
   200 	  os << c;
       
   201 	}
       
   202 	return;
       
   203       }     
       
   204     }
       
   205 
       
   206     bool requireEscape(const std::string& str) {
       
   207       std::istringstream is(str);
       
   208       char c;
       
   209       while (is.get(c)) {
       
   210 	if (isWhiteSpace(c) || isEscaped(c)) {
       
   211 	  return true;
       
   212 	}
       
   213       }
       
   214       return false;
       
   215     }
       
   216     
       
   217     std::ostream& writeToken(std::ostream& os, const std::string& str) {
       
   218 
       
   219       if (requireEscape(str)) {
       
   220 	os << '\"';
       
   221 	for (std::string::const_iterator it = str.begin(); 
       
   222 	     it != str.end(); ++it) {
       
   223 	  writeEscape(os, *it);
       
   224 	}	
       
   225 	os << '\"';
       
   226       } else {
       
   227 	os << str;
       
   228       }
       
   229       return os;
       
   230     }
       
   231 
       
   232   }
       
   233   
       
   234   /// \e
       
   235   template <typename _Digraph>
       
   236   class DigraphWriter {
       
   237   public:
       
   238 
       
   239     typedef _Digraph Digraph;
       
   240     GRAPH_TYPEDEFS(typename Digraph);
       
   241     
       
   242   private:
       
   243 
       
   244 
       
   245     std::ostream* _os;
       
   246     bool local_os;
       
   247 
       
   248     Digraph& _digraph;
       
   249 
       
   250     std::string _nodes_caption;
       
   251     std::string _arcs_caption;
       
   252     std::string _attributes_caption;
       
   253     
       
   254     typedef std::map<Node, std::string> NodeIndex;
       
   255     NodeIndex _node_index;
       
   256     typedef std::map<Arc, std::string> ArcIndex;
       
   257     ArcIndex _arc_index;
       
   258 
       
   259     typedef std::vector<std::pair<std::string, 
       
   260       _writer_bits::MapStorageBase<Node>* > > NodeMaps;    
       
   261     NodeMaps _node_maps; 
       
   262 
       
   263     typedef std::vector<std::pair<std::string, 
       
   264       _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
       
   265     ArcMaps _arc_maps;
       
   266 
       
   267     typedef std::vector<std::pair<std::string, 
       
   268       _writer_bits::ValueStorageBase*> > Attributes;
       
   269     Attributes _attributes;
       
   270 
       
   271     bool _skip_nodes;
       
   272     bool _skip_arcs;
       
   273 
       
   274   public:
       
   275 
       
   276     /// \e
       
   277     DigraphWriter(std::ostream& is, Digraph& digraph) 
       
   278       : _os(&is), local_os(false), _digraph(digraph),
       
   279 	_skip_nodes(false), _skip_arcs(false) {}
       
   280 
       
   281     /// \e
       
   282     DigraphWriter(const std::string& fn, Digraph& digraph) 
       
   283       : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
       
   284 	_skip_nodes(false), _skip_arcs(false) {}
       
   285 
       
   286     /// \e
       
   287     DigraphWriter(const char* fn, Digraph& digraph) 
       
   288       : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
       
   289 	_skip_nodes(false), _skip_arcs(false) {}
       
   290 
       
   291     DigraphWriter(DigraphWriter& other) 
       
   292       : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
       
   293 	_skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
       
   294 
       
   295       other.is = 0;
       
   296       other.local_os = false;
       
   297 
       
   298       _node_index.swap(other._node_index);
       
   299       _arc_index.swap(other._arc_index);
       
   300 
       
   301       _node_maps.swap(other._node_maps);
       
   302       _arc_maps.swap(other._arc_maps);
       
   303       _attributes.swap(other._attributes);
       
   304 
       
   305       _nodes_caption = other._nodes_caption;
       
   306       _arcs_caption = other._arcs_caption;
       
   307       _attributes_caption = other._attributes_caption;
       
   308     }
       
   309 
       
   310     /// \e
       
   311     ~DigraphWriter() {
       
   312       for (typename NodeMaps::iterator it = _node_maps.begin(); 
       
   313 	   it != _node_maps.end(); ++it) {
       
   314 	delete it->second;
       
   315       }
       
   316 
       
   317       for (typename ArcMaps::iterator it = _arc_maps.begin(); 
       
   318 	   it != _arc_maps.end(); ++it) {
       
   319 	delete it->second;
       
   320       }
       
   321 
       
   322       for (typename Attributes::iterator it = _attributes.begin(); 
       
   323 	   it != _attributes.end(); ++it) {
       
   324 	delete it->second;
       
   325       }
       
   326 
       
   327       if (local_os) {
       
   328 	delete _os;
       
   329       }
       
   330     }
       
   331 
       
   332   private:
       
   333     
       
   334     DigraphWriter& operator=(const DigraphWriter&);
       
   335 
       
   336   public:
       
   337 
       
   338     /// \e
       
   339     template <typename Map>
       
   340     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
       
   341       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
       
   342       _writer_bits::MapStorageBase<Node>* storage = 
       
   343 	new _writer_bits::MapStorage<Node, Map>(map);
       
   344       _node_maps.push_back(std::make_pair(caption, storage));
       
   345       return *this;
       
   346     }
       
   347 
       
   348     /// \e
       
   349     template <typename Map, typename Converter>
       
   350     DigraphWriter& nodeMap(const std::string& caption, const Map& map, 
       
   351 			   const Converter& converter = Converter()) {
       
   352       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
       
   353       _writer_bits::MapStorageBase<Node>* storage = 
       
   354 	new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
       
   355       _node_maps.push_back(std::make_pair(caption, storage));
       
   356       return *this;
       
   357     }
       
   358 
       
   359     /// \e
       
   360     template <typename Map>
       
   361     DigraphWriter& arcMap(const std::string& caption, const Map& map) {
       
   362       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
       
   363       _writer_bits::MapStorageBase<Arc>* storage = 
       
   364 	new _writer_bits::MapStorage<Arc, Map>(map);
       
   365       _arc_maps.push_back(std::make_pair(caption, storage));
       
   366       return *this;
       
   367     }
       
   368 
       
   369     /// \e
       
   370     template <typename Map, typename Converter>
       
   371     DigraphWriter& arcMap(const std::string& caption, const Map& map, 
       
   372 			  const Converter& converter = Converter()) {
       
   373       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
       
   374       _writer_bits::MapStorageBase<Arc>* storage = 
       
   375 	new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
       
   376       _arc_maps.push_back(std::make_pair(caption, storage));
       
   377       return *this;
       
   378     }
       
   379 
       
   380     /// \e
       
   381     template <typename Value>
       
   382     DigraphWriter& attribute(const std::string& caption, const Value& value) {
       
   383       _writer_bits::ValueStorageBase* storage = 
       
   384 	new _writer_bits::ValueStorage<Value>(value);
       
   385       _attributes.push_back(std::make_pair(caption, storage));
       
   386       return *this;
       
   387     }
       
   388 
       
   389     /// \e
       
   390     template <typename Value, typename Converter>
       
   391     DigraphWriter& attribute(const std::string& caption, const Value& value, 
       
   392 			     const Converter& converter = Converter()) {
       
   393       _writer_bits::ValueStorageBase* storage = 
       
   394 	new _writer_bits::ValueStorage<Value, Converter>(value, converter);
       
   395       _attributes.push_back(std::make_pair(caption, storage));
       
   396       return *this;
       
   397     }
       
   398 
       
   399     /// \e
       
   400     DigraphWriter& node(const std::string& caption, const Node& node) {
       
   401       typedef _writer_bits::MapLookUpConverter<Node> Converter;
       
   402       Converter converter(_node_index);
       
   403       _writer_bits::ValueStorageBase* storage = 
       
   404 	new _writer_bits::ValueStorage<Node, Converter>(node, converter);
       
   405       _attributes.push_back(std::make_pair(caption, storage));
       
   406       return *this;
       
   407     }
       
   408 
       
   409     /// \e
       
   410     DigraphWriter& arc(const std::string& caption, const Arc& arc) {
       
   411       typedef _writer_bits::MapLookUpConverter<Arc> Converter;
       
   412       Converter converter(_arc_index);
       
   413       _writer_bits::ValueStorageBase* storage = 
       
   414 	new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
       
   415       _attributes.push_back(std::make_pair(caption, storage));
       
   416       return *this;
       
   417     }
       
   418 
       
   419     /// \e
       
   420     DigraphWriter& nodes(const std::string& caption) {
       
   421       _nodes_caption = caption;
       
   422       return *this;
       
   423     }
       
   424 
       
   425     /// \e
       
   426     DigraphWriter& arcs(const std::string& caption) {
       
   427       _arcs_caption = caption;
       
   428       return *this;
       
   429     }
       
   430 
       
   431     /// \e
       
   432     DigraphWriter& attributes(const std::string& caption) {
       
   433       _attributes_caption = caption;
       
   434       return *this;
       
   435     }
       
   436 
       
   437     DigraphWriter& skipNodes() {
       
   438       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
       
   439       return *this;
       
   440     }
       
   441 
       
   442     DigraphWriter& skipArcs() {
       
   443       LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
       
   444       return *this;
       
   445     }
       
   446 
       
   447   private:
       
   448 
       
   449     void writeNodes() {
       
   450       _writer_bits::MapStorageBase<Node>* label = 0;
       
   451       for (typename NodeMaps::iterator it = _node_maps.begin();
       
   452 	   it != _node_maps.end(); ++it) {
       
   453         if (it->first == "label") {
       
   454 	  label = it->second;
       
   455 	  break;
       
   456 	}
       
   457       }
       
   458 
       
   459       *_os << "@nodes";
       
   460       if (!_nodes_caption.empty()) {
       
   461 	*_os << ' ' << _nodes_caption;
       
   462       }
       
   463       *_os << std::endl;
       
   464 
       
   465       if (label == 0) {
       
   466 	*_os << "label" << '\t';
       
   467       }
       
   468       for (typename NodeMaps::iterator it = _node_maps.begin();
       
   469 	   it != _node_maps.end(); ++it) {
       
   470 	*_os << it->first << '\t';
       
   471       }
       
   472       *_os << std::endl;
       
   473 
       
   474       std::vector<Node> nodes;
       
   475       for (NodeIt n(_digraph); n != INVALID; ++n) {
       
   476 	nodes.push_back(n);
       
   477       }
       
   478       
       
   479       if (label == 0) {
       
   480 	IdMap<Digraph, Node> id_map(_digraph);
       
   481 	_writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
       
   482 	std::sort(nodes.begin(), nodes.end(), id_less);
       
   483       } else {
       
   484 	label->sort(nodes);
       
   485       }
       
   486 
       
   487       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
       
   488 	Node n = nodes[i];
       
   489 	if (label == 0) {
       
   490 	  std::ostringstream os;
       
   491 	  os << _digraph.id(n);
       
   492 	  _writer_bits::writeToken(*_os, os.str());
       
   493 	  *_os << '\t';
       
   494 	  _node_index.insert(std::make_pair(n, os.str()));
       
   495 	}
       
   496 	for (typename NodeMaps::iterator it = _node_maps.begin();
       
   497 	     it != _node_maps.end(); ++it) {
       
   498 	  std::string value = it->second->get(n);
       
   499 	  _writer_bits::writeToken(*_os, value);
       
   500 	  if (it->first == "label") {
       
   501 	    _node_index.insert(std::make_pair(n, value));
       
   502 	  }
       
   503 	  *_os << '\t';
       
   504 	}
       
   505 	*_os << std::endl;
       
   506       }
       
   507     }
       
   508 
       
   509     void writeArcs() {
       
   510       _writer_bits::MapStorageBase<Arc>* label = 0;
       
   511       for (typename ArcMaps::iterator it = _arc_maps.begin();
       
   512 	   it != _arc_maps.end(); ++it) {
       
   513         if (it->first == "label") {
       
   514 	  label = it->second;
       
   515 	  break;
       
   516 	}
       
   517       }
       
   518 
       
   519       *_os << "@arcs";
       
   520       if (!_arcs_caption.empty()) {
       
   521 	*_os << ' ' << _arcs_caption;
       
   522       }
       
   523       *_os << std::endl;
       
   524 
       
   525       *_os << '\t' << '\t';
       
   526       if (label == 0) {
       
   527 	*_os << "label" << '\t';
       
   528       }
       
   529       for (typename ArcMaps::iterator it = _arc_maps.begin();
       
   530 	   it != _arc_maps.end(); ++it) {
       
   531 	*_os << it->first << '\t';
       
   532       }
       
   533       *_os << std::endl;
       
   534 
       
   535       std::vector<Arc> arcs;
       
   536       for (ArcIt n(_digraph); n != INVALID; ++n) {
       
   537 	arcs.push_back(n);
       
   538       }
       
   539       
       
   540       if (label == 0) {
       
   541 	IdMap<Digraph, Arc> id_map(_digraph);
       
   542 	_writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
       
   543 	std::sort(arcs.begin(), arcs.end(), id_less);
       
   544       } else {
       
   545 	label->sort(arcs);
       
   546       }
       
   547 
       
   548       for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
       
   549 	Arc a = arcs[i];
       
   550 	_writer_bits::writeToken(*_os, _node_index.
       
   551 				 find(_digraph.source(a))->second);
       
   552 	*_os << '\t';
       
   553 	_writer_bits::writeToken(*_os, _node_index.
       
   554 				 find(_digraph.target(a))->second);
       
   555 	*_os << '\t';
       
   556 	if (label == 0) {
       
   557 	  std::ostringstream os;
       
   558 	  os << _digraph.id(a);
       
   559 	  _writer_bits::writeToken(*_os, os.str());
       
   560 	  *_os << '\t';
       
   561 	  _arc_index.insert(std::make_pair(a, os.str()));
       
   562 	}
       
   563 	for (typename ArcMaps::iterator it = _arc_maps.begin();
       
   564 	     it != _arc_maps.end(); ++it) {
       
   565 	  std::string value = it->second->get(a);
       
   566 	  _writer_bits::writeToken(*_os, value);
       
   567 	  if (it->first == "label") {
       
   568 	    _arc_index.insert(std::make_pair(a, value));
       
   569 	  }
       
   570 	  *_os << '\t';
       
   571 	}
       
   572 	*_os << std::endl;
       
   573       }
       
   574     }
       
   575 
       
   576     void writeAttributes() {
       
   577       if (_attributes.empty()) return;
       
   578       *_os << "@attributes";
       
   579       if (!_attributes_caption.empty()) {
       
   580 	*_os << ' ' << _attributes_caption;
       
   581       }
       
   582       *_os << std::endl;
       
   583       for (typename Attributes::iterator it = _attributes.begin();
       
   584 	   it != _attributes.end(); ++it) {
       
   585 	*_os << it->first << ' ';
       
   586 	_writer_bits::writeToken(*_os, it->second->get());
       
   587 	*_os << std::endl;
       
   588       }
       
   589     }
       
   590     
       
   591   public:
       
   592     
       
   593     /// \e
       
   594     void run() {
       
   595       if (!_skip_nodes) {
       
   596 	writeNodes();
       
   597       }
       
   598       if (!_skip_arcs) {      
       
   599 	writeArcs();
       
   600       }
       
   601       writeAttributes();
       
   602     }
       
   603 
       
   604     /// \e
       
   605     std::ostream& stream() {
       
   606       return *_os;
       
   607     }
       
   608   };
       
   609 
       
   610   template <typename Digraph>
       
   611   DigraphWriter<Digraph> digraphWriter(std::istream& is, Digraph& digraph) {
       
   612     return DigraphWriter<Digraph>(is, digraph);
       
   613   }
       
   614 
       
   615   template <typename Digraph>
       
   616   DigraphWriter<Digraph> digraphWriter(const std::string& fn, 
       
   617 				       Digraph& digraph) {
       
   618     return DigraphWriter<Digraph>(fn, digraph);
       
   619   }
       
   620 
       
   621   template <typename Digraph>
       
   622   DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
       
   623     return DigraphWriter<Digraph>(fn, digraph);
       
   624   }
       
   625 }
       
   626 
       
   627 #endif