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

/* -*- C++ -*-
 * src/lemon/graph_writer.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

///\ingroup io_group
///\file
///\brief Lemon Graph Format writer.

#ifndef LEMON_GRAPH_WRITER_H
#define LEMON_GRAPH_WRITER_H

#include <iostream>
#include <sstream>

#include <map>
#include <vector>

#include <memory>

#include <lemon/map_utils.h>

#include <lemon/invalid.h>
#include <lemon/error.h>


namespace lemon {

  /// \addtogroup io_group
  /// @{

  /// \brief Standard WriterTraits for the GraphWriter class.
  ///
  /// Standard WriterTraits for the GraphWriter class.
  /// It defines standard writing method for all type of value. 
  /// \author Balazs Dezso
  struct DefaultWriterTraits {

    /// \brief Template class for writing an value.
    ///
    /// Template class for writing an value.
    /// \author Balazs Dezso
    template <typename _Value>
    struct Writer {
      /// The value type.
      typedef _Value Value;

      /// \brief Writes a value to the given stream.
      ///
      /// Writes a value to the given stream.
      void write(std::ostream& os, const Value& value) {
        os << value << '\t';
      }
    };

    /// \brief Returns wheter this name is an ID map name.
    ///
    /// Returns wheter this name is an ID map name.
    static bool idMapName(const std::string& name) {
      return name == "id";
    }

  };


  /// \brief Writer class for quoted strings.
  ///
  /// Writer class for quoted strings. It can process the escape
  /// sequences in the string.
  /// \author Balazs Dezso
  class QuotedStringWriter {
  public:
    typedef std::string Value;

    /// \brief Constructor for the writer.
    ///
    /// Constructor for the writer. If the given parameter is true
    /// the writer creates escape sequences from special characters.
    QuotedStringWriter(bool _escaped = true) : escaped(_escaped) {}

    /// \brief Writes a quoted string to the given stream.
    ///
    /// Writes a quoted string to the given stream.
    void write(std::ostream& os, const std::string& value) {
      os << "\"";
      if (escaped) {
        std::ostringstream ls;
        for (int i = 0; i < (int)value.size(); ++i) {
          writeEscape(ls, value[i]);
        }
        os << ls.str();
      } else {
        os << value;
      }
      os << "\"";
    }

  private:
    
    static void writeEscape(std::ostream& os, char c) {
      switch (c) {
      case '\\':
        os << "\\\\";
        return;
      case '\"':
        os << "\\\"";
        return;
      case '\'':
        os << "\\\'";
        return;
      case '\?':
        os << "\\\?";
        return;
      case '\a':
        os << "\\a";
        return;
      case '\b':
        os << "\\b";
        return;
      case '\f':
        os << "\\f";
        return;
      case '\r':
        os << "\\r";
        return;
      case '\n':
        os << "\\n";
        return;
      case '\t':
        os << "\\t";
        return;
      case '\v':
        os << "\\v";
        return;
      default:
        if (c < 0x20) {
          os << '\\' << std::oct << (int)c;
        } else {
          os << c;
        }
        return;
      }     
    }
  private:
    bool escaped;
  };

  
  /// \brief The graph writer class.
  ///
  /// The \c GraphWriter class provides the graph output. To write a graph
  /// you should first give writing commands for the writer. You can declare
  /// write command as \c NodeMap or \c EdgeMap writing and labeled Node and
  /// Edge writing.
  ///
  /// \code
  /// GraphWriter<ListGraph> writer(std::cout, graph);
  /// \endcode
  ///
  /// The \c writeNodeMap() function declares a \c NodeMap writing 
  /// command in the \c GraphWriter. You should give as parameter 
  /// the name of the map and the map object. The NodeMap writing 
  /// command with name "id" should write a unique map because it 
  /// is regarded as ID map.
  ///
  /// \code
  /// IdMap<ListGraph, Node> nodeIdMap;
  /// writer.writeNodeMap("id", nodeIdMap);
  ///
  /// writer.writeNodeMap("x-coord", xCoordMap);
  /// writer.writeNodeMap("y-coord", yCoordMap);
  /// writer.writeNodeMap("color", colorMap);
  /// \endcode
  ///
  /// With the \c writeEdgeMap() member function you can give an edge map
  /// writing command similar to the NodeMaps.
  ///
  /// \code
  /// DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > 
  ///   edgeDescMap(graph);
  /// writer.writeEdgeMap("descriptor", edgeDescMap);
  ///
  /// writer.writeEdgeMap("weight", weightMap);
  /// writer.writeEdgeMap("label", labelMap);
  /// \endcode
  ///
  /// With \c writeNode() and \c writeEdge() functions you can 
  /// point out Nodes and Edges in the graph. By example, you can 
  /// write out the source and target of the graph.
  ///
  /// \code
  /// writer.writeNode("source", sourceNode);
  /// writer.writeNode("target", targetNode);
  ///
  /// writer.writeEdge("observed", edge);
  /// \endcode
  ///
  /// After you give all write commands you must call the \c run() member
  /// function, which execute all the writer commands.
  ///
  /// \code
  /// writer.run();
  /// \endcode
  ///
  /// \see DefaultWriterTraits
  /// \see QuotedStringWriter
  /// \see IdMap
  /// \see DescriptorMap
  /// \see \ref GraphWriter
  /// \see \ref graph-io-page
  /// \author Balazs Dezso
  template <typename _Graph, typename _WriterTraits = DefaultWriterTraits> 
  class GraphWriter {
  public:
    
    typedef _Graph Graph;
    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::EdgeIt EdgeIt;

    typedef _WriterTraits WriterTraits;
 
    /// \brief Construct a new GraphWriter.
    ///
    /// Construct a new GraphWriter. It writes from the given map,
    /// it constructs the given map and it use the given writer as the
    /// default skipper.
    GraphWriter(std::ostream& _os, const Graph& _graph) 
      : os(_os), graph(_graph) {}


    /// \brief Destruct the graph writer.
    ///
    /// Destruct the graph writer.
    ~GraphWriter() {
      for (typename NodeMapWriters::iterator it = node_map_writers.begin(); 
           it != node_map_writers.end(); ++it) {
        delete it->second;
      }

      for (typename EdgeMapWriters::iterator it = edge_map_writers.begin();
           it != edge_map_writers.end(); ++it) {
        delete it->second;
      }

    }

    // Node map rules

    /// \brief Add a new node map writer command for the writer.
    ///
    /// Add a new node map writer command for the writer.
    template <typename Map>
    GraphWriter& writeNodeMap(std::string name, const Map& map) {
      return writeNodeMap<typename WriterTraits::template Writer<
        typename Map::Value>, Map>(name, map);
    }

    /// \brief Add a new node map writer command for the writer.
    ///
    /// Add a new node map writer command for the writer.
    template <typename Writer, typename Map>
    GraphWriter& writeNodeMap(std::string name, const Map& map, 
                              const Writer& writer = Writer()) {
      node_map_writers.push_back(
        make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));
      return *this;
    }

    // Edge map rules

    /// \brief Add a new edge map writer command for the writer.
    ///
    /// Add a new edge map writer command for the writer.
    template <typename Map>
    GraphWriter& writeEdgeMap(std::string name, const Map& map) { 
      return writeEdgeMap<typename WriterTraits::template Writer<
        typename Map::Value>, Map>(name, map);
    }


    /// \brief Add a new edge map writer command for the writer.
    ///
    /// Add a new edge map writer command for the writer.
    template <typename Writer, typename Map>
    GraphWriter& writeEdgeMap(std::string name, 
                            const Map& map, const Writer& writer = Writer()) {
      edge_map_writers.push_back(make_pair(name, 
        new MapWriter<Edge, Map, Writer>(map, writer)));
      return *this;
    }

    /// \brief Add a new labeled node writer for the writer.
    ///
    /// Add a new labeled node writer for the writer.
    GraphWriter& writeNode(std::string name, const Node& node) {
      node_writers.push_back(make_pair(name, node));
      return *this;
    }

    /// \brief Add a new labeled edge writer for the writer.
    ///
    /// Add a new labeled edge writer for the writer.
    GraphWriter& writeEdge(std::string name, const Edge& edge) {
      edge_writers.push_back(make_pair(name, edge));
      return *this;
    }

    /// \brief Executes the writer commands.
    ///
    /// Executes the writer commands.
    void run() {   
      WriterBase<Node>* nodeWriter = 0;
      WriterBase<Edge>* edgeWriter = 0;
      writeNodeSet(nodeWriter);
      writeEdgeSet(nodeWriter, edgeWriter);
      writeNodes(nodeWriter);
      writeEdges(edgeWriter);
      os << "@end" << std::endl;
    }

  private:

    template <class _Item>
    class WriterBase {
    public:
      typedef _Item Item;
      virtual void write(std::ostream&, const Item&) = 0;
    };

    template <class _Item, typename _Map, typename _Writer>
    class MapWriter : public WriterBase<_Item> {
    public:
      typedef _Map Map;
      typedef _Writer Writer;
      typedef typename Writer::Value Value;
      typedef _Item Item;
      
      const Map& map;
      Writer writer;

      MapWriter(const Map& _map, const Writer& _writer) 
        : map(_map), writer(_writer) {}


      virtual void write(std::ostream& os, const Item& item) {
        writer.write(os, map[item]);
      }

    };

    void writeNodeSet(WriterBase<Node>* & nodeWriter) {
      if (node_map_writers.size() == 0) return;
      os << "@nodeset" << std::endl;
      for (int i = 0; i < (int)node_map_writers.size(); ++i) {
        const std::string& id = node_map_writers[i].first;
        os << id << '\t';
        if (WriterTraits::idMapName(id) && nodeWriter == 0) {
          nodeWriter = node_map_writers[i].second;
        }
      } 
      os << std::endl;
      for (NodeIt it(graph); it != INVALID; ++it) {
        for (int i = 0; i < (int)node_map_writers.size(); ++i) {
          node_map_writers[i].second->write(os, it);
        }
        os << std::endl;
      }

    }

    void writeEdgeSet(WriterBase<Node>* nodeWriter, 
                      WriterBase<Edge>* & edgeWriter) {
      if (edge_map_writers.size() == 0) return;
      if (nodeWriter == 0) {
        throw DataFormatError("Cannot find node id map");
      }
      os << "@edgeset" << std::endl;
      os << "\t\t";
      for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
        const std::string& id = edge_map_writers[i].first;
        os << id << '\t';
        if (WriterTraits::idMapName(id) && edgeWriter == 0) {
          edgeWriter = edge_map_writers[i].second;
        }
      } 
      os << std::endl;
      for (EdgeIt it(graph); it != INVALID; ++it) {
        nodeWriter->write(os, graph.source(it));
        nodeWriter->write(os, graph.target(it));
        for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
          edge_map_writers[i].second->write(os, it);
        }
        os << std::endl;
      }
    }

    void writeNodes(WriterBase<Node>* nodeWriter) {
      if (node_writers.size() == 0) return;
      if (nodeWriter == 0) {
        throw DataFormatError("Cannot find node id map");
      }
      os << "@nodes" << std::endl;
      for (int i = 0; i < (int)node_writers.size(); ++i) {
        os << node_writers[i].first << '\t';
        nodeWriter->write(os, node_writers[i].second);
        os << std::endl;
      } 
    }

    void writeEdges(WriterBase<Edge>* edgeWriter) {
      if (edge_writers.size() == 0) return;
      if (edgeWriter == 0) {
        throw DataFormatError("Cannot find node id map");
      }
      os << "@edges" << std::endl;
      for (int i = 0; i < (int)edge_writers.size(); ++i) {
        os << edge_writers[i].first << '\t';
        edgeWriter->write(os, edge_writers[i].second);
        os << std::endl;
      } 
    }
    



    typedef std::vector< std::pair<std::string, WriterBase<Node>*> > 
      NodeMapWriters;
    NodeMapWriters node_map_writers;

    typedef std::vector< std::pair<std::string, WriterBase<Edge>*> > 
      EdgeMapWriters;
    EdgeMapWriters edge_map_writers;

    typedef std::vector<std::pair<std::string, Node> > NodeWriters;
    NodeWriters node_writers;

    typedef std::vector<std::pair<std::string, Edge> > EdgeWriters;
    EdgeWriters edge_writers;

    std::ostream& os;
    const Graph& graph;

  };

  /// \brief Write a graph to the output.
  ///
  /// Write a graph to the output.
  /// \param os The output stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  /// \param s The source node.
  /// \param t The target node.
  /// \param cost The cost map.
  template<typename Graph, typename CapacityMap, typename CostMap>
  void writeGraph(std::ostream& os, const Graph &g, 
                  const CapacityMap& capacity, const typename Graph::Node &s,
                  const typename Graph::Node &t, const CostMap& cost) {
    GraphWriter<Graph> writer(os, g);
    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
    writer.writeNodeMap("id", nodeIdMap);
    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
    writer.writeEdgeMap("id", edgeIdMap);
    writer.writeEdgeMap("capacity", capacity);
    writer.writeEdgeMap("cost", cost);
    writer.writeNode("source", s);
    writer.writeNode("target", t);
    writer.run();
  }

  /// \brief Write a graph to the output.
  ///
  /// Write a graph to the output.
  /// \param os The output stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  /// \param s The source node.
  /// \param t The target node.
  template<typename Graph, typename CapacityMap>
  void writeGraph(std::ostream& os, const Graph &g, 
                  const CapacityMap& capacity, const typename Graph::Node &s,
                  const typename Graph::Node &t) {
    GraphWriter<Graph> writer(os, g);
    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
    writer.writeNodeMap("id", nodeIdMap);
    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
    writer.writeEdgeMap("id", edgeIdMap);
    writer.writeEdgeMap("capacity", capacity);
    writer.writeNode("source", s);
    writer.writeNode("target", t);
    writer.run();
  }

  /// \brief Write a graph to the output.
  ///
  /// Write a graph to the output.
  /// \param os The output stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  /// \param s The source node.
  template<typename Graph, typename CapacityMap>
  void writeGraph(std::ostream& os, const Graph &g, 
                  const CapacityMap& capacity, const typename Graph::Node &s) {
    GraphWriter<Graph> writer(os, g);
    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
    writer.writeNodeMap("id", nodeIdMap);
    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
    writer.writeEdgeMap("id", edgeIdMap);
    writer.writeEdgeMap("capacity", capacity);
    writer.writeNode("source", s);
    writer.run();
  }

  /// \brief Write a graph to the output.
  ///
  /// Write a graph to the output.
  /// \param os The output stream.
  /// \param g The graph.
  /// \param capacity The capacity map.
  template<typename Graph, typename CapacityMap>
  void writeGraph(std::ostream& os, const Graph &g, 
                  const CapacityMap& capacity) {
    GraphWriter<Graph> writer(os, g);
    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
    writer.writeNodeMap("id", nodeIdMap);
    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
    writer.writeEdgeMap("id", edgeIdMap);
    writer.writeEdgeMap("capacity", capacity);
    writer.run();
  }

  /// \brief Write a graph to the output.
  ///
  /// Write a graph to the output.
  /// \param os The output stream.
  /// \param g The graph.
  template<typename Graph>
  void writeGraph(std::ostream& os, const Graph &g) {
    GraphWriter<Graph> writer(os, g);
    IdMap<Graph, typename Graph::Node> nodeIdMap(g);
    writer.writeNodeMap("id", nodeIdMap);
    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);
    writer.writeEdgeMap("id", edgeIdMap);
    writer.run();
  }

  /// @}

}

#endif