RhodeCode

QUIET                  = NO

WARNINGS               = YES

WARN_IF_UNDOCUMENTED   = YES

WARN_IF_DOC_ERROR      = YES

WARN_NO_PARAMDOC       = NO

WARN_FORMAT            = "$file:$line: $text  "

WARN_LOGFILE           = doxygen.log

#---------------------------------------------------------------------------

# configuration options related to the input files

#---------------------------------------------------------------------------

INPUT                  = @abs_top_srcdir@/doc \

                         @abs_top_srcdir@/lemon \

                         @abs_top_srcdir@/lemon/bits \

                         @abs_top_srcdir@/lemon/concepts \

                         @abs_top_srcdir@/demo \

                         @abs_top_srcdir@/tools \

                         @abs_top_srcdir@/test/test_tools.h

INPUT_ENCODING         = UTF-8

FILE_PATTERNS          = *.h \

                         *.cc \

                         *.dox

RECURSIVE              = NO

EXCLUDE                = 

EXCLUDE_SYMLINKS       = NO

EXCLUDE_PATTERNS       = 

EXCLUDE_SYMBOLS        = 

EXAMPLE_PATH           = @abs_top_srcdir@/demo \

                         @abs_top_srcdir@/LICENSE \

                         @abs_top_srcdir@/doc

EXAMPLE_PATTERNS       = 

EXAMPLE_RECURSIVE      = NO

IMAGE_PATH             = @abs_top_srcdir@/doc/images \

INPUT_FILTER           = 

FILTER_PATTERNS        = 

FILTER_SOURCE_FILES    = NO

#---------------------------------------------------------------------------

# configuration options related to source browsing

#---------------------------------------------------------------------------

SOURCE_BROWSER         = NO

INLINE_SOURCES         = NO

STRIP_CODE_COMMENTS    = YES

REFERENCED_BY_RELATION = NO

REFERENCES_RELATION    = NO

REFERENCES_LINK_SOURCE = YES

USE_HTAGS              = NO

VERBATIM_HEADERS       = NO

#---------------------------------------------------------------------------

# configuration options related to the alphabetical class index

#---------------------------------------------------------------------------

ALPHABETICAL_INDEX     = YES

COLS_IN_ALPHA_INDEX    = 2

IGNORE_PREFIX          = 

#---------------------------------------------------------------------------

# configuration options related to the HTML output

#---------------------------------------------------------------------------

GENERATE_HTML          = YES

HTML_OUTPUT            = html

HTML_FILE_EXTENSION    = .html

HTML_HEADER            = 

HTML_FOOTER            = 

HTML_STYLESHEET        = 

HTML_ALIGN_MEMBERS     = YES

GENERATE_HTMLHELP      = NO

GENERATE_DOCSET        = NO

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

\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

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@edges is just a synonym of \c \@arcs. The @arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

has the same caption with \c '+' and \c '-' prefix, then these columns

can be regarded as the values of an arc map.

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

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\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 (assertion)

      std::cerr << " (assertion '" << assertion << "' failed)";

    std::cerr << std::endl;

  }

  inline void assert_fail_abort(const char *file, int line,

                                const char *function, const char* message,

                                const char *assertion)

  {

    assert_fail_log(file, line, function, message, assertion);

    std::abort();

  }

  namespace _assert_bits {

    inline const char* cstringify(const std::string& str) {

      return str.c_str();

    }

    inline const char* cstringify(const char* str) {

      return str;

    }

  }

}

#endif // LEMON_ASSERT_H

#undef LEMON_ASSERT

#undef LEMON_FIXME

#undef LEMON_DEBUG

  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1

#error "LEMON assertion system is not set properly"

#endif

   defined(NDEBUG))

#error "LEMON assertion system is not set properly"

#endif

#if defined LEMON_ASSERT_LOG

#  undef LEMON_ASSERT_HANDLER

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log

#elif defined LEMON_ASSERT_ABORT

#  undef LEMON_ASSERT_HANDLER

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort

#elif defined LEMON_ASSERT_CUSTOM

#  undef LEMON_ASSERT_HANDLER

#  ifndef LEMON_CUSTOM_ASSERT_HANDLER

#    error "LEMON_CUSTOM_ASSERT_HANDLER is not set"

#  endif

#  define LEMON_ASSERT_HANDLER LEMON_CUSTOM_ASSERT_HANDLER

#elif defined LEMON_DISABLE_ASSERTS

#  undef LEMON_ASSERT_HANDLER

#elif defined NDEBUG

#  undef LEMON_ASSERT_HANDLER

#else

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort

#endif

#ifndef LEMON_FUNCTION_NAME

#  if defined __GNUC__

#    define LEMON_FUNCTION_NAME (__PRETTY_FUNCTION__)

