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>

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

      }

    };

#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);

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

    ///

	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) {}

	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;

    Attributes _attributes;

    bool _skip_nodes;

    bool _skip_arcs;

  public:

    /// \e

    DigraphWriter(std::ostream& is, Digraph& digraph) 

      : _os(&is), local_os(false), _digraph(digraph),

	_skip_nodes(false), _skip_arcs(false) {}

    /// \e

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

      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),

	_skip_nodes(false), _skip_arcs(false) {}

    /// \e

    DigraphWriter(const char* fn, Digraph& digraph) 

      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),