RhodeCode

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

    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;

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

    }

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

    int _list_front, _list_back;

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

    }

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

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

///\file

///\brief Basic utilities for concept checking.

///

#ifndef LEMON_CONCEPT_CHECK_H

#define LEMON_CONCEPT_CHECK_H

///\ingroup concept

///\file

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

///

#ifndef LEMON_CONCEPT_PATH_H

#define LEMON_CONCEPT_PATH_H

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

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

    int _stack_head;

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

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

    }

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

    int _stack_head;

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

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

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

    Heap *_heap;

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

    bool local_heap;

    void create_maps()

    {

      if(!_pred) {

        local_pred = true;

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

    }

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

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

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

  class ErrorMessage {

  protected:

    ///\e

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

    ///\e

    bool init() throw() {

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

    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;

      }

    }

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

          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;

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

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

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

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

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

  ///

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

  ///\endcode

  ///

  ///\sa Timer

  ///\sa NoTimeReport

  class TimeReport : public Timer

  {

    std::string _title;

    std::ostream &_os;

///\file

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

///floating point numbers.

///

namespace lemon {

  /// \addtogroup misc