COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_writer.h @ 1394:f0c48d7fa73d

Last change on this file since 1394:f0c48d7fa73d was 1394:f0c48d7fa73d, checked in by Balazs Dezso, 16 years ago

Modifying the interface.
add -> read, write

File size: 15.7 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/map_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 
160  /// \brief The graph writer class.
161  ///
162  /// The \c GraphWriter class provides the graph output. To write a graph
163  /// you should first give writing commands for the writer. You can declare
164  /// write command as \c NodeMap or \c EdgeMap writing and labeled Node and
165  /// Edge writing.
166  ///
167  /// \code
168  /// GraphWriter<ListGraph> writer(std::cout, graph);
169  /// \endcode
170  ///
171  /// The \c writeNodeMap() function declares a \c NodeMap writing
172  /// command in the \c GraphWriter. You should give as parameter
173  /// the name of the map and the map object. The NodeMap writing
174  /// command with name "id" should write a unique map because it
175  /// is regarded as ID map.
176  ///
177  /// \code
178  /// IdMap<ListGraph, Node> nodeIdMap;
179  /// writer.writeNodeMap("id", nodeIdMap);
180  ///
181  /// writer.writeNodeMap("x-coord", xCoordMap);
182  /// writer.writeNodeMap("y-coord", yCoordMap);
183  /// writer.writeNodeMap("color", colorMap);
184  /// \endcode
185  ///
186  /// With the \c writeEdgeMap() member function you can give an edge map
187  /// writing command similar to the NodeMaps.
188  ///
189  /// \code
190  /// DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> >
191  ///   edgeDescMap(graph);
192  /// writer.writeEdgeMap("descriptor", edgeDescMap);
193  ///
194  /// writer.writeEdgeMap("weight", weightMap);
195  /// writer.writeEdgeMap("label", labelMap);
196  /// \endcode
197  ///
198  /// With \c writeNode() and \c writeEdge() functions you can
199  /// point out Nodes and Edges in the graph. By example, you can
200  /// write out the source and target of the graph.
201  ///
202  /// \code
203  /// writer.writeNode("source", sourceNode);
204  /// writer.writeNode("target", targetNode);
205  ///
206  /// writer.writeEdge("observed", edge);
207  /// \endcode
208  ///
209  /// After you give all write commands you must call the \c run() member
210  /// function, which execute all the writer commands.
211  ///
212  /// \code
213  /// writer.run();
214  /// \endcode
215  ///
216  /// \see DefaultWriterTraits
217  /// \see QuotedStringWriter
218  /// \see IdMap
219  /// \see DescriptorMap
220  /// \see \ref GraphWriter
221  /// \see \ref graph-io-page
222  /// \author Balazs Dezso
223  template <typename _Graph, typename _WriterTraits = DefaultWriterTraits>
224  class GraphWriter {
225  public:
226   
227    typedef _Graph Graph;
228    typedef typename Graph::Node Node;
229    typedef typename Graph::NodeIt NodeIt;
230    typedef typename Graph::Edge Edge;
231    typedef typename Graph::EdgeIt EdgeIt;
232
233    typedef _WriterTraits WriterTraits;
234 
235    /// \brief Construct a new GraphWriter.
236    ///
237    /// Construct a new GraphWriter. It writes from the given map,
238    /// it constructs the given map and it use the given writer as the
239    /// default skipper.
240    GraphWriter(std::ostream& _os, const Graph& _graph)
241      : os(_os), graph(_graph) {}
242
243
244    /// \brief Destruct the graph writer.
245    ///
246    /// Destruct the graph writer.
247    ~GraphWriter() {
248      for (typename NodeMapWriters::iterator it = node_map_writers.begin();
249           it != node_map_writers.end(); ++it) {
250        delete it->second;
251      }
252
253      for (typename EdgeMapWriters::iterator it = edge_map_writers.begin();
254           it != edge_map_writers.end(); ++it) {
255        delete it->second;
256      }
257
258    }
259
260    // Node map rules
261
262    /// \brief Add a new node map writer command for the writer.
263    ///
264    /// Add a new node map writer command for the writer.
265    template <typename Map>
266    GraphWriter& writeNodeMap(std::string name, const Map& map) {
267      return writeNodeMap<typename WriterTraits::template Writer<
268        typename Map::Value>, Map>(name, map);
269    }
270
271    /// \brief Add a new node map writer command for the writer.
272    ///
273    /// Add a new node map writer command for the writer.
274    template <typename Writer, typename Map>
275    GraphWriter& writeNodeMap(std::string name, const Map& map,
276                              const Writer& writer = Writer()) {
277      node_map_writers.push_back(
278        make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));
279      return *this;
280    }
281
282    // Edge map rules
283
284    /// \brief Add a new edge map writer command for the writer.
285    ///
286    /// Add a new edge map writer command for the writer.
287    template <typename Map>
288    GraphWriter& writeEdgeMap(std::string name, const Map& map) {
289      return writeEdgeMap<typename WriterTraits::template Writer<
290        typename Map::Value>, Map>(name, map);
291    }
292
293
294    /// \brief Add a new edge map writer command for the writer.
295    ///
296    /// Add a new edge map writer command for the writer.
297    template <typename Writer, typename Map>
298    GraphWriter& writeEdgeMap(std::string name,
299                            const Map& map, const Writer& writer = Writer()) {
300      edge_map_writers.push_back(make_pair(name,
301        new MapWriter<Edge, Map, Writer>(map, writer)));
302      return *this;
303    }
304
305    /// \brief Add a new labeled node writer for the writer.
306    ///
307    /// Add a new labeled node writer for the writer.
308    GraphWriter& writeNode(std::string name, const Node& node) {
309      node_writers.push_back(make_pair(name, node));
310      return *this;
311    }
312
313    /// \brief Add a new labeled edge writer for the writer.
314    ///
315    /// Add a new labeled edge writer for the writer.
316    GraphWriter& writeEdge(std::string name, const Edge& edge) {
317      edge_writers.push_back(make_pair(name, edge));
318      return *this;
319    }
320
321    /// \brief Executes the writer commands.
322    ///
323    /// Executes the writer commands.
324    void run() {   
325      WriterBase<Node>* nodeWriter = 0;
326      WriterBase<Edge>* edgeWriter = 0;
327      writeNodeSet(nodeWriter);
328      writeEdgeSet(nodeWriter, edgeWriter);
329      writeNodes(nodeWriter);
330      writeEdges(edgeWriter);
331      os << "@end" << std::endl;
332    }
333
334  private:
335
336    template <class _Item>
337    class WriterBase {
338    public:
339      typedef _Item Item;
340      virtual void write(std::ostream&, const Item&) = 0;
341    };
342
343    template <class _Item, typename _Map, typename _Writer>
344    class MapWriter : public WriterBase<_Item> {
345    public:
346      typedef _Map Map;
347      typedef _Writer Writer;
348      typedef typename Writer::Value Value;
349      typedef _Item Item;
350     
351      const Map& map;
352      Writer writer;
353
354      MapWriter(const Map& _map, const Writer& _writer)
355        : map(_map), writer(_writer) {}
356
357
358      virtual void write(std::ostream& os, const Item& item) {
359        writer.write(os, map[item]);
360      }
361
362    };
363
364    void writeNodeSet(WriterBase<Node>* & nodeWriter) {
365      if (node_map_writers.size() == 0) return;
366      os << "@nodeset" << std::endl;
367      for (int i = 0; i < (int)node_map_writers.size(); ++i) {
368        const std::string& id = node_map_writers[i].first;
369        os << id << '\t';
370        if (WriterTraits::idMapName(id) && nodeWriter == 0) {
371          nodeWriter = node_map_writers[i].second;
372        }
373      }
374      os << std::endl;
375      for (NodeIt it(graph); it != INVALID; ++it) {
376        for (int i = 0; i < (int)node_map_writers.size(); ++i) {
377          node_map_writers[i].second->write(os, it);
378        }
379        os << std::endl;
380      }
381
382    }
383
384    void writeEdgeSet(WriterBase<Node>* nodeWriter,
385                      WriterBase<Edge>* & edgeWriter) {
386      if (edge_map_writers.size() == 0) return;
387      if (nodeWriter == 0) {
388        throw DataFormatError("Cannot find node id map");
389      }
390      os << "@edgeset" << std::endl;
391      os << "\t\t";
392      for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
393        const std::string& id = edge_map_writers[i].first;
394        os << id << '\t';
395        if (WriterTraits::idMapName(id) && edgeWriter == 0) {
396          edgeWriter = edge_map_writers[i].second;
397        }
398      }
399      os << std::endl;
400      for (EdgeIt it(graph); it != INVALID; ++it) {
401        nodeWriter->write(os, graph.source(it));
402        nodeWriter->write(os, graph.target(it));
403        for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
404          edge_map_writers[i].second->write(os, it);
405        }
406        os << std::endl;
407      }
408    }
409
410    void writeNodes(WriterBase<Node>* nodeWriter) {
411      if (node_writers.size() == 0) return;
412      if (nodeWriter == 0) {
413        throw DataFormatError("Cannot find node id map");
414      }
415      os << "@nodes" << std::endl;
416      for (int i = 0; i < (int)node_writers.size(); ++i) {
417        os << node_writers[i].first << '\t';
418        nodeWriter->write(os, node_writers[i].second);
419        os << std::endl;
420      }
421    }
422
423    void writeEdges(WriterBase<Edge>* edgeWriter) {
424      if (edge_writers.size() == 0) return;
425      if (edgeWriter == 0) {
426        throw DataFormatError("Cannot find node id map");
427      }
428      os << "@edges" << std::endl;
429      for (int i = 0; i < (int)edge_writers.size(); ++i) {
430        os << edge_writers[i].first << '\t';
431        edgeWriter->write(os, edge_writers[i].second);
432        os << std::endl;
433      }
434    }
435   
436
437
438
439    typedef std::vector< std::pair<std::string, WriterBase<Node>*> >
440      NodeMapWriters;
441    NodeMapWriters node_map_writers;
442
443    typedef std::vector< std::pair<std::string, WriterBase<Edge>*> >
444      EdgeMapWriters;
445    EdgeMapWriters edge_map_writers;
446
447    typedef std::vector<std::pair<std::string, Node> > NodeWriters;
448    NodeWriters node_writers;
449
450    typedef std::vector<std::pair<std::string, Edge> > EdgeWriters;
451    EdgeWriters edge_writers;
452
453    std::ostream& os;
454    const Graph& graph;
455
456  };
457
458  /// \brief Write a graph to the output.
459  ///
460  /// Write a graph to the output.
461  /// \param os The output stream.
462  /// \param g The graph.
463  /// \param capacity The capacity map.
464  /// \param s The source node.
465  /// \param t The target node.
466  /// \param cost The cost map.
467  template<typename Graph, typename CapacityMap, typename CostMap>
468  void writeGraph(std::ostream& os, const Graph &g,
469                  const CapacityMap& capacity, const typename Graph::Node &s,
470                  const typename Graph::Node &t, const CostMap& cost) {
471    GraphWriter<Graph> writer(os, g);
472    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
473    writer.writeNodeMap("id", nodeIdMap);
474    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
475    writer.writeEdgeMap("id", edgeIdMap);
476    writer.writeEdgeMap("capacity", capacity);
477    writer.writeEdgeMap("cost", cost);
478    writer.writeNode("source", s);
479    writer.writeNode("target", t);
480    writer.run();
481  }
482
483  /// \brief Write a graph to the output.
484  ///
485  /// Write a graph to the output.
486  /// \param os The output stream.
487  /// \param g The graph.
488  /// \param capacity The capacity map.
489  /// \param s The source node.
490  /// \param t The target node.
491  template<typename Graph, typename CapacityMap>
492  void writeGraph(std::ostream& os, const Graph &g,
493                  const CapacityMap& capacity, const typename Graph::Node &s,
494                  const typename Graph::Node &t) {
495    GraphWriter<Graph> writer(os, g);
496    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
497    writer.writeNodeMap("id", nodeIdMap);
498    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
499    writer.writeEdgeMap("id", edgeIdMap);
500    writer.writeEdgeMap("capacity", capacity);
501    writer.writeNode("source", s);
502    writer.writeNode("target", t);
503    writer.run();
504  }
505
506  /// \brief Write a graph to the output.
507  ///
508  /// Write a graph to the output.
509  /// \param os The output stream.
510  /// \param g The graph.
511  /// \param capacity The capacity map.
512  /// \param s The source node.
513  template<typename Graph, typename CapacityMap>
514  void writeGraph(std::ostream& os, const Graph &g,
515                  const CapacityMap& capacity, const typename Graph::Node &s) {
516    GraphWriter<Graph> writer(os, g);
517    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
518    writer.writeNodeMap("id", nodeIdMap);
519    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
520    writer.writeEdgeMap("id", edgeIdMap);
521    writer.writeEdgeMap("capacity", capacity);
522    writer.writeNode("source", s);
523    writer.run();
524  }
525
526  /// \brief Write a graph to the output.
527  ///
528  /// Write a graph to the output.
529  /// \param os The output stream.
530  /// \param g The graph.
531  /// \param capacity The capacity map.
532  template<typename Graph, typename CapacityMap>
533  void writeGraph(std::ostream& os, const Graph &g,
534                  const CapacityMap& capacity) {
535    GraphWriter<Graph> writer(os, g);
536    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
537    writer.writeNodeMap("id", nodeIdMap);
538    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
539    writer.writeEdgeMap("id", edgeIdMap);
540    writer.writeEdgeMap("capacity", capacity);
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  template<typename Graph>
550  void writeGraph(std::ostream& os, const Graph &g) {
551    GraphWriter<Graph> writer(os, g);
552    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
553    writer.writeNodeMap("id", nodeIdMap);
554    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
555    writer.writeEdgeMap("id", edgeIdMap);
556    writer.run();
557  }
558
559  /// @}
560
561}
562
563#endif
Note: See TracBrowser for help on using the repository browser.