RhodeCode

namespace lemon {

  ///Default traits class of Bfs class.

  ///Default traits class of Bfs class.

  template<class GR>

  struct BfsDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the shortest paths.

    /// 

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %BFS algorithm.

  ///

  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it

  ///is only passed to \ref BfsDefaultTraits.

  ///The default traits class is

  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".

  ///See \ref BfsDefaultTraits for the documentation of

  ///a Bfs traits class.

#ifdef DOXYGEN

  template <typename GR,

	    typename TR>

#else

  template <typename GR=ListDigraph,

	    typename TR=BfsDefaultTraits<GR> >

#endif

    bool reached(Node v) { return (*_reached)[v]; }

    ///@}

  };

  ///Default traits class of Bfs function.

  ///Default traits class of Bfs function.

  template<class GR>

  struct BfsWizardDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the shortest paths.

    /// 

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  template<class _Digraph>

  struct BfsVisitDefaultTraits {

    /// \brief The digraph type the algorithm runs on. 

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    /// 

  ///  

  /// This class provides an efficient implementation of the %BFS algorithm

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// on every bfs event the \c Visitor class member functions. 

  ///

  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it

  /// is only passed to \ref BfsDefaultTraits.

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Bfs events. If you want to observe the bfs

  /// events you should implement your own Visitor class.

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a Bfs visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

	    typename _Visitor = BfsVisitor<_Digraph>,

	    typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  ///\brief A Binary Heap implementation.

  ///

  ///This class implements the \e binary \e heap data structure. A \e heap

  ///is a data structure for storing items with specified values called \e

  ///priorities in such a way that finding the item with minimum priority is

  ///efficient. \c Compare specifies the ordering of the priorities. In a heap

  ///one can change the priority of an item, add or erase an item, etc.

  ///

  ///to handle the cross references.

  ///default is \c std::less<_Prio>.

  ///

  ///\sa FibHeap

  ///\sa Dijkstra

  template <typename _Prio, typename _ItemIntMap,

	    typename _Compare = std::less<_Prio> >

  class BinHeap {

  /// unreliable functionality. Because the alteration observing signals

  /// only erasing and adding but not the reversing it will stores bad

  /// degrees. The sub graph adaptors cannot signal the alterations because

  /// just a setting in the filter map can modify the graph and this cannot

  /// be watched in any way.

  ///

  /// \param _Container The container which is observed.

  /// \param _Item The item type which is obserbved.

  template <typename _Container, typename _Item>

  class AlterationNotifier {

  public:

    typedef True Notifier;

    typedef _Container Container;

    /// The observer interface contains some pure virtual functions

    /// to override. The add() and erase() functions are

    /// to notify the oberver when one item is added or

    /// erased.

    ///

    /// The build() and clear() members are to notify the observer

    /// about the container is built from an empty container or

    /// is cleared to an empty container. 

    class ObserverBase {

    protected:

      typedef AlterationNotifier Notifier;

      friend class AlterationNotifier;

      /// \brief Default constructor.

#ifndef LEMON_BEZIER_H

#define LEMON_BEZIER_H

///\ingroup misc

///\file

///\brief Classes to compute with Bezier curves.

///

///Up to now this file is used internally by \ref graph_to_eps.h

#include<lemon/dim2.h>

namespace lemon {

  namespace dim2 {

class BezierBase {

public:

  /// \ingroup graphbits

  ///

  /// \brief Graph map based on the std::vector storage.

  ///

  /// The VectorMap template class is graph map structure what

  /// automatically updates the map when a key is added to or erased from

  /// the map. This map type uses the std::vector to store the values.

  ///

  template <typename _Graph, typename _Item, typename _Value>

  class VectorMap 

    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  private:

    /// The container type of the map.

    typedef std::vector<_Value> Container;	

#include<vector>

#include<lemon/math.h>

#include<lemon/maps.h>

///\ingroup misc

///\file

///\brief Tools to manage RGB colors.

namespace lemon {

  /// \addtogroup misc

  /// @{

  ///Data structure representing RGB colors.

    /// \addtogroup concept

    /// @{

    /// \brief A skeleton structure for representing directed paths in

    /// a digraph.

    ///

    /// A skeleton structure for representing directed paths in a

    /// digraph.  

    ///

    /// In a sense, the path can be treated as a list of arcs. The

    /// lemon path type stores just this list. As a consequence it

    /// cannot enumerate the nodes in the path and the zero length

    /// paths cannot store the source.

    ///

    template <typename _Digraph>

    class Path {

    /// The main purpose of this concept is that the shortest path

    /// algorithms can enumerate easily the arcs in reverse order.

    /// If we would like to give back a real path from these

    /// algorithms then we should create a temporarly path object. In

    /// Lemon such algorithms gives back a path dumper what can

    /// assigned to a real path and the dumpers can be implemented as

    /// an adaptor class to the predecessor map.

    ///

    /// The paths can be constructed from any path type by a

    /// template constructor or a template assignment operator.

    /// 

    template <typename _Digraph>

    class PathDumper {

    public:

#include <lemon/concept_check.h>

namespace lemon {

  ///Default traits class of Dfs class.

  ///Default traits class of Dfs class.

  template<class GR>

  struct DfsDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the %DFS paths.

    /// 

    }

  };

  ///%DFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %DFS algorithm.

  ///

  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it

  ///is only passed to \ref DfsDefaultTraits.

  ///The default traits class is

  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".

  ///See \ref DfsDefaultTraits for the documentation of

  ///a Dfs traits class.

#ifdef DOXYGEN

  template <typename GR,

	    typename TR>

#else

  template <typename GR=ListDigraph,

	    typename TR=DfsDefaultTraits<GR> >

#endif

  class Dfs {

    bool reached(Node v) { return (*_reached)[v]; }

    ///@}

  };

  ///Default traits class of Dfs function.

  ///Default traits class of Dfs function.

  template<class GR>

  struct DfsWizardDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the %DFS paths.

    /// 

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of DfsVisit class.

  ///

  /// Default traits class of DfsVisit class.

  template<class _Digraph>

  struct DfsVisitDefaultTraits {

    /// \brief The digraph type the algorithm runs on. 

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    /// 

  /// \ingroup search

  /// This class provides an efficient implementation of the %DFS algorithm

  /// with visitor interface.

  ///

  /// The %DfsVisit class provides an alternative interface to the Dfs

  /// class. It works with callback mechanism, the DfsVisit object calls

  /// on every dfs event the \c Visitor class member functions. 

  ///

  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it

  /// is only passed to \ref DfsDefaultTraits.

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Dfs events. If you want to observe the dfs

  /// events you should implement your own Visitor class.

  /// algorithm. The default traits class is

  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a Dfs visit traits class.

  ///

  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  ///Default traits class of Dijkstra class.

  ///Default traits class of Dijkstra class.

  template<class GR, class LM>

  struct DijkstraDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///The type of the map that stores the arc lengths.

    ///The type of the map that stores the arc lengths.

  ///\ref concepts::ReadMap "ReadMap",

  ///so it is easy to change it to any kind of length.

  ///

  ///The type of the length is determined by the

  ///\ref concepts::ReadMap::Value "Value" of the length map.

  ///

  ///It is also possible to change the underlying priority heap.

  ///

  ///is \ref ListDigraph. The value of GR is not used directly by

  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.

  ///arcs. It is read once for each arc, so the map may involve in

  ///relatively time consuming process to compute the arc length if

  ///it is necessary. The default map type is \ref

  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value

  ///of LM is not used directly by Dijkstra, it is only passed to \ref

  ///various data types used by the algorithm.  The default traits

  ///class is \ref DijkstraDefaultTraits

  ///"DijkstraDefaultTraits<GR,LM>".  See \ref

  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits

  ///class.

#ifdef DOXYGEN

  template <typename GR, typename LM, typename TR>

#else

  template <typename GR=ListDigraph,

	    typename LM=typename GR::template ArcMap<int>,

	    typename TR=DijkstraDefaultTraits<GR,LM> >

#endif

  ///Default traits class of Dijkstra function.

  ///Default traits class of Dijkstra function.

  template<class GR, class LM>

  struct DijkstraWizardDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///The type of the map that stores the arc lengths.

    ///The type of the map that stores the arc lengths.

  }

  template<class X> struct ArcWidthsTraits : public T {

    const X &_arcWidths;

    ArcWidthsTraits(const T &t,const X &x) : T(t), _arcWidths(x) {}

  };

  ///Sets the map of the arc widths

  ///Sets the map of the arc widths

  template<class X> GraphToEps<ArcWidthsTraits<X> > arcWidths(const X &x)

  {

    dontPrint=true;

    return GraphToEps<ArcWidthsTraits<X> >(ArcWidthsTraits<X>(*this,x));

  }

  template<class X> struct NodeColorsTraits : public T {

    const X &_nodeColors;

  }

  template<class X> struct ArcColorsTraits : public T {

    const X &_arcColors;

    ArcColorsTraits(const T &t,const X &x) : T(t), _arcColors(x) {}

  };

  ///Sets the map of the arc colors

  ///Sets the map of the arc colors

  ///

  ///\sa Palette

  template<class X> GraphToEps<ArcColorsTraits<X> >

  arcColors(const X &x)

  {

    dontPrint=true;

    return GraphToEps<ArcColorsTraits<X> >(ArcColorsTraits<X>(*this,x));

  }

  ///   ...

  /// }

  ///\endcode

  /// 

  ///\sa findArc()

  ///\sa ArcLookUp

  ///\sa AllArcLookUp

  ///\sa DynArcLookUp

  template <typename _Graph>

  class ConArcIt : public _Graph::Arc {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Arc Parent;

    typedef typename Graph::Arc Arc;

  /// use it the following way:

  ///\code

  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {

  ///   ...

  /// }

  ///\endcode

  ///

  ///\sa findEdge()

  template <typename _Graph>

  class ConEdgeIt : public _Graph::Edge {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Edge Parent;

    typedef typename Graph::Edge Edge;

  /// This type provides simple invertable graph-maps. 

  /// The InvertableMap wraps an arbitrary ReadWriteMap 

  /// and if a key is set to a new value then store it

  /// in the inverse map.

  ///

  /// The values of the map can be accessed

  /// with stl compatible forward iterator.

  ///

  ///

  /// \see IterableValueMap

  template <typename _Graph, typename _Item, typename _Value>

  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {

  private:

    typedef DefaultMap<_Graph, _Item, _Value> Map;

    typedef _Graph Graph;

  /// descriptor (id) for each item of the same type (e.g. node) in the

  /// graph. This id is <ul><li>\b unique: different items (nodes) get

  /// different ids <li>\b continuous: the range of the ids is the set of

  /// integers between 0 and \c n-1, where \c n is the number of the items of

  /// this type (e.g. nodes) (so the id of a node can change if you delete an

  /// other node, i.e. this id is mutable).  </ul> This map can be inverted

  /// with its member class \c InverseMap, or with the \c operator() member.

  ///

  /// Edge.

  template <typename _Graph, typename _Item>

  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {

    typedef _Item Item;

    typedef DefaultMap<_Graph, _Item, int> Map;

  public:

      return InverseMap(*this);

    }

  };

  /// \brief Returns the source of the given arc.

  ///

  /// The SourceMap gives back the source Node of the given arc. 

  /// \see TargetMap

  template <typename Digraph>

  class SourceMap {

  public:

    typedef typename Digraph::Node Value;

    typedef typename Digraph::Arc Key;

    /// \brief Constructor

  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {

    return SourceMap<Digraph>(digraph);

  } 

  /// \brief Returns the target of the given arc.

  ///

  /// The TargetMap gives back the target Node of the given arc. 

  /// \see SourceMap

  template <typename Digraph>

  class TargetMap {

  public:

    typedef typename Digraph::Node Value;

    typedef typename Digraph::Arc Key;

    /// \brief Constructor

  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {

    return TargetMap<Digraph>(digraph);

  }

  /// \brief Returns the "forward" directed arc view of an edge.

  ///

  /// Returns the "forward" directed arc view of an edge.

  /// \see BackwardMap

  template <typename Graph>

  class ForwardMap {

  public:

    typedef typename Graph::Arc Value;

    typedef typename Graph::Edge Key;

    /// \brief Constructor

  inline ForwardMap<Graph> forwardMap(const Graph& graph) {

    return ForwardMap<Graph>(graph);

  }

  /// \brief Returns the "backward" directed arc view of an edge.

  ///

  /// Returns the "backward" directed arc view of an edge.

  /// \see ForwardMap

  template <typename Graph>

  class BackwardMap {

  public:

    typedef typename Graph::Arc Value;

    typedef typename Graph::Edge Key;

    /// \brief Constructor

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

  ///

  ///

  ///\sa ArcLookUp  

  ///\sa AllArcLookUp  

  template<class G>

  class DynArcLookUp 

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

  {

  public:

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

  ///

  ///

  ///\sa DynArcLookUp

  ///\sa AllArcLookUp  

  template<class G>

  class ArcLookUp 

  {

  public:

    TEMPLATE_DIGRAPH_TYPEDEFS(G);

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

  ///

  ///

  ///\sa DynArcLookUp

  ///\sa ArcLookUp  

  template<class G>

  class AllArcLookUp : public ArcLookUp<G>

  {

    using ArcLookUp<G>::_g;

    using ArcLookUp<G>::_right;

  /// \addtogroup paths

  /// @{

  /// \brief A structure for representing directed paths in a digraph.

  ///

  /// A structure for representing directed path in a digraph.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence, it

  /// cannot enumerate the nodes of the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is a back and front insertable and erasable

  /// path type. It can be indexed in O(1) time. The front and back

    typedef std::vector<Arc> Container;

    Container head, tail;

  };

  /// \brief A structure for representing directed paths in a digraph.

  ///

  /// A structure for representing directed path in a digraph.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence it

  /// cannot enumerate the nodes in the path and the zero length paths

  /// cannot store the source.

  ///

  /// This implementation is a just back insertable and erasable path

  /// type. It can be indexed in O(1) time. The back insertion and

    typedef std::vector<Arc> Container;

    Container data;

  };

  /// \brief A structure for representing directed paths in a digraph.

  ///

  /// A structure for representing directed path in a digraph.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence it

  /// cannot enumerate the nodes in the path and the zero length paths

  /// cannot store the source.

  ///

  /// This implementation is a back and front insertable and erasable

  /// path type. It can be indexed in O(k) time, where k is the rank

      }

    }

  };

  /// \brief A structure for representing directed paths in a digraph.

  ///

  /// A structure for representing directed path in a digraph.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence it

  /// cannot enumerate the nodes in the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is completly static, i.e. it can be copy constucted

  /// or copy assigned from another path, but otherwise it cannot be

  ///It is also quite memory efficient, but at the price

  ///that <b> it does support only limited (only stack-like)

  ///node and arc deletions</b>.

  ///It conforms to the \ref concepts::Digraph "Digraph concept" with

  ///an important extra feature that its maps are real \ref

  ///concepts::ReferenceMap "reference map"s.

  ///

  ///\sa concepts::Digraph.

  class SmartDigraph : public ExtendedSmartDigraphBase {

  public:

    typedef ExtendedSmartDigraphBase Parent;

  private:

    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.

  /// - a user cpu time of children

  /// - a system cpu time of children

  ///

  /// TimeStamp's can be added to or substracted from each other and

  /// they can be pushed to a stream.

  ///

  /// In most cases, perhaps the \ref Timer or the \ref TimeReport

  /// class is what you want to use instead.

  class TimeStamp

  {

    double utime;

    double stime;

    double cutime;

    double cstime;

    double rtime;

  ///Also, if you start and stop the timer very frequently, it could lead to

  ///distorted results.

  ///

  ///\note If you want to measure the running time of the execution of a certain

  ///function, consider the usage of \ref TimeReport instead.

  ///

  ///\todo This shouldn't be Unix (Linux) specific.

  ///\sa TimeReport

  class Timer

  {

    int _running; //Timer is running iff _running>0; (_running>=0 always holds)

    TimeStamp start_time; //This is the relativ start-time if the timer

                          //is _running, the collected _running time otherwise.

    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}