#  elif defined _MSC_VER

#    define LEMON_FUNCTION_NAME (__FUNCSIG__)

#  else

#    define LEMON_FUNCTION_NAME (__func__)

///

/// The LEMON assertion system has a wide range of customization

/// properties. As a default behaviour the failed assertion prints a

/// short log message to the standard error and aborts the execution.

///

/// The following modes can be used in the assertion system:

///

/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log

///   message to the standard error and continues the execution.

/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c

///   LEMON_ASSERT_LOG, but it aborts the program. It is the default

///   behaviour.

/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler

///   function.

///   \code

///     void custom_assert_handler(const char* file, int line,

///                                const char* function, const char* message,

///                                const char* assertion);

///   \endcode

///   The name of the function should be defined as the \c

///   LEMON_CUSTOM_ASSERT_HANDLER macro name.

///   \code

///     #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler

///   \endcode

///   Whenever an assertion is occured, the custom assertion

///   handler is called with appropiate parameters.

///

/// The assertion mode can also be changed within one compilation unit.

/// If the macros are redefined with other settings and the

/// \ref lemon/assert.h "assert.h" file is reincluded, then the

/// behaviour is changed appropiately to the new settings.

#  define LEMON_ASSERT(exp, msg)                                        \

                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))

/// \ingroup exceptions

///

/// \brief Macro for mark not yet implemented features.

///

/// Macro for mark not yet implemented features and outstanding bugs.

/// It is close to be the shortcut of the following code:

/// \code

///   LEMON_ASSERT(false, msg);

/// \endcode

///

/// \see LEMON_ASSERT

  (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \

                        static_cast<const char*>(0)))

/// \ingroup exceptions

///

/// \brief Macro for internal assertions

///

/// Macro for internal assertions, it is used in the library to check

/// the consistency of results of algorithms, several pre- and

/// postconditions and invariants. The checking is disabled by

/// default, but it can be turned on with the macro \c

/// LEMON_ENABLE_DEBUG.

/// \code

/// #define LEMON_ENABLE_DEBUG

/// \endcode

/// or with compilation parameters:

/// \code

/// g++ -DLEMON_ENABLE_DEBUG

/// make CXXFLAGS='-DLEMON_ENABLE_DEBUG'

/// \endcode

///

/// This macro works like the \c LEMON_ASSERT macro, therefore the

/// current behaviour depends on the settings of \c LEMON_ASSERT

/// macro.

///

/// \see LEMON_ASSERT

    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                            \

                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))

#else

#  ifndef LEMON_ASSERT_HANDLER

#    define LEMON_ASSERT(exp, msg)  (static_cast<void>(0))

#    define LEMON_FIXME(msg) (static_cast<void>(0))

#    define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#  else

        LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                        \

                             #exp), 0)))

                             static_cast<const char*>(0)))

#    if LEMON_ENABLE_DEBUG

#      define LEMON_DEBUG(exp, msg)

                                #exp), 0)))

#    else

#      define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#    endif

#  endif

#endif

      /// Length of the path ie. the number of arcs in the path.

      int length() const { return 0;}

      /// Returns whether the path is empty.

      bool empty() const { return true;}

      /// Resets the path to an empty path.

      void clear() {}

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths.

      class ArcIt {

      public:

        /// Default constructor

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const Path &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        ArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          Path<Digraph> pc;

          _Path p, pp(pc);

          int l = p.length();

          int e = p.empty();

          p.clear();

          p = pc;

          typename _Path::ArcIt id, ii(INVALID), i(p);

          ++i;

          typename Digraph::Arc ed = i;

          e = (i == ii);

          e = (i != ii);

          e = (i < ii);

          ignore_unused_variable_warning(l);

          ignore_unused_variable_warning(pp);

          ignore_unused_variable_warning(e);

          ignore_unused_variable_warning(id);

          ignore_unused_variable_warning(ii);

          ignore_unused_variable_warning(ed);

        }

      };

      bool empty() const { return true;}

      /// \brief Forward or reverse dumping

      ///

      /// If the RevPathTag is defined and true then reverse dumping

      /// is provided in the path dumper. In this case instead of the

      /// ArcIt the RevArcIt iterator should be implemented in the

      /// dumper.

      typedef False RevPathTag;

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths.

      class ArcIt {

      public:

        /// Default constructor

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const PathDumper&) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        ArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

      };

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths in

      /// reverse direction.

      class RevArcIt {

      public:

        /// Default constructor

        RevArcIt() {}

        /// Invalid constructor

        RevArcIt(Invalid) {}

        /// Constructor for first arc

        RevArcIt(const PathDumper &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        RevArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const RevArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const RevArcIt&) const {return true;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          function_requires<_path_bits::

            PathDumperConstraints<Digraph, _Path> >();

        }

      };

    };

    ///@}

  }

} // namespace lemon

