RhodeCode

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \ref PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \ref ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

    ProcessedMap *_processed;

    //Indicates if _processed is locally allocated (true) or not.

    bool local_processed;

    std::vector<typename Digraph::Node> _queue;

    int _queue_head,_queue_tail,_queue_next_dist;

    int _curr_dist;

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \ref PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    std::vector<typename Digraph::Node> _list;

    int _list_front, _list_back;

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    /// If the given bool is true, the first node of the given edge and

    /// the source node of the returned arc are the same.

    static Arc direct(const Edge &e, bool d) {

      return Arc(e, d);

    }

    /// Returns whether the given directed arc has the same orientation

    /// as the corresponding edge.

    static bool direction(const Arc &a) { return a.forward; }

    using Parent::first;

    using Parent::next;

    void first(Arc &e) const {

      Parent::first(e);

      e.forward=true;

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

  ///

  /// \tparam _Item The item type of the graph items.

  /// \tparam _Value The value type of the map.

  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;

//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)

//

// See http://www.boost.org/libs/concept_check for documentation.

///\file

///\brief Basic utilities for concept checking.

///

#ifndef LEMON_CONCEPT_CHECK_H

#define LEMON_CONCEPT_CHECK_H

namespace lemon {

  /*

    "inline" is used for ignore_unused_variable_warning()

 * purpose.

 *

 */

///\ingroup concept

///\file

///\brief Classes for representing paths in digraphs.

///

#ifndef LEMON_CONCEPT_PATH_H

#define LEMON_CONCEPT_PATH_H

#include <lemon/core.h>

#include <lemon/concept_check.h>

namespace lemon {

    ///arcs of the %DFS paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \ref PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \ref ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

    //Pointer to the map of processed status of the nodes.

    ProcessedMap *_processed;

    //Indicates if _processed is locally allocated (true) or not.

    bool local_processed;

    std::vector<typename Digraph::OutArcIt> _stack;

    int _stack_head;

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

    ///arcs of the %DFS paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \ref PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    std::vector<typename Digraph::Arc> _stack;

    int _stack_head;

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \ref PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \ref ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

    HeapCrossRef *_heap_cross_ref;

    //Indicates if _heap_cross_ref is locally allocated (true) or not.

    bool local_heap_cross_ref;

    //Pointer to the heap.

    Heap *_heap;

    //Indicates if _heap is locally allocated (true) or not.

    bool local_heap;

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

        _pred = Traits::createPredMap(*G);

      }

      if(!_dist) {

        local_dist = true;

    /// The cross reference type used by the heap.

    /// Usually it is \c Digraph::NodeMap<int>.

    typedef typename Digraph::template NodeMap<int> HeapCrossRef;

    ///Instantiates a \ref HeapCrossRef.

    ///This function instantiates a \ref HeapCrossRef.

    /// \param g is the digraph, to which we would like to define the

    /// HeapCrossRef.

    static HeapCrossRef *createHeapCrossRef(const Digraph &g)

    {

      return new HeapCrossRef(g);

    }

    ///The heap type used by the Dijkstra algorithm.

    ///The heap type used by the Dijkstra algorithm.

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \ref PredMap.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \ref ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

  /// Default traits class used by \ref DijkstraWizard

  /// To make it easier to use Dijkstra algorithm

  /// we have created a wizard class.

  /// This \ref DijkstraWizard class needs default traits,

  /// as well as the \ref Dijkstra class.

  /// The \ref DijkstraWizardBase is a class to be the default traits of the

  /// \ref DijkstraWizard class.

  template<class GR,class LM>

  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>

  {

    typedef DijkstraWizardDefaultTraits<GR,LM> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

  /// Helper class which provides a convenient ostream-like (operator <<

  /// based) interface to create a string message. Mostly useful in

  /// exception classes (therefore the name).

  class ErrorMessage {

  protected:

    ///\e

    mutable std::auto_ptr<std::ostringstream> buf;

    ///\e

    bool init() throw() {

      try {

        buf.reset(new std::ostringstream);

      }

      catch(...) {

  ///Draws the graph.

  ///Like other functions using

  ///\ref named-templ-func-param "named template parameters",

  ///this function calls the algorithm itself, i.e. in this case

  ///it draws the graph.

  void run() {

    const double EPSILON=1e-9;

    if(dontPrint) return;

    _graph_to_eps_bits::_NegY<typename T::CoordsMapType>

      mycoords(_coords,_negY);

    os << "%!PS-Adobe-2.0 EPSF-2.0\n";

    if(_title.size()>0) os << "%%Title: " << _title << '\n';

      }

#endif

    }

    if (_autoArcWidthScale) {

      double max_w=0;

      for(ArcIt e(g);e!=INVALID;++e)

        max_w=std::max(double(_arcWidths[e]),max_w);

      if(max_w>EPSILON) {

        _arcWidthScale/=max_w;

      }

    }

    if (_autoNodeScale) {

      double max_s=0;

      for(NodeIt n(g);n!=INVALID;++n)

        max_s=std::max(double(_nodeSizes[n]),max_s);

      if(max_s>EPSILON) {

        _nodeScale/=max_s;

      }

    }

    double diag_len = 1;

    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {

      dim2::Box<double> bb;

                  (A4WIDTH-2*A4BORDER)/bb.width());

        os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '

           << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER

           << " translate\n"

           << sc << " dup scale\n"

           << -bb.left() << ' ' << -bb.bottom() << " translate\n";

      }

      else {

        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),

                  (A4WIDTH-2*A4BORDER)/bb.height());

        os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '

           << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER

           << " translate\n"

           << sc << " dup scale\n90 rotate\n"

           << -bb.left() << ' ' << -bb.top() << " translate\n";

        }

          double sw=0;

          for(typename std::vector<Arc>::iterator e=i;e!=j;++e)

            sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;

          sw-=_parArcDist;

          sw/=-2.0;

          dim2::Point<double>

            dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);

          double l=std::sqrt(dvec.normSquare());

          dim2::Point<double> d(dvec/std::max(l,EPSILON));

          dim2::Point<double> m;

//           m=dim2::Point<double>(mycoords[g.target(*i)]+

//                                 mycoords[g.source(*i)])/2.0;

//            m=dim2::Point<double>(mycoords[g.source(*i)])+

//             dvec*(double(_nodeSizes[g.source(*i)])/

//                (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));

    ///If \c connect is \c true (this is the default value), then a new arc

    ///from \c n to the newly created node is also added.

    ///\return The newly created node.

    ///

    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain

    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may

    ///be invalidated.

    ///

    ///Snapshot feature.

    Node split(Node n, bool connect = true) {

      Node b = addNode();

      for(OutArcIt e(*this,n);e!=INVALID;) {

        OutArcIt f=e;

        ++f;

        changeSource(e,b);

        e=f;

      }

  /// The \c Key type of the map is inherited from \c M2 and the

  /// \c Value type is from \c M1.

  /// \c M2::Value must be convertible to \c M1::Key.

  ///

  /// The simplest way of using this map is through the composeMap()

  /// function.

  ///

  /// \sa CombineMap

  template <typename M1, typename M2>

  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {

    const M1 &_m1;

    const M2 &_m2;

  public:

    typedef MapBase<typename M2::Key, typename M1::Value> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

  /// \c M2::Value and \c M1::Value must be convertible to the

  /// corresponding input parameter of \c F and the return type of \c F

  /// must be convertible to \c V.

  ///

  /// The simplest way of using this map is through the combineMap()

  /// function.

  ///

  /// \sa ComposeMap

  template<typename M1, typename M2, typename F,

           typename V = typename F::result_type>

  class CombineMap : public MapBase<typename M1::Key, V> {

    const M1 &_m1;

    const M2 &_m2;

    F _f;

  public:

    typedef MapBase<typename M1::Key, V> Parent;

      return operator()() < p;

    }

    /// Standard Gauss distribution

    /// Standard Gauss distribution.

    /// \note The Cartesian form of the Box-Muller

    /// transformation is used to generate a random normal distribution.

    double gauss()

    {

      double V1,V2,S;

      do {

        V1=2*real<double>()-1;

        V2=2*real<double>()-1;

        S=V1*V1+V2*V2;

      } while(S>=1);

    ///\return The newly created node.

    ///

    ///\note The <tt>Arc</tt>s

    ///referencing a moved arc remain

    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s

    ///may be invalidated.

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    Node split(Node n, bool connect = true)

    {

      Node b = addNode();

      nodes[b._id].first_out=nodes[n._id].first_out;

      nodes[n._id].first_out=-1;

      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;

      if(connect) addArc(n,b);

      return b;

  ///granularity.

  ///Therefore this tool is not appropriate to measure very short times.

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

  ///

  ///\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();}

  ///  {

  ///    TimeReport tr("Running time of myAlg: ");

  ///    ... //Here comes the algorithm

  ///  }

  ///\endcode

  ///

  ///\sa Timer

  ///\sa NoTimeReport

  class TimeReport : public Timer

  {

    std::string _title;

    std::ostream &_os;

  public:

    ///\e

    ///\param title This text will be printed before the ellapsed time.

#ifndef LEMON_TOLERANCE_H

#define LEMON_TOLERANCE_H

///\ingroup misc

///\file

///\brief A basic tool to handle the anomalies of calculation with

///floating point numbers.

///

namespace lemon {

  /// \addtogroup misc

  /// @{

  ///\brief A class to provide a basic way to

  ///handle the comparison of numbers that are obtained