RhodeCode

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

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

  ///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() {

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

    ///

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

      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;

    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;