#endif // LEMON_CONCEPT_PATH_H

  template <typename _Type>

  class ExceptionMember {

  public:

    typedef _Type Type;

    ExceptionMember() throw() {

      try {

        ptr.reset(new Type());

      } catch (...) {}

    }

    ExceptionMember(const Type& type) throw() {

      try {

        ptr.reset(new Type());

        if (ptr.get() == 0) return;

        *ptr = type;

      } catch (...) {}

    }

    ExceptionMember(const ExceptionMember& copy) throw() {

      try {

        if (!copy.valid()) return;

        ptr.reset(new Type());

        if (ptr.get() == 0) return;

        *ptr = copy.get();

      } catch (...) {}

    }

    ExceptionMember& operator=(const ExceptionMember& copy) throw() {

      if (ptr.get() == 0) return;

      try {

        if (!copy.valid()) return;

      } catch (...) {}

    }

    void set(const Type& type) throw() {

      if (ptr.get() == 0) return;

      try {

        *ptr = type;

      } catch (...) {}

    }

    const Type& get() const {

      return *ptr;

    }

    bool valid() const throw() {

      return ptr.get() != 0;

    }

  private:

    std::auto_ptr<_Type> ptr;

  };

  /// Exception-safe convenient error message builder class.

  /// Helper class which provides a convenient ostream-like (operator <<

  /// based) interface to create a string message. Mostly useful in

  /// exception classes (therefore the name).

  class ErrorMessage {

  protected:

    ///\e

    ///\todo The good solution is boost::shared_ptr...

        os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '

           << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER

           << " translate\n"

           << sc << " dup scale\n90 rotate\n"

           << -bb.left() << ' ' << -bb.top() << " translate\n";

        }

    else if(_scale!=1.0) os << _scale << " dup scale\n";

    if(_showArcs) {

      os << "%Arcs:\ngsave\n";

      if(_enableParallel) {

        std::vector<Arc> el;

        for(ArcIt e(g);e!=INVALID;++e)

          if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0

             &&g.source(e)!=g.target(e))

            el.push_back(e);

        std::sort(el.begin(),el.end(),arcLess(g));

        typename std::vector<Arc>::iterator j;

        for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {

          for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;

          double sw=0;

          for(typename std::vector<Arc>::iterator e=i;e!=j;++e)

            sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;

          sw-=_parArcDist;

          sw/=-2.0;

          dim2::Point<double>

            dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);

          double l=std::sqrt(dvec.normSquare());

          //\todo better 'epsilon' would be nice here.

          dim2::Point<double> d(dvec/std::max(l,EPSILON));

//           m=dim2::Point<double>(mycoords[g.target(*i)]+

//                                 mycoords[g.source(*i)])/2.0;

//            m=dim2::Point<double>(mycoords[g.source(*i)])+

//             dvec*(double(_nodeSizes[g.source(*i)])/

//                (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));

            d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;

          for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {

            sw+=_arcWidths[*e]*_arcWidthScale/2.0;

            dim2::Point<double> mm=m+rot90(d)*sw/.75;

            if(_drawArrows) {

              int node_shape;

              dim2::Point<double> s=mycoords[g.source(*e)];

              dim2::Point<double> t=mycoords[g.target(*e)];

              double rn=_nodeSizes[g.target(*e)]*_nodeScale;

              node_shape=_nodeShapes[g.target(*e)];

              dim2::Bezier3 bez(s,mm,mm,t);

              double t1=0,t2=1;

              for(int ii=0;ii<INTERPOL_PREC;++ii)

                if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;

                else t1=(t1+t2)/2;

              dim2::Point<double> apoint=bez((t1+t2)/2);

              rn = _arrowLength+_arcWidths[*e]*_arcWidthScale;

              rn*=rn;

              t2=(t1+t2)/2;t1=0;

              for(int ii=0;ii<INTERPOL_PREC;++ii)

                if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;

                else t2=(t1+t2)/2;

              dim2::Point<double> linend=bez((t1+t2)/2);

              bez=bez.before((t1+t2)/2);

//               rn=_nodeSizes[g.source(*e)]*_nodeScale;

//               node_shape=_nodeShapes[g.source(*e)];

//               t1=0;t2=1;

//               for(int i=0;i<INTERPOL_PREC;++i)

//                 if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape))

//                   t1=(t1+t2)/2;

//                 else t2=(t1+t2)/2;

#include <vector>

#include <map>

#include <cmath>

#include <algorithm>

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/maps.h>

#include <lemon/bits/traits.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/bits/default_map.h>

///\ingroup gutils

///\file

///\brief Graph utilities.

namespace lemon {

  /// \addtogroup gutils

  /// @{

  ///Creates convenience typedefs for the digraph types and iterators

  ///This \c \#define creates convenience typedefs for the following types

  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,

  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,

  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

  typedef Digraph::ArcMap<double> DoubleArcMap

  ///Creates convenience typedefs for the digraph types and iterators

  ///\see DIGRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

  typedef typename Digraph::ArcIt ArcIt;                                \

  typedef typename Digraph::template ArcMap<double> DoubleArcMap

  ///Creates convenience typedefs for the graph types and iterators

  ///This \c \#define creates the same convenience typedefs as defined

  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates

  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,

  ///\c DoubleEdgeMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

  typedef Graph::EdgeMap<double> DoubleEdgeMap

  ///Creates convenience typedefs for the graph types and iterators

  ///\see GRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

  typedef typename Graph::EdgeIt EdgeIt;                                \

  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap

  /// \brief Function to count the items in the graph.

  ///

  /// This function counts the items (nodes, arcs etc) in the graph.

  /// The complexity of the function is O(n) because

  /// it iterates on all of the items.

  template <typename Graph, typename Item>

  inline int countItems(const Graph& g) {

    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

    int num = 0;

    for (ItemIt it(g); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  // Node counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountNodesSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Node>(g);

      }

    };

    template <typename Graph>

    struct CountNodesSelector<

      Graph, typename

      enable_if<typename Graph::NodeNumTag, void>::type>

    public:

      GraphArcMapStorage(const Graph& graph, Map& map,

                         const Converter& converter = Converter())

        : _graph(graph), _map(map), _converter(converter) {}

      virtual ~GraphArcMapStorage() {}

      virtual void set(const Item& item ,const std::string& value) {

        _map.set(_graph.direct(item, dir), _converter(value));

      }

    };

    class ValueStorageBase {

    public:

      ValueStorageBase() {}

      virtual ~ValueStorageBase() {}

      virtual void set(const std::string&) = 0;

    };

    template <typename _Value, typename _Converter = DefaultConverter<_Value> >

    class ValueStorage : public ValueStorageBase {

    public:

      typedef _Value Value;

      typedef _Converter Converter;

    private:

      Value& _value;

      Converter _converter;

    public:

      ValueStorage(Value& value, const Converter& converter = Converter())

      virtual void set(const std::string& value) {

        _value = _converter(value);

      }

    };

    template <typename Value>

    struct MapLookUpConverter {

      const std::map<std::string, Value>& _map;

      MapLookUpConverter(const std::map<std::string, Value>& map)

        : _map(map) {}

      Value operator()(const std::string& str) {

        typename std::map<std::string, Value>::const_iterator it =

          _map.find(str);

        if (it == _map.end()) {

          std::ostringstream msg;

          msg << "Item not found: " << str;

          throw DataFormatError(msg.str().c_str());

        }

        return it->second;

      }

    };

    template <typename Graph>

    struct GraphArcLookUpConverter {

      const Graph& _graph;

      const std::map<std::string, typename Graph::Edge>& _map;

      GraphArcLookUpConverter(const Graph& graph,

                              const std::map<std::string,

    ArcMaps _arc_maps;

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

      Attributes;

    Attributes _attributes;

    bool _use_nodes;

    bool _use_arcs;

    bool _skip_nodes;

    bool _skip_arcs;

    int line_num;

    std::istringstream line;

  public:

    /// \brief Constructor

    ///

    /// Construct a directed graph reader, which reads from the given

    /// input stream.

    DigraphReader(std::istream& is, Digraph& digraph)

      : _is(&is), local_is(false), _digraph(digraph),

        _use_nodes(false), _use_arcs(false),

        _skip_nodes(false), _skip_arcs(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph reader, which reads from the given

    /// file.

    DigraphReader(const std::string& fn, Digraph& digraph)

      : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),

        _skip_nodes(false), _skip_arcs(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph reader, which reads from the given

    /// file.

    DigraphReader(const char* fn, Digraph& digraph)

      : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),

        _skip_nodes(false), _skip_arcs(false) {}

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

    friend DigraphReader<Digraph> digraphReader<>(std::istream& is,

                                                  Digraph& digraph);

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

                                                  Digraph& digraph);

    friend DigraphReader<Digraph> digraphReader<>(const char *fn,

    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),

        _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),

        _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;

      }

    }

  private:

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

    friend GraphReader<Graph> graphReader<>(const std::string& fn,

                                            Graph& graph);

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

    GraphReader(GraphReader& other)

        : _graph(graph), _map(map), _converter(converter) {}

      virtual ~GraphArcMapStorage() {}

      virtual std::string get(const Item& item) {

        return _converter(_map[_graph.direct(item, dir)]);