RhodeCode

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

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

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

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

      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;

      }

      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;