lemon/lgf_writer.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:30:45 +0100
changeset 809 22bb98ca0101
parent 598 a3402913cffe
parent 584 33c6b6e755cd
child 877 141f9c0db4a3
permissions -rw-r--r--
Entirely rework CostScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Traits class + named parameter for the LargeCost type used in
internal computations.
- Extend the documentation.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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 \ref lgf-format "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/core.h>
    37 #include <lemon/maps.h>
    38 
    39 #include <lemon/concept_check.h>
    40 #include <lemon/concepts/maps.h>
    41 
    42 namespace lemon {
    43 
    44   namespace _writer_bits {
    45 
    46     template <typename Value>
    47     struct DefaultConverter {
    48       std::string operator()(const Value& value) {
    49         std::ostringstream os;
    50         os << value;
    51         return os.str();
    52       }
    53     };
    54 
    55     template <typename T>
    56     bool operator<(const T&, const T&) {
    57       throw FormatError("Label map is not comparable");
    58     }
    59 
    60     template <typename _Map>
    61     class MapLess {
    62     public:
    63       typedef _Map Map;
    64       typedef typename Map::Key Item;
    65 
    66     private:
    67       const Map& _map;
    68 
    69     public:
    70       MapLess(const Map& map) : _map(map) {}
    71 
    72       bool operator()(const Item& left, const Item& right) {
    73         return _map[left] < _map[right];
    74       }
    75     };
    76 
    77     template <typename _Graph, bool _dir, typename _Map>
    78     class GraphArcMapLess {
    79     public:
    80       typedef _Map Map;
    81       typedef _Graph Graph;
    82       typedef typename Graph::Edge Item;
    83 
    84     private:
    85       const Graph& _graph;
    86       const Map& _map;
    87 
    88     public:
    89       GraphArcMapLess(const Graph& graph, const Map& map)
    90         : _graph(graph), _map(map) {}
    91 
    92       bool operator()(const Item& left, const Item& right) {
    93         return _map[_graph.direct(left, _dir)] <
    94           _map[_graph.direct(right, _dir)];
    95       }
    96     };
    97 
    98     template <typename _Item>
    99     class MapStorageBase {
   100     public:
   101       typedef _Item Item;
   102 
   103     public:
   104       MapStorageBase() {}
   105       virtual ~MapStorageBase() {}
   106 
   107       virtual std::string get(const Item& item) = 0;
   108       virtual void sort(std::vector<Item>&) = 0;
   109     };
   110 
   111     template <typename _Item, typename _Map,
   112               typename _Converter = DefaultConverter<typename _Map::Value> >
   113     class MapStorage : public MapStorageBase<_Item> {
   114     public:
   115       typedef _Map Map;
   116       typedef _Converter Converter;
   117       typedef _Item Item;
   118 
   119     private:
   120       const Map& _map;
   121       Converter _converter;
   122 
   123     public:
   124       MapStorage(const Map& map, const Converter& converter = Converter())
   125         : _map(map), _converter(converter) {}
   126       virtual ~MapStorage() {}
   127 
   128       virtual std::string get(const Item& item) {
   129         return _converter(_map[item]);
   130       }
   131       virtual void sort(std::vector<Item>& items) {
   132         MapLess<Map> less(_map);
   133         std::sort(items.begin(), items.end(), less);
   134       }
   135     };
   136 
   137     template <typename _Graph, bool _dir, typename _Map,
   138               typename _Converter = DefaultConverter<typename _Map::Value> >
   139     class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
   140     public:
   141       typedef _Map Map;
   142       typedef _Converter Converter;
   143       typedef _Graph Graph;
   144       typedef typename Graph::Edge Item;
   145       static const bool dir = _dir;
   146 
   147     private:
   148       const Graph& _graph;
   149       const Map& _map;
   150       Converter _converter;
   151 
   152     public:
   153       GraphArcMapStorage(const Graph& graph, const Map& map,
   154                          const Converter& converter = Converter())
   155         : _graph(graph), _map(map), _converter(converter) {}
   156       virtual ~GraphArcMapStorage() {}
   157 
   158       virtual std::string get(const Item& item) {
   159         return _converter(_map[_graph.direct(item, dir)]);
   160       }
   161       virtual void sort(std::vector<Item>& items) {
   162         GraphArcMapLess<Graph, dir, Map> less(_graph, _map);
   163         std::sort(items.begin(), items.end(), less);
   164       }
   165     };
   166 
   167     class ValueStorageBase {
   168     public:
   169       ValueStorageBase() {}
   170       virtual ~ValueStorageBase() {}
   171 
   172       virtual std::string get() = 0;
   173     };
   174 
   175     template <typename _Value, typename _Converter = DefaultConverter<_Value> >
   176     class ValueStorage : public ValueStorageBase {
   177     public:
   178       typedef _Value Value;
   179       typedef _Converter Converter;
   180 
   181     private:
   182       const Value& _value;
   183       Converter _converter;
   184 
   185     public:
   186       ValueStorage(const Value& value, const Converter& converter = Converter())
   187         : _value(value), _converter(converter) {}
   188 
   189       virtual std::string get() {
   190         return _converter(_value);
   191       }
   192     };
   193 
   194     template <typename Value>
   195     struct MapLookUpConverter {
   196       const std::map<Value, std::string>& _map;
   197 
   198       MapLookUpConverter(const std::map<Value, std::string>& map)
   199         : _map(map) {}
   200 
   201       std::string operator()(const Value& str) {
   202         typename std::map<Value, std::string>::const_iterator it =
   203           _map.find(str);
   204         if (it == _map.end()) {
   205           throw FormatError("Item not found");
   206         }
   207         return it->second;
   208       }
   209     };
   210 
   211     template <typename Graph>
   212     struct GraphArcLookUpConverter {
   213       const Graph& _graph;
   214       const std::map<typename Graph::Edge, std::string>& _map;
   215 
   216       GraphArcLookUpConverter(const Graph& graph,
   217                               const std::map<typename Graph::Edge,
   218                                              std::string>& map)
   219         : _graph(graph), _map(map) {}
   220 
   221       std::string operator()(const typename Graph::Arc& val) {
   222         typename std::map<typename Graph::Edge, std::string>
   223           ::const_iterator it = _map.find(val);
   224         if (it == _map.end()) {
   225           throw FormatError("Item not found");
   226         }
   227         return (_graph.direction(val) ? '+' : '-') + it->second;
   228       }
   229     };
   230 
   231     inline bool isWhiteSpace(char c) {
   232       return c == ' ' || c == '\t' || c == '\v' ||
   233         c == '\n' || c == '\r' || c == '\f';
   234     }
   235 
   236     inline bool isEscaped(char c) {
   237       return c == '\\' || c == '\"' || c == '\'' ||
   238         c == '\a' || c == '\b';
   239     }
   240 
   241     inline static void writeEscape(std::ostream& os, char c) {
   242       switch (c) {
   243       case '\\':
   244         os << "\\\\";
   245         return;
   246       case '\"':
   247         os << "\\\"";
   248         return;
   249       case '\a':
   250         os << "\\a";
   251         return;
   252       case '\b':
   253         os << "\\b";
   254         return;
   255       case '\f':
   256         os << "\\f";
   257         return;
   258       case '\r':
   259         os << "\\r";
   260         return;
   261       case '\n':
   262         os << "\\n";
   263         return;
   264       case '\t':
   265         os << "\\t";
   266         return;
   267       case '\v':
   268         os << "\\v";
   269         return;
   270       default:
   271         if (c < 0x20) {
   272           std::ios::fmtflags flags = os.flags();
   273           os << '\\' << std::oct << static_cast<int>(c);
   274           os.flags(flags);
   275         } else {
   276           os << c;
   277         }
   278         return;
   279       }
   280     }
   281 
   282     inline bool requireEscape(const std::string& str) {
   283       if (str.empty() || str[0] == '@') return true;
   284       std::istringstream is(str);
   285       char c;
   286       while (is.get(c)) {
   287         if (isWhiteSpace(c) || isEscaped(c)) {
   288           return true;
   289         }
   290       }
   291       return false;
   292     }
   293 
   294     inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
   295 
   296       if (requireEscape(str)) {
   297         os << '\"';
   298         for (std::string::const_iterator it = str.begin();
   299              it != str.end(); ++it) {
   300           writeEscape(os, *it);
   301         }
   302         os << '\"';
   303       } else {
   304         os << str;
   305       }
   306       return os;
   307     }
   308 
   309     class Section {
   310     public:
   311       virtual ~Section() {}
   312       virtual void process(std::ostream& os) = 0;
   313     };
   314 
   315     template <typename Functor>
   316     class LineSection : public Section {
   317     private:
   318 
   319       Functor _functor;
   320 
   321     public:
   322 
   323       LineSection(const Functor& functor) : _functor(functor) {}
   324       virtual ~LineSection() {}
   325 
   326       virtual void process(std::ostream& os) {
   327         std::string line;
   328         while (!(line = _functor()).empty()) os << line << std::endl;
   329       }
   330     };
   331 
   332     template <typename Functor>
   333     class StreamSection : public Section {
   334     private:
   335 
   336       Functor _functor;
   337 
   338     public:
   339 
   340       StreamSection(const Functor& functor) : _functor(functor) {}
   341       virtual ~StreamSection() {}
   342 
   343       virtual void process(std::ostream& os) {
   344         _functor(os);
   345       }
   346     };
   347 
   348   }
   349 
   350   template <typename DGR>
   351   class DigraphWriter;
   352 
   353   template <typename TDGR>
   354   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
   355                                    std::ostream& os = std::cout);
   356   template <typename TDGR>
   357   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const std::string& fn);
   358 
   359   template <typename TDGR>
   360   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn);
   361 
   362 
   363   /// \ingroup lemon_io
   364   ///
   365   /// \brief \ref lgf-format "LGF" writer for directed graphs
   366   ///
   367   /// This utility writes an \ref lgf-format "LGF" file.
   368   ///
   369   /// The writing method does a batch processing. The user creates a
   370   /// writer object, then various writing rules can be added to the
   371   /// writer, and eventually the writing is executed with the \c run()
   372   /// member function. A map writing rule can be added to the writer
   373   /// with the \c nodeMap() or \c arcMap() members. An optional
   374   /// converter parameter can also be added as a standard functor
   375   /// converting from the value type of the map to \c std::string. If it
   376   /// is set, it will determine how the value type of the map is written to
   377   /// the output stream. If the functor is not set, then a default
   378   /// conversion will be used. The \c attribute(), \c node() and \c
   379   /// arc() functions are used to add attribute writing rules.
   380   ///
   381   ///\code
   382   /// DigraphWriter<DGR>(digraph, std::cout).
   383   ///   nodeMap("coordinates", coord_map).
   384   ///   nodeMap("size", size).
   385   ///   nodeMap("title", title).
   386   ///   arcMap("capacity", cap_map).
   387   ///   node("source", src).
   388   ///   node("target", trg).
   389   ///   attribute("caption", caption).
   390   ///   run();
   391   ///\endcode
   392   ///
   393   ///
   394   /// By default, the writer does not write additional captions to the
   395   /// sections, but they can be give as an optional parameter of
   396   /// the \c nodes(), \c arcs() or \c
   397   /// attributes() functions.
   398   ///
   399   /// The \c skipNodes() and \c skipArcs() functions forbid the
   400   /// writing of the sections. If two arc sections should be written
   401   /// to the output, it can be done in two passes, the first pass
   402   /// writes the node section and the first arc section, then the
   403   /// second pass skips the node section and writes just the arc
   404   /// section to the stream. The output stream can be retrieved with
   405   /// the \c ostream() function, hence the second pass can append its
   406   /// output to the output of the first pass.
   407   template <typename DGR>
   408   class DigraphWriter {
   409   public:
   410 
   411     typedef DGR Digraph;
   412     TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
   413 
   414   private:
   415 
   416 
   417     std::ostream* _os;
   418     bool local_os;
   419 
   420     const DGR& _digraph;
   421 
   422     std::string _nodes_caption;
   423     std::string _arcs_caption;
   424     std::string _attributes_caption;
   425 
   426     typedef std::map<Node, std::string> NodeIndex;
   427     NodeIndex _node_index;
   428     typedef std::map<Arc, std::string> ArcIndex;
   429     ArcIndex _arc_index;
   430 
   431     typedef std::vector<std::pair<std::string,
   432       _writer_bits::MapStorageBase<Node>* > > NodeMaps;
   433     NodeMaps _node_maps;
   434 
   435     typedef std::vector<std::pair<std::string,
   436       _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
   437     ArcMaps _arc_maps;
   438 
   439     typedef std::vector<std::pair<std::string,
   440       _writer_bits::ValueStorageBase*> > Attributes;
   441     Attributes _attributes;
   442 
   443     bool _skip_nodes;
   444     bool _skip_arcs;
   445 
   446   public:
   447 
   448     /// \brief Constructor
   449     ///
   450     /// Construct a directed graph writer, which writes to the given
   451     /// output stream.
   452     DigraphWriter(const DGR& digraph, std::ostream& os = std::cout)
   453       : _os(&os), local_os(false), _digraph(digraph),
   454         _skip_nodes(false), _skip_arcs(false) {}
   455 
   456     /// \brief Constructor
   457     ///
   458     /// Construct a directed graph writer, which writes to the given
   459     /// output file.
   460     DigraphWriter(const DGR& digraph, const std::string& fn)
   461       : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
   462         _skip_nodes(false), _skip_arcs(false) {
   463       if (!(*_os)) {
   464         delete _os;
   465         throw IoError("Cannot write file", fn);
   466       }
   467     }
   468 
   469     /// \brief Constructor
   470     ///
   471     /// Construct a directed graph writer, which writes to the given
   472     /// output file.
   473     DigraphWriter(const DGR& digraph, const char* fn)
   474       : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
   475         _skip_nodes(false), _skip_arcs(false) {
   476       if (!(*_os)) {
   477         delete _os;
   478         throw IoError("Cannot write file", fn);
   479       }
   480     }
   481 
   482     /// \brief Destructor
   483     ~DigraphWriter() {
   484       for (typename NodeMaps::iterator it = _node_maps.begin();
   485            it != _node_maps.end(); ++it) {
   486         delete it->second;
   487       }
   488 
   489       for (typename ArcMaps::iterator it = _arc_maps.begin();
   490            it != _arc_maps.end(); ++it) {
   491         delete it->second;
   492       }
   493 
   494       for (typename Attributes::iterator it = _attributes.begin();
   495            it != _attributes.end(); ++it) {
   496         delete it->second;
   497       }
   498 
   499       if (local_os) {
   500         delete _os;
   501       }
   502     }
   503 
   504   private:
   505 
   506     template <typename TDGR>
   507     friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
   508                                              std::ostream& os);
   509     template <typename TDGR>
   510     friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
   511                                              const std::string& fn);
   512     template <typename TDGR>
   513     friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
   514                                              const char *fn);
   515 
   516     DigraphWriter(DigraphWriter& other)
   517       : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
   518         _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
   519 
   520       other._os = 0;
   521       other.local_os = false;
   522 
   523       _node_index.swap(other._node_index);
   524       _arc_index.swap(other._arc_index);
   525 
   526       _node_maps.swap(other._node_maps);
   527       _arc_maps.swap(other._arc_maps);
   528       _attributes.swap(other._attributes);
   529 
   530       _nodes_caption = other._nodes_caption;
   531       _arcs_caption = other._arcs_caption;
   532       _attributes_caption = other._attributes_caption;
   533     }
   534 
   535     DigraphWriter& operator=(const DigraphWriter&);
   536 
   537   public:
   538 
   539     /// \name Writing Rules
   540     /// @{
   541 
   542     /// \brief Node map writing rule
   543     ///
   544     /// Add a node map writing rule to the writer.
   545     template <typename Map>
   546     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
   547       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   548       _writer_bits::MapStorageBase<Node>* storage =
   549         new _writer_bits::MapStorage<Node, Map>(map);
   550       _node_maps.push_back(std::make_pair(caption, storage));
   551       return *this;
   552     }
   553 
   554     /// \brief Node map writing rule
   555     ///
   556     /// Add a node map writing rule with specialized converter to the
   557     /// writer.
   558     template <typename Map, typename Converter>
   559     DigraphWriter& nodeMap(const std::string& caption, const Map& map,
   560                            const Converter& converter = Converter()) {
   561       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   562       _writer_bits::MapStorageBase<Node>* storage =
   563         new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
   564       _node_maps.push_back(std::make_pair(caption, storage));
   565       return *this;
   566     }
   567 
   568     /// \brief Arc map writing rule
   569     ///
   570     /// Add an arc map writing rule to the writer.
   571     template <typename Map>
   572     DigraphWriter& arcMap(const std::string& caption, const Map& map) {
   573       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   574       _writer_bits::MapStorageBase<Arc>* storage =
   575         new _writer_bits::MapStorage<Arc, Map>(map);
   576       _arc_maps.push_back(std::make_pair(caption, storage));
   577       return *this;
   578     }
   579 
   580     /// \brief Arc map writing rule
   581     ///
   582     /// Add an arc map writing rule with specialized converter to the
   583     /// writer.
   584     template <typename Map, typename Converter>
   585     DigraphWriter& arcMap(const std::string& caption, const Map& map,
   586                           const Converter& converter = Converter()) {
   587       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   588       _writer_bits::MapStorageBase<Arc>* storage =
   589         new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
   590       _arc_maps.push_back(std::make_pair(caption, storage));
   591       return *this;
   592     }
   593 
   594     /// \brief Attribute writing rule
   595     ///
   596     /// Add an attribute writing rule to the writer.
   597     template <typename Value>
   598     DigraphWriter& attribute(const std::string& caption, const Value& value) {
   599       _writer_bits::ValueStorageBase* storage =
   600         new _writer_bits::ValueStorage<Value>(value);
   601       _attributes.push_back(std::make_pair(caption, storage));
   602       return *this;
   603     }
   604 
   605     /// \brief Attribute writing rule
   606     ///
   607     /// Add an attribute writing rule with specialized converter to the
   608     /// writer.
   609     template <typename Value, typename Converter>
   610     DigraphWriter& attribute(const std::string& caption, const Value& value,
   611                              const Converter& converter = Converter()) {
   612       _writer_bits::ValueStorageBase* storage =
   613         new _writer_bits::ValueStorage<Value, Converter>(value, converter);
   614       _attributes.push_back(std::make_pair(caption, storage));
   615       return *this;
   616     }
   617 
   618     /// \brief Node writing rule
   619     ///
   620     /// Add a node writing rule to the writer.
   621     DigraphWriter& node(const std::string& caption, const Node& node) {
   622       typedef _writer_bits::MapLookUpConverter<Node> Converter;
   623       Converter converter(_node_index);
   624       _writer_bits::ValueStorageBase* storage =
   625         new _writer_bits::ValueStorage<Node, Converter>(node, converter);
   626       _attributes.push_back(std::make_pair(caption, storage));
   627       return *this;
   628     }
   629 
   630     /// \brief Arc writing rule
   631     ///
   632     /// Add an arc writing rule to writer.
   633     DigraphWriter& arc(const std::string& caption, const Arc& arc) {
   634       typedef _writer_bits::MapLookUpConverter<Arc> Converter;
   635       Converter converter(_arc_index);
   636       _writer_bits::ValueStorageBase* storage =
   637         new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
   638       _attributes.push_back(std::make_pair(caption, storage));
   639       return *this;
   640     }
   641 
   642     /// \name Section Captions
   643     /// @{
   644 
   645     /// \brief Add an additional caption to the \c \@nodes section
   646     ///
   647     /// Add an additional caption to the \c \@nodes section.
   648     DigraphWriter& nodes(const std::string& caption) {
   649       _nodes_caption = caption;
   650       return *this;
   651     }
   652 
   653     /// \brief Add an additional caption to the \c \@arcs section
   654     ///
   655     /// Add an additional caption to the \c \@arcs section.
   656     DigraphWriter& arcs(const std::string& caption) {
   657       _arcs_caption = caption;
   658       return *this;
   659     }
   660 
   661     /// \brief Add an additional caption to the \c \@attributes section
   662     ///
   663     /// Add an additional caption to the \c \@attributes section.
   664     DigraphWriter& attributes(const std::string& caption) {
   665       _attributes_caption = caption;
   666       return *this;
   667     }
   668 
   669     /// \name Skipping Section
   670     /// @{
   671 
   672     /// \brief Skip writing the node set
   673     ///
   674     /// The \c \@nodes section will not be written to the stream.
   675     DigraphWriter& skipNodes() {
   676       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
   677       _skip_nodes = true;
   678       return *this;
   679     }
   680 
   681     /// \brief Skip writing arc set
   682     ///
   683     /// The \c \@arcs section will not be written to the stream.
   684     DigraphWriter& skipArcs() {
   685       LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
   686       _skip_arcs = true;
   687       return *this;
   688     }
   689 
   690     /// @}
   691 
   692   private:
   693 
   694     void writeNodes() {
   695       _writer_bits::MapStorageBase<Node>* label = 0;
   696       for (typename NodeMaps::iterator it = _node_maps.begin();
   697            it != _node_maps.end(); ++it) {
   698         if (it->first == "label") {
   699           label = it->second;
   700           break;
   701         }
   702       }
   703 
   704       *_os << "@nodes";
   705       if (!_nodes_caption.empty()) {
   706         _writer_bits::writeToken(*_os << ' ', _nodes_caption);
   707       }
   708       *_os << std::endl;
   709 
   710       if (label == 0) {
   711         *_os << "label" << '\t';
   712       }
   713       for (typename NodeMaps::iterator it = _node_maps.begin();
   714            it != _node_maps.end(); ++it) {
   715         _writer_bits::writeToken(*_os, it->first) << '\t';
   716       }
   717       *_os << std::endl;
   718 
   719       std::vector<Node> nodes;
   720       for (NodeIt n(_digraph); n != INVALID; ++n) {
   721         nodes.push_back(n);
   722       }
   723 
   724       if (label == 0) {
   725         IdMap<DGR, Node> id_map(_digraph);
   726         _writer_bits::MapLess<IdMap<DGR, Node> > id_less(id_map);
   727         std::sort(nodes.begin(), nodes.end(), id_less);
   728       } else {
   729         label->sort(nodes);
   730       }
   731 
   732       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
   733         Node n = nodes[i];
   734         if (label == 0) {
   735           std::ostringstream os;
   736           os << _digraph.id(n);
   737           _writer_bits::writeToken(*_os, os.str());
   738           *_os << '\t';
   739           _node_index.insert(std::make_pair(n, os.str()));
   740         }
   741         for (typename NodeMaps::iterator it = _node_maps.begin();
   742              it != _node_maps.end(); ++it) {
   743           std::string value = it->second->get(n);
   744           _writer_bits::writeToken(*_os, value);
   745           if (it->first == "label") {
   746             _node_index.insert(std::make_pair(n, value));
   747           }
   748           *_os << '\t';
   749         }
   750         *_os << std::endl;
   751       }
   752     }
   753 
   754     void createNodeIndex() {
   755       _writer_bits::MapStorageBase<Node>* label = 0;
   756       for (typename NodeMaps::iterator it = _node_maps.begin();
   757            it != _node_maps.end(); ++it) {
   758         if (it->first == "label") {
   759           label = it->second;
   760           break;
   761         }
   762       }
   763 
   764       if (label == 0) {
   765         for (NodeIt n(_digraph); n != INVALID; ++n) {
   766           std::ostringstream os;
   767           os << _digraph.id(n);
   768           _node_index.insert(std::make_pair(n, os.str()));
   769         }
   770       } else {
   771         for (NodeIt n(_digraph); n != INVALID; ++n) {
   772           std::string value = label->get(n);
   773           _node_index.insert(std::make_pair(n, value));
   774         }
   775       }
   776     }
   777 
   778     void writeArcs() {
   779       _writer_bits::MapStorageBase<Arc>* label = 0;
   780       for (typename ArcMaps::iterator it = _arc_maps.begin();
   781            it != _arc_maps.end(); ++it) {
   782         if (it->first == "label") {
   783           label = it->second;
   784           break;
   785         }
   786       }
   787 
   788       *_os << "@arcs";
   789       if (!_arcs_caption.empty()) {
   790         _writer_bits::writeToken(*_os << ' ', _arcs_caption);
   791       }
   792       *_os << std::endl;
   793 
   794       *_os << '\t' << '\t';
   795       if (label == 0) {
   796         *_os << "label" << '\t';
   797       }
   798       for (typename ArcMaps::iterator it = _arc_maps.begin();
   799            it != _arc_maps.end(); ++it) {
   800         _writer_bits::writeToken(*_os, it->first) << '\t';
   801       }
   802       *_os << std::endl;
   803 
   804       std::vector<Arc> arcs;
   805       for (ArcIt n(_digraph); n != INVALID; ++n) {
   806         arcs.push_back(n);
   807       }
   808 
   809       if (label == 0) {
   810         IdMap<DGR, Arc> id_map(_digraph);
   811         _writer_bits::MapLess<IdMap<DGR, Arc> > id_less(id_map);
   812         std::sort(arcs.begin(), arcs.end(), id_less);
   813       } else {
   814         label->sort(arcs);
   815       }
   816 
   817       for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
   818         Arc a = arcs[i];
   819         _writer_bits::writeToken(*_os, _node_index.
   820                                  find(_digraph.source(a))->second);
   821         *_os << '\t';
   822         _writer_bits::writeToken(*_os, _node_index.
   823                                  find(_digraph.target(a))->second);
   824         *_os << '\t';
   825         if (label == 0) {
   826           std::ostringstream os;
   827           os << _digraph.id(a);
   828           _writer_bits::writeToken(*_os, os.str());
   829           *_os << '\t';
   830           _arc_index.insert(std::make_pair(a, os.str()));
   831         }
   832         for (typename ArcMaps::iterator it = _arc_maps.begin();
   833              it != _arc_maps.end(); ++it) {
   834           std::string value = it->second->get(a);
   835           _writer_bits::writeToken(*_os, value);
   836           if (it->first == "label") {
   837             _arc_index.insert(std::make_pair(a, value));
   838           }
   839           *_os << '\t';
   840         }
   841         *_os << std::endl;
   842       }
   843     }
   844 
   845     void createArcIndex() {
   846       _writer_bits::MapStorageBase<Arc>* label = 0;
   847       for (typename ArcMaps::iterator it = _arc_maps.begin();
   848            it != _arc_maps.end(); ++it) {
   849         if (it->first == "label") {
   850           label = it->second;
   851           break;
   852         }
   853       }
   854 
   855       if (label == 0) {
   856         for (ArcIt a(_digraph); a != INVALID; ++a) {
   857           std::ostringstream os;
   858           os << _digraph.id(a);
   859           _arc_index.insert(std::make_pair(a, os.str()));
   860         }
   861       } else {
   862         for (ArcIt a(_digraph); a != INVALID; ++a) {
   863           std::string value = label->get(a);
   864           _arc_index.insert(std::make_pair(a, value));
   865         }
   866       }
   867     }
   868 
   869     void writeAttributes() {
   870       if (_attributes.empty()) return;
   871       *_os << "@attributes";
   872       if (!_attributes_caption.empty()) {
   873         _writer_bits::writeToken(*_os << ' ', _attributes_caption);
   874       }
   875       *_os << std::endl;
   876       for (typename Attributes::iterator it = _attributes.begin();
   877            it != _attributes.end(); ++it) {
   878         _writer_bits::writeToken(*_os, it->first) << ' ';
   879         _writer_bits::writeToken(*_os, it->second->get());
   880         *_os << std::endl;
   881       }
   882     }
   883 
   884   public:
   885 
   886     /// \name Execution of the Writer
   887     /// @{
   888 
   889     /// \brief Start the batch processing
   890     ///
   891     /// This function starts the batch processing.
   892     void run() {
   893       if (!_skip_nodes) {
   894         writeNodes();
   895       } else {
   896         createNodeIndex();
   897       }
   898       if (!_skip_arcs) {
   899         writeArcs();
   900       } else {
   901         createArcIndex();
   902       }
   903       writeAttributes();
   904     }
   905 
   906     /// \brief Give back the stream of the writer
   907     ///
   908     /// Give back the stream of the writer.
   909     std::ostream& ostream() {
   910       return *_os;
   911     }
   912 
   913     /// @}
   914   };
   915 
   916   /// \ingroup lemon_io
   917   ///
   918   /// \brief Return a \ref DigraphWriter class
   919   ///
   920   /// This function just returns a \ref DigraphWriter class. 
   921   ///
   922   /// With this function a digraph can be write to a file or output
   923   /// stream in \ref lgf-format "LGF" format with several maps and
   924   /// attributes. For example, with the following code a network flow
   925   /// problem can be written to the standard output, i.e. a digraph
   926   /// with a \e capacity map on the arcs and \e source and \e target
   927   /// nodes:
   928   ///
   929   ///\code
   930   ///ListDigraph digraph;
   931   ///ListDigraph::ArcMap<int> cap(digraph);
   932   ///ListDigraph::Node src, trg;
   933   ///  // Setting the capacity map and source and target nodes
   934   ///digraphWriter(digraph, std::cout).
   935   ///  arcMap("capacity", cap).
   936   ///  node("source", src).
   937   ///  node("target", trg).
   938   ///  run();
   939   ///\endcode
   940   ///
   941   /// For a complete documentation, please see the \ref DigraphWriter
   942   /// class documentation.
   943   /// \warning Don't forget to put the \ref DigraphWriter::run() "run()"
   944   /// to the end of the parameter list.
   945   /// \relates DigraphWriter
   946   /// \sa digraphWriter(const TDGR& digraph, const std::string& fn)
   947   /// \sa digraphWriter(const TDGR& digraph, const char* fn)
   948   template <typename TDGR>
   949   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, std::ostream& os) {
   950     DigraphWriter<TDGR> tmp(digraph, os);
   951     return tmp;
   952   }
   953 
   954   /// \brief Return a \ref DigraphWriter class
   955   ///
   956   /// This function just returns a \ref DigraphWriter class.
   957   /// \relates DigraphWriter
   958   /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
   959   template <typename TDGR>
   960   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
   961                                     const std::string& fn) {
   962     DigraphWriter<TDGR> tmp(digraph, fn);
   963     return tmp;
   964   }
   965 
   966   /// \brief Return a \ref DigraphWriter class
   967   ///
   968   /// This function just returns a \ref DigraphWriter class.
   969   /// \relates DigraphWriter
   970   /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
   971   template <typename TDGR>
   972   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn) {
   973     DigraphWriter<TDGR> tmp(digraph, fn);
   974     return tmp;
   975   }
   976 
   977   template <typename GR>
   978   class GraphWriter;
   979 
   980   template <typename TGR>
   981   GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os = std::cout);
   982   template <typename TGR>
   983   GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn);
   984   template <typename TGR>
   985   GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn);
   986 
   987   /// \ingroup lemon_io
   988   ///
   989   /// \brief \ref lgf-format "LGF" writer for directed graphs
   990   ///
   991   /// This utility writes an \ref lgf-format "LGF" file.
   992   ///
   993   /// It can be used almost the same way as \c DigraphWriter.
   994   /// The only difference is that this class can handle edges and
   995   /// edge maps as well as arcs and arc maps.
   996   ///
   997   /// The arc maps are written into the file as two columns, the
   998   /// caption of the columns are the name of the map prefixed with \c
   999   /// '+' and \c '-'. The arcs are written into the \c \@attributes
  1000   /// section as a \c '+' or a \c '-' prefix (depends on the direction
  1001   /// of the arc) and the label of corresponding edge.
  1002   template <typename GR>
  1003   class GraphWriter {
  1004   public:
  1005 
  1006     typedef GR Graph;
  1007     TEMPLATE_GRAPH_TYPEDEFS(GR);
  1008 
  1009   private:
  1010 
  1011 
  1012     std::ostream* _os;
  1013     bool local_os;
  1014 
  1015     const GR& _graph;
  1016 
  1017     std::string _nodes_caption;
  1018     std::string _edges_caption;
  1019     std::string _attributes_caption;
  1020 
  1021     typedef std::map<Node, std::string> NodeIndex;
  1022     NodeIndex _node_index;
  1023     typedef std::map<Edge, std::string> EdgeIndex;
  1024     EdgeIndex _edge_index;
  1025 
  1026     typedef std::vector<std::pair<std::string,
  1027       _writer_bits::MapStorageBase<Node>* > > NodeMaps;
  1028     NodeMaps _node_maps;
  1029 
  1030     typedef std::vector<std::pair<std::string,
  1031       _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
  1032     EdgeMaps _edge_maps;
  1033 
  1034     typedef std::vector<std::pair<std::string,
  1035       _writer_bits::ValueStorageBase*> > Attributes;
  1036     Attributes _attributes;
  1037 
  1038     bool _skip_nodes;
  1039     bool _skip_edges;
  1040 
  1041   public:
  1042 
  1043     /// \brief Constructor
  1044     ///
  1045     /// Construct a directed graph writer, which writes to the given
  1046     /// output stream.
  1047     GraphWriter(const GR& graph, std::ostream& os = std::cout)
  1048       : _os(&os), local_os(false), _graph(graph),
  1049         _skip_nodes(false), _skip_edges(false) {}
  1050 
  1051     /// \brief Constructor
  1052     ///
  1053     /// Construct a directed graph writer, which writes to the given
  1054     /// output file.
  1055     GraphWriter(const GR& graph, const std::string& fn)
  1056       : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
  1057         _skip_nodes(false), _skip_edges(false) {
  1058       if (!(*_os)) {
  1059         delete _os;
  1060         throw IoError("Cannot write file", fn);
  1061       }
  1062     }
  1063 
  1064     /// \brief Constructor
  1065     ///
  1066     /// Construct a directed graph writer, which writes to the given
  1067     /// output file.
  1068     GraphWriter(const GR& graph, const char* fn)
  1069       : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
  1070         _skip_nodes(false), _skip_edges(false) {
  1071       if (!(*_os)) {
  1072         delete _os;
  1073         throw IoError("Cannot write file", fn);
  1074       }
  1075     }
  1076 
  1077     /// \brief Destructor
  1078     ~GraphWriter() {
  1079       for (typename NodeMaps::iterator it = _node_maps.begin();
  1080            it != _node_maps.end(); ++it) {
  1081         delete it->second;
  1082       }
  1083 
  1084       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1085            it != _edge_maps.end(); ++it) {
  1086         delete it->second;
  1087       }
  1088 
  1089       for (typename Attributes::iterator it = _attributes.begin();
  1090            it != _attributes.end(); ++it) {
  1091         delete it->second;
  1092       }
  1093 
  1094       if (local_os) {
  1095         delete _os;
  1096       }
  1097     }
  1098 
  1099   private:
  1100 
  1101     template <typename TGR>
  1102     friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
  1103     template <typename TGR>
  1104     friend GraphWriter<TGR> graphWriter(const TGR& graph, 
  1105                                         const std::string& fn);
  1106     template <typename TGR>
  1107     friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn);
  1108     
  1109     GraphWriter(GraphWriter& other)
  1110       : _os(other._os), local_os(other.local_os), _graph(other._graph),
  1111         _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1112 
  1113       other._os = 0;
  1114       other.local_os = false;
  1115 
  1116       _node_index.swap(other._node_index);
  1117       _edge_index.swap(other._edge_index);
  1118 
  1119       _node_maps.swap(other._node_maps);
  1120       _edge_maps.swap(other._edge_maps);
  1121       _attributes.swap(other._attributes);
  1122 
  1123       _nodes_caption = other._nodes_caption;
  1124       _edges_caption = other._edges_caption;
  1125       _attributes_caption = other._attributes_caption;
  1126     }
  1127 
  1128     GraphWriter& operator=(const GraphWriter&);
  1129 
  1130   public:
  1131 
  1132     /// \name Writing Rules
  1133     /// @{
  1134 
  1135     /// \brief Node map writing rule
  1136     ///
  1137     /// Add a node map writing rule to the writer.
  1138     template <typename Map>
  1139     GraphWriter& nodeMap(const std::string& caption, const Map& map) {
  1140       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1141       _writer_bits::MapStorageBase<Node>* storage =
  1142         new _writer_bits::MapStorage<Node, Map>(map);
  1143       _node_maps.push_back(std::make_pair(caption, storage));
  1144       return *this;
  1145     }
  1146 
  1147     /// \brief Node map writing rule
  1148     ///
  1149     /// Add a node map writing rule with specialized converter to the
  1150     /// writer.
  1151     template <typename Map, typename Converter>
  1152     GraphWriter& nodeMap(const std::string& caption, const Map& map,
  1153                            const Converter& converter = Converter()) {
  1154       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1155       _writer_bits::MapStorageBase<Node>* storage =
  1156         new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
  1157       _node_maps.push_back(std::make_pair(caption, storage));
  1158       return *this;
  1159     }
  1160 
  1161     /// \brief Edge map writing rule
  1162     ///
  1163     /// Add an edge map writing rule to the writer.
  1164     template <typename Map>
  1165     GraphWriter& edgeMap(const std::string& caption, const Map& map) {
  1166       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1167       _writer_bits::MapStorageBase<Edge>* storage =
  1168         new _writer_bits::MapStorage<Edge, Map>(map);
  1169       _edge_maps.push_back(std::make_pair(caption, storage));
  1170       return *this;
  1171     }
  1172 
  1173     /// \brief Edge map writing rule
  1174     ///
  1175     /// Add an edge map writing rule with specialized converter to the
  1176     /// writer.
  1177     template <typename Map, typename Converter>
  1178     GraphWriter& edgeMap(const std::string& caption, const Map& map,
  1179                           const Converter& converter = Converter()) {
  1180       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1181       _writer_bits::MapStorageBase<Edge>* storage =
  1182         new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1183       _edge_maps.push_back(std::make_pair(caption, storage));
  1184       return *this;
  1185     }
  1186 
  1187     /// \brief Arc map writing rule
  1188     ///
  1189     /// Add an arc map writing rule to the writer.
  1190     template <typename Map>
  1191     GraphWriter& arcMap(const std::string& caption, const Map& map) {
  1192       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1193       _writer_bits::MapStorageBase<Edge>* forward_storage =
  1194         new _writer_bits::GraphArcMapStorage<GR, true, Map>(_graph, map);
  1195       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1196       _writer_bits::MapStorageBase<Edge>* backward_storage =
  1197         new _writer_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
  1198       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1199       return *this;
  1200     }
  1201 
  1202     /// \brief Arc map writing rule
  1203     ///
  1204     /// Add an arc map writing rule with specialized converter to the
  1205     /// writer.
  1206     template <typename Map, typename Converter>
  1207     GraphWriter& arcMap(const std::string& caption, const Map& map,
  1208                           const Converter& converter = Converter()) {
  1209       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1210       _writer_bits::MapStorageBase<Edge>* forward_storage =
  1211         new _writer_bits::GraphArcMapStorage<GR, true, Map, Converter>
  1212         (_graph, map, converter);
  1213       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1214       _writer_bits::MapStorageBase<Edge>* backward_storage =
  1215         new _writer_bits::GraphArcMapStorage<GR, false, Map, Converter>
  1216         (_graph, map, converter);
  1217       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1218       return *this;
  1219     }
  1220 
  1221     /// \brief Attribute writing rule
  1222     ///
  1223     /// Add an attribute writing rule to the writer.
  1224     template <typename Value>
  1225     GraphWriter& attribute(const std::string& caption, const Value& value) {
  1226       _writer_bits::ValueStorageBase* storage =
  1227         new _writer_bits::ValueStorage<Value>(value);
  1228       _attributes.push_back(std::make_pair(caption, storage));
  1229       return *this;
  1230     }
  1231 
  1232     /// \brief Attribute writing rule
  1233     ///
  1234     /// Add an attribute writing rule with specialized converter to the
  1235     /// writer.
  1236     template <typename Value, typename Converter>
  1237     GraphWriter& attribute(const std::string& caption, const Value& value,
  1238                              const Converter& converter = Converter()) {
  1239       _writer_bits::ValueStorageBase* storage =
  1240         new _writer_bits::ValueStorage<Value, Converter>(value, converter);
  1241       _attributes.push_back(std::make_pair(caption, storage));
  1242       return *this;
  1243     }
  1244 
  1245     /// \brief Node writing rule
  1246     ///
  1247     /// Add a node writing rule to the writer.
  1248     GraphWriter& node(const std::string& caption, const Node& node) {
  1249       typedef _writer_bits::MapLookUpConverter<Node> Converter;
  1250       Converter converter(_node_index);
  1251       _writer_bits::ValueStorageBase* storage =
  1252         new _writer_bits::ValueStorage<Node, Converter>(node, converter);
  1253       _attributes.push_back(std::make_pair(caption, storage));
  1254       return *this;
  1255     }
  1256 
  1257     /// \brief Edge writing rule
  1258     ///
  1259     /// Add an edge writing rule to writer.
  1260     GraphWriter& edge(const std::string& caption, const Edge& edge) {
  1261       typedef _writer_bits::MapLookUpConverter<Edge> Converter;
  1262       Converter converter(_edge_index);
  1263       _writer_bits::ValueStorageBase* storage =
  1264         new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
  1265       _attributes.push_back(std::make_pair(caption, storage));
  1266       return *this;
  1267     }
  1268 
  1269     /// \brief Arc writing rule
  1270     ///
  1271     /// Add an arc writing rule to writer.
  1272     GraphWriter& arc(const std::string& caption, const Arc& arc) {
  1273       typedef _writer_bits::GraphArcLookUpConverter<GR> Converter;
  1274       Converter converter(_graph, _edge_index);
  1275       _writer_bits::ValueStorageBase* storage =
  1276         new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
  1277       _attributes.push_back(std::make_pair(caption, storage));
  1278       return *this;
  1279     }
  1280 
  1281     /// \name Section Captions
  1282     /// @{
  1283 
  1284     /// \brief Add an additional caption to the \c \@nodes section
  1285     ///
  1286     /// Add an additional caption to the \c \@nodes section.
  1287     GraphWriter& nodes(const std::string& caption) {
  1288       _nodes_caption = caption;
  1289       return *this;
  1290     }
  1291 
  1292     /// \brief Add an additional caption to the \c \@arcs section
  1293     ///
  1294     /// Add an additional caption to the \c \@arcs section.
  1295     GraphWriter& edges(const std::string& caption) {
  1296       _edges_caption = caption;
  1297       return *this;
  1298     }
  1299 
  1300     /// \brief Add an additional caption to the \c \@attributes section
  1301     ///
  1302     /// Add an additional caption to the \c \@attributes section.
  1303     GraphWriter& attributes(const std::string& caption) {
  1304       _attributes_caption = caption;
  1305       return *this;
  1306     }
  1307 
  1308     /// \name Skipping Section
  1309     /// @{
  1310 
  1311     /// \brief Skip writing the node set
  1312     ///
  1313     /// The \c \@nodes section will not be written to the stream.
  1314     GraphWriter& skipNodes() {
  1315       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
  1316       _skip_nodes = true;
  1317       return *this;
  1318     }
  1319 
  1320     /// \brief Skip writing edge set
  1321     ///
  1322     /// The \c \@edges section will not be written to the stream.
  1323     GraphWriter& skipEdges() {
  1324       LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
  1325       _skip_edges = true;
  1326       return *this;
  1327     }
  1328 
  1329     /// @}
  1330 
  1331   private:
  1332 
  1333     void writeNodes() {
  1334       _writer_bits::MapStorageBase<Node>* label = 0;
  1335       for (typename NodeMaps::iterator it = _node_maps.begin();
  1336            it != _node_maps.end(); ++it) {
  1337         if (it->first == "label") {
  1338           label = it->second;
  1339           break;
  1340         }
  1341       }
  1342 
  1343       *_os << "@nodes";
  1344       if (!_nodes_caption.empty()) {
  1345         _writer_bits::writeToken(*_os << ' ', _nodes_caption);
  1346       }
  1347       *_os << std::endl;
  1348 
  1349       if (label == 0) {
  1350         *_os << "label" << '\t';
  1351       }
  1352       for (typename NodeMaps::iterator it = _node_maps.begin();
  1353            it != _node_maps.end(); ++it) {
  1354         _writer_bits::writeToken(*_os, it->first) << '\t';
  1355       }
  1356       *_os << std::endl;
  1357 
  1358       std::vector<Node> nodes;
  1359       for (NodeIt n(_graph); n != INVALID; ++n) {
  1360         nodes.push_back(n);
  1361       }
  1362 
  1363       if (label == 0) {
  1364         IdMap<GR, Node> id_map(_graph);
  1365         _writer_bits::MapLess<IdMap<GR, Node> > id_less(id_map);
  1366         std::sort(nodes.begin(), nodes.end(), id_less);
  1367       } else {
  1368         label->sort(nodes);
  1369       }
  1370 
  1371       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
  1372         Node n = nodes[i];
  1373         if (label == 0) {
  1374           std::ostringstream os;
  1375           os << _graph.id(n);
  1376           _writer_bits::writeToken(*_os, os.str());
  1377           *_os << '\t';
  1378           _node_index.insert(std::make_pair(n, os.str()));
  1379         }
  1380         for (typename NodeMaps::iterator it = _node_maps.begin();
  1381              it != _node_maps.end(); ++it) {
  1382           std::string value = it->second->get(n);
  1383           _writer_bits::writeToken(*_os, value);
  1384           if (it->first == "label") {
  1385             _node_index.insert(std::make_pair(n, value));
  1386           }
  1387           *_os << '\t';
  1388         }
  1389         *_os << std::endl;
  1390       }
  1391     }
  1392 
  1393     void createNodeIndex() {
  1394       _writer_bits::MapStorageBase<Node>* label = 0;
  1395       for (typename NodeMaps::iterator it = _node_maps.begin();
  1396            it != _node_maps.end(); ++it) {
  1397         if (it->first == "label") {
  1398           label = it->second;
  1399           break;
  1400         }
  1401       }
  1402 
  1403       if (label == 0) {
  1404         for (NodeIt n(_graph); n != INVALID; ++n) {
  1405           std::ostringstream os;
  1406           os << _graph.id(n);
  1407           _node_index.insert(std::make_pair(n, os.str()));
  1408         }
  1409       } else {
  1410         for (NodeIt n(_graph); n != INVALID; ++n) {
  1411           std::string value = label->get(n);
  1412           _node_index.insert(std::make_pair(n, value));
  1413         }
  1414       }
  1415     }
  1416 
  1417     void writeEdges() {
  1418       _writer_bits::MapStorageBase<Edge>* label = 0;
  1419       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1420            it != _edge_maps.end(); ++it) {
  1421         if (it->first == "label") {
  1422           label = it->second;
  1423           break;
  1424         }
  1425       }
  1426 
  1427       *_os << "@edges";
  1428       if (!_edges_caption.empty()) {
  1429         _writer_bits::writeToken(*_os << ' ', _edges_caption);
  1430       }
  1431       *_os << std::endl;
  1432 
  1433       *_os << '\t' << '\t';
  1434       if (label == 0) {
  1435         *_os << "label" << '\t';
  1436       }
  1437       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1438            it != _edge_maps.end(); ++it) {
  1439         _writer_bits::writeToken(*_os, it->first) << '\t';
  1440       }
  1441       *_os << std::endl;
  1442 
  1443       std::vector<Edge> edges;
  1444       for (EdgeIt n(_graph); n != INVALID; ++n) {
  1445         edges.push_back(n);
  1446       }
  1447 
  1448       if (label == 0) {
  1449         IdMap<GR, Edge> id_map(_graph);
  1450         _writer_bits::MapLess<IdMap<GR, Edge> > id_less(id_map);
  1451         std::sort(edges.begin(), edges.end(), id_less);
  1452       } else {
  1453         label->sort(edges);
  1454       }
  1455 
  1456       for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
  1457         Edge e = edges[i];
  1458         _writer_bits::writeToken(*_os, _node_index.
  1459                                  find(_graph.u(e))->second);
  1460         *_os << '\t';
  1461         _writer_bits::writeToken(*_os, _node_index.
  1462                                  find(_graph.v(e))->second);
  1463         *_os << '\t';
  1464         if (label == 0) {
  1465           std::ostringstream os;
  1466           os << _graph.id(e);
  1467           _writer_bits::writeToken(*_os, os.str());
  1468           *_os << '\t';
  1469           _edge_index.insert(std::make_pair(e, os.str()));
  1470         }
  1471         for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1472              it != _edge_maps.end(); ++it) {
  1473           std::string value = it->second->get(e);
  1474           _writer_bits::writeToken(*_os, value);
  1475           if (it->first == "label") {
  1476             _edge_index.insert(std::make_pair(e, value));
  1477           }
  1478           *_os << '\t';
  1479         }
  1480         *_os << std::endl;
  1481       }
  1482     }
  1483 
  1484     void createEdgeIndex() {
  1485       _writer_bits::MapStorageBase<Edge>* label = 0;
  1486       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1487            it != _edge_maps.end(); ++it) {
  1488         if (it->first == "label") {
  1489           label = it->second;
  1490           break;
  1491         }
  1492       }
  1493 
  1494       if (label == 0) {
  1495         for (EdgeIt e(_graph); e != INVALID; ++e) {
  1496           std::ostringstream os;
  1497           os << _graph.id(e);
  1498           _edge_index.insert(std::make_pair(e, os.str()));
  1499         }
  1500       } else {
  1501         for (EdgeIt e(_graph); e != INVALID; ++e) {
  1502           std::string value = label->get(e);
  1503           _edge_index.insert(std::make_pair(e, value));
  1504         }
  1505       }
  1506     }
  1507 
  1508     void writeAttributes() {
  1509       if (_attributes.empty()) return;
  1510       *_os << "@attributes";
  1511       if (!_attributes_caption.empty()) {
  1512         _writer_bits::writeToken(*_os << ' ', _attributes_caption);
  1513       }
  1514       *_os << std::endl;
  1515       for (typename Attributes::iterator it = _attributes.begin();
  1516            it != _attributes.end(); ++it) {
  1517         _writer_bits::writeToken(*_os, it->first) << ' ';
  1518         _writer_bits::writeToken(*_os, it->second->get());
  1519         *_os << std::endl;
  1520       }
  1521     }
  1522 
  1523   public:
  1524 
  1525     /// \name Execution of the Writer
  1526     /// @{
  1527 
  1528     /// \brief Start the batch processing
  1529     ///
  1530     /// This function starts the batch processing.
  1531     void run() {
  1532       if (!_skip_nodes) {
  1533         writeNodes();
  1534       } else {
  1535         createNodeIndex();
  1536       }
  1537       if (!_skip_edges) {
  1538         writeEdges();
  1539       } else {
  1540         createEdgeIndex();
  1541       }
  1542       writeAttributes();
  1543     }
  1544 
  1545     /// \brief Give back the stream of the writer
  1546     ///
  1547     /// Give back the stream of the writer
  1548     std::ostream& ostream() {
  1549       return *_os;
  1550     }
  1551 
  1552     /// @}
  1553   };
  1554 
  1555   /// \ingroup lemon_io
  1556   ///
  1557   /// \brief Return a \ref GraphWriter class
  1558   ///
  1559   /// This function just returns a \ref GraphWriter class. 
  1560   ///
  1561   /// With this function a graph can be write to a file or output
  1562   /// stream in \ref lgf-format "LGF" format with several maps and
  1563   /// attributes. For example, with the following code a weighted
  1564   /// matching problem can be written to the standard output, i.e. a
  1565   /// graph with a \e weight map on the edges:
  1566   ///
  1567   ///\code
  1568   ///ListGraph graph;
  1569   ///ListGraph::EdgeMap<int> weight(graph);
  1570   ///  // Setting the weight map
  1571   ///graphWriter(graph, std::cout).
  1572   ///  edgeMap("weight", weight).
  1573   ///  run();
  1574   ///\endcode
  1575   ///
  1576   /// For a complete documentation, please see the \ref GraphWriter
  1577   /// class documentation.
  1578   /// \warning Don't forget to put the \ref GraphWriter::run() "run()"
  1579   /// to the end of the parameter list.
  1580   /// \relates GraphWriter
  1581   /// \sa graphWriter(const TGR& graph, const std::string& fn)
  1582   /// \sa graphWriter(const TGR& graph, const char* fn)
  1583   template <typename TGR>
  1584   GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os) {
  1585     GraphWriter<TGR> tmp(graph, os);
  1586     return tmp;
  1587   }
  1588 
  1589   /// \brief Return a \ref GraphWriter class
  1590   ///
  1591   /// This function just returns a \ref GraphWriter class.
  1592   /// \relates GraphWriter
  1593   /// \sa graphWriter(const TGR& graph, std::ostream& os)
  1594   template <typename TGR>
  1595   GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn) {
  1596     GraphWriter<TGR> tmp(graph, fn);
  1597     return tmp;
  1598   }
  1599 
  1600   /// \brief Return a \ref GraphWriter class
  1601   ///
  1602   /// This function just returns a \ref GraphWriter class.
  1603   /// \relates GraphWriter
  1604   /// \sa graphWriter(const TGR& graph, std::ostream& os)
  1605   template <typename TGR>
  1606   GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
  1607     GraphWriter<TGR> tmp(graph, fn);
  1608     return tmp;
  1609   }
  1610 
  1611   class SectionWriter;
  1612 
  1613   SectionWriter sectionWriter(std::istream& is);
  1614   SectionWriter sectionWriter(const std::string& fn);
  1615   SectionWriter sectionWriter(const char* fn);
  1616 
  1617   /// \ingroup lemon_io
  1618   ///
  1619   /// \brief Section writer class
  1620   ///
  1621   /// In the \ref lgf-format "LGF" file extra sections can be placed,
  1622   /// which contain any data in arbitrary format. Such sections can be
  1623   /// written with this class. A writing rule can be added to the
  1624   /// class with two different functions. With the \c sectionLines()
  1625   /// function a generator can write the section line-by-line, while
  1626   /// with the \c sectionStream() member the section can be written to
  1627   /// an output stream.
  1628   class SectionWriter {
  1629   private:
  1630 
  1631     std::ostream* _os;
  1632     bool local_os;
  1633 
  1634     typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
  1635     Sections;
  1636 
  1637     Sections _sections;
  1638 
  1639   public:
  1640 
  1641     /// \brief Constructor
  1642     ///
  1643     /// Construct a section writer, which writes to the given output
  1644     /// stream.
  1645     SectionWriter(std::ostream& os)
  1646       : _os(&os), local_os(false) {}
  1647 
  1648     /// \brief Constructor
  1649     ///
  1650     /// Construct a section writer, which writes into the given file.
  1651     SectionWriter(const std::string& fn)
  1652       : _os(new std::ofstream(fn.c_str())), local_os(true) {
  1653       if (!(*_os)) {
  1654         delete _os;
  1655         throw IoError("Cannot write file", fn);
  1656       }
  1657     }
  1658 
  1659     /// \brief Constructor
  1660     ///
  1661     /// Construct a section writer, which writes into the given file.
  1662     SectionWriter(const char* fn)
  1663       : _os(new std::ofstream(fn)), local_os(true) {
  1664       if (!(*_os)) {
  1665         delete _os;
  1666         throw IoError("Cannot write file", fn);
  1667       }
  1668     }
  1669 
  1670     /// \brief Destructor
  1671     ~SectionWriter() {
  1672       for (Sections::iterator it = _sections.begin();
  1673            it != _sections.end(); ++it) {
  1674         delete it->second;
  1675       }
  1676 
  1677       if (local_os) {
  1678         delete _os;
  1679       }
  1680 
  1681     }
  1682 
  1683   private:
  1684 
  1685     friend SectionWriter sectionWriter(std::ostream& os);
  1686     friend SectionWriter sectionWriter(const std::string& fn);
  1687     friend SectionWriter sectionWriter(const char* fn);
  1688 
  1689     SectionWriter(SectionWriter& other)
  1690       : _os(other._os), local_os(other.local_os) {
  1691 
  1692       other._os = 0;
  1693       other.local_os = false;
  1694 
  1695       _sections.swap(other._sections);
  1696     }
  1697 
  1698     SectionWriter& operator=(const SectionWriter&);
  1699 
  1700   public:
  1701 
  1702     /// \name Section Writers
  1703     /// @{
  1704 
  1705     /// \brief Add a section writer with line oriented writing
  1706     ///
  1707     /// The first parameter is the type descriptor of the section, the
  1708     /// second is a generator with std::string values. At the writing
  1709     /// process, the returned \c std::string will be written into the
  1710     /// output file until it is an empty string.
  1711     ///
  1712     /// For example, an integer vector is written into a section.
  1713     ///\code
  1714     ///  @numbers
  1715     ///  12 45 23 78
  1716     ///  4 28 38 28
  1717     ///  23 6 16
  1718     ///\endcode
  1719     ///
  1720     /// The generator is implemented as a struct.
  1721     ///\code
  1722     ///  struct NumberSection {
  1723     ///    std::vector<int>::const_iterator _it, _end;
  1724     ///    NumberSection(const std::vector<int>& data)
  1725     ///      : _it(data.begin()), _end(data.end()) {}
  1726     ///    std::string operator()() {
  1727     ///      int rem_in_line = 4;
  1728     ///      std::ostringstream ls;
  1729     ///      while (rem_in_line > 0 && _it != _end) {
  1730     ///        ls << *(_it++) << ' ';
  1731     ///        --rem_in_line;
  1732     ///      }
  1733     ///      return ls.str();
  1734     ///    }
  1735     ///  };
  1736     ///
  1737     ///  // ...
  1738     ///
  1739     ///  writer.sectionLines("numbers", NumberSection(vec));
  1740     ///\endcode
  1741     template <typename Functor>
  1742     SectionWriter& sectionLines(const std::string& type, Functor functor) {
  1743       LEMON_ASSERT(!type.empty(), "Type is empty.");
  1744       _sections.push_back(std::make_pair(type,
  1745         new _writer_bits::LineSection<Functor>(functor)));
  1746       return *this;
  1747     }
  1748 
  1749 
  1750     /// \brief Add a section writer with stream oriented writing
  1751     ///
  1752     /// The first parameter is the type of the section, the second is
  1753     /// a functor, which takes a \c std::ostream& parameter. The
  1754     /// functor writes the section to the output stream.
  1755     /// \warning The last line must be closed with end-line character.
  1756     template <typename Functor>
  1757     SectionWriter& sectionStream(const std::string& type, Functor functor) {
  1758       LEMON_ASSERT(!type.empty(), "Type is empty.");
  1759       _sections.push_back(std::make_pair(type,
  1760          new _writer_bits::StreamSection<Functor>(functor)));
  1761       return *this;
  1762     }
  1763 
  1764     /// @}
  1765 
  1766   public:
  1767 
  1768 
  1769     /// \name Execution of the Writer
  1770     /// @{
  1771 
  1772     /// \brief Start the batch processing
  1773     ///
  1774     /// This function starts the batch processing.
  1775     void run() {
  1776 
  1777       LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");
  1778 
  1779       for (Sections::iterator it = _sections.begin();
  1780            it != _sections.end(); ++it) {
  1781         (*_os) << '@' << it->first << std::endl;
  1782         it->second->process(*_os);
  1783       }
  1784     }
  1785 
  1786     /// \brief Give back the stream of the writer
  1787     ///
  1788     /// Returns the stream of the writer
  1789     std::ostream& ostream() {
  1790       return *_os;
  1791     }
  1792 
  1793     /// @}
  1794 
  1795   };
  1796 
  1797   /// \ingroup lemon_io
  1798   ///
  1799   /// \brief Return a \ref SectionWriter class
  1800   ///
  1801   /// This function just returns a \ref SectionWriter class.
  1802   ///
  1803   /// Please see SectionWriter documentation about the custom section
  1804   /// output.
  1805   ///
  1806   /// \relates SectionWriter
  1807   /// \sa sectionWriter(const std::string& fn)
  1808   /// \sa sectionWriter(const char *fn)
  1809   inline SectionWriter sectionWriter(std::ostream& os) {
  1810     SectionWriter tmp(os);
  1811     return tmp;
  1812   }
  1813 
  1814   /// \brief Return a \ref SectionWriter class
  1815   ///
  1816   /// This function just returns a \ref SectionWriter class.
  1817   /// \relates SectionWriter
  1818   /// \sa sectionWriter(std::ostream& os)
  1819   inline SectionWriter sectionWriter(const std::string& fn) {
  1820     SectionWriter tmp(fn);
  1821     return tmp;
  1822   }
  1823 
  1824   /// \brief Return a \ref SectionWriter class
  1825   ///
  1826   /// This function just returns a \ref SectionWriter class.
  1827   /// \relates SectionWriter
  1828   /// \sa sectionWriter(std::ostream& os)
  1829   inline SectionWriter sectionWriter(const char* fn) {
  1830     SectionWriter tmp(fn);
  1831     return tmp;
  1832   }
  1833 }
  1834 
  1835 #endif