COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_writer.h @ 173:b026e9779b28

Last change on this file since 173:b026e9779b28 was 165:b4c336c27a03, checked in by Balazs Dezso <deba@…>, 17 years ago

Undirected LGF IO

File size: 37.2 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  /// \ingroup lemon_io
309  /// 
310  /// \brief LGF writer for directed graphs
311  ///
312  /// This utility writes an \ref lgf-format "LGF" file.
313  ///
314  /// The writing method does a batch processing. The user creates a
315  /// writer object, then various writing rules can be added to the
316  /// writer, and eventually the writing is executed with the \c run()
317  /// member function. A map writing rule can be added to the writer
318  /// with the \c nodeMap() or \c arcMap() members. An optional
319  /// converter parameter can also be added as a standard functor
320  /// converting from the value type of the map to std::string. If it
321  /// is set, it will determine how the map's value type is written to
322  /// the output stream. If the functor is not set, then a default
323  /// conversion will be used. The \c attribute(), \c node() and \c
324  /// arc() functions are used to add attribute writing rules.
325  ///
326  ///\code
327  ///     DigraphWriter<Digraph>(std::cout, digraph).
328  ///       nodeMap("coordinates", coord_map).
329  ///       nodeMap("size", size).
330  ///       nodeMap("title", title).
331  ///       arcMap("capacity", cap_map).
332  ///       node("source", src).
333  ///       node("target", trg).
334  ///       attribute("caption", caption).
335  ///       run();
336  ///\endcode
337  ///
338  ///
339  /// By default, the writer does not write additional captions to the
340  /// sections, but they can be give as an optional parameter of
341  /// the \c nodes(), \c arcs() or \c
342  /// attributes() functions.
343  ///
344  /// The \c skipNodes() and \c skipArcs() functions forbid the
345  /// writing of the sections. If two arc sections should be written
346  /// to the output, it can be done in two passes, the first pass
347  /// writes the node section and the first arc section, then the
348  /// second pass skips the node section and writes just the arc
349  /// section to the stream. The output stream can be retrieved with
350  /// the \c ostream() function, hence the second pass can append its
351  /// output to the output of the first pass.
352  template <typename _Digraph>
353  class DigraphWriter {
354  public:
355
356    typedef _Digraph Digraph;
357    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
358   
359  private:
360
361
362    std::ostream* _os;
363    bool local_os;
364
365    Digraph& _digraph;
366
367    std::string _nodes_caption;
368    std::string _arcs_caption;
369    std::string _attributes_caption;
370   
371    typedef std::map<Node, std::string> NodeIndex;
372    NodeIndex _node_index;
373    typedef std::map<Arc, std::string> ArcIndex;
374    ArcIndex _arc_index;
375
376    typedef std::vector<std::pair<std::string,
377      _writer_bits::MapStorageBase<Node>* > > NodeMaps;   
378    NodeMaps _node_maps;
379
380    typedef std::vector<std::pair<std::string,
381      _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
382    ArcMaps _arc_maps;
383
384    typedef std::vector<std::pair<std::string,
385      _writer_bits::ValueStorageBase*> > Attributes;
386    Attributes _attributes;
387
388    bool _skip_nodes;
389    bool _skip_arcs;
390
391  public:
392
393    /// \brief Constructor
394    ///
395    /// Construct a directed graph writer, which writes to the given
396    /// output stream.
397    DigraphWriter(std::ostream& is, Digraph& digraph)
398      : _os(&is), local_os(false), _digraph(digraph),
399        _skip_nodes(false), _skip_arcs(false) {}
400
401    /// \brief Constructor
402    ///
403    /// Construct a directed graph writer, which writes to the given
404    /// output file.
405    DigraphWriter(const std::string& fn, Digraph& digraph)
406      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
407        _skip_nodes(false), _skip_arcs(false) {}
408
409    /// \brief Constructor
410    ///
411    /// Construct a directed graph writer, which writes to the given
412    /// output file.
413    DigraphWriter(const char* fn, Digraph& digraph)
414      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
415        _skip_nodes(false), _skip_arcs(false) {}
416
417    /// \brief Copy constructor
418    ///
419    /// The copy constructor transfers all data from the other writer,
420    /// therefore the copied writer will not be usable more.
421    DigraphWriter(DigraphWriter& other)
422      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
423        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
424
425      other._os = 0;
426      other.local_os = false;
427
428      _node_index.swap(other._node_index);
429      _arc_index.swap(other._arc_index);
430
431      _node_maps.swap(other._node_maps);
432      _arc_maps.swap(other._arc_maps);
433      _attributes.swap(other._attributes);
434
435      _nodes_caption = other._nodes_caption;
436      _arcs_caption = other._arcs_caption;
437      _attributes_caption = other._attributes_caption;
438    }
439
440    /// \brief Destructor
441    ~DigraphWriter() {
442      for (typename NodeMaps::iterator it = _node_maps.begin();
443           it != _node_maps.end(); ++it) {
444        delete it->second;
445      }
446
447      for (typename ArcMaps::iterator it = _arc_maps.begin();
448           it != _arc_maps.end(); ++it) {
449        delete it->second;
450      }
451
452      for (typename Attributes::iterator it = _attributes.begin();
453           it != _attributes.end(); ++it) {
454        delete it->second;
455      }
456
457      if (local_os) {
458        delete _os;
459      }
460    }
461
462  private:
463   
464    DigraphWriter& operator=(const DigraphWriter&);
465
466  public:
467
468    /// \name Writing rules
469    /// @{
470   
471    /// \brief Node map reading rule
472    ///
473    /// Add a node map reading rule to the writer.
474    template <typename Map>
475    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
476      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
477      _writer_bits::MapStorageBase<Node>* storage =
478        new _writer_bits::MapStorage<Node, Map>(map);
479      _node_maps.push_back(std::make_pair(caption, storage));
480      return *this;
481    }
482
483    /// \brief Node map writing rule
484    ///
485    /// Add a node map writing rule with specialized converter to the
486    /// writer.
487    template <typename Map, typename Converter>
488    DigraphWriter& nodeMap(const std::string& caption, const Map& map,
489                           const Converter& converter = Converter()) {
490      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
491      _writer_bits::MapStorageBase<Node>* storage =
492        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
493      _node_maps.push_back(std::make_pair(caption, storage));
494      return *this;
495    }
496
497    /// \brief Arc map writing rule
498    ///
499    /// Add an arc map writing rule to the writer.
500    template <typename Map>
501    DigraphWriter& arcMap(const std::string& caption, const Map& map) {
502      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
503      _writer_bits::MapStorageBase<Arc>* storage =
504        new _writer_bits::MapStorage<Arc, Map>(map);
505      _arc_maps.push_back(std::make_pair(caption, storage));
506      return *this;
507    }
508
509    /// \brief Arc map writing rule
510    ///
511    /// Add an arc map writing rule with specialized converter to the
512    /// writer.
513    template <typename Map, typename Converter>
514    DigraphWriter& arcMap(const std::string& caption, const Map& map,
515                          const Converter& converter = Converter()) {
516      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
517      _writer_bits::MapStorageBase<Arc>* storage =
518        new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
519      _arc_maps.push_back(std::make_pair(caption, storage));
520      return *this;
521    }
522
523    /// \brief Attribute writing rule
524    ///
525    /// Add an attribute writing rule to the writer.
526    template <typename Value>
527    DigraphWriter& attribute(const std::string& caption, const Value& value) {
528      _writer_bits::ValueStorageBase* storage =
529        new _writer_bits::ValueStorage<Value>(value);
530      _attributes.push_back(std::make_pair(caption, storage));
531      return *this;
532    }
533
534    /// \brief Attribute writing rule
535    ///
536    /// Add an attribute writing rule with specialized converter to the
537    /// writer.
538    template <typename Value, typename Converter>
539    DigraphWriter& attribute(const std::string& caption, const Value& value,
540                             const Converter& converter = Converter()) {
541      _writer_bits::ValueStorageBase* storage =
542        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
543      _attributes.push_back(std::make_pair(caption, storage));
544      return *this;
545    }
546
547    /// \brief Node writing rule
548    ///
549    /// Add a node writing rule to the writer.
550    DigraphWriter& node(const std::string& caption, const Node& node) {
551      typedef _writer_bits::MapLookUpConverter<Node> Converter;
552      Converter converter(_node_index);
553      _writer_bits::ValueStorageBase* storage =
554        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
555      _attributes.push_back(std::make_pair(caption, storage));
556      return *this;
557    }
558
559    /// \brief Arc writing rule
560    ///
561    /// Add an arc writing rule to writer.
562    DigraphWriter& arc(const std::string& caption, const Arc& arc) {
563      typedef _writer_bits::MapLookUpConverter<Arc> Converter;
564      Converter converter(_arc_index);
565      _writer_bits::ValueStorageBase* storage =
566        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
567      _attributes.push_back(std::make_pair(caption, storage));
568      return *this;
569    }
570
571    /// \name Select section by name
572    /// @{
573
574    /// \brief Set \c \@nodes section to be read
575    ///
576    /// Set \c \@nodes section to be read
577    DigraphWriter& nodes(const std::string& caption) {
578      _nodes_caption = caption;
579      return *this;
580    }
581
582    /// \brief Set \c \@arcs section to be read
583    ///
584    /// Set \c \@arcs section to be read
585    DigraphWriter& arcs(const std::string& caption) {
586      _arcs_caption = caption;
587      return *this;
588    }
589
590    /// \brief Set \c \@attributes section to be read
591    ///
592    /// Set \c \@attributes section to be read
593    DigraphWriter& attributes(const std::string& caption) {
594      _attributes_caption = caption;
595      return *this;
596    }
597
598    /// \name Skipping section
599    /// @{
600
601    /// \brief Skip writing the node set
602    ///
603    /// The \c \@nodes section will be not written to the stream.
604    DigraphWriter& skipNodes() {
605      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
606      return *this;
607    }
608
609    /// \brief Skip writing arc set
610    ///
611    /// The \c \@arcs section will be not written to the stream.
612    DigraphWriter& skipArcs() {
613      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
614      return *this;
615    }
616
617    /// @}
618
619  private:
620
621    void writeNodes() {
622      _writer_bits::MapStorageBase<Node>* label = 0;
623      for (typename NodeMaps::iterator it = _node_maps.begin();
624           it != _node_maps.end(); ++it) {
625        if (it->first == "label") {
626          label = it->second;
627          break;
628        }
629      }
630
631      *_os << "@nodes";
632      if (!_nodes_caption.empty()) {
633        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
634      }
635      *_os << std::endl;
636
637      if (label == 0) {
638        *_os << "label" << '\t';
639      }
640      for (typename NodeMaps::iterator it = _node_maps.begin();
641           it != _node_maps.end(); ++it) {
642        _writer_bits::writeToken(*_os, it->first) << '\t';
643      }
644      *_os << std::endl;
645
646      std::vector<Node> nodes;
647      for (NodeIt n(_digraph); n != INVALID; ++n) {
648        nodes.push_back(n);
649      }
650     
651      if (label == 0) {
652        IdMap<Digraph, Node> id_map(_digraph);
653        _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
654        std::sort(nodes.begin(), nodes.end(), id_less);
655      } else {
656        label->sort(nodes);
657      }
658
659      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
660        Node n = nodes[i];
661        if (label == 0) {
662          std::ostringstream os;
663          os << _digraph.id(n);
664          _writer_bits::writeToken(*_os, os.str());
665          *_os << '\t';
666          _node_index.insert(std::make_pair(n, os.str()));
667        }
668        for (typename NodeMaps::iterator it = _node_maps.begin();
669             it != _node_maps.end(); ++it) {
670          std::string value = it->second->get(n);
671          _writer_bits::writeToken(*_os, value);
672          if (it->first == "label") {
673            _node_index.insert(std::make_pair(n, value));
674          }
675          *_os << '\t';
676        }
677        *_os << std::endl;
678      }
679    }
680
681    void writeArcs() {
682      _writer_bits::MapStorageBase<Arc>* label = 0;
683      for (typename ArcMaps::iterator it = _arc_maps.begin();
684           it != _arc_maps.end(); ++it) {
685        if (it->first == "label") {
686          label = it->second;
687          break;
688        }
689      }
690
691      *_os << "@arcs";
692      if (!_arcs_caption.empty()) {
693        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
694      }
695      *_os << std::endl;
696
697      *_os << '\t' << '\t';
698      if (label == 0) {
699        *_os << "label" << '\t';
700      }
701      for (typename ArcMaps::iterator it = _arc_maps.begin();
702           it != _arc_maps.end(); ++it) {
703        _writer_bits::writeToken(*_os, it->first) << '\t';
704      }
705      *_os << std::endl;
706
707      std::vector<Arc> arcs;
708      for (ArcIt n(_digraph); n != INVALID; ++n) {
709        arcs.push_back(n);
710      }
711     
712      if (label == 0) {
713        IdMap<Digraph, Arc> id_map(_digraph);
714        _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
715        std::sort(arcs.begin(), arcs.end(), id_less);
716      } else {
717        label->sort(arcs);
718      }
719
720      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
721        Arc a = arcs[i];
722        _writer_bits::writeToken(*_os, _node_index.
723                                 find(_digraph.source(a))->second);
724        *_os << '\t';
725        _writer_bits::writeToken(*_os, _node_index.
726                                 find(_digraph.target(a))->second);
727        *_os << '\t';
728        if (label == 0) {
729          std::ostringstream os;
730          os << _digraph.id(a);
731          _writer_bits::writeToken(*_os, os.str());
732          *_os << '\t';
733          _arc_index.insert(std::make_pair(a, os.str()));
734        }
735        for (typename ArcMaps::iterator it = _arc_maps.begin();
736             it != _arc_maps.end(); ++it) {
737          std::string value = it->second->get(a);
738          _writer_bits::writeToken(*_os, value);
739          if (it->first == "label") {
740            _arc_index.insert(std::make_pair(a, value));
741          }
742          *_os << '\t';
743        }
744        *_os << std::endl;
745      }
746    }
747
748    void writeAttributes() {
749      if (_attributes.empty()) return;
750      *_os << "@attributes";
751      if (!_attributes_caption.empty()) {
752        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
753      }
754      *_os << std::endl;
755      for (typename Attributes::iterator it = _attributes.begin();
756           it != _attributes.end(); ++it) {
757        _writer_bits::writeToken(*_os, it->first) << ' ';
758        _writer_bits::writeToken(*_os, it->second->get());
759        *_os << std::endl;
760      }
761    }
762   
763  public:
764   
765    /// \name Execution of the writer   
766    /// @{
767
768    /// \brief Start the batch processing
769    ///
770    /// This function starts the batch processing
771    void run() {
772      if (!_skip_nodes) {
773        writeNodes();
774      }
775      if (!_skip_arcs) {     
776        writeArcs();
777      }
778      writeAttributes();
779    }
780
781    /// \brief Gives back the stream of the writer
782    ///
783    /// Gives back the stream of the writer
784    std::ostream& ostream() {
785      return *_os;
786    }
787
788    /// @}
789  };
790
791  /// \relates DigraphWriter
792  template <typename Digraph>
793  DigraphWriter<Digraph> digraphWriter(std::ostream& os, Digraph& digraph) {
794    DigraphWriter<Digraph> tmp(os, digraph);
795    return tmp;
796  }
797
798  /// \relates DigraphWriter
799  template <typename Digraph>
800  DigraphWriter<Digraph> digraphWriter(const std::string& fn,
801                                       Digraph& digraph) {
802    DigraphWriter<Digraph> tmp(fn, digraph);
803    return tmp;
804  }
805
806  /// \relates DigraphWriter
807  template <typename Digraph>
808  DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
809    DigraphWriter<Digraph> tmp(fn, digraph);
810    return tmp;
811  }
812
813  /// \ingroup lemon_io
814  /// 
815  /// \brief LGF writer for directed graphs
816  ///
817  /// This utility writes an \ref lgf-format "LGF" file.
818  template <typename _Graph>
819  class GraphWriter {
820  public:
821
822    typedef _Graph Graph;
823    TEMPLATE_GRAPH_TYPEDEFS(Graph);
824   
825  private:
826
827
828    std::ostream* _os;
829    bool local_os;
830
831    Graph& _graph;
832
833    std::string _nodes_caption;
834    std::string _edges_caption;
835    std::string _attributes_caption;
836   
837    typedef std::map<Node, std::string> NodeIndex;
838    NodeIndex _node_index;
839    typedef std::map<Edge, std::string> EdgeIndex;
840    EdgeIndex _edge_index;
841
842    typedef std::vector<std::pair<std::string,
843      _writer_bits::MapStorageBase<Node>* > > NodeMaps;   
844    NodeMaps _node_maps;
845
846    typedef std::vector<std::pair<std::string,
847      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
848    EdgeMaps _edge_maps;
849
850    typedef std::vector<std::pair<std::string,
851      _writer_bits::ValueStorageBase*> > Attributes;
852    Attributes _attributes;
853
854    bool _skip_nodes;
855    bool _skip_edges;
856
857  public:
858
859    /// \brief Constructor
860    ///
861    /// Construct a directed graph writer, which writes to the given
862    /// output stream.
863    GraphWriter(std::ostream& is, Graph& graph)
864      : _os(&is), local_os(false), _graph(graph),
865        _skip_nodes(false), _skip_edges(false) {}
866
867    /// \brief Constructor
868    ///
869    /// Construct a directed graph writer, which writes to the given
870    /// output file.
871    GraphWriter(const std::string& fn, Graph& graph)
872      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
873        _skip_nodes(false), _skip_edges(false) {}
874
875    /// \brief Constructor
876    ///
877    /// Construct a directed graph writer, which writes to the given
878    /// output file.
879    GraphWriter(const char* fn, Graph& graph)
880      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
881        _skip_nodes(false), _skip_edges(false) {}
882
883    /// \brief Copy constructor
884    ///
885    /// The copy constructor transfers all data from the other writer,
886    /// therefore the copied writer will not be usable more.
887    GraphWriter(GraphWriter& other)
888      : _os(other._os), local_os(other.local_os), _graph(other._graph),
889        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
890
891      other._os = 0;
892      other.local_os = false;
893
894      _node_index.swap(other._node_index);
895      _edge_index.swap(other._edge_index);
896
897      _node_maps.swap(other._node_maps);
898      _edge_maps.swap(other._edge_maps);
899      _attributes.swap(other._attributes);
900
901      _nodes_caption = other._nodes_caption;
902      _edges_caption = other._edges_caption;
903      _attributes_caption = other._attributes_caption;
904    }
905
906    /// \brief Destructor
907    ~GraphWriter() {
908      for (typename NodeMaps::iterator it = _node_maps.begin();
909           it != _node_maps.end(); ++it) {
910        delete it->second;
911      }
912
913      for (typename EdgeMaps::iterator it = _edge_maps.begin();
914           it != _edge_maps.end(); ++it) {
915        delete it->second;
916      }
917
918      for (typename Attributes::iterator it = _attributes.begin();
919           it != _attributes.end(); ++it) {
920        delete it->second;
921      }
922
923      if (local_os) {
924        delete _os;
925      }
926    }
927
928  private:
929   
930    GraphWriter& operator=(const GraphWriter&);
931
932  public:
933
934    /// \name Writing rules
935    /// @{
936   
937    /// \brief Node map reading rule
938    ///
939    /// Add a node map reading rule to the writer.
940    template <typename Map>
941    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
942      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
943      _writer_bits::MapStorageBase<Node>* storage =
944        new _writer_bits::MapStorage<Node, Map>(map);
945      _node_maps.push_back(std::make_pair(caption, storage));
946      return *this;
947    }
948
949    /// \brief Node map writing rule
950    ///
951    /// Add a node map writing rule with specialized converter to the
952    /// writer.
953    template <typename Map, typename Converter>
954    GraphWriter& nodeMap(const std::string& caption, const Map& map,
955                           const Converter& converter = Converter()) {
956      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
957      _writer_bits::MapStorageBase<Node>* storage =
958        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
959      _node_maps.push_back(std::make_pair(caption, storage));
960      return *this;
961    }
962
963    /// \brief Edge map writing rule
964    ///
965    /// Add an edge map writing rule to the writer.
966    template <typename Map>
967    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
968      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
969      _writer_bits::MapStorageBase<Edge>* storage =
970        new _writer_bits::MapStorage<Edge, Map>(map);
971      _edge_maps.push_back(std::make_pair(caption, storage));
972      return *this;
973    }
974
975    /// \brief Edge map writing rule
976    ///
977    /// Add an edge map writing rule with specialized converter to the
978    /// writer.
979    template <typename Map, typename Converter>
980    GraphWriter& edgeMap(const std::string& caption, const Map& map,
981                          const Converter& converter = Converter()) {
982      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
983      _writer_bits::MapStorageBase<Edge>* storage =
984        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
985      _edge_maps.push_back(std::make_pair(caption, storage));
986      return *this;
987    }
988
989    /// \brief Arc map writing rule
990    ///
991    /// Add an arc map writing rule to the writer.
992    template <typename Map>
993    GraphWriter& arcMap(const std::string& caption, const Map& map) {
994      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
995      _writer_bits::MapStorageBase<Edge>* forward_storage =
996        new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
997      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
998      _writer_bits::MapStorageBase<Edge>* backward_storage =
999        new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1000      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1001      return *this;
1002    }
1003
1004    /// \brief Arc map writing rule
1005    ///
1006    /// Add an arc map writing rule with specialized converter to the
1007    /// writer.
1008    template <typename Map, typename Converter>
1009    GraphWriter& arcMap(const std::string& caption, const Map& map,
1010                          const Converter& converter = Converter()) {
1011      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1012      _writer_bits::MapStorageBase<Edge>* forward_storage =
1013        new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1014        (_graph, map, converter);
1015      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1016      _writer_bits::MapStorageBase<Edge>* backward_storage =
1017        new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1018        (_graph, map, converter);
1019      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1020      return *this;
1021    }
1022
1023    /// \brief Attribute writing rule
1024    ///
1025    /// Add an attribute writing rule to the writer.
1026    template <typename Value>
1027    GraphWriter& attribute(const std::string& caption, const Value& value) {
1028      _writer_bits::ValueStorageBase* storage =
1029        new _writer_bits::ValueStorage<Value>(value);
1030      _attributes.push_back(std::make_pair(caption, storage));
1031      return *this;
1032    }
1033
1034    /// \brief Attribute writing rule
1035    ///
1036    /// Add an attribute writing rule with specialized converter to the
1037    /// writer.
1038    template <typename Value, typename Converter>
1039    GraphWriter& attribute(const std::string& caption, const Value& value,
1040                             const Converter& converter = Converter()) {
1041      _writer_bits::ValueStorageBase* storage =
1042        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1043      _attributes.push_back(std::make_pair(caption, storage));
1044      return *this;
1045    }
1046
1047    /// \brief Node writing rule
1048    ///
1049    /// Add a node writing rule to the writer.
1050    GraphWriter& node(const std::string& caption, const Node& node) {
1051      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1052      Converter converter(_node_index);
1053      _writer_bits::ValueStorageBase* storage =
1054        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1055      _attributes.push_back(std::make_pair(caption, storage));
1056      return *this;
1057    }
1058
1059    /// \brief Edge writing rule
1060    ///
1061    /// Add an edge writing rule to writer.
1062    GraphWriter& edge(const std::string& caption, const Edge& edge) {
1063      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
1064      Converter converter(_edge_index);
1065      _writer_bits::ValueStorageBase* storage =
1066        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
1067      _attributes.push_back(std::make_pair(caption, storage));
1068      return *this;
1069    }
1070
1071    /// \brief Arc writing rule
1072    ///
1073    /// Add an arc writing rule to writer.
1074    GraphWriter& arc(const std::string& caption, const Arc& arc) {
1075      typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
1076      Converter converter(_graph, _edge_index);
1077      _writer_bits::ValueStorageBase* storage =
1078        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
1079      _attributes.push_back(std::make_pair(caption, storage));
1080      return *this;
1081    }
1082
1083    /// \name Select section by name
1084    /// @{
1085
1086    /// \brief Set \c \@nodes section to be read
1087    ///
1088    /// Set \c \@nodes section to be read
1089    GraphWriter& nodes(const std::string& caption) {
1090      _nodes_caption = caption;
1091      return *this;
1092    }
1093
1094    /// \brief Set \c \@edges section to be read
1095    ///
1096    /// Set \c \@edges section to be read
1097    GraphWriter& edges(const std::string& caption) {
1098      _edges_caption = caption;
1099      return *this;
1100    }
1101
1102    /// \brief Set \c \@attributes section to be read
1103    ///
1104    /// Set \c \@attributes section to be read
1105    GraphWriter& attributes(const std::string& caption) {
1106      _attributes_caption = caption;
1107      return *this;
1108    }
1109
1110    /// \name Skipping section
1111    /// @{
1112
1113    /// \brief Skip writing the node set
1114    ///
1115    /// The \c \@nodes section will be not written to the stream.
1116    GraphWriter& skipNodes() {
1117      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
1118      return *this;
1119    }
1120
1121    /// \brief Skip writing edge set
1122    ///
1123    /// The \c \@edges section will be not written to the stream.
1124    GraphWriter& skipEdges() {
1125      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
1126      return *this;
1127    }
1128
1129    /// @}
1130
1131  private:
1132
1133    void writeNodes() {
1134      _writer_bits::MapStorageBase<Node>* label = 0;
1135      for (typename NodeMaps::iterator it = _node_maps.begin();
1136           it != _node_maps.end(); ++it) {
1137        if (it->first == "label") {
1138          label = it->second;
1139          break;
1140        }
1141      }
1142
1143      *_os << "@nodes";
1144      if (!_nodes_caption.empty()) {
1145        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
1146      }
1147      *_os << std::endl;
1148
1149      if (label == 0) {
1150        *_os << "label" << '\t';
1151      }
1152      for (typename NodeMaps::iterator it = _node_maps.begin();
1153           it != _node_maps.end(); ++it) {
1154        _writer_bits::writeToken(*_os, it->first) << '\t';
1155      }
1156      *_os << std::endl;
1157
1158      std::vector<Node> nodes;
1159      for (NodeIt n(_graph); n != INVALID; ++n) {
1160        nodes.push_back(n);
1161      }
1162     
1163      if (label == 0) {
1164        IdMap<Graph, Node> id_map(_graph);
1165        _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
1166        std::sort(nodes.begin(), nodes.end(), id_less);
1167      } else {
1168        label->sort(nodes);
1169      }
1170
1171      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
1172        Node n = nodes[i];
1173        if (label == 0) {
1174          std::ostringstream os;
1175          os << _graph.id(n);
1176          _writer_bits::writeToken(*_os, os.str());
1177          *_os << '\t';
1178          _node_index.insert(std::make_pair(n, os.str()));
1179        }
1180        for (typename NodeMaps::iterator it = _node_maps.begin();
1181             it != _node_maps.end(); ++it) {
1182          std::string value = it->second->get(n);
1183          _writer_bits::writeToken(*_os, value);
1184          if (it->first == "label") {
1185            _node_index.insert(std::make_pair(n, value));
1186          }
1187          *_os << '\t';
1188        }
1189        *_os << std::endl;
1190      }
1191    }
1192
1193    void writeEdges() {
1194      _writer_bits::MapStorageBase<Edge>* label = 0;
1195      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1196           it != _edge_maps.end(); ++it) {
1197        if (it->first == "label") {
1198          label = it->second;
1199          break;
1200        }
1201      }
1202
1203      *_os << "@edges";
1204      if (!_edges_caption.empty()) {
1205        _writer_bits::writeToken(*_os << ' ', _edges_caption);
1206      }
1207      *_os << std::endl;
1208
1209      *_os << '\t' << '\t';
1210      if (label == 0) {
1211        *_os << "label" << '\t';
1212      }
1213      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1214           it != _edge_maps.end(); ++it) {
1215        _writer_bits::writeToken(*_os, it->first) << '\t';
1216      }
1217      *_os << std::endl;
1218
1219      std::vector<Edge> edges;
1220      for (EdgeIt n(_graph); n != INVALID; ++n) {
1221        edges.push_back(n);
1222      }
1223     
1224      if (label == 0) {
1225        IdMap<Graph, Edge> id_map(_graph);
1226        _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
1227        std::sort(edges.begin(), edges.end(), id_less);
1228      } else {
1229        label->sort(edges);
1230      }
1231
1232      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
1233        Edge e = edges[i];
1234        _writer_bits::writeToken(*_os, _node_index.
1235                                 find(_graph.u(e))->second);
1236        *_os << '\t';
1237        _writer_bits::writeToken(*_os, _node_index.
1238                                 find(_graph.v(e))->second);
1239        *_os << '\t';
1240        if (label == 0) {
1241          std::ostringstream os;
1242          os << _graph.id(e);
1243          _writer_bits::writeToken(*_os, os.str());
1244          *_os << '\t';
1245          _edge_index.insert(std::make_pair(e, os.str()));
1246        }
1247        for (typename EdgeMaps::iterator it = _edge_maps.begin();
1248             it != _edge_maps.end(); ++it) {
1249          std::string value = it->second->get(e);
1250          _writer_bits::writeToken(*_os, value);
1251          if (it->first == "label") {
1252            _edge_index.insert(std::make_pair(e, value));
1253          }
1254          *_os << '\t';
1255        }
1256        *_os << std::endl;
1257      }
1258    }
1259
1260    void writeAttributes() {
1261      if (_attributes.empty()) return;
1262      *_os << "@attributes";
1263      if (!_attributes_caption.empty()) {
1264        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
1265      }
1266      *_os << std::endl;
1267      for (typename Attributes::iterator it = _attributes.begin();
1268           it != _attributes.end(); ++it) {
1269        _writer_bits::writeToken(*_os, it->first) << ' ';
1270        _writer_bits::writeToken(*_os, it->second->get());
1271        *_os << std::endl;
1272      }
1273    }
1274   
1275  public:
1276   
1277    /// \name Execution of the writer   
1278    /// @{
1279
1280    /// \brief Start the batch processing
1281    ///
1282    /// This function starts the batch processing
1283    void run() {
1284      if (!_skip_nodes) {
1285        writeNodes();
1286      }
1287      if (!_skip_edges) {     
1288        writeEdges();
1289      }
1290      writeAttributes();
1291    }
1292
1293    /// \brief Gives back the stream of the writer
1294    ///
1295    /// Gives back the stream of the writer
1296    std::ostream& ostream() {
1297      return *_os;
1298    }
1299
1300    /// @}
1301  };
1302
1303  /// \relates GraphWriter
1304  template <typename Graph>
1305  GraphWriter<Graph> graphWriter(std::ostream& os, Graph& graph) {
1306    GraphWriter<Graph> tmp(os, graph);
1307    return tmp;
1308  }
1309
1310  /// \relates GraphWriter
1311  template <typename Graph>
1312  GraphWriter<Graph> graphWriter(const std::string& fn, Graph& graph) {
1313    GraphWriter<Graph> tmp(fn, graph);
1314    return tmp;
1315  }
1316
1317  /// \relates GraphWriter
1318  template <typename Graph>
1319  GraphWriter<Graph> graphWriter(const char* fn, Graph& graph) {
1320    GraphWriter<Graph> tmp(fn, graph);
1321    return tmp;
1322  }
1323}
1324
1325#endif
Note: See TracBrowser for help on using the repository browser.