RhodeCode

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * 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.

 *

 */

namespace lemon {

/*!

\page lgf-format Lemon Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences. 

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

 label   coordinates size    title

 1       (10,20)     10      "First node"

 2       (80,80)     8       "Second node"

 3       (40,10)     10      "Third node"

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

 	      capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@attributes section contains key-value pairs, each line

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

//  LocalWords:  whitespace whitespaces

	  if (section == "nodes" && !nodes_done) {

	    if (_nodes_caption.empty() || _nodes_caption == caption) {

	      readNodes();

	      nodes_done = true;

	    }

	  } else if ((section == "arcs" || section == "edges") && 

		     !arcs_done) {

	    if (_arcs_caption.empty() || _arcs_caption == caption) {

	      readArcs();

	      arcs_done = true;

	    }

	  } else if (section == "attributes" && !attributes_done) {

	    if (_attributes_caption.empty() || _attributes_caption == caption) {

	      readAttributes();

	      attributes_done = true;

	    }

	  } else {

	    readLine();

	    skipSection();

	  }

	} catch (DataFormatError& error) {

	  error.line(line_num);

	  throw;

	}	

      }

      if (!nodes_done) {

	throw DataFormatError("Section @nodes not found");

      }

      if (!arcs_done) {

	throw DataFormatError("Section @arcs not found");

      }

      if (!attributes_done && !_attributes.empty()) {

	throw DataFormatError("Section @attributes not found");

      }

    }

    /// @}

  };

  /// \brief Return a \ref DigraphReader class

  /// 

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {

    DigraphReader<Digraph> tmp(is, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  /// 

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const std::string& fn, 

				       Digraph& digraph) {

    DigraphReader<Digraph> tmp(fn, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  /// 

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {

    DigraphReader<Digraph> tmp(fn, digraph);

    return tmp;

  }

  template <typename Graph>

  class GraphReader;

  template <typename Graph>

  GraphReader<Graph> graphReader(std::istream& is, Graph& graph);    

  template <typename Graph>

  GraphReader<Graph> graphReader(const std::string& fn, Graph& graph);   

  template <typename Graph>

  GraphReader<Graph> graphReader(const char *fn, Graph& graph);    

  /// \ingroup lemon_io

  ///  

  /// \brief \ref lgf-format "LGF" reader for undirected graphs

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  ///

  /// It can be used almost the same way as \c DigraphReader.

  /// The only difference is that this class can handle edges and

  /// edge maps as well as arcs and arc maps.

  template <typename _Graph>

  class GraphReader {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    std::istream* _is;

    bool local_is;

    Graph& _graph;

    std::string _nodes_caption;

    std::string _edges_caption;

    std::string _attributes_caption;

    typedef std::map<std::string, Node> NodeIndex;

    NodeIndex _node_index;

    typedef std::map<std::string, Edge> EdgeIndex;

    EdgeIndex _edge_index;

    typedef std::vector<std::pair<std::string, 

      _reader_bits::MapStorageBase<Node>*> > NodeMaps;    

    NodeMaps _node_maps; 

    typedef std::vector<std::pair<std::string,

      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;

    EdgeMaps _edge_maps;

    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 

      Attributes;

    Attributes _attributes;

    bool _use_nodes;

    bool _use_edges;

    bool _skip_nodes;

    bool _skip_edges;

    int line_num;

    std::istringstream line;

  public:

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// input stream.

    GraphReader(std::istream& is, Graph& graph) 

      : _is(&is), local_is(false), _graph(graph),

	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// file.

    GraphReader(const std::string& fn, Graph& graph) 

      : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),

    	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// file.

    GraphReader(const char* fn, Graph& graph) 

      : _is(new std::ifstream(fn)), local_is(true), _graph(graph),

    	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Destructor

    ~GraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin(); 

	   it != _node_maps.end(); ++it) {

	delete it->second;

      }

      for (typename EdgeMaps::iterator it = _edge_maps.begin(); 

	   it != _edge_maps.end(); ++it) {

	delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin(); 

	   it != _attributes.end(); ++it) {

	delete it->second;

      }

      if (local_is) {

	delete _is;

      }

    }

      }

      *_os << std::endl;

      for (typename Attributes::iterator it = _attributes.begin();

	   it != _attributes.end(); ++it) {

	_writer_bits::writeToken(*_os, it->first) << ' ';

	_writer_bits::writeToken(*_os, it->second->get());

	*_os << std::endl;

      }

    }

  public:

    /// \name Execution of the writer    

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

      if (!_skip_nodes) {

	writeNodes();

      } else {

	createNodeIndex();

      }

      if (!_skip_arcs) {      

	writeArcs();

      } else {

	createArcIndex();

      }

      writeAttributes();

    }

    /// \brief Give back the stream of the writer

    ///

    /// Give back the stream of the writer.

    std::ostream& ostream() {

      return *_os;

    }

    /// @}

  };

  /// \brief Return a \ref DigraphWriter class

  /// 

  /// This function just returns a \ref DigraphWriter class.

  /// \relates DigraphWriter

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(std::ostream& os, 

				       const Digraph& digraph) {

    DigraphWriter<Digraph> tmp(os, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphWriter class

  /// 

  /// This function just returns a \ref DigraphWriter class.

  /// \relates DigraphWriter

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const std::string& fn, 

				       const Digraph& digraph) {

    DigraphWriter<Digraph> tmp(fn, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphWriter class

  /// 

  /// This function just returns a \ref DigraphWriter class.

  /// \relates DigraphWriter

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const char* fn, 

				       const Digraph& digraph) {

    DigraphWriter<Digraph> tmp(fn, digraph);

    return tmp;

  }

  template <typename Graph>

  class GraphWriter;

  template <typename Graph>

  GraphWriter<Graph> graphWriter(std::ostream& os, const Graph& graph);    

  template <typename Graph>

  GraphWriter<Graph> graphWriter(const std::string& fn, const Graph& graph);   

  template <typename Graph>

  GraphWriter<Graph> graphWriter(const char *fn, const Graph& graph);    

  /// \ingroup lemon_io

  ///  

  /// \brief \ref lgf-format "LGF" writer for directed graphs

  ///

  /// This utility writes an \ref lgf-format "LGF" file.

  ///

  /// It can be used almost the same way as \c DigraphWriter.

  /// The only difference is that this class can handle edges and

  /// edge maps as well as arcs and arc maps.

  template <typename _Graph>

  class GraphWriter {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    std::ostream* _os;

    bool local_os;

    Graph& _graph;

    std::string _nodes_caption;

    std::string _edges_caption;

    std::string _attributes_caption;

    typedef std::map<Node, std::string> NodeIndex;

    NodeIndex _node_index;

    typedef std::map<Edge, std::string> EdgeIndex;

    EdgeIndex _edge_index;

    typedef std::vector<std::pair<std::string, 

      _writer_bits::MapStorageBase<Node>* > > NodeMaps;    

    NodeMaps _node_maps; 

    typedef std::vector<std::pair<std::string, 

      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;

    EdgeMaps _edge_maps;

    typedef std::vector<std::pair<std::string, 

      _writer_bits::ValueStorageBase*> > Attributes;

    Attributes _attributes;

    bool _skip_nodes;

    bool _skip_edges;

  public:

    /// \brief Constructor

    ///

    /// Construct a directed graph writer, which writes to the given

    /// output stream.

    GraphWriter(std::ostream& is, const Graph& graph) 

      : _os(&is), local_os(false), _graph(graph),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph writer, which writes to the given

    /// output file.

    GraphWriter(const std::string& fn, const Graph& graph) 

      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph writer, which writes to the given

    /// output file.

    GraphWriter(const char* fn, const Graph& graph) 

      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Destructor

    ~GraphWriter() {

      for (typename NodeMaps::iterator it = _node_maps.begin(); 

	   it != _node_maps.end(); ++it) {

	delete it->second;

      }

      for (typename EdgeMaps::iterator it = _edge_maps.begin(); 

	   it != _edge_maps.end(); ++it) {

	delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin(); 

	   it != _attributes.end(); ++it) {

	delete it->second;

      }

      if (local_os) {

	delete _os;

      }

    }

  private:

    friend GraphWriter<Graph> graphWriter<>(std::ostream& os, 

					    const Graph& graph);    

    friend GraphWriter<Graph> graphWriter<>(const std::string& fn, 

					    const Graph& graph);   

    friend GraphWriter<Graph> graphWriter<>(const char *fn, 

					    const Graph& graph);