RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

/**

\dir demo

\brief A collection of demo applications.

This directory contains several simple demo applications, mainly

for educational purposes.

*/

/**

\dir doc

\brief Auxiliary (and the whole generated) documentation.

This directory contains some auxiliary pages and the whole generated

documentation.

*/

/**

\dir test

\brief Test programs.

/**

\dir tools

\brief Some useful executables.

This directory contains the sources of some useful complete executables.

*/

/**

\dir lemon

\brief Base include directory of LEMON.

This is the base directory of LEMON includes, so each include file must be

prefixed with this, e.g.

\code

#include<lemon/list_graph.h>

#include<lemon/dijkstra.h>

\endcode

*/

/**

\dir concepts

\brief Concept descriptors and checking classes.

This directory contains the concept descriptors and concept checking tools.

For more information see the \ref concept "Concepts" module.

*/

/**

\dir bits

\brief Auxiliary tools for implementation.

maps and some other classes.

As a user you typically don't have to deal with these files.

*/

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

/**

@defgroup datas Data Structures

This group describes the several data structures implemented in LEMON.

*/

/**

@defgroup graphs Graph Structures

@ingroup datas

\brief Graph structures implemented in LEMON.

The implementation of combinatorial algorithms heavily relies on

efficient graph implementations. LEMON offers data structures which are

planned to be easily used in an experimental phase of implementation studies,

and thereafter the program code can be made efficient by small modifications.

The most efficient implementation of diverse applications require the

usage of different physical graph implementations. These differences

appear in the size of graph we require to handle, memory or time usage

limitations or in the set of operations through which the graph can be

  to avoid document multiplications, an implementation of a concept

  simply refers to the corresponding concept class.

- These classes declare every functions, <tt>typedef</tt>s etc. an

  implementation of the %concepts should provide, however completely

  without implementations and real data structures behind the

  interface. On the other hand they should provide nothing else. All

  the algorithms working on a data structure meeting a certain concept

  should compile with these classes. (Though it will not run properly,

  of course.) In this way it is easily to check if an algorithm

  doesn't use any extra feature of a certain implementation.

- The concept descriptor classes also provide a <em>checker class</em>

  that makes it possible to check whether a certain implementation of a

  concept indeed provides all the required features.

- Finally, They can serve as a skeleton of a new implementation of a concept.

*/

/**

@defgroup graph_concepts Graph Structure Concepts

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

This group describes the skeletons and concept checking classes of LEMON's

graph structures and helper classes used to implement these.

*/

/**

@defgroup map_concepts Map Concepts

@ingroup concept

\brief Skeleton and concept checking classes for maps

This group describes the skeletons and concept checking classes of maps.

*/

/**

\anchor demoprograms

@defgroup demos Demo programs

Some demo programs are listed here. Their full source codes can be found in

the \c demo subdirectory of the source tree.

It order to compile them, use <tt>--enable-demo</tt> configure option when

build the library.

*/

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

///\file

///\brief Some basic non-inline functions and static global data.

#include<lemon/tolerance.h>

#include<lemon/core.h>

namespace lemon {

  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);

  double Tolerance<double>::def_epsilon = 1e-10;

  long double Tolerance<long double>::def_epsilon = 1e-14;

#ifndef LEMON_ONLY_TEMPLATES

  const Invalid INVALID = Invalid();

#endif

} //namespace lemon

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_BITS_DEFAULT_MAP_H

#define LEMON_BITS_DEFAULT_MAP_H

#include <lemon/config.h>

#include <lemon/bits/array_map.h>

#include <lemon/bits/vector_map.h>

//#include <lemon/bits/debug_map.h>

//\ingroup graphbits

//\file

//\brief Graph maps that construct and destruct their elements dynamically.

namespace lemon {

  //#ifndef LEMON_USE_DEBUG_MAP

  template <typename _Graph, typename _Item, typename _Value>

  struct DefaultMapSelector {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_BITS_MAP_EXTENDER_H

#define LEMON_BITS_MAP_EXTENDER_H

#include <iterator>

#include <lemon/bits/traits.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

//\file

//\brief Extenders for iterable maps.

namespace lemon {

  // \ingroup graphbits

  //

  // \brief Extender for maps

  template <typename _Map>

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_BITS_PRED_MAP_PATH_H

#define LEMON_BITS_PRED_MAP_PATH_H

namespace lemon {

  template <typename _Digraph, typename _PredMap>

  class PredMapPath {

  public:

    typedef True RevPathTag;

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef _PredMap PredMap;

    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,

                typename Digraph::Node _target)

      : digraph(_digraph), predMap(_predMap), target(_target) {}

