lemon/lgf_writer.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 23 Apr 2008 15:33:53 +0200
changeset 147 7c39a090cfc3
parent 139 701c529ba737
child 148 4e2581021300
permissions -rw-r--r--
Fix missing semicolon in GRAPH_TYPEDEFS (ticket #89)
     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     DIGRAPH_TYPEDEFS(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