RhodeCode

                         @abs_top_srcdir@/test/test_tools.h

INPUT_ENCODING         = UTF-8

FILE_PATTERNS          = *.h \

                         *.cc \

                         *.dox

RECURSIVE              = NO

EXCLUDE                = 

EXCLUDE_SYMLINKS       = NO

EXCLUDE_PATTERNS       = 

EXCLUDE_SYMBOLS        = 

EXAMPLE_PATH           = @abs_top_srcdir@/demo \

                         @abs_top_srcdir@/LICENSE \

                         @abs_top_srcdir@/doc

EXAMPLE_PATTERNS       = 

EXAMPLE_RECURSIVE      = NO

IMAGE_PATH             = @abs_top_srcdir@/doc/images \

INPUT_FILTER           = 

FILTER_PATTERNS        = 

FILTER_SOURCE_FILES    = NO

#---------------------------------------------------------------------------

# configuration options related to source browsing

#---------------------------------------------------------------------------

SOURCE_BROWSER         = NO

INLINE_SOURCES         = NO

STRIP_CODE_COMMENTS    = YES

REFERENCED_BY_RELATION = NO

REFERENCES_RELATION    = NO

REFERENCES_LINK_SOURCE = YES

USE_HTAGS              = NO

VERBATIM_HEADERS       = NO

#---------------------------------------------------------------------------

# configuration options related to the alphabetical class index

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@edges is just a synonym of \c \@arcs. The @arcs section can

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

has the same caption with \c '+' and \c '-' prefix, then these columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

    inline const char* cstringify(const std::string& str) {

      return str.c_str();

    }

    inline const char* cstringify(const char* str) {

      return str;

    }

  }

}

#endif // LEMON_ASSERT_H

#undef LEMON_ASSERT

#undef LEMON_FIXME

#undef LEMON_DEBUG

  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1

#error "LEMON assertion system is not set properly"

#endif

   defined(NDEBUG))

#error "LEMON assertion system is not set properly"

#endif

#if defined LEMON_ASSERT_LOG

#  undef LEMON_ASSERT_HANDLER

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log

#elif defined LEMON_ASSERT_ABORT

#  undef LEMON_ASSERT_HANDLER

#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort

#elif defined LEMON_ASSERT_CUSTOM

#  undef LEMON_ASSERT_HANDLER

#  ifndef LEMON_CUSTOM_ASSERT_HANDLER

#    error "LEMON_CUSTOM_ASSERT_HANDLER is not set"

#  endif

///                                const char* function, const char* message,

///                                const char* assertion);

///   \endcode

///   The name of the function should be defined as the \c

///   LEMON_CUSTOM_ASSERT_HANDLER macro name.

///   \code

///     #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler

///   \endcode

///   Whenever an assertion is occured, the custom assertion

///   handler is called with appropiate parameters.

///

/// The assertion mode can also be changed within one compilation unit.

/// If the macros are redefined with other settings and the

/// \ref lemon/assert.h "assert.h" file is reincluded, then the

/// behaviour is changed appropiately to the new settings.

#  define LEMON_ASSERT(exp, msg)                                        \

                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))

/// \ingroup exceptions

///

/// \brief Macro for mark not yet implemented features.

///

/// Macro for mark not yet implemented features and outstanding bugs.

/// It is close to be the shortcut of the following code:

/// \code

///   LEMON_ASSERT(false, msg);

/// \endcode

///

/// \see LEMON_ASSERT

  (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \

                        static_cast<const char*>(0)))

/// \ingroup exceptions

///

/// \brief Macro for internal assertions

///

/// Macro for internal assertions, it is used in the library to check

/// the consistency of results of algorithms, several pre- and

/// postconditions and invariants. The checking is disabled by

/// default, but it can be turned on with the macro \c

/// LEMON_ENABLE_DEBUG.

/// \code

/// #define LEMON_ENABLE_DEBUG

/// \endcode

/// or with compilation parameters:

/// \code

/// g++ -DLEMON_ENABLE_DEBUG

/// make CXXFLAGS='-DLEMON_ENABLE_DEBUG'

/// \endcode

///

/// This macro works like the \c LEMON_ASSERT macro, therefore the

/// current behaviour depends on the settings of \c LEMON_ASSERT

/// macro.

///

/// \see LEMON_ASSERT

    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                            \

                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))

#else

#  ifndef LEMON_ASSERT_HANDLER

#    define LEMON_ASSERT(exp, msg)  (static_cast<void>(0))

