COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/lgf_writer.h @ 185:33e45a9b868c

Last change on this file since 185:33e45a9b868c was 185:33e45a9b868c, checked in by Balazs Dezso <deba@…>, 11 years ago

Fix skip*() functions is GraphWriters? (Ticket #107)

File size: 39.8 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      _skip_nodes = true;
607      return *this;
608    }
609
610    /// \brief Skip writing arc set
611    ///
612    /// The \c \@arcs section will be not written to the stream.
613    DigraphWriter& skipArcs() {
614      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
615      _skip_arcs = true;
616      return *this;
617    }
618
619    /// @}
620
621  private:
622
623    void writeNodes() {
624      _writer_bits::MapStorageBase<Node>* label = 0;
625      for (typename NodeMaps::iterator it = _node_maps.begin();
626           it != _node_maps.end(); ++it) {
627        if (it->first == "label") {
628          label = it->second;
629          break;
630        }
631      }
632
633      *_os << "@nodes";
634      if (!_nodes_caption.empty()) {
635        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
636      }
637      *_os << std::endl;
638
639      if (label == 0) {
640        *_os << "label" << '\t';
641      }
642      for (typename NodeMaps::iterator it = _node_maps.begin();
643           it != _node_maps.end(); ++it) {
644        _writer_bits::writeToken(*_os, it->first) << '\t';
645      }
646      *_os << std::endl;
647
648      std::vector<Node> nodes;
649      for (NodeIt n(_digraph); n != INVALID; ++n) {
650        nodes.push_back(n);
651      }
652     
653      if (label == 0) {
654        IdMap<Digraph, Node> id_map(_digraph);
655        _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
656        std::sort(nodes.begin(), nodes.end(), id_less);
657      } else {
658        label->sort(nodes);
659      }
660
661      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
662        Node n = nodes[i];
663        if (label == 0) {
664          std::ostringstream os;
665          os << _digraph.id(n);
666          _writer_bits::writeToken(*_os, os.str());
667          *_os << '\t';
668          _node_index.insert(std::make_pair(n, os.str()));
669        }
670        for (typename NodeMaps::iterator it = _node_maps.begin();
671             it != _node_maps.end(); ++it) {
672          std::string value = it->second->get(n);
673          _writer_bits::writeToken(*_os, value);
674          if (it->first == "label") {
675            _node_index.insert(std::make_pair(n, value));
676          }
677          *_os << '\t';
678        }
679        *_os << std::endl;
680      }
681    }
682
683    void createNodeIndex() {
684      _writer_bits::MapStorageBase<Node>* label = 0;
685      for (typename NodeMaps::iterator it = _node_maps.begin();
686           it != _node_maps.end(); ++it) {
687        if (it->first == "label") {
688          label = it->second;
689          break;
690        }
691      }
692
693      if (label == 0) {
694        for (NodeIt n(_digraph); n != INVALID; ++n) {
695          std::ostringstream os;
696          os << _digraph.id(n);
697          _node_index.insert(std::make_pair(n, os.str()));       
698        }       
699      } else {
700        for (NodeIt n(_digraph); n != INVALID; ++n) {
701          std::string value = label->get(n);     
702          _node_index.insert(std::make_pair(n, value));
703        }
704      }
705    }
706
707    void writeArcs() {
708      _writer_bits::MapStorageBase<Arc>* label = 0;
709      for (typename ArcMaps::iterator it = _arc_maps.begin();
710           it != _arc_maps.end(); ++it) {
711        if (it->first == "label") {
712          label = it->second;
713          break;
714        }
715      }
716
717      *_os << "@arcs";
718      if (!_arcs_caption.empty()) {
719        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
720      }
721      *_os << std::endl;
722
723      *_os << '\t' << '\t';
724      if (label == 0) {
725        *_os << "label" << '\t';
726      }
727      for (typename ArcMaps::iterator it = _arc_maps.begin();
728           it != _arc_maps.end(); ++it) {
729        _writer_bits::writeToken(*_os, it->first) << '\t';
730      }
731      *_os << std::endl;
732
733      std::vector<Arc> arcs;
734      for (ArcIt n(_digraph); n != INVALID; ++n) {
735        arcs.push_back(n);
736      }
737     
738      if (label == 0) {
739        IdMap<Digraph, Arc> id_map(_digraph);
740        _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
741        std::sort(arcs.begin(), arcs.end(), id_less);
742      } else {
743        label->sort(arcs);
744      }
745
746      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
747        Arc a = arcs[i];
748        _writer_bits::writeToken(*_os, _node_index.
749                                 find(_digraph.source(a))->second);
750        *_os << '\t';
751        _writer_bits::writeToken(*_os, _node_index.
752                                 find(_digraph.target(a))->second);
753        *_os << '\t';
754        if (label == 0) {
755          std::ostringstream os;
756          os << _digraph.id(a);
757          _writer_bits::writeToken(*_os, os.str());
758          *_os << '\t';
759          _arc_index.insert(std::make_pair(a, os.str()));
760        }
761        for (typename ArcMaps::iterator it = _arc_maps.begin();
762             it != _arc_maps.end(); ++it) {
763          std::string value = it->second->get(a);
764          _writer_bits::writeToken(*_os, value);
765          if (it->first == "label") {
766            _arc_index.insert(std::make_pair(a, value));
767          }
768          *_os << '\t';
769        }
770        *_os << std::endl;
771      }
772    }
773
774    void createArcIndex() {
775      _writer_bits::MapStorageBase<Arc>* label = 0;
776      for (typename ArcMaps::iterator it = _arc_maps.begin();
777           it != _arc_maps.end(); ++it) {
778        if (it->first == "label") {
779          label = it->second;
780          break;
781        }
782      }
783
784      if (label == 0) {
785        for (ArcIt a(_digraph); a != INVALID; ++a) {
786          std::ostringstream os;
787          os << _digraph.id(a);
788          _arc_index.insert(std::make_pair(a, os.str()));         
789        }       
790      } else {
791        for (ArcIt a(_digraph); a != INVALID; ++a) {
792          std::string value = label->get(a);     
793          _arc_index.insert(std::make_pair(a, value));
794        }
795      }
796    }
797
798    void writeAttributes() {
799      if (_attributes.empty()) return;
800      *_os << "@attributes";
801      if (!_attributes_caption.empty()) {
802        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
803      }
804      *_os << std::endl;
805      for (typename Attributes::iterator it = _attributes.begin();
806           it != _attributes.end(); ++it) {
807        _writer_bits::writeToken(*_os, it->first) << ' ';
808        _writer_bits::writeToken(*_os, it->second->get());
809        *_os << std::endl;
810      }
811    }
812   
813  public:
814   
815    /// \name Execution of the writer   
816    /// @{
817
818    /// \brief Start the batch processing
819    ///
820    /// This function starts the batch processing
821    void run() {
822      if (!_skip_nodes) {
823        writeNodes();
824      } else {
825        createNodeIndex();
826      }
827      if (!_skip_arcs) {     
828        writeArcs();
829      } else {
830        createArcIndex();
831      }
832      writeAttributes();
833    }
834
835    /// \brief Gives back the stream of the writer
836    ///
837    /// Gives back the stream of the writer
838    std::ostream& ostream() {
839      return *_os;
840    }
841
842    /// @}
843  };
844
845  /// \relates DigraphWriter
846  template <typename Digraph>
847  DigraphWriter<Digraph> digraphWriter(std::ostream& os, Digraph& digraph) {
848    DigraphWriter<Digraph> tmp(os, digraph);
849    return tmp;
850  }
851
852  /// \relates DigraphWriter
853  template <typename Digraph>
854  DigraphWriter<Digraph> digraphWriter(const std::string& fn,
855                                       Digraph& digraph) {
856    DigraphWriter<Digraph> tmp(fn, digraph);
857    return tmp;
858  }
859
860  /// \relates DigraphWriter
861  template <typename Digraph>
862  DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
863    DigraphWriter<Digraph> tmp(fn, digraph);
864    return tmp;
865  }
866
867  /// \ingroup lemon_io
868  /// 
869  /// \brief LGF writer for directed graphs
870  ///
871  /// This utility writes an \ref lgf-format "LGF" file.
872  template <typename _Graph>
873  class GraphWriter {
874  public:
875
876    typedef _Graph Graph;
877    TEMPLATE_GRAPH_TYPEDEFS(Graph);
878   
879  private:
880
881
882    std::ostream* _os;
883    bool local_os;
884
885    Graph& _graph;
886
887    std::string _nodes_caption;
888    std::string _edges_caption;
889    std::string _attributes_caption;
890   
891    typedef std::map<Node, std::string> NodeIndex;
892    NodeIndex _node_index;
893    typedef std::map<Edge, std::string> EdgeIndex;
894    EdgeIndex _edge_index;
895
896    typedef std::vector<std::pair<std::string,
897      _writer_bits::MapStorageBase<Node>* > > NodeMaps;   
898    NodeMaps _node_maps;
899
900    typedef std::vector<std::pair<std::string,
901      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
902    EdgeMaps _edge_maps;
903
904    typedef std::vector<std::pair<std::string,
905      _writer_bits::ValueStorageBase*> > Attributes;
906    Attributes _attributes;
907
908    bool _skip_nodes;
909    bool _skip_edges;
910
911  public:
912
913    /// \brief Constructor
914    ///
915    /// Construct a directed graph writer, which writes to the given
916    /// output stream.
917    GraphWriter(std::ostream& is, Graph& graph)
918      : _os(&is), local_os(false), _graph(graph),
919        _skip_nodes(false), _skip_edges(false) {}
920
921    /// \brief Constructor
922    ///
923    /// Construct a directed graph writer, which writes to the given
924    /// output file.
925    GraphWriter(const std::string& fn, Graph& graph)
926      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
927        _skip_nodes(false), _skip_edges(false) {}
928
929    /// \brief Constructor
930    ///
931    /// Construct a directed graph writer, which writes to the given
932    /// output file.
933    GraphWriter(const char* fn, Graph& graph)
934      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
935        _skip_nodes(false), _skip_edges(false) {}
936
937    /// \brief Copy constructor
938    ///
939    /// The copy constructor transfers all data from the other writer,
940    /// therefore the copied writer will not be usable more.
941    GraphWriter(GraphWriter& other)
942      : _os(other._os), local_os(other.local_os), _graph(other._graph),
943        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
944
945      other._os = 0;
946      other.local_os = false;
947
948      _node_index.swap(other._node_index);
949      _edge_index.swap(other._edge_index);
950
951      _node_maps.swap(other._node_maps);
952      _edge_maps.swap(other._edge_maps);
953      _attributes.swap(other._attributes);
954
955      _nodes_caption = other._nodes_caption;
956      _edges_caption = other._edges_caption;
957      _attributes_caption = other._attributes_caption;
958    }
959
960    /// \brief Destructor
961    ~GraphWriter() {
962      for (typename NodeMaps::iterator it = _node_maps.begin();
963           it != _node_maps.end(); ++it) {
964        delete it->second;
965      }
966
967      for (typename EdgeMaps::iterator it = _edge_maps.begin();
968           it != _edge_maps.end(); ++it) {
969        delete it->second;
970      }
971
972      for (typename Attributes::iterator it = _attributes.begin();
973           it != _attributes.end(); ++it) {
974        delete it->second;
975      }
976
977      if (local_os) {
978        delete _os;
979      }
980    }
981
982  private:
983   
984    GraphWriter& operator=(const GraphWriter&);
985
986  public:
987
988    /// \name Writing rules
989    /// @{
990   
991    /// \brief Node map reading rule
992    ///
993    /// Add a node map reading rule to the writer.
994    template <typename Map>
995    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
996      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
997      _writer_bits::MapStorageBase<Node>* storage =
998        new _writer_bits::MapStorage<Node, Map>(map);
999      _node_maps.push_back(std::make_pair(caption, storage));
1000      return *this;
1001    }
1002
1003    /// \brief Node map writing rule
1004    ///
1005    /// Add a node map writing rule with specialized converter to the
1006    /// writer.
1007    template <typename Map, typename Converter>
1008    GraphWriter& nodeMap(const std::string& caption, const Map& map,
1009                           const Converter& converter = Converter()) {
1010      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1011      _writer_bits::MapStorageBase<Node>* storage =
1012        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
1013      _node_maps.push_back(std::make_pair(caption, storage));
1014      return *this;
1015    }
1016
1017    /// \brief Edge map writing rule
1018    ///
1019    /// Add an edge map writing rule to the writer.
1020    template <typename Map>
1021    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
1022      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1023      _writer_bits::MapStorageBase<Edge>* storage =
1024        new _writer_bits::MapStorage<Edge, Map>(map);
1025      _edge_maps.push_back(std::make_pair(caption, storage));
1026      return *this;
1027    }
1028
1029    /// \brief Edge map writing rule
1030    ///
1031    /// Add an edge map writing rule with specialized converter to the
1032    /// writer.
1033    template <typename Map, typename Converter>
1034    GraphWriter& edgeMap(const std::string& caption, const Map& map,
1035                          const Converter& converter = Converter()) {
1036      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1037      _writer_bits::MapStorageBase<Edge>* storage =
1038        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
1039      _edge_maps.push_back(std::make_pair(caption, storage));
1040      return *this;
1041    }
1042
1043    /// \brief Arc map writing rule
1044    ///
1045    /// Add an arc map writing rule to the writer.
1046    template <typename Map>
1047    GraphWriter& arcMap(const std::string& caption, const Map& map) {
1048      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1049      _writer_bits::MapStorageBase<Edge>* forward_storage =
1050        new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1051      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1052      _writer_bits::MapStorageBase<Edge>* backward_storage =
1053        new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1054      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1055      return *this;
1056    }
1057
1058    /// \brief Arc map writing rule
1059    ///
1060    /// Add an arc map writing rule with specialized converter to the
1061    /// writer.
1062    template <typename Map, typename Converter>
1063    GraphWriter& arcMap(const std::string& caption, const Map& map,
1064                          const Converter& converter = Converter()) {
1065      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1066      _writer_bits::MapStorageBase<Edge>* forward_storage =
1067        new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1068        (_graph, map, converter);
1069      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1070      _writer_bits::MapStorageBase<Edge>* backward_storage =
1071        new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1072        (_graph, map, converter);
1073      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1074      return *this;
1075    }
1076
1077    /// \brief Attribute writing rule
1078    ///
1079    /// Add an attribute writing rule to the writer.
1080    template <typename Value>
1081    GraphWriter& attribute(const std::string& caption, const Value& value) {
1082      _writer_bits::ValueStorageBase* storage =
1083        new _writer_bits::ValueStorage<Value>(value);
1084      _attributes.push_back(std::make_pair(caption, storage));
1085      return *this;
1086    }
1087
1088    /// \brief Attribute writing rule
1089    ///
1090    /// Add an attribute writing rule with specialized converter to the
1091    /// writer.
1092    template <typename Value, typename Converter>
1093    GraphWriter& attribute(const std::string& caption, const Value& value,
1094                             const Converter& converter = Converter()) {
1095      _writer_bits::ValueStorageBase* storage =
1096        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1097      _attributes.push_back(std::make_pair(caption, storage));
1098      return *this;
1099    }
1100
1101    /// \brief Node writing rule
1102    ///
1103    /// Add a node writing rule to the writer.
1104    GraphWriter& node(const std::string& caption, const Node& node) {
1105      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1106      Converter converter(_node_index);
1107      _writer_bits::ValueStorageBase* storage =
1108        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1109      _attributes.push_back(std::make_pair(caption, storage));
1110      return *this;
1111    }
1112
1113    /// \brief Edge writing rule
1114    ///
1115    /// Add an edge writing rule to writer.
1116    GraphWriter& edge(const std::string& caption, const Edge& edge) {
1117      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
1118      Converter converter(_edge_index);
1119      _writer_bits::ValueStorageBase* storage =
1120        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
1121      _attributes.push_back(std::make_pair(caption, storage));
1122      return *this;
1123    }
1124
1125    /// \brief Arc writing rule
1126    ///
1127    /// Add an arc writing rule to writer.
1128    GraphWriter& arc(const std::string& caption, const Arc& arc) {
1129      typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
1130      Converter converter(_graph, _edge_index);
1131      _writer_bits::ValueStorageBase* storage =
1132        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
1133      _attributes.push_back(std::make_pair(caption, storage));
1134      return *this;
1135    }
1136
1137    /// \name Select section by name
1138    /// @{
1139
1140    /// \brief Set \c \@nodes section to be read
1141    ///
1142    /// Set \c \@nodes section to be read
1143    GraphWriter& nodes(const std::string& caption) {
1144      _nodes_caption = caption;
1145      return *this;
1146    }
1147
1148    /// \brief Set \c \@edges section to be read
1149    ///
1150    /// Set \c \@edges section to be read
1151    GraphWriter& edges(const std::string& caption) {
1152      _edges_caption = caption;
1153      return *this;
1154    }
1155
1156    /// \brief Set \c \@attributes section to be read
1157    ///
1158    /// Set \c \@attributes section to be read
1159    GraphWriter& attributes(const std::string& caption) {
1160      _attributes_caption = caption;
1161      return *this;
1162    }
1163
1164    /// \name Skipping section
1165    /// @{
1166
1167    /// \brief Skip writing the node set
1168    ///
1169    /// The \c \@nodes section will be not written to the stream.
1170    GraphWriter& skipNodes() {
1171      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
1172      _skip_nodes = true;
1173      return *this;
1174    }
1175
1176    /// \brief Skip writing edge set
1177    ///
1178    /// The \c \@edges section will be not written to the stream.
1179    GraphWriter& skipEdges() {
1180      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
1181      _skip_edges = true;
1182      return *this;
1183    }
1184
1185    /// @}
1186
1187  private:
1188
1189    void writeNodes() {
1190      _writer_bits::MapStorageBase<Node>* label = 0;
1191      for (typename NodeMaps::iterator it = _node_maps.begin();
1192           it != _node_maps.end(); ++it) {
1193        if (it->first == "label") {
1194          label = it->second;
1195          break;
1196        }
1197      }
1198
1199      *_os << "@nodes";
1200      if (!_nodes_caption.empty()) {
1201        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
1202      }
1203      *_os << std::endl;
1204
1205      if (label == 0) {
1206        *_os << "label" << '\t';
1207      }
1208      for (typename NodeMaps::iterator it = _node_maps.begin();
1209           it != _node_maps.end(); ++it) {
1210        _writer_bits::writeToken(*_os, it->first) << '\t';
1211      }
1212      *_os << std::endl;
1213
1214      std::vector<Node> nodes;
1215      for (NodeIt n(_graph); n != INVALID; ++n) {
1216        nodes.push_back(n);
1217      }
1218     
1219      if (label == 0) {
1220        IdMap<Graph, Node> id_map(_graph);
1221        _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
1222        std::sort(nodes.begin(), nodes.end(), id_less);
1223      } else {
1224        label->sort(nodes);
1225      }
1226
1227      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
1228        Node n = nodes[i];
1229        if (label == 0) {
1230          std::ostringstream os;
1231          os << _graph.id(n);
1232          _writer_bits::writeToken(*_os, os.str());
1233          *_os << '\t';
1234          _node_index.insert(std::make_pair(n, os.str()));
1235        }
1236        for (typename NodeMaps::iterator it = _node_maps.begin();
1237             it != _node_maps.end(); ++it) {
1238          std::string value = it->second->get(n);
1239          _writer_bits::writeToken(*_os, value);
1240          if (it->first == "label") {
1241            _node_index.insert(std::make_pair(n, value));
1242          }
1243          *_os << '\t';
1244        }
1245        *_os << std::endl;
1246      }
1247    }
1248
1249    void createNodeIndex() {
1250      _writer_bits::MapStorageBase<Node>* label = 0;
1251      for (typename NodeMaps::iterator it = _node_maps.begin();
1252           it != _node_maps.end(); ++it) {
1253        if (it->first == "label") {
1254          label = it->second;
1255          break;
1256        }
1257      }
1258
1259      if (label == 0) {
1260        for (NodeIt n(_graph); n != INVALID; ++n) {
1261          std::ostringstream os;
1262          os << _graph.id(n);
1263          _node_index.insert(std::make_pair(n, os.str()));       
1264        }       
1265      } else {
1266        for (NodeIt n(_graph); n != INVALID; ++n) {
1267          std::string value = label->get(n);     
1268          _node_index.insert(std::make_pair(n, value));
1269        }
1270      }
1271    }
1272
1273    void writeEdges() {
1274      _writer_bits::MapStorageBase<Edge>* label = 0;
1275      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1276           it != _edge_maps.end(); ++it) {
1277        if (it->first == "label") {
1278          label = it->second;
1279          break;
1280        }
1281      }
1282
1283      *_os << "@edges";
1284      if (!_edges_caption.empty()) {
1285        _writer_bits::writeToken(*_os << ' ', _edges_caption);
1286      }
1287      *_os << std::endl;
1288
1289      *_os << '\t' << '\t';
1290      if (label == 0) {
1291        *_os << "label" << '\t';
1292      }
1293      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1294           it != _edge_maps.end(); ++it) {
1295        _writer_bits::writeToken(*_os, it->first) << '\t';
1296      }
1297      *_os << std::endl;
1298
1299      std::vector<Edge> edges;
1300      for (EdgeIt n(_graph); n != INVALID; ++n) {
1301        edges.push_back(n);
1302      }
1303     
1304      if (label == 0) {
1305        IdMap<Graph, Edge> id_map(_graph);
1306        _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
1307        std::sort(edges.begin(), edges.end(), id_less);
1308      } else {
1309        label->sort(edges);
1310      }
1311
1312      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
1313        Edge e = edges[i];
1314        _writer_bits::writeToken(*_os, _node_index.
1315                                 find(_graph.u(e))->second);
1316        *_os << '\t';
1317        _writer_bits::writeToken(*_os, _node_index.
1318                                 find(_graph.v(e))->second);
1319        *_os << '\t';
1320        if (label == 0) {
1321          std::ostringstream os;
1322          os << _graph.id(e);
1323          _writer_bits::writeToken(*_os, os.str());
1324          *_os << '\t';
1325          _edge_index.insert(std::make_pair(e, os.str()));
1326        }
1327        for (typename EdgeMaps::iterator it = _edge_maps.begin();
1328             it != _edge_maps.end(); ++it) {
1329          std::string value = it->second->get(e);
1330          _writer_bits::writeToken(*_os, value);
1331          if (it->first == "label") {
1332            _edge_index.insert(std::make_pair(e, value));
1333          }
1334          *_os << '\t';
1335        }
1336        *_os << std::endl;
1337      }
1338    }
1339
1340    void createEdgeIndex() {
1341      _writer_bits::MapStorageBase<Edge>* label = 0;
1342      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1343           it != _edge_maps.end(); ++it) {
1344        if (it->first == "label") {
1345          label = it->second;
1346          break;
1347        }
1348      }
1349
1350      if (label == 0) {
1351        for (EdgeIt e(_graph); e != INVALID; ++e) {
1352          std::ostringstream os;
1353          os << _graph.id(e);
1354          _edge_index.insert(std::make_pair(e, os.str()));       
1355        }       
1356      } else {
1357        for (EdgeIt e(_graph); e != INVALID; ++e) {
1358          std::string value = label->get(e);     
1359          _edge_index.insert(std::make_pair(e, value));
1360        }
1361      }
1362    }
1363
1364    void writeAttributes() {
1365      if (_attributes.empty()) return;
1366      *_os << "@attributes";
1367      if (!_attributes_caption.empty()) {
1368        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
1369      }
1370      *_os << std::endl;
1371      for (typename Attributes::iterator it = _attributes.begin();
1372           it != _attributes.end(); ++it) {
1373        _writer_bits::writeToken(*_os, it->first) << ' ';
1374        _writer_bits::writeToken(*_os, it->second->get());
1375        *_os << std::endl;
1376      }
1377    }
1378   
1379  public:
1380   
1381    /// \name Execution of the writer   
1382    /// @{
1383
1384    /// \brief Start the batch processing
1385    ///
1386    /// This function starts the batch processing
1387    void run() {
1388      if (!_skip_nodes) {
1389        writeNodes();
1390      } else {
1391        createNodeIndex();
1392      }
1393      if (!_skip_edges) {     
1394        writeEdges();
1395      } else {
1396        createEdgeIndex();
1397      }
1398      writeAttributes();
1399    }
1400
1401    /// \brief Gives back the stream of the writer
1402    ///
1403    /// Gives back the stream of the writer
1404    std::ostream& ostream() {
1405      return *_os;
1406    }
1407
1408    /// @}
1409  };
1410
1411  /// \relates GraphWriter
1412  template <typename Graph>
1413  GraphWriter<Graph> graphWriter(std::ostream& os, Graph& graph) {
1414    GraphWriter<Graph> tmp(os, graph);
1415    return tmp;
1416  }
1417
1418  /// \relates GraphWriter
1419  template <typename Graph>
1420  GraphWriter<Graph> graphWriter(const std::string& fn, Graph& graph) {
1421    GraphWriter<Graph> tmp(fn, graph);
1422    return tmp;
1423  }
1424
1425  /// \relates GraphWriter
1426  template <typename Graph>
1427  GraphWriter<Graph> graphWriter(const char* fn, Graph& graph) {
1428    GraphWriter<Graph> tmp(fn, graph);
1429    return tmp;
1430  }
1431}
1432
1433#endif
Note: See TracBrowser for help on using the repository browser.