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.

 *

 */

#ifndef LEMON_GRAPH_UTILS_H

#define LEMON_GRAPH_UTILS_H

#include <iterator>

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

#define DIGRAPH_TYPEDEFS(Digraph)					\

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

#define GRAPH_TYPEDEFS(Graph)						\

  DIGRAPH_TYPEDEFS(Graph);						\

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

    {

      static int count(const Graph &g) {

        return g.nodeNum();

      }

    };    

  }

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

  ///

  /// This function counts the nodes in the graph.

  /// The complexity of the function is O(n) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// If the graph contains a \e nodeNum() member function and a 

  /// \e NodeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the node set.

  template <typename Graph>

  inline int countNodes(const Graph& g) {

    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);

  }

  // Arc counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountArcsSelector {

      static int count(const Graph &g) {

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

      }

    };

    template <typename Graph>

    struct CountArcsSelector<

      Graph, 

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

    {

      static int count(const Graph &g) {

        return g.arcNum();

      }

    };    

  }

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

  ///

  /// This function counts the arcs in the graph.

  /// The complexity of the function is O(e) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// If the graph contains a \e arcNum() member function and a 

  /// \e EdgeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the arc set.

  template <typename Graph>

  inline int countArcs(const Graph& g) {

    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);

  }

  // Edge counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountEdgesSelector {

      static int count(const Graph &g) {

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

      }

	}

      }

    };

  public:

    /// \brief Constructor.

    ///

    /// Constructor for creating out-degree map.

    explicit OutDegMap(const Digraph& digraph) 

      : _digraph(digraph), _deg(digraph) {

      Parent::attach(_digraph.notifier(typename Digraph::Arc()));

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = countOutArcs(_digraph, it);

      }

    }

    /// Gives back the out-degree of a Node.

    int operator[](const Key& key) const {

      return _deg[key];

    }

  protected:

    typedef typename Digraph::Arc Arc;

    virtual void add(const Arc& arc) {

      ++_deg[_digraph.source(arc)];

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        ++_deg[_digraph.source(arcs[i])];

      }

    }

    virtual void erase(const Arc& arc) {

      --_deg[_digraph.source(arc)];

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        --_deg[_digraph.source(arcs[i])];

      }

    }

    virtual void build() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = countOutArcs(_digraph, it);

      }      

    }

    virtual void clear() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = 0;

      }

    }

  private:

    const Digraph& _digraph;

    AutoNodeMap _deg;

  };

  ///Dynamic arc look up between given endpoints.

  ///\ingroup gutils

  ///Using this class, you can find an arc in a digraph from a given

  ///source to a given target in amortized time <em>O(log d)</em>,

  ///where <em>d</em> is the out-degree of the source node.

  ///

  ///It is possible to find \e all parallel arcs between two nodes with

  ///the \c findFirst() and \c findNext() members.

  ///

  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your

  ///digraph is not changed so frequently.

  ///

  ///This class uses a self-adjusting binary search tree, Sleator's

  ///and Tarjan's Splay tree for guarantee the logarithmic amortized

  ///time bound for arc lookups. This class also guarantees the

  ///optimal time bound in a constant factor for any distribution of

  ///queries.

  ///

  ///\param G The type of the underlying digraph.  

  ///

  ///\sa ArcLookUp  

  ///\sa AllArcLookUp  

  template<class G>

  class DynArcLookUp 

    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase

  {

  public:

    typedef typename ItemSetTraits<G, typename G::Arc>

    ::ItemNotifier::ObserverBase Parent;

    typedef G Digraph;

  protected:

    class AutoNodeMap : public DefaultMap<G, Node, Arc> {

    public:

      typedef DefaultMap<G, Node, Arc> Parent;

      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}

      virtual void add(const Node& node) {

	Parent::add(node);

	Parent::set(node, INVALID);

      }

      virtual void add(const std::vector<Node>& nodes) {

	Parent::add(nodes);

	for (int i = 0; i < int(nodes.size()); ++i) {

	  Parent::set(nodes[i], INVALID);

	}

      }

      virtual void build() {

	Parent::build();

	Node it;

	typename Parent::Notifier* nf = Parent::notifier();

	for (nf->first(it); it != INVALID; nf->next(it)) {

	  Parent::set(it, INVALID);

	}

      }

    };

    const Digraph &_g;

    AutoNodeMap _head;

    typename Digraph::template ArcMap<Arc> _parent;

    typename Digraph::template ArcMap<Arc> _left;

    typename Digraph::template ArcMap<Arc> _right;

    class ArcLess {

      const Digraph &g;

    public:

      ArcLess(const Digraph &_g) : g(_g) {}

      bool operator()(Arc a,Arc b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database.

    DynArcLookUp(const Digraph &g) 

      : _g(g),_head(g),_parent(g),_left(g),_right(g) 

    { 

      Parent::attach(_g.notifier(typename Digraph::Arc()));

      refresh(); 

    }

  protected:

    virtual void add(const Arc& arc) {

      insert(arc);

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

	insert(arcs[i]);

      }

    }

    virtual void erase(const Arc& arc) {

      remove(arc);

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

	remove(arcs[i]);

      }     

    }

    virtual void build() {

      refresh();

    }

    virtual void clear() {

      for(NodeIt n(_g);n!=INVALID;++n) {

	_head.set(n, INVALID);

      }

    }

    void insert(Arc arc) {

    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of

    /// outgoing arcs of \c s.  

    ///\param s The source node 

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists, \ref INVALID

    /// otherwise.

    Arc findFirst(Node s, Node t) const

    {

      Arc a = _head[s];

      Arc r = INVALID;

      while (true) {

	if (_g.target(a) < t) {

	  if (_right[a] == INVALID) {

	    const_cast<DynArcLookUp&>(*this).splay(a);

	    return r;

	  } else {

	    a = _right[a];

	  }

	} else {

	  if (_g.target(a) == t) {

	    r = a;

	  }

	  if (_left[a] == INVALID) {

	    const_cast<DynArcLookUp&>(*this).splay(a);

	    return r;

	  } else {

	    a = _left[a];

	  }

	}

      }

    }

    ///Find the next arc between two nodes.

    ///Find the next arc between two nodes in time

    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of

    /// outgoing arcs of \c s.  

    ///\param s The source node 

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists, \ref INVALID

    /// otherwise.

    ///\note If \c e is not the result of the previous \c findFirst()

    ///operation then the amorized time bound can not be guaranteed.

#ifdef DOXYGEN

    Arc findNext(Node s, Node t, Arc a) const

#else

    Arc findNext(Node, Node t, Arc a) const

#endif

    {

      if (_right[a] != INVALID) {

	a = _right[a];

	while (_left[a] != INVALID) {

	  a = _left[a];

	}

	const_cast<DynArcLookUp&>(*this).splay(a);

      } else {

	while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {

	  a = _parent[a];

	}

	if (_parent[a] == INVALID) {

	  return INVALID;

	} else {

	  a = _parent[a];

	  const_cast<DynArcLookUp&>(*this).splay(a);

	}

      }

      if (_g.target(a) == t) return a;

      else return INVALID;    

    }

  };

  ///Fast arc look up between given endpoints.

  ///\ingroup gutils

  ///Using this class, you can find an arc in a digraph from a given

  ///source to a given target in time <em>O(log d)</em>,

  ///where <em>d</em> is the out-degree of the source node.

  ///

  ///It is not possible to find \e all parallel arcs between two nodes.

  ///Use \ref AllArcLookUp for this purpose.

  ///

  ///\warning This class is static, so you should refresh() (or at least

  ///refresh(Node)) this data structure

  ///whenever the digraph changes. This is a time consuming (superlinearly

  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).

  ///

  ///\param G The type of the underlying digraph.

  ///

  ///\sa DynArcLookUp

  ///\sa AllArcLookUp  

  template<class G>

  class ArcLookUp 

  {

  public:

    typedef G Digraph;

  protected:

    const Digraph &_g;

    typename Digraph::template NodeMap<Arc> _head;

    typename Digraph::template ArcMap<Arc> _left;

    typename Digraph::template ArcMap<Arc> _right;

    class ArcLess {

      const Digraph &g;

    public:

      ArcLess(const Digraph &_g) : g(_g) {}

      bool operator()(Arc a,Arc b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database, which remains valid until the digraph

    ///changes.

    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}

  private:

    Arc refreshRec(std::vector<Arc> &v,int a,int b) 

    {

      int m=(a+b)/2;

      Arc me=v[m];

      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;

      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;

      return me;

    }

  public:

    ///Refresh the data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

    ///the number of the outgoing arcs of \c n.

    void refresh(Node n) 

    {

      std::vector<Arc> v;

      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);

      if(v.size()) {

	std::sort(v.begin(),v.end(),ArcLess(_g));

	_head[n]=refreshRec(v,0,v.size()-1);

      }

      else _head[n]=INVALID;

    }

    ///Refresh the full data structure.

    ///Build up the full search database. In fact, it simply calls

    ///\ref refresh(Node) "refresh(n)" for each node \c n.

    ///

    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

    ///the number of the arcs of \c n and <em>D</em> is the maximum

    ///out-degree of the digraph.

    void refresh() 

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    }

    ///Find an arc between two nodes.

    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where

    /// <em>d</em> is the number of outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then

    ///\ref refresh(Node) "refresh(n)" is enough.

    ///

    Arc operator()(Node s, Node t) const

    {

      Arc e;

      for(e=_head[s];

	  e!=INVALID&&_g.target(e)!=t;

	  e = t < _g.target(e)?_left[e]:_right[e]) ;

      return e;

    }

  };

  ///Fast look up of all arcs between given endpoints.

  ///\ingroup gutils

  ///This class is the same as \ref ArcLookUp, with the addition

  ///that it makes it possible to find all arcs between given endpoints.

  ///

  ///\warning This class is static, so you should refresh() (or at least

  ///refresh(Node)) this data structure

  ///whenever the digraph changes. This is a time consuming (superlinearly

  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).

  ///

  ///\param G The type of the underlying digraph.

  ///

  ///\sa DynArcLookUp

  ///\sa ArcLookUp  

  template<class G>

  class AllArcLookUp : public ArcLookUp<G>

  {

    using ArcLookUp<G>::_g;

    using ArcLookUp<G>::_right;

    using ArcLookUp<G>::_left;

    using ArcLookUp<G>::_head;

    typedef G Digraph;

    typename Digraph::template ArcMap<Arc> _next;

    Arc refreshNext(Arc head,Arc next=INVALID)

    {

      if(head==INVALID) return next;

      else {

	next=refreshNext(_right[head],next);

// 	_next[head]=next;

	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))

	  ? next : INVALID;

	return refreshNext(_left[head],head);

      }

    }

    void refreshNext()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);

    }

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database, which remains valid until the digraph

    ///changes.

    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}

    ///Refresh the data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

    ///the number of the outgoing arcs of \c n.

    void refresh(Node n) 

    {

      ArcLookUp<G>::refresh(n);

      refreshNext(_head[n]);

    }

    ///Refresh the full data structure.

    ///Build up the full search database. In fact, it simply calls

    ///\ref refresh(Node) "refresh(n)" for each node \c n.

    ///

    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

    ///the number of the arcs of \c n and <em>D</em> is the maximum

    ///out-degree of the digraph.

    void refresh() 

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);

    }

    ///Find an arc between two nodes.

    ///Find an arc between two nodes.

    ///\param s The source node

    ///\param t The target node

    ///\param prev The previous arc between \c s and \c t. It it is INVALID or

    ///not given, the operator finds the first appropriate arc.

    ///\return An arc from \c s to \c t after \c prev or

    ///\ref INVALID if there is no more.

    ///

    ///For example, you can count the number of arcs from \c u to \c v in the

    ///following way.

    ///\code

    ///AllArcLookUp<ListDigraph> ae(g);

    ///...

    ///int n=0;

    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;

    ///\endcode

    ///

    ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where

    /// <em>d</em> is the number of outgoing arcs of \c s. Then, the

    ///consecutive arcs are found in constant time.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then

    ///\ref refresh(Node) "refresh(n)" is enough.

    ///