#    define LEMON_FIXME(msg) (static_cast<void>(0))

#    define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#  else

        LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                        \

                             #exp), 0)))

                             static_cast<const char*>(0)))

#    if LEMON_ENABLE_DEBUG

#      define LEMON_DEBUG(exp, msg)

                                #exp), 0)))

#    else

#      define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#    endif

#  endif

#endif

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const Path &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        ArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          Path<Digraph> pc;

          _Path p, pp(pc);

          int l = p.length();

          int e = p.empty();

          p.clear();

          p = pc;

          typename _Path::ArcIt id, ii(INVALID), i(p);

        ArcIt() {}

        /// Invalid constructor

        ArcIt(Invalid) {}

        /// Constructor for first arc

        ArcIt(const PathDumper&) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        ArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const ArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const ArcIt&) const {return true;}

      };

      /// \brief Lemon style iterator for path arcs

      ///

      /// This class is used to iterate on the arcs of the paths in

      /// reverse direction.

      class RevArcIt {

      public:

        /// Default constructor

        RevArcIt() {}

        /// Invalid constructor

        RevArcIt(Invalid) {}

        /// Constructor for first arc

        RevArcIt(const PathDumper &) {}

        /// Conversion to Arc

        operator Arc() const { return INVALID; }

        /// Next arc

        RevArcIt& operator++() {return *this;}

        /// Comparison operator

        bool operator==(const RevArcIt&) const {return true;}

        /// Comparison operator

        bool operator!=(const RevArcIt&) const {return true;}

      };

      template <typename _Path>

      struct Constraints {

        void constraints() {

          function_requires<_path_bits::

            PathDumperConstraints<Digraph, _Path> >();

        }

      };

    };

    ///@}

  }

      } catch (...) {}

    }

    ExceptionMember(const ExceptionMember& copy) throw() {

      try {

        if (!copy.valid()) return;

        ptr.reset(new Type());

        if (ptr.get() == 0) return;

        *ptr = copy.get();

      } catch (...) {}

    }

    ExceptionMember& operator=(const ExceptionMember& copy) throw() {

      if (ptr.get() == 0) return;

      try {

        if (!copy.valid()) return;

      } catch (...) {}

    }

    void set(const Type& type) throw() {

      if (ptr.get() == 0) return;

      try {

        *ptr = type;

      } catch (...) {}

    }

    const Type& get() const {

      return *ptr;

    }

    bool valid() const throw() {

      return ptr.get() != 0;

        std::sort(el.begin(),el.end(),arcLess(g));

        typename std::vector<Arc>::iterator j;

        for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {

          for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;

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

          //\todo better 'epsilon' would be nice here.

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

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

            d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;

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

            sw+=_arcWidths[*e]*_arcWidthScale/2.0;

            dim2::Point<double> mm=m+rot90(d)*sw/.75;

            if(_drawArrows) {

              int node_shape;

              dim2::Point<double> s=mycoords[g.source(*e)];

              dim2::Point<double> t=mycoords[g.target(*e)];

              double rn=_nodeSizes[g.target(*e)]*_nodeScale;

              node_shape=_nodeShapes[g.target(*e)];

              dim2::Bezier3 bez(s,mm,mm,t);

              double t1=0,t2=1;

              for(int ii=0;ii<INTERPOL_PREC;++ii)

                if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;

                else t1=(t1+t2)/2;

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.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

  typedef Digraph::ArcMap<double> DoubleArcMap

  ///Creates convenience typedefs for the digraph types and iterators

  ///\see DIGRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

  typedef typename Digraph::ArcIt ArcIt;                                \

  typedef typename Digraph::template ArcMap<double> DoubleArcMap

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

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

  typedef Graph::EdgeMap<double> DoubleEdgeMap

  ///Creates convenience typedefs for the graph types and iterators

  ///\see GRAPH_TYPEDEFS

  ///

  ///\note Use this macro, if the graph type is a dependent type,

  ///ie. the graph type depend on a template parameter.

  typedef typename Graph::EdgeIt EdgeIt;                                \

  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap

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

  }

      virtual void set(const std::string&) = 0;

    };

    template <typename _Value, typename _Converter = DefaultConverter<_Value> >

    class ValueStorage : public ValueStorageBase {

    public:

      typedef _Value Value;

      typedef _Converter Converter;

    private:

      Value& _value;

      Converter _converter;

    public:

      ValueStorage(Value& value, const Converter& converter = Converter())

      virtual void set(const std::string& value) {

        _value = _converter(value);

      }

    };

    template <typename Value>

    struct MapLookUpConverter {

      const std::map<std::string, Value>& _map;

      MapLookUpConverter(const std::map<std::string, Value>& map)

        : _map(map) {}

      Value operator()(const std::string& str) {

        typename std::map<std::string, Value>::const_iterator it =

          _map.find(str);

    /// \brief Constructor

    ///

    /// Construct a directed graph reader, which reads from the given

    /// input stream.

    DigraphReader(std::istream& is, Digraph& digraph)

      : _is(&is), local_is(false), _digraph(digraph),

        _use_nodes(false), _use_arcs(false),

        _skip_nodes(false), _skip_arcs(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph reader, which reads from the given

    /// file.

    DigraphReader(const std::string& fn, Digraph& digraph)

      : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),

        _skip_nodes(false), _skip_arcs(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph reader, which reads from the given

    /// file.

    DigraphReader(const char* fn, Digraph& digraph)

      : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),

        _skip_nodes(false), _skip_arcs(false) {}

    /// \brief Destructor

    ~DigraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin();

           it != _node_maps.end(); ++it) {

        delete it->second;

      }

      for (typename ArcMaps::iterator it = _arc_maps.begin();

           it != _arc_maps.end(); ++it) {

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// input stream.

    GraphReader(std::istream& is, Graph& graph)

      : _is(&is), local_is(false), _graph(graph),

        _use_nodes(false), _use_edges(false),

        _skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// file.

    GraphReader(const std::string& fn, Graph& graph)

      : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),

        _skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// file.

    GraphReader(const char* fn, Graph& graph)

      : _is(new std::ifstream(fn)), local_is(true), _graph(graph),

        _skip_nodes(false), _skip_edges(false) {}

    /// \brief Destructor

    ~GraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin();

           it != _node_maps.end(); ++it) {

        delete it->second;

      }

      for (typename EdgeMaps::iterator it = _edge_maps.begin();

           it != _edge_maps.end(); ++it) {

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

      virtual std::string get() = 0;

    };

    template <typename _Value, typename _Converter = DefaultConverter<_Value> >

    class ValueStorage : public ValueStorageBase {

    public:

      typedef _Value Value;

      typedef _Converter Converter;

    private:

      const Value& _value;

      Converter _converter;

    public:

      ValueStorage(const Value& value, const Converter& converter = Converter())

      virtual std::string get() {

        return _converter(_value);

      }

    };

    template <typename Value>

    struct MapLookUpConverter {

      const std::map<Value, std::string>& _map;

      MapLookUpConverter(const std::map<Value, std::string>& map)

        : _map(map) {}

      std::string operator()(const Value& str) {

        typename std::map<Value, std::string>::const_iterator it =

          _map.find(str);

    ///then the source of each outgoing arc of \c n is moved to this new node.

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

    ///

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

    ///Snapshot feature.

    ///

    ///\todo It could be implemented in a bit faster way.

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

      Node b = addNode();

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

        ++f;

        changeSource(e,b);

        e=f;

      }

      if (connect) addArc(n,b);

      return b;

    }

    ///Split an arc.

    ///This function splits an arc. First a new node \c b is added to

    ///the digraph, then the original arc is re-targeted to \c

    ///b. Finally an arc from \c b to the original target is added.

    ///

    ///\return The newly created node.

    ///

DIGRAPH_TYPEDEFS(Digraph);

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "8\n"

  "9\n"

  "@arcs\n"

  "@attributes\n"

  "source 3\n";

int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};

int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};

int test_len = sizeof(test_seq) / sizeof(test_seq[0]);

template <typename Heap>

void heapSortTest() {

  RangeMap<int> map(test_len, -1);

  Heap heap(map);

  std::vector<int> v(test_len);

template <typename Heap>

void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,

                      Node source) {

  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::

    Create dijkstra(digraph, length);

  dijkstra.run(source);

  for(ArcIt a(digraph); a != INVALID; ++a) {

    Node s = digraph.source(a);

    Node t = digraph.target(a);

    if (dijkstra.reached(s)) {

      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],

    }

  }

  for(NodeIt n(digraph); n != INVALID; ++n) {

    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {

      Arc a = dijkstra.predArc(n);

      Node s = digraph.source(a);

      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],

             "Error in a shortest path tree!");

    }

  }

}

int main() {