COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/lgf_writer.h @ 191:abc5b9d0c67e

Last change on this file since 191:abc5b9d0c67e was 190:1e6af6f0843c, checked in by Balazs Dezso <deba@…>, 16 years ago

Move to private copy constrcutors

File size: 40.9 KB
Line 
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
39namespace 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 _Graph, bool _dir, typename _Map>
75    class GraphArcMapLess {
76    public:
77      typedef _Map Map;
78      typedef _Graph Graph;
79      typedef typename Graph::Edge Item;
80
81    private:
82      const Graph& _graph;
83      const Map& _map;
84     
85    public:
86      GraphArcMapLess(const Graph& graph, const Map& map)
87        : _graph(graph), _map(map) {}
88
89      bool operator()(const Item& left, const Item& right) {
90        return _map[_graph.direct(left, _dir)] <
91          _map[_graph.direct(right, _dir)];
92      }
93    };
94
95    template <typename _Item>   
96    class MapStorageBase {
97    public:
98      typedef _Item Item;
99
100    public:
101      MapStorageBase() {}
102      virtual ~MapStorageBase() {}
103
104      virtual std::string get(const Item& item) = 0;
105      virtual void sort(std::vector<Item>&) = 0;
106    };
107
108    template <typename _Item, typename _Map,
109              typename _Converter = DefaultConverter<typename _Map::Value> >
110    class MapStorage : public MapStorageBase<_Item> {
111    public:
112      typedef _Map Map;
113      typedef _Converter Converter;
114      typedef _Item Item;
115     
116    private:
117      const Map& _map;
118      Converter _converter;
119
120    public:
121      MapStorage(const Map& map, const Converter& converter = Converter())
122        : _map(map), _converter(converter) {}
123      virtual ~MapStorage() {}
124
125      virtual std::string get(const Item& item) {
126        return _converter(_map[item]);
127      }
128      virtual void sort(std::vector<Item>& items) {
129        MapLess<Map> less(_map);
130        std::sort(items.begin(), items.end(), less);
131      }
132    };
133
134    template <typename _Graph, bool _dir, typename _Map,
135              typename _Converter = DefaultConverter<typename _Map::Value> >
136    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
137    public:
138      typedef _Map Map;
139      typedef _Converter Converter;
140      typedef _Graph Graph;
141      typedef typename Graph::Edge Item;
142      static const bool dir = _dir;
143     
144    private:
145      const Graph& _graph;
146      const Map& _map;
147      Converter _converter;
148
149    public:
150      GraphArcMapStorage(const Graph& graph, const Map& map, 
151                         const Converter& converter = Converter())
152        : _graph(graph), _map(map), _converter(converter) {}
153      virtual ~GraphArcMapStorage() {}
154
155      virtual std::string get(const Item& item) {
156        return _converter(_map[_graph.direct(item, dir)]);
157      }
158      virtual void sort(std::vector<Item>& items) {
159        GraphArcMapLess<Graph, dir, Map> less(_graph, _map);
160        std::sort(items.begin(), items.end(), less);
161      }
162    };
163
164    class ValueStorageBase {
165    public:
166      ValueStorageBase() {}
167      virtual ~ValueStorageBase() {}
168
169      virtual std::string get() = 0;     
170    };
171
172    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
173    class ValueStorage : public ValueStorageBase {
174    public:
175      typedef _Value Value;
176      typedef _Converter Converter;
177
178    private:
179      const Value& _value;
180      Converter _converter;
181
182    public:
183      ValueStorage(const Value& value, const Converter& converter = Converter())
184        : _value(value), _converter(converter) {}
185
186      virtual std::string get() {
187        return _converter(_value);
188      }
189    };
190
191    template <typename Value>
192    struct MapLookUpConverter {
193      const std::map<Value, std::string>& _map;
194     
195      MapLookUpConverter(const std::map<Value, std::string>& map)
196        : _map(map) {}
197     
198      std::string operator()(const Value& str) {
199        typename std::map<Value, std::string>::const_iterator it =
200          _map.find(str);
201        if (it == _map.end()) {
202          throw DataFormatError("Item not found");
203        }
204        return it->second;
205      }
206    };
207
208    template <typename Graph>
209    struct GraphArcLookUpConverter {
210      const Graph& _graph;
211      const std::map<typename Graph::Edge, std::string>& _map;
212     
213      GraphArcLookUpConverter(const Graph& graph,
214                              const std::map<typename Graph::Edge,
215                                             std::string>& map)
216        : _graph(graph), _map(map) {}
217     
218      std::string operator()(const typename Graph::Arc& val) {
219        typename std::map<typename Graph::Edge, std::string>
220          ::const_iterator it = _map.find(val);
221        if (it == _map.end()) {
222          throw DataFormatError("Item not found");
223        }
224        return (_graph.direction(val) ? '+' : '-') + it->second;
225      }
226    };
227
228    bool isWhiteSpace(char c) {
229      return c == ' ' || c == '\t' || c == '\v' ||
230        c == '\n' || c == '\r' || c == '\f';
231    }
232
233    bool isEscaped(char c) {
234      return c == '\\' || c == '\"' || c == '\'' ||
235        c == '\a' || c == '\b';
236    }
237
238    static void writeEscape(std::ostream& os, char c) {
239      switch (c) {
240      case '\\':
241        os << "\\\\";
242        return;
243      case '\"':
244        os << "\\\"";
245        return;
246      case '\a':
247        os << "\\a";
248        return;
249      case '\b':
250        os << "\\b";
251        return;
252      case '\f':
253        os << "\\f";
254        return;
255      case '\r':
256        os << "\\r";
257        return;
258      case '\n':
259        os << "\\n";
260        return;
261      case '\t':
262        os << "\\t";
263        return;
264      case '\v':
265        os << "\\v";
266        return;
267      default:
268        if (c < 0x20) {
269          std::ios::fmtflags flags = os.flags();
270          os << '\\' << std::oct << static_cast<int>(c);
271          os.flags(flags);
272        } else {
273          os << c;
274        }
275        return;
276      }     
277    }
278
279    bool requireEscape(const std::string& str) {
280      if (str.empty() || str[0] == '@') return true;
281      std::istringstream is(str);
282      char c;
283      while (is.get(c)) {
284        if (isWhiteSpace(c) || isEscaped(c)) {
285          return true;
286        }
287      }
288      return false;
289    }
290   
291    std::ostream& writeToken(std::ostream& os, const std::string& str) {
292
293      if (requireEscape(str)) {
294        os << '\"';
295        for (std::string::const_iterator it = str.begin();
296             it != str.end(); ++it) {
297          writeEscape(os, *it);
298        }       
299        os << '\"';
300      } else {
301        os << str;
302      }
303      return os;
304    }
305
306  }
307
308  template <typename Digraph>
309  class DigraphWriter;
310
311  template <typename Digraph>
312  DigraphWriter<Digraph> digraphWriter(std::ostream& os,
313                                       const Digraph& digraph);
314
315  template <typename Digraph>
316  DigraphWriter<Digraph> digraphWriter(const std::string& fn,
317                                       const Digraph& digraph);
318
319  template <typename Digraph>
320  DigraphWriter<Digraph> digraphWriter(const char *fn,
321                                       const Digraph& digraph);
322 
323  /// \ingroup lemon_io
324  /// 
325  /// \brief LGF writer for directed graphs
326  ///
327  /// This utility writes an \ref lgf-format "LGF" file.
328  ///
329  /// The writing method does a batch processing. The user creates a
330  /// writer object, then various writing rules can be added to the
331  /// writer, and eventually the writing is executed with the \c run()
332  /// member function. A map writing rule can be added to the writer
333  /// with the \c nodeMap() or \c arcMap() members. An optional
334  /// converter parameter can also be added as a standard functor
335  /// converting from the value type of the map to std::string. If it
336  /// is set, it will determine how the map's value type is written to
337  /// the output stream. If the functor is not set, then a default
338  /// conversion will be used. The \c attribute(), \c node() and \c
339  /// arc() functions are used to add attribute writing rules.
340  ///
341  ///\code
342  ///     DigraphWriter<Digraph>(std::cout, digraph).
343  ///       nodeMap("coordinates", coord_map).
344  ///       nodeMap("size", size).
345  ///       nodeMap("title", title).
346  ///       arcMap("capacity", cap_map).
347  ///       node("source", src).
348  ///       node("target", trg).
349  ///       attribute("caption", caption).
350  ///       run();
351  ///\endcode
352  ///
353  ///
354  /// By default, the writer does not write additional captions to the
355  /// sections, but they can be give as an optional parameter of
356  /// the \c nodes(), \c arcs() or \c
357  /// attributes() functions.
358  ///
359  /// The \c skipNodes() and \c skipArcs() functions forbid the
360  /// writing of the sections. If two arc sections should be written
361  /// to the output, it can be done in two passes, the first pass
362  /// writes the node section and the first arc section, then the
363  /// second pass skips the node section and writes just the arc
364  /// section to the stream. The output stream can be retrieved with
365  /// the \c ostream() function, hence the second pass can append its
366  /// output to the output of the first pass.
367  template <typename _Digraph>
368  class DigraphWriter {
369  public:
370
371    typedef _Digraph Digraph;
372    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
373   
374  private:
375
376
377    std::ostream* _os;
378    bool local_os;
379
380    const Digraph& _digraph;
381
382    std::string _nodes_caption;
383    std::string _arcs_caption;
384    std::string _attributes_caption;
385   
386    typedef std::map<Node, std::string> NodeIndex;
387    NodeIndex _node_index;
388    typedef std::map<Arc, std::string> ArcIndex;
389    ArcIndex _arc_index;
390
391    typedef std::vector<std::pair<std::string,
392      _writer_bits::MapStorageBase<Node>* > > NodeMaps;   
393    NodeMaps _node_maps;
394
395    typedef std::vector<std::pair<std::string,
396      _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
397    ArcMaps _arc_maps;
398
399    typedef std::vector<std::pair<std::string,
400      _writer_bits::ValueStorageBase*> > Attributes;
401    Attributes _attributes;
402
403    bool _skip_nodes;
404    bool _skip_arcs;
405
406  public:
407
408    /// \brief Constructor
409    ///
410    /// Construct a directed graph writer, which writes to the given
411    /// output stream.
412    DigraphWriter(std::ostream& is, const Digraph& digraph)
413      : _os(&is), local_os(false), _digraph(digraph),
414        _skip_nodes(false), _skip_arcs(false) {}
415
416    /// \brief Constructor
417    ///
418    /// Construct a directed graph writer, which writes to the given
419    /// output file.
420    DigraphWriter(const std::string& fn, const Digraph& digraph)
421      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
422        _skip_nodes(false), _skip_arcs(false) {}
423
424    /// \brief Constructor
425    ///
426    /// Construct a directed graph writer, which writes to the given
427    /// output file.
428    DigraphWriter(const char* fn, const Digraph& digraph)
429      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
430        _skip_nodes(false), _skip_arcs(false) {}
431
432    /// \brief Destructor
433    ~DigraphWriter() {
434      for (typename NodeMaps::iterator it = _node_maps.begin();
435           it != _node_maps.end(); ++it) {
436        delete it->second;
437      }
438
439      for (typename ArcMaps::iterator it = _arc_maps.begin();
440           it != _arc_maps.end(); ++it) {
441        delete it->second;
442      }
443
444      for (typename Attributes::iterator it = _attributes.begin();
445           it != _attributes.end(); ++it) {
446        delete it->second;
447      }
448
449      if (local_os) {
450        delete _os;
451      }
452    }
453
454  private:
455
456    friend DigraphWriter<Digraph> digraphWriter<>(std::ostream& os,
457                                                  const Digraph& digraph);
458    friend DigraphWriter<Digraph> digraphWriter<>(const std::string& fn,
459                                                  const Digraph& digraph);   
460    friend DigraphWriter<Digraph> digraphWriter<>(const char *fn,
461                                                  const Digraph& digraph);
462
463    DigraphWriter(DigraphWriter& other)
464      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
465        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
466
467      other._os = 0;
468      other.local_os = false;
469
470      _node_index.swap(other._node_index);
471      _arc_index.swap(other._arc_index);
472
473      _node_maps.swap(other._node_maps);
474      _arc_maps.swap(other._arc_maps);
475      _attributes.swap(other._attributes);
476
477      _nodes_caption = other._nodes_caption;
478      _arcs_caption = other._arcs_caption;
479      _attributes_caption = other._attributes_caption;
480    }
481   
482    DigraphWriter& operator=(const DigraphWriter&);
483
484  public:
485
486    /// \name Writing rules
487    /// @{
488   
489    /// \brief Node map reading rule
490    ///
491    /// Add a node map reading rule to the writer.
492    template <typename Map>
493    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
494      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
495      _writer_bits::MapStorageBase<Node>* storage =
496        new _writer_bits::MapStorage<Node, Map>(map);
497      _node_maps.push_back(std::make_pair(caption, storage));
498      return *this;
499    }
500
501    /// \brief Node map writing rule
502    ///
503    /// Add a node map writing rule with specialized converter to the
504    /// writer.
505    template <typename Map, typename Converter>
506    DigraphWriter& nodeMap(const std::string& caption, const Map& map,
507                           const Converter& converter = Converter()) {
508      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
509      _writer_bits::MapStorageBase<Node>* storage =
510        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
511      _node_maps.push_back(std::make_pair(caption, storage));
512      return *this;
513    }
514
515    /// \brief Arc map writing rule
516    ///
517    /// Add an arc map writing rule to the writer.
518    template <typename Map>
519    DigraphWriter& arcMap(const std::string& caption, const Map& map) {
520      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
521      _writer_bits::MapStorageBase<Arc>* storage =
522        new _writer_bits::MapStorage<Arc, Map>(map);
523      _arc_maps.push_back(std::make_pair(caption, storage));
524      return *this;
525    }
526
527    /// \brief Arc map writing rule
528    ///
529    /// Add an arc map writing rule with specialized converter to the
530    /// writer.
531    template <typename Map, typename Converter>
532    DigraphWriter& arcMap(const std::string& caption, const Map& map,
533                          const Converter& converter = Converter()) {
534      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
535      _writer_bits::MapStorageBase<Arc>* storage =
536        new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
537      _arc_maps.push_back(std::make_pair(caption, storage));
538      return *this;
539    }
540
541    /// \brief Attribute writing rule
542    ///
543    /// Add an attribute writing rule to the writer.
544    template <typename Value>
545    DigraphWriter& attribute(const std::string& caption, const Value& value) {
546      _writer_bits::ValueStorageBase* storage =
547        new _writer_bits::ValueStorage<Value>(value);
548      _attributes.push_back(std::make_pair(caption, storage));
549      return *this;
550    }
551
552    /// \brief Attribute writing rule
553    ///
554    /// Add an attribute writing rule with specialized converter to the
555    /// writer.
556    template <typename Value, typename Converter>
557    DigraphWriter& attribute(const std::string& caption, const Value& value,
558                             const Converter& converter = Converter()) {
559      _writer_bits::ValueStorageBase* storage =
560        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
561      _attributes.push_back(std::make_pair(caption, storage));
562      return *this;
563    }
564
565    /// \brief Node writing rule
566    ///
567    /// Add a node writing rule to the writer.
568    DigraphWriter& node(const std::string& caption, const Node& node) {
569      typedef _writer_bits::MapLookUpConverter<Node> Converter;
570      Converter converter(_node_index);
571      _writer_bits::ValueStorageBase* storage =
572        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
573      _attributes.push_back(std::make_pair(caption, storage));
574      return *this;
575    }
576
577    /// \brief Arc writing rule
578    ///
579    /// Add an arc writing rule to writer.
580    DigraphWriter& arc(const std::string& caption, const Arc& arc) {
581      typedef _writer_bits::MapLookUpConverter<Arc> Converter;
582      Converter converter(_arc_index);
583      _writer_bits::ValueStorageBase* storage =
584        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
585      _attributes.push_back(std::make_pair(caption, storage));
586      return *this;
587    }
588
589    /// \name Select section by name
590    /// @{
591
592    /// \brief Set \c \@nodes section to be read
593    ///
594    /// Set \c \@nodes section to be read
595    DigraphWriter& nodes(const std::string& caption) {
596      _nodes_caption = caption;
597      return *this;
598    }
599
600    /// \brief Set \c \@arcs section to be read
601    ///
602    /// Set \c \@arcs section to be read
603    DigraphWriter& arcs(const std::string& caption) {
604      _arcs_caption = caption;
605      return *this;
606    }
607
608    /// \brief Set \c \@attributes section to be read
609    ///
610    /// Set \c \@attributes section to be read
611    DigraphWriter& attributes(const std::string& caption) {
612      _attributes_caption = caption;
613      return *this;
614    }
615
616    /// \name Skipping section
617    /// @{
618
619    /// \brief Skip writing the node set
620    ///
621    /// The \c \@nodes section will be not written to the stream.
622    DigraphWriter& skipNodes() {
623      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
624      _skip_nodes = true;
625      return *this;
626    }
627
628    /// \brief Skip writing arc set
629    ///
630    /// The \c \@arcs section will be not written to the stream.
631    DigraphWriter& skipArcs() {
632      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
633      _skip_arcs = true;
634      return *this;
635    }
636
637    /// @}
638
639  private:
640
641    void writeNodes() {
642      _writer_bits::MapStorageBase<Node>* label = 0;
643      for (typename NodeMaps::iterator it = _node_maps.begin();
644           it != _node_maps.end(); ++it) {
645        if (it->first == "label") {
646          label = it->second;
647          break;
648        }
649      }
650
651      *_os << "@nodes";
652      if (!_nodes_caption.empty()) {
653        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
654      }
655      *_os << std::endl;
656
657      if (label == 0) {
658        *_os << "label" << '\t';
659      }
660      for (typename NodeMaps::iterator it = _node_maps.begin();
661           it != _node_maps.end(); ++it) {
662        _writer_bits::writeToken(*_os, it->first) << '\t';
663      }
664      *_os << std::endl;
665
666      std::vector<Node> nodes;
667      for (NodeIt n(_digraph); n != INVALID; ++n) {
668        nodes.push_back(n);
669      }
670     
671      if (label == 0) {
672        IdMap<Digraph, Node> id_map(_digraph);
673        _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
674        std::sort(nodes.begin(), nodes.end(), id_less);
675      } else {
676        label->sort(nodes);
677      }
678
679      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
680        Node n = nodes[i];
681        if (label == 0) {
682          std::ostringstream os;
683          os << _digraph.id(n);
684          _writer_bits::writeToken(*_os, os.str());
685          *_os << '\t';
686          _node_index.insert(std::make_pair(n, os.str()));
687        }
688        for (typename NodeMaps::iterator it = _node_maps.begin();
689             it != _node_maps.end(); ++it) {
690          std::string value = it->second->get(n);
691          _writer_bits::writeToken(*_os, value);
692          if (it->first == "label") {
693            _node_index.insert(std::make_pair(n, value));
694          }
695          *_os << '\t';
696        }
697        *_os << std::endl;
698      }
699    }
700
701    void createNodeIndex() {
702      _writer_bits::MapStorageBase<Node>* label = 0;
703      for (typename NodeMaps::iterator it = _node_maps.begin();
704           it != _node_maps.end(); ++it) {
705        if (it->first == "label") {
706          label = it->second;
707          break;
708        }
709      }
710
711      if (label == 0) {
712        for (NodeIt n(_digraph); n != INVALID; ++n) {
713          std::ostringstream os;
714          os << _digraph.id(n);
715          _node_index.insert(std::make_pair(n, os.str()));       
716        }       
717      } else {
718        for (NodeIt n(_digraph); n != INVALID; ++n) {
719          std::string value = label->get(n);     
720          _node_index.insert(std::make_pair(n, value));
721        }
722      }
723    }
724
725    void writeArcs() {
726      _writer_bits::MapStorageBase<Arc>* label = 0;
727      for (typename ArcMaps::iterator it = _arc_maps.begin();
728           it != _arc_maps.end(); ++it) {
729        if (it->first == "label") {
730          label = it->second;
731          break;
732        }
733      }
734
735      *_os << "@arcs";
736      if (!_arcs_caption.empty()) {
737        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
738      }
739      *_os << std::endl;
740
741      *_os << '\t' << '\t';
742      if (label == 0) {
743        *_os << "label" << '\t';
744      }
745      for (typename ArcMaps::iterator it = _arc_maps.begin();
746           it != _arc_maps.end(); ++it) {
747        _writer_bits::writeToken(*_os, it->first) << '\t';
748      }
749      *_os << std::endl;
750
751      std::vector<Arc> arcs;
752      for (ArcIt n(_digraph); n != INVALID; ++n) {
753        arcs.push_back(n);
754      }
755     
756      if (label == 0) {
757        IdMap<Digraph, Arc> id_map(_digraph);
758        _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
759        std::sort(arcs.begin(), arcs.end(), id_less);
760      } else {
761        label->sort(arcs);
762      }
763
764      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
765        Arc a = arcs[i];
766        _writer_bits::writeToken(*_os, _node_index.
767                                 find(_digraph.source(a))->second);
768        *_os << '\t';
769        _writer_bits::writeToken(*_os, _node_index.
770                                 find(_digraph.target(a))->second);
771        *_os << '\t';
772        if (label == 0) {
773          std::ostringstream os;
774          os << _digraph.id(a);
775          _writer_bits::writeToken(*_os, os.str());
776          *_os << '\t';
777          _arc_index.insert(std::make_pair(a, os.str()));
778        }
779        for (typename ArcMaps::iterator it = _arc_maps.begin();
780             it != _arc_maps.end(); ++it) {
781          std::string value = it->second->get(a);
782          _writer_bits::writeToken(*_os, value);
783          if (it->first == "label") {
784            _arc_index.insert(std::make_pair(a, value));
785          }
786          *_os << '\t';
787        }
788        *_os << std::endl;
789      }
790    }
791
792    void createArcIndex() {
793      _writer_bits::MapStorageBase<Arc>* label = 0;
794      for (typename ArcMaps::iterator it = _arc_maps.begin();
795           it != _arc_maps.end(); ++it) {
796        if (it->first == "label") {
797          label = it->second;
798          break;
799        }
800      }
801
802      if (label == 0) {
803        for (ArcIt a(_digraph); a != INVALID; ++a) {
804          std::ostringstream os;
805          os << _digraph.id(a);
806          _arc_index.insert(std::make_pair(a, os.str()));         
807        }       
808      } else {
809        for (ArcIt a(_digraph); a != INVALID; ++a) {
810          std::string value = label->get(a);     
811          _arc_index.insert(std::make_pair(a, value));
812        }
813      }
814    }
815
816    void writeAttributes() {
817      if (_attributes.empty()) return;
818      *_os << "@attributes";
819      if (!_attributes_caption.empty()) {
820        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
821      }
822      *_os << std::endl;
823      for (typename Attributes::iterator it = _attributes.begin();
824           it != _attributes.end(); ++it) {
825        _writer_bits::writeToken(*_os, it->first) << ' ';
826        _writer_bits::writeToken(*_os, it->second->get());
827        *_os << std::endl;
828      }
829    }
830   
831  public:
832   
833    /// \name Execution of the writer   
834    /// @{
835
836    /// \brief Start the batch processing
837    ///
838    /// This function starts the batch processing
839    void run() {
840      if (!_skip_nodes) {
841        writeNodes();
842      } else {
843        createNodeIndex();
844      }
845      if (!_skip_arcs) {     
846        writeArcs();
847      } else {
848        createArcIndex();
849      }
850      writeAttributes();
851    }
852
853    /// \brief Gives back the stream of the writer
854    ///
855    /// Gives back the stream of the writer
856    std::ostream& ostream() {
857      return *_os;
858    }
859
860    /// @}
861  };
862
863  /// \relates DigraphWriter
864  template <typename Digraph>
865  DigraphWriter<Digraph> digraphWriter(std::ostream& os,
866                                       const Digraph& digraph) {
867    DigraphWriter<Digraph> tmp(os, digraph);
868    return tmp;
869  }
870
871  /// \relates DigraphWriter
872  template <typename Digraph>
873  DigraphWriter<Digraph> digraphWriter(const std::string& fn,
874                                       const Digraph& digraph) {
875    DigraphWriter<Digraph> tmp(fn, digraph);
876    return tmp;
877  }
878
879  /// \relates DigraphWriter
880  template <typename Digraph>
881  DigraphWriter<Digraph> digraphWriter(const char* fn,
882                                       const Digraph& digraph) {
883    DigraphWriter<Digraph> tmp(fn, digraph);
884    return tmp;
885  }
886
887  template <typename Graph>
888  class GraphWriter;
889
890  template <typename Graph>
891  GraphWriter<Graph> graphWriter(std::ostream& os, const Graph& graph);   
892
893  template <typename Graph>
894  GraphWriter<Graph> graphWriter(const std::string& fn, const Graph& graph);   
895
896  template <typename Graph>
897  GraphWriter<Graph> graphWriter(const char *fn, const Graph& graph);   
898
899  /// \ingroup lemon_io
900  /// 
901  /// \brief LGF writer for directed graphs
902  ///
903  /// This utility writes an \ref lgf-format "LGF" file.
904  template <typename _Graph>
905  class GraphWriter {
906  public:
907
908    typedef _Graph Graph;
909    TEMPLATE_GRAPH_TYPEDEFS(Graph);
910   
911  private:
912
913
914    std::ostream* _os;
915    bool local_os;
916
917    Graph& _graph;
918
919    std::string _nodes_caption;
920    std::string _edges_caption;
921    std::string _attributes_caption;
922   
923    typedef std::map<Node, std::string> NodeIndex;
924    NodeIndex _node_index;
925    typedef std::map<Edge, std::string> EdgeIndex;
926    EdgeIndex _edge_index;
927
928    typedef std::vector<std::pair<std::string,
929      _writer_bits::MapStorageBase<Node>* > > NodeMaps;   
930    NodeMaps _node_maps;
931
932    typedef std::vector<std::pair<std::string,
933      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
934    EdgeMaps _edge_maps;
935
936    typedef std::vector<std::pair<std::string,
937      _writer_bits::ValueStorageBase*> > Attributes;
938    Attributes _attributes;
939
940    bool _skip_nodes;
941    bool _skip_edges;
942
943  public:
944
945    /// \brief Constructor
946    ///
947    /// Construct a directed graph writer, which writes to the given
948    /// output stream.
949    GraphWriter(std::ostream& is, const Graph& graph)
950      : _os(&is), local_os(false), _graph(graph),
951        _skip_nodes(false), _skip_edges(false) {}
952
953    /// \brief Constructor
954    ///
955    /// Construct a directed graph writer, which writes to the given
956    /// output file.
957    GraphWriter(const std::string& fn, const Graph& graph)
958      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
959        _skip_nodes(false), _skip_edges(false) {}
960
961    /// \brief Constructor
962    ///
963    /// Construct a directed graph writer, which writes to the given
964    /// output file.
965    GraphWriter(const char* fn, const Graph& graph)
966      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
967        _skip_nodes(false), _skip_edges(false) {}
968
969    /// \brief Destructor
970    ~GraphWriter() {
971      for (typename NodeMaps::iterator it = _node_maps.begin();
972           it != _node_maps.end(); ++it) {
973        delete it->second;
974      }
975
976      for (typename EdgeMaps::iterator it = _edge_maps.begin();
977           it != _edge_maps.end(); ++it) {
978        delete it->second;
979      }
980
981      for (typename Attributes::iterator it = _attributes.begin();
982           it != _attributes.end(); ++it) {
983        delete it->second;
984      }
985
986      if (local_os) {
987        delete _os;
988      }
989    }
990   
991  private:
992
993    friend GraphWriter<Graph> graphWriter<>(std::ostream& os,
994                                            const Graph& graph);   
995    friend GraphWriter<Graph> graphWriter<>(const std::string& fn,
996                                            const Graph& graph);   
997    friend GraphWriter<Graph> graphWriter<>(const char *fn,
998                                            const Graph& graph);   
999
1000    GraphWriter(GraphWriter& other)
1001      : _os(other._os), local_os(other.local_os), _graph(other._graph),
1002        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1003
1004      other._os = 0;
1005      other.local_os = false;
1006
1007      _node_index.swap(other._node_index);
1008      _edge_index.swap(other._edge_index);
1009
1010      _node_maps.swap(other._node_maps);
1011      _edge_maps.swap(other._edge_maps);
1012      _attributes.swap(other._attributes);
1013
1014      _nodes_caption = other._nodes_caption;
1015      _edges_caption = other._edges_caption;
1016      _attributes_caption = other._attributes_caption;
1017    }
1018
1019    GraphWriter& operator=(const GraphWriter&);
1020
1021  public:
1022
1023    /// \name Writing rules
1024    /// @{
1025   
1026    /// \brief Node map reading rule
1027    ///
1028    /// Add a node map reading rule to the writer.
1029    template <typename Map>
1030    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
1031      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1032      _writer_bits::MapStorageBase<Node>* storage =
1033        new _writer_bits::MapStorage<Node, Map>(map);
1034      _node_maps.push_back(std::make_pair(caption, storage));
1035      return *this;
1036    }
1037
1038    /// \brief Node map writing rule
1039    ///
1040    /// Add a node map writing rule with specialized converter to the
1041    /// writer.
1042    template <typename Map, typename Converter>
1043    GraphWriter& nodeMap(const std::string& caption, const Map& map,
1044                           const Converter& converter = Converter()) {
1045      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1046      _writer_bits::MapStorageBase<Node>* storage =
1047        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
1048      _node_maps.push_back(std::make_pair(caption, storage));
1049      return *this;
1050    }
1051
1052    /// \brief Edge map writing rule
1053    ///
1054    /// Add an edge map writing rule to the writer.
1055    template <typename Map>
1056    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
1057      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1058      _writer_bits::MapStorageBase<Edge>* storage =
1059        new _writer_bits::MapStorage<Edge, Map>(map);
1060      _edge_maps.push_back(std::make_pair(caption, storage));
1061      return *this;
1062    }
1063
1064    /// \brief Edge map writing rule
1065    ///
1066    /// Add an edge map writing rule with specialized converter to the
1067    /// writer.
1068    template <typename Map, typename Converter>
1069    GraphWriter& edgeMap(const std::string& caption, const Map& map,
1070                          const Converter& converter = Converter()) {
1071      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1072      _writer_bits::MapStorageBase<Edge>* storage =
1073        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
1074      _edge_maps.push_back(std::make_pair(caption, storage));
1075      return *this;
1076    }
1077
1078    /// \brief Arc map writing rule
1079    ///
1080    /// Add an arc map writing rule to the writer.
1081    template <typename Map>
1082    GraphWriter& arcMap(const std::string& caption, const Map& map) {
1083      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1084      _writer_bits::MapStorageBase<Edge>* forward_storage =
1085        new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1086      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1087      _writer_bits::MapStorageBase<Edge>* backward_storage =
1088        new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1089      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1090      return *this;
1091    }
1092
1093    /// \brief Arc map writing rule
1094    ///
1095    /// Add an arc map writing rule with specialized converter to the
1096    /// writer.
1097    template <typename Map, typename Converter>
1098    GraphWriter& arcMap(const std::string& caption, const Map& map,
1099                          const Converter& converter = Converter()) {
1100      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1101      _writer_bits::MapStorageBase<Edge>* forward_storage =
1102        new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1103        (_graph, map, converter);
1104      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1105      _writer_bits::MapStorageBase<Edge>* backward_storage =
1106        new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1107        (_graph, map, converter);
1108      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1109      return *this;
1110    }
1111
1112    /// \brief Attribute writing rule
1113    ///
1114    /// Add an attribute writing rule to the writer.
1115    template <typename Value>
1116    GraphWriter& attribute(const std::string& caption, const Value& value) {
1117      _writer_bits::ValueStorageBase* storage =
1118        new _writer_bits::ValueStorage<Value>(value);
1119      _attributes.push_back(std::make_pair(caption, storage));
1120      return *this;
1121    }
1122
1123    /// \brief Attribute writing rule
1124    ///
1125    /// Add an attribute writing rule with specialized converter to the
1126    /// writer.
1127    template <typename Value, typename Converter>
1128    GraphWriter& attribute(const std::string& caption, const Value& value,
1129                             const Converter& converter = Converter()) {
1130      _writer_bits::ValueStorageBase* storage =
1131        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1132      _attributes.push_back(std::make_pair(caption, storage));
1133      return *this;
1134    }
1135
1136    /// \brief Node writing rule
1137    ///
1138    /// Add a node writing rule to the writer.
1139    GraphWriter& node(const std::string& caption, const Node& node) {
1140      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1141      Converter converter(_node_index);
1142      _writer_bits::ValueStorageBase* storage =
1143        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1144      _attributes.push_back(std::make_pair(caption, storage));
1145      return *this;
1146    }
1147
1148    /// \brief Edge writing rule
1149    ///
1150    /// Add an edge writing rule to writer.
1151    GraphWriter& edge(const std::string& caption, const Edge& edge) {
1152      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
1153      Converter converter(_edge_index);
1154      _writer_bits::ValueStorageBase* storage =
1155        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
1156      _attributes.push_back(std::make_pair(caption, storage));
1157      return *this;
1158    }
1159
1160    /// \brief Arc writing rule
1161    ///
1162    /// Add an arc writing rule to writer.
1163    GraphWriter& arc(const std::string& caption, const Arc& arc) {
1164      typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
1165      Converter converter(_graph, _edge_index);
1166      _writer_bits::ValueStorageBase* storage =
1167        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
1168      _attributes.push_back(std::make_pair(caption, storage));
1169      return *this;
1170    }
1171
1172    /// \name Select section by name
1173    /// @{
1174
1175    /// \brief Set \c \@nodes section to be read
1176    ///
1177    /// Set \c \@nodes section to be read
1178    GraphWriter& nodes(const std::string& caption) {
1179      _nodes_caption = caption;
1180      return *this;
1181    }
1182
1183    /// \brief Set \c \@edges section to be read
1184    ///
1185    /// Set \c \@edges section to be read
1186    GraphWriter& edges(const std::string& caption) {
1187      _edges_caption = caption;
1188      return *this;
1189    }
1190
1191    /// \brief Set \c \@attributes section to be read
1192    ///
1193    /// Set \c \@attributes section to be read
1194    GraphWriter& attributes(const std::string& caption) {
1195      _attributes_caption = caption;
1196      return *this;
1197    }
1198
1199    /// \name Skipping section
1200    /// @{
1201
1202    /// \brief Skip writing the node set
1203    ///
1204    /// The \c \@nodes section will be not written to the stream.
1205    GraphWriter& skipNodes() {
1206      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
1207      _skip_nodes = true;
1208      return *this;
1209    }
1210
1211    /// \brief Skip writing edge set
1212    ///
1213    /// The \c \@edges section will be not written to the stream.
1214    GraphWriter& skipEdges() {
1215      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
1216      _skip_edges = true;
1217      return *this;
1218    }
1219
1220    /// @}
1221
1222  private:
1223
1224    void writeNodes() {
1225      _writer_bits::MapStorageBase<Node>* label = 0;
1226      for (typename NodeMaps::iterator it = _node_maps.begin();
1227           it != _node_maps.end(); ++it) {
1228        if (it->first == "label") {
1229          label = it->second;
1230          break;
1231        }
1232      }
1233
1234      *_os << "@nodes";
1235      if (!_nodes_caption.empty()) {
1236        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
1237      }
1238      *_os << std::endl;
1239
1240      if (label == 0) {
1241        *_os << "label" << '\t';
1242      }
1243      for (typename NodeMaps::iterator it = _node_maps.begin();
1244           it != _node_maps.end(); ++it) {
1245        _writer_bits::writeToken(*_os, it->first) << '\t';
1246      }
1247      *_os << std::endl;
1248
1249      std::vector<Node> nodes;
1250      for (NodeIt n(_graph); n != INVALID; ++n) {
1251        nodes.push_back(n);
1252      }
1253     
1254      if (label == 0) {
1255        IdMap<Graph, Node> id_map(_graph);
1256        _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
1257        std::sort(nodes.begin(), nodes.end(), id_less);
1258      } else {
1259        label->sort(nodes);
1260      }
1261
1262      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
1263        Node n = nodes[i];
1264        if (label == 0) {
1265          std::ostringstream os;
1266          os << _graph.id(n);
1267          _writer_bits::writeToken(*_os, os.str());
1268          *_os << '\t';
1269          _node_index.insert(std::make_pair(n, os.str()));
1270        }
1271        for (typename NodeMaps::iterator it = _node_maps.begin();
1272             it != _node_maps.end(); ++it) {
1273          std::string value = it->second->get(n);
1274          _writer_bits::writeToken(*_os, value);
1275          if (it->first == "label") {
1276            _node_index.insert(std::make_pair(n, value));
1277          }
1278          *_os << '\t';
1279        }
1280        *_os << std::endl;
1281      }
1282    }
1283
1284    void createNodeIndex() {
1285      _writer_bits::MapStorageBase<Node>* label = 0;
1286      for (typename NodeMaps::iterator it = _node_maps.begin();
1287           it != _node_maps.end(); ++it) {
1288        if (it->first == "label") {
1289          label = it->second;
1290          break;
1291        }
1292      }
1293
1294      if (label == 0) {
1295        for (NodeIt n(_graph); n != INVALID; ++n) {
1296          std::ostringstream os;
1297          os << _graph.id(n);
1298          _node_index.insert(std::make_pair(n, os.str()));       
1299        }       
1300      } else {
1301        for (NodeIt n(_graph); n != INVALID; ++n) {
1302          std::string value = label->get(n);     
1303          _node_index.insert(std::make_pair(n, value));
1304        }
1305      }
1306    }
1307
1308    void writeEdges() {
1309      _writer_bits::MapStorageBase<Edge>* label = 0;
1310      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1311           it != _edge_maps.end(); ++it) {
1312        if (it->first == "label") {
1313          label = it->second;
1314          break;
1315        }
1316      }
1317
1318      *_os << "@edges";
1319      if (!_edges_caption.empty()) {
1320        _writer_bits::writeToken(*_os << ' ', _edges_caption);
1321      }
1322      *_os << std::endl;
1323
1324      *_os << '\t' << '\t';
1325      if (label == 0) {
1326        *_os << "label" << '\t';
1327      }
1328      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1329           it != _edge_maps.end(); ++it) {
1330        _writer_bits::writeToken(*_os, it->first) << '\t';
1331      }
1332      *_os << std::endl;
1333
1334      std::vector<Edge> edges;
1335      for (EdgeIt n(_graph); n != INVALID; ++n) {
1336        edges.push_back(n);
1337      }
1338     
1339      if (label == 0) {
1340        IdMap<Graph, Edge> id_map(_graph);
1341        _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
1342        std::sort(edges.begin(), edges.end(), id_less);
1343      } else {
1344        label->sort(edges);
1345      }
1346
1347      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
1348        Edge e = edges[i];
1349        _writer_bits::writeToken(*_os, _node_index.
1350                                 find(_graph.u(e))->second);
1351        *_os << '\t';
1352        _writer_bits::writeToken(*_os, _node_index.
1353                                 find(_graph.v(e))->second);
1354        *_os << '\t';
1355        if (label == 0) {
1356          std::ostringstream os;
1357          os << _graph.id(e);
1358          _writer_bits::writeToken(*_os, os.str());
1359          *_os << '\t';
1360          _edge_index.insert(std::make_pair(e, os.str()));
1361        }
1362        for (typename EdgeMaps::iterator it = _edge_maps.begin();
1363             it != _edge_maps.end(); ++it) {
1364          std::string value = it->second->get(e);
1365          _writer_bits::writeToken(*_os, value);
1366          if (it->first == "label") {
1367            _edge_index.insert(std::make_pair(e, value));
1368          }
1369          *_os << '\t';
1370        }
1371        *_os << std::endl;
1372      }
1373    }
1374
1375    void createEdgeIndex() {
1376      _writer_bits::MapStorageBase<Edge>* label = 0;
1377      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1378           it != _edge_maps.end(); ++it) {
1379        if (it->first == "label") {
1380          label = it->second;
1381          break;
1382        }
1383      }
1384
1385      if (label == 0) {
1386        for (EdgeIt e(_graph); e != INVALID; ++e) {
1387          std::ostringstream os;
1388          os << _graph.id(e);
1389          _edge_index.insert(std::make_pair(e, os.str()));       
1390        }       
1391      } else {
1392        for (EdgeIt e(_graph); e != INVALID; ++e) {
1393          std::string value = label->get(e);     
1394          _edge_index.insert(std::make_pair(e, value));
1395        }
1396      }
1397    }
1398
1399    void writeAttributes() {
1400      if (_attributes.empty()) return;
1401      *_os << "@attributes";
1402      if (!_attributes_caption.empty()) {
1403        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
1404      }
1405      *_os << std::endl;
1406      for (typename Attributes::iterator it = _attributes.begin();
1407           it != _attributes.end(); ++it) {
1408        _writer_bits::writeToken(*_os, it->first) << ' ';
1409        _writer_bits::writeToken(*_os, it->second->get());
1410        *_os << std::endl;
1411      }
1412    }
1413   
1414  public:
1415   
1416    /// \name Execution of the writer   
1417    /// @{
1418
1419    /// \brief Start the batch processing
1420    ///
1421    /// This function starts the batch processing
1422    void run() {
1423      if (!_skip_nodes) {
1424        writeNodes();
1425      } else {
1426        createNodeIndex();
1427      }
1428      if (!_skip_edges) {     
1429        writeEdges();
1430      } else {
1431        createEdgeIndex();
1432      }
1433      writeAttributes();
1434    }
1435
1436    /// \brief Gives back the stream of the writer
1437    ///
1438    /// Gives back the stream of the writer
1439    std::ostream& ostream() {
1440      return *_os;
1441    }
1442
1443    /// @}
1444  };
1445
1446  /// \relates GraphWriter
1447  template <typename Graph>
1448  GraphWriter<Graph> graphWriter(std::ostream& os, const Graph& graph) {
1449    GraphWriter<Graph> tmp(os, graph);
1450    return tmp;
1451  }
1452
1453  /// \relates GraphWriter
1454  template <typename Graph>
1455  GraphWriter<Graph> graphWriter(const std::string& fn, const Graph& graph) {
1456    GraphWriter<Graph> tmp(fn, graph);
1457    return tmp;
1458  }
1459
1460  /// \relates GraphWriter
1461  template <typename Graph>
1462  GraphWriter<Graph> graphWriter(const char* fn, const Graph& graph) {
1463    GraphWriter<Graph> tmp(fn, graph);
1464    return tmp;
1465  }
1466}
1467
1468#endif
Note: See TracBrowser for help on using the repository browser.