#ifdef DOXYGEN

    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}

#else

    using ArcLookUp<G>::operator() ;

    Arc operator()(Node s, Node t, Arc prev) const

    {

      return prev==INVALID?(*this)(s,t):_next[prev];

    }

#endif

  };

	return '\r';

      case 't':

	return '\t';

      case 'v':

	return '\v';

      case 'x':

	{

	  int code;

	  if (!is.get(c) || !isHex(c)) 

	    throw DataFormatError("Escape format error");

	  else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);

	  else code = code * 16 + valueHex(c);

	  return code;

	}

      default:

	{

	  int code;

	  if (!isOct(c)) 

	    throw DataFormatError("Escape format error");

	  else if (code = valueOct(c), !is.get(c) || !isOct(c)) 

	    is.putback(c);

	  else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 

	    is.putback(c);

	  else code = code * 8 + valueOct(c);

	  return code;

	}	      

      } 

    }

    std::istream& readToken(std::istream& is, std::string& str) {

      std::ostringstream os;

      char c;

      is >> std::ws;

      if (!is.get(c)) 

	return is;

      if (c == '\"') {

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

	  if (c == '\\') 

	    c = readEscape(is);

	  os << c;

	}

	if (!is) 

	  throw DataFormatError("Quoted format error");

      } else {

	is.putback(c);

	while (is.get(c) && !isWhiteSpace(c)) {

	  if (c == '\\') 

	    c = readEscape(is);

	  os << c;

	}

	if (!is) {

	  is.clear();

	} else {

	  is.putback(c);

	}

      }

      str = os.str();

      return is;

    }

    std::istream& readIdentifier(std::istream& is, std::string& str) {

      std::ostringstream os;

      char c;

      is >> std::ws;

      if (!is.get(c))

	return is;

      if (!isIdentifierFirstChar(c))

	throw DataFormatError("Wrong char in identifier");

      os << c;

      while (is.get(c) && !isWhiteSpace(c)) {

	if (!isIdentifierChar(c)) 

	  throw DataFormatError("Wrong char in identifier");	  

	os << c;

      }

      if (!is) is.clear();

      str = os.str();

      return is;

    }

  }

  /// \e

  template <typename _Digraph>

  class DigraphReader {

  public:

    typedef _Digraph Digraph;

  private:

    std::istream* _is;

    bool local_is;

    Digraph& _digraph;

    std::string _nodes_caption;

    std::string _arcs_caption;

    std::string _attributes_caption;

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

    NodeIndex _node_index;

    typedef std::map<std::string, Arc> ArcIndex;

    ArcIndex _arc_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<Arc>*> >ArcMaps;

    ArcMaps _arc_maps;

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

      Attributes;

    Attributes _attributes;

    bool _use_nodes;

    bool _use_arcs;

    int line_num;

    std::istringstream line;

  public:

    /// \e

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

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

	_use_nodes(false), _use_arcs(false) {}

    /// \e

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

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

    	_use_nodes(false), _use_arcs(false) {}

    /// \e

    DigraphReader(const char* fn, Digraph& digraph) 

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

    	_use_nodes(false), _use_arcs(false) {}

    /// \e

    DigraphReader(DigraphReader& other) 

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

	_use_nodes(other._use_nodes), _use_arcs(other._use_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;

    }

    /// \e

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

      }

    }

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

	: _map(map) {}

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

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

	  _map.find(str);

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

	  throw DataFormatError("Item not found");

	}

	return it->second;

      }

    };

    bool isWhiteSpace(char c) {

      return c == ' ' || c == '\t' || c == '\v' || 

        c == '\n' || c == '\r' || c == '\f'; 

    }

    bool isEscaped(char c) {

      return c == '\\' || c == '\"' || c == '\'' || 

	c == '\a' || c == '\b';

    }

    static void writeEscape(std::ostream& os, char c) {

      switch (c) {

      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 << static_cast<int>(c);

	} else {

	  os << c;

	}

	return;

      }     

    }

    bool requireEscape(const std::string& str) {

      std::istringstream is(str);

      char c;

      while (is.get(c)) {

	if (isWhiteSpace(c) || isEscaped(c)) {

	  return true;

	}

      }

      return false;

    }

    std::ostream& writeToken(std::ostream& os, const std::string& str) {

      if (requireEscape(str)) {

	os << '\"';

	for (std::string::const_iterator it = str.begin(); 

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

	  writeEscape(os, *it);

	}	

	os << '\"';

      } else {

	os << str;

      }

      return os;

    }

  }

  /// \e

  template <typename _Digraph>

  class DigraphWriter {

  public:

    typedef _Digraph Digraph;

  private:

    std::ostream* _os;

    bool local_os;

    Digraph& _digraph;

    std::string _nodes_caption;

    std::string _arcs_caption;

    std::string _attributes_caption;

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

    NodeIndex _node_index;

    typedef std::map<Arc, std::string> ArcIndex;

    ArcIndex _arc_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<Arc>* > >ArcMaps;

    ArcMaps _arc_maps;

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

      _writer_bits::ValueStorageBase*> > Attributes;