    int length() const {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

///\file

///\brief Some basic non-inline functions and static global data.

#include<lemon/bits/windows.h>

#ifdef WIN32

#ifndef WIN32_LEAN_AND_MEAN

#define WIN32_LEAN_AND_MEAN

#endif

#ifndef NOMINMAX

#define NOMINMAX

#endif

#ifdef UNICODE

#undef UNICODE

#endif

#include <windows.h>

#ifdef LOCALE_INVARIANT

#define MY_LOCALE LOCALE_INVARIANT

#else

        stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;

        cutime = 0;

        cstime = 0;

      } else {

        rtime = 0;

        utime = 0;

        stime = 0;

        cutime = 0;

        cstime = 0;

      }

#else

      timeval tv;

      gettimeofday(&tv, 0);

      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;

      tms ts;

      double tck=sysconf(_SC_CLK_TCK);

      times(&ts);

      utime=ts.tms_utime/tck;

      stime=ts.tms_stime/tck;

      cutime=ts.tms_cutime/tck;

      cstime=ts.tms_cstime/tck;

#endif

    }

    std::string getWinFormattedDate()

    {

      std::ostringstream os;

#ifdef WIN32

      SYSTEMTIME time;

      GetSystemTime(&time);

      char buf1[11], buf2[9], buf3[5];

                        ("ddd MMM dd"), buf1, 11) &&

          GetTimeFormat(MY_LOCALE, 0, &time,

                        ("HH':'mm':'ss"), buf2, 9) &&

          GetDateFormat(MY_LOCALE, 0, &time,

                        ("yyyy"), buf3, 5)) {

        os << buf1 << ' ' << buf2 << ' ' << buf3;

      }

      else os << "unknown";

#else

      timeval tv;

      gettimeofday(&tv, 0);

      char cbuf[26];

      ctime_r(&tv.tv_sec,cbuf);

      os << cbuf;

#endif

      return os.str();

    }

    int getWinRndSeed()

    {

#ifdef WIN32

      FILETIME time;

      GetSystemTimeAsFileTime(&time);

      return GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime;

#else

      timeval tv;

      gettimeofday(&tv, 0);

      return getpid() + tv.tv_sec + tv.tv_usec;

#endif

    }

  }

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_CORE_H

#define LEMON_CORE_H

#include <vector>

#include <algorithm>

#include <lemon/config.h>

#include <lemon/bits/enable_if.h>

#include <lemon/bits/traits.h>

#include <lemon/assert.h>

///\file

///\brief LEMON core utilities.

///

///This header file contains core utilities for LEMON.

///It is automatically included by all graph types, therefore it usually

///do not have to be included directly.

namespace lemon {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_DFS_H

#define LEMON_DFS_H

///\ingroup search

///\file

///\brief DFS algorithm.

#include <lemon/list_graph.h>

#include <lemon/bits/path_dump.h>

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/path.h>

namespace lemon {

  ///Default traits class of Dfs class.

  ///Default traits class of Dfs class.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_GRAPH_TO_EPS_H

#define LEMON_GRAPH_TO_EPS_H

#include<iostream>

#include<fstream>

#include<sstream>

#include<algorithm>

#include<vector>

#ifndef WIN32

#include<sys/time.h>

#include<ctime>

#else

#include<lemon/bits/windows.h>

#endif

#include<lemon/math.h>

#include<lemon/core.h>

#include<lemon/dim2.h>

    private:

      Functor _functor;

    public:

      StreamSection(const Functor& functor) : _functor(functor) {}

      virtual ~StreamSection() {}

