COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_writer.h @ 1402:655d8e78454d

Last change on this file since 1402:655d8e78454d was 1402:655d8e78454d, checked in by Alpar Juttner, 19 years ago

Special maps' placement in the headers and in the doxigen modules
reorganized

File size: 16.0 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/graph_writer.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17///\ingroup io_group
18///\file
19///\brief Lemon Graph Format writer.
20
21#ifndef LEMON_GRAPH_WRITER_H
22#define LEMON_GRAPH_WRITER_H
23
24#include <iostream>
25#include <sstream>
26
27#include <map>
28#include <vector>
29
30#include <memory>
31
32#include <lemon/graph_utils.h>
33
34#include <lemon/invalid.h>
35#include <lemon/error.h>
36
37
38namespace lemon {
39
40  /// \addtogroup io_group
41  /// @{
42
43  /// \brief Standard WriterTraits for the GraphWriter class.
44  ///
45  /// Standard WriterTraits for the GraphWriter class.
46  /// It defines standard writing method for all type of value.
47  /// \author Balazs Dezso
48  struct DefaultWriterTraits {
49
50    /// \brief Template class for writing an value.
51    ///
52    /// Template class for writing an value.
53    /// \author Balazs Dezso
54    template <typename _Value>
55    struct Writer {
56      /// The value type.
57      typedef _Value Value;
58
59      /// \brief Writes a value to the given stream.
60      ///
61      /// Writes a value to the given stream.
62      void write(std::ostream& os, const Value& value) {
63        os << value << '\t';
64      }
65    };
66
67    /// \brief Returns wheter this name is an ID map name.
68    ///
69    /// Returns wheter this name is an ID map name.
70    static bool idMapName(const std::string& name) {
71      return name == "id";
72    }
73
74  };
75
76
77  /// \brief Writer class for quoted strings.
78  ///
79  /// Writer class for quoted strings. It can process the escape
80  /// sequences in the string.
81  /// \author Balazs Dezso
82  class QuotedStringWriter {
83  public:
84    typedef std::string Value;
85
86    /// \brief Constructor for the writer.
87    ///
88    /// Constructor for the writer. If the given parameter is true
89    /// the writer creates escape sequences from special characters.
90    QuotedStringWriter(bool _escaped = true) : escaped(_escaped) {}
91
92    /// \brief Writes a quoted string to the given stream.
93    ///
94    /// Writes a quoted string to the given stream.
95    void write(std::ostream& os, const std::string& value) {
96      os << "\"";
97      if (escaped) {
98        std::ostringstream ls;
99        for (int i = 0; i < (int)value.size(); ++i) {
100          writeEscape(ls, value[i]);
101        }
102        os << ls.str();
103      } else {
104        os << value;
105      }
106      os << "\"";
107    }
108
109  private:
110   
111    static void writeEscape(std::ostream& os, char c) {
112      switch (c) {
113      case '\\':
114        os << "\\\\";
115        return;
116      case '\"':
117        os << "\\\"";
118        return;
119      case '\'':
120        os << "\\\'";
121        return;
122      case '\?':
123        os << "\\\?";
124        return;
125      case '\a':
126        os << "\\a";
127        return;
128      case '\b':
129        os << "\\b";
130        return;
131      case '\f':
132        os << "\\f";
133        return;
134      case '\r':
135        os << "\\r";
136        return;
137      case '\n':
138        os << "\\n";
139        return;
140      case '\t':
141        os << "\\t";
142        return;
143      case '\v':
144        os << "\\v";
145        return;
146      default:
147        if (c < 0x20) {
148          os << '\\' << std::oct << (int)c;
149        } else {
150          os << c;
151        }
152        return;
153      }     
154    }
155  private:
156    bool escaped;
157  };
158
159  class GUIWriter {
160  public:
161    virtual void write(std::ostream& os) = 0;
162  };
163
164 
165  /// \brief The graph writer class.
166  ///
167  /// The \c GraphWriter class provides the graph output. To write a graph
168  /// you should first give writing commands for the writer. You can declare
169  /// write command as \c NodeMap or \c EdgeMap writing and labeled Node and
170  /// Edge writing.
171  ///
172  /// \code
173  /// GraphWriter<ListGraph> writer(std::cout, graph);
174  /// \endcode
175  ///
176  /// The \c writeNodeMap() function declares a \c NodeMap writing
177  /// command in the \c GraphWriter. You should give as parameter
178  /// the name of the map and the map object. The NodeMap writing
179  /// command with name "id" should write a unique map because it
180  /// is regarded as ID map.
181  ///
182  /// \code
183  /// IdMap<ListGraph, Node> nodeIdMap;
184  /// writer.writeNodeMap("id", nodeIdMap);
185  ///
186  /// writer.writeNodeMap("x-coord", xCoordMap);
187  /// writer.writeNodeMap("y-coord", yCoordMap);
188  /// writer.writeNodeMap("color", colorMap);
189  /// \endcode
190  ///
191  /// With the \c writeEdgeMap() member function you can give an edge map
192  /// writing command similar to the NodeMaps.
193  ///
194  /// \code
195  /// DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> >
196  ///   edgeDescMap(graph);
197  /// writer.writeEdgeMap("descriptor", edgeDescMap);
198  ///
199  /// writer.writeEdgeMap("weight", weightMap);
200  /// writer.writeEdgeMap("label", labelMap);
201  /// \endcode
202  ///
203  /// With \c writeNode() and \c writeEdge() functions you can
204  /// point out Nodes and Edges in the graph. By example, you can
205  /// write out the source and target of the graph.
206  ///
207  /// \code
208  /// writer.writeNode("source", sourceNode);
209  /// writer.writeNode("target", targetNode);
210  ///
211  /// writer.writeEdge("observed", edge);
212  /// \endcode
213  ///
214  /// After you give all write commands you must call the \c run() member
215  /// function, which execute all the writer commands.
216  ///
217  /// \code
218  /// writer.run();
219  /// \endcode
220  ///
221  /// \see DefaultWriterTraits
222  /// \see QuotedStringWriter
223  /// \see IdMap
224  /// \see DescriptorMap
225  /// \see \ref GraphWriter
226  /// \see \ref graph-io-page
227  /// \author Balazs Dezso
228  template <typename _Graph, typename _WriterTraits = DefaultWriterTraits>
229  class GraphWriter {
230  public:
231   
232    typedef _Graph Graph;
233    typedef typename Graph::Node Node;
234    typedef typename Graph::NodeIt NodeIt;
235    typedef typename Graph::Edge Edge;
236    typedef typename Graph::EdgeIt EdgeIt;
237
238    typedef _WriterTraits WriterTraits;
239 
240    /// \brief Construct a new GraphWriter.
241    ///
242    /// Construct a new GraphWriter. It writes from the given map,
243    /// it constructs the given map and it use the given writer as the
244    /// default skipper.
245    GraphWriter(std::ostream& _os, const Graph& _graph)
246      : gui_writer(0), os(_os), graph(_graph){}
247
248
249    /// \brief Destruct the graph writer.
250    ///
251    /// Destruct the graph writer.
252    ~GraphWriter() {
253      for (typename NodeMapWriters::iterator it = node_map_writers.begin();
254           it != node_map_writers.end(); ++it) {
255        delete it->second;
256      }
257
258      for (typename EdgeMapWriters::iterator it = edge_map_writers.begin();
259           it != edge_map_writers.end(); ++it) {
260        delete it->second;
261      }
262
263    }
264
265    // Node map rules
266
267    /// \brief Add a new node map writer command for the writer.
268    ///
269    /// Add a new node map writer command for the writer.
270    template <typename Map>
271    GraphWriter& writeNodeMap(std::string name, const Map& map) {
272      return writeNodeMap<typename WriterTraits::template Writer<
273        typename Map::Value>, Map>(name, map);
274    }
275
276    /// \brief Add a new node map writer command for the writer.
277    ///
278    /// Add a new node map writer command for the writer.
279    template <typename Writer, typename Map>
280    GraphWriter& writeNodeMap(std::string name, const Map& map,
281                              const Writer& writer = Writer()) {
282      node_map_writers.push_back(
283        make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));
284      return *this;
285    }
286
287    // Edge map rules
288
289    /// \brief Add a new edge map writer command for the writer.
290    ///
291    /// Add a new edge map writer command for the writer.
292    template <typename Map>
293    GraphWriter& writeEdgeMap(std::string name, const Map& map) {
294      return writeEdgeMap<typename WriterTraits::template Writer<
295        typename Map::Value>, Map>(name, map);
296    }
297
298
299    /// \brief Add a new edge map writer command for the writer.
300    ///
301    /// Add a new edge map writer command for the writer.
302    template <typename Writer, typename Map>
303    GraphWriter& writeEdgeMap(std::string name,
304                            const Map& map, const Writer& writer = Writer()) {
305      edge_map_writers.push_back(make_pair(name,
306        new MapWriter<Edge, Map, Writer>(map, writer)));
307      return *this;
308    }
309
310    /// \brief Add a new labeled node writer for the writer.
311    ///
312    /// Add a new labeled node writer for the writer.
313    GraphWriter& writeNode(std::string name, const Node& node) {
314      node_writers.push_back(make_pair(name, node));
315      return *this;
316    }
317
318    /// \brief Add a new labeled edge writer for the writer.
319    ///
320    /// Add a new labeled edge writer for the writer.
321    GraphWriter& writeEdge(std::string name, const Edge& edge) {
322      edge_writers.push_back(make_pair(name, edge));
323      return *this;
324    }
325
326    GraphWriter& writeGUI(const GUIWriter& writer) {
327      gui_writer = &writer;
328    }
329
330    /// \brief Executes the writer commands.
331    ///
332    /// Executes the writer commands.
333    void run() {   
334      WriterBase<Node>* nodeWriter = 0;
335      WriterBase<Edge>* edgeWriter = 0;
336      writeNodeSet(nodeWriter);
337      writeEdgeSet(nodeWriter, edgeWriter);
338      writeNodes(nodeWriter);
339      writeEdges(edgeWriter);
340      writeGUI();
341      os << "@end" << std::endl;
342    }
343
344  private:
345
346    template <class _Item>
347    class WriterBase {
348    public:
349      typedef _Item Item;
350      virtual void write(std::ostream&, const Item&) = 0;
351    };
352
353    template <class _Item, typename _Map, typename _Writer>
354    class MapWriter : public WriterBase<_Item> {
355    public:
356      typedef _Map Map;
357      typedef _Writer Writer;
358      typedef typename Writer::Value Value;
359      typedef _Item Item;
360     
361      const Map& map;
362      Writer writer;
363
364      MapWriter(const Map& _map, const Writer& _writer)
365        : map(_map), writer(_writer) {}
366
367
368      virtual void write(std::ostream& os, const Item& item) {
369        writer.write(os, map[item]);
370      }
371
372    };
373
374    void writeNodeSet(WriterBase<Node>* & nodeWriter) {
375      if (node_map_writers.size() == 0) return;
376      os << "@nodeset" << std::endl;
377      for (int i = 0; i < (int)node_map_writers.size(); ++i) {
378        const std::string& id = node_map_writers[i].first;
379        os << id << '\t';
380        if (WriterTraits::idMapName(id) && nodeWriter == 0) {
381          nodeWriter = node_map_writers[i].second;
382        }
383      }
384      os << std::endl;
385      for (NodeIt it(graph); it != INVALID; ++it) {
386        for (int i = 0; i < (int)node_map_writers.size(); ++i) {
387          node_map_writers[i].second->write(os, it);
388        }
389        os << std::endl;
390      }
391
392    }
393
394    void writeEdgeSet(WriterBase<Node>* nodeWriter,
395                      WriterBase<Edge>* & edgeWriter) {
396      if (edge_map_writers.size() == 0) return;
397      if (nodeWriter == 0) {
398        throw DataFormatError("Cannot find node id map");
399      }
400      os << "@edgeset" << std::endl;
401      os << "\t\t";
402      for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
403        const std::string& id = edge_map_writers[i].first;
404        os << id << '\t';
405        if (WriterTraits::idMapName(id) && edgeWriter == 0) {
406          edgeWriter = edge_map_writers[i].second;
407        }
408      }
409      os << std::endl;
410      for (EdgeIt it(graph); it != INVALID; ++it) {
411        nodeWriter->write(os, graph.source(it));
412        nodeWriter->write(os, graph.target(it));
413        for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
414          edge_map_writers[i].second->write(os, it);
415        }
416        os << std::endl;
417      }
418    }
419
420    void writeNodes(WriterBase<Node>* nodeWriter) {
421      if (node_writers.size() == 0) return;
422      if (nodeWriter == 0) {
423        throw DataFormatError("Cannot find node id map");
424      }
425      os << "@nodes" << std::endl;
426      for (int i = 0; i < (int)node_writers.size(); ++i) {
427        os << node_writers[i].first << '\t';
428        nodeWriter->write(os, node_writers[i].second);
429        os << std::endl;
430      }
431    }
432
433    void writeEdges(WriterBase<Edge>* edgeWriter) {
434      if (edge_writers.size() == 0) return;
435      if (edgeWriter == 0) {
436        throw DataFormatError("Cannot find node id map");
437      }
438      os << "@edges" << std::endl;
439      for (int i = 0; i < (int)edge_writers.size(); ++i) {
440        os << edge_writers[i].first << '\t';
441        edgeWriter->write(os, edge_writers[i].second);
442        os << std::endl;
443      }
444    }
445   
446    void writeGUI() {     
447      if (gui_writer) {
448        os << "@gui" << std::endl;
449        gui_writer->write(os);
450      }
451    }
452
453
454
455    typedef std::vector< std::pair<std::string, WriterBase<Node>*> >
456      NodeMapWriters;
457    NodeMapWriters node_map_writers;
458
459    typedef std::vector< std::pair<std::string, WriterBase<Edge>*> >
460      EdgeMapWriters;
461    EdgeMapWriters edge_map_writers;
462
463    typedef std::vector<std::pair<std::string, Node> > NodeWriters;
464    NodeWriters node_writers;
465
466    typedef std::vector<std::pair<std::string, Edge> > EdgeWriters;
467    EdgeWriters edge_writers;
468
469    GUIWriter* gui_writer;
470
471    std::ostream& os;
472    const Graph& graph;
473
474  };
475
476  /// \brief Write a graph to the output.
477  ///
478  /// Write a graph to the output.
479  /// \param os The output stream.
480  /// \param g The graph.
481  /// \param capacity The capacity map.
482  /// \param s The source node.
483  /// \param t The target node.
484  /// \param cost The cost map.
485  template<typename Graph, typename CapacityMap, typename CostMap>
486  void writeGraph(std::ostream& os, const Graph &g,
487                  const CapacityMap& capacity, const typename Graph::Node &s,
488                  const typename Graph::Node &t, const CostMap& cost) {
489    GraphWriter<Graph> writer(os, g);
490    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
491    writer.writeNodeMap("id", nodeIdMap);
492    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
493    writer.writeEdgeMap("id", edgeIdMap);
494    writer.writeEdgeMap("capacity", capacity);
495    writer.writeEdgeMap("cost", cost);
496    writer.writeNode("source", s);
497    writer.writeNode("target", t);
498    writer.run();
499  }
500
501  /// \brief Write a graph to the output.
502  ///
503  /// Write a graph to the output.
504  /// \param os The output stream.
505  /// \param g The graph.
506  /// \param capacity The capacity map.
507  /// \param s The source node.
508  /// \param t The target node.
509  template<typename Graph, typename CapacityMap>
510  void writeGraph(std::ostream& os, const Graph &g,
511                  const CapacityMap& capacity, const typename Graph::Node &s,
512                  const typename Graph::Node &t) {
513    GraphWriter<Graph> writer(os, g);
514    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
515    writer.writeNodeMap("id", nodeIdMap);
516    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
517    writer.writeEdgeMap("id", edgeIdMap);
518    writer.writeEdgeMap("capacity", capacity);
519    writer.writeNode("source", s);
520    writer.writeNode("target", t);
521    writer.run();
522  }
523
524  /// \brief Write a graph to the output.
525  ///
526  /// Write a graph to the output.
527  /// \param os The output stream.
528  /// \param g The graph.
529  /// \param capacity The capacity map.
530  /// \param s The source node.
531  template<typename Graph, typename CapacityMap>
532  void writeGraph(std::ostream& os, const Graph &g,
533                  const CapacityMap& capacity, const typename Graph::Node &s) {
534    GraphWriter<Graph> writer(os, g);
535    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
536    writer.writeNodeMap("id", nodeIdMap);
537    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
538    writer.writeEdgeMap("id", edgeIdMap);
539    writer.writeEdgeMap("capacity", capacity);
540    writer.writeNode("source", s);
541    writer.run();
542  }
543
544  /// \brief Write a graph to the output.
545  ///
546  /// Write a graph to the output.
547  /// \param os The output stream.
548  /// \param g The graph.
549  /// \param capacity The capacity map.
550  template<typename Graph, typename CapacityMap>
551  void writeGraph(std::ostream& os, const Graph &g,
552                  const CapacityMap& capacity) {
553    GraphWriter<Graph> writer(os, g);
554    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
555    writer.writeNodeMap("id", nodeIdMap);
556    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
557    writer.writeEdgeMap("id", edgeIdMap);
558    writer.writeEdgeMap("capacity", capacity);
559    writer.run();
560  }
561
562  /// \brief Write a graph to the output.
563  ///
564  /// Write a graph to the output.
565  /// \param os The output stream.
566  /// \param g The graph.
567  template<typename Graph>
568  void writeGraph(std::ostream& os, const Graph &g) {
569    GraphWriter<Graph> writer(os, g);
570    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
571    writer.writeNodeMap("id", nodeIdMap);
572    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
573    writer.writeEdgeMap("id", edgeIdMap);
574    writer.run();
575  }
576
577  /// @}
578
579}
580
581#endif
Note: See TracBrowser for help on using the repository browser.