COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_writer.h @ 1344:9146f77f6d67

Last change on this file since 1344:9146f77f6d67 was 1343:a81f9cfc9775, checked in by Balazs Dezso, 19 years ago

Some bug fixes.

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