      virtual void process(std::istream& is, int& line_num) {

        _functor(is, line_num);

        char c;

        std::string line;

        while (is.get(c) && c != '@') {

          if (c == '\n') {

            ++line_num;

          } else if (!isWhiteSpace(c)) {

            getline(is, line);

            ++line_num;

          }

        }

        if (is) is.putback(c);

        else if (is.eof()) is.clear();

      }

    };

  }

  template <typename Digraph>

  class DigraphReader;

  template <typename Digraph>

                                       std::istream& is = std::cin);

  template <typename Digraph>

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

  template <typename Digraph>

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

  /// \ingroup lemon_io

  ///

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

  ///

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

  ///

  /// The reading method does a batch processing. The user creates a

  /// reader object, then various reading rules can be added to the

  /// reader, and eventually the reading is executed with the \c run()

  /// member function. A map reading rule can be added to the reader

  /// with the \c nodeMap() or \c arcMap() members. An optional

  /// converter parameter can also be added as a standard functor

  /// converting from \c std::string to the value type of the map. If it

  /// is set, it will determine how the tokens in the file should be

  /// converted to the value type of the map. If the functor is not set,

  /// then a default conversion will be used. One map can be read into

  /// multiple map objects at the same time. The \c attribute(), \c

  /// node() and \c arc() functions are used to add attribute reading

  /// rules.

  ///

  ///\code

  /// DigraphReader<Digraph>(digraph, std::cin).

  ///   nodeMap("coordinates", coord_map).

  ///   arcMap("capacity", cap_map).

  ///   node("source", src).

  ///   node("target", trg).

        throw IoError("Cannot open file", fn);

      }

    }

    /// \brief Destructor

    ~DigraphReader() {

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

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

        delete it->second;

      }

      for (typename ArcMaps::iterator it = _arc_maps.begin();

           it != _arc_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;

      }

    }

  private:

    template <typename DGR>

    friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);

    template <typename DGR>

                                            const std::string& fn);

    template <typename DGR>

    friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);

    DigraphReader(DigraphReader& other)

      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),

        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),

        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _arc_index.swap(other._arc_index);

      _node_maps.swap(other._node_maps);

      _arc_maps.swap(other._arc_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphReader& operator=(const DigraphReader&);

  public:

    /// \name Reading rules

    /// @{

  ///

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

  /// \relates DigraphReader

  template <typename Digraph>

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

    DigraphReader<Digraph> tmp(digraph, is);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  ///

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

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(Digraph& digraph,

                                       const std::string& fn) {

    DigraphReader<Digraph> tmp(digraph, fn);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  ///

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

  /// \relates DigraphReader

  template <typename Digraph>

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

    DigraphReader<Digraph> tmp(digraph, fn);

    return tmp;

  }

  template <typename Graph>

  class GraphReader;

  template <typename Graph>

                                 std::istream& is = std::cin);

  template <typename Graph>

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

  template <typename Graph>

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

  /// \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.

  ///

  /// The columns in the \c \@edges (or \c \@arcs) section are the

  /// edge maps. However, if there are two maps with the same name

  /// prefixed with \c '+' and \c '-', then these can be read into an

  /// arc map.  Similarly, an attribute can be read into an arc, if

  /// it's value is an edge label prefixed with \c '+' or \c '-'.

  template <typename _Graph>

  class GraphReader {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    std::istream* _is;

    bool local_is;

        delete _is;

        throw IoError("Cannot open file", fn);

      }

    }

    /// \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;

      }

    }

  private:

    template <typename GR>

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

    template <typename GR>

    template <typename GR>

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

    GraphReader(GraphReader& other)

      : _is(other._is), local_is(other.local_is), _graph(other._graph),

        _use_nodes(other._use_nodes), _use_edges(other._use_edges),

        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._edge_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

      _attributes_caption = other._attributes_caption;

    }

    GraphReader& operator=(const GraphReader&);

  public:

    /// \name Reading rules

    /// @{

    /// \brief Node map reading rule

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

///\file

///\brief \ref lgf-format "LEMON Graph Format" writer.

#ifndef LEMON_LGF_WRITER_H

#define LEMON_LGF_WRITER_H

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <vector>

#include <functional>

#include <lemon/core.h>

#include <lemon/maps.h>

        _skip_nodes(false), _skip_arcs(false) {

      if (!(*_os)) {

        delete _os;

        throw IoError("Cannot write file", fn);

      }

    }

    /// \brief Destructor

    ~DigraphWriter() {

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

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

        delete it->second;

      }

      for (typename ArcMaps::iterator it = _arc_maps.begin();

           it != _arc_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:

    template <typename DGR>

                                            std::ostream& os);

    template <typename DGR>

    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,

                                            const std::string& fn);

    template <typename DGR>

    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,

                                            const char *fn);

    DigraphWriter(DigraphWriter& other)

      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),

        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {

      other._os = 0;

      other.local_os = false;

      _node_index.swap(other._node_index);

      _arc_index.swap(other._arc_index);

      _node_maps.swap(other._node_maps);

      _arc_maps.swap(other._arc_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphWriter& operator=(const DigraphWriter&);

  public:

    /// \name Writing rules

    ~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:

    template <typename GR>

    friend GraphWriter<GR> graphWriter(const GR& graph,

                                       std::ostream& os);

    template <typename GR>

    friend GraphWriter<GR> graphWriter(const GR& graph,

                                       const std::string& fn);

    template <typename GR>

    friend GraphWriter<GR> graphWriter(const GR& graph,

                                       const char *fn);

    GraphWriter(GraphWriter& other)

      : _os(other._os), local_os(other.local_os), _graph(other._graph),

        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._os = 0;

      other.local_os = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._edge_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

      _attributes_caption = other._attributes_caption;

    }

    GraphWriter& operator=(const GraphWriter&);

  public:

    /// \name Writing rules

    /// @{

    /// \brief Node map writing rule

    ///

    /// Add a node map writing rule to the writer.

    template <typename Map>

    GraphWriter& nodeMap(const std::string& caption, const Map& map) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

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

 *

 */

#ifndef LEMON_LIST_GRAPH_H

#define LEMON_LIST_GRAPH_H

///\ingroup graphs

///\file

///\brief ListDigraph, ListGraph classes.

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/bits/graph_extender.h>

#include <vector>

#include <list>

namespace lemon {